## 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
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)