Oh, sorry, this is wrong. I am off by a factor 8. A 6-men only requires 1GB is it is reduced by 8-fold symmetry. A symmetry-less 6-men would be 8GB. Little hope fitting 2 of those in RAM, and then some stuff. So I guess that for building 7-men with a single Pawn we still have to resort to disk storage.
But 5-men P-slices should be very doable. Only 128MB per bitmap.
tpetzke wrote:I guess if I finish to find all the Mated in X positions and only then process their predecessors it will work, but I thought it is sub-optimal.
It sounds like it, but I think it's actually not so bad. The thing is, if you assign it a score now and then you find that it isn't optimal, you need to update it (and depending on how you implement it, its children) and you wasted the initial work you did when you assigned it the wrong score.
hgm wrote:Oh, sorry, this is wrong. I am off by a factor 8. A 6-men only requires 1GB is it is reduced by 8-fold symmetry. A symmetry-less 6-men would be 8GB. Little hope fitting 2 of those in RAM, and then some stuff. So I guess that for building 7-men with a single Pawn we still have to resort to disk storage.
That goes down for the more common (?) case of multiple pawns, right?
Sure. If the number of men would be fixed. But with multiple Pawns you would not be satisfied to do just 7-men. So the important matter is how many non-Pawns there are, and the number of Pawns you can then afford with them is mainly determined by how blocked or mobile they are.
I guess a good initial target would be to get it working for 4 non-Pawns. (Like the important KRKR.) Then each P-slice would only be 2MB. The problem, however, is that you must unavoidably enter KQRKR in order to win. This has 5 non-Pawns. And so many Pawns in addition to that that you cannot draw on any pre-existing knowledge for those tablebases. So you also must prove that it is indeed won after any forcible promotion. What should save the day here is that the end-game is now so unbalanced that you can do it without further Pawn moves, and without allowing an opponent promotion. (It is probably expecting too much to do it without even allowing opponent Pawn advance.) That severely limits the number of KQRKR P-slices that you would have to calculate, and prevents conversion to KQQRKR or KQRKQR 6-men slices. In case the opponent would have an advanced Pawn in the 5-men P-slice, the only option to stay within the artificial restrictions would be to sac your Rook for it. Which should still be winning, unless he would have two very advanced Pawns. But after the Rook sac it should at least not be difficult to figure out if it is winning, as now you are back to 4-men KQKR P-slices, with also one mobile Pawn gone.
But to do interesting 4-men endings, the 5-men slices with extra white Q do play a crucial role.
I changed the algorithm a bit. Now if I generate the retro moves for a newly found Mated in X position I store the winning sores not directly in the table but in a newlyWon table. So in the current iteration those scores are not yet considered in the search of Mated in X positions.
At the end of the iteration I store the newlyWon scores back to the main table if they are better than the current entry there.
This helps a lot, it is still not perfect. Some scores are still off by a move, but I don't see Mates in 30 anymore in the KQK table.
I wonder what would be a faster method for treating the black-King retro-moves to generate potentially-lost positions from the newly-won bitmap. If 64 entries of the EGT that differ only in black-King location are stored in the same word (a 'King bundle'), the King retro-moves should set all 8-bit rings around the newly-won bits. One way to do that is extract the set bits one-by-one, and for each of them OR in the corresponding king-attacks bitboard. The other way would be to treat all positions in bulk, shfiting the newly-won bitboard along the move step, and looping over all moves to OR them together.
I guess this depends on the average number of bits that are set in the newly-won King bundles. In very sparse iterations, you would be lucky to find a bit set, and extracting that only bit and looking up the attack set would be way faster than 8 shifts, 6 ANDs (to mask off bits that wrapped around the edge) and 7 ORs. If there would be on average, say, 8 set bits in a newly-won King bundle, extracting all 8 of them and doing 8 attack-set lookups and ORs would probably be more expensive. So it could depend on the end-game and stage of generation.
If I consider KQKR and KBNK as typical examples of generally-won end-games, I see that at the peak of KQRK 1.2M of the 16M positions are newly-won (7.5%, i.e. 5 per 64-bit word), while for KBNK this is 1.5M (6 per word). More typical during the generation is 0.25M newly won per iteration, which is only a single bit per King bundle. So I guess extracting the individual positions would never hurt very much.
Verification can always start by ANDing off bits of the potentially-lost set with won-so-far bitboards shifted by a King move. This should almost always be faster than extracting individual potentially-lost bits, and detecting the overlap of the corresponding attack sets with the won-so-far bitmap. Because typically even a King bundle with only a single position in it would already lead to 8 potentially-lost positions next to that King, which then would all have to be extracted. So bulk verification by shift, OR and AND for each King step would already be faster. Especially since the verification os subject to beta cutoff: You could test after each shift-OR-AND step whether the board is now zero, and stop when it is.
Ok, so several rewrites and cleanup sessions later, my code is significantly faster than it was, but it still takes a full two seconds to build KBNK. If I can beat that down to under a second I'll consider it a success and ready for the next step.
The problem is figuring out where the bottleneck is. The profiler is pretty unhelpful. It could be the recalculation of the index from scratch (I hope not), but using function pointers to generate all moves may also be suboptimal.
I tried using bitlists to speed up the finding of newly won and lost positions, but it didn't help when I tried it. However, that was a couple of iterations ago, so I may give that another try too.
I'm also fighting in a similar area, I try to get the three 3mens as fast as possible. The way I generate the tables introduces some inconsistencies, so when the table is filled (no new mate in x and mated in x are found) I have to loop through the table several time to correct the scores.
A position stored as Mate in X has a move that leads to a Mated in X-2. When this is corrected some other Mated in X positions now are not consistent anymore. In the KPK endgame it takes 8 loops to get the table consistent which contributes a good deal to the overall time.
I don't know whether there is a method that generates a consistent table from the beginning and whether this is then faster in total.
I guess you are too quick to treat the parents of decided positions. In a 'synchronised' algorithm, where you do not start assigning mated-in-(N+1) before you are sure you have assigned ALL mated-in-N things like you describe can never happen.
If you scan through the EGT and just start treating any position (by deciding parents) that was freshly decided, you run the risk of getting ahead of yourself. It is quite likely that a parent of a position you are treating is behind that position, so that you will still encounter it in the same scan.
1. Init the table with Mated positions, Draws by capture and Stalemate and in the PKP case handle positions with promotions.
In that phase also for every mated position I retro generate the Mate in 1s. I guess this is save.
2. Now in a loop until no more mated positions are detected
-> take an yet unknown position and check in the table whether all moves lead to a Mate in ? position. Then make this position the best Mated in X position and store it in the table.
-> also if such a new position is found generate the retro moves and put a Mate in X position in a separate "newlyWon" table. If in this table already an entry is present replace it only if the new is better.
-> if all entries in this round are processed copy the entries from the newlyWon table into the main table
-> start a new round
This way I don't use newly won entries in the current round in the search for Mated positions, yet some inconsistencies appear.
A 6-men only requires 1GB is it is reduced by 8-fold symmetry. A symmetry-less 6-men would be 8GB. Little hope fitting 2 of those in RAM, and then some stuff. So I guess that for building 7-men with a single Pawn we still have to resort to disk storage.