In this post are gathered the tutorials and exercises, called “mega-recitations”, to apply the concepts presented in the Artificial Intelligence course of Prof. Patrick Winston. Continue reading “24. Reviews and Exercises”
6. Search: Games, Minimax, and Alpha-Beta
How a computer can play games (like Chess)
- How human play chess: mixing analysis, strategy, tactics to choose a move
- If-Then rules
- Look ahead and evaluate
- British museum algorithm
To evaluate the potential of the next situation of the board, (methods 2 and 3) we can use a linear scoring polynomial to give number to situations and choose the best.
In the resulting tree of possibilities:
- the branching factor is the number b of branches at each at each level
- the depth is the number d of levels
- the leaves or terminal nodes are the resulting b^d possibilities
In Chess, there are about 10^120 leaf nodes, making it impossible to compute.
Method: using a scoring system for final leaves of the trees, the algorithm simulates a maximizing player who chooses higher values, while a minimizing player who chooses lower values.
Alpha-Beta is a method to discard useless branches to reduce computations for Minimax.
From terminal nodes, the algorithm evaluates the best choice for the maximizing and minimizing players going up one node at a time. It then cuts off branches that would not be chosen by either players at the nodes they play.
Depending on the game and time available, the branching factor of the tree, the tree can be extended not completely but to a certain number of levels only, ensuring that a good answer can always be reached in time, even though it may not be the single best answer.
Deep Blue essentially used all these methods, plus some extra improvements.
Deep Blue = Minimax + Alpha-Beta + Progressive Deepening
+ Parallel Computing + Opening Book + End Game Tricks
+ Uneven Tree Development
Uneven Tree Development: some situation may need to expand the search further to ensure better choices (take the opponents’ Queen)