Checkers Is Strongly-Solved for 8-pieces

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Sun Feb 12, 2017 6:13 pm

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

Image

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
Posts: 2107
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Gerd Isenberg » Mon Feb 13, 2017 1:04 pm

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
Posts: 3698
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Sven » Mon Feb 13, 2017 1:43 pm

Gerd Isenberg wrote: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.

User avatar
WinPooh
Posts: 230
Joined: Fri Mar 17, 2006 7:01 am
Contact:

Re: Checkers Is Strongly-Solved for 8-pieces

Post by WinPooh » Mon Feb 13, 2017 1:52 pm

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
Posts: 895
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Checkers Is Strongly-Solved for 8-pieces

Post by AlvaroBegue » Mon Feb 13, 2017 2:45 pm

Sven Schüle wrote:
Gerd Isenberg wrote: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
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 13, 2017 4:11 pm

Gerd Isenberg wrote: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
Posts: 2107
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Gerd Isenberg » Mon Feb 13, 2017 7:46 pm

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

syzygy
Posts: 4318
Joined: Tue Feb 28, 2012 10:56 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by syzygy » Mon Feb 13, 2017 8:08 pm

Gerd Isenberg wrote: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
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice » Mon Feb 13, 2017 8:24 pm

syzygy wrote:
Gerd Isenberg wrote: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
Posts: 4318
Joined: Tue Feb 28, 2012 10:56 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by syzygy » Mon Feb 13, 2017 8:30 pm

Ed Trice wrote: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.

Post Reply