Tablebase generation speed

[EricLang]

Does anyone has some tips or tricks to improve the generation speed of tablebases?
The method I'm using right now is the most simple:
Loop through all positions and find DTM=0, then loop again and find DTM=1 etc.
This is all done in memory for 3,4,5 pieces, but will not be possible for 6 pieces, so the tables for 6 pieces have to be written to disk directly, I think this will take weeks for one file!
Generating all moves again and again is slow, I think, but it seems impossible to cache them all. This will cost too much memory.
Tips and tricks are very welcome!

[koistinen]

Both h.g.muller and I have discussed how to generate DTZ tablebases efficiently.
For pawnless 7-man endings, my partitioning scheme works well as long as there are at least 2-3 black pieces and his works well as long as there are at least 3-4 white pieces.
Things our schemes have in common are that we mostly use just a few bits per position when generating and also we partition by keeping examining a limited set of the non-moving pieces at a time.
A difference between us is that I generally don't mind throwing hardware at the problem as long as it doesn't cost more than about EUR 5000. (what I feel I can afford now, hardware will get cheaper anyway)
Both our schemes are limited by the speed of sequential read/writes of hard disks.
Seeks are limited so they require about the same or less time as the read/writes, because our blocks are large enough.

[Codeman]

Another option is to use Bitbases. They will take about 2GB-ram to generate a 6men pawnless EGTB (pawnfull are even cheaper).

One option to save you from generating the moves every time again is to save the movecount once in a byte variable for each index. And everytime you get to the node again you decrement it. As soon as it reaches 0 it means that the loosing side has no good moves left. From that position you can then do all backward-moves from the winning side to get the next Mate in N+1 positions.

[EricLang]

Sounds like magic, Codeman... I'll test it. But I will have to write a GenerateMovesReverse(), hmm...

[EricLang]

I really do not understand how to generate 5-men tables in a few minutes. my KQN-K (4 pieces) takes 14 minutes and everything is done in-memory!

[guyhaw]

Codeman's idea of counting down how many options the 'possible loser' has sounds good in theory - and Ken Thompson tried it, but KT said that it was not a contributor to efficiency in practice. See an old ICCA_J article by or on behalf of Ken Thompson.

Faster speed is achieved by:

1) not having to revisit a position once a depth is determined. This takes skill with DTM but is easier with DTC and DTZ,
2) provided one's unmove function works well (and a simple index-scheme helps here), only unmove from decisive positions rather than 'try all'
3) if (DTM) EGTs pre-exist, then extract the list of positions which are drawn and 'knock them out' first.
4) if not, then calculate the WDL EGT first and use that to eliminate some positions.
5) monitor your program to see where it is spending its time: focus on the inner loops where the time is going
6) get a grip on your disc I/) if possible: more than one drive help, and avoiding needless track-to-track head-movement helps as well.
7) Yakov Konoval gets some speed by writing in Pentium Assembler - but I think this sets the bar high.

I have a theory that files should always be compressed before being sent to disc, and decompressed as they come off disc, but i don't think this is 'shared wisdom' yet, at least not in EGT-generation.

g

[EricLang]

Ok, I'm relatively new to tablebases.
What is WDL EGT?
What is DTZ?
DTC = Distance To Conversion I know that.

I am writing a DTM base as far as I know

I will try to write a UnMove() function, which will not be very easy.
But I cannot imagine how this saves time: what's the difference between accessing positions forwards or backwards?

Tip #3 I can understand

Thanks so far, I thought I was almost ready with my program but it seems I have to work on the speed

[Codeman]

Ok, I'm relatively new to tablebases.
What is WDL EGT?
What is DTZ?
DTC = Distance To Conversion I know that.

WinDrawLoss ... Tablebases which have 2 bit per position. (win, draw, loss, illegal)
Distance to Zero ... Same as DTC, only that pawnmoves (=irreversible as well) are used as zeroing moves as well, not just captures and promotions

I am writing a DTM base as far as I know

I will try to write a UnMove() function, which will not be very easy.
But I cannot imagine how this saves time: what's the difference between accessing positions forwards or backwards?

Tip #3 I can understand

Thanks so far, I thought I was almost ready with my program but it seems I have to work on the speed

You don't have to loop through all positions again every depth. Instead you can just do an unmove from the critical positions.
eg to get all positions where black is mated in n+1 you take all wtm (white wins in n) positions and do one unmove.

[koistinen]

What is DTZ?
DTC = Distance To Conversion I know that.
...
Thanks so far, I thought I was almost ready with my program but it seems I have to work on the speed

DTZ is distance to zeroing the game counter with respect to the 50 move rule. Similar to DTC, only all pawn moves reset the counter too.
DTZ50 is the same but where you count positions as drawn if they are drawn due to the 50 move rule at some point given perfect play.

Don't go for speed before correctness. If you do DTZ50 correctly it is useful for verifying the results of others, even if you only manage 4-man in resonable time.

[notnale]

Here is a method I came up with for generating DTM(k) tables assuming I ever get around to programming it
How can I improve it?

At each point the DTM(k-1) table would be stored in memory, along with the current one in progress

For each position
If the value of the position in DTM(k-1) is not mate in 1, mate in 0, or loss in 1, or loss in 0
find all legal moves
for each move
find the position after the move
find the value of this position in the DTM(k-1) tablebase
compare it to the highest value found so far and take the higher
if it is mate in 1 except the loop early
store the previous tablebase to the hardrive, increment k, and repeat

[Codeman]

This should work well for endgame with <= 6 pieces .. but for anything bigger, you would need another approach.

[notnale]

Well it seems like the biggest bottleneck would be the function that determines which positions each position can move into either forward, or in reverse

[EricLang]

You don't have to loop through all positions again every depth. Instead you can just do an unmove from the critical positions.
eg to get all positions where black is mated in n+1 you take all wtm (white wins in n) positions and do one unmove.

Ok still having problems here.
Assume I have this position with black to move:

WK = c3
BK = e1
WQ = g2

This is a mate in 2 position

Should I now generate all moves which can lead to this position and mark them with dtm=3?
Or only when the resulting preceding positions are marked with a higher dtm?

[h.g.muller]

If you generate the DTx in increasing order, you can always label the predecessors of a DTx=2 btm position as DTx=3 (wtm). Because you know that you have not assigned DTx > 3 to any position yet. Otherwise, you would have to check in order to avoid make an already assigned DTx worse.

For wtm positions with DTx=n the predecessors are not automatically DTx=n+1, they are only potential DTx=n+1. You will have to verify if black does not have other (forward) moves that go to positions with DTx > n or no DTx at all. But if n is the most recent DTx you assigned, the btm positions cannot have a DTx yet, as upto now they had a move that led to a still undecided position. Again, if you generate DTx in order, you will never have to lower an already assigned DTx on btm positions, they will only switch from 'undecided' to their final DTx. And then their btm successors will always be undecided at the moment they switch, and either remain undecided, or get DTx=n as well (if none of their successors is undecided).

[EricLang]

I'll study on that again Mr. Muller.
I think I understand the algorithm, but there must be a diabolical bug in my code. I'll have to debug and debug again and again..
I'll think too about your remark about the "tricky" unique triangle in another post.

[h.g.muller]

Pehaps you should try first without diagonal symmetry (or perhaps without any symmetry at all), to see if you can reproduce the numbers of KRK for the various DTM (e.g. the numbers you get from the generator on my website). If these match, you know that the basic logic is OK, and you can switch on the various symmetry operations to reduce the work.

[EricLang]

Ok about this symmetry. I want to ask a questions to see if I understand it:

Let call a position this is in the egtb "RP" (Real Position).
And a position that is not (so a position that has to be rotated and mirrored to do a probe) "VP" (Virtual Position)

1) I'm testing a RP where DTM = 2.
2) Now I make all unmoves which can lead to this position
3) From this I get all parentpositions, VP's and RP's

Now all resulting RP-parent positions can be marked with DTM = 3
But can we mark the VP-parentpositions (after rotate/mirror) also as DTM=3?
Right now I am doing that and it seems to give the right results as far as I can see.

(Edit: this all provided when I work back from DTM=0 and increase that, as you mentioned)

BTW I read a few posts of yours and your website too, interesting stuff!

[h.g.muller]

Ok about this symmetry. I want to ask a questions to see if I understand it:

Let call a position this is in the egtb "RP" (Real Position).
And a position that is not (so a position that has to be rotated and mirrored to do a probe) "VP" (Virtual Position)

1) I'm testing a RP where DTM = 2.
2) Now I make all unmoves which can lead to this position
3) From this I get all parentpositions, VP's and RP's

Now all resulting RP-parent positions can be marked with DTM = 3
But can we mark the VP-parentpositions (after rotate/mirror) also as DTM=3?

By definition you cannot mark a VP as anything, as it is not in the TB. So there is nothing to mark.

The tricky thing is this: Of most positons there are 8 versions (related by rotation or reflection), 1 RP, and 7 VP. We could say the entire set of 8 is represented by the single RP in the TB. If the RP has DTM=2, the 7 VPs also have DTM=2. Every parent of every position in the set will have DTM=3. But not all of them will be in the TB. Furthermore, we can only get to them from the RP, as the VP do not exist anywhere. When we do an unmove from the DTM=2 RP, we either get to a parent RP or a VP (this might depend on the unmove, e.g. the white King might step out of the triangle, or stay in it). If it gets to a VP, we can mirror or rotate that VP to get the corresponding RP. This RP will then have to be marked as DTM=3.

But it might not be the only RP of the set of 8 parents. Some sets of 8 equivalent positions have 2 RP and 6 VP. For instance in KRK, the positions W:Ka1 Ra8 B:Kc3 (A) will be a RP, but so will be W:Ka1 Rh1 B:Kc3 (A'). So if an unmove from DTM=2 reaches either of those, we must make sure that both the RP are marked DTM=3. This is automatic if the DTM=2 RP we came from also came from a set that had 2 RP, e.g. W:Ka1 Ra7 B:Kc3 (B). Then Ra7-a8 would reach A from B. But there would be another move from the other position, Rg1-h1, which would reach A' from B', so both would get marked automatically. But if we were reaching A from the position W: Kb1 Ra8 B: Kc3 (C), there would not be a corresponding unmove to A' from C' (=W:Ka2 Rh1 B:Kc3), as C' is a VP. So when we are unmoving from C to A, we should be smart enough to realize that A has a 'twin' RP that will ot be automatically marked, as the position it was reached from did not have a similar twin.

Right now I am doing that and it seems to give the right results as far as I can see.

(Edit: this all provided when I work back from DTM=0 and increase that, as you mentioned)

BTW I read a few posts of yours and your website too, interesting stuff!

[EricLang]

Thanks!

The tricky thing is this: Of most positons there are 8 versions (related by rotation or reflection), 1 RP, and 7 VP. We could say the entire set of 8 is represented by the single RP in the TB. If the RP has DTM=2, the 7 VPs also have DTM=2. Every parent of every position in the set will have DTM=3. But not all of them will be in the TB. Furthermore, we can only get to them from the RP, as the VP do not exist anywhere. When we do an unmove from the DTM=2 RP, we either get to a parent RP or a VP (this might depend on the unmove, e.g. the white King might step out of the triangle, or stay in it). If it gets to a VP, we can mirror or rotate that VP to get the corresponding RP. This RP will then have to be marked as DTM=3.

This I understood already

But it might not be the only RP of the set of 8 parents. Some sets of 8 equivalent positions have 2 RP and 6 VP. For instance in KRK, the positions W:Ka1 Ra8 B:Kc3 (A) will be a RP, but so will be W:Ka1 Rh1 B:Kc3 (A'). So if an unmove from DTM=2 reaches either of those, we must make sure that both the RP are marked DTM=3. This is automatic if the DTM=2 RP we came from also came from a set that had 2 RP, e.g. W:Ka1 Ra7 B:Kc3 (B). Then Ra7-a8 would reach A from B. But there would be another move from the other position, Rg1-h1, which would reach A' from B', so both would get marked automatically. But if we were reaching A from the position W: Kb1 Ra8 B: Kc3 (C), there would not be a corresponding unmove to A' from C' (=W:Ka2 Rh1 B:Kc3), as C' is a VP. So when we are unmoving from C to A, we should be smart enough to realize that A has a 'twin' RP that will ot be automatically marked, as the position it was reached from did not have a similar twin.

It is complicated, I almost get it.

I will try to compile your C-program from your website to check the results.
It's funny to see that it's possible in about 500 lines code. I think I have to forget about my standard way of generating moves etc. which I use for my engine.
It seems handy but generating egtb's cannot use all this overhead which makes it slower.

[koistinen]

Another possibility is to examine all moves and positions (except perhaps conversion moves which only need to be examined in the beginning). Then you only need to do a one ply forward search/position to increase depth 1 ply and you never run into the problem of positions that are not updated.
Luckily this is possible to do reasonably quickly using all bits of the processors register width. (At least in theory: I have still not heard of anyone who has used this method to compute even check mates.)

[h.g.muller]

It is complicated, I almost get it.

I will try to compile your C-program from your website to check the results.
It's funny to see that it's possible in about 500 lines code. I think I have to forget about my standard way of generating moves etc. which I use for my engine.
It seems handy but generating egtb's cannot use all this overhead which makes it slower.

I basically used the same move genrator as in micro-Max. It is a bit cluttered, because I used the same move generator for the forward and backward move generation, and they need a different way to treat captures. (Captures and uncaptures are completely different beasts.) The advantage of the move geerator is that it is table driven, so that I can easily use it for all kind of fairy pieces.

This generator is not as I would write it now; I think I could write one that is 10 times faster. This is not even the fastest version; I have one that is about 2 times faster for some end-games. I never put that on the web, as my laptop died just after I made it. I recovered it now, though, so I might still post it. But neither of the generators was written for didactcal purposes; the code is very messy.

If you want to use it for comparing numbers, note that the numbers corrected for diagonal symmetry (i.e. counting positions with the two symmetry pieces on the diagonal as 1, the others as 2) are written on a file (report.txt, IIRC). The numbers it prints on screen during generation probably cannot be compared with anyting.

[h.g.muller]

I posted the more advanced version of my 5-men EGTB generator now on my website as well:

http://home.hccnet.nl/h.g.muller/5men13.html

On my 2.4 GHz Core 2 Duo (E6600) it takes 86.5 sec to generate KBBKN, and 141.5 sec for KQQKQ with this program. The latter end-game is the one that takes the longest time to generate of all pawnless 5-men. The former needs the largest number of cycles, but is still much faster, because per cycle there are far fewer moves. (As the generator does not make use of the two white pieces being equal, in theory it should be possible to reduce these times by a factor 2.)

A 4-men like KBNK takes just under 1 sec, KQKR 1.76 sec.

[EricLang]

I'll try that new code of yours Muller, great! Currently my head is spinning with this reverse algorithm. I'll have a small time out