Suicide checkers match: the details

General Discussion about the game of Checkers.

Who will win?

Poll ended at Tue Mar 07, 2006 11:40 am

Roshi47
0
No votes
Suicidal Cake
5
100%
 
Total votes : 5

Suicide checkers match: the details

Postby Martin Fierz on Thu Mar 02, 2006 11:40 am

Aloha!

as promised, here are the details of the suicide checkers match:

It takes place on wednesday, March 8, 19:00 Swiss time, which is GMT+1, on http://www.kurnik.org. We will play either 2 or 4 games at 30s/move, depending on how fast the games go.

The participants are Suicidal Cake 1.11 and Roshi47. Here are some details on each program:

Suicidal Cake 1.11 by Martin Fierz will be running on an AMD Athlon 64 3400+ with 2GB ram. SC has an opening book based on about 200'000 positions, and the full 7-piece endgame database (which is about 2GB compressed). It searches about 3'000'000 positions per second. It is based on Cake Manchester 1.05, with some changes for suicide checkers (some obvious ones like the necessary changes for the rules, and some less obvious ones concerning the search behavior). It has played some games against human experts and won every single one of them.

Roshi47 by Mike Smith and Frano Sailer is based on a Suicide Checkers program developed for a graduate course at the University of Alberta, in Jonathan Schaeffer's class (That's right, the guy who made Chinook!). Mike and Frano are graduate students in Schaeffer's group. The initial search program had an undefeated tournament record. Since then, it has been enhanced by the addition of 8-piece endgame databases, which total over 18GB in size (compressed!). Its evaluation function has also been trained by a machine learning algorithm under self-play. The new learned evaluation defeats all previous versions. Roshi47 will be running on a machine with approximately equivalent specs as the one Suicidal Cake will be running on. The name comes from an ancient Japanese story, http://en.wikipedia.org/wiki/47_samurai .

Enough said, try to guess the winner! Of course, we will be happy to chat during the match, as we only have to operate our programs!

cheers
Martin
Last edited by Martin Fierz on Thu Mar 02, 2006 6:50 pm, edited 2 times in total.
Martin Fierz
 
Posts: 33
Joined: Mon Dec 05, 2005 3:37 pm
Location: Z

Re: Suicide checkers match: the details

Postby Ed Gilbert on Thu Mar 02, 2006 1:52 pm

Hi Martin,

It seems that you may have quite a strong opponent for your match! In order to pick a winner, I have to consider several aspects of the programs:

Search + eval: very likely this will be a plus for Suicidal Cake. Of course I don't know the other programmers, but I just have to think its unlikely that the average graduate student is able to match your extensive experience and considerable skills at board game programming.

Match experience: here the graduate students have the edge. They have already played their program in several matches, and thus have had the opportunity to observe and correct problems arising from match play.

Endgame database: the grad students seem to have a big edge here. From what little I have read about suicide checkers, the endgame database is perhaps even more important than it is in standard checkers because heuristics based on material strength don't work well. In standard checkers, going from a 7-piece to an 8-piece database is a huge jump in strength, because the 7-piece db does not offer much improvement over a 6-piece db. Probably in suicide checkers this is not the case, and the step from 6 to 7 pieces is just as big as the step from 7 to 8 pieces. It is likely the graduate students have a big edge here, but not so big as it would be in normal checkers between 7 and 8 pieces.

Opening book: I didn't see any mention of an opening book for Roshi47. If it does not have one, then this is probably a huge advantage for Suicide Cake. I say 'probably' because its possible that suicide checkers is so different from standard checkers that automated opening book construction doesn't work well. But I think it is more likely that it does work well, because the branching factor has to be similar in both games, and the small branching factor in checkers is one of the key attributes of the game that make this technique so powerful, as opposed to other boardgames like chess.

Bottom line: Suicide Cake will win, based on its 200,000 position opening book, for which Roshi47 has no answer. Roshi's 8-piece db will not save it from making losing moves early in the games -- even a 10-piece db cannot completely prevent this in normal checkers. But you should have a strong opponent for your match. Good luck, I hope I will get a chance to see some of it.

-- Ed
Ed Gilbert
 
Posts: 127
Joined: Mon Nov 14, 2005 7:37 am
Location: Morristown, New Jersey

Re: Suicide checkers match: the details

Postby Martin Fierz on Thu Mar 02, 2006 6:46 pm

Hi Ed,

indeed, this is certainly a tough challenge for SC. I have no clue who will win. My guess is that SC will win the short games, while Roshi47 will win the long games.

In reply to your thoughts about the endgame database, I think that in general the endgame database is much more important in suicide checkers than in regular checkers. In the regular game, you can at least make some sensible guess about who will win based on the material count and position, while in suicide checkers that is absolutely hopeless. The game is totally dominated by tactics. The question is just whether my opening book can offset that huge disadvantage of the smaller endgame database. I also don't really know how good the opening book is - of course, there are lots of positions where it knows a direct win, but on the other hand, all positions with heuristic values of anything less than a database win may just be totally wrong. I only just did a little polishing on SC, and version 1.11 is much better at a certain kind of tactical theme than earlier versions, and I am recomputing the first N positions of my book - I want to recompute everything, but probably N will only be about 10'000 for this match. When I look at the log file of the recomputation I find things like this:

old value -102 new value 1977
old value 150 new value 1977
old value 28 new value 1975
old value 2 new value 1975
old value 42 new value 1975
old value -2 new value 1973
old value 20 new value 1977
old value 56 new value 1977
old value 72 new value 1975
old value -18 new value 1975

I admit, these 10 missed wins in the earlier version of the book are spread over 1500 recomputed positions, so the problem isn't all that big (also, the very first positions of the book were computed with the 6pc-database only). But you can see that there is no good correlation between the old value and the new value - the heuristic numbers in the book generator are not good at all. Because of that, I am also allowing much more freedom in the epxansion compared to the regular book generator.

I honestly have no idea what to expect from this match!

cheers
Martin
Martin Fierz
 
Posts: 33
Joined: Mon Dec 05, 2005 3:37 pm
Location: Z

Re: Suicide checkers match: the details

Postby Kenny on Sat Mar 04, 2006 8:00 pm

I will be there to watch.
Kenny
 
Posts: 1
Joined: Sat Mar 04, 2006 7:58 pm

Re: Suicide checkers match: the details

Postby Jake Lopez on Sat Mar 04, 2006 9:39 pm

me too
Absolute power corrupts absolutely.

A gentle stream can split a mountain, given enough time

A single death is a tragedy. A million deaths is a statistic.

A mathematician is a blind man in a dark room looking for a black cat which isn't there.
User avatar
Jake Lopez
 
Posts: 28
Joined: Sun Nov 20, 2005 8:54 pm

Re: Suicide checkers match: the details

Postby Bob Murr on Wed Mar 08, 2006 9:47 pm

Congratulations to Martin and Suicidal Cake

http://www.fierz.ch/suicidecheckers.php
Bob Murr
User avatar
Bob Murr
 
Posts: 158
Joined: Sun Nov 13, 2005 11:26 am
Location: Colorado Springs

Re: Suicide checkers match: the details

Postby AKA on Thu Mar 09, 2006 2:08 am

The match was very lopsided. Most of the top suicide players (George Miller, Yuri Sorkin, Igor Keder and probably 20 more) could defeat the Canadian Program. Congratulations to Martin Fierz also for winning his 2 games against the Canadian Authors in 2 more lopsided games.
AKA
 

Re: Suicide checkers match: the details

Postby Ingo_Zachos on Thu Mar 09, 2006 8:19 am

Ja, [b]Gl
Ingo_Zachos
 
Posts: 1269
Joined: Sun Nov 13, 2005 7:41 am
Location: Dortmund, Germany


Return to General Discussion

Who is online

Users browsing this forum: Bing [Bot] and 3 guests

class=