Tuesday, December 19, 2006

Computer power consumption

In a previous post, I promised to measure the power consumption of my PCs. I finally did this, and got the following results:

Computer off, power supply off: ......... 0 Watt
Computer off: ........................... 7 Watt
Windows idle after startup: ............ 64 Watt
Book generator running: ............... 112 Watt
Monitor (Flatscreen) alone: ............ 36 Watt

This result was slightly surprising for me. I would have expected my PC to use more power than 112 Watt when running Cake - after all, it is using the CPU fully and also using the harddisk quite a bit. What are all these 350 Watt power supplies for, I wonder? The result also changes my checkers programming economics post: My book generator now "only" uses 2.7kWh per day, or 0.35$ a day. Since I have been computing opening books for about 4 years now, that puts the worth of the opening book at 500$.
On the other hand, 112 Watt is still a lot, given that we should be moving towards the 2000-Watt-Society - I am using over 5% of my power consumption for something rather useless like checkers book building....

I also measured the power consumption of my other PCs. Unsurprisingly, my other desktop PC is quite similar to the book generator PC, while my old laptop with a 1.4GHz Centrino processor uses only 23.5 Watt idle and 39 Watt when running Cake. Turning off the LCD screen saves another 6 Watt. Here's an interesting thing: on my desktop PC (with a AMD 64 3400+), running Cake costs about 50 Watt more compared to the idle state of the PC for nearly 2000 kN/s. On my laptop, running Cake at about 70% of that speed costs only 15 Watt, or about 3 times less. That means that my laptop is producing about twice as many nodes/second with the same amount of energy. Unfortunately, I measured these numbers before I got my new Core Duo machine, so I have no figures for that.

Monday, December 18, 2006

Core Duo!

It's been a long time since I last bought a new computer (21 months, to be exact, a record for me in the last 10 years!) - but I just did it again: I got myself a new laptop with an Intel Core Duo CPU - unfortunately not one of the even better Core 2 Duos. However, even this machine is absolutely great! Cake runs about as fast on my Core Duo at 2GHz as on my Athlon 64 at 2GHz. But the cool thing is that I can run two instances of Cake at the same speed, if I want to. Not that this really helps me in any way... it just shows why these dual core machines are so cool. The days of single core CPUs are numbered (as far as PCs go, anyway), and the first quad-cores for consumers are already on the market. Which gives me a bit of a headache, because it means that I should try to rewrite Cake so that it can use these new CPUs with multiple cores! All good chess programs have this capability, but the only checkers program that I know of that could use multiple processors was Chinook. However, the speedup from multiple processors there was quite lousy compared to what is reported for chess programs. For chess, it's something like 1.9x faster for dual cores and 3.5x faster for quad-cores, for Chinook it was approximately 3x faster on 16 CPUs [1]. It's not quite clear to me whether checkers is inherently tougher to parallelize than chess or whether the implementation in Chinook was poor. Any opinions?

Friday, December 01, 2006

Usage Statistics for November

Since November 2006, the full 8-piece checkers endgame database is available for download on my website. I checked the usage statistics for my server, and found the following:

Month 2006 traffic
August 7.8 GB
September 67.3 GB
October 93.4 GB
November 142 GB

This means that the 8-piece database is responsible for about a 20-fold increase in data traffic from my website! It also means that the database was downloaded about 60 times. In the same month, CheckerBoard was downloaded 2'500 times, and the opening book 200 times. 60 downloads in one month is not that much, but it still makes me think about something like checkers@home...
For comparison, my 4 in a row program was downloaded 500 times, while Sudoku Champion didn't make it to the top 30 files which I can view.

Monday, November 06, 2006

Cake Manchester 1.09d - KingsRow 1.16: +20-17=251

The match between my "old" Cake Manchester 1.09d and KingsRow 1.16 finished with a narrow win for Cake - 20 wins vs 17 losses and 251 draws (naturally this is with books off - else it would be draws all around - or very nearly so). I also repeated the match with learning disabled in Cake, with the result that not much changed: +22-19=247. So to stay in line with my last post, that would mean that I could leave Cake alone somewhat longer - but the result is too close for comfort, and so I decided to start tuning Cake a bit. When I try to improve Cake, there are many different ways to do it. One of the things I sometimes try is to tune the evaluation function, i.e. to change weights of different terms in the evaluation (as opposed to adding new terms to the evaluation). When an engine has been a sitting duck for years, as Cake Manchester has, then it is quite well possible that the opponent (KingsRow in this case) is just well-tuned to beat Cake. Changing the playing style a bit might make quite a difference in such a case. So to start, I am trying to just tune Cake a bit to avoid Ed's last two years worth of tuning of KingsRow - of course, I don't just mindlessly change the evaluation weights; instead, I checked the games that Cake lost in this match. Then I also have some ideas left on how I might improve the evaluation function with new terms, and a new idea for the search which I already tested but which didn't work well in the first implementation. Nevertheless, it also didn't work too bad, and perhaps with some refinement it will work. If all runs smoothly, I will have a new version of Cake ready for Christmas!

Wednesday, November 01, 2006

KingsRow 1.16

Checkers programming is going slow for me these days, and I don't seem to be the only one: It took Ed Gilbert over half a year to release a new version of KingsRow (1.16) which is now available for download on his webpage. We both seem to have used our time for other projects (For me, writing a suicide checkers engine, for Ed, more sensibly, writing a 10x10 international checkers engine).

I am running a match with KingsRow 1.16 against Cake Manchester 1.09d right now, and it's looking good for KingsRow: after 200 of 288 games, KingsRow is in the lead with 12-11 wins. If KingsRow wins the match, it would be the first time ever since 2004 that I see Cake losing a match - which brings me back to the introduction of this post: One of the reasons that I didn't do very much since my initial Cake Manchester release in 2004 is that it consistently beat KingsRow since then, and that I wasn't motivated to work on Cake because it was (IMO of course) still the world's most powerful checkers engine. It looks like I might have to shake the dust off Cake's source code soon!

Sunday, September 17, 2006

Checkers programming economics

I received a rare donation for CheckerBoard the other day, so today I thought I could try to calculate the economic aspects of CheckerBoard. Here's what I came up with: At the end of november 2005 (10 months ago) I redesigned my checkers webpages and added Google ads to them. I also added that infamous donate button. On the negative side, I have a computer running 24/7 working on CHOB. In Z├╝rich, electricity costs 0.16 Swiss Francs per kWh (that's about 0.13$/kWh). I'll try to measure the power consumption of my PCs soon, for now I'll assume that such a PC needs about 200W, which makes about 5kWh/day or 65 cents per day. So that gives me a daily budget of

Income from Google Ads:....+0.45$
Income from donations:.....+0.25$
Electricity bill:..........-0.65$

which leaves me with an income of 5 cents a day - not exactly much. Nevertheless, I shouldn't complain: Ed Gilbert has no Google ads, and no donations, and he's running 5 (!) machines simultaneously...

As a PS, it is no wonder that Murray Cash gave up on Nemesis!

Tuesday, September 05, 2006

Book update

I released a new version of Cake's Huge Opening Book (CHOB) recently. The new version is now based on about 2.35 million positions that were analyzed by Cake, the previous version (released in mid-April) was based on about 2.2 million positions. The new book would be approximately one ply deeper in the shallower main lines than the old book; however, I also threw out all positions which are in the leaf of my book tree - i.e. those positions where no successors have been searched. The reason I threw out those positions is that they are based on a 90-second book-generating search on a fast computer (AMD Athlon 64 3400+ with 2GB ram), which is good, but perhaps not good enough. The book-generating search produces evaluations for all moves in a given position, and takes longer than the regular search to reach a specified search depth. Therefore, it is approximately equivalent to a 30-second regular search on a fast machine. That means that if you set Cake to search for more than 30 seconds on a fast machine (and if you have the 8-piece database), then you might get a better move than what is in the book. This alone is enough to throw out the leaf positions, but there is more: Ed Gilbert actually found a losing book move in my first release of CHOB, and it was just such a leaf node. Now, this move is no longer in the book, and if you give Cake enough time, it won't make this losing move. Looking at the data from the opening book generator, it seems that it will have to run for another 2-3 months until it will expand that position with the losing move further.
Having found (or been told about, rather) one error in CHOB 1.0, I have to assume that there were more errors. After all, Even in a 288-game-match only about 288x10 = ~3000 book moves are actually played by Cake. Now that I know that one of these was a loser, I could extrapolate and say that 1 of 3000 moves is bad, and that therefore there are approximately 1000 losing moves in the book. I don't think it's this bad at all though, but there is no way to really know.

Wednesday, August 30, 2006

The 8-piece suicide checkers database

It's been a long time since my last post - but that doesn't mean I wasn't doing anything! It just took a long time to do it. But as of today, my suicide checkers 8-piece database is ready. It took about 1 month to compute on an Athlon64 3000+ with 1.5GB memory, and another 2 days to compress it. I decided to compute it after Ed Gilbert told me I was wasting my time computing a suicide checkers opening book with "only" the 7-piece database. I realized he was probably right, and so I stopped that opening book computation and went for endgame database computation. Adapting the database-building code from 7-piece to 8-piece should have been straightforward, but of course there were some little traps into which I promptly fell: In regular checkers, I didn't compute the lopsided databases (like 5-3, 6-2 and 7-1 pieces), and I didn't have any problems with my code. In suicide checkers these databases are important too, and my code to compute the binomial coefficient of n and k (I hope that's what it's called in English; it's = n!/(k!*(n-k)!) ) promptly overflowed past the size that a 32-bit integer can hold, and my database builder crashed when computing the 7-1-piece database. Next, Suicidal Cake crashed when I tried to use it with the 8-piece database - I noticed that I had a hard limit of 25 database files which I could open in my 8-piece database code. But with the new lopsided databases, I needed more, and that caused the crash. After fixing all these bugs, it now seems to be working.

The database takes 113GB uncompressed on my disk, and it is compressed to 18.4GB - that's just over a 6-fold compression. The regular checkers 8-piece database compresses over 4 times better, which shows that the suicide databases are more irregular. I'm surprised that I can even use the database with any efficiency at all, since it is so large, but Ed Gilbert already predicted that this would be the case. He has experience with even larger databases, having computed the 9- and 10-piece databases for regular checkers.

Enough for now, I am going to test my new toy!

Saturday, June 03, 2006

Suicide checkers rematch

On May 29th, Suicidal Cake (now in version 1.13c, with a larger endgame database and less materialistic evaluation than last time round, also with a new 30'000 move book) played a rematch against Suicide Kallisto. We again played 4 games, and again, Kallisto proved to be stronger. At least this time the result was not too lopsided, with +1=1-2 from Cake's point of view. The first two games were horrible to watch: they were a direct repetition of two themes which cost Cake two games in the last match. In the first game, Kallisto sacrificed 2 men just to get a red piece of Cake on the dreaded 21 square, then sacrificed a 3rd man and won convincingly. In the second game, Kallisto sacrificed a man to get an endgame where Cake's pieces were trapped on the edge.
I knew about both themes, the man on 21 and the mobility issue, and had improved Cake accordingly, but apparently I'm still not evaluating these things highly enough. In the 3rd game, Cake showed it wasn't a pushover, by sacrificing a man itself (to place a white man on square 5, which is probably not as bad as square 12/21, but also bad). Cake then went on to win. The last game ended in a fast draw.

[Event "Kurnik"]
[Date "2006-05-29"]
[Black "Suicidal Cake 1.13c"]
[White "Kallisto Suicide Checkers 1.13"]
[Result "0-1"]
1. 10-15 23-18 2. 9-13 21-17 3. 7-10 18-14 4. 3-7 14-9 5. 5x21 24-19 6. 15x24 28x19 7. 6-9 19-16 8. 11x20 27-23 9. 9-14 22-17 10. 13x22 26x17 11. 10-15 17x3 12. 15-18 23x14 13. 2-7 3x10 14. 1-6 10x1 15. 8-11 1-6 16. 20-24 0-1

[Event "kurnik"]
[Date "2006-05-29"]
[Black "Kallisto Suicide Checkers 1.13"]
[White "Suicidal Cake 1.13c"]
[Result "1-0"]
1. 9-13 24-20 2. 12-16 21-17 3. 5-9 28-24 4. 8-12 25-21 5. 1-5 32-28 6. 4-8 29-25 7. 11-15 20x4 8. 9-14 22-18 9. 15x29 26-22 10. 14-18 23x14 11. 7-11 14x7 12. 3x10 30-26 13. 12-16 26-23 14. 5-9 24-20 15. 9-14 28-24 16. 29-25 24-19 17. 25x18 19x12 18. 13x22 21-17 19. 14x21 23x7 20. 21-25 27-24 21. 25-30 31-27 22. 30-26 7-3 23. 11-15 3-8 24. 6-9 20-16 25. 2-6 8-3 26. 6-10 16-11 27. 22-25 11-7 28. 25-30 24-20 29. 26-22 27-24 30. 30-26 7-2 31. 26-23 20-16 32. 23-26 16-11 33. 26-31 3-8 34. 31-26 24-20 35. 26-23 8-3 36. 9-14 3-8 37. 15-19 8-3 38. 14-17 3-8 39. 22-18 20-16 40. 18-22 11-7 41. 22-25 8-3 42. 25-21 4-8 43. 17-22 8-4 44. 21-17 3-8 1-0

[Event "kurnik"]
[Date "2006-05-29"]
[Black "Suicidal Cake 1.13c"]
[White "Kallisto Suicide Checkers 1.13"]
[Result "1-0"]
1. 9-13 22-18 2. 12-16 26-22 3. 16-20 31-26 4. 10-15 18-14 5. 5-9 14x5 6. 8-12 23-19 7. 6-10 22-18 8. 15x31 19-16 9. 12x19 24x8 10. 3x12 28-24 11. 13-17 21x14 12. 10x17 25-21 13. 2-6 21x14 14. 6-9 29-25 15. 9x18 25-21 16. 7-11 21-17 17. 4-8 32-28 18. 18-22 17-14 19. 12-16 14-10 20. 22-26 30x23 21. 31-26 10-7 22. 26x19 24x15 23. 11x18 28-24 24. 8-11 7-3 25. 11-15 3-7 26. 18-22 7-10 27. 16-19 10-7 28. 19x28 27-23 29. 22-26 7-11 30. 15-19 1-0

[Event "Kurnik"]
[Date "2006-05-29"]
[Black "Kallisto Suicide Checkers 1.13"]
[White "Suicidal Cake 1.13c"]
[Result "1/2-1/2"]
1. 9-13 24-20 2. 12-16 22-17 3. 13x22 26x17 4. 8-12 28-24 5. 4-8 25-22 6. 16-19 23x16 7. 12x28 17-13 8. 5-9 21-17 9. 1-5 31-26 10. 8-12 29-25 11. 11-16 20x11 12. 7x16 27-24 13. 2-7 26-23 14. 16-19 23x16 15. 12x19 24x15 16. 10x19 22-18 17. 3-8 25-22 18. 8-11 30-25 19. 19-23 18-14 20. 9x18 22x8 21. 5-9 8-4 22. 23-27 32x23 23. 28-32 25-22 24. 7-11 22-18 25. 32-28 23-19 26. 11-16 19x12 27. 28-24 4-8 1/2-1/2

Wednesday, April 26, 2006

Match report

I posted a match report on the suicide checkers match between Suicidal Cake and SuicideKallisto to my checkers website. You can jump to the report directly: the match report. You can replay the first 3 games online, the fourth would have been identical to the second, and only lasted 3 moves so I left that one out...

4-0 again!

Tonight, Suicidal Cake played a match on Kurnik against SuicideKallisto by Igor Korshunov. Once again, the match was extremely lopsided, and the result 4-0 - but this time, Suicidal Cake was the one to lose!
SuicideKallisto demonstrated a far superior understanding of the game and completely destroyed my program; the final humiliation came in game 4 when Cake tranposed moves in the opening to reach the same position as in game 2, which it had lost previously. I resigned on move 3, because we would just have repeated game 2. Igor generously offered me to play a different move somewhere, but I didn't want to - if my program is too stupid to realize that it is playing into the same loss again, then that is entirely my fault, and it's not really my program that was that stupid, but rather me...

Congratulations to Igor for a fantastic suicide checkers program and for the clear win in this match! I will post the games later on my website.

Saturday, April 22, 2006

Another suicide checkers challenge

I just received the following email:

From: Igor Korshunov
To: Martin Fierz
Date: 4/21/2006

Hi Martin!I am made first version of suicide checkers.I want to match your program.When we can meet in battle?

Best wishes,Igor

I'll try to hold this as an online match on Kurnik again - once I know the time and date, I will publish it here.

Igor is the author of WildCat, a strong chess engine. He has also written a checkers program playing the Russian checkers variant, but I couldn't find an internet reference for that. WildCat is much better than Muse, my chess engine. You can verify this on Leo Dijksman's rating list, where WildCat is rated 2570, while Muse is only rated 2382. In my defence, I never took up chess programming very seriously. In any case, Igor's background in computer programming makes it unlikely that the match will be quite as lopsided as the one against Roshi47.

Tuesday, April 18, 2006

The Book!

I'm still not satisfied with the huge opening book - but I guess I never will be... so I posted it on my checkers site. I'll probably write some more about it later; for the moment: Enjoy!

Friday, April 14, 2006

A hidden function

Sitting here in a comfortable sofa, with the Matterhorn visible through the window, I remember that many years ago I once read in a computer magazine that you could press a wild combination of keys in Excel, and you would get a flight simulator. I tried, and indeed, there was a simple flight simulator where you would fly past something like a mountain where the names of the developers of Excel (a lot of people!) were displayed. Weird stuff! CheckerBoard also has a hidden feature: the engine match. When I want to test a change in Cake, I run a match of 288 games against KingsRow to verify that I have really improved something. Of course, this is all automated, and you can run such a match too: Ctrl+Shift+M starts a match - you can figure out the rest for yourself - I have to go back to staring at Switzerland's most beautiful mountain...

Monday, April 03, 2006

Odds and Ends

I'm busy waiting for my book generator to finish its book computation - but I'm not busy with checkers! Instead, I added a touch to my Connect Four program: it has nicer graphics and now offers different levels of evaluation intelligence - you can make it really dumb so that you can beat it easily. I also just finished a Sudoku program, using C#. C# makes it much easier to create applications rapidly. At least I'm programming something at all; I didn't find much time for that during the last year. Ed Gilbert has used my laziness to catch up with Cake: In my latest match, KingsRow 1.15u still lost to Cake Manchester 1.09d with -21+17=250, but this narrow result may just as well be accidental - Ed has some more results at different levels, and sometimes Cake wins, sometimes KingsRow. When I published Cake Manchester somewhere during Summer 2004, the match results against KingsRow were extremely lopsided - those were the days!

Friday, March 10, 2006

Switzerland 6, Canada 0!

The suicide checkers match ended in an even clearer result than the hockey match between Switzerland and Canada at the olympic games: Suicidal Cake beat Roshi47 4-0. Its authors then challenged me to two games human-human, and I managed to raise the Swiss score to 6-0. All in all, a surprisingly lopsided affair. I wrote a short article on the match. I have a couple of afterthoughts on the match, which I will add to that article in a couple of days. All that is left to add right now is the following email which I received today:

To: Martin Fierz
From: Jonathan Schaeffer
Subject: Suicide Checkers
Date: Wed, 8 Mar 2006 16:48:02 -0700
X-Mailer: Apple Mail (2.746.2)

Congratulations! Experience trumps youth :) I think both
Mike and Frano are stunned at the result.

Now, that is something to be proud of :-)

Monday, February 20, 2006

The fastest suicide checkers loss?

I've been playing around a bit with my book generator for suicide checkers because of the upcoming match against the Canadians. I was looking at early losses in suicide checkers, and this is the earliest I found so far:

1. 10-15 22-17 2. 6-10 23-19??

Red to move and win! Can you solve it? Can you find a faster way to lose a game of suicide checkers?

Wednesday, February 15, 2006

Tweaking the book generator, part 2

At the end of last year I received the following email:

Hi, I recently played Cake Manchester 1.09d and set the time to 10 Seconds and used Best Moves, and Cake couldn't even draw. I analyzed the game and saw that Cake played terribly through out the game. I think that you should produce or if you already have then release a newer version because it's too easy for me.
Attached is the game that I won. Please view it.



Attached was the following game:

[Event "I Lose"]
[Date "2005-12-29"]
[Black "Chikita Mia"]
[White "Yacoob"]
[Result "1-0"]
1. 11-15 24-19 2. 15x24 28x19 3. 8-11 22-18 4. 11-16 25-22 5. 16-20 32-28 6. 10-14 22-17 7. 9-13 17x10 8. 6x22 26x17 9. 13x22 30-26 10. 4-8 26x17 11. 8-11 29-25 12. 11-16 25-22 13. 5-9 19-15 14. 16-19 23x16 15. 12x19 17-13 16. 9-14 22-17 17. 14-18 17-14 18. 19-23 27-24 19. 20x27 31x24 20. 23-27 24-19 21. 27-31 14-9 22. 1-6 28-24 23. 31-27 24-20 24. 27-24 9-5 25. 18-23 19-16 26. 7-11 15x8 27. 3x19 5-1 28. 6-9 13x6 29. 2x9 21-17 30. 9-13 17-14 31. 23-27 20-16 32. 27-32 16-11 33. 19-23 11-8 34. 23-27 1-6 35. 27-31 6-10 36. 31-26 10-15 37. 26-22 14-10 38. 32-28 15-11 39. 13-17 8-3 40. 24-19 10-6 41. 22-18 3-8 42. 17-22 11-7 43. 18-15 6-1 44. 22-26 7-11 45. 15-18 1-6 46. 26-31 6-10 47. 31-27 8-4 48. 27-24 10-6 49. 24-20 6-10 50. 19-16 10-7 51. 16-12 7-3 52. 28-24 11-7 53. 24-19 4-8 54. 20-24 7-10 55. 18-15 10-7 56. 24-27 8-4 57. 27-23 4-8 58. 23-18 7-2 59. 19-16 2-6 60. 18-14 8-4 61. 16-11 6-1 62. 15-10 1-5 63. 10-6 5-1 64. 14-10 1-5 65. 6-1 5-9 66. 1-5 9-13 67. 10-15 13-17 68. 15-18 17-13 69. 18-22 4-8 70. 11x4 3-7 71. 4-8 7-10 72. 22-18 13-17 73. 18-14 10-15 74. 14x21 15-18 75. 8-11 18-23 76. 12-16 23-27 77. 16-19 27-32 78. 11-15 32-28 79. 5-9 28-32 80. 19-24 32-28 81. 9-14 28x17 82. 21x14 1-0

You can make up your own mind as to what I thought when I read that email and looked at the game - in particular check out the game headers :-)
But leaving these petty details aside, I checked on this game quickly - after all, it's not often that Cake loses a game so I decided to investigate. Most of the time, it's because Cake's published opening book has some errors left, and they are fixed in my 2-million-move-book. It turns out that in this game too, Cake is lost when it leaves the book with 9...30-26. I looked at my large book, and - the same error is in that book too! According to Basic Checkers, white should play 22-17 instead of 32-28 on his 5th move. I changed my book generator so that this line will be expanded sooner.
So what was the problem that this line wasn't expanded? Basically, it has a lot to do with the design of the book generator, which I wrote in december 2001. At that time, I only had a 6-piece endgame database, and I didn't foresee what would happen once I had the 8-piece database and 2 million book positions: Most of the positions that my book generator is looking at now are positions which are a more or less clear draw - Cake can see ahead far enough to hit the 8-piece database and return an evaluation of 0. When this started happening (years ago already!), I decided I didn't want the book generator to spend lots of time computing obviously drawn positions. There are many solutions to this problem, and unfortunately, I chose a rather bad solution (it was a quick fix - often a bad idea!): I decided to reduce the priority of positions (i.e. decrease the chance that the book generator would look at them again) which have a heuristic evaluation of 0. With heuristic evaluation I mean that Cake can already see the 0 evaluation in that position - it doesn't have to expand further to be able to back-propagate a 0 evaluation. That is what happens to all first moves: all seven first moves also have a 0 evaluation which has been propagated from the book tree - but they all have non-zero heuristic evaluations. In the example above, Cake produces a heuristic 0 towards the end of the book line, and that was enough for that line not to be expanded further. Now it's your turn to think: what could I do to make my book generator smarter?

Sunday, February 05, 2006

Tweaking the book generator

I was in the alps on my winter holiday for the past two weeks, and used the times in between skiing (when my knee hurt...) to tweak my book generator a bit. I knew of two lines in the book generator that were not what they should be. The first one goes like this:

1. 11-16 22-18 2. 10-14 25-22 3. 8-11 24-20

My openings database thinks that 8-11 is a big mistake because of 24-20 - because red must play 4. 16-19, sacrificing a man to draw. Now, if this 4. 16-19 line was expanded just a couple of moves further, it would play into the white doctor opening (1. 10-14 22-18 2. 12-16 24-20, and now 3. 16-19 is required to draw), which is in the book as a draw. However, this line is not expanded further because of the way the book generation works: if a move is thought to be clearly inferior, then it is not expanded any deeper, or only much later than the best move. In this example, 3. 7-10 is recognized as a draw, and therefore 3. 8-11 never got expanded much further. In a way, this is no serious error in the book, because it is meant only to find sound lines, and if you know one way to draw you don't need another. On the other hand, I would like my book to be a reference which checkers players can trust (once I publish it...), and if it doesn't know about this line, then people could easily be disappointed. The simplest fix to this problem is to tell the book generator to expand this specific line more deeply. This is also a very stupid approach, because the fact that the generator didn't expand this line is telling me that there may be other similar lines that it didn't expand and which would be worthy of expansion too. With over 2 million positions in the book, there is no way for me to check everything, so I have to make sure that whatever fix I make, it will affect the way that this line and others like it are expanded after the fix. In this case, I decided to penalize mistakes on the first 10 moves less than on later moves, causing an earlier expansion of the line above. I wanted the transition to be somewhat smooth so I used a weight of 0.05*depth + 0.5 with which I multiply the penalty for errors on the first 10 moves; for later moves the weight is 1.0. This change has had the desired effect: The line in question is now going to be expanded soon.

There is another line which I had to find a fix for, where even my 2-million-moves book still had a losing move in the book. It's a longer story so I'll keep that for my next post!

Saturday, February 04, 2006

Suicide checkers challenge!

I just received a mail from the Chinook creator, Jonathan Schaeffer. It says:

I have a couple of students who built a suicide checkers program
as a course project. They have tinkered around with it since then
and are curious to know just how good it is. Obviously it kills
all humans. I understand you have a strong suicide checkers program.
Would you be willing to have your program play a match with them?

I'm looking forward to giving SC another spin. On the downside, in the process of saving, synchronizing and backing up things, I seem to have lost the source code of both the latest SC and the latest endgame database builder for SC - I'm feeling pretty stupid! I still have the latest version of the programs and I hope I won't manage to lose those too...

Tuesday, January 17, 2006

Kingscourt solved!

Today, my opening book generator for the game of Kingscourt terminated because it solved the game: white wins in approximately 62 half-moves ( Kingscourt is the checkers variant where crowning a man wins the game). The method with which I solved the game only gives a result and a complete opening book with which the win can be played out; there is no guarantee that this is the shortest possible win. If you want to try to outwit the perfect opponent, you can download the book: kingscourt_book.zip (~2MB). You will have to extract the book in your CheckerBoard directory (not the engines directory), and kingscourt.dll should recognize it. Once you get out of the opening book, you will have to let the dll compute the win, but this should take no longer than a few seconds.

The opening book for the proof contains about 200'000 nodes, and was constructed in about 4-5 months on an AMD Athlon 64 system, using kingscourt.dll to search each of these 200'000 nodes. Initially I thought the game would be easier to solve, and I didn't put too much effort into optimizing the algorithms - I'm sure there is a lot of room for improvement left.

The whole idea of automated opening book computation on which this proof is based is due to Thomas Lincke.