I was recently wondering about a related question: For various tablebase endings, what is the maximum number of non-capturing/reversible moves available in any position of that ending?smatovic wrote:a basic question:
How many possible, legal moves can i get from one board position?
I thought it were 218, but maybe it is less?
--
Srdja
It has implications for the tablebase generation, if you are using the out-counting method. If you know the "outs counter" for an unresolved position has never overflowed, then you can resolve the position immediately when the counter reaches zero without needing to test all of the successors. I think for 3-vs-2 endings (e.g. KQQKQ) or 3-vs-3 endings, the maximum you could have is 62 or so, so if you use 64+64 values to represent unresolved positions (i.e. 64 for "unknown" and 64 for "unknown but a drawing move has been found"), then you can generate e.g. DTZ50 for all of these endings without worrying about counter overflow. I don't know if existing out-counting generators take advantage of this or not.
But for 4-vs-1 or 4-vs-2 endings, the situation is a bit more complicated. You can't afford to dedicate enough of the byte values to represent unresolved positions to cover all of the outs, so the generator will have to deal with the possibility of overflow for one or both sides. You can always generate the successors to check (but this is slow). I thought of a trick though, that might help for some of them. If your indexing function includes all 64 squares for the least-significant piece (which you might do for simplicity/efficiency reasons in the generator) then at least 2 out of every 64 squares are going to be unused, broken positions. So each 64-byte cache line contains 16 bits where you can store bitflags, with each bitflag covering up to 4 positions. You could set each flag if any of its covered positions had overflowed the counter during initialization. When a counter hits zero, you would check its flag (which is in the same cache line) before generating the successors to verify that they are all actually resolved. If the flag was 0 that step could be skipped.
If you want to get even more clever, you can subdivide the 256 byte values into "unresolved" and "resolved" positions in two different ways, and use the flag to differentiate which format those 4 positions are stored in. So you could have e.g. 63+63 unresolved counter values for most positions, but when any position needs to be resolved with a score too large for that representation (which should be relatively rare), OR if you have to initialize one of them with an out-counter too large to fit, then you could set the flag and convert those 4 positions into the other representation where they have e.g. 32+32 unresolved counter values and more values for resolved (win/loss) scores, and for positions in this second format, you would assume that the outcounter might have overflowed.