Weeknote #9 (w/e 11/7/10)

Only one thing of significance to report since my last weeknote; the acceptance of a fun little conference paper on solving a puzzle game that has, so far, escaped the attention of the algorithms community.

The Zen Puzzle Garden is a one-player puzzle game, involving a monk raking a traditional Japanese rock garden. The aim is to find a series of moves that allow the monk to rake all of the available sand, whilst negotiating rocks, pushing statues and collecting leaves - all without getting stuck in a dead-end.

While the problem is easy to describe, it's related to puzzles like Sokoban, which are actually very difficult to solve automatically (ie. with a computer program), in the general case. Jack Coldridge, who graduated from MMU a year ago, worked on this problem with me for his final-year dissertation, and we then developed it further into a full paper. The title, Genetic algorithms and the art of Zen is a play on David Goldberg's 1989 paper Zen and the art of genetic algorithms, which itself references Robert Pirsig's famous book.

Problems such as Sokoban are difficult because there are, potentially, a vast number of possible solutions to consider (where a solution is a path through the garden, in this example). Most solutions will be incorrect or "illegal", and the problem is to find the "needles in the haystack" (that is, the correct solutions). These so-called NP-hard problems are the most "interesting" problems in combinatorial mathematics, because they're the most challenging. The practical significance of such problems lies in the fact that they are related to "real world" problems of great importance, such as scheduling, packing and routeing. For a nice review of hard puzzle games, see this paper (PDF).

Several methods have been applied to the solution of such problems, including "traditional" algorithms, which use a "tree-based" approach to searching the space of possible solutions, as well as biologically-inspired algorithms. In the paper, we used a genetic algorithm to "evolve" paths through the garden. We start with a set of random paths, and see how well they solve the problem. Some will be "less bad" than others, so we keep them and use them to "breed" the next generation of solutions. Gradually, the power of natural selection (combined with a sprinkling of mutation) forces the population towards better and better solutions.

We found that our method was capable of finding the optimal (ie. shortest) solutions in the vast majority of cases, and it required far less processing power than another standard algorithm. Importantly, we have highlighted a new problem for the AI/puzzle community to get its teeth into.

The paper has been accepted for presentation at the IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), to be held in Liverpool, on 8-10 September 2010.