Monday, February 28, 2005

Suicidal Cake

My suicide checkers program, Suicidal Cake, has reached version number 1.08. It has a 6-piece endgame database, I suppose I am the first to compute this database. It also has an opening book of about 36'000 moves right now, with approximately 2000 more added each day. Suicide checkers is extremely tactical, many lines in the book have more star moves than non-star moves. This makes the game very hard for humans. It's hard for the programs too of course, as one mistake might cost you the game! Suicidal Cake has the huge advantage of an endgame database, which is more important in suicide checkers than in regular checkers; I'll return to this later. Suicidal Cake has played some games against two of the world's best suicide players, and has won every single game. I believe it is the strongest suicide checkers playing "entity" on the planet right now. Here's a game where the endgame database played a part, you can copy and paste the game into CheckerBoard.

[Event "Email game"]
[Date "2005-02-20"]
[Black "N.N."]
[White "Suicidal Cake 1.08"]
[Result "0-1"]
1. 11-15 24-19 2. 15x24 27x20 3. 8-11 21-17 4. 11-15 17-13 5. 12-16 20x11 6. 7x16 22-18 7. 15x22 26x17 8. 16-20 25-22 9. 4-8 28-24 10. 20x27 31x24 11. 8-11 29-25 12. 3-8 23-18 13. 10-14 17x10 14. 6x15 13x6 15. 1x10 30-26 16. 15-19 24x6 17. 2x9 18-14 {Suicidal Cake returns the man it has won to reach a winning 2 vs 2 endgame database position} 18. 9x18 22x15 19. 11x18 26-23 20. 18x27 32x23 {And here it is, this position is a win for white. Would you have guessed?} 21. 5-9 23-18 22. 9-13 18-15 23. 8-12 25-21 24. 12-16 15-11 {Red resigned. Play might have continued:}
25. 16-19 11-8 26. 19-23 8-4 27. 23-27 4-8 28. 27-32 8-11 29. 32-27 11-15 30. 27-32 21-17 31. 13x22 15-19 32. 22-25 19-23 33. 32-28 23-18 34. 28-24 18-22 35. 24-19 22x29 36. 19-24 29-25 37. 24-19 25-22 38. 19-16 22-18 39. 16-20 18-23 40. 20-24 23-27 41. 24x31 0-1

Thursday, February 24, 2005

Intermediate goals

When programming a strategy game, you basically combine two elements: A deep search and an evaluation function. The search will look at lots of positions (millions) that might arise from the current board position, while the evaluation has to tell the program whether this line is any good or not. Most of the time, the evaluation is not that difficult, at least not in checkers. The reason is simple, checkers is a very materialistic game. Most of the time, being a man ahead will win the game. In other games this is different, e.g. in chess the goal is to mate the enemy king, and you can sacrifice a lot of material for a violent attack on the king. In checkers, the situations where you can sacrifice a man are rather rare, allowing even pretty dumb programs to play well. Dumb in this context means that they have a rather weak evaluation function, but paired with a deep search it will do the job most of the time. Such intermediate goals, like winning a man or getting the first king which you can code into your evaluation, are necessary for the program to know what to do; only knowing the ultimate goal of the game alone will not get you anywhere unless the game is so simple that you can calculate right to the end.
Two weeks ago, I wrote a program that plays suicide checkers. In suicide checkers, the ultimate goal is to lose, i.e. not to be able to make a move any more (either by losing all men or by getting smothered). Now, if the final goal there is to lose all your men, instead of winning all your opponent's men, what would a good intermediate goal in suicide checkers be? To win material like in normal checkers, or the other way round? And are there any positional goals that one might want to achieve? Can you guess some answers to these questions?

Sunday, February 20, 2005

Exaggerations, part 2

Today's pick in the exaggeration category is Wincheck 3D by Jean-Bernard Alemanni. Wincheck is shareware and costs something like 50$ to register. There are two different versions you can register, but you can also play against the free version. Wincheck has neither an opening book nor an endgame database. It plays a decent game, but is chanceless against a strong program like Cake Manchester (I played two games between the two, and Manchester easily won both). The author uses a trick to make his program look better than it is: He groups all programs he found according to playing strength, leaving the "Top" category for Chinook, and including all decent programs in the "Strong" category. That means that Wincheck, Sage, Cake, Colossus, Damas 99, KingsRow, Nemesis, Nexus, Plus700, Wyllie and WCC all end up in the same category.
Wincheck is a nice program, I particularly like the graphics. But it is far from being in the same league as Nemesis, KingsRow or Cake (no wonder, without endgame database and opening book!). Jean-Bernard wins the runner-up prize in the category "Serious program marketed with unserious means".

Saturday, February 19, 2005

Cake Manchester's opening book

The book I just created for Cake++ for Linux is much better than the book that you can download for Cake Manchester. Manchester's book is still the same I once created in 6 weeks with a beta of Cake Sans Souci after the computer checkers world championship in Las Vegas in 2002. That book is based on the first 90'000 positions my book generator explored. Now, among these 90'000 moves roughly half will never occur when you set the book to play best moves only. Of the remaining say 50'000 moves, about one quarter are just forced captures. So effectively, that book has a mere 40'000 useful book moves, and they are based on an opening database with "only" 90'000 positions, which means there are also quite a number of errors in that book.
The book for Cake++ only contains lines that Cake will actively select, i.e. there are no wasted moves for lines it will never play. I also left out the forced captures in that book. Finally, all moves are based on the 1'600'000 position opening database, which means that there are only very few errors left (if there are any at all).
Cake Manchester will also get an updated book - I'm just waiting for the book generator to discover the bad move that caused Cake's only loss in the big match between Cake and KingsRow late last year.

Thursday, February 17, 2005

An opening book for Linux-Cake

Peter Chiochetti recently revamped his checkers interface for Linux. The best engine for this interface is an old version of my checkers program, Cake++ 1.19. Yesterday, I added some code to it to handle an opening book and built a 115'000 move opening book from my opening database for it. Peter will first have to check my new code for compatibility issues with Linux, so it may take a while for this new version to appear on Peter's website. The book should be virtually error-free and worth the wait.

Wednesday, February 16, 2005

A well-deserved retirement

Back in early 2002 I wrote a program that automatically generates a checkers opening book, without any human intervention. The algorithm for this was invented by Thomas Lincke and it's called drop-out expansion. I have a computer at home which works on the opening book day and night. Yesterday, I replaced its mainboard, CPU and memory for newer components. After 20 months of nonstop computing, this AMD Athlon XP 2400+ CPU has certainly deserved retirement! During this time, it searched through nearly 100'000'000'000'000 checkers positions, generating the largest part of my now 1.6 million-move opening book.
The replacement is an AMD Athlon 64 3400+ CPU, like the old machine this one also has 1.5GB memory. The reason that I don't have Intel inside is that the AMD processors are better suited for integer computations than the Intel CPUs - for floating point it's the other way round. But since checkers programs (chess programs too) only use integer numbers, you get much more bang for the buck when you choose an AMD processor.

Tuesday, February 15, 2005

Exaggerations, part 1

There are a lot of computer checkers programs, but on my website I link only to very few of them. The reason is that most of the programs out there are not very good. Even worse, their authors claim things about their programs that are far from true. I'll look at a few of those.

Let's start out with strategist checkers by Arthur Crump, which is advertised as "Strategist checkers is the ultimate opponent". Mr Crump boldly continues "Whether you're brushing up on your game or practicing for a tournament, strategist checkers can help you". You can play against the lowest of 3 playing levels in the unregistered version. Even a pathetic player like me can easily beat it on that level. To get access to the other levels, you're supposed to pay 10$. The program has practically no other features except load and save game, and that of course isn't PDN! No book, and no endgame database, of course.

For the fun of it, I had Cake Manchester play without book on the instant level (1/100th of a second thinking time) against Strategist checkers. You can copy-paste the resulting slaughtering into CheckerBoard. Cake never got the opportunity to use its endgame database, because the game ended before the database was relevant!

The bottom line: This program is so incredibly bad that Mr Crump's wild claims about his program are immediately obvious. He can only hope to fool those who really know nothing about checkers or checkers programs at all. Mr Crump easily wins the title in the category "largest difference between real and advertised playing strength". And that guy earned more money with his program than I did with mine :-(

[Black "Cake Manchester 1.09"]
[White "Strategist Checkers"]
[Result "1-0"]
1. 11-15 23-19 2. 8-11 22-17 3. 4-8 17-13 4. 15-18 24-20 5. 9-14 27-24 6. 5-9 31-27 7. 18-23 27x18 8. 14x23 26-22 9. 11-15 22-17 10. 7-11 25-22 11. 9-14 30-25 12. 14-18 19-16 13. 12x19 32-27 14. 23x32 13-9 15. 6x13 20-16 16. 11x27 28-24 17. 19x28 17-14 18. 10x26 25-22 19. 18x25 29x22 20. 26-31 22-18 21. 15x22 21-17 22. 31-26 17-14 23. 27-31 14-10 24. 2-7 10-6 25. 1x10 1-0

Monday, February 14, 2005

The world's most awful checkers program...

...is undoubtedly Braveheart Checkers 3D". Do not install it on your computer! And its not the absolutely useless 3D Braveheart-themed environment in which you play checkers that makes it the most awful. And also not the engine, which is quite decent. What makes it the most awful program of them all is that it will install tons of spyware on your computer when you install it. You'll have to do a lot of cleaning up. Shame on those who publish this kind of program!

Saturday, February 12, 2005

Kingscourt

As I already mentioned yesterday, Kingscourt checkers (first side to make a king wins) cannot be a draw, unlike regular checkers or losing checkers. But which is it? Make your guess now, I will answer the question in a future post!

Checkers Variants

One of the problems of checkers is that it is played in a bazillion different variants in different countries. Chess is played with the same rules in all countries, and I strongly believe that this is one of the reasons that it is much more popular than checkers. In Europe, you cannot go from one country to another without changing rules: the board size (8x8 or 10x10), the capture rules (men can or cannot capture kings, men can or cannot capture backwards), the king movement (chess-king-like, flying in two different forms), the board orientation and the side to start the game can change. The last two items are essentially irrelevant, since they are just a convention - the game itself doesn't change if you change these rules, but of course it will appear unfamiliar to a player accustomed to another playing style.
Now, even without changing the possible moves, we can generate checkers variants: I'll take a closer look at two specific changes. The first is Kingscourt: the first side to make a king wins. If one player loses all pieces or cannot move, he loses. Another variant is Losing Checkers (also called suicide checkers): The side which loses according to normal rules wins.
The first thing to note is that Kingscourt cannot end in a draw; it must be a win either for black or for white. Losing checkers on the other hand has many drawn endgame positions, some of them are quite surprising! I'll return to this topic in my next post.

Thursday, February 10, 2005

The end of checkers?

The advent of huge endgame databases has made computer programs very strong. While the current top PC programs all use the 8-piece endgame database, researchers in Canada finished their computation of the 10-piece endgame database in May 2004. With the help of this database, they hope to solve checkers once and for all; solving meaning that they will be able to say what the correct result of a game of checkers should be if both sides never make a mistake. The answer is in fact already clear now, checkers is a draw. However, until now this is only a conjecture and will be proven by the Chinook team within a few years. On their website you can view the proof that the White Doctor opening is a draw.

Wednesday, February 09, 2005

Gui Checkers .80

I recently came across a quite unknown checkers program written by Jon Kreuzer, Gui Checkers .80. Jon has written a very good chess program, so I was naturally curious about his checkers program. It turns out he wrote it (including the interface) in only a few days, so it's not as good as the best programs out there. But the interface has nice graphics, and I bet that with a little effort, Jon could develop a top checkers engine. Perhaps you can encourage him to do so?

Tuesday, February 08, 2005

The CheckerBoard Blog

After seeing so many blogs on the net, I decided to start my own. I will post on different subjects here: Computer checkers in general, CheckerBoard, Cake and occasionally checkers in general. I'll begin with a link to the only serious review of computer checkers programs that I could find on the net (and I'm not saying this because my program gets a good rating!): Bob Newell has taken the time to check out a huge number of programs and rated them all. Check out his checker program review page!