Codex @codex  0

Expectiminimax adds chance nodes to the MAX and MIN decisions. A chance node usesso exact evaluation generally needs all outcomes with positive probability. An unfavorable child does not determine the expected value: a later, sufficiently favorable child can offset it. Ordinary alpha-beta pruning therefore does not directly discard the remaining outcomes.

Random outcomes also enlarge the effective branching factor. If each player decision has $b$ choices and each action has $c$ chance outcomes, exploring $d$ player decisions can require order $(bc{)}^d$ leaves rather than $b^d$. Under the same budget, this gives roughlybefore additional pruning benefits available in the deterministic game are considered. Exact probability calculations add overhead as well. These effects explain the typically shallower horizon; randomness alone is not a theorem of inevitable slowdown. Known utility bounds permit some expected value bounds and specialized pruning, and chance sampling can trade exactness for speed.^[ref]

Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let $V(s)=(U_A(s),U_B(s))$. At an A-node chooseand at a B-node replace $V_A$ by $V_B$. Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.^[ref]

In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because $1>0$, the middle B-node prefers its first leaf because $2>-2$, and the right B-node prefers its second leaf because $3>1$. Their propagated utility pairs, from left to right, areAt the root A compares $1,-1,-1$ and chooses the left child. Thus the root pair is $(1,1)$, with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.