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.
Checkers Is Strongly-Solved for 8-pieces
Moderators: hgm, Rebel, chrisw
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Is Strongly-Solved for 8-pieces
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.AlvaroBegue wrote: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.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
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.
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.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
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).AlvaroBegue wrote: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.
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Checkers Is Strongly-Solved for 8-pieces
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.Ed Trice wrote:It's not too hard to do with checkers either.AlvaroBegue wrote: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.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Is Strongly-Solved for 8-pieces
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:Ed Trice wrote: 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.
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.
There is really no need to be insulting. I am not embarrassed at all for asking questions.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.
-
- Posts: 5557
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Checkers Is Strongly-Solved for 8-pieces
You "could have" detected the troll a couple of days ago from the subject line of this thread...Rein Halbersma wrote:There is really no need to be insulting. I am not embarrassed at all for asking questions.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
Now you're just broadcasting your ignorance.Rein Halbersma wrote: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.
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.
Last edited by Ed Trice on Thu Feb 16, 2017 11:00 pm, edited 2 times in total.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
Yes, I figured that is what you meant.AlvaroBegue wrote: 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.
I meant "all-checkers," as in cases like 3 checkers vs. 3 checkers.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
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?Rein Halbersma wrote:
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...
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?