Help needed with tablebase generator

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Help needed with tablebase generator

Postby Wulff » Sun Apr 10, 2016 12:12 am

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
Wulff
 
Posts: 47
Joined: Thu Jan 05, 2006 4:08 pm

Re: Help needed with tablebase generator

Postby Kirill Kryukov » Thu Apr 14, 2016 9:42 am

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!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Help needed with tablebase generator

Postby Kirill Kryukov » Thu Apr 14, 2016 9:54 am

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.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: Help needed with tablebase generator

Postby Wulff » Wed Apr 20, 2016 12:04 pm

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.
Wulff
 
Posts: 47
Joined: Thu Jan 05, 2006 4:08 pm

Re: Help needed with tablebase generator

Postby syzygy » Sat May 07, 2016 10:30 pm

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.
syzygy
 
Posts: 159
Joined: Sun Aug 03, 2008 4:02 pm

Re: Help needed with tablebase generator

Postby Wulff » Sun Oct 23, 2016 4:15 pm

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
 
Posts: 47
Joined: Thu Jan 05, 2006 4:08 pm

Re: Help needed with tablebase generator

Postby syzygy » Thu Oct 27, 2016 10:37 pm

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:
Code: Select all
  // dtm_iter = n:
  // looping white: from white win-in-n, find potential black loss-in-n
  //                verify white loss-in-n and find black win-n-(n+1)
  // looping black: from black win-in-(n+1), find potential white loss-in-(n+1)
  //                verify black loss-in-n and find white win-n-(n+1)

I think it is still the same as what I wrote above.
syzygy
 
Posts: 159
Joined: Sun Aug 03, 2008 4:02 pm

Re: Help needed with tablebase generator

Postby Wulff » Fri Oct 28, 2016 7:29 am

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.
Wulff
 
Posts: 47
Joined: Thu Jan 05, 2006 4:08 pm

Re: Help needed with tablebase generator

Postby Sven Schuele » Mon Dec 19, 2016 4:30 pm

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.
Sven Schuele
 
Posts: 1
Joined: Mon Jun 13, 2011 10:02 am


Return to Endgame Tablebases

Who is online

Users browsing this forum: Baidu [Spider] and 2 guests

cron