1

AI
SEARCH ALGORITHMS
Informed search vs Uninformed search

2010
• Problem: is defined by its element and their solutions
• A state is a representation of those elements in a
given moment
• Problem solving: is the processes of finding a path
consisting of a sequence of connected states and
ending at one of the goal states.
• State space: is the set of all states reachable from the
initial state to goal state.
• State: Initial state, Goal state
• A path in the state space is a sequence of states
connected by a sequence of actions.

2010 2
• Searching:
– is the search for a solution in a problem space .
– is a systematic examination of states to find paths
from the start state to the goal state, or the desired
goal state.
• A solution in the state space is a path from the
initial state to a goal state or, sometimes, just a
goal state.
• Problem representation: Graph or Tree

2010 3
• A well-defined problem can be described by:
a) State space – all states reachable from initial by
an sequence of actions: S
b) Initial state: S0S
c) Operators (rules) or success factor:A: SiSj
d) Path- sequence through state space: p
e) Path cost- functions that assigns a cost to a path:
f) Goal test- test to determine the goal state :G

2010 4
 Searching for Solutions
• Typical AI problems can have solutions in two
forms.
– The first one is a state, which satisfies the requirements.
– The second one is a path specifying the way in which
one has to traverse to get a solution.
• A good search technique should have the following
requirements.
– A search technique should be systematic
– A search technique should make changes in the
database

2010 5
 Searching…
• Searching strategies are generally evaluated in
terms of the following four criteria:
– Completeness: Is the strategy guaranteed to find a
solution when there is one
– Time Complexity: How long does it take to find a
solution. The time require to run
– Space Complexity: How much memory does it
need to perform the search. The space require to run
– Optimality: Does the strategy find the highest
quality solution when there are several different
solutions
2010 6
• Time and space complexity: are measured in terms of
– b: maximum branching factor of the search tree
– d: depth of the least-cost solution
– m: maximum depth of the state space (may be infinite)
• Big-O: the measure of the execution of an algorithm
time or memory needed, given the problem size n(the
number of item).
• If an algorism require f(n), then O(f(n))
• If n2 , then O(n2)
• If n, then O(n): The run time t should be a direct
proportional to n, i.e. t  n or t = kn , k constant of
proportionality

2010 7
• Calculate the sum of the n elements in an integer
array a[0,…….,n-1]
Line no instruction no of execution steps
1 sum=0 1
2 for(i=0;i<n;i++) n+1
3 sum+=a[i] n
4 print sum 1
sum 2n+3
• Ignoring the constant
• So the big-o of the algorithm is O(n)
• For the 2 D array the big-O is O(n2)

2010 8
 Representation of search problems
• A search problem is represented using a directed
graph.
– The states are represented as nodes.
– The allowed actions are represented as arcs.
• Type of Search strategies:
– uninformed search
• DFS, BFS, Cost FS/Djikstra , DLS, IDDFS/IDS
– Informed search
• Generate and Test , Best FS/Greedy, A*, CSP, Hill-climbing

2010 9
 Route Planning in a Map
• A map is a graph where nodes are cities and links are roads.
This is an abstraction of the real world
• Map gives world dynamics. Starting at city X on the map and
taking some road gets the city Y.
• World (set of cities) is finite and enumerable
• Usually, when working with the map we generally assume that
we know where we are, although it is not always true.
• The states of the world is really enormous. When traveling:
– Bridges may be out
– Roads are closed for construction
– The nature of road
– The traffic situation

2010 10
 Route Finding
• Sample Route

Z O F
S B
A R
L P
T D
M C

2010 11
 Expanding the graph
• Put start state in the agenda
• Loop
– Get a state from the agenda
• If goal, then return
• Expand state (Put children in the agenda)

Which state is chosen from the agenda defines the type of

search and may have huge impact on the effectiveness of
attaining the goal

2010 12
 Uninformed search
• Uninformed (Blind) search
– No problem-specific knowledge that would allow it to
perform to expand one node over another
– There are numerous different Blind searches that may
be used.
– The choice of the search algorithm may lead to vastly
different results depending on the search space.
– The algorithms may have different characteristics in
terms of search Completeness, Search Time
Complexity, Search Space Complexity, and Search
Optimality.

2010 13
Breadth First Search (BFS)

• It is usually implemented using a queue

initialized with one element, the start state.
• States are removed from the front of the
queue and investigated to see if they are
goal states, if so the search terminates, if
not the state is expanded and the resulting
states are added to the back of the queue.

2010 14
 Breadth-first search

•Guaranteed to find shortest solution first

•best-first finds solution a-c-f
•depth-first finds a-b-e-j
2010 15
Example: state space graph

2010 16
 To simplify the search algorithms, it is often
convenient to logically and
programmatically represent a problem
space as a tree.
 A tree is a graph in which any two vertices
are connected exactly one path.
Alternatively, any connected graph with no
cycles is a tree.
2010 17
•The process constructs a search tree is as follows, where
• root is the initial state and
•leaf nodes are nodes
• not yet expanded (i.e., in fringe/agenda) or
•having no successors (i.e., “dead-ends”)

• Search tree may be infinite because of loops even if state

space is small
•The search problem will return as a solution a path to a goal
node.
•Treat agenda as queue
•Expansion: put children at the end of the queue
•Get new nodes from the front of the queue
2010 18
Search tree

2010 19
 BFS illustrated
Step 1: Initially fringe contains only one node corresponding to
the source state A.

Fringe: A

2010 20
 BFS illustrated
Step 2: A is removed from fringe. The node is expanded, and its
children B and C are generated. They are placed at the back of
fringe.

Fringe: BC

2010 21
 BFS illustrated
Step 3: Node B is removed from fringe and is expanded. Its
children D, E are generated and put at the back of fringe.

Fringe: CDE

2010 22
 BFS illustrated
Step 4: Node C is removed from fringe and is expanded. Its
children D and G are added to the back of fringe.

Fringe: DEDG

2010 23
 BFS illustrated
Step 5: Node D is removed from fringe. Its children C and F are
generated and added to the back of fringe.

Fringe: EDGCF

2010 24
 BFS illustrated
Step 6: Node E is removed from fringe. It has no children.

Fringe: DGCF

2010 25
 BFS illustrated
Step 7: D is expanded, B and F are put in OPEN.

Fringe: GCFBF

2010 26
Step 8: G is selected for expansion. It is found to be a goal
node. So the algorithm returns the path A C G by following
the parent pointers of the node corresponding to G. The
algorithm terminates.

2010 27
 Algorithm for the BFS
• Put the root node on a queue
• While( queue not empty )
{ Remove the first node N from queue
If (N is a goal state ) then return success;
pull all children of node onto queue;
} Reurn failure;

However, BFS is wasteful when all paths lead to the goal node
at more or less the same depth. It is also not effective if the
branching factor is large or infinite.

2010 28
• Exercise: Consider the following graph
representing the state space and operators of a
navigation problem: What is the order that BFS will
expand the nodes
A D
G
S

B E F

C H

• S is the start state and G is the goal state. When placing

expanded child nodes on the queue, assume that the child
nodes are placed in the alphabetical order(if node S is
expanded the queue will be A,B). Assume that we never
generate child nodes that appear as ancestors of the
current node in the search tree
2010 29
 Depth-First-Search (DFS)
• DFS traverses the search space by expanding
the state that is deepest in the search tree first.
• The basic algorithm is implemented using a
stack that is initialized with a single value,
the start state. It terminates when the goal
state is found. Upon expanding a state, each
resulting state is pushed onto the Stack.

2010 30
 DFS – Algorithm
• Put the root node on a stack
• While( stack is not empty )
{ Remove the node from the stack;
If (node is a goal node ) then return success;
put all children of node onto the stack;
} Return failure;

2010 31
Depth-first search

2010 32
 Search tree for the state space

Let us now run Depth First Search on the search space given in
Figure below, and trace its progress

2010 33
 DFS illustrated

Step 1: Initially fringe contains only the node for A.

Fringe: A

2010 34
 DFS illustrated

Step 2: A is removed from fringe. A is expanded and its children

B and C are put in front of fringe

Fringe: BC

2010 35
 DFS illustrated
Step 3: Node B is removed from fringe, and its children D and E
are pushed in front of fringe.

Fringe: DEC

2010 36
 DFS illustrated
Step 4: Node D is removed from fringe. C and F are pushed in
front of fringe.

Fringe: CFEC

2010 37
 DFS illustrated
Step 5: Node C is removed from fringe. Its child G is pushed in
front of fringe.

Fringe: GFEC

2010 38
 DFS illustrated
Step 6: Node G is expanded and found to be a goal node. The
solution path A-B-D-C-G is returned and the algorithm
terminates.

Goal.

Fringe: GFEC

2010 39
• DFS is a good idea when you are confident that all partial path
either reach dead ends or become complete path in a reasonable
number of steps.
• The real problem with a depth first search is that it can’t recover
from early poor choices.
• Exercise:
– Consider the following state space in which the states are shown as nodes
labeled A through F. A is the initial state and E is the goal state. Show
how the DFS finds a solution in this state space by writing down, in order,
the names of the nodes removed from the agenda. Assume the search halts
when the goal state is removed
A
B C

D
E F
2010 40
• Exercise
– Suppose that you need to find a path between S
and G in the following graph. For each of the
following search methods list the nodes in the
order in which they are expanded by the search
method while looking for the solutions
• DFS
S
• BFS

A G

C B

2010 41
• Exercise : Suppose that you need to find a path between S
and G in the following graph. For both DFS and BFS search
methods list the nodes in the order in which they are expanded
by the search methods while looking for a solution.

F H
S
G
A D

2010 42
 Attributes for DFS
• Search Completeness: DFS is complete only if
the search has finite depth and does not contain
cycles
• Search Optimality: DFS is not optimal:-it doesn’t
always find a least-cost solution.
• Time Complexity: The time complexity of DFS is
0(bm) where m is the maximum depth and b is the
branching factor
• Space Complexity: The search only requires
roughly half of the number of nodes since it needs
only to store half-tree in the memory at once.
2010 43
 Search notation
• The notion used to defining search are
– f(n): is evaluation function that estimates least cost solution
through node n.
– h(n):is a heuristic function that estimates least cost path
from node n to goal node.
– g(n): is a cost function that estimates least cost from start to
node n.
• The relation among three parameters are expressd

2010 44
 Depth Limited Search (DLS)
• DLS is simply a DFS that has a limit on depth of
states to investigate.
• It avoids the drawback of DFS by imposing a cut-
off on the attributes of DLS.
• The problem now is that it is hard to set a depth
without knowing if a solution will be found in or
lesser depth.
• This will enhance the completeness attribute.

2010 45
 DLS - Algorithms
• depth limit = max depth to search to;
• agenda = initial state;
– if initial state is goal state then return solution
– else
• while agenda not empty do take node from front of agenda;
• if depth(node) < depth limit then
– {new nodes = apply operations to node;
– add new nodes to front of agenda;
– if goal state in new nodes
– then return solution;}

2010 46
 Algorithm - DLS
• Let fringe be a list containing the initial state
• Loop
– if fringe is empty return failure
– Node  remove-first (fringe)
– if Node is a goal
• then return the path from initial state to Node
– else if depth of Node = limit return cutoff
– else add generated nodes to the front of fringe
• End Loop

2010 47
 Depth-First Iterative
Deepening (DFID)
• The limitation of the DLS is that there is no reliable method
on how to decide a depth limit to include at least one
solution.
• Iterative Deepening solves this drawback by repeatedly
checking the search tree at incremental depth; i.e, it checks
the entire tree at depth 0, then depth1, depth2 and so on.
• The search begins by doing a DLS with a limit of l and if a
goal is not found incrementing this limit and trying again
until a goal is found
• Institutively one can see that this strategy is redundant,
since at any depth limit the strategy needs to expand the
nodes that were already checked in the preceding level.

2010 48
 Procedure
• Successive depth-first searches are conducted
– each with depth bounds increasing by 1

2010 49
2010 50
2010 51
2010 52
 Algorithm-DFID
• until solution found do
– DFS with depth cutoff c
– c = c+1
• Advantage
– Linear memory requirements of depth-first search
– Guarantee for goal node of minimal depth

2010 53
Dijkstra/Cost First Search
• Keeps track of the cost of every path
• No guessing
• Computes accumulated cost paid to reach a node
from the start
– Uses the cost (called the given cost) as a priority
value to determine the next node that should be
brought out of the open list
• The algorithm maintains a priority queue of
nodes to be explored.

2010 54
 Example 1
6
A 5 C E v a b c d e f G

7 A 0a 3a 5a 6a a a a
6 5 2
3 2 3 B 0b 3a 5a 5b a a a

C 0a 3a 5c 5b 11c 8c 12c
D
B
F G D 0a 3a 5a 5b 11c 8c 12c
2 9 1
F 0a 3a 5a 5b 11c 8c 9f

The shortest path is = ACFG=9

2010 55
 1
Example 2 4 8
2 7
4 5
3 3 4

VISITED 1 2 3 4 5

{1} 0 4  8 
{1,2} 0 4 7 8 
{1,2,3} 0 4 7 8 
{1,2,3,4} 0 4 7 8 15
{1,2,3,4,5} 0 4 7 8 15

2010 56
 Exercise – Dijkstra
3 C
S 2
7 2
3 B L
A 4 4
4 4 1 I 6
D H J
4 K 4
5 3 2
F G 5
2 E
Answer

The short path = S B H G E

2010 57
 Exercise –Dijkstra Alg.

2
10 B D

1 8
A 4 7 9
3
C E
2

2010 58
 Algorithm
• Let fringe be a priority queue containing the initial state
• Loop
– if fringe is empty return failure
– Node  remove-first (fringe)
• if Node is a goal
– then return the path from initial state to Node
– else generate all successors of Node, and
– put the newly generated nodes into fringe
– according to their f values
• End Loop

2010 59
 Informed Search (heuristic)
• In the informed search, we make available to the
strategy, some problem-specific knowledge about
the likely cost of the path from each node on the
list to a goal node.
• It works by deciding which is the next best node
to expand. It usually more efficient than blind
searches.
• This knowledge is usually encapsulated in the
form of heuristic function that estimates the
distance of a state from the goal state using some
meaningful measure.
• In heuristic search, you need to focus on paths
that seem to be getting you nearer your goal state.
2010 60
Informed Search (heuristic)...
• In informed search there is an estimate available
of the cost(distance) from each state (city) to the
goal.
• This estimate (heuristic) can help you move in the
right direction.
• Heuristic embodied in function h(n), estimate of
remaining cost from search node n to the least cost
goal.
• The search strategies use this (h(n) to
inform the search.

2010 61
 Generate and Test
• The simplest approach
1.Generate a possible solution
• Generate a particular point in problem space
• Generate a path from a start state
2. Test to see if this is actually a solution by comparing
the chosen point or the end point of the chosen path to
the set of acceptable goal states.(Test to see if this is
actually a solution. )
3. If a solution is found quit, otherwise return to step1
• If generation is systematic, then consider as complete
• If the problem space is very large … time complexity is the
problem.

2010 62
 Cont.…
• We generate one by one all possible complete
variable assignments and for each we test if it
satisfies all constraints.
• The corresponding program structure is very
simple, just nested loops, one per variable. In
the innermost loop we test each constraint. In
most situation this method is intolerably slow.

2010 63
Greedy search (Best First Search)

• In greedy search, the idea is to expand the node

with the smallest estimated cost to reach the goal.
• Minimizes estimated cost to reach a goal
• Expands a node closest to goal (min h(n))
• Criterion function f uses only heuristic function h
f(n)= h(n)
• Always expands the heuristically best nodes (Best
First Search )

2010 64
 Algorithm: Greedy
• QUEUE: Path only containing root
• WHILE (QUEUE not empty && goal not reached) DO
– Remove first path from QUEUE
– Create paths to all children
– Reject paths with loops
– Add paths to QUEUE and sort the entire QUEUE (heuristic)
• IF goal reached
– THEN success
– ELSE failure

2010 65
• Example: route finding using Greedy Search
N
I
O

S F V
Z
B U H
A R
T
L P E
M G

D C

Initial state is A and the goal state is2010B 66

 • Straight-line distances to goal (B)
360
A-366 M-241 A
B-0 N-234 253
374
S 329
Z
C-160 O-380 T
176
D-242 P-100 F 380 193
O R
E-161 R-193 . . .
F-176 S-253 . . .
G-77 T-329 .
. .
H-151 U-80
I-226 V-199
L-244 Z-374 2010 67
• Exercise : Imagine the problem of finding a
route on the road map. Use the Best search
strategy to find a path between S and G.

A B C
S
G
D E F

Define h(n) to be the straight-line distance from each node to G

A 11 B 6 C 4
12 G
S 3
8 7
D E F
2010 68
 A* Search
• It has seen that Greedy Search uses a heuristic
function h(n) to decide which node to expand
next. It was also shown that this strategy might
not find the least costly path because it doesn’t
take into consideration the cost of the path itself
as a variable to minimize cost.
• To improve this restriction, a new function f(n) is
introduced where
• h(n): It gives the estimated cost to the goal
• g(n): It gives the cost of the path so far
• Improves on the greedy search by using both
criterion functions
– f(n)=g(n)+h(n)
2010 69
 A* Algorithms
• QUEUE: Path only containing root
• WHILE (QUEUE not empty && first path not reach goal)
DO
– Remove first path from QUEUE
– Create paths to all children
– Reject paths with loops
– Add paths and sort QUEUE (by f = cost + heuristic)
– IF QUEUE contains paths: P, Q AND P ends in node N i && Q
contains node Ni AND cost_P ≥ cost_Q
– THEN remove P
• IF goal reached THEN success ELSE failure

2010 70
 A* Algorithm
1 Add START to OPEN list
2 while OPEN not empty
3 get node n from OPEN that has the lowest f(n)
4 if n is GOAL then return path
5 move n to CLOSED
6 for each n' = CanMove(n, direction)
7 g(n') = g(n) + 1
8 calculate h(n')
9 if n' in OPEN list and new n' is not better, continue
10 if n' in CLOSED list and new n' is not better, continue
11 remove any n' from OPEN and CLOSED
12 add n as n's parent
13 add n' to OPEN
14 end for
15 end while
16 if we get to here, then there is No Solution
2010 71
 3 C
S 2
7 2
3 B L
A 4 4
4 4 1 I 6
D H J
4 K 4
5 3 2
F G 5
2 E

2010 72
Node H(n)
S 10
A 9
• S=0+10=10, then
B 7
expand S, then A,B,C
C 8 • A=9+7,B=2+7,C=3+8
D 8 • Prioritize them BCA
E 0 • Then expand the
F 6 smallest value which is
G 3 B
H 6 • D=6+8, H=3+6
I 4 • Expand H
J 4 • Ans= SBHGE
K 3
L 6 2010 73
1 h=9 2 h=8 3 7 4 6 5 5 6 6

7 8 8 7 9 6 10 5 11 4 12 5

13 7 14 6 15 5 16 17 3 18 4

19 6 20 5 21 4 22 3 23 2 24 3

25 5 26 27 3 28 29 1 30 2

31 4 32 3 33 2 34 35 36 1

37 5 38 4 39 3 40 2 41 1 42 2

43 6 44 5 45 4 46 3 47 2 48 3

2010 74
• G value = movement cost
– 10 for horizontal
– 14 for vertical
• H value=heuristic (Manhattan distance )
• F value = g+h
• Parent (node to reach this node)
• Open node
– list of nodes that need to be checked)
• Closed node
– list nodes that have been checked )
2010 75
1 h=9 2 h=8 3 7 4 6 5 5 6 6

7 8 8 7 9 6 10 5 11 4 12 5

13 7 14 6 15 5 16 17 3 18 4

19 6 20 5 21 4 22 3 23 2 24 3

25 5 26 27 3 28 29 1 30 2

31 4 32 3 33 2 34 35 36 1

37 5 38 4 39 3 40 2 41 1 42 2

43 6 44 5 45 4 46 3 47 2 48 3

2010 76
1 h=9 2 h=8 3 7 4 6 5 5 6 6

7 8 8 f=17 7 9 h=6 10 5 11 4 12 5
G=14 f=20
13 f=17 14 6 15 G=10 5 16 17 3 18 4
7 f=15

19 F=20 20 f=15 5 21 f= 22 3 23 2 24 3
6 14+4=18 4
25 5 26 27 3 28 29 1 30 2

31 4 32 3 33 2 34 35 36 1

37 5 38 4 39 3 40 2 41 1 42 2

43 6 44 5 45 4 46 3 47 2 48 3
2010 77
1 h=9 2 h=8 3 7 4 6 5 5 6 6

7 8 8 7 9 6 10 5 11 4 12 5

13 7 14 6 15 5 16 17 3 18 4

19 6 20 5 21 4 22 3 23 2 24 3

25 5 26 27 3 28 29 1 30 2

31 4 32 3 33 2 34 35 36 1

37 5 38 4 39 3 40 2 41 1 42 2

43 6 44 5 45 4 46 3 47 2 48 3

2010 78
 Exercise

Ans = SBCG
2010 79
 A* EXERCISE
87
N
I
O
151 92
71 99
S 221 V
Z F 142
140 80 85
75 98
A R B U H
118 97
101 86
T 111 90

L 70 P E
M 148 G
139
75
120
D C
2010 80
Solution

360
A
140+253
75+374
118+329
S Z
T
140+99+176
140+151+380
F 140+80+193
O R
140+151+148+380 140+151+97+380

C P

B C

2010 81
 IDA*
• Iterative deepening A* or IDA* is similar to
iterative-deepening depth-first, but with the
following modifications:
• The depth bound modified to be an f-limit .
– 1. Start with limit = h(start)
– 2. Prune any node if f(node) > f-limit
– 3. Next f-limit=minimum cost of any node pruned
• The cut-off for nodes expanded in an iteration is
decided by the f-value of the nodes.

2010 82
 IDA*
• Iterative deepening work by repeating depth-
first search with increasing depth.
• What can we use instead of depth? What
analogous feature is the A* algorithm based
on?
– The f(N) function
• How do we use the f(N) function?
– Do depth-first search with increasing f-limit

2010 83
 IDA* algorithm
• bound = f(start_node) • f-bound f(S)
• found = false • WHILE (goal is not
– while not found do
reached) DO
• depth-first search from
start_node for nodes N – f-bound f-
such that f(N) ≤ bound limitted_search(f-bound)
– if goal_found • Perform f-limited search
– then found  true with f-bound
– else bound = min { f(N) | N
generated by search f(N) >
bound }
• end

2010 84
 Example
• Trace the execution of A* for the tree. How
many nodes are generated by A* and IDA*?
Count all re-generated nodes.

2010 85
Exercise

2010 86
 Bi-Directional
• Algorithm:
– Bidirectional search involves alternate searching
from the start state toward the goal and from the
goal state toward the start. The algorithm stops
when the frontiers intersect
• The idea behind bi-directional search is to
search simultaneously both forward from the
initial state and backwards from the goal state,
and stop when the two BFS searches meet in
the middle.
2010 87
 Simple Hill Climbing
Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or there are no new
operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal  quit
better than current state  new current state

2010 88
 Hill-Climbing
• Algorithm:
– determine successors of current state
– choose successor of maximum goodness (break ties randomly)
– if goodness of best successor is less than current state's
goodness, stop
– otherwise make best successor the current state and go to step
1
• No search tree is maintained, only the current state.
• Like greedy search, but only states directly reachable
from the current state are considered.

2010 89
 Hill Climbing: Disadvantages
Local maximum
A state that is better than all of its neighbours,
but not
better than some other states far away.

2010 90
 Games
• Multiagent environment
• Cooperative vs. competitive
– Competitive environment is where the agents’ goals are in
conflict
– Adversarial Search
• Game Theory
– A branch of economics
– Views the impact of agents on others as significant rather
than competitive (or cooperative).

2010 91
 Properties of Games
• Game Theorists
– Deterministic, turn-taking, two-player, zero-sum games of
perfect information
• AI
– Deterministic
– Fully-observable
– Two agents whose actions must alternate
– Utility values at the end of the game are equal and opposite
• In chess, one player wins (+1), one player loses (-1)
• It is this opposition between the agents’ utility functions that
makes the situation adversarial

2010 92
 Games as Search Problems
• Games have a state space search
– Each potential board or game position is a
state
– Each possible move is an operation to another
state
– The state space can be HUGE!!!!!!!
• Large branching factor (about 35 for chess)
• Terminal state could be deep (about 50 for chess)

2010 93
Games vs. Search Problems
• Unpredictable opponent
• Solution is a strategy
– Specifying a move for every possible opponent
reply
• Time limits
– Unlikely to find the goal…agent must approximate

2010 94
 Types of Games
Deterministic Chance

Perfect Chess, Backgammon,

Information checkers, go, monopoly
othello
Imperfect Bridge, poker,
Information scabble,
nuclear war

2010 95
Optimal Decisions in Games
• Consider games with two players (MAX, MIN)
• Initial State
– Board position and identifies the player to move
• Successor Function
– Returns a list of (move, state) pairs; each a legal move and
resulting state
• Terminal Test
– Determines if the game is over (at terminal states)
• Utility Function
– Objective function, payoff function, a numeric value for
the terminal states (+1, -1) or (+192, -192)

2010 96
 Game Trees
• The root of the tree is the initial state
– Next level is all of MAX’s moves
– Next level is all of MIN’s moves
–…
• Example: Tic-Tac-Toe
– Root has 9 blank squares (MAX)
– Level 1 has 8 blank squares (MIN)
– Level 2 has 7 blank squares (MAX)
– …
• Utility function:
– win for X is +1
– win for O is -1

2010 97
Game Trees

The search tree for min max toe

2010 98
 Minimax Strategy
• Basic Idea:
– Choose the move with the highest minimax value
• best achievable payoff against best play
– Choose moves that will lead to a win, even though
min is trying to block
• Max’s goal: get to 1
• Min’s goal: get to -1
• Minimax value of a node (backed up value):
– If N is terminal, use the utility value
– If N is a Max move, take max of successors
– If N is a Min move, take min of successors

2010 99
 Minimax Strategy
Max Represent as or -  And Min Represent as or +

2010 100
Minimax Algorithm

2010 101
 Exercise

11 14 5
10 15 2 3 21 20
12 14 4
9 13 2010
1 22 102
 Alpha-Beta Pruning
• The problem with minimax search is that
the number of game states is has to
examine is exponential in the number of
moves
• Use pruning to eliminate large parts of
the tree from consideration
• Alpha-Beta Pruning

2010 103
 Alpha-Beta Pruning
• Recognize when a position can never be
chosen in minimax no matter what its children
are
– Max (3, Min(2,x,y) …) is always ≥ 3
– Min (2, Max(3,x,y) …) is always ≤ 2
– We know this without knowing x and y!

2010 104
 Alpha-Beta Pruning
• Alpha = the value of the best choice we’ve
found so far for MAX (highest)
• Beta = the value of the best choice we’ve
found so far for MIN (lowest)
• When maximizing, cut off values lower than
Alpha
• When minimizing, cut off values greater than
Beta
Prune; if   
2010 105
Example

2010 106
  

Example

2010 107
  

Example
 


2010 108
  

Example
 

 


2010 109
  

 
Example 

 


 


2010 110
  

 
Example 

 


 


10

2010 111
  

 
Example 

 


 
10

10

2010 112
  

 
Example 

 


 
10

10 11

2010 113
  

 
Example 

 


 
10
10

10 11

2010 114
  

 
Example 

 10


 
10
10

10 11

2010 115
  

 
Example 

 10


   10
10 

10

10 11

2010 116
  

 
Example 

 10


   10
10 

10

10 11

9 2010 117
  

 
Example 

 10


   10
10 9

10

10 11

9 2010 118
  

 
Example 

 10


   10
10 9

10 9

10 11

9 2010 119
  

 
Example 

 10

10
   10
10 9

10 9

10 11

9 2010 120
  

 
Example 10

 10

10
   10
10 9

10 9

10 11

9 2010 121
  

 
Example 10

 10  
 10

10
   10
10 9

10 9

10 11

9 2010 122
  

 
Example 10

 10  
 10

10
   10  
10 9 10

10 9

10 11

9 2010 123
  

 
Example 10

 10  
 10

10
   10  
10 9 10

10 9

10 11 14

9 2010 124
  

 
Example 10

 10  
 10

10
   10  
10 9 10

10 9

10 11 14 15

9 2010 125
  

 
Example 10

 10  
 10

10
   10  
10 9 10

10 9 14

10 11 14 15

9 2010 126
  

 
Example 10

 10  14
 10

10
   10  
10 9 10

10 9 14

10 11 14 15

9 2010 127
  

 
Example 10

 10  14
 10

10 14
   10  
10 9 10

10 9 14

10 11 14 15

9 2010 128
  

 
Example 10

 10  14
 10

10 14
   10  
10 9 10

10 9 14

10 11 14 15

9 2010 129
  10

 
Example 10
10
 10  14
 10

10 14
   10  
10 9 10

10 9 14

10 11 14 15

9 2010 130
  10

 
Example 10
 10
10 
 10  14
 10  10
10 14 
   10  
10 9 10  10

10 9 14

10 11 14 5
15

9 2010 131
  10

 
Example 10
 10
10 
 10  14
 10  10
10 14 
   10  
 10
10 9 10
5
10 9 14

10 11 14 5
15

9 2010 132
  10

 
Example 10
 10
10 
 10  14  10
 10 
10 14
   10  
 10  10
10 9 10
5 
10 9 14 5

10 11 14 5
15

9 2010 133
  10

 
Example 10
 10
10 
 10  14
 10  10
10 14 
   10  
 10  10
10 9 10
5 
10 9 14 5

10 11 14 5
15

9 4
2010 134
  10

 
Example 10
 10
10 
 10  14  10
 10 
10 14
   10  
 10  10
10 9 10
5 4
10 9 14 5 4

10 11 14 5
15

9 4
2010 135
  10

 
Example 10
 10
10 
 10  14  10
 10 
10 14 5
   10  
 10  10
10 9 10
5 4
10 9 14 5 4

10 11 14 5
15

9 4
2010 136
  10

 
Example 10
 10
10 5
 10  14  10
 10 
10 14 5
   10  
 10  10
10 9 10
5 4
10 9 14 5 4

10 11 14 5
15

9 4
2010 137
  10

 
Example 10
 10
10 5 5
 10  14  10
 10 
10 14 5
   10  
 10  10
10 9 10
5 4
10 9 14 5 4

10 11 14 5
15

9 4
2010 138
  10
10 
 
Example 10
 10
10 5 5
 10  14  10
 10 
10 14 5
   10  
 10  10
10 9 10
5 4
10 9 14 5 4

10 11 14 5
15

9 4
2010 139
The maximizing player guaranteed at least
by scoring 10 by choosing LHS(node with
10 value)

2010 140
Alpha-Beta Pruning Example

2010 141
Alpha-Beta Pruning Example

2010 142
Alpha-Beta Pruning Example

2010 143
Alpha-Beta Pruning Example

2010 144
Alpha-Beta Pruning Example

2010 145
 Alpha-Beta Algorithm
• MaxEval(node, alpha, beta):
• If terminal(node), return U(n)
• For each c in childlist(n)
• val←MinEval(c, alpha, beta)
• alpha ←max(alpha, val)
• If alpha ≥beta, return alpha
• Return alpha
• MinEval(node, alpha, beta):
• If terminal(node), return U(n)
• For each c in childlist(n)
• val←MaxEval(c, alpha, beta)
• beta ←min(beta, val)
• If alpha ≥beta,
• return beta Return beta
2010 146
Exercise

4 5 6 3 8

3 4 7 9
2010 147
Exercise

2010 148
Minimax with -pruning

2010 149
CSP using Search

2010 150
 Constraint Satisfaction Problem
• Constraint satisfaction is a search procedure that
operates in a space of constraint sets.
• The goal is to discover some problem state that
satisfies a certain constrains.
• Constraint Satisfaction is a two step process:
Propagation and guess
– Constraints are discovered and propagated as far as
possible trough out the system. Then if there is still not a
solution, search begins
– A guess about something is made and added as a new
constraint. Propagation can then occur with the new
constraint and so on…

2010 151
 CSP: Definition on
• Definition: lati
u
• A CSP consists of : orm
f
1. A set of variables, X
2. For each variable Xi in X, a domain Di
Di is a finite set of possible values
3. a set of constraints Ci specifies allowable combinations of values
for subsets of variables
– a consistent state violates none of the constraints C
– a complete assignment has values assigned to all variables.
– A Solution is a complete, consistent assignment.
• Allows useful general-purpose algorithms with more power
than standard search algorithms

2010 152
 Example
• Ex1 • Ex2
• V={v1} • V={V1 ,V2}
– Dom(v1)={1,2,3,4} – Dom(v1)={1,2,3}
• C={c1,c2} – Dom(v2)={1,2}
– C1:v1 2 • C={c1,c2 , c3}
– C2:v1>1 – C1:v2 2
– C2:v1 + v2 <5
– C3:v1 > v2
2010 153
• Definition
– A model of a csp is an assignment of values to all of its
variables that satisfies all of its constraints
– V={v1}, Dom(v )={1,2,3,4}
1

– C={c1,c2}, C1:v1 2, C2:v1>1

– All models for this csp:
• {v1=3}, {v1=4}
– For 2nd example; the models are
• {v1=1,v1=1},{v1=2,v2=1},{v1=3,v2=1}
– A model is a possible world that satisfies all constraints

2010 154
 Constraints
• Constraints are restrictions on the values that one
or more variables can take
– Unary constraints involve a single variable
• E.g. V2  2
– Binary constraints involve pairs of variables,
• e.g., SA ≠ WA, v1+v2<5
– Higher-order constraints involve 3 or more variables,
– e.g., cryptarithmetic column constraints
• The scope of constraint is the set of variables that are
involved in the constraint

2010 155
 Example: Map-Coloring
• Color each region
Either red, green or
Blue
• No adjacent region can
Have the same color

• Variables WA, NT, Q, NSW, V, SA, T

• Domains Di = {red, green, blue}
• Constraints: adjacent regions must have different colors
• e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),
(green,red), (green,blue),(blue,red),(blue,green)}
2010 156
 Map-Coloring

• Solutions are complete and consistent assignments,

• e.g.,
– WA = red, NT = green, Q = red, NSW = green, V = red,
SA = blue, T = green
2010 157
 Constraint graph
• Binary CSP: each constraint relates two variables
• Constraint graph: nodes are variables, arcs are
constraints

2010 158
 Real-world CSPs
• Assignment problems
– e.g., who teaches what class
• Timetabling problems
– e.g., which class is offered when and where?
• Transportation scheduling
» Factory scheduling
» Notice that many real-world problems involve
real-valued variables

2010 159
 Example
• Consider the following CSP with 3 variables X,
Y and Z:
– Dom(X) = {1, …, 10}
– Dom(Y) = {5, …, 15}
– Dom(Z) = {5, …, 20}
• And binary constraints:
– C1(X, Y): X > Y,
– C2(Y, Z): Y + Z = 12
– C3(X, Z): X + Z = 16

2010 160
 Scheduling classes
• Formulate in terms of variables, domains and
constraints.
• X={cosc1021, cosc3142, cosc1101, cosc4241}
• D={mon2:30,mon4:30, mon5:30,….,Fri11:30}
• C: i,j if xi , xj are co-requisites, then TiTj

2010 161
 CSP example
• Sudoku:
– 81 variables, 
each representing the value
 of a cell.
– Values: a fixed value for th
ose cells that are already fil
led in, the  values {1‐
9} for those cells that are e
mpty.

2010 162
 CSP example
• Solution: a value for each cell satisfying the co
nstraints:
– no cell in the same column can have the same valu
e.
– no cell in the same row can have the same value
– no cell in the same sub‐
square can have the same value

2010 163
 Cryptarithmetic
• Variables: F T U W R O X1 X2 X3
• Domains: {0,1,2,3,4,5,6,7,8,9}
• Constraints: Alldiff (F,T,U,W,R,O)
– O + O = R + 10 · X1
– X1 + W + W = U + 10 · X2
– X2 + T + T = O + 10 · X3
– X3 = F, T ≠ 0, F ≠ 0

2010 164
 Cryptarithmetic Puzzles
T w o S e n d
 M o r e
 T w o
M o n e y
F o u r

0123456789

2010 165
 Exercise
• An addition is given below where all letter
stands for a single digit number and no two
numbers are represented by the same letter
• What is the value of J+U+N+E=?
N O O N
 M O O N
S O O N
J U N E
2010 166
 Standard search formulation
(incremental)
• Let's start with the straightforward approach, then fix it
– Initial state: the empty assignment { }
– Successor function: assign a value to an unassigned variable
that does not conflict with current assignment  fail if no legal
assignments
– Goal test: the current assignment is complete
1. This is the same for all CSPs
2. Every solution appears at depth n with n variables
 use depth-first search
3. Path is irrelevant, so can also use complete-state
formulation
• States are defined by the values assigned so far

2010 167
Backtracking search
• Variable assignments are commutative,
• i.e., [if WA = red then NT = green ] same as
[ if NT = green then WA = red ]
• Backtrack when variable has no legal value
• Depth-first search for CSPs with single-variable
assignments is called backtracking search
• Backtracking search is the basic uninformed
algorithm for CSPs
• Only need to consider assignments to a single
variable at each node

2010 168
 Backtracking search
• Explore search space via DFS but
evaluate each constraint as soon as all its
variables are bound.
• Any partial assignment that doesn’t
satisfy the constraint can be pruned.

2010 169
Backtracking search

2010 170
Backtracking example

2010 171
Backtracking example

2010 172
Backtracking example

2010 173
Backtracking example

2010 174
Forward checking
• Keep track of remaining legal values for unassigned variables.
Terminate search when any variable has no legal values
• It look at a variable just assigned and looks all unassigned
variables , then it removes the values which is inconsistent to
the variable
– Domain={r,g,b,y}
– A=b
– B={g,r}
– C={r,g}
– D={b,r,g}
– E={b,g,r,}

2010 175
Forward checking
• Function forward checking(CSP)
– Each var
– For each variable x in csp do
• For each unassigned variable Y connected to X do
– For each value d in Domain(Y)
» If d is inconsistent with value (X)
» Domain (Y)={domain()-d}
– Return csp

2010 176
 Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal values

2010 177
Forward checking

2010 178
 Forward checking
• Idea:
– Keep track of remaining legal values for unassigned
variables
– Terminate search when any variable has no legal values

2010 179
 Constraint propagation
• Forward checking propagates information from assigned to
unassigned variables, but doesn't provide early detection for all
failures:

• NT and SA cannot both be blue!

• Constraint propagation repeatedly enforces
constraints locally
2010 180
 Arc consistency
X Y X Y

• It looks at all the value of X and check if there is any

possible value in the Y node, which is consistent to X
• Simplest form of propagation makes each arc
consistent
• X Y is consistent iff
– for every value x of X there is some allowed y

2010 181
 Example

• Domain={r,g,b,} A
• A=b B C E
• B={g,r} D
• C={r,g}
• D={b,r,g}
• E={b,g,r,}

2010 182
 Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff for every value x of X there is some
allowed y

2010 183
 Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff for every value x of X there is some
allowed y

• If X loses a value, neighbors of X need to be rechecked

2010 184
 Arc consistency
• Simplest form of propagation makes each arc consistent
• X Y is consistent iff
– for every value x of X there is some allowed y

• If X loses a value, neighbors of X need to be rechecked

• Arc consistency detects failure earlier than forward checking

•
• Can be run as a preprocessor or after each assignment
2010 185
 Question
• If we assigned a value to a variable A, which domain might be
changed as a result of running forward checking .
• Assigned a value to A run forward checking, and then assign
the value to B and run forward checking again, which domain
might change.
• Run Arc-consistency after assigning a value to A.(all except
A)

C F
A D

B E

2010 186
 Arc-consistency
Question

A B C D E

A B C D E

2010 187
MRV(Most Restricted Variable)

• MRV aka Most constrained variable

• It is a criteria that tells us which variables should
be to explored next
• choose the variable with the fewest legal values
– It see all neighbor variables and choose the least
number of value remain in the domain(chose most
restricted variable)
– choose the variable with the most constraints on
remaining variables

2010 188
LCV(Least constraint Value)

• LCV tells us which value to choose next

• Given a variable, choose the least
constraining value:
– the one that rules out the fewest values in
the remaining variables

2010 189
 Example

• Domain={r,g,b,y} A
• A=b B C E
• B=g D
• C={r,y}
• D={b,r,y}
• E={b,g,r,y}

2010 190
 ND
E

2010 191