6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games

Next: Status of AI Game Previous: Nondeterministic Games

Nondeterministic Game Algorithm

  • Just like Minimax except also handle chance nodes
  • Compute ExpectMinimaxValue of successors
    • If n is terminal node, then ExpectMinimaxValue(n) = Utility(n)
    • If n is a Max node, then ExpectMinimaxValue(n) = \(max_{s \in Successors(n)}\) ExpectMinimaxValue(s)
    • If n is a Min node, then ExpectMinimaxValue(n) = \(min_{s \in Successors(n)}\) ExpectMinimaxValue(s)
    • If n is a chance node, then ExpectMinimaxValue(n) = \(Sigma_{s \in Successors(n)}\) P(s) * ExpectMinimaxValue(s)