CMPUT 657 - Algorithms for Combinatorial Games
- Course overview
- Time and location:
- Course start and end date: Sep 2, 2025 - Dec 8, 2025
- Time: Tuesday and Thursday 14:00 - 15:20
- Location: VVC 1-662, Van Vliet Complex, downstairs - 1st floor, map
- No class:
- Sep 30 - Truth and Reconciliation Day
- Nov 11 and Nov 13 - Reading Week
- Last class: Thu, Dec 4
- Instructor:
Martin Müller,
office: 6-190 University Commons,
email: mmueller
- Office hour: Tuesday after class (in class or in my office)
-
Canvas course site for quizzes, assignment submissions, announcements, discussion forum.
-
Syllabus,
built with Simple Syllabus. The template does not quite work for my purposes, but I did what I could...
- Assessments
- CMPUT 657 Week by Week
- Resources page
- Sample code in Python
Week by Week
Week 1, Sep 2 – 5 (Click on the triangle to show details for a past week)
- Sep 2: first class, introduction and course overview. Types of games and search. Example - game of Clobber. Sample codes and software.
- Sep 2 reading: Course overview,
syllabus, Canvas course site
- Sep 4: Continue introduction. Game of Go.
- Sep 4 reading, read by Sep 8:
D. Knuth and R. Moore.
An analysis of alpha-beta pruning.
Artificial Intelligence 6(4), pages 293 - 326, 1975.
- Slides and Notes:
Week 2, Sep 8 – 12
- Sep 9: Finish Introduction: types of state space - Tree, DAG, DCG; size and complexity of state space. Game tree as union of possible games.
Game of NoGo. Minimax search.
- Sep 11: Discussion of Knuth/Moore paper. More on minimax
- Slides and Notes:
- Lots of Sample code for minimax and alphabeta, with TicTacToe and Clobber examples
- Readings for next week:
Schaeffer et al.,
Checkers is solved, and
Kishimoto et al.,
Game-Tree Search Using Proof Numbers: The First Twenty Years.
Week 3, Sep 15 – 19
- Assessments - Upcoming due dates:
- Sep 16, alphabeta paper discussion
- Sep 21, checkers paper discussion
- Sep 23, proof number paper discussion
- Future: Sep 26, Quiz 1
- Readings and discussions:
Schaeffer et al.,
Checkers is solved, and
Kishimoto et al.,
Game-Tree Search Using Proof Numbers: The First Twenty Years.
- Sep 16: Game of NoGo. Minimax search optimizations
- Sep 18: Game of checkers. Proof number search and df-pn
- Slides and Notes:
Week 4, Sep 22 – 26
- Assessments - Upcoming due dates:
- Sep 21 checkers paper discussion
- Sep 23 proof number paper discussion
- Sep 26 Quiz 1 on Canvas
- Assignment 1 published on Canvas.
Please decide on the teams
for assignment 1 and tell me about it by Sep 30.
- New Reading and discussion:
Randall et al., Expected Work Search.
- Class Sep 23: Assignment 1. Game of Battle Sheep. Continue Proof number search and df-pn.
- Class Sep 25: Wrap-up alphabeta and checkers paper discussions. Game of Hex. Owen Randall Guest Lecture - Expected Work Search.
- Classes, slides:
- Sample code for proof number search:
gametree.py, tic_tac_toe.py, pns.py, ttt_pns.py, clob_1d_pns.py
Week 5, Sep 29 – Oct 3
- Assessments - Upcoming due dates:
- Oct 1 EWS paper discussion
- No class Sep 30 - Truth and Reconciliation Day
- Class plan for Oct 2: Wrap-up proof number and EWS paper discussions.
Finish Proof number search and df-pn.
Introduction to combinatorial games.
- New "Reading" and discussion:
Watch the first 35 minutes of Owen Maitzen's video on combinatorial games.
-
Slides - Owen Randall,
Efficiently Solving Games with Expected Work Search
- Slides - Introduction to combinatorial games
- Sample code for proof number search:
gametree.py, tic_tac_toe.py, pns.py, ttt_pns.py, clob_1d_pns.py
Week 6, Oct 6 – 10
- Assessments - Upcoming due dates:
- Oct 8 Hackenbush video discussion
- Oct 10 Assignment 1 Battle Sheep due
- New: "Reading CGT Intro" and discussion:
Do three tutorials in CGSuite, try out some games, and discuss.
- Oct 7 class: Wrap-up Hackenbush video (Abel). Continue introduction to combinatorial games.
- Oct 9 class: Continue introduction to combinatorial games. Comparing and simplifying games.
Week 7, Oct 13 – 17
- Assessments and upcoming due dates:
- Now: Start work on Quiz 2, due Oct 24, combinatorial games concepts
- Oct 15 Group Discussion due: CGSuite and tutorial
Week 8, Oct 20 – 24
Week 9, Oct 27 – 31
Week 10, Nov 3 – 7
- Assessments - Upcoming due dates:
- Nov 5 Amazons paper discussion due
-
Nov 6 in class: Project step 1, brief in-class presentation
-
Nov 7 Project step 1, written proposal: submit on Canvas (one per team)
- See Research Project and
Step 1
-
Extended to Nov 7: Assignment 2 due
- Read and discuss parts of the paper by Berlekamp,
The Economist’s View of Combinatorial Games. Follow the reading guide!!!
- Nov 4 class:
In class wrap-up discussion MCGS paper.
Two student paper presentations: Alternating linear clobber, TDS+
Assignments 1 and 2 discussion
Topics: mean, temperature and thermograph.
- Nov 6 class:
One student paper presentation: Chopsticks
Project in-class presentations.
-
Game of the Amazons (rules etc, wikipedia)
-
Slides: Mean, temperature and thermograph
- Slides: Solving 5x5 Amazons
- Slides: 5 x 6 Amazons Solution
- Slides: Simple no-search strategies for playing sum games (Hotstrat, Thermostrat, Sentestrat)
- Slides:
Locally Informed Global Search for Sums of Combinatorial Games
- Slides: The Economist’s View of Combinatorial Games
- Slides: The Book for Economic Rules for our Game Example
- Slides: Notes on When to Play One-Sided Sente
- NewSlides for Abel's presentation,
Alternating Linear Clobber is a 1st-Player Win
- TODO: add slides for student presentations
Week 11, Nov 10 – 14
Reading week, no classes
Week 12, Nov 17 – 21
Week 13, Nov 24 – 28
Week 14, Dec 1 – 5, and beyond
Last update: Martin Müller