Posts

Showing posts from 2010

Engine-Engine Matches on Android

I am extending Chess for Android with a feature to run automatic engine-engine matches between UCI engines that have been "natively" compiled for Android. After importing two UCI engines, or using the built-in Java engine for one, a fixed number of games is played using random openings from the built-in book while allocating a fixed time per move. All games are saved in a "match.pgn" file, which can be used by another chess program, such as Arena or Chessbase. A Chessbase-generated cross-table for a 1-second-per-move tournament between some UCI engines compiled for Android is shown below.

I hope to release this feature sometimes early in January.

                 1          2          3          4          5
1 Stockfish 1.9  ********** 11½0100101 111111½111 1111111111 1111111111 35.0/40
2 Crab 1.0 beta  00½1011010 ********** 111½1½1111 1111111111 1111111111 33.5/40
3 GNU Chess 5.07 000000½000 000½0½0000 ********** ½½11111110 1111111111 19.5/40
4 BikJump v2.1P  00000000…

Racing during the Holidays

Image
The vacation just started, and Karina and her friend Ella are enjoying 50 lap races on our Carrera racetrack. Nice to see the difference between a year ago, when the girls crashed the cars most of the time, and now, when they actually understand braking before and accelerating in a curve. Still, lots of repairs to be done on the cars when this race is over.


I like the Carrera Digital 132 race track. Cars have regular and braking lights, can switch lanes on designated lane change sections, and the speed, braking power, and fuel tank capacity can be set individually for each car. When cars run out of gas, lights are blinking as they slow down, and a visit to the pit stop is required first. Moreover, up to six cars can race together, or autonomous cars can be programmed to make racing harder while an electronic lap counter keeps track of interesting statistics.

Merry Christmas and a Happy New Year

Image
A merry Christmas and a happy 2011 for all my blog readers. In the picture, you see the snow covered city hall of my home town Gouda in the Netherlands. In "sunny" California we just get rain :-)

BikMove v1.2

Continuing the detour in checkers. I also released v1.2 of BikMove, a checkers engine plugin to Martin Fierz' CheckerBoard application. New features include:
Added internal iterative deepening to searchConfigurable transposition table and endgame database cacheImproved evaluation functionAvoid querying Fierz's database when *either* side can captureBelow are results of a 3-move openings match between BikMove v1.2 and other engines (1 second-per-move, 256MB hash, 256MB database cache, 2-8 piece endgames, best-move for engines that have their own book).

BikMove v1.2 vs. Easy Checkers 1.0   : W-L-D: 284-  0-  4  99%
BikMove v1.2 vs. Simple Checkers 1.14: W-L-D: 136- 21-131  70%
BikMove v1.2 vs. GUI checkers 1.05+  : W-L-D:   9-108-171  33%
BikMove v1.2 vs. Cake1.8 + huge book : W-L-D:   0-152-136  24%
BikMove v1.2 vs. Kingsrow 1.16d      : W-L-D:   1-181-106  19%

For comparison, also some results under similar conditions with v1.1.

BikMove v1.1 vs. Simple Checkers 1.14: W-L-D: 75- 64-14…

Improved Checkers Endgame

Image
To improve endgame play, I have added a few "distance-to-win" endgame databases to Checkers for Android (K-K, p-K, p-p, KK-K). These databases are small enough to reside in memory and are queried during the engine search. In the screenshot below, for instance, the engine (playing black) announces that it will win in 20 moves. If you are up to the challenge, just download version 2.4 of Checkers for Android from the market.


More Lego Mindstorms NXT

A movie of a robot having some fun fetching and throwing a ball.

Lego Mindstorms NXT

Image
Through Google, I signed up as volunteer for a Lego engineering mentoring/outreach program in a local school. This was a very good excuse for Karina and me to get reacquainted with our Lego Mindstorms NXT kit (also see our earlier Mindstorms adventures). As you can see, we had lots of fun together.

Android Game Manuals

It is long overdue, but I finally wrote brief manuals for Chess, Checkers, and Reversi for Android that explain the full menu structure of the games. I plan to add more explanation here over time. Please let me know if you have suggestions.

King Attacked Warning

Image
It is minor, but the latest release 2.4.3 of Chess for Android now shows a red circle around the king as an in-check (or mate) warning when the move coach is enabled. A sample screenshot is shown below. This version also improves UCI engine unloading on exit.

U.S. Citizenship

Image
The adventure that started in Indiana in 1996 and continued in California in 1998 reached a very special point today. I received my U.S. Citizenship. Thanks, America, for being my home for so many years and welcoming me into the American family.

Chess for Android 2.4.1

Image
I just released version 2.4.1 of Chess for Android with the following changes:
Ability to install application on SD card Moved navigation buttons downFew improvements to UCI engine supportTo verify that UCI engine support works for third party engines as well (not just for BikJump), I downloaded sources of ZCT0.3.2500 (by Zach Wegner) and Crab1.0Beta (by Tord Romstad, Marco Costalba, Joona Kiiski, Adam Kleng) and compiled these "natively" for Android. Importing and playing the engines work fine.

As before, instructions on setting up an UCI engine are given at UCI for Android.


Animation of Engine Moves

Because it is hard to print all information from the UCI engine on the phone screen, I am toying with a feature where the current move considered by the UCI engine is shown graphically. Below is a short demo of this feature. Let me know what you think!

Chess for Android 2.4

I just released version 2.4 of Chess for Android at the Android Market with the following new feature:
basic UCI engine support (ability to replace built-in Java engine with any third party UCI engine compiled "natively" for Android)Instructions on how to setup an UCI engine are given at UCI for Android. As far as I know currently only BikJump is available as stand-alone UCI engine for Android. Although stronger than the built-in engine, I hope I will be able to add links to much stronger third party UCI engines soon. Please note that support is still rather basic (elaborate setup, only tested on one engine, GUI does not support engine options, time control restricted to time-per-move, position sent as FEN, making the engine more prone to three-fold repetition, no tournaments, etc.). Nevertheless, I hope it is an interesting start.

UCI Engine on Android

Image
Here is an UCI engine running on a Nexus One in Chess for Android, probing the complete 3- and 4-piece Nalimov endgame tablebases (29.6 MB) from SD card.


Here is a screenshot where the UCI engine already reports a mate (using the tablebases), while the internal Java engine only reports a negative score for white given a search tree of depth 9.


Steps to make this work are shown at UCI for Android.

More UCI Support for Android

Image
The UCI engine output is now presented in a slightly better format, where information is broken up into individual fields. Also, I have compiled BikJump v2.1 natively for Android, which is more elaborate multi-threaded bitboard-based engine that also supports the Nalimov endgame tablebases (with kind permission from Eugene Nalimov and Andrew Kadatch). I copied a few tablebases into the emulator's SD card and started the engine analysis. As can be seen in the screenshot below, the engine together with the probing code run fine on the Android emulator.

UCI Support for Android

Image
The UCI (Universal Chess Interface) protocol defines an open interface between a chess engine and a graphical chess program, which allows chess programmers to focus on their engine rather than GUI details. Many programs on Windows, Linux, and MacOS support the UCI protocol (e.g. ChessBase, Arena, Sigma Chess, Lucas Chess), but as far as I know, no UCI support exists for Android. Even Chess for Android uses a simplified Java port of my own UCI engine BikJump rather than going through the UCI interface.

Therefore, I am prototyping UCI support in Chess for Android with the idea that, in the long run, this will allow importing third party engines into the GUI. So far, I added a "kibitzer feature". Any UCI engine binary that has been "natively" compiled for Android (using a compiler that ships with the Android NDK) can be imported through a file finder dialog, as shown below for a natively compiled version of BikJumpv1.8 running on the Android emulator.

Once imported, th…

Chess for Android 2.3

Image
Version 2.3 of Chess for Android has following changes:
replay buttons for full game navigationimproved draw detectionadded two levels (longer thinking time)more efficient game storage in memoryThere are now five on-screen buttons. The first one is:
← : undo button, accepted any time to correct mistakes (even when engine is thinking), discarding all subsequent moves when used during navigationThe replay buttons are useful to navigate through a game without discarding any moves. These buttons are only accepted when the engine is not thinking, and work as follows:
<< : goes to beginning of current game <  : steps back one move >  : steps forward one move >> : goes to end of current game During navigation, all subsequent moves not played yet are greyed out (see screenshot). Playing any move while navigating (including switching sides) discards all following moves (even if the moves matches the subsequent play; use replay buttons to maintain the current game). As be…

Fidelity Electronics Chess Challenger

Image
As long as I am making a trip down to memory lane, I remember how happy I was when I got a Chess Challenger for my birthday in 1981. As a starting young chess player, I certainly learned a lot from playing this computer, and I was thrilled when I had beaten the highest level for the first time. It certainly has sparked my interest in chess programming.

After playing for a while, I discovered that if Chess Challenger responsed to e2-e4 with e7-e7 from its random opening book, it could always be beaten at Level 1 through the game shown below. As depicted on the corresponding photo, the Chess Challenger would admit its defeat by flashing all 64 red indicators.
[Date "sometimes in 1981"] [White "a much younger Aart Bik"] [Black "Chess Challenger (Level 1)"] [Result "1-0"] 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Bxc6 dxc6 5. Nxe5 Qd4 6. Qh5 Qxe4+ 7. Kd1 Qxg2 8. Qxf7+ Kd8 9. Qxf8# 1-0
Although modern chess software is much more practical, it lacks some of t…

Casio FX-700P

Image
This week I realized that it has been more than 25 years since I learned programming on the Casio FX-700P programmable calculator. This little computer is powered by a 455KHz HD61913 processor and features 2KB RAM, with exactly 1568 bytes available for BASIC programs. Output can be printed with the Casio FP-12 mini thermal printer and programs and data can be saved and loaded using the Casio FA-3 cassette interface.


I still use the FX-700P as my desktop calculator, but this week I also tried the printer and cassette interface. The internal battery of the FP-12 was exhausted, so I had to improvise an external battery holder. But after that, the printer still produces those little thermal listings! The FA-3 also still works after all those years, although I could not read my old programs back unfortunately. Time had taken its toll on those old cassettes.

One Deeper Perft for Checkers

I optimized the distributed implementation for 8x8 checkers with a transposition table (but one that stores full board positions to avoid the risk of "hard collisions"). The speed improvement enabled me to compute perft(23) on a cluster of machines in a relatively short time.

As before, the table below shows the perft breakdown per move (called "divide") from the start position, but now for depths 21 to 23.

move divide(21) divide(22) divide(23) --------------------------------------------------------- 12-16: 52945190026737 243598269855110 1123463594881857 11-16: 53527954221225 246743868125768 1131373985922218 11-15: 44775005468548 209016678583301 984253557821317 10-15: 46574865098865 215412869777867 1000606302770349 10-14: 39822944739732 184865466345796 856779998157523 09-14: 45530585259776 213736468971938 1003310451936358 09-13: 61923979665936 288999100078322 1337748969176591 -----------------------------------------------…

A Very Short Defeat

Image
I got a kind email from Thorsten Czub, who is very active in testing chess programs in general and, currently, chess programs for Android in particular. He conducted a few tests with Chess for Android running on a Rockchip Android Tablet (600MHz ARM) with Android 1.5 against some programs running on other platforms. Below is a game between Shredder Java running on a Motorola ROKR Z6 (550 MHz ARM) with white and Chess for Android on the tablet with black.

[Event "average 30"] [Date "2010.07.08"] [White "Shredder Java"] [Black "Chess for Android"] [Result "1-0"] 1. e4 e5 2. Nc3 Nf6 3. g3 Be7 4. Nf3 Nc6 5. d4 exd4 6. Nxd4 Nxd4 7. Qxd4 O-O 8. e5 c5 9. Qc4 Ne8 10. Bd3 a5 11. O-O Nc7 12. Be3 Ne6 13. Nd5 f5 14. exf6 gxf6 15. Qg4+ Ng5 16. Rfe1 d6 17. Bxh7+ Kxh7 18. Qh5+ Kg7 19. Bxg5 Rf7 20. Bh6+ Kg8 21. Qg6+ 1-0 White will mate soon. Embarrassing how quickly king safety was lost.

Perft for Checkers (yet again)

Rein Halbersma recently posted 8x8 checkers perft results for depth 22 with a request for confirmation (because he uses a hash table, he wanted to make sure no "hard collisions" occur). So I verified his results for depth 22 using a distributed, brute force implementation (no hash tables).

The table below shows the perft breakdown per move (called "divide") from the start position for depths 20 to 22.

move divide(20) divide(21) divide(22) ------------------------------------------------------- 12-16: 11531470109861 52945190026737 243598269855110 11-16: 11736729175821 53527954221225 246743868125768 11-15: 9515983205474 44775005468548 209016678583301 10-15: 10055597639275 46574865098865 215412869777867 10-14: 8600202424158 39822944739732 184865466345796 9-14: 9698986164172 45530585259776 213736468971938 9-13: 13406062152792 61923979665936 288999100078322 ------------------------------------------------------- 74545030871…

Android Demo

If your browser supports the video tag, below you will see a short movie of my first Android animation demo. Otherwise you will just see a boring text message. Let me know if this works for you; it seems an interesting new way of presenting features in my Android applications.



your browser does not have  video support

Animation on Android

Image
I wrote my first animation on Android! It is actually part of a simple screen tester, where I can inspect the screen size of a device and see different font sizes, colors, and text positions. For fun, I added three moving balls (the circles in the screenshot below), all bouncing between the four screen borders.

Checkers Move Coach

Image
I received an email from Rein Halbersma who suggested an improvement for Checkers for Android by accepting a move as soon as any ambiguity has been resolved. In many cases this enables single click input. I have implemented this request, together with extending the "move coach" to show all valid moves, as illustrated below.


Hopefully this new option is useful for people that are learning checkers. Both improvements are available in v2.3 of Checkers for Android.

Board Gradient

Image
Although I like the wooden board textures that I use for chess and checkers, I was never quite happy with the board texture I used for Reversi for Android (some called it a dirty pool table :-). Therefore, I am trying something new in version 2.3. Instead of using a texture, I use a radial gradient on the board, which gives the impression that the board has been placed under a lamp.


This new approach also slightly reduces the size of the binary. Let me know what you think.

Android 2.2

I am excited that Android 2.2 (aka Froyo) has been announced at Google I/O. Especially the Dalvik JIT compiler directly benefits all my game engines with deeper search. And yes, the 5x improvement reported for checkers in the Android 2.2 highlights page refers to Checkers for Android!

Replay Buttons

Image
I am working on extending Chess for Android with full replay buttons. This will remove the somewhat arbitrary restriction of only an 8 half-move undo. Furthemore, it allows replaying older saved games and experimenting with different continuations.



Here is already a quick preview of the new landscape and portrait layout I am planning to use. Early feedback welcome!

Loading and Saving Games

Image
I added a much requested feature to Chess for Android: the ability to load and save games (other than just the one in progress). To use this feature, long-press anywhere in the notation window to get to a menu for exporting the game to clipboard as PGN or FEN or, the new feature, for loading and saving games as file.

As illustrated below, after pressing "Save Game to File", a pop-up window asks the user to pick a file. Initially files are empty, but after saving they get marked with the date and time of the last stored game. Simply pick a marked file to overwrite or pick an empty file, as done below for file 3. Loading a game is done in a similar manner.

Perft for Checkers (again)

Today I was prototyping a distributed worker pool at work which needed some test input, and this gave me a good excuse to compute perft for checkers for depth 21 (one deeper than results I posted a while back). The perft breakdown per move (called "divide") from the start position for depths 18 up to 21 is shown below.

move divide(18) divide(19) divide(20) divide(21)
-----------------------------------------------------------------
12-16: 550829166472 2517202147314 11531470109861 52945190026737
11-16: 566149929068 2564849953998 11736729175821 53527954221225
11-15: 435063007630 2041959240377 9515983205474 44775005468548
10-15: 472279451484 2180656975018 10055597639275 46574865098865
10-14: 402570639569 1859042884028 8600202424158 39822944739732
9-14: 441590753001 2068865301476 9698986164172 45530585259776
9-13: 625398758917 2881467090588 13406062152792 61923979665936
-----------------------------------------------------------------
3493881706141 161…

Maze Solving in 6510

Image
Not sure why, but I suddenly felt the strong urge to see if I could still program in 6510. So I implemented a backtracking solver that finds the path in a maze from the '-' symbol to the '+' symbol (actually an undergraduate programming exercise I did long time ago on a Motorola 68000). The result running on a Commodore 64 emulator is shown below. The active search path appears as white '*' symbols, dead end positions appear as '.' symbols.


And below the solution has been found. You can find the assembler source file maze.s (and a 6510 cross-assembler) on my Commodore 64 page if you are interested. You can define a different maze in the .byte section (just make sure the active search path length cannot exhaust the small stack of the Commodore 64). Also don't forget to remove the artificial delay to appreciate how fast machine code runs!

Commodore 64

Image
Remember this screen?


Yes, that's right. I too became interested in computer science because of the Commodore 64. Although I still have my Commodore 64 somewhere, nowadays it is much easier to relive the good old times with an emulator, such as CCS64 (Per HÃ¥kan Sundell), VICE (the VICE team), or MP64 (an emulator under development by Michael Plet).

A while back I wrote a 6510 cross-assembler win2c64 that converts an assembler source file into a target file that can run on one of these emulators or, with some work, on the real Commodore 64 (an assembler converts human readable mnemonics, labels, and simple expressions into machine code; win2c64 is a cross-assembler because it runs on a Windows platform but generates machine code for the Commodore 64). If you are interested, you can find the cross-assembler and some sample programs at Aart's C64 page.

More Board Textures

Image
Now that I am enthusiastic about textures, I also added a board texture to the other games. For Reversi for Android this hopefully also addresses complaints that the board was "too green".


For Checkers for Android, I simply reused the coffee table texture, as shown below.

Wood Texture

Image
A user "dragonfish" suggested to add texture to the wooden chess board in Chess for Android. So I took a picture of my coffee table and used that as texture for the dark squares. See the result below.



Together with a minor engine improvement, this new feature has been released in v2.2.

Topeka

Image
I am now working for Topeka.

Copy to Clipboard (PGN/FEN)

Image
Version 1.2.9 of Chess for Android will enable users to export a game to another application, such as an editor, email, or another chess program:

copy all moves to the clipboard as PGN (Portable Game Notation)
copy the position to the clipboard as FEN (Forsyth–Edwards Notation)

To use these options, long-press anywhere in the move list area. Then, the following menu appears.


Select one, then exit the chess application and go to the application where you want to paste the game. For example, I picked Copy Moves as PGN and went to messaging and long-pressed the text area.


Then Paste the contents of the clipboard into the message, and the game appears in PGN format (note that, for convenience, I use a slightly more elaborate algebraic chess notation than strictly required; readers should still accept that format though).


Likewise, using Copy Position as FEN, the contents would look as follows.

Opening Book

Image
I added an opening book to Chess for Android. The opening book is small (slightly over 150 opening lines) and simple (transpositions are not recognized, unless the line is explicitly stored). Nevertheless, since the engine picks a matching line at random during the opening, the variety of play will increase. Version v1.2.8 (and onwards) supports the opening book, as well as a new copy-to-clipboard feature (more about that later).

While still in an opening line, the message "opening" appears at the position that usually shows the engine evaluation, as shown below.

One Star Ratings

I don't mind constructive criticism. Really, I don't. But take two recent one-star reviews for Chess for Android:

Stupid cant start a new game after youve lost
greg Fri, Mar 12 01:31:00 UTC 2010

This game cheats. Pawns shouldnt be able to capture pieces next to them and then move diagonally.
Eyal Wed, Mar 10 02:35:00 UTC 2010

Really, my game gets one star because you cannot find the menu button on your own phone, or because you don't know the en-passant rule (see also previous posting)? Please, if you don't like the game for a good reason, by all means give one star. But this?

Too Many Updates?!

While browsing through some recent comments posted on the Android market, I was surprised to read that some users complain that I am pushing too many updates. I usually work on these games in spurts, i.e. a lot of improvements in a short time followed by a period of relative quiet. Another problem is that the Android market does not enable me to push updates to specific platforms or builds only. So, for example, when I fix a bug for Android 1.1, some users will not see a change, but others may be happy to receive an update. Last, the Android market does not support a good way to show revision history.

Luckily not all users feel that way, as reflected in the comment:

Updates are a pain? Really? its wonderful when developers continually work on their FREE app to improve it. Be thankful not frustrated.
Vin Fri, Feb 12 11:47:00 PST 2010

Thanks Vin!

Android 1.1 Bug Fix

I always test new releases on emulators for Android 1.5 and higher (api 3 and up), for various screen sizes and other settings, as well as on the two actual Android devices that I have. However, I found out there was a bug on Android 1.1 (api 2), which I fixed in the latest releases of Chess, Checkers, and Reversi for Android. Users with an "older" phone that have never updated to more recent builds may have experienced problems (apologies for that!). The games should work again for all platforms. Needless to say, I added the Android 1.1 emulator to my mandatory release criteria.

Explanation of Levels

Image
Since I just got some questions on the different levels in my Android games, I hope the following posting on this topic is helpful.

To change the level in either Chess, Checkers, or Reversi for Android, first press the Menu button on your phone, then pick the Level option, which gives you something that looks like the following screenshot.



Then select any of these levels. Here, Free Play means that the game engine will never compute a reply. Instead, the phone can be used as a "magnetic board" to study games or play a game up to a position for further play with the engine. In Random, the engine will instantaneously pick a valid next move at random. Pick this level if you like to win! The next Level 1 through Level 5 select different normal playing levels, increasing in both strength as well as time taken by the engine to compute its next move.

Finally, Chess for Android also has an Auto Play option where the engine plays against itself. After selecting this level, either make a…

Chess for Android Update

Image
I just released a new version of Chess for Android that, like the previous updates of the other games, improves the text size on larger screens. On the Nexus One, for example, the notation window in previous versions was barely readable. This is now hopefully resolved for all current phones.

Next planned updates consist of adding a small opening book and an option to export a game to some external format.

More Updates

Image
I just released new versions of Checkers and Reversi for Android that improve the text size on larger screens. The reversi application now also uses a randomized opening for variety of play (see below).

Checkers for Android Update

Image
I just released v1.2.2 of Checkers for Android with the following improvements:

+ improved endgame play
+ randomized opening for variety
+ announces win/loss

The latter feature is illustrated in the screenshot below. Please let me know if you encounter any issues with the new features.

Miscellaneous Updates

Just a few unrelated updates.

First, the Android App Review Source website posted a brief online interview with me on developing Android applications.

Also, version 2.01 of BikJump ended at second place in the CCC 17th Amateur Series (Division 8), which opens the possibility of promotion to a higher division. Many thanks to Graham Banks for running this tournament!

Finally, Martin Fierz published Checkers Tutor for Android, a strong checkers program for Android.

Happy New Year!

Image
I just came back from a great trip to my home town Gouda in the Netherlands and want to wish all my blog readers a happy 2010.