## Revision c61630700070f570f62e4016919eb1973e469ca1 (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**

- The basic solution technique is
- Minimax search grows exponentially
- heuristic searches are important (Section 6.3)

# Briefing

## 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

- Stochastic Games -

# 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

- Clone the git repo,
`git clone https://github.com/hgeorgsch/pai-exercises.git`

- Change to the
`TicTacToe`

subdirectory - Modify the template to implement your intelligent agent. You should use the minimax algorithm as described for two-player, zero sum games.
- Play the game, using the test scripts:
`python3 ttt.py`

- Consult the README file for details.

This assumes that you have git and python3 installed.

## Discussion

From R&N Exercises

- Exercise 1
- Exercise 3