Syzygy bases from memory

[mar]

I suppose one could view it as a problem of finding the one bits in a (very) sparsely populated bit stream. For (very) simple endings, there'll be quite some periodicity in the stream, you could probably construct the stream using variables like stm and distance to queen and so on. Or, why not reverse the problem, brute force find the variables and the polynomial connecting them backwards off the bit stream. Probably PyTorch or Scipy will do it for you. I jest, alhough something may be possible. Then put that in your evaluation and smoke it.

I guess everything will depend on how the bits are distributed.
one could improve the binary search over indices by reserving n bits for repeat count, like 3 bits and then you save up to 7 indices in cases where there are 8 consecutive draw bits sets or something like that
but as hgm said, sometimes even log n is just too slow, I don't know.

EDIT: if the assumption that there are lots of repetitive patterns is true, one might do even better by having and extra lookup table, say for each n bits and simply store a starting bit index for the entire group. assumining uniform slicing, one might save some space while still retaining O(1) lookup, if such slices are sufficiently large, but all this would have to be tried I guess, perhaps there's more to it

also, if I'm not mistaken syzygy only stores the tables for one side and uses 1-ply search for the other, effectively cutting the data in half, but I may be wrong on this

[Rebel]

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?

Simple hashing + binary search is how I currently have it, just to see if it works, and it does. The complicated way -> bitbases may follow, but only if there is a need for that.

[hgm]

You have an uncommon notion of simplicity. The bitbase solution is completely trivial: calculate the index (e.g. by concatenating the square numbers of the pieces), and probe the corresponding bit (e.g. EGT[index>>5] & 1<<(index&31)). What you advocate amounts to a conversion of a bitbase to a cumbersome format that is an order of magnitude larger as preparatory work, and a complex probing mechanism that requires a complex search process that requires many probes to this bloated amount of data.

[chrisw]

You have an uncommon notion of simplicity. The bitbase solution is completely trivial: calculate the index (e.g. by concatenating the square numbers of the pieces), and probe the corresponding bit (e.g. EGT[index>>5] & 1<<(index&31)). What you advocate amounts to a conversion of a bitbase to a cumbersome format that is an order of magnitude larger as preparatory work, and a complex probing mechanism that requires a complex search process that requires many probes to this bloated amount of data.

You’re missing the point. We all know and Martin has described that indexing the sparse cases will only sensibly work if the sparse cases are very few. The concept was avoid using EGTs and fix the holes in HCE code. Simple ending, KRKP for example, can be defined by HC rules, square of king, stm and so on. Ed’s concern were certain special cases where either his HCE rules were not enough, or they were mal-functioning. If he can trap (exhaustively presumably) all draw cases where his rules fail, then he can both fix or write more rules until he is left with just a few special cases, which he can then index. If they are few enough he has a workable system. Some people may have other ways to spend their time, but as a chess programming exercise it has maybe some merit and may be extendable. Or not, but throwing the whole concept out based on superficial reading of the problem in repeat posts is not useful.

[hgm]

It might have started with that for KPK, but when the discussion progressed to KRKN, KRKB and KRKP, I understood the idea is to rely on a table entirely. I wouldn't know any simple rules for KRKN. For KPK the rules are pretty straightforward. But even then it is a pain to accurately cover every possible case, and if you need any kind of table for exceptions at all, you might as well load the entire EGT, as it is only 24KB.

BTW, one trick for a rule-based evaluation I did not mention yet is tu use the ply counter. The point is that the default evaluation of a certain material combination must be a compromise between the statistics and the speed of resolution. E.g. KRKP is in most cases won. And then it just takes a few moves to gobble up the Pawn. OTOH, in cases where it is draw you need a much deeper search to see that. And if you score it as a win by default (which is statistically the most accurate), you would have a wrong score in draw positions until you have searched deep enough to force the draw.

This can be remedies by assuming a win for low value of the ply counter, but a draw for somewhat higher value. Then you only have to search up to that value in a drawn position to get the correct score. Presumably you can take the counter value where the transition occurs high enough such that won positions would never exceed it before they make the winning conversion.

A similar method works in end-games like KQKP when you keep a counter that resets on King moves. (Or, more generally, when you switch to moving another piece as on the previous turn.) You can then score the position as a win for low counter value, but as a draw after some higher value. That way you would see the draw in drawn positions much faster than when you have to search all the way to a 50-move draw or repetition (which in KQKP can also be avoided almost indefinitely).

[Rebel]

You have an uncommon notion of simplicity. The bitbase solution is completely trivial: calculate the index (e.g. by concatenating the square numbers of the pieces), and probe the corresponding bit (e.g. EGT[index>>5] & 1<<(index&31)). What you advocate amounts to a conversion of a bitbase to a cumbersome format that is an order of magnitude larger as preparatory work, and a complex probing mechanism that requires a complex search process that requires many probes to this bloated amount of data.

It seems that what's complicated for you is simple and elegant for me. 1) it's faster code and 2) I don't have to load 4-6 bitbase files into memory at program start, just one, 3) no different sub-routines, just one. I don't want to argue about programming style, each has his own.

[hgm]

Faster code? You search through a table of 3.8M positions, not? That requires 22 accesses in a binary search, rather than 1. Or do you store these positions in a hash table?

I don't understand your remark about 4-6 bitbases. Why would anyone load 6 bitbases if he needs 1?

[Rebel]

Have a look at the bit-base source code of Scorpio and Slowchess, then you will understand.

[hgm]

How is that relevant? The reference code is the code I already gave above:

Code: Select all

int index = location[wKing] | location[wRook] << 6 | location[bPawn]-8 << 12;
int isDraw = EGT[index] >> location[bKing] & 1;

If your code is faster than that, it would be very interesting to see how you manage that. Any code that is much slower seriously sucks.

[Rebel]

Working code never sucks.

Example:

[d]8/2P5/8/K7/8/8/8/k1q5 w - - bm Kb6; ce 0; acd 1;
This is the first of the ~125,000 draw positions of the KQKP endgame stored in the TT together with the best move Kb6 to guide the search.

Unbeatable IMO.