Previous Next About my new 7-men generator
Below you find the C source of a somewhat streamlined EGTB generator. It is basically the same as the one on the main EGTB page, but has some refinements that speed it up. One is that in the verification step, in stead of stopping at the first move that black has to an undecided position, it completes all moves to count how many of such 'escapes' black exactly has. It stores this 'escape count' in the tablebase entry for the position, encoded in such a way that it can be distinguished from a DTM (using negative numbers for it). In later iterations, it then only has to decrement the count, in stead of generating moves and following them up to probe the tabebase. If the excape count hits zero, the position is verified as lost to black, otherwise it remains undecided (so the escape count can stay stored in it).
This saves a lot of time in generally won end-games, as in the end (in the iteration that declares the position won) all black moves would have to be generated and probed anyway, and it is not any slower to do that in the beginning. But there will be many earlier iterations that would generate (and probe) part of those same moves over and over again, before they found one that led to an undecided position. Only for generally drawn end-games it slows matters down, as you would invest in counting all escapes for many positions that would not ever be indicated as 'potentially lost', and so would nver have to be verified.
In the case where there are very many won positions found per iteration, (like KQQKQ), it pays to treat the positions reached through retrograde moving in bunches differing in black-King position, as these are cached together. If many of them get decided in the same iteration, it saves time labeling them all while they are still cached, rather than having to load the same cache line several times. In end-games where only a very small number of positions get decided per iteration, most cache lines contain only one position that has to be labeled, and the strategy of bunching does not provide any advantage. (But it doesn't cost anything either.)
/************************************************************************/
/* Pieces-Only Tablebase Generator, by H.G. Muller */
/************************************************************************/
/* Working version, 8-symmetry, but uncompacted. 2-pass strategy. */
/* counts escape moves, and makes position won.btm if count reaches zero*/
/* This version counts up until count reaches 256. check/stalemate=2/1 */
/* Version that does batch processing black King positions in pass 1 */
#include <time.h>
#include <stdio.h>
#define MEN 5
#define SIZE (1<<6*MEN-2)
#define MAX MEN+1
#define BOX 0x80
#define LABEL 0xFE
#define RANKS 07070707070
#define FILES 00707070707
#define TICK (1./CLOCKS_PER_SEC)
#define board (bord+9) /* to allow negative index */
/* piece names */
#define K 4
#define Q 7
#define R 6
#define B 5
#define N 3
int nblack = 2; /* number of black pieces */
int piece[MAX] = {K,N,B,B,K}; /* desired end-game: */
int pos[MAX]; /* black pieces first, */
int stride[MAX]; /* kings first and last! */
char exch;
char bord[138];
int tbindex;
int cnt, cnt2, sample1, sample2;
clock_t t;
unsigned char *tb, *tbdir, *tbdir2, *tbh;
char ii;
int mcnt, lcnt, ccnt;
int histo[128];
unsigned char stack[64]; int sp, op;
int boardvec[] = {1,-1,16,-16,0,1,-1,16,-16,15,-15,17,-17,0,
14,-14,18,-18,31,-31,33,-33,0}; /* step vectors for 0x88 board */
int basevec[] = {1,-1,8,-8,0,1,-1,8,-8,7,-7,9,-9,0,
6,-6,10,-10,15,-15,17,-17,0}; /* step vectors for 64-board */
int first[] = {4,4,4,14,5,9,0,5}; /* vector directory per piece */
char rclass[]={0,0,0,0,0,1,2,3,4,5,6,7,8,0,9,10,11,12,13,14,15,16,0};
int codevec[16*MEN]; /* step vectors in TB index */
int classvec[24];
zgen(int start, int stop, int task, int n, int tbind, int symmask, int diag)
/* move generator, for both forward and backward moves. The forward */
/* moves can capture enemy pieces, the backward moves can 'uncapture' */
/* i.e. leave any of the captured foes on the square they 'came from', */
/* or leave it empty. Uncapturing a king is mandatory (finds checks). */
/* THERE ARE NO PROVISIONS FOR PAWNS WHATSOEVER; PIECES ONLY! */
{
int i, j, k, *p, nwind, vec, block, stind, unind, ustart, ecnt=0, s,
b, u, uu, h, h2=0666, tbadr, nwadr, nwmask, nwdiag, twice=0, mask2;
stind = unind = tbind; /* TB index of origin position */
tbadr = tbind ^ symmask;
ustart = start ? start : MEN-1; /* end of opponents piece list */
u = ustart; uu = -1; /* normally start w/o uncapture */
if(task==0) /* called to generate in-checks */
u = 0; /* request uncapture black king */
do{ /* loop over pieces to uncapture*/
for(i=start; i<stop; i++) /* loop through own pieces */
{
if(i!=MEN-1 && pos[i]==pos[MEN-1])
continue; /* piece is captured */
j = first[piece[i]];
p = codevec + 8*i;
board[pos[i]] = 0; /* clear start square */
if(u<ustart) /* uncapture requested */
{ pos[u] = pos[i]; /* make uncapt. piece appear */
board[pos[i]] = u+1; /* and put it on the board */
/* and encode its presence in the TB index: */
stind = unind + ((pos[u] + (pos[u]&7))>>1)*stride[u];
uu = u;
}
while(vec = boardvec[j++])
{
b = k = pos[i]; /* start ray from current square*/
nwind = stind; /* and current TB index */
nwmask = symmask; nwdiag = diag;
do{
k += vec; /* next square */
if(k & 0x88) break; /* off-board move */
block = board[k]; /* occupant of target square */
if(block && /* square not empty */
(task<3 /* is invalid for backward move */
|| block<nblack+1)/* or forward capture own piece */
) break;
nwind += *p; /* move piece also in TB */
if(block) /* for (forward) captures */
{ /* mov capt. piece in TB to 'prison' (= wK pos) */
nwind -= stride[block-1]*((k+(k&7)>>1)
-(pos[MEN-1]+(pos[MEN-1]&7)>>1));
}
if(i>MEN-3) /* white, worry about symmetry */
{
nwmask = twice = 0;
if(i==MEN-1) /* wK, drag along capt. pieces */
{ for(h=1;h<MEN-1;h++)
if(h!=uu && pos[h]==pos[MEN-1])
nwind += basevec[j-1]*stride[h];
/* symmetry reduction, make sure wK in quadrant */
if(nwind&040<<6*MEN-6) nwmask = RANKS&~(-1<<6*MEN);
if(nwind&004<<6*MEN-6) nwmask ^= FILES&~(-1<<6*MEN);
}
nwadr = nwind ^ nwmask;
mask2 = nwmask; /* mask for no diagonal mirror */
/* let mask also move most sign. bit to hole */
if(nwadr&020<<6*MEN-6) mask2 ^= 024<<6*MEN-6;
h = (nwadr>>6*MEN-6&7) - (nwadr>>6*MEN-3);
if(h<=0)
{ /* treat wK & 1st other both on diag in 2 symm. */
h2 = (nwadr>>6*MEN-12&7) - (nwadr>>6*MEN-9&7);
twice = h==0 && h2==0 && (tbind>>3^tbind)&0707<<6*MEN-12;
if(h<0 || h2<0 || twice)
{ nwdiag=8*MEN;
if(nwadr&02<<6*MEN-6) nwmask ^= 042<<6*MEN-6;
}
else nwmask = mask2;
} else nwmask = mask2;
}
again:
nwadr = nwind ^ nwmask;
if(nwdiag) nwadr = (nwadr&RANKS)>>3 | (nwadr&FILES)<<3;
switch(task) /* process move as requested */
{
case 0:
/* mark mothers as win.wtm and go on to grandm. */
if(!(tb[nwadr]&1)) /* only if not done yet */
{ tb[nwadr] |= 1; /* set win.wtm bit */
mcnt++; sample1 = nwind;
}
if(twice)
{ twice = 0; nwmask = mask2; nwdiag = diag;
goto again; /* redo unmirrorred */
}
break;
case 1:
/* mark mothers as win.wtm and go on to grandm. */
/* put piece on board & recursion */
board[pos[i]=k] = i+1;
if(i==MEN-1) /* 'drag along' capt. */
{ for(h=1;h<MEN-1;h++)
if(h!=uu && pos[h]==b)
pos[h]=k;
}
for(s=sp; s>0; s--)
{ unsigned int ind, kpos = stack[s-1];
pos[0] = (kpos&63) + (kpos&0x38);
if(board[pos[0]]) continue;
ind = nwind + kpos;
nwadr = ind ^ nwmask;
if(nwdiag)
nwadr = (nwadr&RANKS)>>3 | (nwadr&FILES)<<3;
if(!(tb[nwadr]&1)) /* only if not done yet */
{ tb[nwadr] |= 1; /* set win.wtm bit */
mcnt++; sample1 = ind;
board[pos[0]] = 1; /* put bK on board */
zgen(0, start, 2, n, ind, nwmask, nwdiag);
board[pos[0]] = 0; /* and erase bK again */
}
}
pos[0] = 128;
if(i==MEN-1)
{ for(h=1;h<MEN-1;h++)
if(h!=uu && pos[h]==k)
pos[h]=b;
}
board[k] = 0; pos[i] = b;
if(twice)
{ twice = 0; nwmask = mask2; nwdiag = diag;
goto again; /* redo unmirrorred */
}
break;
case 2:
/* label grandmothers as potential win(n).btm */
/* if(!(tb[nwadr]>>1))
{ tb[nwadr] |= n<<1; lcnt++; }
break;
/* decrease escape count of grandmothers */
if(tb[nwadr] > (n<<1)+1)
{ tb[nwadr] += 2; lcnt++;
/* label as won(n).btm if count hits 0 */
if(tb[nwadr]<2)
{ tb[nwadr] = (tb[nwadr]&1) + (n<<1);
tbdir2[nwadr>>6]++;
cnt++;
}
}
break;
case 3:
/* check daughters, if all win.wtm */
ccnt++;
if(block==MEN)
{ tb[tbadr] &= 1;
/* black can capt wK: never win(n).btm */
tb[tbadr] |= 2;
board[b] = i+1;
return; /* one non-win reachable, abort */
}
if(!(tb[nwadr]&1)) ecnt++; /* count escapes */
}
block += piece[i]<5;/* fake capt. to terminate PNK */
} while(!block); /* continue ray if not blocked */
p++; /* next ray, nex TB move vector */
}
board[b] = i+1; /* put piece back */
} /* all moves done */
if(uu>=0) pos[uu] = pos[MEN-1];
if(task+1&2) /* regular backward move gen. */
{ /* look if (other) piece to uncapture, if so, redo. */
while(--u && pos[u]!=pos[MEN-1]);
if(!start && u<nblack) break;
/* TB 'base' index, w piece on sq. 0 instead of 'in prison' */
unind = tbind - (pos[MEN-1] + (pos[MEN-1]&7)>>1)*stride[u];
} else u = 0; /* forward or in-check gen. */
}while(u); /* redo with next uncapture */
/* note that we never REdo for uncapturing a king (u= 0 or MEN-1) */
if(task==3)
{
tb[tbadr] = (tb[tbadr]&1) + (ecnt ? 256-2*ecnt : n<<1);
}
}
void scan(int pass, int n)
/* scan through TB and board positions to perform task requested by */
/* argument 'pass'. The board pos. is updated in synchronicty with the */
/* TB index, so it can be immediately used for move generation. In order*/
/* not to waste too much time on this the fastest-scanning piece (the */
/* black king) is put only on the board when we find a marked position */
/* that we want to process, and otherwise only every 64 entries a board */
/* update is necessary. */
{
int i, j, k, m, tbaddr, mask=0, ondiag, scnt, his[65], tmp, d;
for(i=0;i<65;i++)his[i]=0;
cnt = cnt2 = 0;
for(i=0;i<129;i++) board[i] = 0; /* clear board */
for(i=1;i<=MEN;i++) pos[i] = -9; /* set position to '-1' */
tbindex = 0;
i = MEN-1; /* first board update all pieces*/
do{
/* differentially update board-position of 'higher order' pieces*/
do{
board[pos[i]] = 0; /* erase piece */
tbindex -= stride[i]; /* precompensation */
do{
tbindex += stride[i]; /* skip invalid positions */
pos[i] = pos[i]+9&~8; /* search: next square */
if(i>MEN-3)
if(i==MEN-1)
{ ondiag = pos[i]==0;
if(pos[i]&4) /* wK leaves symmetry sector */
{ /* skip to diag of next rank */
pos[i] += 13+(pos[i]>>4);
tbindex += (4+(pos[i]>>4))*stride[i];
ondiag = 1;
if(pos[i]&0x20) mask = 024*stride[i];
}
} else if(ondiag && !(pos[i]&BOX+7))
/* if wK on diag, next white piece must not be above it */
{ tbindex += (pos[i]>>4)*stride[i]; /* skip */
pos[i] += pos[i]>>4; /* and start on diag. */
}
} while(board[pos[i]] /* until empty square for it */
&& pos[i]!=pos[MEN-1]); /* or captured (= @wK) */
/* this terminated as we run off-board, for BOX is empty */
board[pos[i]] = i+1; /* put piece on found square */
board[pos[MEN-1]] = MEN; /* but protect white king */
if(pos[i] == BOX) /* if piece ran off board */
{
board[BOX] = 0; /* keep dummy square empty */
pos[i] = -9; /* and prepare wrap around */
i++; /* but first move higher-order */
} else i--; /* if succesfully placed, finish*/
/* placing lower-order pieces */
} while(i); /* until piece 1, ... n done */
if(tbindex>=2*SIZE) break;
tbaddr = tbindex ^ mask;
scnt = 0;
if(pass==1)
/* now pieces 1-n placed, try all positions for piece 0 (=bK) */
{
int d = tbaddr>>6;
/* if no labels in this block, skip it without access */
if(!tbdir[d]) goto skipblock;
tbdir[d] = 0; /* remove from to-do list */
/* first collect all sought entries for batch processing */
sp = 0;
do{ /* for all positions of bK */
if(tb[tbaddr]>>1 == n) /* look for properly marked pos */
stack[sp++] = tbaddr&63;
} while(++tbaddr & 63);
/* generate parents (certain win.wtm) */
/* and grandparents (potential win.btm) */
pos[0] = 128;
zgen(nblack,MEN,1,n+1,tbindex,mask,0);
his[sp]++;
} else if(pass>=2)
/* now pieces 1-n placed, try all positions for piece 0 (=bK) */
{
do{ /* for all positions of bK */
pos[0] = (tbaddr&63) + (tbaddr&0x38);
if(board[pos[0]]) continue;
board[pos[0]] = 1; /* put bK on board */
/* screen potential win(n).btm */
zgen(0,nblack,pass+1,n,tbaddr^mask,mask,0);
if(tb[tbaddr]>>1==n)
{ /* the position checked out, but if */
/* n==1 it still might be stalemate */
if(n==3 && !(tb[tbaddr]&1))
{ tb[tbaddr] = 4; } /* stalemate */
else
{ cnt++;
/* mark blok as containing new */
tbdir2[tbaddr>>6]++;
}
sample2 = tbaddr^mask;
}
board[pos[0]] = 0; /* and erase bK again */
scnt++;
} while(++tbaddr & 63);
his[scnt]++;
} else if(pass==0)
/* seed for black in-check positions has no bK at all */
zgen(nblack,MEN,0,n,tbindex,mask,0);
else
do{ if(pass==-1) tb[tbaddr]=0; else
{ j = tbaddr ^ mask; k = 1; m = j>>6*MEN-6;
if((m&7)!=m>>3 || (j>>6*MEN-12&7)!=(j>>6*MEN-9&7))
k = 2;
if((j&63)==m || (j>>6&63)==m ||
(j>>6*MEN-12&63)==m || (j>>6*MEN-18&63)==m ||
(j&63)==(j>>6&63) || (j&63)==(j>>12&63) || (j&63)==(j>>6*MEN-12&63)
) continue; /* don't count pos. with capt. pieces */
histo[tb[tbaddr]>>1] += k;
if(tb[tbaddr]&1) cnt += k;
}
} while(++tbaddr&63);
skipblock:
tbindex += 64;
i = 1; /* next board update for piece 1*/
} while(tbaddr<SIZE);
/*for(i=0;i<65;i++)if(his[i])printf(" %2d. %6d\n",i,his[i]);*/
}
void build()
/* build the TB by working backwards from king-captured positions. */
/* Indicate only positions that are won for white. Each position has a */
/* 1-byte entry, that has the '1' bit set if it is won with white to */
/* move (win.wtm), and for which the other bits hold the DTM if it is */
/* won with black to move (win(n).btm). A zero in this field means draw,*/
/* lost or undecided (the latter during building). DTM=1 means checkmate*/
{
int n, i, ocnt, pcnt, dcnt;
clock_t t,t1=0,t2=0;
t = clock(); ocnt = lcnt; pcnt = mcnt; dcnt = ccnt;
scan(0,3); /* label potential check-mates */
t1 += clock()-t;
n = 3;
printf("%3d. %9d %9d %9d %9d %7.3f %7.3f %7.3f\n",
n-3,cnt,lcnt-ocnt,mcnt-pcnt,ccnt-dcnt,(clock()-t)*TICK,t1*TICK,t2*TICK);
scan(2,3); /* screen checkmates */
t2 += clock()-t-t1;
do{
printf("%3d. %9d %9d %9d %9d %7.3f %7.3f %7.3f\n",
n-3,cnt,lcnt-ocnt,mcnt-pcnt,ccnt-dcnt,(clock()-t)*TICK,t1*TICK,t2*TICK);
ocnt = lcnt; pcnt = mcnt; dcnt = ccnt;
tbh = tbdir; tbdir = tbdir2; tbdir2 = tbh;
scan(1,n); /* label potential win(n).btm */
t1 = clock()-t-t2;
n++;
/*scan(3,n);*/
t2 = clock()-t-t1;
} while(cnt); /* until none is good */
printf("%3d. %9d %9d %9d %9d %7.3f %7.3f %7.3f\n",
n-3,cnt,lcnt-ocnt,mcnt-pcnt,ccnt-dcnt,(clock()-t)*TICK,t1*TICK,t2*TICK);
printf("%9d marked win.wtm\n%9d labeled potential win(n).btm\n%9d checked\n",
mcnt, lcnt, ccnt);
}
char cc[]="?PpNKBRQ";
int main()
{
int i, j, k, l, m;
char *p, name[MAX]; FILE *f;
p = (char *) malloc(SIZE+(SIZE>>5)+4096);
if(p == NULL) exit(1);
tb = (char*)((int)p+4095&~4095); /* align with cash line */
printf("%x %x\n",p, tb);
tbdir = tb + SIZE;
tbdir2 = tb + SIZE + (SIZE>>6);
f = fopen("report.txt","w");
/*for(piece[1]=3;piece[1]<8;piece[1]++)if(piece[1]!=4)
for(piece[2]=piece[1];piece[2]<8;piece[2]++)if(piece[2]!=4)
for(piece[3]=3;piece[3]<8;piece[3]++)if(piece[3]!=4)*/
{
j = 0;
for(i=MEN-1;i>=nblack;i--) name[j++]=cc[piece[i]]; name[j++]='_';
for(i=0;i<nblack;i++) name[j++] = cc[piece[i]];
name[j] = 0; printf("%s\n", name); fprintf(f, "\n%s\n", name);
exch = MEN-nblack>2 && piece[MEN-2]==piece[MEN-3];
scan(-1,0); /* clear TB */
stride[0] = 1; /* define TB mapping */
for(i=1;i<MEN;i++) stride[i] = 64*stride[i-1];
/*(basically all 6-bit square numbers packed next to each other)*/
/* initialize stepvectors in TB for each piece, by pre-scaling */
for(i=0; i<MEN; i++)
{ j = first[piece[i]]-1; m=8*i;
while(k = basevec[++j])
{ codevec[m++] = stride[i]*k; /* scaled 077 vectors */
if(i<nblack) classvec[rclass[j]] = k*stride[i];
}
}
build();
printf("%o %o\n",sample1, sample2);
/* collect stats and write those to file */
for(i=0;i<128;i++) histo[i] = 0;
scan(-2,1);
fprintf(f, "WON.wtm %10d\n", cnt); cnt = 0;
for(i=3;i<128;i++) if(histo[i])
{ fprintf(f, "%3d. %10d\n", i-3, histo[i]); cnt += histo[i]; }
fprintf(f, "WON.btm %10d\n", cnt-histo[0]);
fprintf(f, "stalemate %8d\n", histo[2]);
fprintf(f, "in check %8d\n", histo[1]);
fprintf(f, "LEGAL %10d\n", cnt+histo[2]);
fprintf(f, "TOTAL %10d\n", cnt+histo[1]+histo[2]);
}
fclose(f);
}