Checkers Is Strongly-Solved for 8-pieces

[AlvaroBegue]

For pawn-less endgames, it's easy to use a perfect indexing scheme, and I am sure everyone that has ever seriously tried to generate tablebases for checkers has done it that way.

I generated 6-men tablebases for Spanish checkers (essentially the same as the Portuguese checkers mentioned by Álvaro Cardoso) a couple of years ago, and the indexing scheme I used didn't waste any space as long as one side didn't have pawns. It's not a particularly difficult thing to do.

[Rein Halbersma]

For pawn-less endgames, it's easy to use a perfect indexing scheme, and I am sure everyone that has ever seriously tried to generate tablebases for checkers has done it that way.

I generated 6-men tablebases for Spanish checkers (essentially the same as the Portuguese checkers mentioned by Álvaro Cardoso) a couple of years ago, and the indexing scheme I used didn't waste any space as long as one side didn't have pawns. It's not a particularly difficult thing to do.

Exactly, binomial indexing of identical pieces is rather straightforward. The only reasonable deviation is to not correct for black/white interference and to keep Binomial[32, 4]^2 positions, and do legality checking (cheap with bitboards) during generation. This leads to 2.6 Gb for 4 kings vs 4 kings. One advantage of this is that it is easier to swap the order of black and white piece groups in an index for caching purposes.

[Ed Trice]

Oh ye of little faith.

4 kings vs. 4 kings requires 1.61 GB of RAM.

WWWWRRRR with white to move can jump into:
WWWWRRR in the 7-piece database where it is RRRRWWW to be probed.
WWWWRR in the 6-piece database where it is RRRRWW to be probed.
WWWWR in the 5-piece database where it is RRRRW to be probed.

WWWWRRRR = 1404.34 MB
RRRRWWW = 224.70 MB
RRRRWW = 25.93 MB
RRRRW = 1.92 MB

total = 1656.89 MB = 1.61 GB

The reason I said you need a 128 GB computer to solve the 8-piece perfect play database is because 2 kings + 2 checkers vs. 3 kings + 1 checker needs 81114 MB = 79.21 GB and any amount over 64 GB must require a minimum of 2 x 64 = 128 GB of RAM.

WWwwRRRr and WWWwRRrr must both be in RAM to solve this asymmetric slice. With white to move, sometime a checker can JUMP AND CROWN into a king, and sometimes a white checker just jumps.

WWwwRRRr can jump into WWwwRRR, WWwwRRr, WWWwRRR, WWWwRRr, WWwwRR, WWwwRr, WWWwRR, WWWwRr, WWwwR, WWwwr, WWWwR, WWWwr

It promotes into WWWwRRRr.

Now you must do the same thing for the other slice, WWWwRRrr.

You can give me all of your wooden rhetoric, I'm not listening to it. I solved the 8-piece perfect play databases, and you didn't.

As I said before, just stop posting. You're just embarrassing yourself.

[Ed Trice]

For pawn-less endgames, it's easy to use a perfect indexing scheme, and I am sure everyone that has ever seriously tried to generate tablebases for checkers has done it that way.

I generated 6-men tablebases for Spanish checkers (essentially the same as the Portuguese checkers mentioned by Álvaro Cardoso) a couple of years ago, and the indexing scheme I used didn't waste any space as long as one side didn't have pawns. It's not a particularly difficult thing to do.

It's not too hard to do with checkers either. The trick is to put both sides' checkers on the board first before any kings, and treat them as 1 sub-index, paying attention to when checkers of opposing sides are still in the back row (and can interfere with each other).

Ed Gilbert and I worked on improving the GUI Checkers program by Jonathan Kruezer. Ed got it to work with Martin Fierz's checkerboard program and I hooked up my 6-piece Perfect Play databases to it. I wrote one indexing function for each type of material distribution for up to 3 vs. 3, so if you go to GitHub you can see the source code if you want.

[AlvaroBegue]

For pawn-less endgames, it's easy to use a perfect indexing scheme, and I am sure everyone that has ever seriously tried to generate tablebases for checkers has done it that way.

I generated 6-men tablebases for Spanish checkers (essentially the same as the Portuguese checkers mentioned by Álvaro Cardoso) a couple of years ago, and the indexing scheme I used didn't waste any space as long as one side didn't have pawns. It's not a particularly difficult thing to do.

It's not too hard to do with checkers either.

I was talking about checkers. The board in Spanish checkers is exactly the same, so the indexing schemes are also the same. I might have confused you by using the word "pawn" instead of "checker": It's a mistranslation of the Spanish "peón". Sorry about that.

[Rein Halbersma]

The reason I said you need a 128 GB computer to solve the 8-piece perfect play database is because 2 kings + 2 checkers vs. 3 kings + 1 checker needs 81114 MB = 79.21 GB and any amount over 64 GB must require a minimum of 2 x 64 = 128 GB of RAM.

WWwwRRRr and WWWwRRrr must both be in RAM to solve this asymmetric slice. With white to move, sometime a checker can JUMP AND CROWN into a king, and sometimes a white checker just jumps.

WWwwRRRr can jump into WWwwRRR, WWwwRRr, WWWwRRR, WWWwRRr, WWwwRR, WWwwRr, WWWwRR, WWWwRr, WWwwR, WWwwr, WWWwR, WWWwr

It promotes into WWWwRRRr.

Now you must do the same thing for the other slice, WWWwRRrr.

Well, yes if you want to do it like that, yes you can indeed use huge amounts of RAM. But you can do it considerably more compactly:
a) use leading rank indexing or even more fine grained subdivisions to keep the two dbs being built a lot smaller (up to 49 times smaller for leading rank indexing)
b) use the compressed versions of the already built dbs and use a cache of compressed blocks.

Again, all these refinements were documented 20 years ago and became feasible with consumer hardware 12 years ago. DTW only requires a factor of 8 more RAM than WLD.

You can give me all of your wooden rhetoric, I'm not listening to it. I solved the 8-piece perfect play databases, and you didn't.

As I said before, just stop posting. You're just embarrassing yourself.

There is really no need to be insulting. I am not embarrassed at all for asking questions.

[syzygy]

There is really no need to be insulting. I am not embarrassed at all for asking questions.

You "could have" detected the troll a couple of days ago from the subject line of this thread...

[Ed Trice]

Again, all these refinements were documented 20 years ago and became feasible with consumer hardware 12 years ago. DTW only requires a factor of 8 more RAM than WLD.

Now you're just broadcasting your ignorance.

I solved the 8-piece WLD database in 2001, in fact on December 6,2001 Dr. Schaeffer writes about it in his second "One Jump Ahead" book.

That's over 15 years ago that I did it, and you're posting as if you're giving me information.

And your statements about subdivisions are comical. Your hard disk would disintegrate with all of the activity needed to solve DTW for checkers with 49 subdivisions per configuration times all of the simultaneous access to solve the largest slices. You'd need to call fopen(), fseek(), fread(), fwrite(), and fclose() up to 49 times x 2 x the number of checkers slices I listed in the comma separated list a couple posts up for EACH time I only needed to de reference a single pointer in RAM.

So, "yeah you could do it that way," to use your own words, if you wanted to take 90 days to do what I did in 5.

You're what's called an "Armchair Quarterback." You talk as if you know everything and you haven't written one line of code.

I've finished the project after having tried many different approaches that wouldn't complete the project until after the Milky Way collides with Andromeda.

But go ahead, please, I enjoy the comedy.

And if your STATEMENTS were in the form of QUESTIONS, I would't be tarring-and-feathering you online. I'd answer any questions.

But you're trying to TELL ME as if you know what the hell you're talking about, and I've already repeatedly corrected you.

[Ed Trice]

I was talking about checkers. The board in Spanish checkers is exactly the same, so the indexing schemes are also the same. I might have confused you by using the word "pawn" instead of "checker": It's a mistranslation of the Spanish "peón". Sorry about that.

Yes, I figured that is what you meant.

I meant "all-checkers," as in cases like 3 checkers vs. 3 checkers.

[Ed Trice]

Well, yes if you want to do it like that, yes you can indeed use huge amounts of RAM. But you can do it considerably more compactly:

...

b) use the compressed versions of the already built dbs and use a cache of compressed blocks.

Again, all these refinements were documented 20 years ago...

So tell me, what compression technique did they use "20 years ago" that compressed data that used all 256 numbers from 0 to 255 within a single byte?

Oh, that's right, there was none, because the Chinook team only had win-loss-draw entries, whereas I used every integer from 0 to 255, leaving NO COMPRESSION SCHEME available for run-length tokens of single byte lengths.

See why being an "armchair quarterback" is stupid yet?