Breadth first search (BFS): expand frontier all the way around before going further. Finds the SHORTEST path to any destination. Requires lots of memory if the graph is big.
Depth first search (DFS): pursues one path as far as possible (until dead end, or it hits someplace already visited). Only then does it backtrack to last decision point, and try a different route. Advantage: relatively little memory required compared to BFS. Disadvantage: not likely to find the shortest path.
Greedy Best-First Search: when deciding which direction to take from a particular node, can make an educated estimate of which is “likely” to lead closer to the goal – this estimate is called a HEURISTIC.
A* Search “A-star”: also uses heuristic, but takes into account how far we’ve come so far, in addition to the estimate of how far remains to the goal.
Zero-sum: Two players, directly opposed to each other. (Alice’s win is Bob’s loss, and vice versa.)
Perfect-information: Nothing is hidden from either player.
Example: tic-tac-toe
Initial board: ---,---,---
Suppose player X goes first.
Frontier becomes:
X--,---,---
-X-,---,---
--X,---,---
---,X--,---
---,-X-,---
---,--X,---
---,---,X--
---,---,-X-
---,---,--XMinimax search algorithm
(handout)