10 piece endgame databases

[MichelG]

After a discussion with Bert, i decided to do a bit of work on the endgame databases again. I increased the generation speed manyfold, and also generated a partial 5 man vs 5 man endgame database. (win/draw/lose only, international draughts)

First i generated the full 1-8 piece endings (120 hours) and then did 5 man vs 4 man partial (about half a day) and then 5 vs 5 partial (about 1 day). On on a 64 GB, 24 core, intel 13900.

5v4 is resolved 48.6% for non-capture positions, and 5v5 solves only 18.9%.

Details and some sample positions at:
https://www.mdgsoftware.nl/draughts/sta ... -5040.html and
https://www.mdgsoftware.nl/draughts/sta ... -5050.html

I am still working on increasing the percentage of solved positions; that involves computing some of the sub-databases like 4+1 vs 3+1 first, but i suspect the effect will be limited.

Unfortunately the files are too huge to distribute (171 GB for 5v5) and they definitely will not improve program strength. I just generated them for fun.

[BertTuyt]

Michel, nice work!
My next question would be, could a neural network encode this information (example 5x5), with 99% accuracy?
Or sufficient accuracy to win complicated endgames, or to draw endgames where you have an enormous problem.

Bert

[MichelG]

Michel, nice work!
My next question would be, could a neural network encode this information (example 5x5), with 99% accuracy?
Or sufficient accuracy to win complicated endgames, or to draw endgames where you have an enormous problem.

Bert

I don't think so. For these endgames, i think many wins/loses hinge on edge cases and precise configurations. For a neural net to work well, it needs to figure out the regularities.

Think of the NN's as an analog compression algorithm.

Just for fun: this function would be highly accurate:

int score5v5quiet(position)
{
return DRAW;
}

The neural net in Dragon that for endgames without database available, does not even try to predict the win/draw/lose outcome, even though is trained on the endgame database. It just outputs a score rather than w/d/l percentages. I tried both mechanisms, and the score version works better.

[MichelG]

I did 4+1 vs 3+1 partial, and this position suprised me a bit:

with 47-41 the only winning move. With both sides having kings, i would have expected it to be a draw.

Percentages for quiet positions:
Win: 237.313.915.755 (17.1%)
Draw: 594.416.943.731 (42.7%)
Lose: 41.281.296.044 (3.0%)
Loss or draw: 79.466.560.844 (5.7%)
Draw or win: 406.949.904.351 (29.3%)
Unknown: 31.113.034.806 (2.2%)

[BertTuyt]

Michel, this is beyond human understanding, at least beyond mine.
Do you have a move sequence how the story continues?
This must be zillions of ply, before black surrenders.

Bert

[MichelG]

A 30-ply search with dragon give it +0.5 (like the 1 ply search)

I produced the game below manually because the partial databases are not supported in the search engine. They only show up in the analyse all moves. Don't know if i will change that.

So i played winning moves by hand, and let dragon play against that, and got this:

[Fen "W:WK44,47,48,49,50:BK1,2,3,4"]
1. 47-41 1-23 2. 41-36 23-37 3. 44-39 4-10 4. 39-30 10-15
5. 30-24 2-7 6. 24-2 7-12 7. 2-11 15-20 8. 50-45 20-25
9. 11-33 12-18 10. 33-29 37-23 11. 29-40 25-30 12. 40-35 30-34
13. 36-31 23-10 14. 35-24 10-14 15. 31-26 18-22 16. 24-33 14-28
17. 33-20 28-46 18. 20-38 46-19 19. 49-44 19-10 20. 38-16 10-14
21. 16-49 14-28 22. 44-40 28-10 * with conversion to a won regular database position.

Michel

[Rein Halbersma]

I did 4+1 vs 3+1 partial, and this position suprised me a bit:

with 47-41 the only winning move. With both sides having kings, i would have expected it to be a draw.

Percentages for quiet positions:
Win: 237.313.915.755 (17.1%)
Draw: 594.416.943.731 (42.7%)
Lose: 41.281.296.044 (3.0%)
Loss or draw: 79.466.560.844 (5.7%)
Draw or win: 406.949.904.351 (29.3%)
Unknown: 31.113.034.806 (2.2%)

I can believe that 47-41 is the only winning man move. But what is wrong with taking the long diagonal with the king move 44-28?

[pontel]

Hello MichelG,

This may be the most challenging endgame position for the draughts engines I know. With accurate defense from Black, converting the win can take almost the full 25 moves allowed by the rule. In other words, even a slight inaccuracy by White may be enough to let the win slip away.

[FEN "W:WK26,K25,15,K08,K02:BK46,K04."]

[Joost Buijs]

This may be the most challenging endgame position for the draughts engines I know. With accurate defense from Black, converting the win can take almost the full 25 moves allowed by the rule. In other words, even a slight inaccuracy by White may be enough to let the win slip away.

[FEN "W:WK26,K25,15,K08,K02:BK46,K04."]

To evaluate this position using an engine, information regarding the number of reversible moves is required; a Draughts FEN does not provide this information, which is a major shortcoming. For convenience, we assume that the number of reversible moves for this position is zero.
I can imagine that for engines with a WDL endgame database, it is difficult to find the correct line because they lack information about the minimum number of plies needed to win this position.

It turns out that a full-width search of 61 plies deep is required to find the win, which is impossible for an engine without an endgame database.
Ares has recently started using a 7P-DTW endgame database, which provides the distance-to-win. While this does not immediately allow the engine to account for the draw rules, a special search makes it easy to find all variations that satisfy the 16- and 25-move draw rules—of which there are many thousands.

I have attached a PDN file containing the first 100 variations found by Ares.

[MichelG]

I completed the rest of 5v4 with max 1 king per side, and then regenerated the 5v5 ending. This increased the percentage with exact scores considerably, from 19 before, to 45 percent now on 5v5, and 92% on 5v4.

results are on https://www.mdgsoftware.nl/draughts/stats/index.html Total disk size is 1.192 TiB (not available for download!) I also added several thousands of random positions for future independend verification.

The databases were generated by a slightly adapted dragon endgame generator.

Note that for 4+1 vs 3+1, in some positions, no party can progress their man, and only wander around with their kings. The endgame generator can detect this, and that was used to prove many draws in that endgame. 65.5% of non-captures are now exact.

Generating databases this way, with only a few kings, is not memory bound like the full databases, it is disk bound. (and also patience bound). 6v5 and maybe even 6v6 should be in possible, albeit at increasingly lower percentages. It would require more work on the generator, most notably a different indexing scheme. And for 6x6 one might want to exclude fields 46-50 for white and/or 1-5 for black.

But i will leave it at this for now.