Previous Next About my new 7-men generator
Below you find the C source of a simple EGTB generator. It is written to solve (by retrograde analysis) any 3- to 5-men end-game without Pawns: it makes use of the 8-fold symmetry that exists in that case. (Left-right and front-back mirroring, plus diagonal mirroring.) Pawns would break the front-back and diagonal symmetries, because they care about direction in their moves. An EGTB generator for end-games with Pawns cannot benifit from symmetry at all, and thus could be even simpler than this one.
This EGTB generator builds the EGTB in the array tb
(actually a pointer, since it is allocated dependent on need).
Apart from reporting statistics during the build,
it does not do anything with the EGTB.
It was really designed to generate EGTBs for probing by my engine Usurpator,
on the fly as they are needed in the game.
To build a 4-men EGTB takes a few seconds, a 5-men EGTB a few minutes.
The version below is set to generate the KbbKn 5-men end-game.
To wire it for another end-game,
you should recompile with other values for the macro MEN (3, 4 or 5 are valid),
initialize the variable nblack to the number of black pieces (including the King),
and initialize the array piece[] to the required pieces.
The black pieces should lead the list.
The first and the last pieces you give in the list will be considered to be royal,
(i.e. the ones you have to capture to win the game),
so in FIDE chess you better make them Kings.
If you mention Kings elsewhere in the list, they will be treated as
Commoners.
(You are encourged to try the KkKk end-game, which,
unlike you might expect for equal material,
can very often be won in a higly non-trivial and beautiful way,
sometimes after 40 moves of strategic manouevring.)
To probe the EGTB, you will have to know where to find a certain position in the array tb[].
Basically, the index is just the position (square number) of all pieces stringed together,
the last mentioned piece (usually the white King) in the most significant bits.
So piece0 + 64*piece1 + 4096*piece2 + ..., where piecen indicates the square number of that piece.
The lowest 3 bits of a square number give the file, the highest 3 the rank, in the trivial order.
The symmetry maps the white King to the triangle a1-d1-d4. As a result the most-significant bit of file and square number for this piece are always 0. In addition, the file number has to be larger or equal to the rank number. To not cause gaps in the TB the most significant remaining bit of this King's rank (the one that is set for 3rd and 4th rank) is displaced to the 'hole' in the file number (the bit that would have been set on files e-h). Entries with file number smaller than rank number are allocated, but never used, and should not be probed.
An EGTB will contain all EGTBs with a subset of the pieces, you won't have to build other EGTBs first. These sub-set EGTBs are stored in the 'broken' positions: Captured pieces are given the same square number as the white King (i.e. last mentioned piece). So if you want to probe a position of KbbK after making the KbbKn, use the index that has black Knight and white King on the same square.
For any position in the EGTB, one byte is stored. The least significant bit of this byte indicates if the position is won for white with white to move (i.e. a bit-base, really). The other 7 bits contain the DTM (where white mates) for that position with black to move, with the caveat that DTM codes 127 and 126 are reserved for stale-mate and illegal positions, (where black can capture the white King), respectively, and 0 means draw or loss (or undecided during the build). The EGTB contains only wins for white, to know the losses you would have to build another EGTB with the colors swapped. You would need to find the optimal defense from a two-ply search, though, because after one ply you only probe the bit-base.
In end-games that take more than 125 moves to win, there would not be enough bits for the DTM. As far as I know this does not happen in FIDE-chess 3-, 4- or 5-men EGTBs. For fairy pieces (if you would care to implement those in the move generator, which is rather simple), it can happen, though. Especially end-games involving Nightriders tend to be lengthy (e.g. Bishop + Commoner against Nightrider, generally won, but average DTC for a non-trivial win with black to move = 265.5, maximin DTC = 308 moves). Recommended in that case is to reset all winning DTMs to 1 after you reach 125, (perhaps after saving them on disk), and simply continue the construction from there, knowing you will have to add 124 to the listed DTMs.
Note: the listing below was updated on April 7, 2006. Before that date, I accidentally put an experimental version there that might not generally work (although it worked for KbbKn).
/************************************************************************/
/* Pieces-Only Tablebase Generator, by H.G. Muller */
/************************************************************************/
/* Working version, 8-symmetry, but uncompacted. 2-pass strategy. */
#include <time.h>
#include <stdio.h>
#define MEN 5
#define SIZE (1<<6*MEN-2)
#define MAX MEN+2
#define BOX 0x80
#define LABEL (~1)
#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, sample1, sample2;
clock_t t;
unsigned char *tb;
char ii;
int mcnt, lcnt, vcnt, ccnt;
int histo[128];
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 */
int codevec[16*MEN]; /* step vectors in TB index */
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,
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:
case 1:
/* 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;
/* 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;
}
zgen(0, start, 2, n, nwind, nwmask, nwdiag);
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++; vcnt++;}
break;
case 3:
/* check daughters, if all win.wtm */
ccnt++;
if(block==MEN||!(tb[nwadr]&1))
{ tb[tbadr] &= 1; vcnt--;
/* black can capt wK: never win(n).btm */
if(block==MEN) tb[tbadr] |= LABEL-2;
board[b] = i+1;
return; /* one non-win reachable, abort */
}
}
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) */
}
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];
for(i=0;i<65;i++)his[i]=0;
cnt = 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>0)
/* now pieces 1-n placed, try all positions for piece 0 (=bK) */
{
do{ /* for all positions of bK */
if(tb[tbaddr]>>1 == n) /* look for properly marked pos */
{
pos[0] = (tbaddr&63) + (tbaddr&0x38);
board[pos[0]] = 1; /* put bK on board */
switch(pass)
{
case 1:
/* generate parents (certain win.wtm) */
/* and grandparents (potential win.btm) */
zgen(nblack,MEN,1,n+1,tbaddr^mask,mask,0);
break;
case 2:
/* screen potential win(n).btm */
/*if(n==1 & !(tb[tbadr]&1)) tb[tbaddr]=0;
else*/
zgen(0,nblack,3,n,tbaddr^mask,mask,0);
/*if(tb[tbaddr]>>1==n) cnt++;*/
if(tb[tbaddr]>>1==n)
{ /* the position checked out, but if */
/* n==1 it still might be stalemate */
if(n==1 && !(tb[tbaddr]&1))
{ tb[tbaddr] |= LABEL; vcnt--;}
else cnt++;
sample2 = tbaddr^mask;
}
break;
}
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);
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,1); /* label potential check-mates */
t1 += clock()-t;
scan(2,1); /* screen checkmates */
t2 += clock()-t-t1;
n = 1;
do{
printf("%3d. %9d %9d %9d %9d %7.3f %7.3f %7.3f\n",
n-1,cnt,lcnt-ocnt,mcnt-pcnt,ccnt-dcnt,(clock()-t)*TICK,t1*TICK,t2*TICK);
ocnt = lcnt; pcnt = mcnt; dcnt = ccnt;
scan(1,n); /* label potential win(n).btm */
t1 = clock()-t-t2;
n++;
scan(2,n); /* and screen them */
t2 = clock()-t-t1;
} while(cnt); /* until none is good */
printf("%3d. %9d %9d %9d %9d %7.3f %7.3f %7.3f\n",
n-1,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 verified win(n).btm\n%9d checked\n",
mcnt, lcnt, vcnt, ccnt);
}
char cc[]="?PpNKBRQ";
int main()
{
int i, j, k, l, m;
char *p, name[MAX]; FILE *f;
p = (char *) malloc(SIZE+4096);
if(p == NULL) exit(1);
tb = (char*)((int)p+4095&~4095); /* align with cash line */
printf("%x %x\n",p, tb);
f = fopen("report.txt","w");
/*for(piece[1]=3;piece[1]<8;piece[1]++)/*if(piece[1]!=4)*/
/*for(piece[2]=3;piece[2]<8;piece[2]++)/*if(piece[2]!=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 */
}
build();
printf("%o %o\n",sample1, sample2);
for(i=0;i<128;i++) histo[i] = 0;
scan(-2,1);
fprintf(f, "WON.wtm %10d\n", cnt); cnt = 0;
for(i=0;i<126;i++) if(histo[i])
{ fprintf(f, "%3d. %10d\n", i, histo[i]); cnt += histo[i]; }
fprintf(f, "WON.btm %10d\n", cnt-histo[0]);
fprintf(f, "stalemate %8d\n", histo[127]);
fprintf(f, "in check %8d\n", histo[126]);
fprintf(f, "LEGAL %10d\n", cnt+histo[127]);
fprintf(f, "TOTAL %10d\n", cnt+histo[126]+histo[127]);
}
fclose(f);
}