# Catalogue of Artificial Intelligence Techniques

## Expectiminimax

**Keywords:**
game theory, minimax, search

### Categories: Search

Author(s): **Xarius Desai**

The Expectiminimax heuristic is heavily based upon the minimax heuristic for game search trees. It's application is for games that contain a certain element of unpredictability, and as such the game tree is not deterministic. Typical games that can use this method include Backgammon, and those with dice-rolling.

The game tree that minimax works on is based between two sets of nodes, Max nodes and Min nodes, however the expectiminimax game tree includes another set of nodes – Chance nodes, which are shown as circles. At each players turn there is a chance node for every possible permutation of the random element outcome (in the case of rolling 2 dice there are 21 distinct outcomes) and an associated probability of that node occurring.

The main decision-making process of the minimax algorithm is linked with its minimax value. However due to the element of unpredictability, it is not possible to calculate a definite minimax value for each level, so the expected value of the level is used. Calculating the expectiminimax value of a node n is given by the following:

**Expectiminimax(n) =**

**Utility(n),** if n is terminal node

**Max(successors(n)),** if n is Max node

**Min(successors(n)),** if n is Min node

**Sum( successors(n) x Prob(successor) ),** if n is Chance node

*adapted from Russell & Norvig*

*Artificial Intelligence: A Modern Approach*

The usual running time for the minimax algorithm is O(bm) where b is the possible number of legal moves. This increases to O(bmnm) time for expectiminimax, where n is the distinct number of chance nodes. This can be reduced via the use of alpha-beta pruning, which works on the chance nodes as well as the max and min nodes.

### References:

- Stuart Russell and Peter Norvig,
*Artificial Intelligence: A Modern Approach*, Prentice Hall, 2003, pp.175-178.

### Comments:

No comments.