The problem with Game trees
Game trees are huge
- O’s and X’s not bad, just 9! = 362,880
- Checkers/Draughts about 1040
- Chess about 10 120
- Go utterly ludicrous, e.g. 361! ?10750
Recall from Search1 Lecture,
- It is not good enough to find a route to a win
- Have to find a winning strategy
- Unlike 8s/SAT/TSP, can’t just look for one leaf node
- typically need lots of different winning leaf nodes
- Much more of the tree needs to be explored