Tuesday, October 28, 2008

Chess programming is interesting

It took a while, but I now like everything about the new rewritten BikJump better. The code has become much cleaner, bitboards suit me better than the mailbox representation, move generation is much faster (most apparent for 64-bit, but also for 32-bit), the search heuristics are more intuitive, the evaluation function has more chess knowledge, and the new version scores much better on tactical problem test suites.

So, can I finally release v2.0? Unfortunately not. Despite all these apparent improvements, BikJump v2.0 still scores less than 50% against BikJump v1.8 in blitz games. I am puzzled. More analysis is required....

Saturday, October 25, 2008

A new logo for BikJump

Now that the new BikJump is taking shape, it is also time to upgrade the UCI engine logo to reflect the new version. The old logo of v1.x and the new logo of upcoming v2.0 are shown below (both kindly designed by my sister Elies):



The new logo no longer contains version information, since most chess GUIs show the version information elsewhere anyway. Furthermore, now I can keep this logo for many BikJump generations to come.

As for some background on the logos, the three colored bands hint at my Dutch origins (our flag). The jumping horse obviously relates to the knight in chess as well as the name BikJump (derived from my last name, not yet hinting at a "big jump" for computer chess unfortunately).

Graham Banks also designed the following nice logo for BikJump that is used to post the results of tournaments on the CCRL Forum.

Friday, October 24, 2008

Another anti null move position

Here is another interesting anti null move position, actually derived from a chess problem by Troitski.





With null move pruning, engines are at risk of overlooking the simple mate in four (even Fritz11 under default settings fails to find the mate while search depths go over thirty!). The mate is found quickly, however, without null move pruning or by skipping the heuristic if only a few moves are possible. In this case, simply not trying a null move if few pieces remain on the board also works.

Since I see no simple, yet general way to detect for what positions null move pruning should be disabled to deal with zugzwang, I decided to apply full move generation prior to the heuristic in the second generation BikJump as well. Overall tactical play seems to improve, at the expense of slightly slower searching speeds (luckily, move generation has become a lot faster compared to the first generation).

Monday, October 20, 2008

Some chess ramblings

I am spending some free time rewriting the first generation of my UCI chess engine BikJump into the second generation by replacing the "mailbox" representation with a home-brewed bitboard representation, while carefully revisiting all other parts of the engine as well. The switch to bitboards has improved search speed substantially. In a typical middle game position, the nodes-per-second rating of the search increased from around 500Kns to close to 2000Kns on a Intel Core 2 Quad Q6700 2.66GHz (single-threaded 64-bit binary).

Interesting enough, the strength increase is still disappointing given the major rewrite. Therefore, I am now performing experiments with tournaments and test positions to find more opportunities to enhance its strength.

I like this test position (white to move wins), which I found on TalkChess, one of my favorite forums on chess (thanks to Chess Imager for generating the diagram).





This is an anti "null move" position. The old BikJump, which tries a null move after full move generation only when sufficient moves are possible, found the forced mate very quickly. The new BikJump performs the null move prior to full move generation to enhance searching speed. As a result, however, the mate is no longer found in reasonable time (just like many strong chess engines fail to find it quickly). Common wisdom is that the second approach is better, since the position above is unlikely to occur in real games. It leaves me somewhat weary though. Would a strong human chess player find the mate quickly? And if so, do current chess engines, which beat the strongest players but struggle on positions like this, truly pass the Turing test? Opinions?

Wednesday, October 15, 2008

The first post....

In 1996, a very long time back now, I moved from the Netherlands to the USA. First, for one year at the Indiana University, in Bloomington, Indiana. After that, in California to work for Intel in Santa Clara, where I researched Java JIT compilation and later became the compiler architect for vectorization in the Intel C++/Fortran compilers. A lot has happened since then. I got married to Renu, we bought a house together, and we got a beautiful daughter Karina, who is now four years old. A little more than a year back, I decided to take on new challenges and moved to Google in Mountain View, which is really an amazing place to work. Obviously, working for a web company, I should supplement my static web pages with a little more dynamic content, so I decided to take on blogging. I will probably write about various topics, such as living in the USA, interesting cultural differences, progress on my chess engine, Lego Mindstorms NXT, and what not. Please come again if these topics seem interesting.