Nemesis wins the Computer Checkers World Championship in Las Vegas
26th January 2009: A new introduction to this report, as a response to the new edition of One Jump Ahead.
My report on the computer checkers world championship 2002 in Las Vegas hurt some people's feelings due to my comments on Chinook. Recently, Jonathan Schaeffer, leader of the Chinook effort, published a new edition of his book One Jump Ahead
(which you can buy at Amazon) where
Darse Billings (who is not a checkers programmer, and not a member of the Chinook team) calls this article obnoxious and slanderous,
and I myself am called a Dweeb, Pipsqueak and a Punk. Not being a native English speaker, I had to look those up! I got called all these names
for suggesting that Nemesis was the better program than Chinook, and for calling the Chinook database access code crappy.
What can I say? Perhaps my wording was not ideal, but I do like calling a spade a spade - perhaps I could have stated things a bit differently, but I certainly still
believe that Nemesis was the better program, and that the database access code wasn't exactly pretty. Apparently, even the Chinook team decided that the database access
code was worth replacing, and you can now download an improved version here.
An independent blogger wrote about this database access code:
Well, in a fit of productivity (or what passes for productivity when you are working on useless pet projects), I decided to get the Chinook 6 piece endgame database working in my checkers program. How hard could it be? They give you code to access it after all. A few simple adaptations, and….
Well, it’s not that simple. The code is dreadful. I mean really bad.
(retrieved on January 26, 2009 from
http://brainwagon.org/2008/05/13/chinook-endgame-database-working-pretty-much)
I don't know which version he is referring to, but I rest my case :-)
The report below first was written in an original version, and later I added some comments in italics. I haven't changed anything since.
I've added some notes after writing the final version of this report. They're in italics throughout. From August 3rd-9th, a computer checkers tournament was played in the Four
Queens hotel and casino in Las Vegas. Nemesis has won the title of "world computer tournament draughts champion" and has the opportunity to challenge Chinook for the man-machine world championship. In my opinion, the title which Nemesis won is worth more than the title Chinook currently holds. The challenge should actually be the other way round! After the results of this tournament, I also wonder about any title which has drawing odds for the defending champion. The programs are so close to perfection that this is a very tough situation for the challenger - on the verge of being unfair, in my opinion. Mac Banks, referee of this tournament said that this had probably been the highest calibre checkers ever played.
Some people have complained about this paragraph. They say I'm belittling the achievements
of the Chinook team. That's not what I meant to do. In my opinion, Nemesis played better checkers in Las Vegas than the
final version of Chinook did. But that does not change the fact that the Chinook project was groundbreaking, and
ahead of its time. When Murray and I computed the 8-piece endgame database, we were using their publications to guide us.
We used their 6-piece database
to verify our database generators were working properly. It's as they say: if we see further, it's because we're standing on the
shoulders of giants.
Participants in the tournament were Cake, KingsRow and Nemesis. We were all running on high-end windows machines, Cake on a P4 2GHz with 1.5GB RAM, Nemesis on a 1.6GHz Athlon with 2GB RAM, and KingsRow on a P4 2.4GHz with 2GB RAM. The performance difference between these machines was not very big, and had no effect on the outcome of the tournament. All programs were equipped with 8-piece databases, Murray and I had both computed our own, Ed was relying on the Chinook database - which he was going to regret. Nemesis is a commercial program, which is selling for 119$. The only difference between the commercial version and the one in the tournament was that the 'vegas' version had a bit a larger opening book. KingsRow and Cake are both available as free downloads on the internet, but the versions which we were using in las Vegas were much more powerful than the ones you can download - using the 8-piece database instead of the 6-piece database, with many bugfixes, and with much larger opening books. Cake 'las Vegas' beat the current version, Cake++ 1.41 in a test match just before the tournament with 20 wins to one loss in 122 games. The version of KingsRow playing in las Vegas beat the version of KingsRow on the net with 15 wins to zero losses in 122 games.
There were 24 games played between each two programs. The tournament was organized in 18 rounds of 4 games each. The openings were restricted to the 'computer tough deck', which consists of the 12 mail-play openings and 49 hard 3-move openings. You can look at the full rules on George Miller's site.
For those of you who do not play checkers: It is common practice to select an opening at random, and play it twice reversing the colors,
to make it fair on both sides. To decrease the chances of easy draws, we decided to use a reduced deck of hard openings.
The final set of rules was made after an initial proposal had been sent out to the participants, and their feedback was used to produce the final rules. The tournament director was Mac Banks, one of the world's best checkers-by-mail players. Below you can find a chronology of events and a couple of games to replay.
Day 1
Las Vegas in August! It's about 100 degrees Fahrenheit during the day, and the humidity can usually be measured with single-digit numbers. But as Ed Gilbert remarked, we are in the 'air conditioning capital of the world'. Day one didn't see much hot action either: The tournament started off with 4 draws between KingsRow and Nemesis in round 1, and continued with 4 more draws between Cake and Nemesis. Cake played a new move on the weak side of the Gemini I, which may or may not be sound. My opponents will have a chance to repeat with another attack by selecting the Gemini II, so I'm a little worried about that...
Below: Ed and Murray shake hands at the start of the first game of the tournament. Mac Banks is watching the games.
Day 2
The second day saw another 12 draws, 8 between KingsRow and Cake, 4 between KingsRow and Nemesis. Ed chose to play a sideline on the strong side of the skullcraker against me in the hope of getting me out of book early, but nothing came of it. Up to now, with all draws, our games are going rapidly so at least we have a lot of time for sight-seeing :-)
Since the last time I was in Las Vegas (1996) a couple of new hotel/casino/resorts have openend, and they are quite spectacular! The Venetian, the Bellagio and the Mandalay Bay are all very new and very exquisite. Below is a picture of the strip at night, seen from the stratosphere tower. You may be able to recognize the MGM Grand by it's green color, and the Luxor by it's light beacon. Between these two is the Mandalay Bay, perhaps the classiest hotel in Vegas right now. For my taste, the Bellagio is just a bit too much, but the water ballet (which featured in "Ocean's Eleven") is really cool, of course.
Day 3
The first 8 games of today between Nemesis and Cake were all drawn. I was afraid of Murray repeating the Gemini, which he didn't do though, because he thought my defense was sound. However, in the last 4 games of today Ed Gilbert chose the Gemini and KingsRow blew Cake's defence to pieces with a fine attack (involving the sacrifice of a checker, which is notoriously hard for computers...), winning the first and so far only game in this tournament. Ed had gone over the game of Cake against Nemesis, where Cake managed a draw. KingsRow chose a different attack against Cake's defence, which was more testing - but with correct play it might have still been a draw. However, my opening book had a bad move in it, which lead to a quick loss. I had my opening book generator take a close look at this line after the tournament. It thinks white has a big advantage, but it cannot resolve the question whether it's a win or a draw. The opening book had a bad move in, which gave Cake a bad position, but with correct crossboard play after the book, it remains unclear whether it would really be a loss. KingsRow took the lead, and even though there were still 40 games to go, I had the feeling that this game may already have been decisive. Which turned out to be wrong...
Day 4
Another day with draws all around, 8 between Nemesis and KingsRow, another 4 between Nemesis and Cake. However, a weak book move by Cake caused some excitement in round 11. Cake's book was generated by the program itself, in just 3 months for all 61 openings. The only way I influenced it was by telling it which openings to look at for how long - for example, I had it work on the black widow and on the black hole for about 4 days each, and on the geminis and wildernesses also for a couple of days. For some of the openings which seemed easier I had to make do with less time, so the book there was rather weak. This is what happened in this game. Replay the game!
Below: Murray, surprisingly wearing a Brazil shirt despite the loss of Beckham's boys agains the Brazilians at the world cup, me (with my obligatory Starbucks breakfast) and Mac. Murray's girlfriend is Brazilian, which explains his shirt. I'm living in Hawaii, which explains mine. Photo courtesy of Ed Gilbert.
Day 5
Cake and KingsRow played 7 draws in their first 7 games, and the last game of round 13 was heading for a draw as well. During the games we were always looking at each other's monitors to see what the other programs were thinking (The rules said that the computer screens had to be visible to both players, to prevent cheating). Often, one program would be seeing an advantage, and then the other player would start getting nervous. Was his program missing something? During this game, Cake was seeing a nice advantage (+20 to +30), and Ed was getting nervous. I made a joke that I would change my program so that it showed a database win in the next round, and when he had a heart attack, I would win by default. A few moves later, both of our programs showed database draws, and we were going to make a couple of moves more, just so that everything was clear, and then agree to a draw. But then KingsRow played a move which made Cake's evaluation jump to a database win immediately, while KingsRow was still showing a draw. As it turned out, we ended up in a position in the 4 men vs 4 men database which was won for Cake - but which showed up as a draw in the Chinook database which Ed is using in KingsRow. When it happened, we guessed that there was an error in the Chinook database Ed was using - we all knew that the original 8-piece Chinook database was flawed, and speculated that Schaeffer had put the old, uncorrected version on the web for download.
Round 13... hmm... maybe there is something to that number after all. At least Ed did not have a heart attack! Replay the game!
This was of course an awful situation for Ed, who didnt quite know what was wrong with his database. Ed and I had already decided before this tournament that he would like to use my database in the future because it is more compact than the Chinook database. So Ed asked me if he could get it right now to avoid losing another game due to his strange database error. Murray was not too happy with this, as I had been able to profit from Ed's bug, whereas he had not been able to do so. In the end, Mac Banks decided that we were here to find out which program was strongest, and not which database had bugs, so I was allowed to give Ed my 8-piece database and the access code to it to use. KingsRow played the last round of the day against Nemesis with the Chinook database, without any further bugs turning up, and in the evening Ed switched to my database, and used it for the remaining rounds. We didn't think we'd really need a referee, but as usual things turn out a bit differently than planned...
I'm glad Mac decided as he did, since it didn't affect the outcome of the tournament in the end. And winning such a tournament just because another program has a bug isn't really a great achievement, and would have devalued the tournament a bit. In a way, Nemesis also profited from KingsRow's problem, since after this round all programs were even again.
Day 6
In the meantime, Roberto Waldteufel, programmer of Wyllie told us that the final position in KingsRow's loss is in fact a loss in his version of the Chinook database. Ed may either have a corrupt database file, or have made an error in his database access code. The second version is quite likely, since the original access code on the Chinook website is written only for 6-piece databases and would take a top spot in any "obfuscated C programming" contest. Personally, I would be ashamed to publish code only half as crappy as that... Jonathan Schaeffer has also confirmed that his version of the Chinook database is correct in this position.
After the tournament, Ed found the problem: it was in fact an error in his database access code, which came from porting the Chinook code from 6-piece to 8-piece, where one of the database indices overflowed.
In the games between Nemesis and Cake of today, there were a couple of draws to begin with; in one of them Cake's auto-generated opening book came up with a new move - replay the game. For the final two games, Murray chose the Wilderness I. Cake took the 9-13 22-18 11-16 18-14 xx 6-9 defence. Nemesis came up with a great "computer buster" line, which took Cake out of book and into another of those dreaded man-down positions - with Nemesis being a man down. Nearly the whole game was played out of Nemesis' book! With this win, Nemesis took the lead with two rounds to go and is looking very good. Once again, I had my book generator scrutinize this game. It turns out that again, Cake made a mistake in a difficult position, where it could still have drawn. The game is published on the Nemesis website, where you can also find Murray's report of this event. In the last round of the day, KingsRow was trying to repeat the Wilderness win against me, but I varied by taking the other defence (9-13 22-18 11-16 18-14 xx 16-20). Cake managed to draw a tough bridge ending (Actually, it first had to make a bad move to get into the bad bridge ending!)(replay the game), which leaves only one round for tomorrow between KingsRow and Nemesis to play. If Nemesis draws the round, it wins the Championship.
Murray Cash is only four games away from the title!
Day 7
The last four games between KingsRow and Nemesis were all drawn, which makes the final standings: 1. Nemesis 26 points, 2. KingsRow 24 points, 3. Cake 22 points.
All 72 games will be published in Charles Walker's "Checkers Magazine", which should be out this December. To order, contact Charles at P.O. Box 365, Petal, Mississippi 39465, phone (601) 582-7090, fax (601) 583-9761. The computer games are only a small part of the magazine; this issue is dedicated to Marion Tinsley. The magazine costs 30$ before publication, 40$ after publication.
The picture below was taken during the last round, standing (left to right): Thomas Lincke, inventor of the "drop-out expansion" technique used in both KingsRow's and Cake's automated book generators, visiting in Las Vegas, Charles Walker, director of the international checker hall of fame. Sitting: Mac Banks, Murray Cash, Ed Gilbert.
Conclusions
In our 72 games, we had only three wins. One of these would not have happened without the error in Ed's database or access code, leaving only 2 losses (by Cake) in all 72 games. The other two programs played nearly perfect checkers, and were never in any real trouble. Both of these programs would have deserved to win, if KingsRow had not had this problem with the database. I think that although the format - "book wars in vegas!" - was criticized a lot, the tournament did place the programs in the right order. Cake definitely deserved the last place; it's opening book was the most vulnerable. Nemesis' win reflects the fact that Murray put more work in his program than Ed or I did - he verified his endgame database, and spent a lot of time making his opening book close to perfect, and I think he deserved to win this title.
The level of play was so close to perfection that I think I can safely predict that if we were to play with the same format in two year's time, we would see no wins at all any more. A different format will be necessary if we want to repeat this kind of event.
While we were playing, one of the most-heard questions was why some of the other programs were not there. The missing programs were Chinook, WCC and Wyllie. Chinook was actually invited to play, but Schaeffer didn't want to compete. That's a bit sad, as I would really have liked to see just how good Chinook was - after all, at the time it was playing, it had no competition at all from other computers due to it's far superior hardware, and it's hard to say how good it really was. Roberto Waldteufel, programmer of Wyllie, didn't come to las Vegas because of the travel expenses. In the British championship, 2 months before the las Vegas tournament, Wyllie lost 5 games out of 16 with 11 draws against Nemesis, and probably would not have been competitive in las Vegas. WCC did not play either in las Vegas. After first entering the event, they pulled out again, giving the possibility of an anti-WCC conspiracy as reason. I don't quite know how they got this idea, Ed and I both had our own chance to win this tournament, and the idea that we would throw games to Nemesis just to prevent WCC from winning is ridiculous.
Even though my program finished last, I had a great time in las Vegas. I enjoyed meeting Ed and Murray, who I only knew by email until then; Even though we were competitors, we had a good time together. I also enjoyed meeting some real checkers players who were playing in the national tournament, and Mac Banks, our diplomatic referee. One day Murray walked up to him and said with his English accent: "Mac, there is something here that we don't have in England, and I was wondering about it. Can you tell me what a (remember to use an English accent here) pawn shop is?". Mac of course misunderstood the question (which is easily misunderstood just because of the accent, and being in las Vegas of course makes it even more likely that you would be talking about porn shops) and came up with a fine answer: "Well, if you see something you like, you buy it. And if you don't know how to use it, ask for instructions". We had a good laugh over that... Mac did confess that he was kind of worried that Murray would want to continue the discussion :-)
I had planned to take a longish break from checkers programming after this tournament, but of course, I got some ideas while watching our programs play which I can't wait to test...
After realizing that Cake had made (at least) 3 weak moves crossboard, 2 of which cost it games, I worked a lot on my engine. The current experimental version would play the correct moves now - too late!
Back to main checkers page