Editing Expectiminimax

{{Short description|Variation of the minimax algorithm}}
{{Infobox algorithm
|class=[[Search algorithm]]
|image=
|data=
|time=<math>\mathcal{O}(b^mn^m)</math>, where <math>n</math> is the number of distinct dice throws
|best-time=<math>\mathcal{O}(b^m)</math>, in case all dice throws are known in advance
|average-time=
|space=
|optimal=
|complete=
}}

The '''expectiminimax''' algorithm is a variation of the [[minimax]] algorithm, for use in [[artificial intelligence]] systems that play two-player [[zero-sum game]]s, such as [[backgammon]], in which the outcome depends on a combination of the player's skill and [[games of chance|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.<ref name="RussellNorvig2009">{{cite book |last1=Russell |first1=Stuart Jonathan |last2=Norvig |first2=Peter |last3=Davis |first3=Ernest |title=Artificial Intelligence: A Modern Approach |date=2010 |publisher=Prentice Hall |isbn=978-0-13-604259-4 |pages=177–178 }}</ref> In [[game theory]] terms, an expectiminimax tree is the game tree of an [[extensive-form game]] of [[perfect information|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|utility values]] of their children, chance nodes take a weighted average, with the weight being the probability that child is reached.<ref name="RussellNorvig2009"/>

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).<ref name="RussellNorvig2009"/>

For example, consider a game in which each round consists of a single die 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".<ref name="RussellNorvig2009"/>

==Pseudocode==

The expectiminimax algorithm is a variant of the [[minimax]] algorithm and was firstly proposed by [[Donald Michie]] in 1966.<ref>{{cite book |doi=10.1016/B978-0-08-011356-2.50011-2 |chapter=Game-Playing and Game-Learning Automata |title=Advances in Programming and Non-Numerical Computation |date=1966 |last1=Michie |first1=D. |pages=183–200 |isbn=978-0-08-011356-2 }}</ref>
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.)

==Expectimax search==

Expectimax search is a variant described in ''Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability'' (2005) by Tom Everitt and [[Marcus Hutter]]. 

==Alpha-beta pruning==

Bruce Ballard was the first to develop a technique, called *-minimax, that enables [[alpha-beta pruning]] in expectiminimax trees.<ref>{{cite journal |last1=Ballard |first1=Bruce W. |title=The *-minimax search procedure for trees containing chance nodes |journal=Artificial Intelligence |date=September 1983 |volume=21 |issue=3 |pages=327–350 |doi=10.1016/S0004-3702(83)80015-0 }}</ref><ref>{{cite book |doi=10.1007/11674399_3 |chapter=Rediscovering *-Minimax Search |title=Computers and Games |series=Lecture Notes in Computer Science |date=2006 |last1=Hauk |first1=Thomas |last2=Buro |first2=Michael |last3=Schaeffer |first3=Jonathan |volume=3846 |pages=35–50 |isbn=978-3-540-32488-1 }}</ref> The problem with integrating [[alpha-beta pruning]] into the expectiminimax algorithm is that the scores of a chance node's children may exceed the alpha or beta bound of its parent, even if the weighted value of each child does not. However, it is possible to bound the scores of a chance node's children, and therefore bound the score of the CHANCE node.

If a standard iterative search is about to score the <math>i</math>th child of a chance node with <math>N</math> equally likely children, that search has computed scores <math>v_1, v_2, \ldots, v_{i-1}</math> for child nodes 1 through <math>i-1</math>. Assuming a lowest possible score <math>L</math> and a highest possible score <math>U</math> for each unsearched child, the bounds of the chance node's score is as follows:

<math>\text{score} \leq \frac{1}{n} \left( ( v_1 + \ldots + v_{i-1}) + v_i + U \times (n - i) \right)</math>

<math>\text{score} \geq \frac{1}{n} \left( ( v_1 + \ldots + v_{i-1}) + v_i + L \times (n - i) \right)</math>

If an alpha and/or beta bound are given in scoring the chance node, these bounds can be used to cut off the search of the <math>i</math>th child. The above equations can be rearranged to find a new alpha & beta value that will cut off the search if it would cause the chance node to exceed its own alpha and beta bounds:

<math>\alpha_i = N \times \alpha - \left( v_1 + \ldots + v_{i-1} \right) + U \times (n - i)</math>

<math>\beta_i = N \times \beta - \left( v_1 + \ldots + v_{i-1} \right) + L \times (n - i)</math>

The [[pseudocode]] for extending expectiminimax with fail-hard [[alpha-beta pruning]] in this manner is as follows:

 '''function''' *-minimax(node, depth, α, β)
     '''if''' node is a terminal node '''or''' depth = 0
         '''return''' the heuristic value of node
     '''if''' node is a max or min node
         '''return''' the minimax value of the node
     '''let''' N = numSuccessors(node)
     // Compute α, β for children
     '''let''' A = N * (α - U) + U
     '''let''' B = N * (β - L) + L
     '''let''' sum = 0
     '''foreach''' child of node
         // Limit child α, β to a valid range
         '''let''' AX = max(A, L)
         '''let''' BX = min(B, U)
         // Search the child with new cutoff values
         '''let''' score = *-minimax(child, depth - 1, AX, BX)
         // Check for α, β cutoff conditions
         '''if''' score <= A
             '''return''' α
         '''if''' score >= B
             '''return''' β
         sum += score
         // Adjust α, β for the next child
         A += U - v
         B += L - v
     // No cutoff occurred, return score
     '''return''' sum / N

This technique is one of a family of variants of algorithms which can bound the search of a CHANCE node and its children based on collecting lower and upper bounds of the children during search. Other techniques which can offer performance benefits include probing each child with a heuristic to establish a min or max before performing a full search on each child, etc.

==See also==
* [[Minimax]]
* [[Alpha–beta pruning]]
* [[Negamax]]
* [[Expected value]]

==References==
<references/>

{{DEFAULTSORT:Expectiminimax Tree}}
[[Category:Search algorithms]]
[[Category:Game artificial intelligence]]
[[Category:Trees (data structures)]]
[[Category:Combinatorial game theory]]