Expectiminimax

Expectiminimax is a decision algorithm used by artificial intelligence programs that play two-player zero-sum games in which chance plays a part, such as backgammon, where the outcome depends on both skill and random events like dice rolls. It extends the minimax algorithm by adding chance nodes, also described as moves by nature, to the usual max and min nodes of the game tree. A chance node does not take the maximum or minimum of its children. Instead it returns a weighted average of their values, weighted by the probability that each child is reached. The chance nodes are interleaved with the max and min nodes according to the game, so a game of one die throw followed by the AI player and then the opponent alternates chance, max and min. In game theory terms the tree is the game tree of an extensive-form game of perfect but incomplete information. The algorithm was first proposed by Donald Michie in 1966, and Bruce Ballard later developed *-minimax, which allows alpha-beta pruning in such trees by bounding the scores of a chance node's children.