6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games

Next: Game Trees Previous: Search Applied to Adversarial

Using Search

Search could be used to find perfect sequence of moves except the following problems arise:

*
There exists an adversary who is trying to minimize your chances of winning every other move. You cannot control his/her move.

*
Search trees can be VERY large, but you have finite time to move

chess has \(10^{40}\) nodes in search space

With single-agent search (15 puzzle), can afford to wait

Some 2-player games have time limits

Solution? Search to n levels in the tree (n ``ply''), evaluate the nodes at the nth level, and head for the best looking node