## Revision c61630700070f570f62e4016919eb1973e469ca1 (click the page title to view the current version)

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

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

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

## Discussion

From R&N Exercises

• Exercise 1
• Exercise 3