DTC Tablebases (or generator) and probing code - Available?

[rjones]

I've been hunting around for DTC tablebases but haven't been able to find any publicly accessible data. There is at least one place where you can probe the tables via a web interface but I'd like to have access to the raw data and probing code. Does anyone know if there are any freely distributable DTC tablebases around (with relevant probing code). Alternatively, a pointer to any table generator code that could generate said tables would also be very useful.

Thanks,
Richard.

[h.g.muller]

I have a version of the generator th source of which is on my website that does DTC. I could send you this source, if you are interested. (It is just a very small modification compared to the dtM verion that is published.) It only does pawnless endgames, though, and it doesn't do anything with the tablebases it generates. (I.e., they are present in RAM as an array, and it doesn't write them to disk.)

I made that code only for acquiring statistics on end-games, to see which combinations of pieces provide a general win over others. DTC is highy favored for that, because it makes it much easier to discount the positions that do not lead to the expected outcome because one of the pieces is hanging, or can be forked or skewered; these all have DTC=1 or 2. So by excluding these short DTC from the statistcs you get a much better impression which end-games are general wins (which might have overall statistics of only 40% won if the losing side has the move). For DTM there is no easy trick to exclude the tactical position; they can have a very long DTM even if they start with capturing a piece, just because the mate in the subsequent phase takes long (e.g. the non-drawn KRKR positions).

[rjones]

Hi,

Thanks, I would certainly like to see the code (I'll PM you my contact details).

Unfortunately for my current uses the pawn endings are probably the most important to me. I'm trying to determine moves which although slower in DTM may still be considered "good" from a human perspective due to leading to relatively quick conversions, and I'm guessing that the situations where this is the case is going to come up much more often in the pawn endings than the pawnless ones. I'd still like to see the code though, especially if you thought it might be extendable to pawn endings without too much effort. If you don't mind me asking, what are the memory requirements of your in memory structures like compared Nalimov space usage? (If I was to use the code I'd probably write something that saved the index to disk, but I'd still be interested in the relative space differences).

As an alternative to modifying your code to handle pawn endings, does anyone have any idea how difficult it might be to modify the nalimov generator to handle DTC instead of DTM? I'd suspect it might be easier than trying to get a non-pawn ending DTC generator to do pawn endings, but I'm new to all this so have no experience to base this intuition on.

Thanks again,
Richard.

[koistinen]

I tried running the code from your website and after changing SIZE and alignment:

Code: Select all

#define SIZE (1<<6*MEN)
for(tb=p;(int)tb&4095;++tb); /* align with cash line         */

it didn't cause a segmentation fault but gave the result:

Code: Select all

79fbb010 79fbc000
KBB_KN
  0.         0         0         0         0   0.000   0.000   0.000
  1.         0         0         0         0   0.000   0.000   0.000
        0 marked win.wtm
        0 labeled potential win(n).btm
        0 verified win(n).btm
        0 checked
0 0

Perhaps you know what is happening? (My OS is 64bit Ubuntu)

[h.g.muller]

If you don't mind me asking, what are the memory requirements of your in memory structures like compared Nalimov space usage? (If I was to use the code I'd probably write something that saved the index to disk, but I'd still be interested in the relative space differences).

The generator uses 1 byte per position (7 bits for the DTC of the btm position, and a single bit to indicat if that same position is won with wtm). It is a bit sloppy with RAM usage, as it assumes that virtual memory that is never accessed don't hurt. So for a 5-men EGT it allocates 256MB, (64^5 / 4, which would be needed is you could not make use of diagonal symmetry), and then uses only 160MB of that (never touching the memory reseved for positions with the white King above the diagonal).

[h.g.muller]

I tried running the code from your website and after changing SIZE and alignment:

Code: Select all

#define SIZE (1<<6*MEN)
for(tb=p;(int)tb&4095;++tb); /* align with cash line         */

I am not sure what you intend to accomplish by changing SIZE. I don't expect the program to remain consistent if you do that. SIZE is not only used to determine the amount of allocated memory, but also for determining when loops scanning through all positions should terminate.

When scanning through all positions, the white King moves in a raster scan rank by rank over the board, but code is added to make it skip the e,f,g,h-files, and all squares above the diagonal. The non-contiguous 'index' that is obtained that way is then mapped onto a more contiguous address range by shifting the upper-most bit two places down. So continuing the scan past the number of positions would probably give unpredictable results, as the only squares below the diagonal are on the e,f,g,h-files.

If your idea is to abandon exploiting any symmetry, the scan logic (in the routine scan()) would have to be changed not to skip any white King (and secondary symmetry piece) positions. This is basically a simplification of the logic, and it can be done by deleting the code responsible for the skipping. It also means that the mapping of the tbindex variable (the concatenated square numbers) onto tbaddres (the actual address in the allocated array) should become an identity.

Fixing the scan is not enough to make it work as a non-symmetrizing generator, though: the code for (conditionally) reflecting the position after a white move would also have to be deleted.

[koistinen]

Yes, changing SIZE the way I did was a bad idea. I did it cause the subtraction looked strange to me and the program crashed before the change but not after.
The alignment code change is more sensible.
What I would like is having the code work correctly on my 64-bit system.
Maybe I'll go look for some 32-bit compilation option of gcc.
(Update: tried gcc -O2 -m32 -march=i386 oldtest.c
and still get segmentation fault, but fewer compilation warnings.)

[h.g.muller]

OK, so te problem is that it crashes. this is stange, as I am using gcc too (albeit on a 32-bit machine under cygwin). I have no compilation warnigs for the version on my webpage (when I compile as 'gcc -O2' that is; when I use -Wall, I get a lot of pedantic warnings about use of parantheses). And it definitely does not segfault.

The only reason for segfaulting I can imagine is that the malloc call in main() to allocate the tablebase array did not work. But I dont see how this could happen; I even test for that.

[koistinen]

Adding:

Code: Select all

#include <malloc.h>
#include <stdlib.h>

and casting pointers to int for printing "%x" makes the warnings go away when compiling with gcc -O2 -m32.
Still crashes though, and when I compile without -O2 it crashes quickly:

Code: Select all

time ./a.out 
e7dbf008 e7dc0000
KBB_KN
Segmentation fault

real	0m1.737s
user	0m1.320s
sys	0m0.376s

$ time ./a.out 
e7e40008 e7e41000
KBB_KN
Segmentation fault

real	0m0.005s
user	0m0.000s
sys	0m0.012s

(First run is after compiling with -m32 -O2 and second is with just -m32.)

[rjones]

There appear to be a few 64 bit issues related to the use of ints and pointer arithmatic used in some parts of the code.
The code worked fine first time for me on my macbook (64 bit intel), but I suspect the apple modified gcc may be using 64 bit values for ints.

The code did not work on 64 bit linux, but changing some types to long got it working for me, namely:

/* (change int to long) */
int codevec[16*MEN];

/* (again change int to long, however only some of these probably need to be 64 bit, I didn't read the code closely enough to find out). */
int i, j, k, *p, nwind, vec, block, stind, unind, ustart,
b, u, uu, h, h2=0666, tbadr, nwadr, nwmask, nwdiag, twice=0, mask2;

/* change from int to long (or maybe even unsigned long) */
tb = (char*)((int)p+4095&~4095); /* align with cash line */

After those changes it worked for me under Linux, but I didn't understand the code well enough to understand how many of these changes were actually required, probably with these changes the memory usage will get needlessly doubled in some places.

Also long probably isn't a good choice if you want it to build on non-linux platforms as under windows long is still 32 bit, but I don't do much C coding these days, so I couldn't recall the names of the ansi 64 bit types.

I Hope the above info allows you to more easily diagnose exactly which of the 64 bit integer issues are real problems and which are not.

Thanks again for the generator code.

Regards,
Richard.

[h.g.muller]

Unfortunately my long post had not stuck untder the ctrl-c when the server failed, so let me just say this:

MAX should be difined as MEN+2 rather than MEN+1, for the array holding the name of the EGT not to overflow.

[rjones]

From what I could see, the 32/64 bit issues could have lead to scribbling on memory in some situations, so the crash may well occur in different places depending on what optimisation (or other compiler) flags etc are on (I built with debugging and could see that the tb pointer had become corrupted in my case).

Regards,
Richard.

[h.g.muller]

In my case it was the (FILE *) pointer to the stats file that was corrupted because the terminating 0 of the name string was written into it. This led to an immediate crash, as the first thing the generator does is write the name of the EGT to the stats file.

I guess the optimization level also affects the allocation of variables (e.g. eliminating unused variables, or variables that the optimization process could replace by registers). Also the order in which statements are executed might change, if they are not supposed to affect each other (but do if you exceed array bounds...).

[rjones]

Hi h.g,

Is your ubuntu machine running 32 bit or 64 bit?
I'm fairly sure this line alone with cause major problems on 64 bit:
tb = (char*)((int)p+4095&~4095); /* align with cash line */
as the cache alignment code will definitely be truncating p in some situations under linux where an int will be 32 bits even on a 64 bit machine (how badly this impacts you might depend on how much memory you have)..

Richard.

[h.g.muller]

Is your ubuntu machine running 32 bit or 64 bit?
I'm fairly sure this line alone with cause major problems on 64 bit:
tb = (char*)((int)p+4095&~4095); /* align with cash line */
as the cache alignment code will definitely be truncating p in some situations under linux where an int will be 32 bits even on a 64 bit machine

I compiled with the -m32 flag. I am not sure if this Ubuntu normally runs in 64-bit mode, I never really used it for anything except testing the hard-drive speed. A 64-bit compiler should at least produce the warning against casting a pointer to too small an int format.

If you want to run it for upto 5 men (which it also can do in 32-bit mode) I think this is really the only place that would need fixing.

I think if int everywhere in the program is replaced by a 64-bit int type, and the constants are written such that they also are 64-bit (I am not sure if this require suffixing them with L or LL, e.g. (1LL<<6*MEN-2)), it will probably be possible to set MEN to 6 (if you have the required memory; it will allocate 16GB virtual memory and use 10GB of that if you do it). You would also have to add 2 extra digits to the bitmasks for FILES and RANKS. The program never assumes anything about the size of the ints it is using, only that they won't overflow. (And in that one place that they can hold a pointer.)

[rjones]

Thanks for the extra details h.g.

Regards,
Richard.