Aart's Blog

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.

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 -------------------------------------------

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.

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 ------------------------------------------------------- 7454503

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

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.

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.

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.

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!

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!

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.

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 ----------------------------------------------------------------- 349388

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!

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 .

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.