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
Click on the triangle to show details for a past week.
Week 1, Sep 2 – 5
- 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
- Assessments - Upcoming due dates:
-
Oct 21 In class wrap-up discussion CGSuite
- Oct 22 Group Discussion due: Nimbers
- Oct 23 Pick paper for your presentation and let Martin know; add it to signup sheet
- Oct 24 Quiz 2 due
-
Assignment 2 published - combinatorial games
-
Oct 21 class: impartial games algorithms, rationals
-
Oct 23 class: Finish rationals; Assignment 1 discussion;
Sums and incentives
- Slides added Oct 16: SEGClobber - A Linear Clobber Solver,
talk by Taylor
- Slides: rationals.pdf
- Slides: sums of hot games; incentives
-
Oct 21 - 23, Optional: Advances in Computer Games conference. Online,
free registration,
conference program
Week 9, Oct 28 – Nov 4
- Assessments - Upcoming due dates:
-
Oct 31: Assignment 2 due
-
Oct 31 Research Project
Step 0 due - form teams and discuss project ideas
- Oct 28 class: Nimbers paper discussion wrap-up.
Two student paper presentations.
Start mean, temperature and thermograph.
- Oct 30 class: Two student paper presentations.
Continue mean, temperature and thermograph.
- Slides: Mean, temperature and thermograph
- TODO: add student slides for presentations
Preview
-
Nov 4 In class wrap-up discussion MCGS paper
- Nov 6 Project step 1, written proposal
- Nov 7 Project step 1, brief in-class presentation
- Topics: MCGS intro; More on sums; the incentive of a move; incentive-based pruning
- Slides: mean, temperature and thermographs
- Slides: Solving 5x5 Amazons
Last update: Martin Müller