Code: Select all
/***************************************************************************/
/* EGT generator to determine mating potential for 3 men vs bare King. */
/* */
/* The generator does not make any symmetry assumption. */
/* It uses some simplifications that would not work for a general-purpose */
/* EGT generator: */
/* - Black has a bare royal piece, which is non-divergent, so that all its */
/* moves can both go to empty and occupied (will be opponent!) squares. */
/* - None of the white pieces has mating potential by itself, so that any */
/* capture of an unprotected piece automatically draws. */
/* */
/* H.G. Muller, (c) 2011 */
/***************************************************************************/
#include <stdio.h>
#include <time.h>
typedef int int_ptr;
#define BWIDTH 8
#define BSIZE BWIDTH*8
#define STRIDE3 BSIZE
#define STRIDE2 (STRIDE3*BSIZE + BSIZE)
#define STRIDE1 (STRIDE2*BSIZE + BSIZE)
#define b (board + 2*BSIZE + BWIDTH)
#define SEC (1./CLOCKS_PER_SEC)
/*
* Some macros to define often-used control constructs
*/
// loop through all moves of given piece. capts indicates which captures will be accepted
#define FOR_ALL_MOVES(movelist, from, index, capts) \
{ int r, f; \
for(r=movelist; f=flags[r]; r++) { \
int v=steps[r], to=from, nwind=index; \
while(b[to+=v] <= capts) { \
nwind += isteps[r]; \
#define NEXT_MOVE \
if(b[to] || f&4) break; \
} \
} \
}
// scan through tablebase and update 0x88 board in lockstep
#define SCAN(p, index, start, stride) \
for(nr[p]=0, index=start; nr[p]<BSIZE; nr[p]++, index+=stride) { \
pos[p] = Ox88[nr[p]]; \
if(b[pos[p]]) continue; /* skip broken positions */ \
b[pos[p]] = p+1;
#define NEXT(p) \
b[pos[p]] = 0; \
}
/*
* Global variables: board & piece-list, move-gen and auxiliary tables
*/
unsigned int Ox88[BSIZE]; // raster-scan square nr to 0x88 square nr translation table
unsigned char board[6*BSIZE + BWIDTH]; // raw 0x88 board with generous guard band
int pos[4]; // piece locations on 0x88 board; piece 3 = black King, 2 = white King, 0 & 1 other white men
int nr[4]; // piece locations as raster-scan number;
int first[4], firstCapts[4]; // indicate first entry in move table for each piece.
int N, wcnt, todo;
unsigned char *EGT, *map;
signed char steps[128], flags[128];
int isteps[128], cnt[256], ptr;
// char array[1500000000];
// sample piece descriptions: (mode, delta_x, delta_y) triples, where mode 4=leaper, 2=non-capt, 1=capt
int king[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0};
int knight[] = {7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int zebra[] = {7,2,3, 7,2,-3, 7,-2,-3, 7,-2,3, 7,3,2, 7,-3,2, 7,3,-2, 7,-3,-2, 0};
int camel[] = {7,3,1, 7,3,-1, 7,-3,-1, 7,-3,1, 7,1,3, 7,-1,3, 7,1,-3, 7,-1,-3, 0};
int bishop[] = {3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 0};
int wazir[] = {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0};
int ferz[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 0};
int silver[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,0,1, 0};
int copper[] = {7,1,1, 7,-1,1, 7,0,1, 7,0,-1, 0};
int omni[] = {5,1,1, 5,1,-1, 5,-1,-1, 5,-1,1, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0};
int lang[] = {7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 7,3,3, 7,3,-3, 7,-3,3, 7,-3,-3, 0};
int phoenix[]= {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int alibaba[]= {7,2,0, 7,-2,0, 7,0,2, 7,0,-2, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int unicorn[]= {7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int elephant[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0};
int fibnif[] = {7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0};
int admiral[]= {3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 3,2,0, 3,0,2, 3,0,-2, 3,-2,0, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0};
/*
* Initialization stuff
*/
// routines to prepare move-gen tables from the piece descriptors.
// each piece has two tables; one used for retrograde moving (so contains only non-captures),
// one for forward moving. Both the 0x88 board step and EGT index step are tabulated in each.
// To allow for asymmetric pieces, the retro table flips the sign, so it can be used with the same generator.
// The forward table is used for black king escapes, and for determining black-king locations that are
// attacked by the white pieces (by generating captures of the latter on empty squares with black-king stride).
int Fill(int sgn, int mode, int *desc, int stride)
{
int i, res = ptr;
for(i=0; desc[i]; i+=3) {
if(!(desc[i] & mode)) continue; // skip directions we cannot capture in;
steps[ptr] = sgn*(2*BWIDTH*desc[i+1] + desc[i+2]);
isteps[ptr] = sgn*(BWIDTH*desc[i+1] + desc[i+2])*stride;
flags[ptr++] = desc[i];
}
flags[ptr++] = 0;
return res;
}
int AddPiece(int nr, signed int *desc, int stride)
{
first[nr] = Fill(-1, 2, desc, stride); // unmoves, so flip sign, and non-capts only
firstCapts[nr] = Fill( 1, 1, desc, 1); // captures only
}
static Init(int *desc1, int *desc2, int *desc3, int *desc4, void *mem)
{
int i, j;
// create empty 0x88 board with large guard band
for(i=0; i<6*BSIZE+BWIDTH; i++) board[i] = 5; // guards
for(i=0; i<BSIZE; i++) b[Ox88[i] = (i/BWIDTH)*BWIDTH + i] = 0;
for(i=0; i<256; i++) cnt[i] = 0; // reset stats
// load move-generator tables
AddPiece(0, desc1, STRIDE1); // N
AddPiece(1, desc2, STRIDE2); // B
AddPiece(2, desc3, STRIDE3); // K
AddPiece(3, desc4, 1); // K
// allocate and cache-align main storage
EGT = (unsigned char*) mem;
if(!EGT)
EGT = (unsigned char*) ((int_ptr)malloc(j = BSIZE*STRIDE1+64) + 63 & ~(int_ptr)63);
printf("allocate %d bytes at %x\n", j, (int) EGT);
}
/*
* routines for retrograde generation through 3-ply tree (2 unmoves followed by 1 move)
*/
static int Escape(int sq, int index)
{ // try black King moves (assumed to be valid as both capts and non-capts!)
FOR_ALL_MOVES(firstCapts[3], sq, index, 3)
if(!(EGT[nwind] & 1)) return 1;
NEXT_MOVE
return 0;
}
static void RetroBlack(int index, int kpos)
{
// don't bother to move black king; the move it blocks on verify went to the now won position
FOR_ALL_MOVES(first[3], kpos, index, 0)
if(!Escape(to, nwind)) {
EGT[nwind] |= N+2;
cnt[N+2]++; todo += 3; // takes 3 visits to treat!
}
NEXT_MOVE
}
static void RetroWhite(int p, int index, int kpos)
{
b[kpos] = 4; // place black King on board to prevent white unmoving to broken position
b[pos[p]] = 0; // start making white unmove by removing piece from 0x88 board
FOR_ALL_MOVES(first[p], pos[p], index, 0)
if(!(EGT[nwind] & 1)) { // parent was not yet marked as won
EGT[nwind] |= 1; // mark it
b[to] = p+1; // complete white unmove on 0x88 board
RetroBlack(nwind, kpos); // check if this closes last escape of parents (making them lost)
b[to] = 0;
cnt[N+1]++;
}
NEXT_MOVE
b[pos[p]] = p+1;
b[kpos] = 0;
todo--;
}
static void IterStart31()
{
int i1, i2, i3, k, p;
SCAN(1, i1, 0, STRIDE2)
SCAN(2, i2, i1, STRIDE3)
SCAN(0, i3, i2, STRIDE1)
// at this point the board goes through all white constellations,
// while i3 is the corresponding white contribution to the index
// mark checks in current black chunk, by making all possible white capture steps
for(p=0; p<3; p++) {
FOR_ALL_MOVES(firstCapts[p], pos[p], i3+nr[p], 2) // allow capt of own piece 0 & 1 and non-capts
cnt[1] += !b[to] & !EGT[nwind]; // do not count broken or doubles
EGT[nwind] = 1;
NEXT_MOVE
}
// label checkmates in the chunk where we just marked all captures
for(k=0; k<BSIZE; k++) { // when not in check, or broken position, no testing needed
if(EGT[i3+k] && !b[Ox88[k]] && !Escape(Ox88[k], i3+k) ) EGT[i3+k] = 3, cnt[2]++, todo += 3;
}
NEXT(0)
NEXT(2)
NEXT(1)
}
void *Build31(desc1, desc2, desc3, desc4, verbose, mem)
int *desc1, *desc2, *desc3, *desc4; // piece descriptions
int verbose; // flag to enable printing
void *mem; // memory area to build EGT in (if NULL the memory is allocated)
// returns start of end-game table (which can be different from mem, because of alignment to cache-line boundaries)
{
int i1, i2, i3, k, p;
clock_t t;
Init(desc1, desc2, desc3, desc4, mem); // initialize auxiliary tables
if(!EGT) return (void*) EGT; // allocation failed, abort
N=2; // double of iteration count
todo = 0; t = clock();
IterStart31(); // detrmine checkmates, first half (piece-0 moves) of iteration 1
if(verbose) printf(" mated mate\nKing captures %d\nmates %7d (%5.2f sec)\n",
cnt[1], cnt[2], (clock()-t)*SEC);
while(todo) { // plain iteration; cache unfriendly!
// treat unmoves of white pieces 1 and 2 (plus black unmoves & verification), two iterations
SCAN(0, i1, 0, STRIDE1)
SCAN(1, i2, i1, STRIDE2)
SCAN(2, i3, i2, STRIDE3)
for(k=0; k<BSIZE; k++)
if((EGT[i3+k] & ~1) == N) /* broken won't ever match! */
for(p=0; p<3; p++) RetroWhite(p, i3+k, Ox88[k]);
NEXT(2)
NEXT(1)
NEXT(0)
if(verbose) printf("in-%-2d %7d %7d (%5.2f sec)\n", N/2, cnt[N+2], cnt[N+1], (clock()-t)*SEC);
N += 2;
if(N>253) break;
}
return (void*) EGT;
}
PrintStats()
{
int i, wtot=0, btot=0, wsum=0, bsum=0;
double tot;
tot = BSIZE;
tot = 100./(tot*(tot-1)*(tot-2)*(tot-3));
for(i=0; i<254; i+=2) wtot+=cnt[i+1], btot+=cnt[i+2], wsum+=i*cnt[i+1], bsum+=i*cnt[i+2];
printf("won: %9d (%5.1f%%)\nlost: %9d (%5.1f%%)\navg: %9.1f moves\n",
wtot, wtot*tot, btot, btot*tot, bsum*0.5/btot);
}
main()
{
Build31(knight, bishop, king, king, 1, NULL); // NBKK
PrintStats();
}