CS 410/510 Games: Combinatorial Game Theory

# Combinatorial Game Theory

PSU CS410/510GAMES
Lecture 9

May 30, 2002

- Review: Hidden Information
- Failure of pure strategies
- Mixed strategies
- Opponent modeling: RSP
- Iocaine Powder (Dan Egnor) and machine learning
- Strategies
- Naive prediction, adjust once, adjust twice
- Three reverse strategies

- Predictors
- Random guess
- Frequency analysis
- History matching: find previous eg of current sequence
- Variants of these

- Meta-strategies: pick strategy and predictor based on performance over various history sizes

- Strategies

- Theory of Combinatorial Games (Berlekamp, Conway, Guy)
- Our analysis: situational, may be approximate
- CGT: side-independent, exact
- Analyze games where first "stuck" player loses (e.g. Amazons)
- First approximation: who wins in a state if
- Left moves first
- Right moves first

- Moving first is
- Disadvantage: run out of moves sooner
- Advantage: can control what happens

- Example: Blue-Red Hackenbush
- Rules
- Draw a rooted graph with blue and red edges
- Left player deletes a blue edge, right deletes red
- Any disconnected edges are discarded.

- Analysis
- Simplest positions are boring
- Separable positions are more interesting
- Mixed positions are complicated
- Symmetry argument
- Fractional moves

- Value of a position is to Left
- Computed by combining games

- Theory generalizes
- Amazons endgames are analyzable using this theory
- Endgame position values
- Berlekamp analyzes all 2x10 positions
- Seperated endgames are NP-complete! (Buro)