Checkers Is Strongly-Solved for 8-pieces

[Ed Trice]

Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.

Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hard-pressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 60-80 moves before making a single trade. Ed Gilbert stored conversion data while he had storage capacity. And, as I mentioned already, conversion databases work best with a plethora of kings.

How long do you have to search before you find a winning pawn move? That's all that's needed here.

Me? I have the result in RAM, so a beam of light travels about 5 inches and I have my result.

Them? The sun would run out of Hydrogen in the time it would take to find the definitive move leading to a win in a complex bridge ending in checkers.

[Sven]

Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.

Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hard-pressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 60-80 moves before making a single trade. Ed Gilbert stored conversion data while he had storage capacity. And, as I mentioned already, conversion databases work best with a plethora of kings.

That's just fine for a strong solution.

So in chess, if a program can't find a mate in 2 but instead promotes a pawn to a queen and spends 29 moves running down the enemy King, you would say that is a strong solution?

Sorry, I disagree.

If a solution cannot outperform a human amateur, it's not "strong" in any sense of the word.

IMO, any win is equal in value.
And any draw is equal in value.
And any loss is equal in value.

A shorter win is only prettier.

A proven win in 100 moves is a win.
A proven win in 1 move is a win.
Neither is superior from a game theoretic standpoint, as far as I can see.

This is one opinion. There are several opinions about it. My point is: the literature mostly ignores that "perfect play" for a legal position that is not a game-theoretical draw should require to provide the shortest path to win resp. the longest path to lose.

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win on the board - unless there are other limitations like 50-moves rule or threefold repetition. So for chess, for instance, I could accept a DTZ50 endgame tablebase as a valid tool for "perfect play" for the subset of endgame positions it covers. But in case of checkers I doubt that the 50-moves rule (or 40-moves rule - seems to be unclear which one is used?) is currently considered in any existing EGT. In any case, not playing the shortest win can't be called "perfect play" if it involves the risk of never winning the game at all.

A similar point applies to lost positions, here in conjunction with limiting rules like the 50-moves rule: if you have two choices which both lose the game but you always choose the quicker loss then you may miss the opportunity to draw by postponing the loss long enough so that the 50-moves rule will apply.

For these reasons I can't accept statements that pretend that "perfect play" has a consistent definition in literature. It simply hasn't. Even "strongly solved" is defined differently, sometimes the definition involves to always provide the "best move", without mentioning the "distance to win" aspect.

[Ed Trice]

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win...

A similar point applies to lost positions, here in conjunction with limiting rules like the 50-moves rule: if you have two choices which both lose the game but you always choose the quicker loss then you may miss the opportunity to draw by postponing the loss long enough so that the 50-moves rule will apply.

Thank you for demonstrating that you have no idea what you are talking about. Now I don't have to reply to any more of your posts.

With Perfect Play databases, you do the exact opposite of what you mentioned, nullifying whatever points you were trying to make in that pontification of noisey diatribe above.

When in a winning position, you pick the move leading to the quickest loss for the opponent, thereby winning most quickly.

When in a losing position, you pick the move leading to the longest win for the opponent, thereby losing most slowly.

The program announces the distance remaining along the way. Its play is perfect and irrefutable.

[Krzysztof Grzelak]

Hi Ed.

Be where you can download the database 8-pieces.

Krzysztof Grzelak.

[Sven]

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win...

A similar point applies to lost positions, here in conjunction with limiting rules like the 50-moves rule: if you have two choices which both lose the game but you always choose the quicker loss then you may miss the opportunity to draw by postponing the loss long enough so that the 50-moves rule will apply.

Thank you for demonstrating that you have no idea what you are talking about. Now I don't have to reply to any more of your posts.

With Perfect Play databases, you do the exact opposite of what you mentioned, nullifying whatever points you were trying to make in that pontification of noisey diatribe above.

When in a winning position, you pick the move leading to the quickest loss for the opponent, thereby winning most quickly.

When in a losing position, you pick the move leading to the longest win for the opponent, thereby losing most slowly.

The program announces the distance remaining along the way. Its play is perfect and irrefutable.

Ed, I absolutely agree but I don't see where I wrote something different than you? Would you mind to read my post once again? I am *very* sure that you misunderstood my point, completely. The point was: using WDL only, instead of DTM, can lead to infinite winning attempts (in a won position), or to missing a 50-moves draw (in a lost position that needs more than 50 moves for the opponent to win).

I think we both have a similar position in this topic, so it is not necessary to be aggressive (and you can be sure that I know how DTM works).

[Rein Halbersma]

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win...

A similar point applies to lost positions, here in conjunction with limiting rules like the 50-moves rule: if you have two choices which both lose the game but you always choose the quicker loss then you may miss the opportunity to draw by postponing the loss long enough so that the 50-moves rule will apply.

Thank you for demonstrating that you have no idea what you are talking about. Now I don't have to reply to any more of your posts.

With Perfect Play databases, you do the exact opposite of what you mentioned, nullifying whatever points you were trying to make in that pontification of noisey diatribe above.

When in a winning position, you pick the move leading to the quickest loss for the opponent, thereby winning most quickly.

When in a losing position, you pick the move leading to the longest win for the opponent, thereby losing most slowly.

The program announces the distance remaining along the way. Its play is perfect and irrefutable.

Alright, so 8 piece DTM checkers databases could have been generated 20 years ago. They weren't. You did it now. Congrats. Attaboy. Let's call "Perfect Play" also UltraStronglySolvedBeyondAnyReasonableDoubtForEternity. Are there any additional insights that are relevant for other db builders?

[syzygy]

This is one opinion. There are several opinions about it. My point is: the literature mostly ignores that "perfect play" for a legal position that is not a game-theoretical draw should require to provide the shortest path to win resp. the longest path to lose.

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win on the board - unless there are other limitations like 50-moves rule or threefold repetition.

The literature asks for a winning strategy. A strategy that fails to make progress towards a win is clearly not a winning strategy. But there is no need to require the winning strategy to be DTM-optimal.

So for chess, for instance, I could accept a DTZ50 endgame tablebase as a valid tool for "perfect play" for the subset of endgame positions it covers. But in case of checkers I doubt that the 50-moves rule (or 40-moves rule - seems to be unclear which one is used?) is currently considered in any existing EGT. In any case, not playing the shortest win can't be called "perfect play" if it involves the risk of never winning the game at all.

I also doubt that endgame databases for checkers take into account such 50-move rule-like drawing rules. So strictly speaking they are endgame databases for the game of checkers without that rule. And as long as they contain sufficient information to guarantee progress (which the MTC data seems to do), they give a winning strategy for that game.

For these reasons I can't accept statements that pretend that "perfect play" has a consistent definition in literature. It simply hasn't. Even "strongly solved" is defined differently, sometimes the definition involves to always provide the "best move", without mentioning the "distance to win" aspect.

You will have to agree on the game: chess with 50-move rule or chess without 50-move rule. They are two different games. Same for checkers. Change the game and you change what strategies give "perfect play".

The concept of a game being "strongly solved" has a perfectly clear and commonly accepted definition. You just have to be aware of what exactly is the game that is solved.

[syzygy]

The point was: using WDL only, instead of DTM, can lead to infinite winning attempts (in a won position), or to missing a 50-moves draw (in a lost position that needs more than 50 moves for the opponent to win).

Do you realise that using DTM will mess up perfectly fine wins in "chess including the 50-move rule"?

DTM gives a winning strategy / perfect play for chess without 50-move rule.
Idem for DTC and DTZ.

DTZ50 gives a winning strategy / perfect play for chess with 50-move rule.
DTM50 (which is a far more complicated metric than I want to explain in this thread and requires considerably more storage space than DTM) gives a winning strategy / perfect play for chess with 50-move rule.

DTZ50+ (implemented by my tablebases) gives a winning strategy / perfect play both for chess with 50-move rule and for chess without 50-move rule.

[Ed Trice]

Alright, so 8 piece DTM checkers databases could have been generated 20 years ago. They weren't.....

Are there any additional insights that are relevant for other db builders?

There are only two researchers on planet earth who ever successfully completed DTW databases for the game of checkers: Gil Dodgen and Ed Trice.

My friend and colleague died in 2016. I promised him "one day" I would solve the 8-piece set after we both did the 4x3 part of the 7-piece database.

I've done Distance To Win endgames for chess (The Sniper, 1987), Gothic Chess (my 80-square variant with Archbishop and Chancellor pieces, 2004), and checkers (2001, 2017). In my opinion, the checkers algorithm is the one requiring the most brain power. It's hard to prevent an "infinite loop" in checkers DTW for reasons I will not elaborate here. Suffice it to say the iteration on which a win or loss is first realized RARELY matches the final Distance To Win number.

Furthermore, since the 8-piece exceeds the DTW distance for a single byte, unless you use operator-overloading for making functional 9-bit or 10-bit bytes, then you need two bytes per position in RAM. When you include the promotion slices and jump sub-databases, even loading and unloading them to minimize the RAM, you still need a 128 GB system, unless you want to grind your hard drive into pulp and magnify the time taken to solve it by a few thousand.

So, yeah, 20 years ago? Yeah right.

And, in the paper I published in 2003, I corrected Published Play going back to 1756. A common endgame called "4th Position" had been played sub-optimally since before the United States was even a country. And guess who corrected the well-known endgame? Me.

No checkers world champions, nor the legendary Marion Tinsley, could conceive of the sharp solution offered by the Perfect Play databases. The closest equivalent in chess I could think of is the Lucena Position.

So now, with the 8-piece, I can rewrite most of the book Boland's Bridges if I want to. By the way, do you have any published play corrections of your own? Or is it just me?

[Ed Trice]

Ed, I absolutely agree but I don't see where I wrote something different than you? Would you mind to read my post once again? I am *very* sure that you misunderstood my point, completely.

If so, then I apologize.

I did read and re-read it, and it still sounds like you're indicating my databases could misplay a win and have the game go on forever, and also misplay a swindle attempt whereby the losing side tries hard for a draw.

This is not the case, of course.