CMPUT 657 Course Resources
Contents:
University of Alberta Resources
Computing Resources and Access
-
Computing Resources
for the Department of Computing Science. Access to ohaton, innisfree, coronation, and over 150 undergrad lab machines.
-
More details for access - Owen's notes
Course Readings
Incomplete list. I will add more readings and due dates later.
Click on the triangle to show details for a topic.
Course Readings - Minimax
Optional: Course Readings -
Dynamic programming and Retrograde Analysis of Endgames
Course Readings - Proof-Number Search and df-pn
-
Required: read by Sep 17.
A. Kishimoto, M. Winands, M. Müller and J. Saito.
Game-Tree Search Using Proof Numbers: The First Twenty Years.
ICGA Journal 35(3), 131-156, 2012.
Erratum for this article - see here.
-
Required: read before Sep 25 class.
O. Randall, M. Müller, T. Wei and R. Hayward.
Expected Work Search: Combining Win Rate and Proof Size Estimation.
IJCAI 2024, p. 7003-7011.
-
Optional:
Extra slides: Nagai and Imai, proof of equivalence of df-pn with PNS
-
Optional:
V. Allis, M. v.d. Meulen and J. v.d. Herik.
Proof-number search (access through U of A library), Artificial Intelligence 66(1), pp. 91-124, 1994.
-
Optional:
chessprogramming.org
Proof-Number Search
-
Optional:
chessprogramming.org
Conspiracy Numbers
-
Optional:
AO*, an extension of A* (OR-tree method) for finding least-cost solutions
in AND/OR trees with edge costs and admissible heuristic functions.
C. Gao, On AO*, Proof Number Search and Minimax Search has a discussion and references, including (Nilsson 1980),
which is a textbook containing one popular early formulation, and
(Nagai, 2002) with df-pn+, an extension of df-pn that computes least-cost solutions as in AO*.
Approaches to Over-Counting
- See references in Section 6 of survey paper (required reading)
Course Readings - Combinatorial Games
Incomplete, will mark some more papers as required later.
Combinatorial Games - Introduction
-
Required: watch the first 35 minutes of this video (stop before the infinite numbers part), before Oct 2 class.
Owen Maitzen,
HACKENBUSH: a window to a new world of math, "A playful venture into the vast and mysterious forests of combinatorial game theory".
-
Required: before Oct 14 class, download CGSuite 2.1.1 and do at least the first three tutorials: Welcome to CGSuite!, Using the Worksheet, Games and Rulesets. Try out some games and compute the canonical forms of some positions. Discuss in Canvas.
Combinatorial Games - Impartial Games
-
Required: read before Oct 14 class.
Julien Lemoine and Simon Viennot,
Nimbers are Inevitable.
Theoretical Computer Science 462 (2012) 70-79.
A summary of this work is in the slides on impartial games, which I recommend you study before reading this paper.
- Optional:
Piotr Beling, Novek Rogalski, On pruning search trees of impartial games. Artificial Intelligence 283, 2020, article 103262.
Combinatorial Games Algorithms - Solving Games
Temperature, Thermographs, Coupon Stacks
- Required:
Read only selected sections, see slides for instructions: Elwyn Berlekamp,
The Economist’s View of Combinatorial Games
-
Optional:
Elwyn Berlekamp,
Idempotents Among Partisan Games,
More Games of No Chance, MSRI Publications Volume 42, 2002.
I recommend reading the section on enriched environments, pages 13-15.
This part has the final version of coupon stacks, which start
from temperature t = -1.
-
M. Müller, M. Enzenberger, and J. Schaeffer.
Temperature discovery search.
AAAI 2004, pages 658-663.
-
Y. Zhang and M. Müller.
TDS+: Improving Temperature Discovery Search.
AAAI 2015, pages 1241-1247.
Search Sums of Hot Games
Decomposition Search and Go Endgames
Even More Combinatorial Game Algorithms (optional material)
- Kao's Mean and Temperature search (MTS)
- Generalized thermography, thermographs for ko loops in Go. Slides: Generalized thermography
Course Readings - Specific games
All of these are optional.
Some might be good candidates for in-class paper presentations.
I will add more later.
- Chinese Chess
Ren Wu and Don Beal,
A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames
-
Clobber:
M. Albert, J. Grossman, R. Nowakowski, and D. Wolfe.
An introduction to Clobber, Integers 5(2), 12 pp, Article A01, MR2192079, 2005.
J. Grossman.
Appendix A: report on the first international Clobber tournament. Theoretical Computer Science 313(3), 533-537, 2004.
Describes solutions to Clobber on rectangular boards up to size 5x6.
-
Domineering:
Wikipedia - Domineering
Nathan Bullock,
Domineering: Solving large combinatorial search spaces.
ICGA Journal, 25(2):67-84, 2002.
Nathan Bullock,
Domineering: Solving large combinatorial search spaces.
MSc thesis, University of Alberta, 2002.
- Cram = impartial Domineering:
J. Uiterwijk,
Construction and investigation of Cram endgame databases
J. Uiterwijk,
Solving Cram Using Combinatorial Game Theory
ACG 2019, pp 91–105.
- Phutball:
Sucharit Sarkar,
Phutball draws. Games of No Chance 5, 439–446, 2019.
Phutball Wikipedia article
- Sprouts:
This is closely related to the "nimbers are inevitable" article that we will read.
Julien Lemoine and Simon Viennot,
Computer analysis of sprouts with nimbers.
Games of No Chance 4, MSRI Publications, 2015.
Other Readings
Software and Sample Code
-
Python sample code for this course
- CGSuite, A computer algebra system
for research in combinatorial game theory. We will use Version 2.1.1.
-
MCGS Minimax-based Combinatorial Game Solver
- New: final version
T. Folkersen, Z. Bashir, F. Tavakoli and M. Müller,
SEGClobber - A Linear Clobber Solver.
Advances in Computer Games 2025.
- Other:
Play Combinatorial Games
CGT Math Background
Textbooks
- A CGT textbook, undergrad level.
Lessons in Play: An Introduction to Combinatorial Game Theory, Second Edition, by
Michael Albert, Richard Nowakowski, and David Wolfe.
-
Prove Your Move. An introduction to Discrete Mathematics through Combinatorial Game Theory,
by Kyle Burke and Craig Tennenhouse. Free download.
-
A CGT textbook, grad level. Best and most complete
book about the theory.
Combinatorial Game Theory, by
Aaron Siegel. AMS Graduate Studies in Mathematics,
Volume 146, 2013.
- The classics:
Winning Ways, by Berlekamp, Conway and Guy, and
On Numbers and Games, by Conway.
Article Collections
Games of no chance (GONC) series: the main series of collected research
papers on CGT.
Many theory papers, some experimental work, some surveys.
Related Other Courses
Some courses I found, as of Sep 2025
Last update: Sep 14, 2025, Martin Müller