Name		Name	Last commit message	Last commit date
parent directory ..
README.md		README.md
assignment_connect4.ipynb		assignment_connect4.ipynb
assignment_dots_and_boxes.ipynb		assignment_dots_and_boxes.ipynb
assignment_mean_connect4.ipynb		assignment_mean_connect4.ipynb
tictactoe.py		tictactoe.py
tictactoe_alpha_beta_tree_search.ipynb		tictactoe_alpha_beta_tree_search.ipynb
tictactoe_and_or_tree_search.ipynb		tictactoe_and_or_tree_search.ipynb
tictactoe_definitions.ipynb		tictactoe_definitions.ipynb
tictactoe_heuristic_alpha_beta_tree_search.ipynb		tictactoe_heuristic_alpha_beta_tree_search.ipynb
tictactoe_interactive.ipynb		tictactoe_interactive.ipynb
tictactoe_monte_carlo_tree_search.ipynb		tictactoe_monte_carlo_tree_search.ipynb
tictactoe_monte_carlo_tree_search_restricted.ipynb		tictactoe_monte_carlo_tree_search_restricted.ipynb
tictactoe_pure_monte_carlo_search.ipynb		tictactoe_pure_monte_carlo_search.ipynb

README.md

Chapter 5: Adversarial Search and Games

Contents

Defining a Game

Example Tic-Tac-Toe

Connection to search with nondeterministic actions (from Chapter 4.3)

Example: Solving Tic-Tac-Toe with And-Or-Tree Search. Here the opponent is seen as part of the environment, i.e., each action by the player is followed by an unknown action of the opponent which, from the viewpoint of the player makes the outcomes of actions nondeterministic.

Solving games using adversarial search

Interactive game play

Example: Play Tic-Tac-Toe Interactively (Simple Implementation)

Assignments

Assignment: Adversarial Search: Playing Connect 4
Assignment: Adversarial Search: Playing "Mean" Connect 4
Assignment: Adversarial Search: Playing Dots and Boxes

Connection to Machine Learning (more in Chapter 19)

The example Learn to Score a Tic-Tac-Toe Board by Example uses a neural network trained on self-play data to lean 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)

The example Learning to Play Tic-Tac-Toe with Q-Learning implements a simple table-based Q-learning algorithm to play the game.

License

All code and documents in this repository is provided under Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License