CCRL Discussion Board

Hi,

First off: sorry for this rather long post.

I know there are a lot of tablebase formats out there already, but I started ny own little project, to get a better understanding of the process.
Also I am learning C# as a bonus (I know it is not as fast as C++, but I want a GUI, and that was a lot easier in C#, and I never was able to read C++ very well, and I will need C# for work soon).

I have tried reading some of the theory on the internet about the topic of retrograde generation, but sadly I am unable to understand most of it
So, I am relying on my own sense of logic, and programming skills.

So far I have made the basic GUI, and I have a working prototype of the generator that, in theory, could build any base with as many as 9 or 10 men, with pawns on one side only (no e.p. capture support yet).
It would take a very long time to do so, but it should work, and it does not require everything to be in RAM when generating the bases.
So far I have only tested 3-5 man bases, and it produces results consistent with Nalimov's numbers.

I am using DTM metric, as that was the easiest to understand.

My current implementation looks something like this:
1) Allocate the file, and set all positions to Unknown.
2) Go through all positions, and mark them as Checkmate, or Broken as per the standard definitions.
3) Look for checkmates:
3.1.1) Find a position that has a value of Unknown.
3.1.2) Loop through legal moves, and see if we can get to a mate position, and if so, mark the position as a win-in-1.
4) Iterate:
4.2) Iterate for losses:
4.1.1) Find a position that has a value of Unknown.
4.1.2) Loop through legal moves, and see if we can AVOID getting to a loss-in-n position, and if NOT, mark the position as a loss-in-n.
4.2) Iterate for wins:
4.2.1) Find a position that has a value of Unknown.
4.2.2) Loop through legal moves, and see if we can get to a loss-in-n position, and if so, mark it as a win-in-(n+1).
5) Repeat step 4 until neither search mark any positions.
6) Compress, and generate statistics file.

This appear to work just fine, but it is painfully slow.

I tried making use of generating take back moves, and implemented step 4 from above like this:

4) Iterate:
4.2) Iterate for losses:
4.1.1) Find a position that has a won-in-n value.
4.1.2) Generate take back moves for the other side
4.1.3) For each move: Take it back, swap sides, then loop through legal moves, and see if we can AVOID getting to a loss-in-n position, and if NOT, mark the position as a loss-in-n.
4.2) Iterate for wins:
4.2.1.1) For loss-in-n positions:
4.2.1.2) Generate take back moves for the other side
4.2.1.3) For each move: Take it back, swap sides, and set all positions that has an Unknown value to win-in-(n+1).
4.2.2) For Unknown positions:
4.2.2.1) Generate captures and Promotions.
4.2.2.2) For each move: If we can get to a loss-in-n, set the current position's value to win-in-(n+1).

This is much faster, but unfortunately doesn't work as intended, producing invalid results, and I cannot figure out whether my reasoning is wrong, or I made a coding mistake somewhere.
Any sort of help with this would be appreciated, whether it is comments on the methods used, or an explanation of the correct method in plain English, or a link to an explanation in plain English.
Feel free to comment, or ask any questions you like about my problem, or my project in general.

Have a nice day.

Dan Wulff

Hi Dan,

Here is a standard technique for finding bugs in a tablebase. Iterate through all positions in a finished tablebase. For each position, make all possible moves, including captures and promotions (search 1 ply deep). Compute the position value based on this search, and compare with the stored value. If it differs from the stored value, something went wrong during generation. Knowing which positions are solved wrongly may give useful clue about why it happened.

This kind of verification is not a guarantee that the tablebase is bug-free (e.g., some bug can be shared between solving and verification code), but it an absolutely necessary first step towards a correct tablebase.

If many positions are affected, you can choose some that is closer to checkmate (so it is solved earlier in generation), and investigate it. E.g., using printf debugging, print a status every time the position is touched during solving.

If you store all positions, and store them on disk, the code should be fairly straightforward. Most of complications result from 1. Trying to keep as much as possible in memory and minimize disk access. and 2. Storing as few positions as possible (e.g., not storing redundant and illegal positions).

Good luck!

Your second method is roughly what I use in my solvers, it's called the "grandfather method". Is is described a bit here: https://chessprogramming.wikispaces.com ... #Algorithm and also in 1986 Ken Thompson's paper.

Hi Kirill,

Thanks for replying.

The description you point to for the "Grandfather method" leaves some questions.
First of all, I dont understand the part about it being illegal to start in check...
If the side NOT to move is in check, the position is broken, right ?
Otherwise legal un-moves would defend against a check, or am I wrong here ?

Verifying the base is not the problem, I know there are errors in it, but I am trying to find out whether I am looking for a coding issue, or if my method (as described above) is the source of the errors.

I think your second method is in principle correct.

Your algorithm can still be improved though. One improvement is to not immediately check whether a position that might be lost is actually lost, but mark such positions as "potential loss" and check them for being a real loss in the next iteration. Another improvement is to probe all captures only once at the very beginning.

I'll try to formulate an algorithm based on my DTZ generator.

We have two tables, one for white to move (wtm) and one for black to move (btm).
First we set all positions to unknown.

Now we find illegal positions in wtm by looping through all positions with the black king removed and "uncapturing" the black king in all possible ways with white pieces. Same for btm.

If a position in the wtm table is illegal and in the btm table is legal (i.e. the position with btm is legal but in-check), then we set the position in the btm table to loss-in-0. We do the same for in-check positions in the wtm table. These are potential mate positions that still have to be verified.

Then we initialise captures by removing each non-king piece, looping through all (legal) positions with that piece removed, probing the value of the position and performing all "uncaptures" of the piece by the other color. If a table position is unknown, set it to the probed value (sign reversed). If a table position has a value unequal to unknown, set it to the probed value (sign reversed) if that value is better.

At this point, the value of each legal position will be either unknown, draw, win-in-n or loss-in-n. These are all provisional values: win-in-n means that a capture exists that wins in n. draw means that a drawing capture exists. loss-in-0 means in-check (and no legal capture exists), loss-in-n means that the best capture loses in n, unknown means that no captures exist from that position. So at this point, all values unequal to unknown are just lower bounds.

Now we start doing iterations. We set n = 0 and first loop through the wtm table, then through the btm table.
Looping through the wtm table do for each position:
- if win-in-n, take back moves and change "unknown" positions in the btm table to loss-in-n [this does nothing if n = 0, but that's ok];
- if loss-in-n, check whether the position is really a loss-in-n by trying out all non-captures
- - if it is, take back moves and set positions in the btm table to win-in-(n+1) (unless their value is win-in-k with k <= n);
- - if not, set the position to unknown;
Looping through the btm table do for each position:
- if won-in-(n+1), take back moves and change "unknown" positions in the wtm table to loss-in-(n+1);
- if loss-in-n, check whether the position is really a loss-in-n by trying out all non-captures
- - if it is, take back moves and set positions in the wtm table to win-in-(n+1) (unless their value is win-in-k with k <= n);
- - if not, set the position to unknown.
Increase n by one and repeat.

When done, set all remaining "unknown" values to draw.

Hi,

Thanks for the algorithm.
Sorry for being so long to reply, but I have not been working on the generator for several month for personal reasons, and now I am trying to get back up to speed.
I have tried your method, but I cannot seem to get it working.
I have been debugging for quite some time now, and cant see that I made a mistake anywhere.

I have a hard time understanding why you would NOT treat wtm and btm positions the same, wont that be an issue for classes with equal material, e.g. KQ vs. KQ ?

Also I am wondering if you made a typo in the second part, where you wrote: "(unless their value is win-in-k with k <= n);". Shouldnt that be k<=n+1 ?
I already tried that, but it makes no difference. I cant make KQ vs .K work using my understanding of the specified algorithm.
If it is not too much trouble, could you double check your previous reply, to make sure the algorithm is accurate ?

Completely unrelated to that problem, but also on the subject of equal material on both sides:
If you have the KQ vs. KQ class generated, isnt it possible to rely on the wtm table exclusively, then if you have to probe a btm position, simply flip the board+ep. square , swap the colors for all pieces, do a lookup for wtm, and return the result with sign reversed ?
That would save a good deal of space, I think.
Is my assumption correct, or am I just being silly ?

Thank you for your time.

Dan

Wulff wrote:Completely unrelated to that problem, but also on the subject of equal material on both sides:
If you have the KQ vs. KQ class generated, isnt it possible to rely on the wtm table exclusively, then if you have to probe a btm position, simply flip the board+ep. square , swap the colors for all pieces, do a lookup for wtm, and return the result with sign reversed ?
That would save a good deal of space, I think.
Is my assumption correct, or am I just being silly ?

It works, and I assume most TB implementations also do that. At least mine does. But I don't think it is very useful to use this trick during generation, because it would be a lot of special code for dealing with a small subset of all tables.

Also I am wondering if you made a typo in the second part, where you wrote: "(unless their value is win-in-k with k <= n);". Shouldnt that be k<=n+1 ?

It makes little difference: if the value is n+1, then setting it to n+1 is the same as doing nothing. So yes, you can take k <= n+1 there, but the important thing is not to overwrite values win-in-k with k <= n.

I have a hard time understanding why you would NOT treat wtm and btm positions the same, wont that be an issue for classes with equal material, e.g. KQ vs. KQ ?

I'm not really treating them differently, I'm treating them slightly asymmetrically.

wtm and btm start out equally.
Now I loop through wtm and work through 1 ply on the basis of what is in btm. As a result, wtm is 1 ply ahead of btm.
Then I switch to btm and can work through 2 plies on the basis of what is in wtm, because wtm is 1 ply ahead. When I finish this iteration, btm is 1 ply ahead of wtm.
So now I switch back to wtm and can work through 2 plies, because btm is 1 ply ahead.
And so on.

For the end result it does not matter. But my approach is about 2x as fast as doing 1 ply per iteration (first all loss-in-0s for both wtm and btm, then all win-in-1s for both wtm and btm, then all loss-in-1s for both wtm and btm, etc.).

This works for me: I think it is still the same as what I wrote above.

Hi,

Thanks for your reply, I'll keep working on it.

About symmetrical material: I was not talking about using it during generation, only to save space after generation is done. Thanks for confirming hat it works.

Hi Dan,

I saw your post only now since I do not visit this board very often (this might even be my first post here, usually I post on TalkChess). Your algorithm appears to generate captures and promotions only in the "Iterate for wins" part. Shouldn't it be better to do this in the "Iterate for losses" part as well, since a capture or promotion of the losing side may be part of the opponent's winning strategy?

Just a thought ... Maybe I have misunderstood your algorithm, in that case please accept my apologies.

Hi,

As mentioned in another post, I am back to working in my own Endgame generator again.
The method as posted by Syzygy earlier is working like a charm.
I have managed to get a working 3-piece generator (I think) at least I have not found any bugs yet.

I am using the a1-d1-d4-a1 triangle scheme when doing endgames without pawns.
I am also employing that scheme during generation to save space.
I am wondering if that is a bad idea.
I was having problems with the reflection on the diagonal, so now I, in addition to updating position with the white king in the a1-d1-d4 triangle, I also do a mirror on the diagonal when the white king is ON the diagonal.
This seems to fix the problem, at least for 3-man bases.
However, when I try to do e.g. KRKN it messes up.

Am I on the right track about doing an extra diagonal reflection when the white king is on the diagonal, and what more do I need to do ?
Hoping for a reply from the experts.

Thanks in advance.

Wulff wrote:I am using the a1-d1-d4-a1 triangle scheme when doing endgames without pawns.
I am also employing that scheme during generation to save space.
I am wondering if that is a bad idea.

No, that is a good idea.

I was having problems with the reflection on the diagonal, so now I, in addition to updating position with the white king in the a1-d1-d4 triangle, I also do a mirror on the diagonal when the white king is ON the diagonal.
This seems to fix the problem, at least for 3-man bases.
However, when I try to do e.g. KRKN it messes up.

Am I on the right track about doing an extra diagonal reflection when the white king is on the diagonal, and what more do I need to do ?

If you restrict the white king to a1-d1-d4 and leave the other pieces unrestrained, then all positions with the white king on the a1-d4 diagonal will have a mirror position.

I think what you need to do is this: if you "backmove" the white king onto the diagonal from a position not on the diagonal when updating table values, you need to apply the update to both mirror positions. This is because the position you come from, with the white king not on the diagonal, only occurs once in the table, whereas the position you backmove to occurs twice. If the white king backmoves from one diagonal position to another (e.g. Ka1b2), then you don't need to check because you will cover both positions anyway.

If in KRKN you are processing a backmove of the R, N or black K, then again you don't need to specifically check for mirror positions because you will loop anyway over both positions, because the white king is and remains on the diagonal.

Thanks, I finally found that damn bug

I can now generate bases with pieces on both side (other than the black king)

One more thing, though: During generation I am also encoding multiple pieces of the same type and color (up to 4 pieces) as one "piece configuration", that shouldnt matter either, as far as I can tell, or am I wrong here ?

Wulff wrote:One more thing, though: During generation I am also encoding multiple pieces of the same type and color (up to 4 pieces) as one "piece configuration", that shouldnt matter either, as far as I can tell, or am I wrong here ?

For, say, KRRvKQ it is certainly possible to use an indexing scheme that assigns a unique index to positions with the two white Rs interchanged.

Hi again,

One thing I have been putting off, but which I can no longer avoid is e.p. captures.

I have been thinking about just ignoring them during generation, and then do a two (or three) position lookup when an e.p. square is present in the lookup request.
Is that the way to handle it, or is there something better/easier/cleaner that I can do ?

Wulff wrote:One thing I have been putting off, but which I can no longer avoid is e.p. captures.

I have been thinking about just ignoring them during generation, and then do a two (or three) position lookup when an e.p. square is present in the lookup request.
Is that the way to handle it, or is there something better/easier/cleaner that I can do ?

Ignoring them does not work, since that would break the tablebase for positions that may still result in an e.p. capture.

However, you do not actually need to store values for the positions with a legal e.p. capture. In your probing code you could test whether the position has an e.p. capture and, if so, just do 1 ply of probing (or - somewhat more tricky and bugprone - calculate the correct value on the basis of the value of the position without e.p. capture, the value(s) of the position(s) after the e.p. capture(s), and on whether the position would be stalemate without e.p. capture).

How you deal with e.p. captures will depend on how you deal with pawns in general. My generator basically treats each pawn constellation as an independent tablebase where only the pieces can move, initialised with the values of captures and pawn moves. It is then not too difficult conceptually (but still rather tricky) to initialise the positions that have a legal double pawn push (i.e. the positions immediately before positions with e.p. captures), basically by performing the double pawn push (giving a position e.p. rights) and determining its value (by a 1-ply search or the more tricky/bugprone approach). This way you don't have to store the positions with e.p. rights.

To make this pawn-slice-by-pawn-slice generation work, you have to make sure to generate the pawn slices in the correct order. So white pawns start on a7, then a6, a5, etc. (Or a7, b7, c7, d7, a6, etc.). Black pawns start on a2, etc.

If you don't generate by pawn slices and treat pawns as other pieces, then I have to think about whether a similar approach is still possible. Unmoving double pawn pushes correctly will need some thought. I'm afraid it does not really fit into the scheme I set out in my first post in this thread (i.e. without pawn slicing and without storing in the table, at least during generation, a separate set of values for positions with e.p. rights).

So, without pawn slicing, it seems easier (and it may be necessary) to include in the table (at least during generation) an area for positions with e.p. rights. Then you simply make sure not to unmove double pawn pushes from position without e.p. rights but only from the equivalent positions with e.p. rights (since doing a double pawn push would give the position with e.p. rights). With this approach, unmoves to a position with an e.p. and a non-e.p. variant need to be made to both variants. You don't really have to care about whether the "e.p." variant of a position with a white pawn on rank 4 or a black pawn on rank 5 has legal e.p. captures. If it has no such captures, its value after generation will simply be the same as that of its "non-e.p." variant.

Hi,

Thanks, since the post I've been doing some more work, and some more thinking on the subject.
You are right, obviously, that ignoring e.p. rights will not work.
I am treating pawns the same as any other piece, so no pawn slices, and I have made room in my data structure for two values, if there are pawns on both sides.
I am going to experiment a bit, and I may get back to you if I have any further questions after that.