Help needed with tablebase generator
Posted: 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
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