Troyis™ is an addictive online flash game where you move a chess knight through increasingly difficult puzzles. After hours and hours of playing, sometimes late into the night, I decided I'd waste even more of my time and write a little program that can play the game on its own. The result is quite amazing -- imagine Garry Kasparov riding Seabiscuit! See for yourself:
The rest of this post will show you how this little guy (a mix of R and AutoHotKey) works but first, let's review the rules and go through a little theory.
Game rules
The rules are quite simple: as the game starts, a chess knight is placed at the top left corner of a square board where only a few squares are painted in white. The goal is for you to move the knight with your mouse, and make it visit all the white squares, as quickly as possible.
As you progress through the levels, the size of the board increases and the time limit for solving each puzzle decreases.
Finding an optimal path
In the beginning, learning how the knight moves and how to go from one square to another faster and faster can get you far into the game. But eventually, as you start mastering the game, what will really make a difference is how much time you can save by not re-visiting squares you once visited before. In other words, how short your path to a solution can be. Ideally, the shortest path would be one that visits each square only once, as shown below.
In graph theory, the problem of finding a path that visits each vertex of an undirected graph exactly once is a well-studied problem known as the Hamiltonian path problem, a special case of another classic: the travelling salesman problem. The problem is NP-complete, a class of problems so difficult that there is no known efficient algorithm for systematically finding a solution, especially as the problem's size increases. Luckily for us, Troyis puzzles are always small enough (at most 46 vertices and a maximum degree of 8) that we can come with very decent algorithms that will do just fine in most situations.
What I implemented is a backtracking algorithm. All possible paths are explored recursively: at each step, a path of length n can give rise to multiple paths of length n+1 by considering all allowed moves. I also used a number of rules for abandoning bad paths as early as possible. For example, since it is easy to see that if a non-visited square has only one non-visited neighbour then it has to be the final vertex of a hamiltonian path, then we can cut short any path that has two such squares as it won't provide a solution. To increase the chances of finding a hamiltonian path quickly, I also included a simple heuristic: at each step of the recursion, we first try to move the knight to the square that has the fewest possible onward moves, as an attempt to preserve good overall graph connectivity.
It is only later, while researching for this blog post that I found my algorithm is an implementation of the Warnsdorff's rule for solving an eerily similar problem to ours: the Knight's tour. Oh well...
The program
To me, writing the Hamiltonian path solver seemed like the easy part. I did it in R. What I thought would be really hard is to embed the solver in a higher level program that can interface with my internet browser. That was until I found AutoHotKey, a simple programming language for writing automation scripts under Windows. The main program is thus an AutoHotkey script GUI (main.ahk) with two main actions:
- SelectFrame which asks the user to locate the chessboard by drawing a rectangle in a click, hold and drag fashion. Why? I thought that asking the user where the chessboard is would save me a lot of work trying to figure it out programmatically from a full screenshot.
- Solve which does all the heavy work, in this order:
- Takes a snapshot of the chessboard.
- Calls a R script (solver.R) that successively:
- parses the chessboard snapshot into a matrix of booleans (to be visited or not),
- finds a Hamiltonian path, i.e., an optimal path that visits each square only once,
- writes a AutoHotkey script (a series of mouse clicks) for solving the puzzle.
- Runs the AutoHotkey script just created above.
The code
People interested in checking out the code are free to do so on github.
Comments welcome!
