The Java port of GNU Chess is now doing well enough to play a game and beat me. To get the main alpha-beta engine to work I had to track down about a half-dozen or so translation errors I had made in going from C to Java. Fortunately, I got the C version to build under Xcode, which gave me a IDE with debugger that I could use to compare my code with the C code as they were both running. Just as fortunately, most of the errors made themselves felt pretty early in the move evaluation process, so it wasn’t too tough to track down what was going wrong by narrowing the window between when things were good and when they were bad.
There are several sets of “find the best move” problems that are used for evaluating chess programs. With 5 seconds per problem for the “BT2630″ set, my Java version of GNU Chess gets 7 out of 30 correct (10 if I increase the hash table size from 1K to 16K entries, and 16 if I give it about 30 seconds per problem), and the C version gets 11 out of 30 correct (12 with the bigger hash table). The C version is still running about twice as fast at processing positions. The hash table management appears to be a place where improvement is possible.
The toughest errors to track down were those that originated in the C source. In one case the Java version would get an IndexOutOfBounds exception evaluating a position, and it turned out the position was invalid as there was a black pawn on its eighth rank (it hadn’t been promoted). It made me feel a little better than the C code had the same problem, except that negative array indices executed silently there. I couldn’t find any problem with the move generation code or the move execution code, but I eventually found that there was a backdoor for stale moves to enter into consideration.
Moves in the hash table that were once good “killer” moves would be considered later even if the board had changed, as long as they were still legal. So at some point a move such as g2-g1 would make it on the list with a rook on g2. Later the move would be considered again when a black pawn was on g2, and the legality-checking code wasn’t watching for such a pawn move (since none would be generated by the move generator without also setting the promotion info). So a fix to IsLegalMove finally got things going.
Everything I test shows new errors, and now I’m seeing problem processing the opening book…
I’m curious about the hash table management problem. Are you using 1.4’s HashMap-s? They rehash the returned hashCode-s. I don’t know whether that’s overkill if your hashCodes are already well distributed.
Another alternative might be to use Trove’s hashMaps: he uses another hashing algorithm (Knuth’s prime-number sized arrays with overlapping lookups) and also maps of ints etc. It’s LGPL code so the execs don’t want to hear about it… but you don’t have that constraint.
Thanks Anli. I’m still just using a transliteration of the C code, which manages the hash table “manually”. When I get to the point to Java-izing the code more, I’ll check out the Trove work.
The hash table maps board positions to evaluation scores, and there are several interesting problems besides the mechanics of the table. For example, how to most efficiently represent a chess position, and whether some positions are more cache-worthy than others.
But first I need to get the straight port done…