Computer programs tournament

[tgf]

There is a guy in Poland, goes under the name Krzychumag on shashki.com, who does a wonderful job organizing and running World championships among computer programs, Russian checkers, Brazilian, and 10x10.
He sets up fast computers with similar hardware in his lab. He now wants to test Straight Checkers programs, many Russian programs have Draughts version, but I do not think they could compare to the dedicated programs you guys use.
Look him up, he proved himself a great and fair tester.

[MostFamousDane]

There is no point - Kingsrow is so many light years ahead of the competition.

[megamau]

Not to mention that straight checkers was solved by Schaeffer in 2007

http://www.cs.cornell.edu/courses/CS670 ... e-2007.pdf
http://webdocs.cs.ualberta.ca/~jonathan ... eckers.pdf

So programs of the level of Chinook would draw all their games.

[MostFamousDane]

Not to mention that straight checkers was solved by Schaeffer in 2007

http://webdocs.cs.ualberta.ca/~jonathan ... eckers.pdf

So programs of the level of Chinook would draw all their games.

Deep sigh

[Ed Gilbert]

Not to mention that straight checkers was solved by Schaeffer in 2007

http://webdocs.cs.ualberta.ca/~jonathan ... eckers.pdf

So programs of the level of Chinook would draw all their games.

Chinook solved GAYP checkers, not 3-move checkers. A number of 3-move ballots were solved in the process, but IIRC there are some that were not solved.
No program available to the public has the Chinook "opening book" that plays perfect GAYP checkers.
Computer tournaments could play 11-man ballots to negate the effects of large opening books, thereby exposing the true strengths and weaknesses of the search engines.

edit: I also disagree that kingsrow has no competition. Cake is at the same level of strength when both engines are configured with equal databases.

-- Ed

[megamau]

Chinook solved GAYP checkers, not 3-move checkers. A number of 3-move ballots were solved in the process, but IIRC there are some that were not solved.
No program available to the public has the Chinook "opening book" that plays perfect GAYP checkers.
Computer tournaments could play 11-man ballots to negate the effects of large opening books, thereby exposing the true strengths and weaknesses of the search engines.

edit: I also disagree that kingsrow has no competition. Cake is at the same level of strength when both engines are configured with equal databases.

Ed, I agree with all you say.
But at this stage, with the databases and current computing power, would computer checkers be interesting ?
Even with 11-man ballots, I foresee several hundreds (if not thousands) drawn games before a program makes a mistake in some very very very complex line.

Even for international draughts this problem can not easily be solved.

[Alex_Moiseyev]

would computer checkers be interesting ?

Yes, of course. 11 man ballot and/or 4-moves restrictions could be a good model. The programs should probably play in auto-regime with all 156 openings (312 games) by using 1-3 seconds for move. 6 or 8 pieces ending database can be use for all programs to equalize them.

It will be an excellent test for engine.

BTW. GAYP also not solved completely by Chinook, Chinook just doesn't lose the game and makes scientifically proved not losing moves. But theoretically there is a possibility that Chinook can miss a win. At least this is something which was never proved scientifically.

AM

[Ed Gilbert]

But at this stage, with the databases and current computing power, would computer checkers be interesting ?
Even with 11-man ballots, I foresee several hundreds (if not thousands) drawn games before a program makes a mistake in some very very very complex line..

I am not a strong player, so probably not a good judge of what might be interesting to players. As an engineer, program vs program matches are interesting to me. I often test kingsrow at very quick time controls with opening books turned off. Configured this way, there are plenty of lost games.

-- Ed

[MostFamousDane]

edit: I also disagree that kingsrow has no competition. Cake is at the same level of strength when both engines are configured with equal databases.

-- Ed

"Hvis og hvis, min røv var spids og fyldt med marmelade" My Grandma

[bazkitcase5]

It would be cool to see some kind of tournament done with the entire 11 man ballot deck - it would be a neat way to maybe start legitimizing the 11 man deck by helping eliminate those ballots that lose so we could then condense the deck to something more manageable.

Of course, a lower time control would probably make the this somewhat less effective, but it would be a start.

[Krzysztof Grzelak]

There is a guy in Poland, goes under the name Krzychumag on shashki.com, who does a wonderful job organizing and running World championships among computer programs, Russian checkers, Brazilian, and 10x10.
He sets up fast computers with similar hardware in his lab. He now wants to test Straight Checkers programs, many Russian programs have Draughts version, but I do not think they could compare to the dedicated programs you guys use.
Look him up, he proved himself a great and fair tester.

We sincerely thank you for your kind words about me tgf. It's me Krzychumag. I just wanted to write that last preparation for the tournament checkers English. So far in the tournament will have the following programs, of course, everything can change.

1. Aurora Borealis Professional
2. Kingsrow
3. WCC Platinum III
4. Sage Draughts 9.0
5. Nexus 99
6. Wincheck 3D 7.0
7. Gui Checkers 1.05+
8. Cake

For the tournament, I would like to include two programs - Nemesis 2.0 by Murray Cash and Wyllie Checkers by Roberto Waldtaufel . Unfortunately it's very hard to get these programs. If a person has these programs, please let me know, I will be very grateful.

Krzysztof

[Ed Trice]

Chinook solved GAYP checkers, not 3-move checkers. A number of 3-move ballots were solved in the process, but IIRC there are some that were not solved.
No program available to the public has the Chinook "opening book" that plays perfect GAYP checkers.
Computer tournaments could play 11-man ballots to negate the effects of large opening books, thereby exposing the true strengths and weaknesses of the search engines.

edit: I also disagree that kingsrow has no competition. Cake is at the same level of strength when both engines are configured with equal databases.

If you read Jonathan Schaeffer's updated book, "One Jump Ahead: Computer Perfection At Checkers," he described the concept of the "Proof Tree" and what was needed to solve the game of checkers. Initially, he thought that 50 openings needed to be solved, since transpositions were possible that could lead to the same middlegame landings and things of this nature. On page 485 of the book, he recounts how he calculated that 13 was the minimum number of openings that needed exhaustive analysis in order to be able to solve checkers. Minimum: The count could be larger.

Chinook maintains a data structure that prohibits it from entering into a loss when starting on equal footing. I'm not sure I would call this an opening book, since it is much more than that. It is the output of the Proof Tree. When playing against a fallible opponent, Chinook can at least draw and will always win once an opponent makes a losing move. Chinook will also maintain a draw for the entire game if an opponent does not make a flawed move. This is, by definition, having a program that definitively solved the game.

When programs of today play matches, there are 3 components that factor into play:

1. The opening books
2. The evaluation functions
3. The endgame databases

When you are running a match, you are testing the interaction of all three.

Because most opening books are good enough to avoid early losses, and even a 6-piece database can guide any middlegame position to a drawn ending, most programs have functionally solved checkers. That is, we must "tilt the playing field" to see if it is possible that, under extreme circumstances, one program can trump another one.

I believe Ed Gilbert and Martin Fierz enjoyed turning off their books and endgame databases to basically have an "evaluation function only match." I forget the final score, but it was extremely close, the time controls were very quick, and one program did emerge ahead of the other by an extremely slim margin.

I know both programmers were inspired to continually work on their evaluation functions so that they became incredibly strong in this respect.

When one program does emerge victorious, it is no longer "dominant" over the runner up: It is "first among equals," so to speak.

What we should do is rank programs according to the strengths of their books, evaluation function, and endgame databases.

I think it's safe to say Kingsrow's 10-piece opening book would have to be the deadliest/most accurate around.
Kingsrow and the strongest version of Cake are the top evaluation functions.
Kingsrow has the top endgame database set.

[MostFamousDane]

If you read Jonathan Schaeffer's updated book, "One Jump Ahead: Computer Perfection At Checkers," he described the concept of the "Proof Tree" and what was needed to solve the game of checkers. Initially, he thought that 50 openings needed to be solved, since transpositions were possible that could lead to the same middlegame landings and things of this nature. On page 485 of the book, he recounts how he calculated that 13 was the minimum number of openings that needed exhaustive analysis in order to be able to solve checkers. Minimum: The count could be larger.

Chinook maintains a data structure that prohibits it from entering into a loss when starting on equal footing. I'm not sure I would call this an opening book, since it is much more than that. It is the output of the Proof Tree. When playing against a fallible opponent, Chinook can at least draw and will always win once an opponent makes a losing move. Chinook will also maintain a draw for the entire game if an opponent does not make a flawed move. This is, by definition, having a program that definitively solved the game

As we have been over many times of this forum - Chinook team used heuristics in constructing the proof tree making their method unsound. The absolute minimum requirement for solving checkers is that a sound method is used. So no Chinook has in no way solved checkers.

Another aspect is that they don't have all the reachable nodes in their proof tree so if Chinook was to play a game there would be positions after the opening and before they reach the endgame databases where they would have to use a regular search. Therefore it is very likely they would lose a game.

[Alex_Moiseyev]

Privet, Ed ! In 2007 after Chinook team claimed "solving checkers", New York Times correspondent called me at home and asked few questions. I can repeat now small portions of my answers

Chinook can at least draw

True for GAYP

and will always win once an opponent makes a losing move.

Not true. This is not a part of scientific proof. Chinook team only claimed that program never makes a losing move in GAYP games. This is the lowest level of solving checkers.

[Ed Gilbert]

I'm not sure I would call this an opening book, since it is much more than that.

Well it's mostly semantics, and I put "opening book" in quotes, but it sure sounds like an opening book to me. An opening book is generally a database where you lookup a position from the front half of the game, and it gives you the best move or moves to play in that position, and possibly some other attributes. That's how kingsrow's book works, and that seems to be how the Schaeffer GAYP checkers solution works.

I believe Ed Gilbert and Martin Fierz enjoyed turning off their books and endgame databases to basically have an "evaluation function only match."

We used to run engine matches all the time with books off, but still using 8-piece endgame dbs. Usually pretty fast time controls, like 1 or 2 seconds per move. We've both run hundreds of these matches. One pass over all the 3-move ballots was a few hundred games. I now know that that is not nearly enough games to make decisions about the effectiveness of code changes, and I have changed to using thousands of games at much shorter time controls.

With books on, almost all the games are draws, and you can't learn anything.

-- Ed