October Chess Engine Updates

When I wrote a chess engine a year ago, I left it in a slightly incomplete state. The original intention was to try out an old genetic algorithm idea of mine, and creating a chess engine was just a side effect of that. Well, that didn’t work out so well since the vast majority of my engine’s games against itself would end in ties, leaving me with very little data to work with.

I was left with a working chess engine with some rough edges. Mainly, there was an “undo move” option that didn’t work right, the graphics could use a little work, and the only way to set the engine’s strength was by editing a text file and injecting it into the classpath.

Six months later it got some attention on a chess enthusiast forum. I gave some advice on how to tweak the engine a bit and it made me realize how hard that is for many people to do. “Hey, there are some people actually interested in using my unnamed chess engine. Cool! I should probably fix some of those rough edges.” So I did.

First I gave it a name, since no one on that forum seemed to know what to call it. Most of the work was done in October of 2010, so I went with that: October. The October Chess Engine. It’s also now in the public domain, no copyrights attached.

Next, since I’ve learned so much about Java 2D graphics in the last year, I reworked the graphics. The graphics code is shorter and simpler, the GUI looks nicer, and it now permits user resizing of the window. It’s also a little larger by default.

I fixed the engine so that it can search an odd number of plies. All it needed was a a sign change in one place. The hard part was figuring out where exactly it needed to be done. With that fixed, I modified the GUI so that the user can select the difficulty setting.

I’ve also advanced my knowledge of Java threading, cleaning up thread management in the engine. There’s no difference from a user perspective, except that it no longer triggers thread-related JVM bugs — which I’ve seen occur when rapidly instantiating and tearing down many threads.

As a side-effect of tidying threading, I made an experimental branch (distributed) that allows the AI to make use of other computers in the network. The entire board state is serialized, along with a single unevaluated move, and sent off to other machines. They analyze the move and report back with the move’s score.

While investigating a move can be done independently, it misses out on a serious optimization. Scores from previous moves can be used to constrain the current search, allowing the AI to skip over entire branches of the search tree (alpha-beta pruning). When all 30-some possible moves are evaluated in parallel, that optimization is completely lost. As a result, going from one machine to two equal machines tends to have no real speedups, because cumulatively they have to work harder than a single machine. It’s not until several machines are added that the optimization loss is overcome.

Also with the threading change, I added an AI time estimate, so the user knows how long the AI will take. This is important with the new difficulty settings, since high difficulties can take awhile to compute. Sometimes it’s wildly off, particularly when the AI only takes a few seconds, but, to my own surprise, it can be quite accurate when the AI is taking several minutes to complete its turn. Because of the previously-mentioned optimization, the AI speeds up as it progresses, so newer timings are weighted more than older timings.

And finally, one of the most visible changes to the user, I created an NSIS installer for the Windows users (available in the downloads section of October’s website). They can click their way through a familiar install wizard, making the chess engine a neatly-packaged product. I got the idea from DCSS, which has a very well organized build system and makes good use of NSIS.

In the future I’d like to tidy up the experimental distributed AI stuff, possibly rebuild it on top of Java RMI. I’d also like to add support for the Universal Chess Interface (UCI). That would allow me to determine an accurate rating for October, and it would give me an excellent excuse to not do any more GUI work because another GUI could easily be used in its place.

Have a comment on this article? Start a discussion in my public inbox by sending an email to ~skeeto/public-inbox@lists.sr.ht [mailing list etiquette] , or see existing discussions.

This post has archived comments.

null program

Chris Wellons

wellons@nullprogram.com (PGP)
~skeeto/public-inbox@lists.sr.ht (view)