Revision 8941a18c85195a805f5b16feba960d2d1c4adf4d (click the page title to view the current version)

Adversarial Search

Changes from 8941a18c85195a805f5b16feba960d2d1c4adf4d to current

title: Adversarial Search
categories: session

# Reading

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
+ Video lecture [mp4](multiplayer.mp4)/[ogg](multiplayer.ogg)
  provides a few anchor points for the material.
  It does not replace the text book.

# Briefing (Quiz)

## Two-plaer, Zero Sum games
+ What information has to be defined for each state in a minmax tree?
    + What information is specific for minmax trees?
+ What is the difference between minmax trees and and/or trees? 
+ How can we exploit the adversariality of minmax trees compared to and/or trees?
+ What does it mean that Minmax search grows exponentially?
+ Is it possible to avoid exponential growth?
+ Name at least two approaches to reduce the run time.
+ What is the core idea in $\alpha$/$beta$-pruning?
+ What are the benefits of heuristic $\alpha$/$beta$-pruning compared to regular
+ What are the disadvantages of heuristic $\alpha$/$beta$-pruning compared to regular
+ What is the difference between Type A and Type B strategies?
+ What does the area actually searched (expanded) look like after respectively
  a Type A and a Type B search?
+ What is the main idea in a Monte Carlo Search?

+ 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
    - haustive research
+ Caveats and variations
    - multi-player games - alliances and trust
    - co-operative games
    - $\alpha\beta$ pruning
    - heuristic searches
    - Type A and Type B:
        - move generation
        - move evaluation
See also [Notes on Adversarial Search]() (brief bullet points used 2023)

# Exercise

## Tic Tac Toe

+ [Code from github](

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

## Monte Carlo Tree Search

+ [Can you save the forest - Episode 1](

# Debrief

All the algorithms we have studied are based on (discrete) 
**state machine models** and **tree search algorithms** 
in the graph defined by the states and transitions in the
state machines.
It is crucial that we understand the basic structure of these 
models and algorithms well, so that we can adapt them to the 
different special cases we encounter.

+ exhaustive searches in small state spaces
    - BFS
    - DFS
+ non-deterministic environments lead to random transitions
    + modelled by and-or trees
+ partial observation leads to belief states
+ in offline search we can jump to arbitrary nodes to restart the search
    + in online searches we need to backtrack by actual actions in the environment
+ two-player games lead to adversarial transitions
    + Minimax algorithm considers both own moves (max) and adversarial moves (min)
    + Why is adversarial search radically different from search in probabilistic games? 
+ Pruning may be essential to speed up the algorithm
    + Dijkstra prunes subtrees which are known to give longer paths than the best one known
    + alpha-beta pruning applies to minimax search
+ Heuristics are estimates of the value/cost of a node.  This allows
    + Greedu algorithms and best first searches
    + Heuristic pruning, discarding subtrees which look bad, but with no guarantee