Anyway, to further the public-domain cause, the following code actually runs, and prints some numbers that seem to make sense (like the number of stalemates, which matches what I calculated by hand). I even put in the initial double-push, which is important for rule-of-squares situations.
Btw, this is the dumb algorithm, which does not use any unmoves. It just attempts regular moving from all not-yet-decided positions, to look for a move to a won position for white, and to a non-lost position for black.
Code: Select all
/* Public-domain KPK bitbase code by H.G. Muller */
#define WTM 0
#define BTM 1
char dtc[2][64][64][64]; // 512 KB
char bitbase[2*64*64*3];
char steps[] = {1, -1, 16, -16, 15, -15, 17, -17}; // 0x88 King steps
void
Init ()
{ /* 3 = bK captured, 2 = can capture bK, 1 = won, 0 = undecided, -1 = broken or wK captured */
int wk, bk, p;
for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {
if(bk == wk) dtc[BTM][wk][p][bk] = 3, dtc[WTM][wk][p][bk] = -1; else
if(wk == p) dtc[BTM][wk][p][bk] = dtc[WTM][wk][p][bk] = -1; else
if(bk == p) dtc[BTM][wk][p][bk] = -3; else // with WTM black just captured P
if(p >= 56) dtc[WTM][wk][p][bk] = 1; // promoted and on move = win
}
}
void
Pass (int stm, int first, int def, int esc)
{
int wk, bk, p, d;
for(wk=0; wk<64; wk++) for(p=0; p<64; p++) for(bk=0; bk<64; bk++) {
int k = stm == WTM ? wk : bk;
int O88 = (k & 070) + k; // 0x88 square number of King
if(dtc[stm][wk][p][bk]) continue; // already decided
dtc[stm][wk][p][bk] = def; // assume lost if btm, undecided if wtm
if(bk != p && stm == WTM) { // pawn not captured, so can move
if(p+8 != bk && (dtc[BTM][wk][p+8 ][bk] > first || p < 16 &&
p+16 != bk && dtc[BTM][wk][p+16][bk] > first)) { dtc[WTM][wk][p][bk] = esc; continue; }
if(p+7 == bk && (p & 7) != 0) { dtc[WTM][wk][p][bk] = 2; continue; }
if(p+9 == bk && (p & 7) != 7) { dtc[WTM][wk][p][bk] = 2; continue; }
}
for(d=0; d<8; d++) {
int to = O88 + steps[d];
if(to & 0x88) continue; // off board
to -= to>>1 & 070;
if(stm == WTM ? dtc[BTM][to][p][bk] > first : dtc[WTM][wk][p][to] <= first)
{ dtc[stm][wk][p][bk] = esc; break; }
}
}
}
void
Pack ()
{
int wk, bk, p, i;
for(wk=0; wk<64; wk++) for(p=8; p<56; p+=2) for(bk=0; bk<64; bk++) { // calculate probe address and bit
int index = (bk >> 3) + 8*wk + 8*64*(p-8>>1);
bitbase[2*index] |= (dtc[WTM][wk][p][bk] > 0) << (bk & 7);
bitbase[2*index+1] |= (dtc[BTM][wk][p][bk] > 0) << (bk & 7);
}
}
void
Build ()
{
int i;
Init();
Pass(WTM, 2, 0, 2); Pass(BTM, 1, -2, 0); // calculate King captures and
stalemates
for(i=0; i<25; i++) // won't take more than 25 moves
Pass(WTM, 0, 0, 1), Pass(BTM, 0, 1, 0);
Pack();
}
Code: Select all
white to move: 124960+, 41044=, 6096-, 0 stalemate, 24508 K-capture
black to move: 97604+, 89866=, 6066-, 18 stalemate, 0 K-capture