Solving Zero-sum Game for Multi-agent

Description:

• Zero Sum Game

Value of a state:

• Assume knowing all terminal states and values of all states
• Value of any state is the best achievable outcome (utility) from that state
  • meaning the MAX(x)/MIN(x) of all of its children’s Terminal State
• $V(s)={\text{max}}_{s^{\prime }\in \text{children}(s)}V(s^{\prime })$ for MAX agent and $V(s)={\text{min}}_{s^{\prime }\in \text{children}(s)}V(s^{\prime })$ for MIN agent
• However, given that agents take turns, MIN agent will take state with min $V(s)$ at its turn and likewise for MAX agent
  • 

Minimax search

• and expactimax
• Expectiminimax Search