endgame table generation
Moderator: Ras
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: endgame table generation
I found the posting where Marcel presented his KBNK and KQKR generators ( forum3/viewtopic.php?f=7&t=50962&start=39 ), but the links in there now seem to point to malware. At least my computer totally panicked, and even started speaking to me, screaming that I should call a MicroSoft technician to save it. Could be a phishing attempt. But better not click those links!
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: endgame table generation
I looked up Marcel's 'Pretty Fast' sources that I had downloaded from those links on my old laptop. (The one with the defective keyboard...) Let me post those here:
Code: Select all
/*
* pfkbnk.c (pretty fast kbnk generator)
*
* This demonstration program solves the kbnk
* endgame by means of the bitmapped database
* method as proposed by Urban Koistinen.
*
* written by Marcel van Kervinck
* <marcelk@stack.urc.tue.nl>
*
* 18 March 1996
*/
/*
* platform cputime (seconds)
*
* 68000-7MHz Amiga 1602
* 486-66MHz FreeBSD 45
* Sun Sparc SLC 36
* Pentium-90MHz FreeBSD 16
* SG Challenge IRIX 12
*/
/* include the usual stuff */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* some 64 bit definitions for gcc, change these for other compilers */
typedef unsigned long long bitmap;
#define I 0x0000000000000001ULL
#define B5 0xffffffff00000000ULL
#define B4 0xffff0000ffff0000ULL
#define B3 0xff00ff00ff00ff00ULL
#define B2 0xf0f0f0f0f0f0f0f0ULL
#define B1 0xccccccccccccccccULL
#define B0 0xaaaaaaaaaaaaaaaaULL
#define W 0x7f7f7f7f7f7f7f7fULL
#define E 0xfefefefefefefefeULL
/* bit tricks */
#define FIRST(b) ((b)&(~(b)+1)) /* return first bit */
/* compiler should be smart enough to generate b&-b */
#define DROP(b) ((b)&=((b)-1)) /* drop first bit */
/* general macros */
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define TIME difftime(time(NULL),starttime)
/* chess macros */
#define STEP_N(b) ((b) << 8)
#define STEP_S(b) ((b) >> 8)
#define STEP_W(b) (((b) & W) << 1)
#define STEP_E(b) (((b) & E) >> 1)
#define STEP_NE(b) STEP_N(STEP_E(b))
#define STEP_NW(b) STEP_N(STEP_W(b))
#define STEP_SE(b) STEP_S(STEP_E(b))
#define STEP_SW(b) STEP_S(STEP_W(b))
#define KING(b) \
( STEP_N(STEP_W(b) | STEP_E(b) | (b)) \
| STEP_W(b) | STEP_E(b) \
| STEP_S(STEP_W(b) | STEP_E(b) | (b)) )
#define KNIGHT(b) \
( STEP_N( STEP_N(STEP_W(b)|STEP_E(b)) \
| STEP_W(STEP_W(b)) \
| STEP_E(STEP_E(b)) ) \
| STEP_S( STEP_S(STEP_W(b)|STEP_E(b)) \
| STEP_W(STEP_W(b)) \
| STEP_E(STEP_E(b)) ) )
/* memory structures */
bitmap wtm[10][64][64][2]; /* wtm database, 2 bits per position */
/* 0: score>=mate 1: score<mate */
/* 2: score=mate 3: score=mate-1 */
bitmap mask[2][64]; /* bitnumber to bitmap */
short slide[64][4][8]; /* sliding moves */
short king[64][9]; /* king moves */
short knight[64][9]; /* knight moves */
short map[64] = { /* map king to database index */
0,1,2,3,0,0,0,0,
0,4,5,6,0,0,0,0,
0,0,7,8,0,0,0,0,
0,0,0,9,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
};
short mir[64] = { /* reflection bits */
0,0,0,0,1,1,1,1,
4,0,0,0,1,1,1,5,
4,4,0,0,1,1,5,5,
4,4,4,0,1,5,5,5,
6,6,6,2,3,7,7,7,
6,6,2,2,3,3,7,7,
6,2,2,2,3,3,3,7,
2,2,2,2,3,3,3,3,
};
short dia[64] = { /* reflection over diagonal */
0, 8,16,24,32,40,48,56,
1, 9,17,25,33,41,49,57,
2,10,18,26,34,42,50,58,
3,11,19,27,35,43,51,59,
4,12,20,28,36,44,52,60,
5,13,21,29,37,45,53,61,
6,14,22,30,38,46,54,62,
7,15,23,31,39,47,55,63,
};
short factor[64] = { /* multiplication for position counts */
4,8,8,8,8,8,8,4,
8,4,8,8,8,8,4,8,
8,8,4,8,8,4,8,8,
8,8,8,4,4,8,8,8,
8,8,8,4,4,8,8,8,
8,8,4,8,8,4,8,8,
8,4,8,8,8,8,4,8,
4,8,8,8,8,8,8,4,
};
short bitcount(bitmap b) /* count number of bits */
{
short i;
for(i=0; b; b&=b-1)
i++;
return i;
}
unsigned init(void) /* init global data */
{
bitmap wkb, wbb, wnb, b, c, ray[64][8];
short wk, wb, wn, i, *m;
unsigned count;
/* move tables and others */
for(wb=0, wbb=I; wb<64; wbb<<=1, wb++) {
for(b=wbb, i=0; ~b&STEP_NE(b); b|=STEP_NE(b), i++)
slide[wb][0][i] = wb+7+7*i;
ray[wb][0] = b & ~wbb;
slide[wb][0][i] = -1;
for(b=wbb, i=0; ~b&STEP_NW(b); b|=STEP_NW(b), i++)
slide[wb][1][i] = wb+9+9*i;
ray[wb][1] = b & ~wbb;
slide[wb][1][i] = -1;
for(b=wbb, i=0; ~b&STEP_SW(b); b|=STEP_SW(b), i++)
slide[wb][2][i] = wb-7-7*i;
ray[wb][2] = b & ~wbb;
slide[wb][2][i] = -1;
for(b=wbb, i=0; ~b&STEP_SE(b); b|=STEP_SE(b), i++)
slide[wb][3][i] = wb-9-9*i;
ray[wb][3] = b & ~wbb;
slide[wb][3][i] = -1;
for(i=0, m=king[wb]; i<64; i++)
if(i!=wb && abs((i%8)-(wb%8))<=1 && abs((i/8)-(wb/8))<=1)
*m++ = i;
*m = -1;
for(i=0, m=knight[wb]; i<64; i++)
if(abs( ((i%8)-(wb%8)) * ((i/8)-(wb/8)) )==2)
*m++ = i;
*m = -1;
mask[0][wb] = I<<wb;
mask[1][wb] = ~(I<<wb);
}
/* mark relevant illegal positions */
count = 0;
for(wk=0, wkb=I; wk<64; wkb<<=1, wk++) if(!mir[wk])
for(wb=0, wbb=I; wb<64; wbb<<=1, wb++)
for(wn=0, wnb=I; wn<64; wnb<<=1, wn++) {
b = KING(wkb) | KNIGHT(wnb);
for(i=0; i<4; i++) {
c = ray[wb][i];
if(c & wkb)
c &= ~ray[wk][i];
if(c & wnb)
c &= ~ray[wn][i];
b |= c;
}
b &= ~wkb;
wtm[map[wk]][wb][wn][0] = b;
wtm[map[wk]][wb][wn][1] = 0;
count += factor[wk]
* (wk==wb || wk==wn || wb==wn ? 64 : bitcount(b | wkb | wbb | wnb) );
}
return count;
}
unsigned new2old(void) /* mark new found positions as old */
{
short wk, wb, wn;
unsigned count;
bitmap b;
count = 0;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wb=0; wb<64; wb++)
for(wn=0; wn<64; wn++) {
b = ~wtm[map[wk]][wb][wn][0] & wtm[map[wk]][wb][wn][1];
wtm[map[wk]][wb][wn][0] |= b;
wtm[map[wk]][wb][wn][1] &= b;
count += factor[wk] * bitcount(b);
}
return count;
}
short index(bitmap b) /* return bitnumber (pre: bitcount(b)==1) */
{
return (b & B5 ? 32 : 0)
+ (b & B4 ? 16 : 0)
+ (b & B3 ? 8 : 0)
+ (b & B2 ? 4 : 0)
+ (b & B1 ? 2 : 0)
+ (b & B0 ? 1 : 0);
}
void enter(short wk, short wb, short wn, bitmap b) /* add wtm positions */
{
bitmap c;
if(b) {
if(mir[wk] & 1) { /* mirror vertical */
wk ^= 007;
wb ^= 007;
wn ^= 007;
for(c=b, b=0; c; DROP(c))
b |= mask[0][index(FIRST(c))^007];
}
if(mir[wk] & 2) { /* mirror horizontal */
wk ^= 070;
wb ^= 070;
wn ^= 070;
for(c=b, b=0; c; DROP(c))
b |= mask[0][index(FIRST(c))^070];
}
if(mir[wk] & 4) { /* mirror diagonal */
wk = dia[wk];
wb = dia[wb];
wn = dia[wn];
for(c=b, b=0; c; DROP(c))
b |= mask[0][dia[index(FIRST(c))]];
}
if( (b &= ~wtm[map[wk]][wb][wn][0]
& ~wtm[map[wk]][wb][wn][1]) ) { /* which are new? */
wtm[map[wk]][wb][wn][1] |= b; /* enter those */
if(dia[wk]==wk) { /* and the doubles */
wb = dia[wb];
wn = dia[wn];
for(c=0; b; DROP(b))
c |= mask[0][dia[index(FIRST(b))]];
wtm[map[wk]][wb][wn][1] |= c;
}
}
}
}
void retro_btm(short wk, short wb, short wn, bitmap b) /* process btm positions */
{
short i, *m;
/* find all white moves that lead to the btm positions */
/* white bishop */
for(i=0; i<4; i++)
for(m=slide[wb][i]; *m>=0 && *m!=wk && *m!=wn; m++)
enter(wk,*m,wn,b & mask[1][*m]);
/* white knight */
for(m=knight[wn]; *m>=0; m++)
if(*m!=wk && *m!=wb)
enter(wk,wb,*m,b & mask[1][*m]);
/* white king */
for(m=king[wk]; *m>=0; m++)
if(*m!=wb && *m!=wn)
enter(*m,wb,wn,b & mask[1][*m]);
}
void retro_wtm(short wk, short wb, short wn, bitmap b) /* process wtm positions */
{
/* find forced black moves that lead to the wtm positions */
/* black king */
if( (b = KING(b) & mask[1][wb] & mask[1][wn]
& ~KING(~wtm[map[wk]][wb][wn][0])) )
retro_btm(wk,wb,wn,b);
}
int main(void) /* compute database */
{
bitmap b;
short wk, wb, wn;
unsigned count, total;
int mate;
time_t starttime;
/* init */
starttime = time(NULL);
printf("kbnk wtm\n");
printf(" status count time\n");
total = init();
printf("illegal %8u (%1.0f)\n", total, TIME);
/* enter mates */
mate = 1;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wb=0; wb<64; wb++) if(wb!=wk) if(dia[wk]!=wk || dia[wb]<=wb)
for(wn=0; wn<64; wn++) if(wn!=wk && wn!=wb) if(dia[wk]!=wk || dia[wb]!=wb || dia[wn]<=wn)
if( (b = wtm[map[wk]][wb][wn][0] & ~KING(~wtm[map[wk]][wb][wn][0])) )
retro_btm(wk,wb,wn,b);
/* iterate */
while( (count = new2old()) ) {
total += count;
printf("mate%03d %8u (%1.0f)\n", mate, count, TIME);
count = 0;
mate++;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wb=0; wb<64; wb++) if(dia[wk]!=wk || dia[wb]<=wb)
for(wn=0; wn<64; wn++) if(dia[wk]!=wk || dia[wb]!=wb || dia[wn]<=wn)
if( (b = wtm[map[wk]][wb][wn][0] & wtm[map[wk]][wb][wn][1]) )
retro_wtm(wk,wb,wn,b);
}
/* count left overs */
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wb=0; wb<64; wb++) if(wk!=wb)
for(wn=0; wn<64; wn++) if(wk!=wn && wb!=wn)
count += factor[wk]
* bitcount(~wtm[map[wk]][wb][wn][0]
& mask[1][wk] & mask[1][wb] & mask[1][wn]);
printf("no_mate %8u (%1.0f)\n", count, TIME);
total += count;
/* print total */
printf(" total %8u (%1.0f)\n", total, TIME);
/* be happy */
return 0;
}
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: endgame table generation
Code: Select all
/*
* pfkqkr.c (pretty fast kqkr generator)
*
* written by Marcel van Kervinck
* <marcelk@stack.urc.tue.nl>
*
* March 1996
*/
/*
* platform cputime (seconds)
*
* 68000-7MHz Amiga 7534
* 486-66MHz FreeBSD
* Sun Sparc SLC
* Pentium-90MHz FreeBSD
* SG Challenge IRIX
*/
/* include the usual stuff */
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/* some 64 bit definitions for gcc, change these for other compilers */
typedef unsigned long long bitmap;
#define I 0x0000000000000001ULL
#define W 0x7f7f7f7f7f7f7f7fULL
#define E 0xfefefefefefefefeULL
#define V0 0xf0f0f0f0f0f0f0f0ULL
#define V1 0x0f0f0f0f0f0f0f0fULL
#define V2 0xccccccccccccccccULL
#define V3 0x3333333333333333ULL
#define V4 0xaaaaaaaaaaaaaaaaULL
#define V5 0x5555555555555555ULL
#define H2 0x0000ffff0000ffffULL
#define H3 0xffff0000ffff0000ULL
#define H4 0x00ff00ff00ff00ffULL
#define H5 0xff00ff00ff00ff00ULL
#define D0 0xf0f0f0f00f0f0f0fULL
#define D1 0x00000000f0f0f0f0ULL
#define D2 0x0f0f0f0f00000000ULL
#define D3 0xcccc3333cccc3333ULL
#define D4 0x0000cccc0000ccccULL
#define D5 0x3333000033330000ULL
#define D6 0xaa55aa55aa55aa55ULL
#define D7 0x00aa00aa00aa00aaULL
#define D8 0x5500550055005500ULL
/* bit tricks */
#define MIRV(b) b = (b<<4 & V0) | (b>>4 & V1); \
b = (b<<2 & V2) | (b>>2 & V3); \
b = (b<<1 & V4) | (b>>1 & V5);
#define MIRH(b) b = (b>>32 ) | (b<<32 ); \
b = (b>>16 & H2) | (b<<16 & H3); \
b = (b>>8 & H4) | (b<<8 & H5);
#define MIRD(b) b = (b & D0) | (b>>28 & D1) | (b<<28 & D2); \
b = (b & D3) | (b>>14 & D4) | (b<<14 & D5); \
b = (b & D6) | (b>>7 & D7) | (b<<7 & D8);
/* general macros */
#define TIME difftime(time(NULL),starttime)
/* chess macros */
#define STEP_N(b) ((b)<<8)
#define STEP_S(b) ((b)>>8)
#define STEP_W(b) ((b)<<1 & E)
#define STEP_E(b) ((b)>>1 & W)
#define KING(b) \
( STEP_N(STEP_W(b) | STEP_E(b) | (b)) \
| STEP_W(b) | STEP_E(b) \
| STEP_S(STEP_W(b) | STEP_E(b) | (b)) )
/* memory structures */
bitmap wtm[10][64][64][2]; /* wtm database, 2 bits per position */
/* wk wq br */ /* 0: score>=mate 1: score<mate */
/* 2: score=mate 3: score=mate-1 */
/* kqk entries are coded as kqkr with wk==br */
unsigned kqkr, kqk; /* position counts */
bitmap mask[2][64]; /* bitnumber to bitmap */
bitmap ray[64][8]; /* attack rays */
short slide[64][8][8]; /* sliding moves */
short king[64][9]; /* king moves */
short map[64] = { /* map king to database index */
0,1,2,3,0,0,0,0,
0,4,5,6,0,0,0,0,
0,0,7,8,0,0,0,0,
0,0,0,9,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
};
short mir[64] = { /* reflection bits */
0,0,0,0,1,1,1,1,
4,0,0,0,1,1,1,5,
4,4,0,0,1,1,5,5,
4,4,4,0,1,5,5,5,
6,6,6,2,3,7,7,7,
6,6,2,2,3,3,7,7,
6,2,2,2,3,3,3,7,
2,2,2,2,3,3,3,3,
};
short dia[64] = { /* reflection over diagonal */
0, 8,16,24,32,40,48,56,
1, 9,17,25,33,41,49,57,
2,10,18,26,34,42,50,58,
3,11,19,27,35,43,51,59,
4,12,20,28,36,44,52,60,
5,13,21,29,37,45,53,61,
6,14,22,30,38,46,54,62,
7,15,23,31,39,47,55,63,
};
short factor[64] = { /* multiplication for position counts */
4,8,8,8,8,8,8,4,
8,4,8,8,8,8,4,8,
8,8,4,8,8,4,8,8,
8,8,8,4,4,8,8,8,
8,8,8,4,4,8,8,8,
8,8,4,8,8,4,8,8,
8,4,8,8,8,8,4,8,
4,8,8,8,8,8,8,4,
};
short bitcount(bitmap b) /* count number of bits */
{
short i;
for(i=0; b; b&=b-1)
i++;
return i;
}
void init(void) /* setup move tables and others */
{
bitmap b;
short sq, x, y, i, j, *m;
short dx[8] = { 0, 0, 1,-1, 1, 1,-1,-1};
short dy[8] = { 1,-1, 0, 0, 1,-1, 1,-1};
for(sq=0; sq<64; sq++) { /* useful masks */
mask[0][sq] = I<<sq;
mask[1][sq] = ~(I<<sq);
}
for(sq=0; sq<64; sq++) {
/* precompute sliding moves and attack rays */
for(i=0; i<8; i++) {
x = sq % 8;
y = sq / 8;
m = slide[sq][i];
b = 0;
for(j=0; j<7; j++) {
x += dx[i];
y += dy[i];
if(0<=x && x<8 && 0<=y && y<8) {
*m++ = y*8+x;
b |= mask[0][y*8+x];
}
}
*m = -1;
ray[sq][i] = b;
}
/* precompute king moves */
for(i=0, m=king[sq]; i<64; i++)
if(i!=sq && abs((i%8)-(sq%8))<=1 && abs((i/8)-(sq/8))<=1)
*m++ = i;
*m = -1;
}
}
void illegal(void) /* mark relevant illegal positions as lost */
{
short wk, wq, br, i;
bitmap b, c;
unsigned count;
kqkr = kqk = 0;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wq=0; wq<64; wq++)
for(br=0; br<64; br++) {
b = KING(mask[0][wk]);
for(i=0; i<8; i++) {
c = ray[wq][i];
if(c & mask[0][wk])
c &= ~ray[wk][i];
if(c & mask[0][br])
c &= ~ray[br][i];
b |= c;
}
b |= mask[0][br];
b &= mask[1][wk]; /* allows easy mate detection */
wtm[map[wk]][wq][br][0] = b;
wtm[map[wk]][wq][br][1] = 0;
count = factor[wk]
* (wk==wq || wq==br ? 64
: bitcount(b | mask[0][wk] | mask[0][wq]));
if(wk!=br)
kqkr += count;
else
kqk += count;
}
}
void new2old(void) /* mark new found positions as old */
{
short wk, wq, br;
unsigned count;
bitmap b;
kqkr = kqk = 0;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wq=0; wq<64; wq++)
for(br=0; br<64; br++) {
b = ~wtm[map[wk]][wq][br][0] & wtm[map[wk]][wq][br][1];
wtm[map[wk]][wq][br][0] |= b;
wtm[map[wk]][wq][br][1] &= b;
count = factor[wk] * bitcount(b);
if(wk!=br)
kqkr += count;
else
kqk += count;
}
}
void enter(short wk, short wq, short br, bitmap b) /* add wtm positions */
{
short m;
if(b) {
m = mir[wk];
if(m & 1) { /* mirror vertical */
wk ^= 007;
wq ^= 007;
br ^= 007;
MIRV(b);
}
if(m & 2) { /* mirror horizontal */
wk ^= 070;
wq ^= 070;
br ^= 070;
MIRH(b);
}
if(m & 4) { /* mirror diagonal */
wk = dia[wk];
wq = dia[wq];
br = dia[br];
MIRD(b);
}
if( (b &= ~wtm[map[wk]][wq][br][0]
& ~wtm[map[wk]][wq][br][1]) ) { /* which are new? */
wtm[map[wk]][wq][br][1] |= b; /* enter those */
if(dia[wk]==wk) { /* and the doubles */
wq = dia[wq];
br = dia[br];
MIRD(b);
wtm[map[wk]][wq][br][1] |= b;
}
}
}
}
void retro_btm(short wk, short wq, short br, bitmap b) /* process btm positions */
{
short i, *m;
/* find all white moves that lead to the btm positions */
/* white queen */
for(i=0; i<8; i++)
for(m=slide[wq][i]; *m>=0 && *m!=wk && *m!=br; m++) {
enter(wk,*m,br,b & mask[1][*m]);
if(wk==br)
enter(wk,*m,wq,b & mask[1][*m]);
}
/* white king */
for(m=king[wk]; *m>=0; m++)
if(*m!=wq && *m!=br) {
enter(*m,wq,br,b & mask[1][*m]);
if(wk==br)
enter(*m,wq,*m,b & mask[1][*m]);
}
}
void filter(short wk, short wq, short br, bitmap b) /* remove non-forced btm positions */
{
bitmap c;
short i, *m;
b &= ~KING(~wtm[map[wk]][wq][br][0]);
if(wk!=br)
for(i=0; i<4; i++) {
m = slide[br][i];
c = 0;
while(*m>=0 && *m!=wk && *m!=wq) {
c |= mask[0][*m];
b &= wtm[map[wk]][wq][*m][0] | c;
if(!b) return;
m++;
}
if(*m>=0) /* can capture king or queen */
b &= c;
}
if(b)
retro_btm(wk,wq,br,b);
}
void retro_wtm(short wk, short wq, short br, bitmap b) /* process wtm positions */
{
short i, *m;
bitmap c;
/* find black moves that lead to the wtm positions */
/* black rook */
if(wk!=br)
for(i=0; i<4; i++) {
m = slide[br][i];
c = b;
while(*m>=0 && *m!=wk && *m!=wq && c) {
filter(wk,wq,*m,c);
c &= mask[1][*m];
m++;
}
}
/* black king */
if( (c = KING(b) & mask[1][wq] & mask[1][br]) )
filter(wk,wq,br,c);
}
int main(void) /* compute database */
{
short wk, wq, br, mate;
bitmap b;
unsigned count, total;
time_t starttime;
/* init */
starttime = time(NULL);
printf("status kqkr kqk (time)\n");
init();
illegal();
printf("illegal %8u %6u (%1.0f)\n", kqkr, kqk, TIME);
total = kqkr + kqk;
/* enter mates */
mate = 1;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wq=0; wq<64; wq++) if(wq!=wk)
for(br=0; br<64; br++) if(br!=wq)
if( (b = wtm[map[wk]][wq][br][0]) )
filter(wk,wq,br,b);
/* iterate */
new2old();
while(kqkr+kqk) {
printf("mate%03d %8u %6u (%1.0f)\n", mate, kqkr, kqk, TIME);
total += kqkr + kqk;
mate++;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wq=0; wq<64; wq++)
for(br=0; br<64; br++)
if( (b = wtm[map[wk]][wq][br][0] & wtm[map[wk]][wq][br][1]) )
retro_wtm(wk,wq,br,b);
new2old();
}
/* count left overs */
count = kqkr = kqk = 0;
for(wk=0; wk<64; wk++) if(!mir[wk])
for(wq=0; wq<64; wq++) if(wq!=wk)
for(br=0; br<64; br++) if(br!=wq) {
count = factor[wk]
* bitcount(~wtm[map[wk]][wq][br][0] & mask[1][wk] & mask[1][wq]);
if(wk!=br)
kqkr += count;
else
kqk += count;
}
printf("no_mate %8u %6u (%1.0f)\n", kqkr, kqk, TIME);
total += kqkr+kqk;
printf("\ntotal %8u\n", total);
/* be happy */
return 0;
}
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: endgame table generation
Well, it is how Marcel's PrettyFast generators work. And these are running circles around FairyGen.Dave Gomboc wrote: ↑Sun Sep 25, 2022 9:29 amThat's interesting. I am familiar with using a counter (might be larger than a byte, if using DTM or if tracking accurate DTC past 100 ply) per position, but I wasn't aware that some folks were instead using a separate bit plane per DTx. Has anyone done a resource analysis (time, memory) analysis of this choice?
Well, to set things right, I wanted to say less memory. Because you can 'factorize' those into P-slices, and solve those one at the time. So a 7-men with 3 Pawns only contains 4 mobile pieces in a P-slice, and have about the same memory requirements as a 4-men. And definitely a lot less than a 5-men.This seems incorrect to me: there are fewer symmetries, but not none. If nothing else, there's always the "invert colours, flip the side to move, and interchange ranks: 1<->8, 2<->7, 3<->6, 4<->5" symmetry. Also, unless castling is legal in a position (and the tables actually handle positions when castling is possible rather than bailing with "don't know" -- are there even any such tables that support castling built and used with open-source code?), then there would also be an "interchange files: a<->h, b<->g, c<->f, d<-e>" symmetry available.
As to the symmetry: reversing colors is indeed always possible, but in general it would not stay the same end-game: KQKR would become KRKQ. So it is not a symmetry of KQKR. This is usually taken for granted, and one only builds EGT where white is the strong side. If these are 'two-sided EGT', that is (i.e. if they contain WDL info). I usually calculate 'single-sided EGT', which contain W/non-W info. Then KQKR and KRKQ contain essentially different info: the latter would contain as W the L-info for the former.
The left-right symmetry is usually only a symmetry if you consider all positions with that material a single EGT. But these factorize into P-slices, and in general the horizontal reflection would not map the P-slice in itself, but into another one. So the P-slices themselves do not have the symmetry, and thesolving algorithm can thus not exploit it. Of course you still benefit from it from the fact that you son't have to solve all P-slices, but can derive the result of one from that of its mirror image.
Well, to an EGT generator it doesn't matter whether a piece happened to feature in orthodox Chess or not; the algorithm is exactly the same, and it is up to the move generator to determine what material you are solving for.I'm going to limit my search to regular Chess. (Actually, an endgame table generator for Xiangqi might be fine too, though Shogi play doesn't generally converge.)
Solving Xiangqi EGT actually is far harder than Chess, because you have to deal with the rule that perpetual checking is forbidden. While in end-games with few men it is almost always possible, and in Chess would qualify such end-games as a draw because of it.
-
hgm
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: endgame table generation
Some more things worth noting:
My JavaScript generator uses the out-counting method, because it was designed for solving EGT with a bare (orthodox) King. So the number of out-counts is limited to 8, eating only a small part of the range that for the remainder is used for recording DTM. Like in FairyGen I put the 'won' bit for the position in thos bite as well (the LSB), so the available range is only 128. When the losing side has a Queen in addition to his King, the counts could run up to 35. That still leaves room for doing mates of up to 90 moves without resorting to tricks.
The JavaScript generator uses 'bulk methods' for generating the out-counts. So it doesn't generate moves in every possible position. The idea (for mating a bare King) is that you calculate a 1-men table with just the losing King on the board (on an empty board that would be 8 everywhere, except 3 in a corner and 5 on an edge, but in a P-slice you would have to take account of the Pawns), and a two-men table for each winning piece and the losing King that tabulates how many out-moves would be invalidated by the presence of that piece (i.e. how many moves would step into check). In addition you also make such tables where you record where the losing King is in check. These tables are all very much smaller than the EGT you want to generate, even in the 3-men case, so it doesn't matter much by which method you do this.
Then you just combine the tables. E.g. for a KXk end-game you take EGT = k - Kk - Xk. That does not account for slider blocking. So if X is a slider, the cases where K sits on a square attacked by X (as seen in the Xk checks table), which happens rarely, you have to retrace the sliding move downstream of K, decrease the total number of times k is checked there, and if this ends up as 0, give the out-count back to all positions with k adjacent to that (only a small fraction of all positions). I usually do this before adding the contribution from the k table to the out-count, so that I can do that last to get the total. If this ends at 0, the position is a mate. If it was marked in the checking table, it is a checkmate, and you can mark it as such in the EGT.
A hybrid method between out-counting and testing for out-moves on the fly is to use a move generator for the latter that can be interrupted and restarted. And save its state in the DTx field as long as the position is not yet decided. That information then allows you to skip all the moves that were already leading to won positions on a previous visit. You will either run the move generation to the end, without finding any out-moves, in which case the position becomes lost, and its byte is set to the DTx. Or it will find an out-move, and then will store its encoded state there. E.g. you could use the first 8 state codes for King moves (even in cases where a King has fewer moves), and the immediately following codes for the moves of the other piece. For a Rook that could be 16, which can be translated to a direction and distance by a small lookup table.
My JavaScript generator uses the out-counting method, because it was designed for solving EGT with a bare (orthodox) King. So the number of out-counts is limited to 8, eating only a small part of the range that for the remainder is used for recording DTM. Like in FairyGen I put the 'won' bit for the position in thos bite as well (the LSB), so the available range is only 128. When the losing side has a Queen in addition to his King, the counts could run up to 35. That still leaves room for doing mates of up to 90 moves without resorting to tricks.
The JavaScript generator uses 'bulk methods' for generating the out-counts. So it doesn't generate moves in every possible position. The idea (for mating a bare King) is that you calculate a 1-men table with just the losing King on the board (on an empty board that would be 8 everywhere, except 3 in a corner and 5 on an edge, but in a P-slice you would have to take account of the Pawns), and a two-men table for each winning piece and the losing King that tabulates how many out-moves would be invalidated by the presence of that piece (i.e. how many moves would step into check). In addition you also make such tables where you record where the losing King is in check. These tables are all very much smaller than the EGT you want to generate, even in the 3-men case, so it doesn't matter much by which method you do this.
Then you just combine the tables. E.g. for a KXk end-game you take EGT = k - Kk - Xk. That does not account for slider blocking. So if X is a slider, the cases where K sits on a square attacked by X (as seen in the Xk checks table), which happens rarely, you have to retrace the sliding move downstream of K, decrease the total number of times k is checked there, and if this ends up as 0, give the out-count back to all positions with k adjacent to that (only a small fraction of all positions). I usually do this before adding the contribution from the k table to the out-count, so that I can do that last to get the total. If this ends at 0, the position is a mate. If it was marked in the checking table, it is a checkmate, and you can mark it as such in the EGT.
A hybrid method between out-counting and testing for out-moves on the fly is to use a move generator for the latter that can be interrupted and restarted. And save its state in the DTx field as long as the position is not yet decided. That information then allows you to skip all the moves that were already leading to won positions on a previous visit. You will either run the move generation to the end, without finding any out-moves, in which case the position becomes lost, and its byte is set to the DTx. Or it will find an out-move, and then will store its encoded state there. E.g. you could use the first 8 state codes for King moves (even in cases where a King has fewer moves), and the immediately following codes for the moves of the other piece. For a Rook that could be 16, which can be translated to a direction and distance by a small lookup table.