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