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.

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