Revision c61630700070f570f62e4016919eb1973e469ca1 (click the page title to view the current version)

Adversarial Search


R&N Chapter 6

  • The fundamental concept is two-player, zero-sum games
    • The basic solution technique is minimax search
  • Minimax search grows exponentially
    • heuristic searches are important (Section 6.3)


Two-plaer, 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


Tic Tac Toe

I was not able to find suitable exercises on CodinGame, so instead, I have provided a simulator for you. You should

  1. Clone the git repo, git clone
  2. Change to the TicTacToe subdirectory
  3. Modify the template to implement your intelligent agent. You should use the minimax algorithm as described for two-player, zero sum games.
  4. Play the game, using the test scripts: python3
  5. Consult the README file for details.

This assumes that you have git and python3 installed.


From R&N Exercises

  • Exercise 1
  • Exercise 3