Tic Tac Toe

• or Noughts and Crosses (pg 166).
• Everyone knows the game?
• What's the size of the search space?
• Is there some symmetry?
• The big difference is that the agent doesn't control all of the moves. There are two agents.
• This leads to adversarial search.
• A common algorithm here is Minimax. One side tries to minimize (say X), and the other maximize (say O).
• This requires an evaluation function. In this case let's just use -1 for X wins, 1 for O wins, and 0 for a draw.
• Can you draw the tree?
• It should always end in a draw if both sides play correctly.