CMPUT 657 - Algorithms for Combinatorial Games

Contents:

• Course Overview
• More Detailed Course Content
  • Part 1 - Search for Two player board games
  • Part 2 - Introduction to Combinatorial games
  • Part 3 - Efficient algorithms and case studies for combinatorial games
  • Limits: what this course is NOT about

Course Overview

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:

1. Playing well against humans and other programs
2. Solving games by finding perfect (not just very good) play

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.

Detailed Course Content

This list reflects my plan at the start of term. Details will change depending on our speed of progress, student and instructor interests, and new publications we can discuss.

Part 1 - Two player board games

About one month: Introduction to two player games and solution strategies. Games, minimax search, playing vs. solving, alphabeta and proof-number search, search efficiency

• Types of games. Introduction to two player board games. Course logistics, types of games, first examples, states and state spaces
• Basic solution strategies for games: minimax and alphabeta. Size and structure of search space
• Solving games more efficiently - opening books and endgame databases
• Proof-number search methods PNS and df-pn, expected work search (EWS)

Part 2 - Introduction to Combinatorial games

A bit more than one month: We will discuss combinatorial games using many examples such as Go, NoGo, Amazons, Clobber, Domineering,... We will also begin our investigation of basic algorithms for playing combinatorial games well, or perfectly, by using the subgame structure. We will use software tools: CGSuite and MCGS.

• Divide and conquer for solving large problems. Basic concepts of combinatorial games, winning by making the last move, splitting a game into a sum of subgames, examples
• Types of combinatorial games: Impartial and partisan games, the four outcome classes, hot games, games that are numbers
• Basic solution strategies - solving combinatorial games from first principles. Using full-board minimax search. Relation of minimax to combinatorial games concepts. MCGS software
• The mathematical approach to combinatorial games. Canonical forms, CGSuite software
• Towards efficient algorithms. Simplifying games, improving search algorithms.
• Algorithms for impartial games: MEX (minimum excluded number), Lemoine/Viennot, Beling/Rogalski
• Case studies in MCGS and CGSuite: Clobber, Nogo, impartial games,...

Part 3 - Efficient algorithms and case studies for combinatorial games

Remaining course time: Studying further topics while working on course projects. In this part of the course, we study more algorithms for both playing and solving combinatorial games. At the same time, you will deepen and apply your knowledge by doing a software project in a small group. You will have a large degree of freedom in choosing our topics, both for projects and for in-class discussions, as long as it fits our course.

We will discuss a subset of the topics below, plus possibly others:

• Exact and approximate solutions
• Temperature, thermographs, and related algorithms
• Algorithms for sums of hot games. Hotstrat, thermostrat etc. Using temperature in search
• Building and using databases with thermograph information
• Forward search for temperatures - Temperature Discovery Search and TDS+ algorithms
• Scaling up to large subgames, and to sums of many subgames
• Research papers
• Deep dive into MCGS - algorithms, data structures, optimisations.
• Deep dive into CGSuite - implementing basic CGT operations. (In-)efficiency of operations. Strategies for speeding things up.
• Case study - Go endgames. Finding safe stones and territories, board decomposition, local search, incentives, finding a globally good move.
• Case study - Amazons on small boards. 5x5 and 5x6 solutions.
• Case study - Domineering. Search and knowledge.
• Case study - Clobber as an all-small game. Database of infinitesimals.
• Generalized thermography - dealing with position repetition (Ko) in Go

Limitations: what this course is NOT about

This course covers a lot of material from a relatively narrow area. There are many other interesting related topics that we will not discuss here, such as:

• Heuristics for evaluating game states. While the course is part of heuristic search in the widest sense, we will not really talk much about heuristics. Our focus will be on algorithms that use combinatorial sum game structure.
• This course is not about games with imperfect or incomplete information, such as poker, backgammon, video games etc. It is also limited to two player games.
• This course is not focused on Alpha Go, Alpha Zero, Muzero and similar learning algorithms.
• This course is not an introduction to the mathematical theory of combinatorial games. While we will learn a little bit of that along the way, our focus is on efficient computation and algorithms.
• This course is not about the type of ``classical'' game theory used e.g. in poker or in economics, which deals with bluffing, Nash equilibria, best responses etc. This course is about algorithms in combinatorial games. We study the same games as in combinatorial game theory.

Martin Müller, last update Aug 5, 2025