Abstract strategic board games represent one of the purest mathematical environments for studying decision-making under uncertainty.

1. Deterministic vs. Stochastic Game Trees: The Fundamental Divergence

In classical computational game theory, two-player zero-sum games have historically been categorized by their information state and branching mechanisms. Games of perfect information and deterministic state transitions—such as chess and draughts—adhere to standard Minimax game trees. In these spaces, a node at ply d transitions deterministically to child nodes at ply d+1 via discrete player moves. Because the state transition function is bijective with respect to the selected action, alpha-beta pruning operates with optimal pruning efficiency, reducing effective search complexity from O(b^d) to O(b^(d/2)) under ideal move ordering.

However, introducing a stochastic transition element—such as the roll of two six-sided dice in backgammon—fundamentally shatters the alternating Minimax structure. Instead of a direct transition between MAX and MIN decision layers, an intermediate layer of Chance Nodes must be introduced. This architecture transforms the standard search tree into an Expectiminimax tree, fundamentally altering algorithmic pruning, search horizons, and strategic risk management.

2. The Expectiminimax Formalism

In an Expectiminimax tree, the evaluation function of a state s is defined recursively across three distinct node types:

1. MAX Nodes (Player 1 Decision): V(s) = max_{a in A(s)} V(s, a)
2. MIN Nodes (Player 2 Decision): V(s) = min_{a in A(s)} V(s, a)
3. CHANCE Nodes (Stochastic Environmental Transition): V(s) = sum_{i=1}^{K} P(omega_i) * V(s circ omega_i)

In backgammon, the sample space Omega of two fair six-sided dice contains 36 elementary events, mapping to 21 distinct outcomes:

• 15 asymmetric combinations (e.g., 6-5, 4-2, 3-1), each possessing a probability of 2/36 = 1/18 (~5.56%).
• 6 symmetric doublets (e.g., 6-6, 5-5, 1-1), each possessing a probability of 1/36 (~2.78%), but granting four identical moves rather than two.

Consequently, from any given position, a player does not select an immediate successor state. Instead, nature selects one of 21 dice combinations, and only then does the player select the optimal legal move corresponding to that specific roll. In complex contact positions where each roll generates an average of 20 legal moves, the effective branching factor at a single ply explodes: Branching Factor B_eff approx 21 * 20 = 420

Evaluating even a modest 3-ply horizon via brute-force enumeration requires traversing over 74 million terminal nodes, rendering deep exhaustive search computationally intractable within interactive clock constraints.

3. The Collapse of Standard Alpha-Beta Pruning

In deterministic alpha-beta pruning, if a single child of a MIN node yields a value less than alpha, the entire remaining subtree beneath that MIN node can be immediately pruned. This is because the minimizing player already has a guaranteed outcome that MAX will never allow.

At a chance node, however, this monotonic cutoff principle completely fails. Because the value of a chance node is an expectation—a weighted convex combination of all possible outcomes—no single high or low child evaluation can guarantee whether the overall expected value will exceed alpha or fall below beta. A terrible outcome on a 6-6 roll (probability 1/36) can easily be counterbalanced by favorable outcomes on the remaining 35 combinations.

To salvage pruning efficiency in stochastic trees, specialized algorithms such as Star1 and Star2 (developed by Bruce Ballard in 1983) establish mathematical upper and lower bounds on the possible values that untraversed chance branches can achieve: