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