Search algorithms don’t necessarily feel like very cool AI methods.

However,
they can be used to solve tasks that most of us would admit require intelligence
like navigation or playing chess

I. Search and problem solving

Many problems can be phrased as search problems. This requires that we start
by formulating the alternative choices and their consequences.

Search in practice: getting from A to B Intro

Imagine you’re in a foreign city, at some address and want to use public
transport to get to another address. If you are like many people, you pull out
your smartphone, type in the destination and start following the instructions.

This question belongs to the class of search and planning problems. Similar
problems need to be solved by self-driving cars, and (perhaps less obviously) AI
for playing games. In the game of chess, for example, the difficulty is not so
much in getting a piece from A to B as keeping your pieces safe from the
opponent.

Often there are many different ways to solve the problem, some of which may be
more preferable in terms of time, effort, cost or other criteria. Different search
techniques may lead to different solutions, and developing advanced search
algorithms is an established research area.

We will not focus on the actual search algorithms. Instead, we emphasize the
first stage of the problem solving process: defining the choices and their
consequences, which is often far from trivial and can require careful thinking. We
also need to define what our goal is, or in other words, when we can consider
the problem solved. After this has been done, we can look for a sequence of
actions that leads from the initial state to the goal.

In this chapter, we will discuss two kinds of problems:

 Search and planning in static environments with only one

“agent”
 Games with two-players (“agents”) competing against each other

These categories don’t cover all possible real-world scenarios, but they are
generic enough to demonstrate the main concepts and techniques.

Before we address complex search tasks like navigation or playing chess, let
us start from a much simplified model in order to build up our understanding
of how we can solve problems by AI.
Toy problem: chicken crossing

We’ll start from a simple puzzle to illustrate the ideas. A robot on a rowboat
needs to move three pieces of cargo across a river: a fox, a chicken, and a sack
of chicken-feed. The fox will eat the chicken if it has the chance, and the chicken
will eat the chicken-feed if it has the chance, and neither is a desirable outcome.
The robot is capable of keeping the animals from doing harm when it is near
them, but only the robot can operate the rowboat and only two of the pieces of
cargo can fit on the rowboat together with the robot. How can the robot move all
of its cargo to the opposite bank of the river?
We will model the puzzle by noting that five movable things have been identified:
the robot, the rowboat, the fox, the chicken, and the chicken-feed. In principle,
each of the five can be on either side of the river, but since only the robot can
operate the rowboat, the two will always be on the same side. Thus there are
four things with two possible positions for each, which makes for sixteen
combinations, which we will call states:

States of the chicken crossing puzzle

We have given short names to the states, because otherwise it would be

cumbersome to talk about them. Now we can say that the starting state is NNNN
and the goal state is FFFF, they all are on the Near Side, and in the goal state
the robot is on the far side”, and so on.

Some of these states are forbidden by the puzzle conditions. For example, in
state NFFN (meaning that the robot is on the near side with the chicken-feed but
the fox and the chicken are on the far side), the fox will eat the chicken, which
we cannot have. Thus we can rule out states NFFN, NFFF, FNNF, FNNN,
NNFF, and FFNN (you can check each one if you doubt our reasoning).

State Robot Fox Chicken Chicken-feed

NNNN Near side Near side Near side Near side
NNNF Near side Near side Near side Far side
NNFN Near side Near side Far side Near side
NNFF NO Near side Near side Far side Far side
NFNN Near side Far side Near side Near side
NFNF Near side Far side Near side Far side
NFFN NO Near side Far side Far side Near side
NFFF NO Near side Far side Far side Far side
FNNN NO Far side Near side Near side Near side
FNNF Far side Near side Near side Far side
FNFN Far side Near side Far side Near side
FNFF NO Far side Near side Far side Far side
FFNN NO Far side Far side Near side Near side
FFNF Far side Far side Near side Far side
FFFN Far side Far side Far side Near side
FFFF Far side Far side Far side Far side

We are left with the following ten states:

State Robot Fox Chicken Chicken-feed

NNNN Near side Near side Near side Near side
NNNF Near side Near side Near side Far side
NNFN Near side Near side Far side Near side
NFNN Near side Far side Near side Near side
NFNF Near side Far side Near side Far side
FNFN Far side Near side Far side Near side
FNFF Far side Near side Far side Far side
FFNF Far side Far side Near side Far side
FFFN Far side Far side Far side Near side
FFFF Far side Far side Far side Far side

Next we will figure out which state transitions are possible, meaning simply that
as the robot rows the boat with some of the items as cargo, what the resulting
state is in each case. It’s best to draw a diagram of the transitions, and since in
any transition the first letter alternates between N and F, it is convenient to draw
the states starting with N (so the robot is on the near side) in one row and the
states starting with F in another row:

Now let's draw the transitions. We could draw arrows that have a direction so
that they point from one node to another, but in this puzzle the transitions are
symmetric: if the robot can row from state NNNN to state FNFF, it can equally
well row the other way from FNFF to NNNN. Thus it is simpler to draw the
transitions simply with lines that don't have a direction. Starting from NNNN, we
can go to FNFN, FNFF, FFNF, and FFFN:

Then we fill in the rest:

We don’t seem any closer to the solution, and there is little doubt that you could
have solved the whole puzzle already by using your “natural intelligence”.
But for more complex problems, where the number of possible solutions grows
in the thousands and in the millions, our systematic or mechanical approach will
shine since the hard part will be suitable for a simple computer to do. Now that
we have formulated the alternative states and transitions between them, the rest
becomes a mechanical task: find a path from the initial state NNNN to the final
state FFFF.
One such path is colored in the following picture. The path proceeds from NNNN
to FFFN (the robot takes the fox and the chicken to the other side), thence to
NFNN (the robot takes the chicken back on the starting side) and finally to FFFF
(the robot can now move the chicken and the chicken-feed to the other side).

State space, transitions, and costs

To formalize a planning problem, we use concepts such as the state space,

transitions, and costs.
The state space
Means to set the create a comfortable situation.
If the task, is to navigate from A to B, could be the definition of the coordinates
that can be reached from the start.
Or we could use a constrained set of location, for ex, street’s address.
Transition
Transitions are possible moves between one state to another, it is important to
note that we only consider the transitions that can be accomplished with a
single action, a sequence of multiple actions ( transitions)is a path
Costs
The transitions are not all the same, some could be cheaper or more costly( not just in the
monetary sense).
We could express this by associating with each transition a certain cost.
The goal is to minimize the distance traveled, or could be minimize the time instead of the
distance.
If all the transitions are equal, than we can ignore costs.

[Link] problems with AI

Interlude on the history of AI: starting from search

AI is arguably as old as computer science.
Long before we had computers, people thought about automatic reasoning and intelligence,
computer science include the insight that anything that can be computed ( computed= calculated
using either numbers or symbols) can be automated

Note
Helping win WWII

Turing designed a simple device that is capable of computing anything that is computable.
His device is known as the Turing machine, this led Turing to the inventin of programmable
computers, that can be used to carry out different tasks depending on what they were programmed
to do.
In this way instead of building a different device for each task, we can usetha same machine for
many task, nowadays it sounds trivial but it wasn’t.
Some of the programmable computers used during WWII to crack German codes, were projected
by Turing

The term AI was coined by John McCarthy who is referred as the Father of AI, the term became established
when it was chosen as the topic of a summer seminar, known as Dartmouth conference.

In the proposal to organize the seminar, MCCarthy continued with Tring’s argument computation, the
proposal contains the flowing crucial statement

Note
John McCarthy’s key statement about AI
“The study is to proceed on the basis of the conjecture that every aspect of learning or any
other feature of intelligence can in principle be so precisely described that a machine can
be made to simulate it.”

In other words, any element of intelligence can be divided into smalls steps, in this way each step
will be simple and “mechanical” to be written down as a computer program
This statement is a conjecture, which means that we can’t really prove it to be true.
Neverthless, the idea is fundamental when it comes to the way we think about AI.
For ex it shows that McCarthy wanted to bypass any arguments in the spirit of the Chinese Room:
intelligence is intelligence even when the system that implement it is just a computer that follows
a program.

Why search and games became central in AI research

As computers developed to the level where it was feasible in 1950s, the most distinctive AI
problems were games.
Games provided a convenient restricted domain that could be formalized easily.

Board games have inspired countless researchers.

Closely to games, search and planning techniques were an area where AI lead to great
advances in 60’s.

Algorithms such as Minimax or Alpha-Beat Pruning, are still the basis for game playing AI,
although more advanced variants have been proposed over the years

[Link] and games

Example: playing tic tac toe

Maxine and Minnie are true game enthusiasts. They just love games. Especially two-person,
perfect information games such as tic-tac-toe or chess. One day they were playing tic-tac-toe.
Maxine, or Max as her friends call her, was playing with X. Minnie, or Min as her friends call her,
had the Os. Min had just played her turn and the board looked as follows:

Max was looking at the board and contemplating her next move, as it was her turn, when
she suddenly buried her face in her hands in despair, looking quite like Garry Kasparov
playing Deep Blue in 1997.

Yes, Min was close to getting three Os on the top row, but Max could easily put a stop to
that plan. So why was Max so pessimistic?

Game trees

To solve games using AI, we will introduce the concept of game tree.

The different states of the game are represented by nodes in the game tree.

In the game tree node are arranged in levels that correspond to each player’s turn in the
game

In this way the “root” (often depicted at the top of the diagram) is the beginning position.
In tic-tac-toe, this would be a empty grid, under root, there are the possible states that can
result from the first player’s moves, this noted are called “children” of the main node.

Each node on the second level, would further have as its children nodes, the states that
come from the opposing player’s moves.

This develop level by level

Minimizing and maximizing value

In order to be able to create game AI that attempts to win game, we attach numerical value
to each possible and result.

In the board where X has a line of three Max wins, and we attach the value +1, to the
positions where Min could win we attach the value -1 and where the board is full and
neither player wins we use the neutral value 0

A sample game tree

Consider for ex. The following game tree which begins not at the root but in the middle.

The tree is composed of alternating layer where it is either Min’s turn to place an O or
Max’s turn to place an X to any vacant slots.

The player whose turn it is to play next is shown at left

The game continues at the board position as shown in the root node (n.1) at the top, with Min’s
turn to place O at a at any of the three vacant cells.
Noed (2-4), show the board positions that came from each of the three choices.
In the next step, each node has two possible choices.
In the next step, each node has two possibility for Max to play X, and so the tree branches again.
When starting from the above starting position, the game always end in a row of three, in node (7
and 9), the winner is Max who plays with X, and in nodes (11 and 14) the winner is Min.

Being strategic

Nodes 5 and 10 on the second level from the bottom. In nodes 7 and 9 the game is over, and Max
wins with three X’s in a row.
The value of these positions is +1 in the remaining nodes 5,6,8 and 10 the game is over too,
because Min only needs to place O in the last cell to win.
Any way, we know how the game will end at each node on the second level from the bottom, nad
the value’s -1

Let’s consider the values of the nodes one level higher towards the root: nodes 2,4 because we
observed that both of the children of 2, 5 and 6, lead Min’s victory, we can attach values without
hesitation, Min’s victory -1 and Max victory’s +1
(
e -1 to node (2) as well. However, for node (3), the left child (7) leads to Max's victory, +1,
but the right child (8) leads to Min winning, -1. What is the value of node (3)? Think about
this for a while, keeping in mind who makes the choice at node (3).)
Since it is Max's turn to play, she will of course choose the left child, node (7). Thus, every
time we reach the board position in node (3), Max can ensure victory, and we can attach
the value +1 to node (3).
The same holds for node (4): again, since Max can choose where to put her X, she can
always ensure victory, and we attach the value +1 to node (4).

Determining who wins

The most important lesson is to apply the above kind of reasoning repeatedly to determinate the
winner.
So we have just valued nodes 2 with -1, values 3 and 4 are +1 which means that Max can be sure
to win if she plays her turn wisely.
In this way we can decide that since Min is an experienced player, she can reach the same
conclusion, and thus she only has one real option: play the O in the middle.
The diagram below will be an optimal game play starting at Min's turn in the root node.

The value of the root node = who wins

The value of the root node, is the “value of the game” tells us who wins, max wins if the value of the game
is +1, Min if it is -1, and with 0 the game will end draw. In other games, the value may also take other values
(monetary for ex.)
This all is based on the auumption that both player choose the best for them, what is the best for one is the
worst for the other this is called “zero-sum game”

Note
Finding the optimal moves

By determinating the values of all the nodes in the game tree, the optimal moves can be
deduced: at any Min node (when is Min’s turn), the optimal choice is given by the child
node whose is minimal, at any Max node,, the best choice is given by the child node
whose value is maximal.
Sometimes there will be two good choices, these will be equally good.