Expectiminimax tree
Encyclopedia
An expectiminimax tree is a specialized variation of a minimax
game tree
for use in artificial intelligence
systems that play two-player zero-sum
games such as backgammon
, in which the outcome depends a combination of the player's skill and chance elements such as dice rolls. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" ("move by nature
") nodes, which take the expected value
of a random event occurring. In game theory
terms, an expectiminimax tree is the game tree of an extensive-form game of perfect
, but incomplete information.
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".
algorithm and was first proposed by Donald Michie
.
Its pseudocode
is given below.
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.)
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
for use in artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
systems that play two-player zero-sum
Zero-sum
In game theory and economic theory, a zero-sum game is a mathematical representation of a situation in which a participant's gain of utility is exactly balanced by the losses of the utility of other participant. If the total gains of the participants are added up, and the total losses are...
games such as backgammon
Backgammon
Backgammon is one of the oldest board games for two players. The playing pieces are moved according to the roll of dice, and players win by removing all of their pieces from the board. There are many variants of backgammon, most of which share common traits...
, in which the outcome depends a combination of the player's skill and chance elements such as dice rolls. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" ("move by nature
Move by nature
In game theory a move by nature is a decision or move in an extensive form game made by a player who has no strategic interests in the outcome. The effect is to add a player, 'Nature' whose practical role is to act as a random number generator...
") nodes, which take the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
of a random event occurring. In game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
terms, an expectiminimax tree is the game tree of an extensive-form game of perfect
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
, but incomplete information.
In the traditional minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
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
Utility
In economics, utility is a measure of customer satisfaction, referring to the total satisfaction received by a consumer from consuming a good or service....
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
The expectiminimax algorithm is a variant of the minimaxMinimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
algorithm and was first proposed by Donald Michie
Donald Michie
Donald Michie was a British researcher in artificial intelligence. During World War II, Michie worked for the Government Code and Cypher School at Bletchley Park, contributing to the effort to solve "Tunny," a German teleprinter cipher.-Early life and career:Michie was born in Rangoon, Burma...
.
Its pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
is given below.
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.)