EndGame Databases

[Ed Gilbert]

Hi Gerard,

Why do you need to lock the cache during "decode position's WLD value" ? Isn'it possible to first update LRU links and unlock immediatly the cache like this :

Yes you are quite right, and when I looked in my egdb driver code that is exactly how I did it. I shouldn't rely so much on my memory!

Damy implementation is completetly different because I wanted to optimise the number of cache locks.
The main point if the following : suppose that you have an infinity entries for your cache. That means that you never need to replace an old block by a new one. As a consequence you do not need to handle a LRU link and you never need to lock the cache.
That is the idea in Damy : as long as the cache is not full the cache is never locked. When the cache becomes full I lock the cache in order to remove about 25% of the cache and then I unlocked the cache until it becomes full again. As you see, in real real game it may happen that the cache is never locked !

I'm not sure why you are trying to minimize the number of cache locks at the expense of having less cache buffers full of data, because the cache locks are brief and therefore do not have much affect on performance. Let's say that on average your data cache is only 85% full. If instead it was always 100% full like mine is, doesn't that mean that you would on average have fewer cache misses and fewer disk reads?

-- Ed

[TAILLE]

I'm not sure why you are trying to minimize the number of cache locks at the expense of having less cache buffers full of data, because the cache locks are brief and therefore do not have much affect on performance. Let's say that on average your data cache is only 85% full. If instead it was always 100% full like mine is, doesn't that mean that you would on average have fewer cache misses and fewer disk reads?
-- Ed

I see your point. It could be significant with the 8 pieces endgame database but not with the 7 pieces endgame database because with this last db and a 1Go cache, the cache can hardly be full for a given game.
With the 8 pieces endgame db I will have to run some tests in order to know if the oldest blocks in cache may really help to avoid cache misses. In any case I can tune the number of entries that I want to remove from cache when it is full. It can be one entry or whatever I want (1% of the cache, 10% of the cache, 25% of the cache as currently or anyother figure).

[BertTuyt]

Intrigued by the discussions related to BreakThrough Draughs, I wanted to calculate the (theoretical) number of positions for a 8x8 board.
Inline with the statement that this variant was already solved by Martin Fierz for checkers after several months of calculations.
So Im sure that we can solve BreakTrought Draughts for 8x8 (using the 10x10 rules), but I doubt if we still need months of computing time.
Below the number of positions (144 Databases).

Code: Select all

Init Factoral Start
Init Factorial Done
1:1.1 Positions = 760
Number of Pieces = 2 Count = 760
Cumulatief    = 760
2:1.2 Positions = 9936
3:2.1 Positions = 9936
Number of Pieces = 3 Count = 19872
Cumulatief    = 20632
4:1.3 Positions = 83304
5:2.2 Positions = 125664
6:3.1 Positions = 83304
Number of Pieces = 4 Count = 292272
Cumulatief    = 312904
7:1.4 Positions = 503100
8:2.3 Positions = 1018056
9:3.2 Positions = 1018056
10:4.1 Positions = 503100
Number of Pieces = 5 Count = 3042312
Cumulatief    = 3355216
11:1.5 Positions = 2330640
12:2.4 Positions = 5933850
13:3.3 Positions = 7959904
14:4.2 Positions = 5933850
15:5.1 Positions = 2330640
Number of Pieces = 6 Count = 24488884
Cumulatief    = 27844100
16:1.6 Positions = 8611200
17:2.5 Positions = 26495040
18:3.4 Positions = 44717500
19:4.3 Positions = 44717500
20:5.2 Positions = 26495040
21:6.1 Positions = 8611200
Number of Pieces = 7 Count = 159647480
Cumulatief    = 187491580
22:1.7 Positions = 26048880
23:2.6 Positions = 94220880
24:3.5 Positions = 192174480
25:4.4 Positions = 241788751
26:5.3 Positions = 192174480
27:6.2 Positions = 94220880
28:7.1 Positions = 26048880
Number of Pieces = 8 Count = 866677231
Cumulatief    = 1054168811
29:1.8 Positions = 65714220
30:2.7 Positions = 273907920
31:3.6 Positions = 656756720
32:4.5 Positions = 998568024
33:5.4 Positions = 998568024
34:6.3 Positions = 656756720
35:7.2 Positions = 273907920
36:8.1 Positions = 65714220
Number of Pieces = 9 Count = 3989893768
Cumulatief    = 5044062579
37:1.9 Positions = 140111400
38:2.8 Positions = 662963730
39:3.7 Positions = 1831760480
40:4.6 Positions = 3274073276
41:5.5 Positions = 3956576472
42:6.4 Positions = 3274073276
43:7.3 Positions = 1831760480
44:8.2 Positions = 662963730
45:9.1 Positions = 140111400
Number of Pieces = 10 Count = 15774394244
Cumulatief    = 20818456823
46:1.10 Positions = 254963280
47:2.9 Positions = 1353752400
48:3.8 Positions = 4245982620
49:4.7 Positions = 8745200024
50:5.6 Positions = 12423500232
51:6.5 Positions = 12423500232
52:7.4 Positions = 8745200024
53:8.3 Positions = 4245982620
54:9.2 Positions = 1353752400
55:10.1 Positions = 254963280
Number of Pieces = 11 Count = 54046797112
Cumulatief    = 74865253935
56:1.11 Positions = 398806200
57:2.10 Positions = 2354660880
58:3.9 Positions = 8287015000
59:4.8 Positions = 19374908751
60:5.7 Positions = 31716102264
61:6.6 Positions = 37283864156
62:7.5 Positions = 31716102264
63:8.4 Positions = 19374908751
64:9.3 Positions = 8287015000
65:10.2 Positions = 2354660880
66:11.1 Positions = 398806200
Number of Pieces = 12 Count = 161546850346
Cumulatief    = 236412104281
67:1.12 Positions = 538899660
68:2.11 Positions = 3512903160
69:3.10 Positions = 13747443160
70:4.9 Positions = 36064560004
71:5.8 Positions = 67013445840
72:6.7 Positions = 90774659360
73:7.6 Positions = 90774659360
74:8.5 Positions = 67013445840
75:9.4 Positions = 36064560004
76:10.3 Positions = 13747443160
77:11.2 Positions = 3512903160
78:12.1 Positions = 538899660
Number of Pieces = 13 Count = 423303822368
Cumulatief    = 659715926649
79:2.12 Positions = 4516906290
80:3.11 Positions = 19514811840
81:4.10 Positions = 56923426846
82:5.9 Positions = 118679869176
83:6.8 Positions = 182479296120
84:7.7 Positions = 210267794000
85:8.6 Positions = 182479296120
86:9.5 Positions = 118679869176
87:10.4 Positions = 56923426846
88:11.3 Positions = 19514811840
89:12.2 Positions = 4516906290
Number of Pieces = 14 Count = 974496414544
Cumulatief    = 1634212341193
90:3.12 Positions = 23812470860
91:4.11 Positions = 76678769604
92:5.10 Positions = 177751054008
93:6.9 Positions = 306649643784
94:7.8 Positions = 401079159360
95:8.7 Positions = 401079159360
96:9.6 Positions = 306649643784
97:10.5 Positions = 177751054008
98:11.4 Positions = 76678769604
99:12.3 Positions = 23812470860
Number of Pieces = 15 Count = 1971942195232
Cumulatief    = 3606154536425
100:4.12 Positions = 88528413971
101:5.11 Positions = 226538083608
102:6.10 Positions = 434517247428
103:7.9 Positions = 637645511976
104:8.8 Positions = 723777011100
105:9.7 Positions = 637645511976
106:10.6 Positions = 434517247428
107:11.5 Positions = 226538083608
108:12.4 Positions = 88528413971
Number of Pieces = 16 Count = 3498235525066
Cumulatief    = 7104390061491
109:5.12 Positions = 246637926576
110:6.11 Positions = 522186906144
111:7.10 Positions = 851961761376
112:8.9 Positions = 1084984470504
113:9.8 Positions = 1084984470504
114:10.7 Positions = 851961761376
115:11.6 Positions = 522186906144
116:12.5 Positions = 246637926576
Number of Pieces = 17 Count = 5411542129200
Cumulatief    = 12515932190691
117:6.12 Positions = 534084182200
118:7.11 Positions = 961799942400
119:8.10 Positions = 1361753975340
120:9.9 Positions = 1527822346512
121:10.8 Positions = 1361753975340
122:11.7 Positions = 961799942400
123:12.6 Positions = 534084182200
Number of Pieces = 18 Count = 7243098546392
Cumulatief    = 19759030737083
124:7.12 Positions = 920149402480
125:8.11 Positions = 1437924255240
126:9.10 Positions = 1793545076928
127:10.9 Positions = 1793545076928
128:11.8 Positions = 1437924255240
129:12.7 Positions = 920149402480
Number of Pieces = 19 Count = 8303237469296
Cumulatief    = 28062268206379
130:8.12 Positions = 1280393721750
131:9.11 Positions = 1762663139952
132:10.10 Positions = 1959596777424
133:11.9 Positions = 1762663139952
134:12.8 Positions = 1280393721750
Number of Pieces = 20 Count = 8045710500828
Cumulatief    = 36107978707207
135:9.12 Positions = 1452466314728
136:10.11 Positions = 1782142334544
137:11.10 Positions = 1782142334544
138:12.9 Positions = 1452466314728
Number of Pieces = 21 Count = 6469217298544
Cumulatief    = 42577196005751
139:10.12 Positions = 1349779853708
140:11.11 Positions = 1489690180992
141:12.10 Positions = 1349779853708
Number of Pieces = 22 Count = 4189249888408
Cumulatief    = 46766445894159
142:11.12 Positions = 1028695710120
143:12.11 Positions = 1028695710120
Number of Pieces = 23 Count = 2057391420240
Cumulatief    = 48823837314399
144:12.12 Positions = 641335986590
Number of Pieces = 24 Count = 641335986590
Cumulatief    = 49465173300989
End Calculation

Number of positions around 49.5 E12.
As we only need win/lose values in the DB (no draw), 1 bit is required for raw decoding, which yield 5.7 TByte.
If we want speed, we need a SSD, so most likely we need to introduce compression (to avoid that Disk IO becomes the bottleneck).
Memory might also be an issue, but I assume that with slicing this would be doable.
As I did not recently focus on DB Generation, Im not aware of recent speed.
But gut feel says that to prove the theoretical outcome (based on DBs) this should be possible in week(s)...

Bert

[BertTuyt]

I modified my older DB-prgram (based upon work of Michel) to generate BreakThrough (BT) Databases (so no need to include king based DBs).
To generate, as a test, all the DBs for a max of 5 pieces (10 DBs, 10x10 board) it took my i7-940 (at around 3 GHz, and with 1 core) around 30.2 seconds, which yield a speed of 1.3 MPositions/second.

So if one can extrapolate this towards generating the full set of DBs for BT on a 8x8 board (and assuming it scales linear with more core and larger DB sizes, (which might not be true due to more disk IO), we need around 3.6 E6 seconds ( = 1000 hours = around 42 days) on a 4 GHz 8-core machine (with plenty of memory and SSD) to generate all 49.5 E12 positions .

Bert

[Fabien Letouzey]

I modified my older DB-prgram (based upon work of Michel) to generate BreakThrough (BT) Databases (so no need to include king based DBs).
To generate, as a test, all the DBs for a max of 5 pieces (10 DBs, 10x10 board) it took my i7-940 (at around 3 GHz, and with 1 core) around 30.2 seconds, which yield a speed of 1.3 MPositions/second.

So if one can extrapolate this towards generating the full set of DBs for BT on a 8x8 board (and assuming it scales linear with more core and larger DB sizes, (which might not be true due to more disk IO), we need around 3.6 E6 seconds ( = 1000 hours = around 42 days) on a 4 GHz 8-core machine (with plenty of memory and SSD) to generate all 49.5 E12 positions .

Bert

I'm curious about your interest in solving 8x8 BT. Is it to gain experience for 10x10, or do you have a fondness for endgame tables?

There seems to be no reason to go backward-only for solving this game, because most moves are irreversible. I remember that mixing forward and backward searches failed in Awari and instead they had to build the whole DBs on a parallel machine with a lot of RAM around year 2000. Opening-book construction wasn't making enough progress due to too many reversible moves, but this is not going to happen in BT.

Fabien.

[BertTuyt]

Fabien, good question(s).
Its based upon a fuzzy idea (also triggered by one of your comments, than maybe Draughts is about who promotes first, and than go from there...).

So I was thinking could we (one way or the other), combine BT DBs with search results in normal 10x10 Draughts.
From a search point of view , 2 different moves could look equal, but if one yields (according to the DB) a faster promotion to king, it could be worth trying.
As BT DBs are easier to generate, we could generate these beyond the piece limits (=8) we have today.
Maybe to 10 (so 5x5), as you suggested.

There are zillions of reasons why this approach does not work.
On the other hand if you would have posted your idea about the new evaluation, all could have find a same number of arguments why this was also non-sense.

Until you did, and all proved to be wrong.

And I still hope there is not a death penalty in Computer Draughts to at least try something different

Bert

[Fabien Letouzey]

Fabien, good question(s).
Its based upon a fuzzy idea (also triggered by one of your comments, than maybe Draughts is about who promotes first, and than go from there...).

Yes I was wondering whether draughts strategy is mostly about making a king first. With the implied effect that you cannot lose if you do that without giving away too much material. But even assuming that's true, it still leaves open the question of whether the opponent can get a draw. I didn't give that much thought, but I can imagine some threshold, say 7 plies, that would go like this:
IF I make a king first
AND my opponent cannot do the same <n> plies later
THEN I win (more often than not)

So I was thinking could we (one way or the other), combine BT DBs with search results in normal 10x10 Draughts.
From a search point of view , 2 different moves could look equal, but if one yields (according to the DB) a faster promotion to king, it could be worth trying.
As BT DBs are easier to generate, we could generate these beyond the piece limits (=8) we have today.
Maybe to 10 (so 5x5), as you suggested.

My plan was related. I wanted to learn a BT eval, and see if it played decent draughts during the middle game. I did learn an eval and it was distinctly better than a generic one, but I can't plug it in just like that, because it has no king evaluation (even material). Then other subjects were opened, and I switched to working on the protocol and cleaning up my GUI code. I should run a simple experiment anyway with a fixed value for kings, as it's not much work and the result can affect your project. I expect the BT eval to do badly: give too much to make a king first.

BT could also help me putting Killer draughts into perspective. I see an imaginary "drawishness" axis like this:
- normal draughts: too many draws
- killer draughts: good compromise?
- BT: no draws, but is it still draughts?
So if BT "fails" to be draughts-like (although it could still be fun), this would reinforce Killer draughts as a good replacement candidate for the official rules.

Fabien.

[BertTuyt]

Another thought, with 8x8 BT DBs, one can test all kinds of algorithms (in 8x8 DB Draughts), and have an absolute calibration to measure against.
If findings translate towards normal 8x8 and normal 10x10, indeed depends upon the question if it still draughts...

Bert

[Rein Halbersma]

Another thought, with 8x8 BT DBs, one can test all kinds of algorithms (in 8x8 DB Draughts), and have an absolute calibration to measure against.
If findings translate towards normal 8x8 and normal 10x10, indeed depends upon the question if it still draughts...

Bert

Hi Bert,

Indeed, having a strongly solved game (8x8 BT) is a great way to test correctness of all kinds of algorithms, in particular those where graph-history interactions (GHI) can invalidate the results of a search. Also, you get insight in the scaling behavior of the graph as a function of depth.

I have the same in mind, not for 8x8 yet but for for 6x6 variants. My idea is to a) strongly solve it by computing all dbs, b) computing a "reachability db" (i.e. reachable from the initial position) for all positions, and then c) compute a "relevancy db" (i.e. reachable from the initial position without a mistake that gives away the game-theoretic value of the initial position). I think you also did some Monte Carlo stuff to estimate reachability for endgames, but with a strongly solved variant you can compute this exactly.

With all that stuff into place, you can also do the following: drop more and more endgame dbs, and combine a forward search from the initial position with the reduced dbs. Plotting the total search effort against the size of the available dbs gives insight into the shape of the game-theoretic solution path, and it also lets you test the correctness of a forward search.

Rein

[BertTuyt]

Rein, agree with your post, having a strongly solved game opens all kind of options and opportunities for testing and learning.

In the meantime I needed to make small adjustments so the program (10 x 10 BT) was also able to generate the max. 6P Dbs.
This time 415.4 sec which also results in 1.3 MPositions/second (cumulative 555.265.745 positions) .

Note: I didnt check (so far) the DBs on correctness.

So a first try, Fabien, what was for the 1 x 1 BT DB the number of wins and losses (my output 1148 win, 837 lose)?

Bert

[Fabien Letouzey]

So a first try, Fabien, what was for the 1 x 1 BT DB the number of wins and losses (my output 1148 win, 837 lose)?

That's correct. For 2 vs. 2 I get 567700/335740. Without capture positions: 424883/285789.

[BertTuyt]

Fabien thanks.
I so far don't compress and don't exclude (and count) the capture positions, but the result here is the same!
Did you also measure time for generate up to 6P?

Bert

[Fabien Letouzey]

Did you also measure time for generate up to 6P?

10 minutes without verification. This includes 4v2 and 5v1.

selected win/loss ratios (all positions):
1v1: 1148/837
2v2: 567700/335740
3v3: 107237253/59754547

Fabien.

[BertTuyt]

Fabien,

3v3 has 166.991.800 positions.
In my calculation win 147.237.253 and lose 59.754.547

So think you made a typo with 107.237.253

Bert

[Fabien Letouzey]

3v3 has 166.991.800 positions.
In my calculation win 147.237.253 and lose 59.754.547

So think you made a typo with 107.237.253

I just checked again and that's what the code is printing ...