(written 2023)

Two-player, Zero Sum games

• State-machine
  • to-move: state \(\to\) player
  • actions: state \(\to\) {action}
  • result: state \(\times\) action \(\to\) state
  • utility: state \(\times\) player \(\to\mathbb{R}\)
• Minimax algorithm:
  • maximises utility for the player currently to move
  • Tree Search: optimise utility bottom-up
    • min nodes and max nodes
  • exhaustive research
• Caveats and variations
  • Branching factor
  • multi-player games - alliances and trust
  • co-operative games
  • \(\alpha\beta\) pruning
  • heuristic searches
  • Type A and Type B:
    • move generation
    • move evaluation
• Monte Carlo Tree Search
  • Monte Carlo \(\sim\) Stochastic Simulation
  • Balance Exploitation and Exploration
• More Caveats
  • Stochastic Games - Chance Nodes
  • Partially Observable Games
    • the percept sequence is no longer the opponent’s move.
  • Limitations - Section 6.7
    • Intractible
  • Approximations and Assumptions
  • Individual moves - no sight of the bigger picture