More 3-move openings solved by Schaeffer

[Ingo_Zachos]

Chinook has not played any serious game for years, and I wonder if Dr. Schaeffer worked on the code in that time at all.
So most likely other programs r stronger now then Chinook.
And even at the time Chinook was at its peak, other programs defeated it, so it was not even the stongest then.

...
BTW, I'm a chess snob and don't play checkers myself.

...

Ja, ich bin auch schachverr

[EdTrice]

Ed, By the way I have WCC Plat. and when it came out I think it was the best at that time. Your copy of WCC that you have continued improving maybe as good as cake & kingsrow, you are probably the only one who knows. The last time I talked to Gil he told me he would not work on WCC again. I still use WCC along with cake & kingsrow to analyze positions, but nemisis is to slow for me.

Gene Lindsay

Based on new information from Ed Gilbert, I would have to say Kingsrow is better than WCC overall. But remember, when WCC was first playing checkers in tournaments (as "Checkers Experimental") it was getting about 5,000 nodes per second and rarely completing an 11-ply search! Recall also that Gil's 1990 version of the program had no databases and the 1992 version had a 4-piece perfect play database. That's it!

So, the type of knowledge it employed "bridged the gap". It had to get into strong positions since it did not have the ability to search very deeply. This type of "knowledge" is no longer needed. Deeper searches uncover what WCC tries to do intelligently.

By the way, Gil's checkers program did play a 4-game match against Marion Tinsley in 1992. It had 3 draws, and lost the 4th game. Marion lead it into an 8-piece loss. Current analysis shows the 4x4 ending had only one move to win for 3 moves in a row, and Marion made them correctly each time. So clearly Marion had his own 8-piece database in his head.

As I look over the WCC code, I see part of the evaluation function written by Gil, and part written by me. I just spoke with Gil tonight on the phone. It's funny how much we both forget! The best thing to do now is just re-write another program from scratch. I already started this, and I am calling it Only Perfect Checkers.

I decided to completely redo the database format for OPC. WCC Platinum has a run-time probed database of win-loss-draw positions, just like everyone else, and a perfect-play database, which is only read off of the disk. The perfect play database announce "Win in 253", but only once you entered that position. The run-time database is what is actually used as the program searches.

Well, I decided to combine the two into one database, PLUS add information about how hard it is for a draw to be achieved. Here is how the one king vs. one king database would look:

http://www.gothicchess.com/checkers/1K0C_1K0C.txt

That is all 992 positions drawn as a text file, so don't click it unless you have an internet connection that is fast.

But if you can look at it, you can see the "theoretical value" of a position (win loss draw) is also close to the "qualitative values" -- how many moves would the win/loss require, and how hard is it to draw the position?

The problem is, this takes up a great deal of RAM. The good news is, a distance to win up to and including 511 plies can be stored using only 1 byte.

OPC will be the smartest dumb program out there. By that I mean it will probe perfect-play databases in RAM, making it very intelligent. It will have no other terms in its evaluation function, making it extremely dumb.

While currently technology does not exist to make this the best program in the world (the databases are too far away to effect the play in the opening of the game, and programs are too slow to search that far ahead), at one point in time, this will no longer be the case.

OPC will not seek to enter a position because it can inflict a deadly cramping formation, nor will it be able to win a complex ending due to strangling the mobility of your kings. It will have NO knowledge of such things.

It will enter won positions because they are going to be impossible to avoid, and it will announce the distance to the end of the game as it gets ever closer. If the position is a draw, it will place the opponent in a position with the fewest chances to retain the draw, move after move after move.

In 2006, this won't achieve much. In 2010, when the 10-piece perfect play database will be finished, computers will be faster, and this will make a big difference. In 2020, with 512 Terabytes of RAM and lightning fast processors, it will finally be as close to "perfect" as possible, with play that will be better than any hand-crafted evaluation function.

[EdTrice]

Chinook has not played any serious game for years, and I wonder if Dr. Schaeffer worked on the code in that time at all.
So most likely other programs r stronger now then Chinook.
And even at the time Chinook was at its peak, other programs defeated it, so it was not even the stongest then.

I can answer this. The Chinook databases were regenerated, twice. With its new compression technique, they are about 30% of the size of the original databases. That is, they are almost 4 times as small.

As Ed Gilbert alluded to, the Chinook team has solved the Graph History Interaction problem. While this is Greek to most people, basically, they figured out a way to prove a draw is a draw, with no dependencies on the "path" to the draw.

Just imagine your program is searching a king move, 1-5. Then, next ply, it moves back, 5-1. Next ply, it will generate the move 1-5, and so on. Technically speaking, one of the 20-ply nodes it is examining could contain 1-5 5-1 1-5 5-1... and this is not making any form of progress! Programmers have to keep such meaningless repetition moves out of the game tree, so as they crop up, they are entered as "draws" into the hash table, then the search retreats to fetch another move to examine.

The problem is, some other elements may produce the identical position further down the road, when the see-saw moves were not made to flag it as a repetition candidate. It might be that the opponent plays some move like 23-19 before the 1-5 5-1 1-5 moves occur, but later on, a move such as 15-19 might create the identical position, and there were no see saw moves 1-5 5-1... so the position needs evaluation.

While the chance is very slim that such a position would overthrow the searched value at the root of the tree, solving this problem was a tremendous undertaking, and a necessary one if you are going to "solve checkers."

The Chinook databases, coupled with its RAM-based tree solver, make it an invincible opponent. Its evaluation function no longer matters. It has enough data to probe to always win from a won position, never lose a drawn position, and never enter a lost position, provided you start from any balloted position. It is extending this to be able to PROOVE this, not just demonstrate its play.

I played the last 2 games ever against Chinook. We played two 11-man ballot games, with Chinook probing its 10-piece databases. I made things interesting by going a piece down one game to play for complications, but it never waivered from its analysis: draw.

You can say what you want about "old Chinook", but it no longer applies.

[Martin Fierz]

The problem with Chinook is that it has retained its name throughout - while evolving very significantly. The first versions of Chinook were good, but nowhere near the best humans (I'll call this "Early Chinook"). Then came 8-piece databases and Martin Bryant's Colossus opening book, and some hard work on the engine - and Chinook was very very strong. This is the Chinook that played the second match against Tinsley and then against Lafferty, and made its last showing in a US national, and then was retired, and this is also the Chinook that checker players remember ("Mature Chinook"). Later, without ever playing again officially, the 10-piece database was computed and now we have "Super Chinook". Of course, each of these 3 versions of Chinook also existed in minor versions.

So when somebody writes "Chinook is the best" this is a fuzzy statement which could either be totally false or possibly true. One has to specify which version of Chinook one is talking about.

I believe (and I have data to back this up, but not well organized) that "Mature Chinook" was clearly weaker than the best PC programs today (like Cake). Part of this (but not all) is simply due to the fact that PCs today are much faster than the hardware that was available to Mature Chinook.

I have no idea what "Super Chinook" can do - but of course it would be very strong. I also don't really know how much difference it makes if you take Super Chinook or KingsRow 10 instead of Cake or KingsRow 8. I suppose a match would end in a zillion draws anyway, but of course, for arbitrary positions the 10pc programs would be better.

Anyway, whoever wants to make a statement about Chinook should also add which version is being talked about! I generally also believe that KingsRow-10 is on the same level as Super Chinook.

cheers
Martin

[Ed Gilbert]

I have no idea what "Super Chinook" can do - but of course it would be very strong. I also don't really know how much difference it makes if you take Super Chinook or KingsRow 10 instead of Cake or KingsRow 8. I suppose a match would end in a zillion draws anyway, but of course, for arbitrary positions the 10pc programs would be better.

I think that if you played a match of all 156 drawn ballots between super chinook and either cake or kingsrow/8, super chinook would lose some games and lose the match. The main reason I think that is that chinook only has a really good opening book on 6 openings. For the remaining 150, it has Martin Bryant's book. This may have been a good book for the mid 90's, but it has none of the many corrections to pp that have been found since that time. It must have very little play on the 12 mail-play ballots, and IIRC the total number of positions in this book is small by today's standards -- less than 1/10th the number in the kingsrow or cake books. You may think that a program with a 10pc db does not need an opening book, but I can assure you that it certainly does. The 10pc db provides little help for positions very early in the game with 20+ pieces still on the board.

The Chinook databases, coupled with its RAM-based tree solver, make it an invincible opponent. Its evaluation function no longer matters. It has enough data to probe to always win from a won position, never lose a drawn position, and never enter a lost position, provided you start from any balloted position.

The new chinook 'opening books' cannot always win from a won position. It can always attain at least a draw, but it does not have information on all positions reachable from a ballot's start position.

-- Ed

[mday]

How about we talk about the ability of the greatest players of in history instead of the ability of programs? Programs are getting too much attention!

[Lindus Edwards]

I see no harm in "talking" about checker programs. There is only one thing in the world worse than talking about checker programs and that is not talking about them

[EdTrice]

The new chinook 'opening books' cannot always win from a won position. It can always attain at least a draw, but it does not have information on all positions reachable from a ballot's start position.

Chinook's tree solver has created a permanent middlegame database on disk which can be loaded into RAM. This is like having mini-slices of the 18-piece, 16-piece, 14-piece, and 12-piece databases! All of the positions relevant to the search have been written out to disk.

Don't forget, Chinook is a parallel searching program that can run on supercomputers. The search speed gains are directly proportional to the square root of the number of processors. So, a 4-processor box will be twice as fast as 1-processor Chinook. Schaeffer had a 16-processor box on loan once, so if he could get access to a 16-processor box with today's speed, it would be 4 times as fast as the 1-processor version.

I think it's safe to say that 2,000,000 nodes per second is about the search speed of a 1-processor program on today's hardware. So a hypothetical Chinook would be able to generate 8,000,000 nodes per second.

Coupled with its 10-piece databases and middlegame databases, I don't think it will lose any ballots, previously barred or otherwise, book or no book.

All conjecture of course. Just understand the technologies the new Chinook will bring to the table!

[EdTrice]

The problem with Chinook is that it has retained its name throughout - while evolving very significantly. The first versions of Chinook were good, but nowhere near the best humans (I'll call this "Early Chinook"). Then came 8-piece databases and Martin Bryant's Colossus opening book, and some hard work on the engine - and Chinook was very very strong. This is the Chinook that played the second match against Tinsley and then against Lafferty, and made its last showing in a US national, and then was retired, and this is also the Chinook that checker players remember ("Mature Chinook"). Later, without ever playing again officially, the 10-piece database was computed and now we have "Super Chinook". Of course, each of these 3 versions of Chinook also existed in minor versions.

I agree 100% that Chinook should have demarcated its versions somehow. In fact, I asked Dr. Schaeffer to start referring to Chinook in subsequent papers as Chinook II so that people cannot make statements like: "I beat Chinook".

(Which I can say, I beat it 3 times, on the web. Way back in 1996....)