XBoard and GNU4J

After I got the Java port of the GNU Chess engine working last month, I mentioned converting XBoard to Java to provide a GUI for the engine. These days I’m investigating using Jin as a GUI. Jin is a Java client app for Internet chess servers. The architecture is pluggable with plug-ins for FICS and ICC. My plan is to make a plug-in for local engines, perhaps pretending to be other players on the network to play against.

Before doing any of that though, I realized I could run XBoard on my Mac within X11 and let it talk to chessbox_gnu4j via the command line like it talks to other engines. Putting the jar file in the same directory as XBoard, the command to launch XBoard and have it use the Java engine is:

./xboard -fcp "java -cp chessbox_gnu4j.jar org.chessbox.gnu4j.Main"

Playing this way uncovered a couple of bugs, which I have fixed. Taking back a move and starting a new game didn’t work. I’ve updated the download at chessbox.org to version 1.02.

Exploring Minimax

I’ve been playing around with the GNU Chess code trying to understand the minimax algorithm and its alpha-beta pruning. The pruning offers a chance for a huge optimization if you can immediately refute candidate moves. Unforunately, refuting a move often requires finding the best response, which means searching the whole subtree, which defeats the purpose of the optimization. So implementers typically guess at the best refutations with checks, captures and moves that scored well in other subtrees (a.k.a. “killer” moves). My tinkering didn’t have any real impact on performance, but I’m getting a better idea about how things work.

Anyway, in the process of exploring the code, I noticed some of the output was being duplicated. I’ve posted a new version to chessbox.org with the minor bug fixes.

Introducing Chessbox

My Java port of GNU Chess is now available at a new domain name www.chessbox.org, which is just a redirect to www.forthgo.com/chessbox/. The tagline for chessbox is “a collection of chess pieces” allowing it to be a home for various open source chess programs that I (or friends!) might port/derive/create as time and interest allows. The Java port of GNU Chess is now called “chessbox_gnu4j”. If you’ve got a better name, I’d like to hear it.

The code is released with the same license as GNU Chess, GPL. I’m not sure if I had a choice in the matter since it is clearly a derivative work of GNU Chess.

Predictable Randomness

One GNU Chess source file I didn’t port to Java was the random number generator, and that turned out to be a problem for processing the binary opening book files.

The board position hash codes are 64-bit numbers created by xor’ing a set of hash codes that come from the random number generator. These hash codes are written to the binary book file, so in order to read a binary book file, you have to get the exact same sequence of “random” numbers from your random number generator. So I ported over the random number algorithm and was then able to read the binary book files which allows the program to play moves from the opening book.

I also got PGN file reading working, so I don’t know of any remaining functional issues (except for the i/o handling, especially control-C, which I may just ignore).

I tried the program on the 300 “Win at Chess” problems. The Java version got 278 correct, and the C version got 284 correct. Both used 5 seconds per move on my Mac G5.

“Jnuchess” Plays and Wins

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…

GNU Chess/Java Starts to Run

I decided to go ahead and convert the remaining printf() calls (too chicken to try switching to Java 5 at this point) and ignore the signal() calls so I could try running GNU Chess/Java. The signal() calls are only used for handling control-C to allow interupting of the think process. Not sure what the Java equivalent would be.

For a while, I would get early crashes when trying to run. Usually these were NullPointerExceptions due to uninitialized array members. IndexOutOfBounds errors were a little trickier to fix, and for one of them I had to actually run the C version to compare values. Turns out the array index was -1 there, too! I’ve already marked a half dozen or so places where the C code looks suspicious, so I think this effort will unearth a few problems in the original source.

There were a couple of errors to get around when trying to build the C version, which I’m guessing are due to different versions of the developer tools on Mac OS X 10.4. There is also a problem running the C version. It seems to process one command and then get a bus error. Coincidentally, the Java version has a similar problem. After processing one command, it gets lost trying to look for more input — there’s some threading issue going on.

The program has some self-test commands that I was able to use to compare speeds. The Java version appears to be about half the speed of the C version. Some results

Test C Java
movegen 34M moves/sec 16M moves/sec
eval 217K evals/sec 110K evals/sec

Not bad.

Other tests, which actually try to find the best moves, are crashing …. If I can get past that, I may need a catchy name for this project. Jnuchess?