Syzygy bases from memory

[hgm]

Working code never sucks.

It does, if it is excessively slow. Try hash-probing with a linear search through the entire TT, end you will see what I mean...

[Pio]

For KRKP (36 million positions) my only interest are draw scores, only those (3.8 million) go into a the table else the table becomes too big. And since these 3.8 million are checked with the Syzygy bases the result is always correct. For KPK / KRKN / KRKB my only interest are the won positions, only those go into the table, another case is the KQKP ending with a pawn on the 6/7th row, some of them are draws -> into the table. As for the path to win or draw simply add a small PST value.

My mind is wondering off here into a sorted list of hash indices for the win positions and then a binary search into the list to see if the position is in it. I guess you wouldn’t need hash indices, just a position index would do (so few pieces). Or am I just over complicating it?

I've been thinking for a while that I too would like to know whether a position is a draw only, and that's 1 bit per index, however when I counted how many indices I'd need I quickly realized then even this is a huge amount of data

for KRKP I count this: 32*64*64*48*2 = 12 582 912 indices, this is still 32-bit (if I understand your idea), I thought of this too if a vast majority is winning/losing, then you'd only need to store indices for drawn positions
however, that still inflates by a factor of 32, so you'd need less than 1/32 drawn positions (or the opposite if the majority is draws) to actually save space (which I don't believe is the case here) plus I bet indices (even delta coded) would compress worse, would have to be tried though, perhaps byte slicing would help

You should be able to save KRKP in 32*64*64*48*2 bits if I am not mistaken (with some tricks that slow everything down a lot). The 32 comes from that side to move king always could be confined to the left side of the board (if you rotate the board if the king is on the right side). The 64, 64 and 48 comes from the number of positions of this side to move rook, other side’s king and other side’s pawn respectively (I know that it is possible to make it even smaller since you could remove some squares that are not valid since kings cannot be next to each other). The last two comes from the other possibility that the side to move has the pawn and the opponent has the rook.

The trick is to save a 1 if it is a win for side to move and 0 otherwise. If it is a zero we do not know if it is a draw or a loss. What we can do if we get a zero is to generate all opponent’s moves one at a time and see if the resulting position is saved as a 1 and if so we know that the original zero meant loss. If all of the opponent’s moves positions are 0 we know that the original zero meant a draw.

In this way you can save everything in 1.5 mega bytes

[Pio]

For KRKP (36 million positions) my only interest are draw scores, only those (3.8 million) go into a the table else the table becomes too big. And since these 3.8 million are checked with the Syzygy bases the result is always correct. For KPK / KRKN / KRKB my only interest are the won positions, only those go into the table, another case is the KQKP ending with a pawn on the 6/7th row, some of them are draws -> into the table. As for the path to win or draw simply add a small PST value.

My mind is wondering off here into a sorted list of hash indices for the win positions and then a binary search into the list to see if the position is in it. I guess you wouldn’t need hash indices, just a position index would do (so few pieces). Or am I just over complicating it?

I've been thinking for a while that I too would like to know whether a position is a draw only, and that's 1 bit per index, however when I counted how many indices I'd need I quickly realized then even this is a huge amount of data

for KRKP I count this: 32*64*64*48*2 = 12 582 912 indices, this is still 32-bit (if I understand your idea), I thought of this too if a vast majority is winning/losing, then you'd only need to store indices for drawn positions
however, that still inflates by a factor of 32, so you'd need less than 1/32 drawn positions (or the opposite if the majority is draws) to actually save space (which I don't believe is the case here) plus I bet indices (even delta coded) would compress worse, would have to be tried though, perhaps byte slicing would help

You should be able to save KRKP in 32*64*64*48*2 bits if I am not mistaken (with some tricks that slow everything down a lot). The 32 comes from that side to move king always could be confined to the left side of the board (if you rotate the board if the king is on the right side). The 64, 64 and 48 comes from the number of positions of this side to move rook, other side’s king and other side’s pawn respectively (I know that it is possible to make it even smaller since you could remove some squares that are not valid since kings cannot be next to each other). The last two comes from the other possibility that the side to move has the pawn and the opponent has the rook.

The trick is to save a 1 if it is a win for side to move and 0 otherwise. If it is a zero we do not know if it is a draw or a loss. What we can do if we get a zero is to generate all opponent’s moves one at a time and see if the resulting position is saved as a 1 and if so we know that the original zero meant loss. If all of the opponent’s moves positions are 0 we know that the original zero meant a draw.

In this way you can save everything in 1.5 mega bytes

What I think is the future of egtb format is to make some sort of smart rules that you train with a random forest. I believe that it is possible with maybe a hundred or so simple patterns to only make one miss prediction in maybe ten thousand positions. That should make it possible to make a size reduction of more than a factor hundred since you will only have to save the result of those indices that are miss predicted.

So when you want to look up the position you start by looking up if the position is among the miss predicted indices in logarithmic time (of course you can do it in constant time with cuckoo hashing for example but I do not think it is necessary). If the position is not among the miss predicted indices, you make your prediction with your random forest and return the result. Otherwise you return the result from the (index, result) tuple.

[Rebel]

Working code never sucks.

It does, if it is excessively slow. Try hash-probing with a linear search through the entire TT, end you will see what I mean...

Nah, draws can be cut off as a real transposition, bit-bases can't, you missed that and snp it.

[mar]

...
for KRKP I count this: 32*64*64*48*2 = 12 582 912 indices
...

You should be able to save KRKP in 32*64*64*48*2 bits if I am not mistaken (with some tricks that slow everything down a lot). The 32 comes from that side to move king always could be confined to the left side of the board (if you rotate the board if the king is on the right side). The 64, 64 and 48 comes from the number of positions of this side to move rook, other side’s king and other side’s pawn respectively (I know that it is possible to make it even smaller since you could remove some squares that are not valid since kings cannot be next to each other). The last two comes from the other possibility that the side to move has the pawn and the opponent has the rook.

The trick is to save a 1 if it is a win for side to move and 0 otherwise. If it is a zero we do not know if it is a draw or a loss. What we can do if we get a zero is to generate all opponent’s moves one at a time and see if the resulting position is saved as a 1 and if so we know that the original zero meant loss. If all of the opponent’s moves positions are 0 we know that the original zero meant a draw.

In this way you can save everything in 1.5 mega bytes

I believe the number of indices is identical to what I wrote... I guess you meant 48 is the pawn as it can't occupy ranks 1 or 8 in legal positions; 32 is clearly the horizontal mirror for one of the kings, in pawnless configurations 3 symmetries are possible and the 32 becomes 10 instead

the idea of saving a win is clever though and one might indeed extract WDL from it using a 1-ply search - haven't thought of it (I assume this is how WDL is actually stored in bitbases?),
but even so you still get a huge number of indices as you add more pieces, and KRKP is just one of the 4-man bitbases

my mind was fixed on the idea that it's often more valuable to know if a position is a draw - because each time I add some EG knowledge to my engine, it's always to scale down drawish configurations - the rest can be handled by search (*not always, in complicated configurations), like in KRKP the side with the pawn will be winning only in a vast minority of cases;
still even WDL doesn't guarantee progress in complicated configurations, I believe that's why syzygy uses both WDL and DTZ to guarantee progress

[mar]

What I think is the future of egtb format is to make some sort of smart rules that you train with a random forest. I believe that it is possible with maybe a hundred or so simple patterns to only make one miss prediction in maybe ten thousand positions. That should make it possible to make a size reduction of more than a factor hundred since you will only have to save the result of those indices that are miss predicted.

So when you want to look up the position you start by looking up if the position is among the miss predicted indices in logarithmic time (of course you can do it in constant time with cuckoo hashing for example but I do not think it is necessary). If the position is not among the miss predicted indices, you make your prediction with your random forest and return the result. Otherwise you return the result from the (index, result) tuple.

I believe some engines (slowchess?) use small NNs for prediction, so yes perhaps training a prediction net and encoding the residual error might save some extra space, however it'd have to be tried in practice.
question remains if a prediction would be able to cope with DTZ though, I'm not so sure. and I assume DTZ occupies more space than WDL in syzygy - so while you might save on WDL, DTZ would probably still occupy a lot of space

I guess that fitting all the insteresting 4-6 men endgames (WDL or D) in memory is a no-go and the best thing is to actually use syzygy as it's supposed to be used, I don't know

another interesting thing might be to compare scorpio bitbases (WDL I assume) with syzygy WDL, I believe scorpio bitbases actually occupy less disk space

[Pio]

What I think is the future of egtb format is to make some sort of smart rules that you train with a random forest. I believe that it is possible with maybe a hundred or so simple patterns to only make one miss prediction in maybe ten thousand positions. That should make it possible to make a size reduction of more than a factor hundred since you will only have to save the result of those indices that are miss predicted.

So when you want to look up the position you start by looking up if the position is among the miss predicted indices in logarithmic time (of course you can do it in constant time with cuckoo hashing for example but I do not think it is necessary). If the position is not among the miss predicted indices, you make your prediction with your random forest and return the result. Otherwise you return the result from the (index, result) tuple.

I believe some engines (slowchess?) use small NNs for prediction, so yes perhaps training a prediction net and encoding the residual error might save some extra space, however it'd have to be tried in practice.
question remains if a prediction would be able to cope with DTZ though, I'm not so sure. and I assume DTZ occupies more space than WDL in syzygy - so while you might save on WDL, DTZ would probably still occupy a lot of space

I guess that fitting all the insteresting 4-6 men endgames (WDL or D) in memory is a no-go and the best thing is to actually use syzygy as it's supposed to be used, I don't know

another interesting thing might be to compare scorpio bitbases (WDL I assume) with syzygy WDL, I believe scorpio bitbases actually occupy less disk space

Predictions will not work if you save the dtz directly (or at least it will be extremely hard). But if you would save the moves (cannot be so many with few pieces) that minimises dtz instead, you can train a model to make one of the minimising moves and only store those positions having miss predicted one of the minimising moves. In that way you should theoretically be able to compress dtz or whatever metric you use.

About the 1ply search idea, I have no idea if anyone uses it. I just came up with the idea while writing the post. Since the idea is so obvious I guess others have thought about it as well. I don’t think my idea about 1 ply search is good in practice since it will probably slow down the probes too much.

[mar]

About the 1ply search idea, I have no idea if anyone uses it. I just came up with the idea while writing the post. Since the idea is so obvious I guess others have thought about it as well. I don’t think my idea about 1 ply search is good in practice since it will probably slow down the probes too much.

I think syzygy uses something similar for DTZ? not sure if for WDL

now that I think about it - how is your idea superior to storing 2-bit true WDL for only one side and doing a 1-ply search for the other, that might work as well (and who knows perhaps even compress a bit better since only 3 values out of 4 would be used)

[jonkr]

The endgame neural nets in SlowChess are primarily for board positions larger than 5-man usually multiple pieces and any number of pawns. They are trained on W/L/D result of the sample games so that is similar (though eventually started blending in some search scoring after initial training on some of them.) I do think training a neural net to replace a tablebase could do pretty well for a much smaller size, probably well enough that the difference would be hard to measure. But can't beat perfect, I'm sure I'd end up seeing some loss like maybe in TCEC if I dropped tablebases then want to re-add support.

I plan on trying to use distance-to-mate in the target value to train a mating net (for no-pawns positions) to replace my hard-coded MatingEval function, to see if it can find mates quicker, just as an experiment. But probably won't try specific endgames with only a few pieces.

The SlowChess bitbase for KP-KR is 428 kb, it only stores a win/draw bit. I would have to look to see how else it's stored, my bitbases are from 2005 I think haha. I think the syzygy for that endgame are actually smaller though? I was surprised at how small the syzygy were when I first looked at them.

I remember for some like KPKQ I had some piece position checks and only stored possibly drawn positions so that one is only 40kb.

[hgm]

Nah, draws can be cut off as a real transposition, bit-bases can't, you missed that and snp it.

What are you babbling about? I think you have lost everyone now. But perhaps that is the entire idea.