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.