Thing Every Once in a While

So it turns out that wordpress has no sort of a “smart spam filter”.  Between April 4th and now, I got over 1,400 comments to this blag.  Now, that’s not all that bad, because I have to manually approve the comments.  However, it is eating up bandwidth on my home internet connection, and if a real person posts a comment, there’s no way I will be able to find it to approve it.

For all you faithful readers, I have to apologize.  If I didn’t have work, I’d post here more often, but lately, work has been draining my motivation to work on personal projects.  Poor excuse, I know, but I needed a reason to categorize this post under “excuses”.

As most of you know, I created a weak chess engine as an independent study, for my last semester of school.  After I completed it, wrote a paper about it, and gave a presentation, I didn’t look back.  It’s not that I didn’t enjoy it as a project, it’s just that I stressed myself a lot over the project, and it was nice to be away from it for a long while.

Well, now I am revisiting the project, trying to correct a lot of the mistakes I made for my “release” version of my independent study.  Here are some of the mistakes I made, and how I plan to resolve them with my new chess engine:

• Objective-C.  Now, Objective-C isn’t a bad language, especially for GUIs and event-driven applications, but for something logical, rigid, and procedural (like a chess engine), the object-orientedness and message handling just turns into overhead and causes overly-complex code.  My resolution for this: implement everything in  pure c.
• Profiling.  I inlined a bunch of macros and preprocessor definitions which I could turn off and on at compile time, which would keep track of how many times each function was called, and how many times an operation was performed in each function.  This is fine, until you realize how ugly and unreadable it made the code.  My resolution: to use GDB or some other product designed to analyze running code.
• Premature optimization.  This was a twofold problem.  First, it caused me to write functions and procedures in an unreadable, inflexible way.  Second, it took up a lot of time that needed to be spent elsewhere.  An example of this would be where I created a heap object for the sole purpose of pushing moves into it, and pulling them out in a sorted, best-first order.  Note that the average number of moves from a specific position is somewhere around 30.  I could have gotten away with a fixed array which I sorted with insertion sort.  This would have caused no noticeable slowdown in the program, and would have saved me a good week of work.  The solution to premature optimization is this: don’t ever do it.
• Interface.  When I was finished with the project, I created my own Java-based GUI, which allowed straightforward input of moves.  However, that meant I couldn’t play it against other chess engines.  This wasn’t a mistake, so much as a choice when I was running out of time to give it a usable interface.  This time I think it’s necessary to do it right.  I want to create a library which can talk with both the Xboard Chess Engine Communication Protocol and with the Universal Chess Interface.  That way, it will be easy to casually play against my engine, and it should be straightforward for my engine to talk to other engines.  Also, my library could reasonably be a springboard for chess projects anyone else might work on.

There are also a few things I didn’t implement which would substantially increase the strength/speed of my program.

• Iterative deepening
• Quiescence search
• Positional-based/strategy-based static evaluation function (as opposed to pure material)

Iterative deepening is just an algorithm and would be straightforward to implement, but those last two are crucial to making a chess engine strong.  However, I am too much a novice at chess to know what I should tell the engine.  ”This is a volatile board position” and “White has the positional advantage” both seem like very subjective statements to me, and I can’t think of a practical way to make those objective.  My long-term plan is to get good at chess.  Maybe practical experience will help me to understand what it means to have “positional advantage”, in a way that a computer will understand.  I am probably joining a chess club…

My current focus is the interface.  I think that it’s one of the most useful parts of this project, in that other projects should be able to use it.  Also, it will be crucial for troubleshooting and testing my engine, once I have the engine working.  Let’s hope I make good progress on the interface.  I’ll keep you posted.

Josh