Currently on Hold / Previous and Future Research

These are good research topics for me, but no one in my group is actively working on these topics right now. If you have an interest in one of those topics, please talk to me.

• SAT Solving and Exploration
• Leela Chess Zero learning in chess endgames
• Understanding and improving Monte Carlo Tree Search
• Utilizing state similarity in Monte Carlo Tree Search. This question is at the core of generalization in search and learning. For example, Alpha Zero architectures learn a deep neural net from self play, which generalizes to play new, unseen positions at a very high level. Less effort has been put into methods that use similarity directly in the search. One successful example is our Memory-Augmented Monte Carlo Tree Search (M-MCTS) algorithm (paper).
• Combinatorial Game Theory, especially efficient algorithms that combine search and subgame decomposition
• Parallel game tree search and parallel planning
• Domain-independent planning, random walk planning, motion planning
• Exploration methods for motion planning
• Exploration methods for probabilistic planning and MDP (future topic)
• Random Sampling from Time-Changing Discrete Distributions
• Better algorithms for best-arm identification in bandits and tree search
• The Fuego framework for games
• Programs and algorithms for specific games:
  • Go
  • Amazons, an interesting game combining ideas from chess and Go
  • Clobber
  • The Fuego Go program
  • Feature learning for Go
  • NoGo, a new combinatorial game
  • Search and deep learning for Hex
• Decomposition Search, solving hard Go endgames by divide-and-conquer and combinatorial game theory
• Proof Set Search
• Partial Order Bounding
• Adversarial Planning
• Incremental Algorithms for topological sorting and solving systems of difference constraints
• Other search algorithms: path-finding, Post's correspondence problem

SAT Solving and Exploration

Md Solimul Chowdhury, Jia-Huai You, Martin Müller.

You can find publications, talks, and code on Solimul's homepage.

Leela Chess Zero learning in chess endgames

Rejwana Haque, Ting-han Wei, Martin Müller.

Leela Chess Zero (Lc0) is one of the strongest AlphaZero type open-source chess programs. To evaluate how well current AlphaZero type architectures learn and play late chess endgames, we perform a systematic analysis of Lc0's decisions for three, four, and five piece endgames. In addition to statistical results, we also present interesting case studies.

This project was part of research theme 3.

R. Haque. On the Road to Perfection? Evaluating LeelaChess Zero Against Endgame Tablebases. MSc thesis, University of Alberta, 2021.

R. Haque, T.-h. Wei and M. Müller. On the Road to Perfection? Evaluating LeelaChess Zero Against Endgame Tablebases. Accepted for Advances in Computer Games (ACG 2021).

Last modified: Apr 10, 2022