Code: Select all
// pseudo-code for leap-frog solution of KQK
// Note it is not really essential to store the full DTx of BTM positions
// For efficiency, however, it is important to be able to distinguish
// the entries decided in the most-recent cycle from those assigned earlier
//
// The basic structure has the nesting
//
// SCAN staticPieces
// SCAN dynamicPieces
// MOVE dynamicPieces
#define WHITE_KING 0
#define WHITE_QUEEN 1
#define BLACK_KING 2
int lostBTM[64*64*64];
boolean wonWTM[64*64*64];
int pos[NR_OF_MEN];
DoSlice(int N, int whiteDynamicPiece, int whiteStaticPiece)
{
// perform one cycle through grandparent algorithm within cached slice
for(pos[whiteDynamicPiece] = 0 to 63) {
for(pos[blackKing] = 0 to 63) {
if(lostBTM[currentPosition] == N) {
while(move1 = NextMove(whiteDynamicPiece)) {
Make(move1);
if(!wonWTM[currentPosition]) {
wonWTM[currentPosition] = 1;
while(move2 = NextMove(BLACK_KING)) {
Make(move2);
if(lostBTM[currentPosition] == UNDECIDED) {
while(move3 = NextMove(BLACK_KING)) {
Make(move3);
escape = !wonWTM[currentPosition];
UnMake(move3);
if(escape) goto cutoff;
}
lostBTM[currentPosition] = N+1;
cutoff:
}
Unmake(Move2);
}
}
Unmake(move1);
}
}
}
}
}
DoCycles(int N, boolean leapFrog, int whiteDynamicPiece, int whiteStaticPiece)
{
for(pos[whiteStaticPiece]=0 to 63) {
// do the N -> N+1 cycle for the slice that keeps the whiteStaticPiece fixed
// in the current place. The slice fits in fast storage,
// and all moves remain inside of it
DoSlice(N, whiteDynamicPiece, whiteStaticPiece);
if(!leapFrog) continue;
// the slice with the whiteStaticPiece fixed (64*64 entries)
// is still in fast storage after this. Make use of that by doing
// the N+1 -> N+2 cycle in this slice as well, now that we are finished
// determining the lostBTM[] == N+1 positions.
DoSlice(N+1, whiteDynamicPiece, whiteStaticPiece);
}
}
build()
{
int N = 0;
LabelCheckmatesAndIllegals();
// now lostBTM[i] is set to 0 for every checkmate, and to UNDECIDED for others
// wonWTM is set to 1 for every position where black is in check.
DoCycles(N, FALSE, WHITE_KING, WHITE_QUEEN);
do {
DoCycles(N, TRUE, WHITE_QUEEN, WHITE_KING);
if(FINISHED) break;
N++;
DoCycles(N, TRUE, WHITE_KING, WHITE_QUEEN);
N++;
} while(!FINISHED);
}