Types of Games

• Single player vs Multiplayer:
  • Single Player: The game is the opponent
  • Multiplayer: The other player either compete or cooperate
• Deterministic vs Stochastic
  • Deterministic: The outcome of your move is perfectly predictable
  • Stochastic: There are random elements
• Perfect Information: State is fully observable
• Zero sum vs Collaboration:
  • Zero sum: Competition. One side win what the other lose

Deterministic Games

Modeling

• States: $S, s_0$
• Two Players: MAX and MIN $player(s)$ returns the player to move
• $actions(s)$ returns legal moves
• Transition Functions: $results(s,a)$ Return the next state after a move
• Terminal Test: $terminal(s)$ Check if the game ends
• Terminal Utilities: $utility(s)$ Return MAX’s utility in terminal state s (e.g. positive score for winning, negative for losing)

Min-Max Search

DFS Minimax

1. Choose the optimal next step on each player’s turn (minimize for MIN, maximize for MAX)
2. Recurse until the base case where the game ends

• Guarantee optimal
• Time: $O(b^m)$ - impossible

Resource Limits: Depth-limited search with heuristic functions ⭐