brainwagon

John Bentley demonstrates quite adequately in his book Programming Pearls that to write even the simplest program, say, one that does binary search, is frequently fraught with peril and subtle errors. If you try to write a binary search, chances are you’ll get something wrong. Even Bentley’s own binary search contains a potential overflow condition which might manifest itself as an error if you are searching Google-sized tables.

It should come as no suprise that most implementations and descriptions of alpha-beta search (the key algorithm that you need to write, say, a checkers program) have similar flaws. Most of them don’t actually list the preconditions and invariants that are supposed to be maintained throughout program execution, and in fact, if you actually chose to write some down, you’d find that most of these implementations and descriptions wouldn’t actually work.

Irritatingly, most of them work most of the time. A couple of days ago I started doing what I should have done all along: develop some unit tests and scaffolding for my checkers program. The first thing I discovered was a subtle bug in my alpha-beta code. By comparing the score returned by alpha-beta and a simple minimax traversal of the same tree, I discovered that my code didn’t return the same values. It wasn’t hard to figure out the bug then.

I then tried doing some modifications to do aspiration search with very narrow, and ultimately empty search windows. I discovered an error in those too, and it was due to a misconception
of how alphabeta actually operates in so-called “fail-soft” mode. I had thought that the return value was the minimax value if it was greater than or equal to alpha and less than beta, but the reality is that is only true if the return value is greater than alpha and less than beta. If you get this wrong, null search windows don’t operate properly, and you won’t get the proper minimax value.

This all means that I’m making headway on my checkers program.