Improved AI

alex on 2007/09/05 13:32 of Lazy Susan

I found two more subtle bugs in the alpha-beta pruning. This is a function that is seriously less than 10 lines of code, and was more or less translated from pseudocode in wikipedia. The bugs caused it to improperly prune search paths early, so rather than crashing or showing a blank screen or any of the usual things you get when you make a mistake, it just played a little stupider. I only found the bugs by inspection while optimising the code -- I couldn't tell just from playtesting.

Before finding these bugs I was able to play a close match, but usually win, against the computer with a depth search of 5. Unfortunately the computer took over a minute for each move on my fastest desktop (hence the optimising).

I implemented two standard chess optimisations: iterative-deepening depth first search, and a transposition table. The ID-DFS improves alpha-beta performance (despite appearing on the surface to do more work), and also means I can set a time limit on the search and have it return the best result found so far. The transposition table is a cache, with some tricky code to get it to behave well with the alpha-beta pruning (again, several subtle bugs resulting in less-than-perfect play -- luckily by now I could spot when the computer made a bad move it should have known about).

With both optimisations implemented the depth=5 search takes a maximum of 14 seconds, and typically much faster later on in the game (as the winning path becomes more obvious and the translation table fills up). Because of the bug fixes that came with optimising, the computer beats me consistently even at depth=3 (which is searched in under a second).

I've run a couple of computer vs computer games at various different depths. One apparent design flaw in the game is that the inital player gets a large winning advantage -- a depth=3 player can beat a depth=4 player easily if they move first, and only narrowly loses against depth=5. I might try some slight juggling of the initial position to remedy this; otherwise I could make games happen in two rounds, at either side of the court.

Next stop: pretty graphics.