Recent Projects
Mini Bio
My PhD research was in computer science and complexity science, although I also published in web-technologies (and even paleontology!) I have founded, run and sold a high-tech business based on my research and written two technical text-books published by Elsevier.
Puzzle Setting Turing Test
October 2007 - December 2007
I developed code to produce logic puzzles of a publishable standard that had the feel of hand-build puzzles.
For many commercial logic puzzles (such as Sudoku and its variants), customers will pay a premium for puzzles that are hand-created. Computer-generated puzzles are built without a sense of how they will be solved, and the features of the puzzle that will act as hints or red-herrings for the solver. As such computer-built puzzles are of patchy, and typically poor quality.
I was asked to improve the state of the art in puzzle generation. The software I built uses a model of how players solve the puzzles, along with state of the art AI algorithms to optimize that experience. It can anticipate the major routes through the puzzle, and craft each one to be more or less difficult. It can generate puzzles that involve the same set of solving steps, but have different sets of hints to make the solving process smoother or more tricky. It can work in interactive mode with a human puzzle-setter, giving feedback on the validity of the puzzle, where additional puzzle features are required, and the solving process that would result.
The software is designed to be generic: it can create puzzles for any non-linguistic logic puzzle and can be extended to new puzzles by defining a new game module in the source code. As delivered it had modules for Sudoku and several of variations (including multi-board variants), Kakuro and polyomino tilings (which is a common test case for this kind of algorithms and can be used to show performance characteristics).
The software is currently being used to generate Sudoku variants indistinguishable from human-set puzzles.