How can CGT be used to improve MCTS? And vice versa, how can MCTS techniques be used for sums of games?
One example would be to implement a version of Temperature Discovery Search, TDS, in the MCTS framework.
Type of project: MSc or PhD. Requirements are a strong interest in games and algorithms, and mathematical skills to understand the required CGT background. The background could be acquired through an independent study course (Cmput 605).
Most algorithms for playing sums of hot games, such as hotstrat or thermostrat, have two limitations:
1. They assume that local games are simple enough to analyze completely,
and compute e.g. their temperature exactly.
2. The algorithms are static and do not make use of extra available computing power.
The goal of this research is to develop better algorithms that:
1. scale with computational power and
2. approach perfect play in the limit, i.e. are able to solve the game given enough resources
Type of project: MSc or PhD. Requirements are a strong interest in games and algorithms, and mathematical skills to understand the required CGT background. The background could be acquired through an independent study course (Cmput 605).
Example: computation of canonical form of a simple 1xn position in Amazons, B......W, takes exponential time in CGSuite.
Ideas: use thermographs for move ordering, try to prune. play difference games to find dominated options.
Type of project: MSc. Requirements are a strong interest in games and algorithms, and mathematical skills to understand the required CGT background. The background could be acquired through an independent study course (Cmput 605).
Most of the theory of CGT for hot games assumes that subgames are "simple enough". How to play well in sums of complex local games?
Also see Temperature Discovery Search and Sums of Hot Games.
Amazons is well suited for CGT analysis. Much work so far has been on small boards. For example Temperature Discovery Search. This project would seek to develop a strong endgame solver for full (10x10 board) Amazons. A first step is to improve our existing algorithms for board partitioning and finding safe territories. Then, improve search to find "simplest-first" proofs and take advantage of known information on subgames, such as bounds on their mean and temperature.
Solve 6x5 Amazons. This work was started in 2013 but not finished. See Amazons 6x5 attempt. Some new ideas to speed up the remaining search would be good.
Implement a form of Temperature Discovery Search that works for Go, i.e. take Ko fights and other loops into account. Apply that search to real Go endgames, integrate it with Fuego. Several years ago, preliminary work has been done in our group by Enzenberger.
A Go endgame puzzle generator would take a library of local endgames that can be solved by Decomposition Search, and compose full-board problems.
It would also be cool to create new local endgames from games, by "fortifying" the boundaries around the local endgame, to make sure the boundary stones can be proven safe.
Also see the Computer Go pages.
NoGo is a combinatorial game. We have the two strong NoGo programs. They can be improved further by using CGT ideas, such as finding and evaluating subgames. Also, not much research has been done about the type of positions that occur in NoGo.
You can look at a past course, Cmput657 Assignment 1 and Assignment 2, for background information.
At least one of the top clobber programs from the games olympiad, Johan de Koning's Pan, uses CGT, see the screenshots here.
Martin Müller