Untitled

Graph search algorithms

  • 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 perfect-information game

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-
---,---,--X

Minimax search algorithm

(handout)