= Solution
<Expectiminimax> adds <chance nodes> to the MAX and MIN decisions. A <chance node> uses
$$
V(s)=\sum_j p_jV(s_j),
$$
so 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 roughly
$$
d_{\mathrm{stochastic}}\approx\frac{\log n}{\log b+\log c}
$$
before 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.<CS 188 stochastic and general game notes>[§3.3, chance-node expected-value backup; §3.3.1, mixed layer types]{ref}
Back to article page
