Tag: games

How a computer can play games (like Chess)

1. How human play chess: mixing analysis, strategy, tactics to choose a move
2. If-Then rules
3. Look ahead and evaluate
4. 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.

Minimax

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

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.

Progressive Deepening

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

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)