Saturday, August 05, 2006

Minesweeper, success at last!

I had this project, that I started in 2002, to write a program that plays Minesweeper like I do. My goal was to reproduce, as far as I could, the actual thought processes that went on my mind, rather than to reach for linear algebra, minimax algorithm, or some other ad-hoc hacked together algorithm*.

I made some SUnit tests, with beautiful messages such as thereAre: anIntegerMines in: aCollectionOfSquares, so that I could create stress tests for each solver prototype, and off I went to write them. But I would get stuck --- either the solver would completely fail to see dependencies that were there, or it would end up resorting to brute force.

But when people play, they do not need the age of the universe to solve a particular game --- in fact, they seem able to realize that there are multiple solutions without much effort. How do they do it, then, if they couldn't possibly use brute force?

So last night, something told me that I had to play Minesweeper but this time paying attention to how I thought about it, instead of trying to reproduce the thought process after the fact. So I played with attention... and I realized that my previous mistake had been not to separate two phases of solving. One is the "mark/unmark everything that is obvious" phase. The other one is capable of "marking/unmarking" when nothing is obvious. And because I had combined them in my earlier attempts, the code ended up reflecting my confusion.

In an inspiration attack, I did better in a couple hours than I did in all the previous months of work, and for the first time a beautifully written solver passed all the stress tests.

It was a great experience, and for more than one reason. This project lives in a Stable Squeak image. It's about 2mb, and has all the refactorings I had done for Morphic. One that I frequently remember is that I replaced all the event mechanisms with when:send:to:, without needing to restart Morphic. Such nice memories!

* Incidentally, Google knows about many hacked together algorithms that play Minesweeper, but none that I know is written rigorously :(.

No comments: