CHECKERS SOLVED??? - DEGREES OF SOLVABILITY

[liam stephens]

Whether the game is solved or not appears to be a moot point.
(see the discussions in the previous topic)
Among the many learned theses produced on the subject there are references to: “ ultra weakly solved”, “weakly solved” " strongly solved" etc.
Forgive the layman for asking what does all this mean ?
Putting it bluntly, if the Fortress positions by Dr. Brown and others cannot be solved, then surely the game of checkers remains unsolved.

This sort of nonsense strongly reminds me of an old rhetorical question:
When is a man not a man ?
One said when the heavens are quakers, a second said when Bohemiand lips, a third said when he, no when hold hard a jiffy, when he is a gnawstick and determined to, the next one said when the angel of death kicks the bucket of life, still another said when the wine’s at witsend and still another when lovely wooman stoops to conk him, still one said when you are old I’m grey fall full wi sleep, and still another when wee deader walkner, another when yea, he hath no mananas, and one when dose pigs they begin now that they will flies up intil the looft.
All were wrong, so Shem himself, the doctator, took the cake, the correct solution being – all give it up ? –;
when he is a – yours till the rending of the rocks, - Sham.

“ Shem was a sham and a low sham ……………………………………….”

From : Tales told of Shem and Shaun.

[Ed Trice]

Whether the game is solved or not appears to be a moot point.
(see the discussions in the previous topic)
Among the many learned theses produced on the subject there are references to: “ ultra weakly solved”, “weakly solved” " strongly solved" etc.
Forgive the layman for asking what does all this mean ?
Putting it bluntly, if the Fortress positions by Dr. Brown and others cannot be solved, then surely the game of checkers remains unsolved.

I am a subject matter expert on Strong Solutions. I collaborated with the late Gil Dodgen on the 7-piece perfect play databases, where we identified one 7-piece ending that required 253 ply (a number which counts moves for both sides) as the longest win among all 4x3 endings. I have since taken up the task of strongly solving all 8- and 9-piece positions. At present, I have the code, but not the disk space, to strongly solve the 10-piece database.

This is the longest win in checkers known so far. White to move wins in 291 ply.


The first move for white, and the follow-up by red, are both easy to see, but my supposition is that the rest of this ending will confound every human and program on planet earth.

[megamau]

Dear Liam,

It's actually quite simple. Checkers is solved in the sense that:

If you play GAYP against Chinook, you will NEVER win, and you may lose. The same is true if the opponent of Chinook is Michele Borghetti, Kingsrow or anybody/anything else.

The fortress position will not be relevant, because Chinook will not enter in that variation.

If you want a program that plays perfectly in ANY position that you can setup, that is at the moment only available for maximum 10 pieces on the board.

[MostFamousDane]

Dear Liam,

It's actually quite simple. Checkers is solved in the sense that:

If you play GAYP against Chinook, you will NEVER win, and you may lose. The same is true if the opponent of Chinook is Michele Borghetti, Kingsrow or anybody/anything else.

Assuming that all of the proof tree is correct Chinook could still lose if the timer is less than 2 minutes per move.

The fortress position will not be relevant, because Chinook will not enter in that variation.

Fortress positions is an illustration of why you can't reliably do futility pruning. Is your assertion that they didn't do any futility pruning despite saying that on their home page ?

[megamau]

Assuming that all of the proof tree is correct Chinook could still lose if the timer is less than 2 minutes per move.

Sure. Or if the hard disk breaks or if electricity blacks out, or if the human operator makes a mistake.
But we usually don't take into consideration "abnormal" conditions. Also, two minutes of computer time of seven years ago are probably 30-40 seconds at most with today hardware.

Fortress positions is an illustration of why you can't reliably do futility pruning. Is your assertion that they didn't do any futility pruning despite saying that on their home page ?

In the scientific paper (which is the most reliable document) there is no mention of futility pruning.
Moreover, using futility pruning in the #proof manager# does not invalidate the solution as long as the solver (proof number search) does not use it.
In the example of the fortress (assuming Chinook could have reached a similar position during the solution) the proof manager would suggest a particular move, but the solver would not be able to prove it rigorously, and they would eventually change move. It would be a loss of time, but not invalidate the solution.

[Ed Trice]

If you want a program that plays perfectly in ANY position that you can setup, that is at the moment only available for maximum 10 pieces on the board.

This is not true.

I published a paper in 2003 and showed that without "Perfect Play Databases," it is possible for a program to be in a winning position (which was 4 vs. 3) and not be able to win it.

https://www.semanticscholar.org/paper/T ... 1077f37a30

Kingsrow and Wyllie were two programs with 7-piece "win-loss-draw" databases, and neither could win from the winning side of the position that required 253-ply to win.
My database was able to hold them to a draw by having them cycle forever and never converge on the win.

When playing the winning side against the programs, my database won more quickly than 253 moves, since each of the other programs did not play "perfectly."

At present, only 1 program plays perfectly with 7 pieces or fewer: WCC Platinum III.

I am working on extending that to 8- and 9-pieces.

It should be noted that since this time, Kingsrow has added "Move to Conversion" databases to its program, which helps avoid this situation. I am in the process of running an experiment where "Perfect Play meets Conversion," and this will be the subject of a new paper.

[Krzysztof Grzelak]

You also need to honestly write that at one time the base had an error.

[MostFamousDane]

Assuming that all of the proof tree is correct Chinook could still lose if the timer is less than 2 minutes per move.

Sure. Or if the hard disk breaks or if electricity blacks out, or if the human operator makes a mistake.
But we usually don't take into consideration "abnormal" conditions. Also, two minutes of computer time of seven years ago are probably 30-40 seconds at most with today hardware.

Being able to make a move within the required time limit is the normal condition - there is nothing abnormal about it. You are going to have to explain to me how a time limit is abnormal I just don't understand your thinking. Also are you reading that as though it is uniformly 2 minutes - I read that as average as in sometimes it takes 10 seconds some times an hour but I'm not sure either way my point still stands.

Fortress positions is an illustration of why you can't reliably do futility pruning. Is your assertion that they didn't do any futility pruning despite saying that on their home page ?

In the scientific paper (which is the most reliable document) there is no mention of futility pruning.

There is also no mention of their solution being sound - they mention something about the graph history interaction problem and simply say that errors in evaluation of nodes is unlikely to propagate to the root. That argument only holds if you are only trying to obtain the game theoretic value of the start position not build a program that never loses.

Moreover, using futility pruning in the #proof manager# does not invalidate the solution as long as the solver (proof number search) does not use it.


In the example of the fortress (assuming Chinook could have reached a similar position during the solution) the proof manager would suggest a particular move, but the solver would not be able to prove it rigorously, and they would eventually change move. It would be a loss of time, but not invalidate the solution.

Yes I get that they can use all the heuristics they want to select the nodes in the tree as long as the leaf nodes are evaluated correctly. I don't know too much about proof number search but I understand that the algorithm is heuristically in nature and that thresholds are build into the algorithm (ie pruning) but maybe you can enlighten me ?

Also it still uses a transposition table so using a hash function with collisions (like zobrist keys) can still produce wrong evaluations. They claim to have done millions of searches hundreds of moves long. This indicates to me that these thresholds are set quite high (or low whatever prunes most).

[Krzysztof Grzelak]

Mr. Ed please add sound while performing movements in the program. I have to admit that during the preparations for the tournament, tested the program in the full version and made me a very good impression.

Krzysztof

[liam stephens]

Thank you gentlemen for all your words of wisdom.
I have reached the following conclusions.

1. The experts cannot agree on the topic.
2. The title I used “Degrees of Solvability” is an accurate one.
3. The claim of " solved" is Incomplete ( does not cover every possible position).


Reminds me of another old question:
What is a home without Plumtree’s Potted Meat?
Incomplete.
With it an abode of bliss.
(An advertisment in the Freeman’s Journal)

[Ed Trice]

You also need to honestly write that at one time the base had an error.

You need to pay more attention to the important details.

Kingsrow was using its own database in 2003 when we played the match. Its databases were correct.

At the 2002 checkers championship event in Vegas, Kingsrow used the chinook databases, which were corrected, because on December 6, 2001, Gil Dodgen and I helped correct the Chinook databases. This is well-documented in Schaeffer's follow-up book, One Jump Ahead: Computer Perfection At Checkers.

What was erroneous: The Chinook indexing function used to probe the databases. Gil discovered that one subset of its calculations for an index used a data type that was overflowed, such as a 16-bit variable where a 32-bit variable was needed, or more likely, a "signed 32-bit variable" which is functionally a 31-bit variable in the positive range, and a 32-bit variable in the positive range was needed. In the case where certain positions were being probed, the indexing function sent Kingsrow looking in the wrong location. Therefore, it misplayed an ending that led to a loss where otherwise a draw was possible.

I think the Chinook team did not update their website immediately after being notified of the problem. Once it was discovered, Gil asked me to write all of the indexing functions for WCC from scratch, "just in case." So I spent some time hand-crafting indexing functions that would always "count" from 1 to the number of positions in a particular arrangement (like 2 kings + 2 checkers vs. 3 kings + 1 checker). The index would always increment by 1, it would never produce the same number twice, and it would generate every number in the range from 1,2,3.....whatever the last position was.

In short: Kingsrow and Wyllie both could not win the longest win in the 7-piece database NOT because of any erroneous database errors, but because their searches were too shallow (even though Kingsrow could reach depth 30) to see all the way to the end of the game and select the winning path.

You can verify this for yourself. Set up the longest 7-piece win, and see if your own computer program can win it without using WCC Platinum III or any Move To Conversion databases.

As far as I know, there is still no human or computer on planet earth that can win that position against the most accurate defense.

[megamau]

Being able to make a move within the required time limit is the normal condition - there is nothing abnormal about it. You are going to have to explain to me how a time limit is abnormal I just don't understand your thinking. Also are you reading that as though it is uniformly 2 minutes - I read that as average as in sometimes it takes 10 seconds some times an hour but I'm not sure either way my point still stands.

I just mean that the standard time allowed in high level checkers (24 moves per hour) will be more than enough to use the solvers, and it would be abnormal to set a time limit that does not allow the solver to finish its job.
That is 2.5 minutes per move per player. If you consider that:

- All the moves from the stored proof-tree can be played immediately, and there are on average 50/60 moves stored in the proof tree
- All the moves in the database can be played immediately
- The computer can think during the opponent time (pondering)
- The time for the solver becomes less and less as we approach the endgame database
- The estimate of 2 minutes is using 2007 hardware

It is clear than the program would have no issues to show the solutions within "normal" time limits.

There is also no mention of their solution being sound - they mention something about the graph history interaction problem and simply say that errors in evaluation of nodes is unlikely to propagate to the root. That argument only holds if you are only trying to obtain the game theoretic value of the start position not build a program that never loses.

They *PROVE* that the opening position is a draw. In science this has a clear meaning, and means that the solution has to be sound.
Proving that the starting position has a game theoretic value of a draw and building a program that never loses from that starting position is the same thing. They even explain it in the article on the second page as the goal
******If checkers were a proven draw, then a “perfect” CHINOOK would never lose******.

Yes I get that they can use all the heuristics they want to select the nodes in the tree as long as the leaf nodes are evaluated correctly. I don't know too much about proof number search but I understand that the algorithm is heuristically in nature and that thresholds are build into the algorithm (ie pruning) but maybe you can enlighten me ?
Also it still uses a transposition table so using a hash function with collisions (like zobrist keys) can still produce wrong evaluations. They claim to have done millions of searches hundreds of moves long. This indicates to me that these thresholds are set quite high (or low whatever prunes most).

Proof number search does not "prune" anything, unless it has already proved the node. It is not heuristic, it's goal is to *PROVE* something.
Of course once you prove that an opponent move leads to a loss for you, you can prune all other opponent moves, but this does not change the correctness. If you see a black sheep you can concluded that "not all the sheep are white" without analyzing every single sheep.
In my knowledge proof number search also has no hash function, because it stores the whole tree (with related proof numbers) in memory.
I don't have the code of the Chinook implementation, but I would be surprised if they have used an "unsound" algorithm for a "proof" paper.

This is not true.
I published a paper in 2003 and showed that without "Perfect Play Databases," it is possible for a program to be in a winning position (which was 4 vs. 3) and not be able to win it.
https://www.semanticscholar.org/paper/T ... 1077f37a30
Kingsrow and Wyllie were two programs with 7-piece "win-loss-draw" databases, and neither could win from the winning side of the position that required 253-ply to win.
My database was able to hold them to a draw by having them cycle forever and never converge on the win.

The issue that you highlight is that WLD (Win-Loss-Draw) databases are sometimes not able to win because they do not progress in won positions, instead cycling forever over other won position.
This is exactly the "Graph History Interaction" (GHI) problem; the program eventually gets a draw by repetition instead of a win. This problem is claimed to have been solved by Kishimoto and Mueller in their 2004 paper.
Although I have not yet read the actual paper, I tend to believe that they would not claim something false.

A simple fix to GHI in the databases is to have different tables:
- DTC (distance to conversion) tables always win (although not in the fastest way)
- DTM (distance to mate, a name which derives from chess) tables always win in the shortest possible way. I understand you call these PPL in your program.

[Krzysztof Grzelak]

As far as I know, there is still no human or computer on planet earth that can win that position against the most accurate defense.

Please write and present this position.

[MostFamousDane]

Being able to make a move within the required time limit is the normal condition - there is nothing abnormal about it. You are going to have to explain to me how a time limit is abnormal I just don't understand your thinking. Also are you reading that as though it is uniformly 2 minutes - I read that as average as in sometimes it takes 10 seconds some times an hour but I'm not sure either way my point still stands.

I just mean that the standard time allowed in high level checkers (24 moves per hour) will be more than enough to use the solvers, and it would be abnormal to set a time limit that does not allow the solver to finish its job.
That is 2.5 minutes per move per player. If you consider that:

- All the moves from the stored proof-tree can be played immediately, and there are on average 50/60 moves stored in the proof tree
- All the moves in the database can be played immediately
- The computer can think during the opponent time (pondering)
- The time for the solver becomes less and less as we approach the endgame database
- The estimate of 2 minutes is using 2007 hardware

It is clear than the program would have no issues to show the solutions within "normal" time limits.

OK I disagree but I understand your position - to my knowledge Chinook has not demonstrated this ability in practice - your guess is as good as my guess.

Proof number search does not "prune" anything, unless it has already proved the node. It is not heuristic, it's goal is to *PROVE* something.

I invite you to read this article https://dke.maastrichtuniversity.nl/m.w ... hapter.pdf and search for the word heuristic.

In my knowledge proof number search also has no hash function, because it stores the whole tree (with related proof numbers) in memory.
I don't have the code of the Chinook implementation, but I would be surprised if they have used an "unsound" algorithm for a "proof" paper.

Again I invite you to do a search for transposition table in the above article. Also search for the word threshold I might have misunderstood it but it seems to me that this is futility pruning.

[Ed Trice]

Please write and present this position.

The way to go about this is to have WCC Platinum III take the losing side while somebody plays the winning side.

It should be noted: This position is NOT creating a "GHI problem," as someone else mentioned.

The reason why computers cannot win this is because it requires a 67-ply search to see through all of the complications leading to the win.

I documented this in the appendix of the paper I published, showing ways in which both Wyllie and "Kingsrow 2003" could have proceeded (and won) from the positions they created.