Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

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:


Comments:

Add Comment

No comments.