Research Project Ideas

Information for Prospective Students

My group offers research opportunities for both undergraduate and graduate students. I also offer individual study courses for topics relevant to our research, if they are not currently covered by normal courses. If you are already at University of Alberta, please contact me or one of my students. If you want to come to Alberta, please apply through the GAPS system.

Ongoing Projects

These are projects we are currently working on.

Recent Projects

These are some projects we were recently working on.

Project Ideas - Games

Understanding Monte Carlo Simulations

How to analyze the success and failure of simulation policies? How to develop better, improved policies in a principled manner?

Type of project: This could be anything from an undergrad to a PhD project. Requirements are a strong interest in games, and skills to analyze large amounts of data in the form of simulated game "playouts".

Improve Amazons Player Arrow

Improve our amazons player Arrow. Improvements can be achieved in many areas, such as MCTS engine, evaluation function, and endgame knowledge.

Type of project: MSc or PhD. Requirements are a strong interest in games and search algorithms.

Improving user interfaces for game-playing programs

Improve existing UI such as AmazonsGui.

Type of project: Undergrad. Requires skills in UI design, and in reading and extending an existing code base written in Java.

Go Endgame Solver

Go on several small boards such as 5x5 has been solved by Erik van der Werf. Develop a stronger endgame solver based on ideas such as our efficient solution to the graph history interaction problem, and combinatorial game theory.

Monte Carlo Tree Search Improvements

Many improvements are possible. One recent focus is on massively parallel search.

Fuego Improvements

Many improvements are possible. Implement pattern matching, local life and death search, semeai search.

Improve gogui-regress for stochastic algorithms

Improve the gogui-regress tool to run each test multiple times. GoGui GoGui documentation gogui-regress tool

Background: gogui-regress is used both as a regression testing tool and a performance testing tool. Regression testing is used to check that no bugs are introduced that break existing functionality in the game program. This means a regression test should always run with no failures.

For a performance test, typically a number of test positions is given and we count how many of them the program can solve. The current tool is fine for deterministic programs that always give the same answer. However, Monte-Carlo tree search based programs can give different answers because of randomization in their simulation policies. So the results from running a performance test change with each run. To get a better picture, it would be preferable to perform each test multiple times, and check the percentages of how often each test was passed/failed.

  1. Look at how html output is generated. Think about how to format it to show results (e.g. statistics) of multiple runs. Think about log file etc.
  2. Think about running tests on multiple machines and if/how that will affect the design.
  3. Think about command line option(s) for gogui-regress to specify how many tests, (extension: which computers)
  4. Learn the necessary skills in Java, html, scripting along the way
  5. Implement your design.

Type of project: Undergrad, summer student.

Implement RAVE for Amazons, partial moves

The RAVE technique uses statistics over the success of moves what played at any time in a Monte Carlo simulation. It works very well in Go, but not in Amazons when full moves - select queen, move queen, shoot arrow - are considered. Try if RAVE works for partial moves in the game of Amazons, when each of the three move phases is considered separately. For example, it may be beneficial to have move a queen toa certain square, or to block a square with an arrow shot. RAVE for partial moves could possibly learn and use such information.

Type of project: Undergrad, summer student.

Fix problems with AmazonsGui

AmazonsGui is an open source program, similar to GoGui. Itwas developed by a group of undergraduate students at UofA as a course project. This project is about updating AmazonsGui to current Java, to fix a few issues with the program, and bring it up to date with new developments in GoGui. Some examples:
  1. Sometimes the UI and the engine are out of sync when it comes to whose turn it is - the wrong player is to play in the engine.
  2. UI does not update state after arrow shot in each case.
  3. The coordinate system is upside down compared to the GTP command showboard.
  4. Burned-off squares are hard to see on the chess board background.

Type of project: Undergrad, summer student.

Project Ideas - Planning

Motion Planning

Use random walk planning techniques to plan the motion of animated characters.

Type of project: MSc or PhD. Requirements are a strong interest in search and planning, and in the application to motion planning in graphics. The background could be acquired through an independent study course (Cmput 605).

Investigating Macro Actions in Random Walk Planning

How to learn and use macro actions for a planner based on random walks such as Arvand?

Type of project: MSc or PhD. Requirements are a strong interest in search and planning. The background could be acquired through an independent study course (Cmput 605).

Probabilistic Planning

Extend Random Walk methods developed in our research group to the case of planning with uncertain outcomes of actions. Current top probabilistic planners use Monte Carlo Tree Search. We have a lot of expertise in this area in our department, such as our Fuego software.

Type of project: MSc or PhD. Requirements are a strong interest in search and planning. The background could be acquired through an independent study course (Cmput 605).

Parallel Planning

Our system ArvandHerd won the multicore track at the most recent planning competition, IPC 2011. There are many ways to improve the performance of this system and try to scale it to more cores.

Type of project: MSc or PhD. Requirements are a strong interest in search and planning. The background could be acquired through an independent study course (Cmput 605).

Visualization of Plans generated by an automated planner

Automated planning systems can create long solution plans for complex problems. Input domains, problems and plans are described in the PDDL planning language. The purpose of this project is to visualize solutions to planning problems, by showing the sequence of states from the initial state to a goal state. For example, a transportation domain may involve trucks and airplanes transporting packages between different locations on a map.

Relevant Links


Created: Aug 25, 2012 Last modified: May 11, 2016

Martin Müller