Checkers Is Strongly-Solved for 8-pieces

[Ed Trice]

This morning my endgame database solver finished the last of the positions featuring "4 against 4" in the game of checkers.



The longest win requires 293-ply.

I've completed all of the 7-piece endings, including 5 vs. 2 and 6 vs. 1.

The entire calculation took from January 10 to February 12 one a single core of my 128 GB Intel i7-5960X Overclocked to 4.6 GHz. The process used a "forward move generator" only, examining every position of every arrangement on each pass. There is a much faster technique involving "reverse move generation" for most of the iterations, but I was a bit lazy and decided to let the hardware do most of the work

I'll need more solid state drives to do the 5x3, 6x2, and 7x1 sets, but all of the code is written and ready to go.

[Gerd Isenberg]

Excuse my ignorance. I thought Chinook had already 9 piece checkers databases in 2004? Doesn't that imply they already strongly soved 9x9 checkers then?

https://web.archive.org/web/20040930164 ... /~chinook/

We began the effort to solve checkers in 1989 with the construction of the 4-piece checkers endgame database (7.3 million positions). Today we have the complete 9-piece databases and the 5-piece versus 5-piece subset of the 10-piece database (13 trillion positions). These computations took a "backwards" approach, starting at the end of the game and moving towards the start of the game. We also used a forward search, which began computing at the start of the game, searching until an endgame database position is encountered.

[Sven]

Excuse my ignorance. I thought Chinook had already 9 piece checkers databases in 2004? Doesn't that imply they already strongly soved 9x9 checkers then?

https://web.archive.org/web/20040930164 ... /~chinook/

We began the effort to solve checkers in 1989 with the construction of the 4-piece checkers endgame database (7.3 million positions). Today we have the complete 9-piece databases and the 5-piece versus 5-piece subset of the 10-piece database (13 trillion positions). These computations took a "backwards" approach, starting at the end of the game and moving towards the start of the game. We also used a forward search, which began computing at the start of the game, searching until an endgame database position is encountered.

www.talkchess.com/forum/viewtopic.php?t=62550

The difference is that Ed computes DTM which Chinook didn't do.

[WinPooh]

If I recall correctly, Chinook could only play perfectly from the initial position. In other words, it stores main PV and all refutations for non-PV moves from his opponent. This requires much less storage than complete game tree.

[AlvaroBegue]

Excuse my ignorance. I thought Chinook had already 9 piece checkers databases in 2004? Doesn't that imply they already strongly soved 9x9 checkers then?

https://web.archive.org/web/20040930164 ... /~chinook/

We began the effort to solve checkers in 1989 with the construction of the 4-piece checkers endgame database (7.3 million positions). Today we have the complete 9-piece databases and the 5-piece versus 5-piece subset of the 10-piece database (13 trillion positions). These computations took a "backwards" approach, starting at the end of the game and moving towards the start of the game. We also used a forward search, which began computing at the start of the game, searching until an endgame database position is encountered.

www.talkchess.com/forum/viewtopic.php?t=62550

The difference is that Ed computes DTM which Chinook didn't do.

That difference doesn't matter when considering whether the game is strongly solved or not.

[Ed Trice]

Excuse my ignorance. I thought Chinook had already 9 piece checkers databases in 2004? Doesn't that imply they already strongly soved 9x9 checkers then?

In the Artificial Intelligence nomemclature, there are different tiers associated with solving a game. The Chinook team was able to prove that the game of checkers is a draw from the starting position. This is referred to as "weakly" solving the game.

A minor point before continuing: checkers is an 8x8 game played on 32 of the 64 squares. You mentioned 9x9 above which I am supposing was a simple typo.

During their quest to weakly solve the game, they computed endgames with up to 10-pieces and stored only 3 values: win, loss, or draw.

I computed distance to win, which occasionally required more than one byte per position since wins > 255 were found.

[Gerd Isenberg]

Oups, yes, I meant 8x8. I was not aware they only had wdl databases, thank you.

[syzygy]

Oups, yes, I meant 8x8. I was not aware they only had wdl databases, thank you.

But the 10-piece checkers endgame databases completed by Ed Gilbert on 17 July 2005 include "moves-to-conversion" (i.e. distance-to-zero) data which is sufficient for converting any win.

http://edgilbert.org/Checkers/KingsRow.htm
http://edgilbert.org/EnglishCheckers/10-pieceBuild.htm
http://edgilbert.org/EnglishCheckers/mtc.htm

The moves-to-conversion information is available as a side effect of building WLD endgame databases, and I have been saving this data while building the 10-piece db. The entire MTC data for up to 10 pieces is huge, as there are about 10.9 trillion positions. The WLD data can be compressed into about 60 positions per byte, but the MTC data requires much more space because of the greater range of values for each position. Fortunately the majority of checkers positions convert in very few moves. The MTC data for these positions is not very interesting because a checkers program can determine the correct moves for these with a quick search. I am only saving MTC data for positions that have values of ten moves or greater. When completed this data will compress to about 50GB.

[Ed Trice]

Oups, yes, I meant 8x8. I was not aware they only had wdl databases, thank you.

But the 10-piece checkers endgame databases completed by Ed Gilbert on 17 July 2005 include "moves-to-conversion" (i.e. distance-to-zero) data which is sufficient for converting any win

Two quick comments and one further elaboration:

1. The Moves To Conversion database is not complete for all 10-piece endings, only those with a total of 8 or more kings.

2. As I demonstrated in a paper published in 2003, with as few as 3 pieces on the board, the MTC database can miss a win in 2 moves and instead elect to promote a checker to a king (a "conversion in 1") which prolongs the game for 29 more moves.

MTC databases are good in positions with many kings and few checkers, but even in "all kings" endings, a Distance To Win database still wins faster.

I have a 237-ply win for 4 checkers vs. 4 checkers. There is no corresponding entry in the MTC world as of yet.

I wanted to know the quickest win possible from any position. That's the difference.

Google for "The 7-Piece Perfect Play Database" and you should find a PDF you can download.

[syzygy]

Two quick comments and one further elaboration:

1. The Moves To Conversion database is not complete for all 10-piece endings, only those with a total of 8 or more kings.

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

2. As I demonstrated in a paper published in 2003, with as few as 3 pieces on the board, the MTC database can miss a win in 2 moves and instead elect to promote a checker to a king (a "conversion in 1") which prolongs the game for 29 more moves.

That's just fine for a strong solution.