Revision 7899ce29e7b447a66e54ebaae9cf2523c1a45264 (click the page title to view the current version)

Notes on Adversarial Search

Changes from beginning to 7899ce29e7b447a66e54ebaae9cf2523c1a45264

---
title: Adversarial Search
categories: notes
---

(written 2023)

# Two-player, 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