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

Adversarial Search

Reading

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)

Briefing

Exercise

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 https://github.com/hgeorgsch/pai-exercises.git
  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 ttt.py
  5. Consult the README file for details.

This assumes that you have git and python3 installed.