Expectiminimax tree

Expectiminimax tree

An expectiminimax tree is a specialized variation of a minimax tree for use in artificial intelligence systems which play games of chance. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" nodes, which take the expected value of a random event occurring.

In the traditional minimax method, the levels of the tree alternate from max to min until the depth limit of the tree has been reached. In an expectiminimax tree, the "chance" nodes are interleaved with the max and min nodes. Instead of taking the max or min of the utility values of their children, chance nodes take a weighted average, with the weight being the probability that that child is reached.

The interleaving depends on the game. Each "turn" of the game is evaluated as a "max" node (representing the AI player's turn), a "min" node (representing a potentially-optimal opponent's turn), or a "chance" node (representing a random effect or player).

For example, consider a game which, in each round, consists of a single dice throw, and then decisions made by first the AI player, and then another intelligent opponent. The order of nodes in this game would alternate between "chance", "max" and then "min".

Pseudocode

Pseudocode for the expectiminimax algorithm is given below. (It is derived from the Minimax algorithm).

function expectiminimax(node, depth) if node is a terminal node or depth = 0 return the heuristic value of node if the adversary is to play at node // Return value of minimum-valued child node let α := +∞ foreach child of node α := min(α, expectiminimax(child, depth-1)) else if we are to play at node // Return value of maximum-valued child node let α := -∞ foreach child of node α := max(α, expectiminimax(child, depth-1)) else if random event at node // Return weighted average of all child nodes' values let α := 0 foreach child of node α := α + (Probability [child] * expectiminimax(child, depth-1)) return α

Note that for random nodes, there must be a known probability of reaching each child. (For most games of chance, child nodes will be equally-weighted, which means the return value can simply be the average of all child values).

ee also

* Minimax
* Expected value

References

* [http://www.cs.mcgill.ca/~dprecup/courses/AI/Lectures/ai-lecture06.pdf Game Playing - McGill University] ( [http://72.14.235.104/search?q=cache:-oLqTm93WZ8J:www.cs.mcgill.ca/~dprecup/courses/AI/Lectures/ai-lecture06.pdf+expectiminimax&hl=en&ct=clnk&cd=26 Google cache] )


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Decision tree — This article is about decision trees in decision analysis. For the use of the term in machine learning, see Decision tree learning. A decision tree is a decision support tool that uses a tree like graph or model of decisions and their possible… …   Wikipedia

  • Combinatorial game theory — This article is about the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory. Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content …   Wikipedia

  • Minimax — This article is about the decision theory concept. For other uses, see Minimax (disambiguation). Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”