Stochastic Games & Expectiminimax Decision Trees

Real-world environments and games such as Backgammon include elements of chance (dice rolls, card shuffling). In stochastic game trees, we introduce a third type of node: the Chance Node.

The Expectiminimax Formulation:

$Expectiminimax(s) = \begin{cases} Utility(s) & if s is terminal \\ \max_{a} Expectiminimax(Result(s, a)) & if Player(s) = MAX \\ \min_{a} Expectiminimax(Result(s, a)) & if Player(s) = MIN \\ \sum_{s'} P(s') × Expectiminimax(s') & if s is a Chance Node \end{cases}$

In standard deterministic Minimax, an evaluation function requires only an order-preserving (monotonic) scale: replacing evaluation v with v^3 or \log(v) does not alter which move is maximum or minimum.

However, in Expectiminimax, expected utility is a weighted linear sum: \sum P(i) v_i.

Applying a non-linear monotonic transformation alters the expectation! For example, expected value of outcomes (1, 9) with P = 0.5 is 0.5(1) + 0.5(9) = 5. If we apply non-linear transform f(x) = x^2, the expectation becomes 0.5(1) + 0.5(81) = 41, which can invert the preferred decision compared to an alternative move.

Theorem: An evaluation function in expectiminimax must be a positive affine transformation f(x) = a x + b (a > 0) of the true probability of winning to preserve optimal move choices.