Checkers Is Strongly-Solved for 8-pieces

[Ed Trice]

That's what I like in DTW TBs, instant play.
Also at interior nodes, in a win/loss position just returning the DTW value adjusted to the current ply is so simple.
Another really great thing I like is that you can generate a very long pv by probing repeatedly the DTW TB until the final winning position.
All you need is an initial long enough pv that terminates in a position that is on the DTW TBs , and from there you can continue appending the "best" moves found in the TBs, really really great. Sometimes you get spectacularly long pvs even when the root position has several pieces more than your TBs.
You can't do that with WDL TBs only.
What I don't like is poor compression ratio, and to a less extent generation time wich is bigger than WDL TBs.
As I said in another post my first attempt to generating TBs for the portuguese variation of the game was the DTW flavor, only later I did the WDL, so currently I have the 9man WDL (14GB) and the 8man DTW (46GB), all using the leading checker (not rank) subdivision and both compressed and with the option to load them into RAM or using memory mapped files.

best regards,
Alvaro

Hi Alvaro,

I am still writing the access code for searching DTW during the play of the game. Right now all I can do is print out the solutions with my console app.

I did gather some stats.

I have 148,193,593,345 Distance To Win positions solved. This represents all of the 4x4 for 8-pieces + every 7-piece or fewer combination, including 6x1.

There are 25,735 positions that need 16-bits. So I have:

1.000000347315959 bytes per position without using compression.

The lookup is instantaneous though, even faster than the move generator, so my nodes/second will never drop when accessing the uncompressed databases.

I do have some db-9 and db-10 results so far for DTW:


White to move wins in 175-ply


White to move wins in 291-ply. The white checker crowns at the bottom.

I need more storage to continue, so for now I'm working on trying to design the GUI for it.

I'd like to see some of the longest wins in your variant. I'll have to look up the rules for your game and see the differences.

[Cardoso]

OK the portuguese/spanish variant has square 1 at lower right corner.
Square 32 at upper left corner, so the main diagonal 1-32, descends from left to right. The kings are replace by queens or "damas" and can make long range moves.

As I said before I had the 8man uncompressed DTW for many years, around 460GB.
Then an HDD failure caused the loss of those TBs.
Only recentely I recomputed the 8man DTW, but this time I compressed them to 46GB.
Their probing code is working just fine.
I've just one thing left to do: to achieve the best compression ratio I could, I removed many positions: captures for the side to move and captures for the side not to move.
So for the moment I can't display those spectacularly long pvs since my pv extending code lacks a simple search function that fills in the gaps for positions that were removed to obtain better compression. It's a simple thing to do, I just haven't had the time.

If you want I can send you a 2012 statistics file I generated by request of Herson P. Guier, the author of http://damasclasicas.blogspot.pt/
Herson, is from Costa Rica and he is a friend of mine and the most enthusiastic spanish checkers engine match organizer/maker. In that site you can see the matches he made using my program Profound.
That statistics file shows some positions and their DTW value.
I think there is a bug in the stats generating code since the DTW=210 counter doesn't show up. Oh wait I know what it is, since it shows only wins counters, that means it only shows odd DTW values, since losses are even values.
Anyway at the top of the file there is some 210 positions.
Below are some of those positions in FEN format.

best regards,
Alvaro


Positions DTW =210
B:W3,4,8,k6,k20:B26,k10,k25
B:W4,7,8,k14,k17:B26,k27,k29

Positions DTW =209
B:W7,k2,k8:B25,26,29,k15,k27

Positions DTW =206
B:W4,7,8,k10,k28:B26,k27,k29

[Ed Trice]

That's interesting. You place your pieces on the light-colored squares. We place our on the dark colors. So our games play on the same board but our pieces would never be in contact!

Our King = your Queen, and your Queen moves like a chess Bishop.

Now I see why the DTW is at 209/210: your Queen has lots of power.

I don't think I could figure out how to code your multiple jump rule. Capturing the greatest number of pieces, it the most Queens if the piece counts are the same...that must have been hard to implement.

I like the graphics too. Thanks for sharing. If I ever get mine finished I'll let you know!

[Cardoso]

You place your pieces on the light-colored squares

Yes, in spain and spanish language countries it's like that, but in portugal we invert the colors of the squares, so we do place the pieces on the dark squares, but we use a chess board rotated by 90º.

Now I see why the DTW is at 209/210: your Queen has lots of power.

Right, the queens/damas have more power and because of that it shortens the game.

I don't think I could figure out how to code your multiple jump rule. Capturing the greatest number of pieces, it the most Queens if the piece counts are the same...that must have been hard to implement.

Yes it is more work, because on captures we must first follow the quantity rule and then the quality rule, but the worst is the long range multiple jumps, so my capture generation functions are more complex and a bit slower than in english checkers.

I like the graphics too. Thanks for sharing. If I ever get mine finished I'll let you know!

my GUI was made in vb6, imagine that, I haven't updated it on the webpage for several years, but take a look at:
https://www.youtube.com/watch?v=gTuMUMnxauc

best regards,
Alvaro

[Ed Trice]

my GUI was made in vb6, imagine that, I haven't updated it on the webpage for several years, but take a look at:
https://www.youtube.com/watch?v=gTuMUMnxauc

best regards,
Alvaro

That's pretty nice looking! I didn't know it was possible to have a Visual Basic front end communicate to a C or C++ engine under the hood. I'll have to look into it.

By any chance, do you work as a carpenter? Your GUI had so many different choices for the wood, I thought it must be your profession

[Cardoso]

No I'm not a carpenter
But you are right, I do have a soft spot for wood.
I find wood is an exceptionally beautiful material, really gorgeous.
That's why I have so many boards/backgrounds of wood in the GUI.
I think it gives a warm cozy feeling to the GUI.
Try it out your self in your GUI and I think you will like it.

Alvaro

[Rein Halbersma]

I don't think I could figure out how to code your multiple jump rule. Capturing the greatest number of pieces, it the most Queens if the piece counts are the same...that must have been hard to implement.

Yes it is more work, because on captures we must first follow the quantity rule and then the quality rule, but the worst is the long range multiple jumps, so my capture generation functions are more complex and a bit slower than in english checkers.

Multiple jump rules can be programmed rather straightforward. First, you need to write an operator== and operator< (in C++, in C you would write a function) to be able to compare moves. For international checkers, the only criterion is the number of captured pieces. So you need to store an integer and compare for two moves the expression:

Code: Select all

m.num_captured_pieces()

For multi-criterion draughts variants it gets a little more complicated. Of course, operator== is easy, just logical-AND the various criterions. But it turns out that you can also use a std::tuple (C++11 library addition) that also makes it very easy to use operator<. E.g. for Spanish checkers, you store 2 extra ints and you compare the expression

Code: Select all

std::make_tuple(m.num_captured_pieces(), m.num_captured_kings())

Now you can pass this tuple of two integers to operator== and operator< and the C++ library will call automatically a routine that does the right thing: first comparing the first criterion, then the second etc.

I also implemented this for the hardest draughts variant, Italian draughts, where there are 4 criterions for capture resolution. For each move, I store an extra int, bool, int and bitboard and use the expression

Code: Select all

std::make_tuple(m.num_captured_pieces(), m.is_with_king(), m.num_captured_kings(), m.piece_order())

Here, the bitboard "piece_order" stores a 1 on index 63-i if the i-th captured piece was a king, and a 0 otherwise.

Then during capture generation, you have to keep the largest capture moves generated so far, and for each newly found capture move, you have to check whether it is smaller, equal or greater than the currently largest jump move. If it's smaller, you ignore it, if it's equal you add it, and if it's larger you remove the currently best moves and store the new one.

[Ed Trice]

No I'm not a carpenter
But you are right, I do have a soft spot for wood.
I find wood is an exceptionally beautiful material, really gorgeous.
That's why I have so many boards/backgrounds of wood in the GUI.
I think it gives a warm cozy feeling to the GUI.
Try it out your self in your GUI and I think you will like it.

Alvaro

I have a wooden frame around a green and white marble board, but now I'm thinking about redoing the frame. Do you have any "driftwood" or "sequoia" samples?

While testing out a bare bones search with only a material value evaluation function with Distance To Win Databases, I stumbled upon an interesting algorithm that is game-independent. You might be able to use it in your game.

I call it the...

Endgame Premonition Algorithm

It's really quite simple, yet a powerful forecaster when hitting your databases from a distance, even if they are too far away to overturn an assessment at the root. Here's what you do:

1. Create 3 signed counters: db_good, db_bad, db_draw.
2. Each time you hit a db win for the computer's side, db_good++
3. Each time you hit a db loss for it, db_bad++
4. Do the same for draws.
5. If your oppent hits a db win, db_bad++
6. If your opponent hits a loss, db_good++

If a score for the best move is a tie, pick the move with the best Endgame Premonition Score.

I use db_good minus db_bad as the tiebreaker.

If the parent position is "bad" for the computer, I use:

db_good + db_draw - db_bad

If the parent position is "very good" for the computer:

db_good - db_draw - db_bad



I'm testing it out on known early losses in checkers using a search too shallow to tactically see the danger, and it's working as I had hoped!

[Ed Trice]

No I'm not a carpenter
But you are right, I do have a soft spot for wood.
I find wood is an exceptionally beautiful material, really gorgeous.
That's why I have so many boards/backgrounds of wood in the GUI.
I think it gives a warm cozy feeling to the GUI.
Try it out your self in your GUI and I think you will like it.

Alvaro

Hello Alvaro,

I finally hooked up an interface to the code to be able to play a full game. I started with some test positions involving the longest wins for 4 vs. 4 (4x4).

In the position where red to move wins in 293-ply, my program was able to draw with the LOSING side against programs playing the winning side with win-loss-draw databases for 8-pieces. The programs would make progress, occasionally encountering a slew of consecutive positions where there was only 1 move to sustain the win, and then choices would then proliferate. Literally every move could win in some cases, and progress would be lost 10-30 ply, and programs could not get below 191-ply to the game's end.

Even searching 35-41 plies with an 8-piece database is not enough to find the winning tactic since the win is so distant.

Are there any such equivalent positions in your game?

[Cardoso]

No I'm not a carpenter
But you are right, I do have a soft spot for wood.
I find wood is an exceptionally beautiful material, really gorgeous.
That's why I have so many boards/backgrounds of wood in the GUI.
I think it gives a warm cozy feeling to the GUI.
Try it out your self in your GUI and I think you will like it.

Alvaro

Hello Alvaro,

I finally hooked up an interface to the code to be able to play a full game. I started with some test positions involving the longest wins for 4 vs. 4 (4x4).

In the position where red to move wins in 293-ply, my program was able to draw with the LOSING side against programs playing the winning side with win-loss-draw databases for 8-pieces. The programs would make progress, occasionally encountering a slew of consecutive positions where there was only 1 move to sustain the win, and then choices would then proliferate. Literally every move could win in some cases, and progress would be lost 10-30 ply, and programs could not get below 191-ply to the game's end.

Even searching 35-41 plies with an 8-piece database is not enough to find the winning tactic since the win is so distant.

Are there any such equivalent positions in your game?

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