CMPUT 657 Project Ideas

Not yet: this page will contain descriptions of some previous projects from similar courses, and some ideas for what you could do this term. As always, having your own ideas is best.

Your own idea! Just discuss it with me first.
Advances in Computer Games Attend the free online conference and get ideas. Free registration and conference program.
Unsolved problems in combinatorial games Games of No Chance 6, pp. 55-98, contains the article Unsolved problems in combinatorial games by Richard Nowakowski. While many of these problems are purely mathematical, some may allow a computational approach. Other articles in the Games of no chance series (see resources) may inspire project ideas as well. You can browse the tables of contents for a start.
Strong Battle sheep solver. It could combine best features of existing solvers, and add more, such as subgame split, recognising when more sheep do not increase the move options, and finding interesting positions and values. This could be implemented in MCGS or standalone. It would also be nice to have a CGSuite implementation of battle sheep; however that by itself is not a full project.
Solve 6x6 Clobber. Current MCGS can solve 6x5 Clobber in a bit more than a day. This size matches the largest known result for almost square rectangles in Grossman's 2004 "Appendix A" paper. With further improvements, e.g. in databases and move ordering, could 6x6 be within reach? If not, what are some early game positions that we can solve? Can we solve other rectangular boards not yet solved by Grossman?
Game-independent move ordering heuristics for MCGS: Develop move ordering heuristics, based either on ideas from minimax search, or from combinatorial games, and show that they work well in a variety of games supported by MCGS. And, can we build a good mechanism to support game-specific heuristics as well?
Extend MCGS to score-counting games. In such games, you can win by having a higher score than the opponent, even if you do not make the last move. TODO add some references, discuss in class?
Implement the algorithm for impartial games from the Beling-Rogalski paper in the readings. Implement in MCGS and compare with our other algorithms. TODO: there is a repo with their own implementation. Hard to read their code.
Solving hot games. Improve the work in Müller and Z. Li. Locally informed global search for sums of combinatorial games TODO link to paper, slides
Use reversible moves in MCGS: Reversible moves simplify the game tree by "skipping" over lines of play to the first "logical" follower. Implement an algorithm to detect reversible moves using minimax search in MCGS. I cannot see how this can be used in the general search, but it can be used for building more efficient databases. This would speed up the search whenever a database hit encounters a subgame with such a move.
Add the EWS algorithm to MCGS: implement a different solving algorithm based on EWS, not negamax. Adapt it to the case of sum games - can we take advantage of sum structure in EWS?
Top down thermography with Alpha-beta like pruning: This is an idea proposed by Berlekamp a long time ago, but has never been researched as far as I know. The usual computation is bottom-up, and computes the thermograph of a position from the thermograph of all options. In contrast, TDS and TDS+ are top-down algorithms. However, they require an extra coupon stack. Can we compute thermographs top-down, without coupons, and take advantage of knowing strong moves, in order to add alphabeta-like cuts?
When is a game an integer?: Given a game G (say a NoGo position), can we determine efficiently whether G is an integer, and if yes, which one? We can do a kind of binary search, but is there something better?

More Project Ideas

Some Cmput 655 Course Project ideas from 2022, with updated comments.

Pruning by Thermographs and Stops: For hot games, we can very often compute thermographs (TG) much faster than canonical forms. The complexity of each TG stays bounded by a small constant in practice. In hot games, many options will be dominated from looking only at the stops of their TG. Use this idea for improved pruning. Implement a thermograph-based game simplification algorithm. Example: 1 x n corridors in Amazons. Many moves, but only one or two good moves.
Thermograph database for classifying infinitesimals: We have built databases with thermographs for small combinatorial games. Example: Amazons up to about $4x5$ area Those were very useful in the $5x6$ Amazons proof On small Amazons boards infinitesimals are quite important We can tell apart 4 outcome classes from the subzero thermograph Equal to 0, Greater, less, or confused The idea here is to distinguish more cases. Idea: play game G + X, where X is an infinitesimal. Build database of thermographs for G+X for several X. E.g. if $G + * = N$ with number N, then we know $G = N+*$, rather than just knowing that G is confused with N. Similar for $G + uparrow$, $G + downarrow$, $G + \uparrow + *$, ... This will allow much better pruning. Application: solve $6x 5$ Amazons, maybe even $6x 6$ Amazons
Stronger Clobber Player using CGT: There were already several good 2017 and 2022 course projects. Still room to improve on those. Take some of the ideas in the linear Clobber solver in Folkersen et al, and try to apply them to two-dimensional boards. For example, build a more powerful (not just larger) database for small Clobber positions.
Large Board Amazons Endgame Solver with CGT: Analyze real Amazons endgames on a full 10x10 board. Need to deal with cases where the separation into subgames is not perfect. E.g. we can get bounds on the result by restricting one player to always keep a separation intact. Need an algorithm to reliably fill large territories. We have hundreds of strong human (and some computer) game records from LittleGolem server. We can analyze how well they play the endgames, and find interesting study problems.
Better Computer Go Endgame Player: Make our existing endgame solver more robust for positions with ``irrelevant ko''. Re-implement the exact algorithm part of the (Mueller and Gasser 1996) paper (the old implementation was lost). It computes upper and lower bounds on game with loops. If bounds coincide, then the loop is irrelevant. Application: solve more realistic Go endgame puzzles.
Implement more of Kao's Algorithm: (The first part of this project, with one move per player, was done in a 2022 project.) Two papers by Kao describe a different algorithm to compute mean and temperature. Kao's algorithm works when integers are always recognized as leaf nodes. He applies it to some games that have this property. Goal: implement his algorithm and compare to our TDS+ experimentally Can you make it work for the general case, where players have more than one move option?
Alpha-beta-like Pruning for Search of Sum Games: The economist's forecast (Berlekamp 1996) can be used to compute upper and lower bounds on the minimax value = the left or right stop of a sum game. We know from the (Mueller and Li) paper that move ordering by temperatures is very strong. Project: combine the approaches from (Berlekamp 1996) and (Mueller and Li) to implement an efficient search. Can test with artificial games, or Go/Amazons.
Temperature Discovery Search for Go: Implement a form of Temperature Discovery Search that works for Go Take Ko fights and other loops into account Follow the ideas in (Berlekamp 1996) and (Mueller 1997) Measure the performance of unmodified TDS+. What problems, what mistakes? Extend TDS+ for case where a ko ban exists Deal with temperatures that are not dyadic fractions
Approximate Temperature with One Coupon?: Scenario game $G$ Idea: search $G$ plus a single coupon of value $t$ Vary $t$ Determine the largest $t$ where the first move switches from taking a coupon to playing in $G$ Compare results and efficiency against TDS, exact temperature computation. How about using two coupons?
Reimplement TDS+: Problem: I have code for TDS but not for TDS+. The student left and took the modified code with them... Use the (pretty detailed) description in the TDS+ paper to reimplement and test it.
Develop and Test an Algorithm for "Semi-stable" Positions: This is from Berlekamp's paper "Economist's View of Combinatorial Games". We will discuss it in a few weeks. I have never seen such an algorithm written down, but I think I kind of know how to develop this. Berlekamp: "Semi-stable positions can be treated as stable or as unstable. Treating them as stable yields the simplest and most convenient economic analyses. Treating them as unstable leads to more refined, more complicated algorithms that exploit the calculus of infinitesimal games to get the last move at each t, whenever possible."

Revisit Previous Course Projects?

Some previous course projects have been successfully completed. However there might still be useful follow-up work.

NoGo: (See recent papers by H. Du) NoGo rules are like Go but capturing is forbidden. This completely changes the flavor of the game, e.g. no loops. Not much research has been done about the type of positions that occur in NoGo. Build endgame databases for NoGo and research the values hat occur in this game. Can we solve larger NoGo positions? How hot do NoGo positions get? (Probably not very hot?)
Improve Impartial Clobber solver: In a 2022 course project, Dai and Chen develop an efficient solver for impartial Clobber on $1 x n$ and $2 x n$ boards based on algorithms for searching impartial games (Beling 2020, Lemoine 2012). Their solver computes the nim value of a given game position, including values of (BW)^n for many n up to 42, except for n in {17, 21, 29, 40}. It also computes values of (BBW)^n for all n up to 11, n=13, n=18, and n=20. Can you improve it? Maybe using MCGS? How large boards can you solve? Does a pattern of Nim-values emerge? This is problem 1 in https://perso.liris.cnrs.fr/eric.duchene/articles/Survey.pdf . Since Clobber appears to be a hard game even on regular positions, what about the impartial version? What can we say about 2-player Impartial Clobber, where the rules are the same, except that each player can indifferently move a black or a white stone. Build a strong solver based on all the best ideas from class and the literature. Verify the hypotheses about values of $(BW)^n$ and $(BBW)^n$ for more values of $n$ Study random games, find interesting game values, etc.

Last update: Oct 10, 2025, Martin Müller