Expectiminimax

The expectiminimax algorithm is a variant of the minimax algorithm and was firstly proposed by Donald Michie in 1966.^[2] 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 is a variant described in Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (2005) by Tom Everitt and Marcus Hutter.

Bruce Ballard was the first to develop a technique, called *-minimax, that enables alpha-beta pruning in expectiminimax trees.^[3][4] 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 ${\displaystyle i}$ th child of a chance node with ${\displaystyle N}$  equally likely children, that search has computed scores ${\displaystyle v_{1},v_{2},\ldots ,v_{i-1}}$  for child nodes 1 through ${\displaystyle i-1}$ . Assuming a lowest possible score ${\displaystyle L}$  and a highest possible score ${\displaystyle U}$  for each unsearched child, the bounds of the chance node's score is as follows:

${\displaystyle {\text{score}}\leq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+U\times (n-i)\right)}$ 

${\displaystyle {\text{score}}\geq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+L\times (n-i)\right)}$ 

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 ${\displaystyle i}$ 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:

${\displaystyle \alpha _{i}=N\times \alpha -\left(v_{1}+\ldots +v_{i-1}\right)+U\times (n-i)}$ 

${\displaystyle \beta _{i}=N\times \beta -\left(v_{1}+\ldots +v_{i-1}\right)+L\times (n-i)}$ 

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.

• Minimax
• Alpha–beta pruning
• Negamax
• Expected value