Checkers Is Strongly-Solved for 8-pieces

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 5:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice »

Cardoso wrote: Sorry for the late reply, I only now noticed your posts, and I'm still at work.
About your Endgame Premonition Algorithm, looks interesting, I'll give it a try when I have the time.
About testing very distant winning positions with the loosing side against programs with only WDL, no I never tested that. The only other program for spanish checkers with EGTBs is Aurora, it has WDL+MTC and I don't have that program.
But I imagine there are positions in the spanish checkers variant where Profound + DTW tbs playing the loosing side could draw against Profound using only WDL, because it would be hard to make progress using only WDL.
Anyway your checkers variant has longer DTW lines.
But there are ways to make an engine with WDL only to make progress torwards the win, like giving bonus to advance men, bonus for promotions, and bonus for exchanging pieces to reach lower piece count endgames.
I have some of that but they are rudimentary, I never explored that because I fall in love with DTW tbs from the very beginning :-)

best regards,
Alvaro
I also created an Aggressive Draw Heuristic. Every draw it encounters for the opponent gets a score between +122 to -122 (I use 1 checker = 500, 1 King = 650) where a low score indicates a higher percentage of moves draw and a high score means fewer moves draw. It can find positions where only 1 move out of 25 choices draw!

I don't evaluate draws where there are jumps, or for the same side as the program (no need to do this if you think about it).

I'm working on speeding this up a bit by putting the results in its own hash table.
User avatar
MikeB
Posts: 4889
Joined: Thu Mar 09, 2006 6:34 am
Location: Pen Argyl, Pennsylvania

Re: Checkers Is Strongly-Solved for 8-pieces

Post by MikeB »

Ed Trice wrote:
Cardoso wrote: Sorry for the late reply, I only now noticed your posts, and I'm still at work.
About your Endgame Premonition Algorithm, looks interesting, I'll give it a try when I have the time.
About testing very distant winning positions with the loosing side against programs with only WDL, no I never tested that. The only other program for spanish checkers with EGTBs is Aurora, it has WDL+MTC and I don't have that program.
But I imagine there are positions in the spanish checkers variant where Profound + DTW tbs playing the loosing side could draw against Profound using only WDL, because it would be hard to make progress using only WDL.
Anyway your checkers variant has longer DTW lines.
But there are ways to make an engine with WDL only to make progress torwards the win, like giving bonus to advance men, bonus for promotions, and bonus for exchanging pieces to reach lower piece count endgames.
I have some of that but they are rudimentary, I never explored that because I fall in love with DTW tbs from the very beginning :-)

best regards,
Alvaro
I also created an Aggressive Draw Heuristic. Every draw it encounters for the opponent gets a score between +122 to -122 (I use 1 checker = 500, 1 King = 650) where a low score indicates a higher percentage of moves draw and a high score means fewer moves draw. It can find positions where only 1 move out of 25 choices draw!

I don't evaluate draws where there are jumps, or for the same side as the program (no need to do this if you think about it).

I'm working on speeding this up a bit by putting the results in its own hash table.
Ed - thanks for sharing, just curious as to what your endgame is here ( no pun intended :D ) , is it simply along the lines of I can do this which nobody else has ever done or you are planning to enter the checkers software market with a new engine , I guess it could be many different reasons. Regardless, I find it very interesting and appreciate you sharing what you are doing.
Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 5:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice »

MikeB wrote:
Ed - thanks for sharing, just curious as to what your endgame is here ( no pun intended :D ) , is it simply along the lines of I can do this which nobody else has ever done or you are planning to enter the checkers software market with a new engine , I guess it could be many different reasons. Regardless, I find it very interesting and appreciate you sharing what you are doing.
First and foremost, completing the 8-piece perfect play databases was a promise I made to my friend and colleague, Gil Dodgen, who died in 2016. Gil and I collaborated on two commercial software projects of tremendous complexity: World Championdhip Checkers (still available, since 1996) and Gothic Vortex, an 80-square chess variant of ours that can announce mate in 268 with its 5-piece tablebases. Gil and I solved distance-to-win in checkers up to 7 pieces with 4 on one side. I recently did the 5x2 and 6x1 set, and all of the 4x4 set for the 8-piece database.

Secondly, some of the ideas I published here are brand new, game-independent, and could be used by chess engine authors.

My Endgame Premonition Algorithm and Aggressive Draw Search Heuristic are two such examples.

Finally, posting such information is a way for like-mind people with similar interests to share their own ideas. From such acorns, mighty oaks grow.
Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 5:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice »

Krzysztof Grzelak wrote:Hi Ed.

Be where you can download the database 8-pieces.

Krzysztof Grzelak.
There are not for download, but I will be releasing a new checkers engine at some point in time this year.

There are 440 billion positions in the 8-piece database. At one bytes per position, this would be a 440 GB download.
Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 5:03 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Ed Trice »

syzygy wrote: You seem to have serious issues.
I have confirmation that it was your bullshit comments to my 8-piece database paper for checkers that kept it from being considered.

I will be publishing your comments for everyone to read.

You can't hide behind your mask of anonymity anymore, and people will be able to see what a jackass Ronald de Man is.
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Rein Halbersma »

Ed Trice wrote:
syzygy wrote: You seem to have serious issues.
I have confirmation that it was your bullshit comments to my 8-piece database paper for checkers that kept it from being considered.

I will be publishing your comments for everyone to read.

You can't hide behind your mask of anonymity anymore, and people will be able to see what a jackass Ronald de Man is.
Please make sure to publish your submitted paper as well.
syzygy
Posts: 5557
Joined: Tue Feb 28, 2012 11:56 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by syzygy »

Ed Trice wrote:
syzygy wrote: You seem to have serious issues.
I have confirmation that it was your bullshit comments to my 8-piece database paper for checkers that kept it from being considered.

I will be publishing your comments for everyone to read.

You can't hide behind your mask of anonymity anymore, and people will be able to see what a jackass Ronald de Man is.
I have no idea what you are talking about.
Rein Halbersma
Posts: 741
Joined: Tue May 22, 2007 11:13 am

Re: Checkers Is Strongly-Solved for 8-pieces

Post by Rein Halbersma »

syzygy wrote:
Ed Trice wrote:
syzygy wrote: You seem to have serious issues.
I have confirmation that it was your bullshit comments to my 8-piece database paper for checkers that kept it from being considered.

I will be publishing your comments for everyone to read.

You can't hide behind your mask of anonymity anymore, and people will be able to see what a jackass Ronald de Man is.
I have no idea what you are talking about.
I suppose a paper by the OP was rejected and he assumes it was a negative referee report by you that did him in. No reputable journal I know however would break referee anonymity. So he might have pointed out to him that his 8 piece checkers DTM paper does not sufficiently cite the relevant prior art, or otherwise does not sufficiently contribute to the state of the art in the field (method wise or computation size wise).

Until the OP posts said paper and rejection letter, we can only speculate from the peanut gallery :D
syzygy
Posts: 5557
Joined: Tue Feb 28, 2012 11:56 pm

Re: Checkers Is Strongly-Solved for 8-pieces

Post by syzygy »

I don't act as referee for any journal, reputable or not.

Any similarity with what was said in this thread must be due to the truth being objective.