whoashish's cp notes

Home

❯

20. Game Theory

20. Game Theory

Oct 08, 20261 min read

  • i. Combinatorial Games and Nim: P/N positions, Bouton’s theorem, misère Nim, Moore’s Nim, staircase Nim and the variant table.
  • ii. Sprague-Grundy: every impartial position is a Nim heap; mex, XOR of sums, certified periods (Kayles, Dawson), Lasker’s Nim, coin-turning games.
  • iii. Hackenbush and Partizan Games: green Hackenbush on any graph (colon and fusion), Blue-Red stalks, dyadic game values and the simplicity rule.
  • iv. Loopy Games and Retrograde Analysis: win / loss / draw with optimal lengths on cyclic game graphs, and the generalized Sprague–Grundy function for sums.
  • v. Game DP, Minimax and Game Search: advantage DP, negamax, alpha-beta, PVS, Zobrist hashing, proof-number search, MCTS with UCT.
  • vi. Games on Graphs and Matchings: vertex geography via Gallai–Edmonds, cops and robber via dismantlability, and which graph games are PSPACE-complete.

6 items under this folder.

  • Oct 08, 2026

    i. Combinatorial Games and Nim

    • game-theory
  • Oct 08, 2026

    iii. Hackenbush and Partizan Games

    • game-theory
  • Oct 08, 2026

    v. Game DP, Minimax and Game Search

    • game-theory
  • Oct 08, 2026

    ii. Sprague-Grundy

    • game-theory
  • Oct 08, 2026

    iv. Loopy Games and Retrograde Analysis

    • game-theory
  • Oct 08, 2026

    vi. Games on Graphs and Matchings

    • game-theory