Expectiminimax Tree - Pseudocode

Pseudocode

The expectiminimax algorithm is a variant of the minimax 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 * 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.)