In this course we delve deeply into the world of combinatorial games, and learn how to solve them by computer algorithms. Combinatorial games are two player games with perfect information, where both players know the game state completely. Much research on two player games has pursued one of two main directions:
We will discuss both, with a strong focus on the second goal of solving games. For both playing and solving, most games programs use a standard search algorithm such as alphabeta minimax search or Monte Carlo Tree Search (MCTS). In the standard approach, each search state represents a complete board position. In this course, we study algorithms that take advantage of the sum game structure that is typical for combinatorial games: a game consists of several independent subgames, and a player must choose to play in exactly one of these at each turn. Examples are games such as Nim, Clobber, Amazons, endgames in the game of Go, and many others.
There is a very strong computational advantage that comes from having sumgame structure: We can gain a lot of information, greatly reduce the search needed, or even play perfectly, from analysing individual subgames, which have a much smaller state space than the full game.
In the first part of this course we study the basic concepts of classical (full-board) search methods such as minimax, alphabeta and proof number search. Next, we study the basics of combinatorial games, leading to algorithms that can play or solve games with subgame structure. We start from basic concepts and proceed step by step to the current state of the art. The course will focus on algorithms and computational aspects, as opposed to studying combinatorial game theory as a purely mathematical subject.
Our course includes a large hands-on component, where you will work on concrete examples and program your own algorithms. We will be building on software such as Siegel's CGSuite and our own Minimax-based Combinatorial Game Solver (MCGS). Projects can be done either individually or in small teams.
Martin Müller, last update Jul 23, 2025