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