Chapter 5: Adversarial Search and Games

Defining a Game

• Defining Tic-Tac-Toe

Connection to Search with Nondeterministic Actions (from Chapter 4.3)

• Solving Tic-Tac-Toe with And-Or-Tree Search. Here, the opponent is seen as part of the environment: each action by the player is followed by an unknown action by the opponent, making the outcome nondeterministic from the player’s viewpoint.

Solving Games Using Adversarial Search

• Solving Tic-Tac-Toe with Minimax Search and Alpha-Beta Pruning
• Solving Tic-Tac-Toe with Heuristic Alpha-Beta Tree Search
• Solving Tic-Tac-Toe with Pure Monte Carlo Search
• Solving Tic-Tac-Toe with Pure Monte Carlo Search + UCB1 Selection Policy

Interactive Game Play

• Play Tic-Tac-Toe Interactively (Simple Implementation)

Exercises

• Adversarial Search: Playing Connect 4
• Adversarial Search: Playing “Mean” Connect 4
• Adversarial Search: Playing Dots and Boxes

Connection to Machine Learning (more in Chapter 19)

• Learn to Score a Tic-Tac-Toe Board by Example uses a neural network trained on self-play data to learn an evaluation function that can be used as a heuristic in Heuristic Minimax Search or as a playout policy for Monte Carlo Search.

Connection to Reinforcement Learning (more in Chapter 22)

• Model-free Reinforcement Learning to Play Tic-Tac-Toe with Q-Learning.
• Model-based Reinforcement Learning to Play Tic-Tac-Toe with Value Iteration.

License

© 2025-2026 Michael Hahsler. All code and documents in this repository are provided under Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License