Game Theory for Computer Science Cheat Sheet

Updated 2026-05-20

Game theory for computer science sits at the intersection of mathematics, economics, and algorithm design, providing formal frameworks for modeling strategic decision-making among rational agents. It spans two distinct traditions: combinatorial game theory (perfect-information, deterministic two-player games like Nim and Chess) and classical game theory (Nash equilibria, mechanism design, and auction theory). Practitioners apply these tools across AI game-playing, network routing, cybersecurity, distributed systems, and algorithmic mechanism design. The unifying insight is that many computational problems — from adversarial search to incentive-compatible protocol design — are, at their core, games between agents with conflicting objectives.

What This Cheat Sheet Covers

This topic spans 12 focused tables and 112 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Fundamental Game ClassificationsTable 2: Core Concepts in Classical Game TheoryTable 3: Nim and Combinatorial Game FundamentalsTable 4: Sprague–Grundy TheoryTable 5: Minimax and Game Tree SearchTable 6: Monte Carlo Tree Search (MCTS)Table 7: Extensive-Form Games and Solution ConceptsTable 8: Adversarial Search Algorithms in PracticeTable 9: Game Complexity and DecidabilityTable 10: Mechanism Design and Auction TheoryTable 11: Repeated Games and LearningTable 12: Advanced Combinatorial Game Theory

Table 1: Fundamental Game Classifications

Understanding how a game is classified determines which mathematical tools apply to it. The two broadest divisions are combinatorial vs. classical games and impartial vs. partisan — each axis unlocks or closes off entire solution methods.

Game Type	Example	Description
Combinatorial game	Nim, Chess, Go	Two-player, perfect-information, deterministic, no draws (or determined draws) — analyzed with combinatorial or minimax methods.
Zero-sum game	Chess, Poker (fixed stakes)	• One player's gain exactly equals the other's loss • $\sum payoffs = 0$ in every outcome
Non-zero-sum game	Prisoner's Dilemma	• Players' interests partially align or partially conflict • collective payoffs can vary across outcomes
Impartial game	Nim, Kayles, Chomp	• Both players have identical legal moves from every position • Sprague–Grundy theorem applies
Partisan game	Chess, Domineering, Blue-Red Hackenbush	• Move sets differ per player • Sprague–Grundy does not apply — analyzed with surreal-number theory
Perfect-information game	Chess, Go, Checkers	• All players know the complete game state at every decision point • no hidden information
Imperfect-information game	Poker, Bridge	• Some state information is hidden from at least one player • modeled with information sets

Table 1: Fundamental Game Classifications

Game Type	Example	Description
Combinatorial game	Nim, Chess, Go	Two-player, perfect-information, deterministic, no draws (or determined draws) — analyzed with combinatorial or minimax methods.
Zero-sum game	Chess, Poker (fixed stakes)	• One player's gain exactly equals the other's loss • $\sum payoffs = 0$ in every outcome
Non-zero-sum game	Prisoner's Dilemma	• Players' interests partially align or partially conflict • collective payoffs can vary across outcomes
Impartial game	Nim, Kayles, Chomp	• Both players have identical legal moves from every position • Sprague–Grundy theorem applies
Partisan game	Chess, Domineering, Blue-Red Hackenbush	• Move sets differ per player • Sprague–Grundy does not apply — analyzed with surreal-number theory
Perfect-information game	Chess, Go, Checkers	• All players know the complete game state at every decision point • no hidden information
Imperfect-information game	Poker, Bridge	• Some state information is hidden from at least one player • modeled with information sets