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.