#include <limits.h>
#include "sjeng.h"
#include "extvars.h"
#include "protos.h"
#include "squares.h"
#define FILE(x) ((x) & 7)
#define RANK(x) ((x) >> 3)
#define TWO_PIECE_SIZE 4096
#define TWO_PIECE_HASH(x,y,z) (((((x) << 5) | (y)) << 6) | (z))
#define TWO_PIECE_FILE "stb/2pieces.bin"
#define THREE_PIECE_SIZE (64*TWO_PIECE_SIZE)
#define THREE_PIECE_HASH(x,y,z,w) (((((((x) << 5) | (y)) << 6) | (z)) << 6) | (w))
#define THREE_PIECE_FILE "stb/xxx.bin"
#define TABLE_KEY(x,y,z) (((((x) << 3) | (y)) << 3) | (z))
#define IO_BUFSIZE 4096
#define CACHE_SIZE 8
int upscale[64] = {
A1,B1,C1,D1,E1,F1,G1,H1,
A2,B2,C2,D2,E2,F2,G2,H2,
A3,B3,C3,D3,E3,F3,G3,H3,
A4,B4,C4,D4,E4,F4,G4,H4,
A5,B5,C5,D5,E5,F5,G5,H5,
A6,B6,C6,D6,E6,F6,G6,H6,
A7,B7,C7,D7,E7,F7,G7,H7,
A8,B8,C8,D8,E8,F8,G8,H8
};
int vertical_flip[64] = {
7, 6, 5, 4, 3, 2, 1, 0,
15, 14, 13, 12, 11, 10, 9, 8,
23, 22, 21, 20, 19, 18, 17, 16,
31, 30, 29, 28, 27, 26, 25, 24,
39, 38, 37, 36, 35, 34, 33, 32,
47, 46, 45, 44, 43, 42, 41, 40,
55, 54, 53, 52, 51, 50, 49, 48,
63, 62, 61, 60, 59, 58, 57, 56
};
int rotate[64] = {
63, 62, 61, 60, 59, 58, 57, 56,
55, 54, 53, 52, 51, 50, 49, 48,
47, 46, 45, 44, 43, 42, 41, 40,
39, 38, 37, 36, 35, 34, 33, 32,
31, 30, 29, 28, 27, 26, 25, 24,
23, 22, 21, 20, 19, 18, 17, 16,
15, 14, 13, 12, 11, 10, 9, 8,
7, 6, 5, 4, 3, 2, 1, 0
};
int white_addr[64] = {
0, 1, 2, 3, -1, -1, -1, -1,
4, 5, 6, 7, -1, -1, -1, -1,
8, 9, 10, 11, -1, -1, -1, -1,
12, 13, 14, 15, -1, -1, -1, -1,
16, 17, 18, 19, -1, -1, -1, -1,
20, 21, 22, 23, -1, -1, -1, -1,
24, 25, 26, 27, -1, -1, -1, -1,
28, 29, 30, 31, -1, -1, -1, -1
};
int section_map[6][6] = {
{ 0, 1, 2, 3, 4, 5 },
{ -1, 6, 7, 8, 9, 10 },
{ -1, -1, 11, 12, 13, 14 },
{ -1, -1, -1, 15, 16, 17 },
{ -1, -1, -1, -1, 18, 19 },
{ -1, -1, -1, -1, -1, 20 }
};
int section_trans[] = {666, 0, 0, 1, 1, 5, 5, 3, 3, 4, 4, 2, 2, 6};
char xpiece_char[] = {'F','P','P','N','N','K','K','R','R','Q','Q','B','B','E' };
typedef struct
{
int table_key;
int last_access;
} cache_data;
signed char *two_piece_data;
signed char *three_piece_data;
signed char *temp_table;
int cache_counter;
cache_data table_cache[CACHE_SIZE];
int temp_key;
int SEGTB;
int valid_2piece(int w, int b, int w_man, int b_man)
{
if(white_addr[w] == -1)
return 0;
if(w == b)
return 0;
if(w_man == wpawn || w_man == bpawn)
if(w < 8 || w > 55)
return 0;
if(b_man == bpawn || b_man == wpawn)
if(b < 8 || b > 55)
return 0;
return 1;
}
int valid_3piece(int w, int b1, int b2, int w_man, int b1_man, int b2_man)
{
if(white_addr[w] == -1)
return 0;
if(w == b1)
return 0;
if(w == b2)
return 0;
if(b1 == b2)
return 0;
if(w_man == wpawn || w_man == bpawn)
if(w < 8 || w > 55)
return 0;
if(b1_man == bpawn || b1_man == wpawn)
if(b1 < 8 || b1 > 55)
return 0;
if(b2_man == bpawn || b2_man == wpawn)
if(b2 < 8 || b2 > 55)
return 0;
return 1;
}
int check_result()
{
int p, xp, res;
int wp = 0, bp = 0;
int a, j, i;
move_s moves[MOVE_BUFF];
int num_moves;
for (j = 1, a = 1; (a <= piece_count); j++)
{
i = pieces[j];
if (!i)
continue;
else
a++;
switch (board[i])
{
case wpawn:
case wbishop:
case wrook:
case wking:
case wqueen:
case wknight: wp++; break;
case bpawn:
case bbishop:
case brook:
case bking:
case bqueen:
case bknight: bp++; break;
}
}
if (!(wp) && (bp))
{
if (white_to_move)
{
return -127;
}
else
{
return 126;
}
}
else if ((!bp) && (wp))
{
if (white_to_move)
{
return 126;
}
else
{
return -127;
}
}
gen(&moves[0]);
num_moves = numb_moves;
if(!num_moves)
{
if (white_to_move)
{
p = wp;
xp = bp;
}
else
{
p = bp;
xp = wp;
}
if(p < xp) return -127;
else if(xp < p) return 126;
else return 0;
}
res = egtb(white_to_move);
if(res > -10 && res < 10 && res)
printf("Warning: near zero values!\n");
if(res > 0)
return -res+1;
else if(res < 0 && res > -128)
return -res-1;
return res;
}
void gen_2piece(int w_man, int b_man, signed char *table)
{
int i, w, b, t, addr;
signed char best, res;
int f, unknown;
move_s moves[MOVE_BUFF];
int num_moves;
ply = 1;
reset_board();
memset(table, -128, TWO_PIECE_SIZE);
if (!(w_man & 1)) w_man--;
if (b_man & 1) b_man++;
do
{
f = FALSE;
for(t = 0; t < 2; t++)
{
white_to_move = t;
for(w = 0; w < 64; w++)
{
for(b = 0; b < 64; b++)
{
if(!valid_2piece(w, b, w_man, b_man)) continue;
addr = TWO_PIECE_HASH(t, white_addr[w], b);
if(table[addr] != -128) continue;
board[upscale[w]] = w_man;
board[upscale[b]] = b_man;
pieces[1] = upscale[w];
pieces[2] = upscale[b];
squares[upscale[w]] = 1;
squares[upscale[b]] = 2;
piece_count = 2;
ep_square = 0;
gen(&moves[0]);
num_moves = numb_moves;
if(num_moves == 0)
{
if (table[addr] != 0) f = TRUE;
table[addr] = 0;
}
else
{
best = -128;
unknown = FALSE;
for(i = 0; i < num_moves; i++)
{
make(&moves[0], i);
res = (signed char) check_result();
unmake(&moves[0], i);
if(res == -128)
{
unknown = TRUE;
continue;
}
if(res > best) best = res;
}
if(best > 0 || (best < 0 && !unknown))
{
if (table[addr] != best) f = TRUE;
table[addr] = best;
}
}
board[upscale[w]] = npiece;
board[upscale[b]] = npiece;
squares[upscale[w]] = 0;
squares[upscale[b]] = 0;
pieces[1] = 0;
pieces[2] = 0;
}
}
}
printf(".");
}
while(f);
printf("\n");
for(i = 0; i < TWO_PIECE_SIZE; i++)
if(table[i] == -128) table[i] = 0;
}
void gen_3piece(int w_man, int b1_man, int b2_man, signed char *table)
{
int i, w, b1, b2, t, addr;
signed char best, res;
int f, unknown;
move_s moves[MOVE_BUFF];
int num_moves;
ply = 1;
reset_board();
memset(table, -128, THREE_PIECE_SIZE);
if (!(w_man & 1)) w_man--;
if (b1_man & 1) b1_man++;
if (b2_man & 1) b2_man++;
do
{
f = FALSE;
for(t = 0; t < 2; t++)
{
white_to_move = t;
for(w = 0; w < 64; w++)
{
for(b1 = 0; b1 < 64; b1++)
{
for(b2 = 0; b2 < 64; b2++)
{
if(!valid_3piece(w, b1, b2, w_man, b1_man, b2_man)) continue;
addr = THREE_PIECE_HASH(t, white_addr[w], b1, b2);
board[upscale[w]] = w_man;
board[upscale[b1]] = b1_man;
board[upscale[b2]] = b2_man;
piece_count = 3;
pieces[1] = upscale[w];
pieces[2] = upscale[b1];
pieces[3] = upscale[b2];
squares[upscale[w]] = 1;
squares[upscale[b1]] = 2;
squares[upscale[b2]] = 3;
ep_square = 0;
gen(&moves[0]);
num_moves = numb_moves;
if(!num_moves)
{
if (table[addr] != (white_to_move ? 126 : -127))
f = TRUE;
table[addr] = (white_to_move ? 126 : -127);
}
else
{
best = -128;
unknown = FALSE;
for(i = 0; i < num_moves; i++)
{
make(&moves[0], i);
res = (signed char) check_result();
unmake(&moves[0], i);
if(res == -128)
{
unknown = TRUE;
continue;
}
if(res > best) best = res;
}
if(best > 0 || (best < 0 && !unknown))
{
if (table[addr] != best) f = TRUE;
table[addr] = best;
}
}
board[upscale[w]] = npiece;
board[upscale[b1]] = npiece;
board[upscale[b2]] = npiece;
squares[upscale[w]] = 0;
squares[upscale[b1]] = 0;
squares[upscale[b2]] = 0;
pieces[1] = 0;
pieces[2] = 0;
pieces[3] = 0;
}
}
}
}
printf(".");
}
while(f);
printf("\n");
for(i = 0; i < THREE_PIECE_SIZE; i++)
if(table[i] == -128) table[i] = 0;
}
int save_2piece()
{
int i, j;
FILE *f;
signed char *table;
if(!(f = fopen(TWO_PIECE_FILE, "w"))) return 0;
for(i = 0; i < 21; i++)
{
table = two_piece_data + i * TWO_PIECE_SIZE;
for(j = 0 ; j < TWO_PIECE_SIZE; j++)
{
fputc(table[j], f);
}
}
fclose(f);
return 1;
}
int save_3piece(int w1_man, int b1_man, int b2_man, signed char *t)
{
FILE *f;
signed char fname[13];
signed char *buf;
int i;
strcpy(fname, THREE_PIECE_FILE);
fname[4] = xpiece_char[w1_man];
fname[5] = xpiece_char[b1_man];
fname[6] = xpiece_char[b2_man];
if(!(f = fopen(fname,"w"))) return 0;
for(i = 0; i < THREE_PIECE_SIZE; i += IO_BUFSIZE)
{
buf = t + i;
if(!fwrite(buf, IO_BUFSIZE, 1, f))
{
printf("Error writing %s\n",fname);
fclose(f);
return 0;
}
}
fclose(f);
return 1;
}
void gen_all_tables()
{
int w_man, b1_man, b2_man;
signed char *base_addr;
printf("Two-piece tables:\n");
for(w_man = wknight; w_man <= wbishop; w_man += 2)
{
for(b1_man = bknight; b1_man <= bbishop; b1_man += 2)
{
if(section_map[section_trans[w_man]][section_trans[b1_man]] == -1) continue;
printf("Generating %c vs %c ",
xpiece_char[w_man], xpiece_char[b1_man]);
base_addr = two_piece_data
+ (section_map[section_trans[w_man]][section_trans[b1_man]] * TWO_PIECE_SIZE);
gen_2piece(w_man, b1_man, base_addr);
}
}
w_man = wpawn;
for(b1_man = bknight; b1_man <= bbishop; b1_man += 2)
{
if(section_map[section_trans[w_man]][section_trans[b1_man]] == -1) continue;
printf("Generating %c vs %c ",
xpiece_char[w_man], xpiece_char[b1_man]);
base_addr = two_piece_data
+ (section_map[section_trans[w_man]][section_trans[b1_man]] * TWO_PIECE_SIZE);
gen_2piece(w_man, b1_man, base_addr);
}
printf("Generating %c vs %c ",
xpiece_char[wpawn], xpiece_char[bpawn]);
base_addr = two_piece_data
+ (section_map[section_trans[wpawn]][section_trans[bpawn]]*TWO_PIECE_SIZE);
gen_2piece(wpawn, bpawn, base_addr);
if(save_2piece())
printf("Saved two-piece tables in %s\n", TWO_PIECE_FILE);
temp_table = malloc(THREE_PIECE_SIZE);
if(!temp_table) return;
for(w_man = wknight; w_man <= wbishop; w_man += 2)
for(b1_man = bknight; b1_man <= bbishop ; b1_man += 2)
for(b2_man = bknight; b2_man <= bbishop; b2_man += 2)
{
if(section_map[section_trans[b1_man]][section_trans[b2_man]] == -1) continue;
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
}
w_man = wpawn;
for(b1_man = bknight; b1_man <= bbishop; b1_man += 2)
for(b2_man = bknight; b2_man <= bbishop; b2_man += 2)
{
if(section_map[section_trans[b1_man]][section_trans[b2_man]] == -1) continue;
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
}
for(w_man = wknight; w_man <= wbishop; w_man += 2)
{
b1_man = bpawn;
for(b2_man = wknight; b2_man <= bbishop; b2_man += 2)
{
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
}
}
w_man = wpawn;
b1_man = bpawn;
for(b2_man = bknight; b2_man <= bbishop; b2_man += 2)
{
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
}
for(w_man = wknight; w_man <= wbishop; w_man += 2)
{
b1_man = bpawn;
b2_man = bpawn;
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
}
w_man = wpawn;
b1_man = bpawn;
b2_man = bpawn;
printf("Generating %c vs %c+%c ", xpiece_char[w_man],
xpiece_char[b1_man], xpiece_char[b2_man]);
temp_key = TABLE_KEY(section_trans[w_man],
section_trans[b1_man],
section_trans[b2_man]);
gen_3piece(w_man, b1_man, b2_man, temp_table);
save_3piece(w_man, b1_man, b2_man, temp_table);
printf("\nAll done.\n");
free(temp_table);
reset_board();
}
void free_egtb()
{
free(two_piece_data);
free(three_piece_data);
}
int init_segtb()
{
int i;
two_piece_data = malloc(21 * TWO_PIECE_SIZE);
three_piece_data = malloc(CACHE_SIZE * THREE_PIECE_SIZE);
if(!two_piece_data || !three_piece_data)
{
return FALSE;
}
if(!load_2piece())
{
return FALSE;
}
for(i = 0; i < CACHE_SIZE; i++)
{
table_cache[i].table_key = -1;
table_cache[i].last_access = 0;
}
cache_counter = 0;
temp_key = -1;
printf("Two-piece suicide endgame tables preloaded (using %d kB of memory)\n",
(21 * TWO_PIECE_SIZE) / 1024);
printf("Three-piece suicide endgame table cache %d kB\n",
(CACHE_SIZE * THREE_PIECE_SIZE) / 1024);
return TRUE;
}
int egtb(int s)
{
int w1_man, w2_man, b1_man, b2_man;
int w1, w2, b1, b2;
int w_count = 0, b_count = 0;
int i, t, temp, junk, bpc;
signed char *table;
for(i = 0; i < 64; i++)
{
bpc = board[upscale[i]];
if (bpc == npiece) continue;
if(bpc & 1)
{
if(!w_count)
{
w1_man = bpc;
w1 = i;
}
else
{
w2_man = bpc;
w2 = i;
}
w_count++;
}
else
{
if(!b_count)
{
b1_man = bpc;
b1 = i;
}
else
{
b2_man = bpc;
b2 = i;
}
b_count++;
}
}
if(w_count == 1 && b_count == 1) {
if(section_map[section_trans[w1_man]][section_trans[b1_man]] == -1)
{
temp = b1_man;
b1_man = w1_man;
w1_man = temp;
temp = b1;
if(w1_man == wpawn || w1_man == bpawn)
{
b1 = rotate[w1];
w1 = rotate[temp];
}
else
{
b1 = w1;
w1 = temp;
}
s ^= 1;
}
table = two_piece_data
+ (section_map[section_trans[w1_man]][section_trans[b1_man]] * TWO_PIECE_SIZE);
if(white_addr[w1] == -1)
{
w1 = vertical_flip[w1];
b1 = vertical_flip[b1];
}
return (int)table[TWO_PIECE_HASH(s, white_addr[w1], b1)];
}
else if((w_count == 1 && b_count == 2) ||
(w_count == 2 && b_count == 1))
{
if(w_count > 1)
{
b2_man = w2_man;
temp = w1_man;
w1_man = b1_man;
b1_man = temp;
temp = w1;
if(w1_man == wpawn || w1_man == bpawn ||
b1_man == bpawn || b1_man == wpawn ||
b2_man == bpawn || b2_man == wpawn)
{
b2 = rotate[w2];
w1 = rotate[b1];
b1 = rotate[temp];
}
else
{
b2 = w2;
w1 = b1;
b1 = temp;
}
s ^= 1;
}
if(section_map[section_trans[b1_man]][section_trans[b2_man]] == -1)
{
temp = b1_man;
b1_man = b2_man;
b2_man = temp;
temp = b1;
b1 = b2;
b2 = temp;
}
if(white_addr[w1] == -1)
{
w1 = vertical_flip[w1];
b1 = vertical_flip[b1];
b2 = vertical_flip[b2];
}
t = TABLE_KEY(section_trans[w1_man],
section_trans[b1_man],
section_trans[b2_man]);
if(temp_key == t)
table = temp_table;
else
{
temp = INT_MAX;
cache_counter++;
for(i = 0; i < CACHE_SIZE; i++)
{
if(table_cache[i].table_key == t)
{
table = three_piece_data + (i * THREE_PIECE_SIZE);
table_cache[i].last_access = cache_counter;
return (int) table[THREE_PIECE_HASH(s, white_addr[w1], b1, b2)];
}
else if(table_cache[i].last_access < temp)
{
temp = table_cache[i].last_access;
junk = i;
}
}
table = three_piece_data + (junk * THREE_PIECE_SIZE);
if(!load_3piece(w1_man, b1_man, b2_man, table))
{
table_cache[junk].table_key = -1;
return (-128);
}
table_cache[junk].table_key = t;
table_cache[junk].last_access = cache_counter;
}
return (int) table[THREE_PIECE_HASH(s, white_addr[w1], b1, b2)];
}
else
return (-128);
}
int load_2piece()
{
int i,j;
FILE *f;
signed char *table;
if(!(f = fopen(TWO_PIECE_FILE, "r"))) return 0;
for(i = 0; i < 21; i++)
{
table = two_piece_data + i * TWO_PIECE_SIZE;
for(j = 0; j < TWO_PIECE_SIZE; j++)
table[j] = (signed char) fgetc(f);
}
fclose(f);
return 1;
}
int load_3piece(int w1_man, int b1_man, int b2_man, signed char *t)
{
FILE *f;
signed char fname[13];
signed char *buf;
int i;
strcpy(fname, THREE_PIECE_FILE);
fname[4]= xpiece_char[w1_man];
fname[5]= xpiece_char[b1_man];
fname[6]= xpiece_char[b2_man];
if(!(f = fopen(fname,"r"))) return 0;
for(i = 0; i < THREE_PIECE_SIZE; i += IO_BUFSIZE)
{
buf = t + i;
if(!fread(buf, IO_BUFSIZE, 1, f)) {
printf("Error reading %s\n",fname);
fclose(f);
return 0;
}
}
fclose(f);
return 1;
}