Computational Game Solving

Fall 2026

Focus

The course will focus on multi-step imperfect-information games because most real-world strategic settings are such games. Such games beget additional issues beyond perfect-information games like chess and Go, such as signaling, deception, and understanding deception by others. There has been tremendous progress in the AI community on solving such games since around 2003. This course covers the fundamentals and the state of the art of solving such games.

Course logistics

Instructors	Office	Email
Prof. Tuomas Sandholm	GHC 9205	sandholm AT cs
Ioannis Anagnostides	GHC 6213	ianagnos AT cs

Lecture time: Mondays & Wednesdays 11:00 AM - 12:20 PM.

Lecture location: Doherty Hall 1117

Office hours:
- Tuomas: Mondays after class, 12:20 PM – 1:00 PM in GHC 9205
- Ioannis: Fridays, 2:00 PM – 3:00 PM in GHC 6213

Course structure and evaluation

The course will be lecture based. At the end of the course there will be a few lectures of project presentations by students.

Readings will consist of a mixture of papers and course notes.

Students will complete a final project. It may be done individually or in groups of 2-3 students. It can be theoretical or experimental, or a combination. The students can pick their course project topic subject to instructor approval of the project proposal. The project can be related to the student’s normal research, but it cannot be the student’s normal research itself. We encourage creativity in the course projects.

The deadline for the project proposal is October 9.

Grading will be as follows:

· 50% final project

· 20% final exam

· 20% homework sets (there will be 2 homework sets that may include both paper-and-pen questions and programming assignments)

· 10% completion of readings, attendance, and participation in class discussions

Homework sets

	Released	Due	Files
Homework 1	September 30	October 9	HW1.pdf \| HW1.zip
Homework 2	TBD	TBD

AI policy

For course projects, students may use any AI tool, provided that they explicitly declare their use of AI.

Any submitted homework will receive full credit. Students who declare that they did not use AI on a homework will also receive feedback.

Schedule (subject to change)

Lecture	Date	Topic	Reading(s)	Lecture slides
1	M 8/24	Introduction Course organization. Introduction to game theory. Game representations. Normal form, extensive form. Solution concepts. Properties of 2-player zero-sum games.		Slides
2	W 8/26	Perfect-information games 1 Tree search methods for two-player perfect-information games: minimax search, alpha-beta pruning, iterative deepening, quiescence search, singular extension, evaluation function learning, endgame databases, horizon problem, search depth pathology, chess.		Slides
3	M 8/31	Perfect-information games 2 Monte Carlo Tree Search (MCTS). AlphaGo and AlphaGo Zero.	[Silver et al., Nature 2017]	Slides
4	W 9/2	Equilibrium finding in normal-form games LP formulation of zero-sum normal-form equilibrium computation. Fictitious play and follow the regularized leader (FTRL). Online learning and regret minimization. Mirror descent (MD). Multiplicative weights (MWU). Regret matching (RM) and RM+. Self-play and connection to game-theoretic equilibria.	[Section 4.1 and 4.6 of MAS] [Section 4.2-3 of AGT]	Lecture notes Slides
5	W 9/9	Extensive-form games 1 Extensive-form games. Behavioral representation of a strategy. Kuhn's theorem. Sequence-form representation and sequence-form LP. Construction of counterfactual regret minimization (CFR) and proof of correctness using regret circuits.	[Section 5.2 of MAS] [Section 3.10-11 of AGT] [Zinkevich et al., NIPS 2007] [Farina et al., ICML 2019]	Lecture notes Slides
6	M 9/14	Learning in general-sum games: correlated equilibria and Phi-regret Correlated and coarse correlated equilibrium. Phi-regret and its connections to types of correlated equilibrium. The GGM framework, and Blum-Mansour as a special case.	[Blum & Mansour, JMLR 2007] [Gordon, Greenwald, and Marks, ICML 2008]	Lecture notes Slides
7	W 9/16	Algorithms for minimizing Phi-regret: nonlinear deviations and ellipsoid Achieving swap regret among low-degree deviations. Linear-swap correlated equilibria as a special case. Nonlinear deviations. Expected fixed points. Ellipsoid against hope.	[Zhang et al., NeurIPS 2024] [Farina and Pipis, NeurIPS 2024] [Daskalakis et al., STOC 2025]	Lecture notes Slides
8	M 9/21	Faster no-regret learning dynamics and last-iterate convergence Near-optimal regret using optimism. Connections to last-iterate convergence. Scale-invariant near-optimal RM+ variants.	[Anagnostides et al., ICML 2022] [Anagnostides et al., NeurIPS 2022] [Zhang, Anagnostides, and Sandholm, EC 2026]	Lecture notes Slides
9	W 9/23	Extensive-form games 2: CFR speedups Alternation. Reweighted updates of regrets and strategies, LCFR, DCFR. Dynamic pruning in imperfect-information games. Warm starting from given strategies. Optimistic regret minimization algorithms. Hyperparameter schedules.	[Brown & Sandholm, ICML 2017] [Brown & Sandholm, AAAI 2019] [Farina, Kroer, and Sandholm, AAAI 2021] [Zhang, McAleer, and Sandholm, AAAI 2026]	Slides
10	M 9/28	Team games. Guest lecture by Brian Zhang. Team maxmin equilibrium and TMECor; why the latter is often significantly better. Realization polytope: low dimensional but hard to represent; ways around that in practice. Team DAG and Team PSRO.	[Farina et al., NeurIPS 2018] [Zhang, Farina, and Sandholm, ICML 2023] [McAleer et al., NeurIPS 2023] [Zhang et al., EC 2024]	Slides
11	W 9/30	General automated mechanism and information design. Guest lecture by Brian Zhang. Stackelberg equilibria, correlated equilibria, mechanism design, and information design. Optimal (revenue-maximizing) auctions.	[Zhang et al., NeurIPS 2023] [Kamenica and Gentzkow, AER 2011]	Slides
12	M 10/5	Provably convergent reinforcement learning techniques for imperfect-information games. Guest lecture by Gabriele Farina. Superhuman Stratego.	[Sokota et al., 2025] [Rudolph et al., ICLR 2026] [Kalogiannis & Farina, NeurIPS 2025]
13	W 10/7	Double oracle-based methods Double oracle (DO), policy space response oracles (PSRO), extensive-form double oracle (XDO), anytime PSRO, self-play PSRO, diversity in PSRO. AlphaStar and OpenAI Five.	[Heinrich and Silver, 2016] [Lanctot et al., NeurIPS 2017] [McAleer et al., NeurIPS 2021] [McAleer et al., ICLR 2024]
14	M 10/19	Game abstraction 1 Practical state of the art. Lossless abstraction: GameShrink. Lossy state abstraction. Potential-aware, earth-mover-distance abstraction.	[Brown et al., AAMAS 2015]
15	W 10/21	Game abstraction 2 Abstraction algorithm for distributed equilibrium finding. Action-abstraction algorithms. Reverse mapping. Abstraction pathology. Lossy abstraction with solution-quality bounds. Application of the theory to game modeling.	[Kroer & Sandholm, NeurIPS 2018]
16	M 10/26	Deep learning in tree-based game solving Monte Carlo CFR (MCCFR) and sampling approaches. Deep CFR as an alternative to abstraction. DREAM, ESCHER.	[Lanctot et al., NeurIPS 2009] [Brown et al., ICML 2019] [McAleer et al., ICLR 2023]
17	W 10/28	Real-time reasoning in imperfect-information games 1: State of the art for two-player no-limit Texas hold'em — Libratus (I) History of game theory and AI for poker, rules of Texas hold'em, man-machine match setup.	[Brown & Sandholm, Science 2018]
18	M 11/2	Real-time reasoning in imperfect-information games 2: State of the art for two-player no-limit Texas hold'em — Libratus (II) Subgame solving in imperfect-information games.	[Brown & Sandholm, Science 2018]
19	W 11/4	Real-time reasoning in imperfect-information games 3: Libratus (III) and newer techniques Solving multiple subgames, self-improver, transforming poker knowledge. Sound real-time reinforcement learning for imperfect-information games. Equilibrium refinement in real-time reasoning.	[Brown & Sandholm, Science 2018] [Kubíček, Lisý, and Sandholm, ICLR Workshop 2026] [Kubíček, Lisý, and Sandholm, 2026]
20	M 11/9	Real-time reasoning in imperfect-information games 4: Knowledge-limited subgame solving (KLSS) Limits of subgame solving with common knowledge. Subgame solving without common knowledge. Superhuman Fog-of-War chess. Safe KLSS.	[Zhang and Sandholm, NeurIPS 2021] [Liu et al., ICML 2023]
21	W 11/11	Real-time reasoning in imperfect-information games 5 Depth-limited subgame solving. State of the art for multi-player no-limit Texas hold'em: Pluribus.	[Brown & Sandholm, Science 2019]
22	M 11/16	Final exam
23	W 11/18	Course project presentations
24	M 11/23	Course project presentations
25	M 11/30	Course project presentations
26	W 12/2	Course project presentations

No class: Monday, September 7 (Labor Day); Monday, October 12 and Wednesday, October 14 (Fall Break); Wednesday, November 25 (Thanksgiving Break).

Related courses

Professor	Title	Year	University
Shankar Sastry and Pan-Yang Su	Learning Enabled Multi-Agent Systems	2026	UC Berkeley
Tuomas Sandholm and Ioannis Anagnostides	Computational Game Solving	2025	CMU
Eva Tardos	Algorithmic Game Theory	2025	Cornell
Nika Haghtalab	Foundations of Learning, Decisions, and Games	2025	UC Berkeley
Tuomas Sandholm and Brian Hu Zhang	Computational Game Solving	2024	CMU
Vince Conitzer	Foundations of Cooperative AI	2024	CMU
Tuomas Sandholm and Stephen McAleer	Computational Game Solving	2023	CMU
Gabriele Farina and Constantinos Daskalakis	Topics in Multiagent Learning	2023	MIT
Vince Conitzer, Caspar Oesterhald, Tuomas Sandholm	Foundations of Cooperative AI	2022	CMU
Tuomas Sandholm and Gabriele Farina	Computational Game Solving	2021	CMU
Christian Kroer	Economics, AI, and Optimization	2020	Columbia
John P. Dickerson	Applied Mechanism Design for Social Good	2018	UMD
Fei Fang	Artificial Intelligence Methods for Social Good	2018	CMU
Yiling Chen	Topics at the Interface between Computer Science and Economics	2016	Harvard
Vincent Conitzer	Computational Microeconomics: Game Theory, Social Choice, and Mechanism Design	2016	Duke
Ariel Procaccia	Truth, Justice, and Algorithms	2016	CMU
Tuomas Sandholm	Foundations of Electronic Marketplaces	2015	CMU
Tim Roughgarden	Algorithmic Game Theory	2013	Stanford