Monthly Archives: January 2012

Shall we play a game?

How about Global Thermonuclear war?

Wouldn’t you prefer a nice game of chess?

(Wargames, 1983)

I’m very pleased to announce that a project I’ve been working on off and on for the last year is finally coming to life. I’m working on a new chess engine — a complete rewrite of “Prophet.” Prophet is a ‘C++ as a better C’ style engine that I started back in 2000 or so. I haven’t touched it in the last few years, partly because I got tired of it but partly because it became difficult to work on.

There is absolutely nothing new in this code in terms of features — not yet anyway. In fact, it has just enough logic to play a legal game of chess. Strengthwise, there is a LOT to do to get back to the level of the previous version of Prophet. That said, I am excited about this program for a number of reasons.

First, I am really very pleased with how I’ve gone about writing this engine. If there is one thing I have learned very well over the last couple of years, it’s the importance of doing test driven development (TDD). When I started the last version (12 years ago!), my approach was to write a bunch of code, then test it out, squashing whatever bugs surfaced. And there were always bugs. With this program, I wrote tests as I went – even before the implementation. As a result, I have a very high level of confidence in the code, because bugs were eliminated at a very early stage. In fact, by the time I got around to doing some higher level testing, everything just worked! Another side effect of this approach is that it forced me to modularize code a bit better and to keep “side effects” to a minimum.

One thing that is slightly awkward then doing TDD in a C program is that I haven’t found a way to run tests as part of the build (make) process. I’m pretty sure I could leverage Maven to accomplish this, but I haven’t really tried yet. The tests are literally just compiled into the binary with an “assert” statement to trigger them when running with DEBUG on.

This is a code snippet from main() to demonstrate:

   print_greeting();
   assert_assumptions();
   init();
   assert(run_tests());

So, perhaps not the most elegant approach, but it definitely gets the job done for now.

Another reason I am excited about this project is that, frankly, I am just better than I used to be at decomposing code into small, maintainable (easily testable) functions. I’ve come to the conclusion over the years that large functions are evil. Functions with side effects are also evil. As an example of the improvement in this area I’ll point out the function that is responsible for interpreting user input and taking the appropriate action.

In the previous version of Prophet, I had a “ParseCommand” function that was 92 lines long, and another “ParseXBoardCommand” function that was a whopping 257 lines long! Both followed this basic formula:

if (!strcmp(cmd,"some command")) {
   some action
   return 1;
}
 
if (!strcmp(cmd,"another command")) {
   another action
   return 1;
}
 
...

Which is perfectly correct, but not as nice as my new approach. My entire parsing function is now:

void parse_command(const char *cmd) {
 
   print("# RECEIVED: %s\n",cmd);
 
   int len=sizeof(function_table)/sizeof(function_table_entry);
 
   for (int i=0;i<len;i++) {
      function_table_entry fte = function_table[i];
      if (strcmp(cmd,fte.name)==0) {
         fte.func();
         return;
      }
   }
 
   print("Error (unknown command): %s\n",cmd);
}

Yep, 16 lines of code including whitespace and a debug statement! The trick is the use of a function table, which looks like this:

struct function_table_entry {
   const char *name;
   void (*func)();
};
struct function_table_entry function_table[] = {
   {"accepted", no_op_with_arg},
   {"analyze", no_op},
   {"bk", no_op},
   {"computer", no_op},
   {"drawboard", handle_drawboard}, // not xboard!
   {"db", handle_drawboard}, // not xboard!
   ...
   {"time", handle_time},
   {"undo", handle_undo},
   {"usermove", handle_usermove},
   {"variant", no_op_with_arg},
   {"xboard", no_op},
   {"?", handle_move_now}
};

Which, IMHO, is much more legible.

That is one example, and there are similar improvements in other areas.

In the next weeks I will finish off the XBoard integration so it’s possible to play a complete game of chess using a nice graphical interface. Once that and some other basic features are complete I’ll turn my attention to making Prophet a competitive engine. Look for more posts on some of these efforts in the next weeks and months.