Thursday, December 25, 2008

Chess for Android Update

Version 1.2 of Chess for Android at the Android Market has several improvements. The first is the much requested "undo" feature, where up to eight plies (half-moves) can be taken back to correct mistakes in the input (or mere blunders, as for black in the screenshot below!).



The second is a "free play" option, where the phone can be used as a "magnetic chessboard" to study games, or play a game up to a position for further play with the chess engine (this option, like the different levels of play, can be found under the "Menu" button). Furthermore, move highlighting has been modified with a black border, which looks slightly better along files and ranks. Finally, a few rules were added to evaluation function of the chess engine.

Wednesday, December 24, 2008

Reversi for Android Update

Version 1.2 of Reversi for Android at the Android Market now highlights the new and flipped white stones after each computer move with a red border, as shown below. Hopefully this will make it more clear what was played last.

Monday, December 15, 2008

User Feedback at the Android Market

Perhaps a surprise to some, but I don't actually have the G1 Android phone myself yet. Instead, I developed the three game applications on the Android emulator. This unfortunately also implies that I cannot read the comments that were posted at the Android Market, I only can see the average rating. As such, I just get a sense of user feedback from emails I receive.

These emails can be divided into roughly three categories. The first, and luckily largest category consists of nice emails in which people say they enjoy the game(s) and give constructive feedback and suggestions for improvements. I hope to implement some of the requested features, but please keep in mind that this is "spare time" development. The second, smaller category consists of emails where people claim the program is "cheating". So far those claims invariably resulted from a lack of understanding the proper rules (castling or en-passant in chess, forward jumps only for uncrowned pieces in checkers, etc). If you do find a bug, please be so kind to send me complete information, such as position and last move, so I will be able to debug the program. The last and smallest category consists of short emails in which people say they find the game "horrible" (or worse words). Although luckily the minority, each of these obviously hurts. I realize the applications are basic and many features found in commercial programs are missing, but hey, I am giving them away for free. So, cut me some slack. You can always uninstall! :-)

Tuesday, December 9, 2008

Optional Captures

To my great surprise, quite a few users complained that captures should not be mandatory in the just released Checkers for Android, even though the official straight checkers rules clearly state that jumps are forced (something that in my opinion adds to the beauty of the game). Nevertheless, since this seems a popular feature request, I just posted an update at the Android Market in which the user can chose between mandatory or optional captures prior to the game. The latter option does not follow the so-called "huffing" rule, where the piece that should have performed the capture is forfeited. Instead, the game simply continues, which may lead to some interesting draw situations.

Tuesday, December 2, 2008

Checkers for Android

The number of downloads of Chess and Reversi for Android exceeded all my expectations, and I received a lot of nice feedback. The most popular request was for a checkers application. So I gave it a try and implemented Checkers for Android which, like Reversi and Chess for Android, is available for free at the Android Market.

Some screen shots are shown below. Since captures in checkers can consist of several jumps, I tried a new input mechanism where touching a square shows all valid moves that involve that square. By clicking on those squares (making orange colors red) eventually a move is uniquely defined. Also, the last played move is highlighted on the board (a feature requested for Chess and Reversi as well). The checkers engine plays at various levels (including random).

Monday, November 24, 2008

Chess and Reversi for Android

If you have a G1 Android phone, you can try out two games that I developed. They are available for free at the Android Market.

Chess for Android is a simple standalone chess application, consisting of a chess engine (derived from BikJump) together with a GUI (thanks to Joseph Wain for designing the chess graphics). The application accepts moves through the keyboard or touch screen. Once a source square has been determined, all valid destination squares are shown in green. The engine plays at various levels (including random or against itself).


Reversi for Android supports keyboard and touchscreen input, and displays all valid moves through labeled "ghost" stones. This engine also plays at various levels (including random).

Friday, November 21, 2008

UCI option: Processors

My attempts to get consensus on standardizing an option to define the number of processors for an UCI engine on talkchess failed miserably, so I simply picked "Processors". The output of the prototype Deep BikJump on the "uci" command is shown below.

id name BikJump v2.1P (64-bit)
id author Aart J.C. Bik
option name Hash type spin default 32 min 1 max 65536
option name NalimovPath type string default
option name NalimovCache type spin default 8 min 1 max 2048
option name Ponder type check default true
option name Processors type spin default 1 min 1 max 4
uciok

I completed the threading toolkit for Linux and MacOS using pthreads and for Windows using the Windows threads. The latter was slightly more elaborate as I found out that CONDITION_VARIABLE (a synchronization primitive) is only supported on Vista, but not XP. Since I want to keep BikJump as portable as possible, I had to rewrite the Windows version using the slightly less elegant, but more widely supported events instead.

I am now ready for the fun stuff, namely finding a proper way to utilize the additional processors to speedup the search.

Thursday, November 13, 2008

"Deep" BikJump

The 32-bit version of BikJump v2.01 (after a minor bug fix) received a first rating of 2103 RUEL. Since this was tested on a Pentium IV processor (not good for bitscans), I am looking forward to get results back for the 64-bit version running on a Core 2 Duo or Quad platform.

In the meanwhile, I have started work on Deep BikJump, featuring multi-threading to perform the search in parallel (commonly referred to as SMP support). Upcoming versions will be designated with the suffix P (e.g. v2.1P) to denote this new parallel support. Because I want to continue support for all major platform (Windows, Linux, and MacOS), I am working on a small threading toolkit that provides the right abstraction for keeping the major part of the chess engine unaware of details on Windows threads and pthreads.

Tuesday, November 11, 2008

BikJump v2.0 released

Besides switching to a home-brewed bitboard representation, other parts of BikJump underwent refactoring as well. Some modifications turned out to modify strength negatively. I already wrote about null moves below. Furthermore, because the new bitboard move generator generates legal captures much faster than all legal moves, the quiescence search originally had been modified to look at captures only. After including checks again in the first few nodes, some bad tactical errors were avoided. Similarly, late move reduction had become too optimistic, and needed some adjustment towards the scheme used by the older BikJump.

The "perft" nodes-per-second performance (which everybody measures differently; I simply traverse the complete tree with the same move generator that is used in search, including some bookkeeping) is about 13000KNs on a 2.66GHz Core 2 Duo. The nodes-per-second of the actual search in the first Nunn position is now about 1070KNs (64-bit) and 790KNs (32-bit) on a 2.66GHz Core 2 Duo, and about 480KNs (32-bit) on a 3GHz Pentium IV processor (mainly because bitscans are much slower on this platform). In contrast v1.8 scored about, respectively, 570KNs (no difference for 32-bit and 64-bit) and 350KNs (32-bit) on these two platforms. After a few preliminary tournaments, playing strength of the new BikJump seems improved when running on a Core 2 Duo, and appears the same on the older Pentium IV processor.

Although I had really hoped for much more noticeable gains from switching to bitboards and revising the sources, I decided to release BikJump v2.0 to give it a wider exposure. The source code has become much cleaner, while occasionally the new version plays pretty decent chess. I am still hopeful, though a little less optimistic than before, to make more substantial improvements later.

Results of a Nunn test set run-the-gauntlet 4'+1'' tournament, 512MB cache, Nalimov endgame tablebases (complete 3,4,5-piece, some 6-piece), ponder on, on an Intel Core 2 Quad Q6700 2.66GHz, 8MB L2 Cache, 1066MHz FSB, 6GB RAM:


BikJump v2.0 (64-bit)
- Roce 0.0380 16.0 - 3.0 +15/-2/=2 84.21%
- Mediocre v0.332 13.0 - 7.0 +11/-5/=4 65.00%
- BikJump v1.8 (64-bit) 12.5 - 7.5 +10/-5/=5 62.50%
- Philou 2.0.0 12.5 - 7.5 +12/-7/=1 62.50%
- Monarch 1.7 11.5 - 7.5 +10/-6/=3 60.53%
- BikJump v2.0 (32-bit) 11.0 - 9.0 +5/-3/=12 55.00%
- ZCT0.3.2447 JA 6.5 - 13.5 +4/-11/=5 32.50%
- Twisted Logic 20080620 0.5 - 19.5 +0/-19/=1 2.50%
- Fritz 11 0.0 - 20.0 +0/-20/=0 0.00%

Monday, November 10, 2008

A nice result

While I am struggling to translate all "improvements" of BikJump v2.0 into actual stronger play, BikJump v1.8 became third in group A of the 5th Division WBEC Ridderkerk edition 16 and qualified for the final.

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.