endgame table generation

[hgm]

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]

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]

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]

That'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, it is how Marcel's PrettyFast generators work. And these are running circles around FairyGen.

End-games with pawns are much simpler, as these have no symmetry. But they require more memory.

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.

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.

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.

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.)

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.

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]

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.

[Dave Gomboc]

The retrograde analysis code encodes each position as an index. Let's assume a pawnless table.

So possible values are (for pawnless tables):

Code: Select all

#define ILLEGAL 0
#define BROKEN 0xff
#define UNKNOWN 0xfe
#define CHANGED 0xfd
#define CAPT_CLOSS 0xfc
#define CAPT_DRAW 0xfb
#define MATE 0xfa
#define LOSS_IN_ONE 0xf9
#define CAPT_WIN 1
#define WIN_IN_ONE 2

BROKEN means two pieces on the same square.
ILLEGAL means that the side to move can take the enemy king. (So the corresponding position in the other table is in check -> potentially mate.)
UNKNOWN means not yet known.
CHANGED is used to mark positions which are potentially lost (it is the ancestor of a position which was found to be a win in the last iteration).
CAPT_CLOSS means the position has a capture into a cursed loss.
CAPT_DRAW means the position has a capture into a draw.
MATE means mate.
LOSS_IN_ONE+k mean loss with DTZ=k+1 for k >= 0.
CAPT_WIN means the position has a capture into a win.
WIN_IN_ONE means the position is won with DTZ=1 but not CAPT_WIN. So mate in 1.
WIN_IN_ONE+k means won with DTZ=k+1 for k >= 1.

I'm just revisiting this informative post from Ronald from a few years ago. In the above, it was assumed that the table was pawnless. Let's talk a bit about the pawnful case, though.

Clearly, any pawn move that captures something is a capturing move, and that would include a pawn making a capture while reaching promotion rank. For any of these positions, CAPT_WIN or CAPT_DRAW may eventually be set for the position in question. If either of these happens, then that entry will end up being treated as a position that will never be probed when Syzygy does its compressing after the table has been generated, so it will end up filled with some value that is believed to compress well.

Now, the rub: can't CAPT_WIN or CAPT_DRAW also end up being set when a pawn is pushed but does not make a capture? I mean, clearly, if the pawn promotion square is being reached with the pawn push, then we're definitely hitting a new table. However, even if the pawn promotion square is not reached, while we're not technically reaching a new table, we are reaching a new zeroing-move zone, so isn't it possible that Syzygy might process this in a similar way too? I mean, I've never assumed that any position where there's a possible pawn push would always need to be searched forward instead of probed directly when using Syzygy tables, because that could lead to long sequences of pawn race positions where there's no capturing happening but there nonetheless needs to be lookahead performed regardless in order to probe a pawnful Syzygy table correctly. It seems that there is definitely some room for different choices to be made here, though. So now I'm wondering specifically in the case of the Syzygy table generation and compression algorithm (for regular Chess, not variants) in which cases (if any) a non-capturing pawn move will nonetheless require what we have been referring to as a "capture search" so far. To what extent is "capture search" an oversimplification?

[syzygy]

Now, the rub: can't CAPT_WIN or CAPT_DRAW also end up being set when a pawn is pushed but does not make a capture? I mean, clearly, if the pawn promotion square is being reached with the pawn push, then we're definitely hitting a new table. However, even if the pawn promotion square is not reached, while we're not technically reaching a new table, we are reaching a new zeroing-move zone, so isn't it possible that Syzygy might process this in a similar way too? I mean, I've never assumed that any position where there's a possible pawn push would always need to be searched forward instead of probed directly when using Syzygy tables, because that could lead to long sequences of pawn race positions where there's no capturing happening but there nonetheless needs to be lookahead performed regardless in order to probe a pawnful Syzygy table correctly. It seems that there is definitely some room for different choices to be made here, though. So now I'm wondering specifically in the case of the Syzygy table generation and compression algorithm (for regular Chess, not variants) in which cases (if any) a non-capturing pawn move will nonetheless require what we have been referring to as a "capture search" so far. To what extent is "capture search" an oversimplification?

For pawn moves which are not captures, the pawnful generator uses the PAWN_WIN, PAWN_CWIN and PAWN_DRAW values.
When compressing WDL, these values are treated as regular win-in-1 (similar to mate-in-1, not winning-capture-in-1), cursed-win-in-1 and draw values.
When compressing DTZ, both PAWN_WIN, PAWN_CWIN and PAWN_DRAW are treated as don't care values.

So probe_dtz() may need to try out all pawn moves to detect a (cursed) winning or drawing pawn move as the potentially best move, but for each of these moves it only needs to call probe_wdl(), which should be fine because probe_dtz() is only called at the root, and each probe_wdl() will be succesful (WDL tables being 2-sided). Also, there is no recursion here (probe_wdl() does not need to test pawn moves).

There is no PAWN_BLOSS or PAWN_CLOSS (blessed/cursed loss) because these are not useful for DTZ. A "blessed loss in 1" is worse than a "blessed loss in n > 1", whereas a "cursed win in 1" is better than a "cursed win in n > 1".
(It could be useful for WDL, but then probe_wdl() would have to try out all pawn moves, as you point out, and recursively. That seems way too costly.)

Recently I found a small bug in my generator. I think it was here:
https://github.com/syzygy1/tb/blob/0bb8 ... #L321-L327

Code: Select all

MARK(mark_win_in_1)
{
  MARK_BEGIN;
  if (table[idx2] != ILLEGAL && table[idx2] != CAPT_WIN)
    table[idx2] = WIN_IN_ONE;
  MARK_END;
}

This overwrites PAWN_WIN with WIN_IN_ONE. So a position with both a winning pawn move and a mating move is encoded as win-in-1, whereas it "should" be encoded as don't care. This does not affect correctness (otherwise it would have been found earlier) and it doesn't seem to have a significant impact on compression ratio (but I did not test on many tables). But the correct test is table[idx2] > WIN_IN_ONE.

[noobpwnftw]

Track the current frontier with a bitset works like a charm.

[syzygy]

Track the current frontier with a bitset works like a charm.

Something like https://github.com/syzygy1/tb8gen ?

[syzygy]

For pawn moves which are not captures, the pawnful generator uses the PAWN_WIN, PAWN_CWIN and PAWN_DRAW values.
When compressing WDL, these values are treated as regular win-in-1 (similar to mate-in-1, not winning-capture-in-1), cursed-win-in-1 and draw values.
When compressing DTZ, both PAWN_WIN, PAWN_CWIN and PAWN_DRAW are treated as don't care values.

So PAWN_DRAW is actually treated in the same way as a regular draw both when compressing WDL and when compressing DTZ. I think the generator uses it only to mark positions with a drawing capture as "at least" a draw to avoid having to look at pawn moves, including promotions, more than once. ("Regular" draws are only determined to be draws when they are still UNKNOWN when the generation process finishes.)

My generator marks positions which are found to have a "best" pawn move leading to a cursed/blessed loss as CAPT_CLOSS. This seems suspect at first because CAPT_CLOSS positions can be encoded as losing in the WDL table (which will then corrected by the probing code noting that a cursed/blessed loss can be achieved by a capture). However, the initial assignment as CAPT_CLOSS to a position is just to mark it as a candidate loss, which will then be verified in iter() and marked either as la oss-in-101-ply or as (still) UNKNOWN.