/* -*- mode: C; fill-column: 100; eval: (c-set-style "stroustrup"); -*- * * HOFFMAN - a chess endgame tablebase builder * * by Brent Baccala * * August, 2006 * * no rights reserved; you may freely copy, modify, or distribute HOFFMAN * * written in C for speed * * This program is formated for a (minimum) 100 character wide display. * * INTRODUCTION * * This program calculates chess tablebases, which are large files containing all possible * configurations of chess pieces in an endgame and the best play to either win or draw. Unlike a * conventional chess engine, which uses a heuristic evaluation function, a retrograde engine is * almost completely non-heuristic. When it labels a position as a win, it is because it has * considered all possibles lines, be they 10, 20, or 100 moves long, and determined that the win is * forced, even with best play by the opposing side. Some chess-like games, such as the Japanese * game Shogi, are not suitable for retrograde analysis because pieces never leave the game * (captured pieces in Shogi can be put back into play by the capturing player). Yet for chess, the * frequent reduction of games to positions where only a handful of pieces remain has created an * entire subfield of endgame analysis. * * Systematic analysis of chess endgames dates at least to the ninth century. Pioneering work in * computer retrograde analysis was done in the 1980s by Ken Thompson, the same of UNIX fame, and * S.J. Edwards, but the most popular tablebases today are those generated by a program written by * E.V. Nalimov. Suffice it to say that while Nalimov's program has completely solved all chess * endgames with six or fewer pieces remaining, and while Nalimov tablebases are widely available on * the Internet, the Nalimov approach of solving an endgame completely results in very slow run * times and exceptionally large tablebases. The K+P+P vs K+P endgame, for example, due to the * possibility of all pawns queening, requires the K+Q+Q vs K+Q endgame to be solved before it can * be calculated. * * Hoffman takes a somewhat different approach, one pioneered by the Eiko Bleicher's Freezer, now a * commercial program. When faced with something like K+P+P vs K+P, rather than calculate all * possible resulting positions, it may ignore the possibility of more than two pawns queening at * the same time, thus computing nothing more complex than K+Q+P vs K+Q. While incomplete, such a * tablebase is nevertheless useful. For the player with two pawns, if the tablebase finds a * winning line subject to the queening restrictions, then that line is still playable for a win, * even though a faster winning line may exist. From the opposing point of view, if the tablebase * treats any position where the third pawn queens as a forced win, then the player can be confident * that any drawing line can not be improved upon by the superior side. From a computational * perspective, we have reduced the complexity requirements to a point where the calculation can be * performed in a reasonable amount of time. While still too slow for over-the-board use, we now * have a useful tool for the analysis of more complex endgames, useful for either static analysis, * or for the slow time controls of correspondence games. * * Hoffman improves upon Freezer with a more sophisticated method of chaining one endgame analysis * into another, allowing more realistic modeling of queening combinations and exchanges. For * example, in a bishop vs knight endgame (with pawns), if we can (if we wish) analyze first the * king and pawn endgame resulting after a trade of the minors, then use this information to analyze * a similar set of king vs knight and king vs bishop endgames, and finally combine all this * information together to analyze the bishop vs knight endgame. While the current version of * Freezer can only regard the capture of the knight or bishop as a forced win for one side or the * other, Hoffman can look through the exchange to determine the result more accurately. * * Hoffman thus attempts to combine the best of Nalimov and Freezer. Unlike Freezer, the program is * powerful enough to solve any endgame completely (given enough computing resources), exactly * reproducing any Nalimov tablebase. Unlike Nalimov, the program is capable of pruning pawn moves, * queening combinations, movement options and exchanges, giving it Freezer's ability to solve * complex endgames in a reasonable amount of time. The exact tradeoff between the two extremes is * made using a XML-based configuration that can seem daunting at first, but ultimately offers the * user the ability to extensively tailor the program's operation. Combined with a human being's * common sense and chess judgement, it is my hope that this flexibility with ultimately make the * program more useful for endgame retrograde analysis than either Nalimov or Freezer. * * For those not up on Americana, the program is named after Trevor Hoffman, an All Star baseball * pitcher who specializes in "closing" games. It was written specifically for The World vs. Arno * Nickel game. * * * Usage: hoffman -g -o (generate mode) * hoffman -v ... (verification mode) * hoffman -p ... (probe mode) */ #include #include #include #include /* for write(), lseek(), gethostname() */ #include /* for putting timestamps on the output tablebases */ #include /* for O_RDONLY */ #include /* for stat'ing the length of the tablebase file */ #include /* for mmap */ #include /* for gethostbyname() */ /* The GNU readline library, used for prompting the user during the probe code. By defining * READLINE_LIBRARY, the library is set up to read include files from a directory specified on the * compiler's command line, rather than a system-wide /usr/include/readline. I use it this way * simply because I don't have the readline include files installed system-wide on my machine. */ #define READLINE_LIBRARY #include "readline.h" #include "history.h" /* The GNOME XML library. To use it, I need "-I /usr/include/libxml2" (compiler) and "-lxml2" * (linker). */ #include #include #include #include /* According the GCC documentation, "long long" ints are supported by the C99 standard as well as * the GCC compiler. In any event, since chess boards have 64 squares, being able to use 64 bit * integers makes a bunch of stuff a lot easier. Might have to be careful with this if porting. */ typedef unsigned long long int int64; typedef unsigned int int32; typedef short boolean; #define ROW(square) ((square) / 8) #define COL(square) ((square) % 8) inline int square(int row, int col) { return (col + row*8); } /***** GLOBAL CONSTANTS *****/ /* Maximum number of mobile pieces; used to simplify various arrays * * "8" may seem absurd, but it's probably about right. "4" is easily doable in memory. "5" * requires sweeping passes across a file on disk. "6" and "7" are worse than "5", but doable with * severe restrictions on the movements of the pieces. So "8" is enough. */ #define MAX_MOBILES 16 /* Why 100? Well, I just think it's less likely to introduce bugs into this code if I count * half-moves instead of moves. So it takes 100 half-moves to stalemate. */ #define STALEMATE_COUNT 100 /* Number of possibilities for pawn promotions. "2" means queen and knight, but that can cause some * problems, as I've learned the hard (and embarrassing) way. */ #define PROMOTION_POSSIBILITIES 3 /* seven possible pieces: KQRBNP; 64 possible squares, up to 8 directions per piece, up to 7 * movements in one direction */ #define NUM_PIECES 6 #define NUM_SQUARES 64 #define NUM_DIR 8 #define NUM_MOVEMENTS 7 /***** DATA STRUCTURES *****/ /* position - the data structures that represents a board position * * There are two kinds of positions: local and global. Locals are faster but are tied to a specific * tablebase. Globals are more general and are used to translate between different tablebases. * * Both types use a 64-bit board_vector with one bit for each board position, in addition to a flag * to indicate which side is to move and the en passant capture square (or -1 if no en passant * capture is possible). We use board_vector to easily check if possible moves are legal by looking * for pieces that block our moving piece. This is done during futurebase propagation (mobile * capture only), during intratable propagation, and during initialization. It could be used to * check if en passant positions are legal (are the two squares behind the pawn blocked or not), but * that is problematic now because the board_vector isn't correct at the point where we need to * make that check. * * Local positions use numbers (0-63) indicating the positions of the mobile pieces, and also have a * quick way to check captures using a black_vector and a white_vector. You have to look into the * tablebase structure to figure out what piece corresponds to each number. "black_vector" and * "white_vector" are only used during tablebase initialization and in the probe code. It's * starting to look like these vectors would be better arranged as PTM_vector and PNTM_vector * (player to move and player not to move). * * It makes sense to include these vectors in the position structures because it's easiest to * compute them in the routines that convert indices to positions, but if you alter the position, * then they get out of sync, and its tempting to just leave them that way because you rarely need * them to be right at that point. This really came back to haunt me when implementing en passant. * * Global positions contain an 8x8 unsigned char array with ASCII characters representing each * piece. * * Sometimes I allow the board vectors, black_vector and white_vector to get out of sync with the * position (for speed). This can be a problem, so it has to be done really carefully. * * We don't worry about moving a piece that's pinned on our king, for example. The resulting * position will already have been flagged illegal in the table. * */ /* Where are the kings located in the mobile piece list? */ #define WHITE_KING 0 #define BLACK_KING 1 typedef struct { struct tablebase *tb; int64 board_vector; int64 white_vector; int64 black_vector; short side_to_move; short en_passant_square; short piece_position[MAX_MOBILES]; } local_position_t; /* This is a global position, that doesn't depend on a particular tablebase. It's slower to * manipulate, but is suitable for translating positions between tablebases. Each char in the array * is either 0 or ' ' for an empty square, and one of the FEN characters for a chess piece. */ typedef struct { unsigned char board[64]; int64 board_vector; short side_to_move; short en_passant_square; } global_position_t; /* bitvector gets initialized in init_movements() */ int64 bitvector[64]; int64 allones_bitvector = 0xffffffffffffffffLL; /* pawn can't be on the first or last eight squares of the board */ #define LEGAL_PAWN_BITVECTOR 0x00ffffffffffff00LL /* I'm not sure which one of these will be faster... */ /* #define BITVECTOR(square) bitvector[square] */ #define BITVECTOR(square) (1ULL << (square)) /* tablebase - the data structure used to hold tablebases * * WHITE and BLACK are also used for the side_to_move variable in the position type above */ #define KING 0 #define QUEEN 1 #define ROOK 2 #define BISHOP 3 #define KNIGHT 4 #define PAWN 5 char * piece_name[NUM_PIECES+1] = {"KING", "QUEEN", "ROOK", "BISHOP", "KNIGHT", "PAWN", NULL}; char piece_char[NUM_PIECES+1] = {'K', 'Q', 'R', 'B', 'N', 'P', 0}; char * colors[3] = {"WHITE", "BLACK", NULL}; unsigned char global_pieces[2][NUM_PIECES] = {{'K', 'Q', 'R', 'B', 'N', 'P'}, {'k', 'q', 'r', 'b', 'n', 'p'}}; #define WHITE 0 #define BLACK 1 /**** TABLEBASE STRUCTURE AND OPERATIONS ****/ /* The 'xml' in the tablebase is authoritative; much of the other info is extracted from it * for efficiency. * * movecnt - 0 if this entry is ready to propagate; 255 if it has been propagated * * While movecnt is > 0, it is the number of moves FORWARD from this position that haven't been * analyzed yet. The other three numbers are the number of moves out of this position for which * white wins, for which black wins, for which there is some kind of draw. * * If this position is WHITE TO MOVE, then we don't have to count outcomes which are WHITE WINS, * since that makes this position WHITE WINS. We only have to count outcomes which are BLACK WINS, * in order to conclude that, if all possible white moves result in BLACK WINS, then this position * is BLACK WINS. If at least one move leads to a draw (other moves lead to BLACK WINS), then the * position is WHITE DRAWS. If all moves lead to draws, then the position is also BLACK DRAWS. * Since we assume that white will make the best move, then we can just say that this position DRAWS * unless either there is at least one move which leads to WHITE WINS, or if all moves lead to BLACK * WINS. * * So, all we really need is movecnt. If we backtrace from a single WHITE WINS, then this position * becomes WHITE WINS. If we backtrace from BLACK WINS, we decrement movecnt. If movecnt reaches * zero, then the position becomes BLACK WINS. When we're all done backtracing possible wins, * anything left with a non-zero movecnt is a DRAW. * * We also need a mate-in count and a stalemate (conversion) count. * * To make this work for either white or black positions, let's adopt the notation PTM (Player to * move) and PNTM (Player not to move) * * movecnt * 255 - ILLEGAL POSITION * 254 - PTM WINS; propagation done * 253 - PNTM WINS; propagation done * 252 - PTM WINS; propagation needed * 0 - PNTM WINS; propagation needed * * 1 through 251 - movecnt (during run), or DRAW (after run is finished) * */ #define ILLEGAL_POSITION 255 #define PTM_WINS_PROPAGATION_DONE 254 #define PNTM_WINS_PROPAGATION_DONE 253 #define PTM_WINS_PROPAGATION_NEEDED 252 #define PNTM_WINS_PROPAGATION_NEEDED 0 #define MAX_MOVECNT 251 struct fourbyte_entry { unsigned char movecnt; unsigned char mate_in_cnt; unsigned char stalemate_cnt; unsigned char futuremove_cnt; }; #define RESTRICTION_NONE 0 #define RESTRICTION_DISCARD 1 #define RESTRICTION_CONCEDE 2 char * restriction_types[4] = {"NONE", "DISCARD", "CONCEDE", NULL}; typedef struct tablebase { int32 max_index; enum {NAIVE_INDEX=1, SIMPLE_INDEX} index_type; int total_legal_piece_positions[MAX_MOBILES]; int simple_piece_positions[MAX_MOBILES][64]; int simple_piece_indices[MAX_MOBILES][64]; xmlDocPtr xml; void *fileptr; size_t length; int num_mobiles; int move_restrictions[2]; /* one for each color */ short piece_type[MAX_MOBILES]; short piece_color[MAX_MOBILES]; int64 piece_legal_squares[MAX_MOBILES]; struct fourbyte_entry *entries; } tablebase_t; boolean place_piece_in_local_position(tablebase_t *tb, local_position_t *pos, int square, int color, int type); int find_name_in_array(char * name, char * array[]) { int i=0; while (*array != NULL) { if (!strcasecmp(name, *array)) return i; array ++; i ++; } return -1; } /***** INDICES *****/ int32 local_position_to_naive_index(tablebase_t *tb, local_position_t *pos) { /* This function, given a local board position, returns an index into the tablebase. * * Initially, this function can be very simple (multiplying numbers together), but to build * smaller tables it can be more precise. * * For example, two kings can never be next to each other. Pieces can never be on top of each * other, or on top of static pieces. The side to move can not be in check. * * It also updates the position's board_vector (which doesn't have to be valid going in), * but not the white_vector or black_vector. It does this to check for illegal en passant * positions. * * Returns either an index into the table, or -1 (probably) if the position is illegal. * * What exactly is an illegal position? Well, for starters, one that index_to_local_position() * reports as illegal, because that's the function that initialize_tablebase() uses to figure * which positions are flagged illegal, as well as which positions to consider during back prop, * and the program screams if you try to back prop into an illegal position. * * This function is currently used only during back propagation to generate indices, and during * probing to convert "next move" positions into indices. * * When we back propagate a local position from either a futurebase or intratable, we generate * en passant positions simply by running through the pawns on the fourth and fifth ranks. If * we don't look then to see if there was a piece behind the "en passant" pawn (that would have * prevented it from moving), and we currently don't (correctly) because the board vectors * aren't set right, then we have to detect that and return -1 here. Otherwise, we would try to * back propagate to a position that had been labeled illegal during initialization by * index_to_local_position(). * * This function is also used during probing to see if possible next positions are legal. */ /* Keep it simple, for now */ int shift_count = 1; int32 index = pos->side_to_move; /* WHITE is 0; BLACK is 1 */ int piece; pos->board_vector = 0; for (piece = 0; piece < tb->num_mobiles; piece ++) { if ((pos->piece_position[piece] < 0) || (pos->piece_position[piece] > 63) || !(tb->piece_legal_squares[piece] & BITVECTOR(pos->piece_position[piece]))) { fprintf(stderr, "Bad mobile piece position in local_position_to_index()\n"); /* BREAKPOINT */ return -1; } /* The way we encode en passant capturable pawns is use the column number of the * pawn. Since there can never be a pawn (of either color) on the first rank, * this is completely legit. */ if ((tb->piece_type[piece] == PAWN) && (pos->en_passant_square != -1) && (((tb->piece_color[piece] == WHITE) && (pos->en_passant_square + 8 == pos->piece_position[piece])) || ((tb->piece_color[piece] == BLACK) && (pos->en_passant_square - 8 == pos->piece_position[piece])))) { index |= COL(pos->en_passant_square) << shift_count; } else { index |= pos->piece_position[piece] << shift_count; } if (pos->board_vector & BITVECTOR(pos->piece_position[piece])) return -1; pos->board_vector |= BITVECTOR(pos->piece_position[piece]); shift_count += 6; /* because 2^6=64 */ } /* Check board_vector to make sure an en passant position is legal */ if (pos->en_passant_square != -1) { if (pos->board_vector & BITVECTOR(pos->en_passant_square)) return -1; if (pos->side_to_move == WHITE) { if (pos->board_vector & BITVECTOR(pos->en_passant_square + 8)) return -1; } else { if (pos->board_vector & BITVECTOR(pos->en_passant_square - 8)) return -1; } } /* Possibly a quicker check for position legality that all that en passant stuff */ if (tb->entries[index].movecnt == ILLEGAL_POSITION) return -1; return index; } boolean naive_index_to_local_position(tablebase_t *tb, int32 index, local_position_t *p) { /* Given an index, fill in a board position. Obviously has to correspond to local_position_to_index() * and it's a big bug if it doesn't. The boolean that gets returned is TRUE if the operation * succeeded (the index is at least minimally valid) and FALSE if the index is so blatantly * illegal (two pieces on the same square) that we can't even fill in the position. * * Used by index_to_side_to_move() (which is currently only use to check move restrictions) to * determine position legality. * * Used in propagate_move_within_table() to get from an index to a position, and its return * value is ignored there, because a position that needs_propagation() couldn't have been marked * illegal during initialization. * * Used in initialize_tablebase() to determine which positions are legal. * * Use to prepare a move list during probe. * * So how about a static 64-bit vector with bits set for the frozen pieces but not the mobiles? * Everytime we call index_to_local_position, copy from the static vector into the position * structure. Then we compute the positions of the mobile pieces and plug their bits into the * structure's vector at the right places. */ int piece; bzero(p, sizeof(local_position_t)); p->en_passant_square = -1; p->side_to_move = index & 1; index >>= 1; for (piece = 0; piece < tb->num_mobiles; piece++) { int square = index & 63; /* En passant */ if ((tb->piece_type[piece] == PAWN) && (square < 8)) { if (p->en_passant_square != -1) return 0; /* can't have two en passant pawns */ if (tb->piece_color[piece] == WHITE) { if (p->side_to_move != BLACK) return 0; /* en passant pawn has to be capturable */ p->en_passant_square = square + 2*8; square += 3*8; } else { if (p->side_to_move != WHITE) return 0; /* en passant pawn has to be capturable */ p->en_passant_square = square + 5*8; square += 4*8; } } /* The first place we handle restricted pieces, and one of most important, too, because this * function is used during initialization to decide which positions are legal and which are * not. */ if (!(tb->piece_legal_squares[piece] & BITVECTOR(square))) { return 0; } p->piece_position[piece] = square; if (p->board_vector & BITVECTOR(square)) { return 0; } p->board_vector |= BITVECTOR(square); if (tb->piece_color[piece] == WHITE) { p->white_vector |= BITVECTOR(square); } else { p->black_vector |= BITVECTOR(square); } index >>= 6; } /* If there is an en passant capturable pawn in this position, then there can't be anything * on the capture square or on the square right behind it (where the pawn just came from), * or its an illegal position. */ if (p->en_passant_square != -1) { if (p->board_vector & BITVECTOR(p->en_passant_square)) return 0; if (p->side_to_move == WHITE) { if (p->board_vector & BITVECTOR(p->en_passant_square + 8)) return 0; } else { if (p->board_vector & BITVECTOR(p->en_passant_square - 8)) return 0; } } return 1; } int32 local_position_to_simple_index(tablebase_t *tb, local_position_t *pos) { int32 index; int piece; index = 0; pos->board_vector = 0; for (piece = 0; piece < tb->num_mobiles; piece ++) { index *= tb->total_legal_piece_positions[piece]; if ((pos->piece_position[piece] < 0) || (pos->piece_position[piece] > 63) || !(tb->piece_legal_squares[piece] & BITVECTOR(pos->piece_position[piece]))) { fprintf(stderr, "Bad mobile piece position in local_position_to_index()\n"); /* BREAKPOINT */ return -1; } /* The way we encode en passant capturable pawns is use the column number of the * pawn. Since there can never be a pawn (of either color) on the first rank, * this is completely legit. */ if ((tb->piece_type[piece] == PAWN) && (pos->en_passant_square != -1) && (((tb->piece_color[piece] == WHITE) && (pos->en_passant_square + 8 == pos->piece_position[piece])) || ((tb->piece_color[piece] == BLACK) && (pos->en_passant_square - 8 == pos->piece_position[piece])))) { index += tb->simple_piece_indices[piece][COL(pos->en_passant_square)]; } else { index += tb->simple_piece_indices[piece][pos->piece_position[piece]]; } if (pos->board_vector & BITVECTOR(pos->piece_position[piece])) return -1; pos->board_vector |= BITVECTOR(pos->piece_position[piece]); } /* Check board_vector to make sure an en passant position is legal */ if (pos->en_passant_square != -1) { if (pos->board_vector & BITVECTOR(pos->en_passant_square)) return -1; if (pos->side_to_move == WHITE) { if (pos->board_vector & BITVECTOR(pos->en_passant_square + 8)) return -1; } else { if (pos->board_vector & BITVECTOR(pos->en_passant_square - 8)) return -1; } } /* We've still got code that assumes flipping the index's LSB flip side-to-move */ index *= 2; index += pos->side_to_move; /* WHITE is 0; BLACK is 1 */ /* Possibly a quicker check for position legality that all that en passant stuff */ if (tb->entries[index].movecnt == ILLEGAL_POSITION) return -1; return index; } boolean simple_index_to_local_position(tablebase_t *tb, int32 index, local_position_t *p) { int piece; bzero(p, sizeof(local_position_t)); p->en_passant_square = -1; p->side_to_move = index % 2; index /= 2; for (piece = tb->num_mobiles - 1; piece >= 0; piece --) { int square = tb->simple_piece_positions[piece][index % tb->total_legal_piece_positions[piece]]; index /= tb->total_legal_piece_positions[piece]; /* En passant */ if ((tb->piece_type[piece] == PAWN) && (square < 8)) { if (p->en_passant_square != -1) return 0; /* can't have two en passant pawns */ if (tb->piece_color[piece] == WHITE) { if (p->side_to_move != BLACK) return 0; /* en passant pawn has to be capturable */ p->en_passant_square = square + 2*8; square += 3*8; } else { if (p->side_to_move != WHITE) return 0; /* en passant pawn has to be capturable */ p->en_passant_square = square + 5*8; square += 4*8; } } /* This should never happen. */ if (!(tb->piece_legal_squares[piece] & BITVECTOR(square))) { fprintf(stderr, "Illegal piece position in simple_index_to_local_position!\n"); return 0; } p->piece_position[piece] = square; if (p->board_vector & BITVECTOR(square)) { return 0; } p->board_vector |= BITVECTOR(square); if (tb->piece_color[piece] == WHITE) { p->white_vector |= BITVECTOR(square); } else { p->black_vector |= BITVECTOR(square); } } if (index != 0) { fprintf (stderr, "index != 0 at end of simple_index_to_local_position!\n"); /* BREAKPOINT */ return 0; } /* If there is an en passant capturable pawn in this position, then there can't be anything * on the capture square or on the square right behind it (where the pawn just came from), * or its an illegal position. */ if (p->en_passant_square != -1) { if (p->board_vector & BITVECTOR(p->en_passant_square)) return 0; if (p->side_to_move == WHITE) { if (p->board_vector & BITVECTOR(p->en_passant_square + 8)) return 0; } else { if (p->board_vector & BITVECTOR(p->en_passant_square - 8)) return 0; } } return 1; } int32 local_position_to_index(tablebase_t *tb, local_position_t *pos) { switch (tb->index_type) { case NAIVE_INDEX: return local_position_to_naive_index(tb, pos); case SIMPLE_INDEX: return local_position_to_simple_index(tb, pos); default: fprintf(stderr, "Unknown index type in local_position_to_index()\n"); /* BREAKPOINT */ return -1; } } boolean index_to_local_position(tablebase_t *tb, int32 index, local_position_t *p) { switch (tb->index_type) { case NAIVE_INDEX: return naive_index_to_local_position(tb, index, p); case SIMPLE_INDEX: return simple_index_to_local_position(tb, index, p); default: fprintf(stderr, "Unknown index type in index_to_local_position()\n"); /* BREAKPOINT */ return 0; } } /* Used just to double check the code above. */ void check_1000_positions(tablebase_t *tb) { local_position_t position1; local_position_t position2; int32 index; int positions; int piece; for (positions=0; positions < 1000; positions ++) { bzero(&position1, sizeof(position1)); position1.side_to_move = rand() % 2; position1.en_passant_square = -1; for (piece = 0; piece < tb->num_mobiles; piece ++) { do { position1.piece_position[piece] = rand() % 64; } while (! (BITVECTOR(position1.piece_position[piece]) & tb->piece_legal_squares[piece])); } index = local_position_to_index(tb, &position1); if (index != -1) { /* white_vector/black_vector were never set in position1, so don't check them now */ if (!index_to_local_position(tb, index, &position2) || (position2.white_vector = 0, position2.black_vector = 0, memcmp(&position1, &position2, sizeof(position1)))) { fprintf(stderr, "Mismatch in check_1000_positions()\n"); /* BREAKPOINT */ } } } } /***** XML TABLEBASE INTERACTION *****/ /* Parses XML, creates a tablebase structure corresponding to it, and returns it. * * Eventually, I want to provide a DTD and validate the XML input, so there's very little error * checking here. The idea is that the validation will ultimately provide the error check. */ tablebase_t * parse_XML_into_tablebase(xmlDocPtr doc) { tablebase_t *tb; xmlXPathContextPtr context; xmlXPathObjectPtr result; xmlNodePtr tablebase; xmlChar * index; tb = malloc(sizeof(tablebase_t)); if (tb == NULL) { fprintf(stderr, "Can't malloc tablebase\n"); return NULL; } bzero(tb, sizeof(tablebase_t)); tb->xml = doc; /* Fetch tablebase from XML */ context = xmlXPathNewContext(tb->xml); result = xmlXPathEvalExpression((const xmlChar *) "//tablebase", context); tablebase = result->nodesetval->nodeTab[0]; xmlXPathFreeObject(result); xmlXPathFreeContext(context); /* Fetch the mobile pieces from the XML */ context = xmlXPathNewContext(doc); result = xmlXPathEvalExpression((const xmlChar *) "//mobile", context); if (xmlXPathNodeSetIsEmpty(result->nodesetval)) { fprintf(stderr, "No mobile pieces!\n"); return NULL; } else if (result->nodesetval->nodeNr < 2) { fprintf(stderr, "Too few mobile pieces!\n"); return NULL; } else if (result->nodesetval->nodeNr > MAX_MOBILES) { fprintf(stderr, "Too many mobile pieces!\n"); return NULL; } else { int i; tb->num_mobiles = result->nodesetval->nodeNr; for (i=0; i < result->nodesetval->nodeNr; i++) { xmlChar * color; xmlChar * type; xmlChar * location; color = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "color"); type = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "type"); location = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "location"); tb->piece_color[i] = find_name_in_array((char *) color, colors); tb->piece_type[i] = find_name_in_array((char *) type, piece_name); if (location == NULL) { if (tb->piece_type[i] == PAWN) { tb->piece_legal_squares[i] = LEGAL_PAWN_BITVECTOR; } else { tb->piece_legal_squares[i] = allones_bitvector; } } else if ((location[0] >= 'a') && (location[0] <= 'h') && (location[1] >= '1') && (location[1] <= '8') && (location[2] == '\0')) { tb->piece_legal_squares[i] = BITVECTOR(square(location[1] - '1', location[0] - 'a')); } else { fprintf(stderr, "Illegal location (%s) in mobile\n", location); return NULL; } if ((tb->piece_color[i] == -1) || (tb->piece_type[i] == -1)) { fprintf(stderr, "Illegal color (%s) or type (%s) in mobile\n", color, type); xmlFree(color); } } } if ((tb->piece_color[WHITE_KING] != WHITE) || (tb->piece_type[WHITE_KING] != KING) || (tb->piece_color[BLACK_KING] != BLACK) || (tb->piece_type[BLACK_KING] != KING)) { fprintf(stderr, "Kings aren't where they need to be in mobiles!\n"); return NULL; } xmlXPathFreeObject(result); xmlXPathFreeContext(context); /* Fetch the index type and compute tb->max_index */ index = xmlGetProp(tablebase, (const xmlChar *) "index"); if ((index == NULL) || !strcasecmp((char *) index, "naive")) { if (index == NULL) { xmlNewProp(tablebase, (const xmlChar *) "index", (const xmlChar *) "naive"); fprintf(stderr, "Index type not expressly specified; assuming NAIVE\n"); } tb->index_type = NAIVE_INDEX; /* The "2" is because side-to-play is part of the position; "6" for the 2^6 squares on the board */ tb->max_index = (2<<(6*tb->num_mobiles)) - 1; } else if (!strcasecmp((char *) index, "simple")) { int piece, square; /* The "2" is because side-to-play is part of the position */ tb->index_type = SIMPLE_INDEX; tb->max_index = 2; for (piece = 0; piece < tb->num_mobiles; piece ++) { for (square = 0; square < 64; square ++) { if (! (tb->piece_legal_squares[piece] & BITVECTOR(square))) continue; tb->simple_piece_positions[piece][tb->total_legal_piece_positions[piece]] = square; tb->simple_piece_indices[piece][square] = tb->total_legal_piece_positions[piece]; tb->total_legal_piece_positions[piece] ++; /* if the pawn is en-passant capturable, add an index for that */ if ((tb->piece_type[piece] == PAWN) && (((tb->piece_color[piece] == WHITE) && (ROW(square) == 3)) || ((tb->piece_color[piece] == BLACK) && (ROW(square) == 4)))) { tb->simple_piece_positions[piece][tb->total_legal_piece_positions[piece]] = COL(square); tb->simple_piece_indices[piece][COL(square)] = tb->total_legal_piece_positions[piece]; tb->total_legal_piece_positions[piece] ++; } } tb->max_index *= tb->total_legal_piece_positions[piece]; } tb->max_index --; } else { fprintf(stderr, "Unknown index type (%s) in XML\n", index); return NULL; } /* Fetch the move restrictions */ context = xmlXPathNewContext(doc); result = xmlXPathEvalExpression((const xmlChar *) "//move-restriction", context); if (! xmlXPathNodeSetIsEmpty(result->nodesetval)) { int i; for (i=0; i < result->nodesetval->nodeNr; i++) { xmlChar * color_str; xmlChar * type_str; int color; int type; color_str = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "color"); type_str = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "type"); color = find_name_in_array((char *) color_str, colors); type = find_name_in_array((char *) type_str, restriction_types); if ((color == -1) || (type == -1)) { fprintf(stderr, "Illegal move restriction\n"); return NULL; } else { if ((tb->move_restrictions[color] > 0) && (tb->move_restrictions[color] != type)) { fprintf(stderr, "Incompatible move restrictions\n"); return NULL; } else { tb->move_restrictions[color] = type; } } } } xmlXPathFreeContext(context); return tb; } /* Parses an XML control file. This function allocates an entries array, as well. */ tablebase_t * parse_XML_control_file(char *filename) { xmlParserCtxtPtr ctxt; /* the parser context */ xmlDocPtr doc; tablebase_t *tb; /* create a parser context */ ctxt = xmlNewParserCtxt(); if (ctxt == NULL) { fprintf(stderr, "Failed to allocate parser context\n"); return NULL; } /* parse the file, activating the DTD validation option */ doc = xmlCtxtReadFile(ctxt, filename, NULL, XML_PARSE_DTDVALID); /* check if parsing suceeded */ if (doc == NULL) { fprintf(stderr, "'%s' failed XML read\n", filename); return NULL; } else { /* check if validation suceeded */ if (ctxt->valid == 0) { fprintf(stderr, "WARNING: '%s' failed XML validatation\n", filename); } } /* free up the parser context */ xmlFreeParserCtxt(ctxt); #if 0 doc = xmlReadFile(filename, NULL, 0); if (doc == NULL) { fprintf(stderr, "'%s' failed XML read\n", filename); return NULL; } #endif tb = parse_XML_into_tablebase(doc); if (tb != NULL) { tb->entries = (struct fourbyte_entry *) calloc(tb->max_index + 1, sizeof(struct fourbyte_entry)); if (tb->entries == NULL) { fprintf(stderr, "Can't malloc tablebase entries\n"); } } /* We don't free the XML doc because the tablebase struct contains a pointer to it */ return tb; } /* Loads a futurebase, by mmap'ing it into memory, parsing the XML header, and returning a pointer * to the resulting tablebase structure after setting 'entries' to point into the mmap'ed data. */ tablebase_t * load_futurebase_from_file(char *filename) { int fd; struct stat filestat; char *fileptr; int xml_size; xmlDocPtr doc; xmlNodePtr root_element; xmlChar * offsetstr; long offset; tablebase_t *tb; fd = open(filename, O_RDONLY); if (fd == -1) { fprintf(stderr, "Can not open futurebase '%s'\n", filename); return NULL; } fstat(fd, &filestat); fileptr = mmap(0, filestat.st_size, PROT_READ, MAP_SHARED, fd, 0); close(fd); for (xml_size = 0; fileptr[xml_size] != '\0'; xml_size ++) ; doc = xmlReadMemory(fileptr, xml_size, NULL, NULL, 0); tb = parse_XML_into_tablebase(doc); if (tb != NULL) { tb->fileptr = fileptr; tb->length = filestat.st_size; root_element = xmlDocGetRootElement(doc); if (xmlStrcmp(root_element->name, (const xmlChar *) "tablebase")) { fprintf(stderr, "'%s' failed XML parse\n", filename); return NULL; } offsetstr = xmlGetProp(root_element, (const xmlChar *) "offset"); offset = strtol((const char *) offsetstr, NULL, 0); tb->entries = (struct fourbyte_entry *) (fileptr + offset); } return tb; } void unload_futurebase(tablebase_t *tb) { if (tb->fileptr != NULL) munmap(tb->fileptr, tb->length); tb->fileptr = NULL; } /* Given a tablebase, change its XML structure to reflect the fact that the tablebase has now * actually been built. */ xmlDocPtr finalize_XML_header(tablebase_t *tb) { xmlXPathContextPtr context; xmlXPathObjectPtr result; xmlNodePtr tablebase, node; time_t creation_time; char hostname[256]; struct hostent *he; context = xmlXPathNewContext(tb->xml); result = xmlXPathEvalExpression((const xmlChar *) "//tablebase", context); tablebase = result->nodesetval->nodeTab[0]; xmlXPathFreeObject(result); xmlXPathFreeContext(context); xmlNewProp(tablebase, (const xmlChar *) "offset", (const xmlChar *) "0x1000"); xmlNewProp(tablebase, (const xmlChar *) "format", (const xmlChar *) "fourbyte"); /* 'index' should now either be specified in input, or set to its default value earlier */ /* xmlNewProp(tablebase, (const xmlChar *) "index", (const xmlChar *) "naive"); */ node = xmlNewChild(tablebase, NULL, (const xmlChar *) "generating-program", NULL); xmlNewProp(node, (const xmlChar *) "name", (const xmlChar *) "Hoffman"); xmlNewProp(node, (const xmlChar *) "version", (const xmlChar *) "$Revision: 1.108 $"); node = xmlNewChild(tablebase, NULL, (const xmlChar *) "generating-time", NULL); time(&creation_time); xmlNewProp(node, (const xmlChar *) "time", (const xmlChar *) ctime(&creation_time)); gethostname(hostname, sizeof(hostname)); he = gethostbyname(hostname); node = xmlNewChild(tablebase, NULL, (const xmlChar *) "generating-host", NULL); xmlNewProp(node, (const xmlChar *) "fqdn", (const xmlChar *) he->h_name); return tb->xml; } /* do_write() is like the system call write(), but keeps repeating until the write is complete */ int do_write(int fd, void *ptr, int length) { while (length > 0) { int writ = write(fd, ptr, length); if (writ == -1) return -1; ptr += writ; length -= writ; } return 0; } void write_tablebase_to_file(tablebase_t *tb, char *filename) { xmlDocPtr doc; xmlSaveCtxtPtr savectx; int fd; fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0666); if (fd == -1) { fprintf(stderr, "Can't open '%s' for writing tablebase\n", filename); return; } doc = finalize_XML_header(tb); savectx = xmlSaveToFd(fd, NULL, 0); xmlSaveDoc(savectx, doc); xmlSaveClose(savectx); if (lseek(fd, 0x1000, SEEK_SET) != 0x1000) { fprintf(stderr, "seek failed\n"); } do_write(fd, tb->entries, sizeof(struct fourbyte_entry) << (1 + 6*tb->num_mobiles)); close(fd); } /***** INDICES AND POSITIONS *****/ /* This function could be made a bit faster, but this simpler version is hopefully safer. */ int index_to_side_to_move(tablebase_t *tb, int32 index) { local_position_t position; if (! index_to_local_position(tb, index, &position)) return -1; else return position.side_to_move; } inline void flip_side_to_move_local(local_position_t *position) { if (position->side_to_move == WHITE) position->side_to_move = BLACK; else position->side_to_move = WHITE; } inline void flip_side_to_move_global(global_position_t *position) { if (position->side_to_move == WHITE) position->side_to_move = BLACK; else position->side_to_move = WHITE; } /* invert_colors_of_global_position - just what its name implies * * We used to use this when propagating from a futurebase, but now it's only use is in the probe * code. It translates a position for a tablebase built for the opposite colors, say a K+R vs K * endgame that we now want to probe where the rook is black, not white. If there are pawns in the * game, this function has to reflect the board around a horizontal centerline. */ void invert_colors_of_global_position(global_position_t *global) { int squareA; global->board_vector = 0; for (squareA=0; squareA < NUM_SQUARES/2; squareA++) { unsigned char pieceA; unsigned char pieceB; int squareB = square(7-ROW(squareA),COL(squareA)); pieceA = global->board[squareA]; pieceB = global->board[squareB]; if ((pieceA >= 'A') && (pieceA <= 'Z')) { pieceA += 'a' - 'A'; } else if ((pieceA >= 'a') && (pieceA <= 'z')) { pieceA += 'A' - 'a'; } if ((pieceB >= 'A') && (pieceB <= 'Z')) { pieceB += 'a' - 'A'; } else if ((pieceB >= 'a') && (pieceB <= 'z')) { pieceB += 'A' - 'a'; } global->board[squareA] = pieceB; global->board[squareB] = pieceA; if (pieceB >= 'A') global->board_vector |= BITVECTOR(squareA); if (pieceA >= 'A') global->board_vector |= BITVECTOR(squareB); } if (global->side_to_move == WHITE) { global->side_to_move = BLACK; if (global->en_passant_square != -1) global->en_passant_square -= 3*8; } else { global->side_to_move = WHITE; if (global->en_passant_square != -1) global->en_passant_square += 3*8; } } /* translate_foreign_index_to_local_position() - one of our key, key functions, used extensively * during futurebase back propagation. It takes an index into a foreign tablebase and converts it * to a position in the local tablebase (the tablebase we're processing). Of course, the pieces * might not match up between the two tablebases, but there are only a finite number of possible * differences: * * 1. There can be an "extra" piece in the foreign tablebase that doesn't appear in the * local tablebase. * * 2. There can be up to two "missing" pieces in the local tablebase that don't appear in * the foreign tablebase. * * 3. There can be one piece (the "restricted" piece) that matches up, but is on a square flagged * illegal for it in the local tablebase. * * If there are additional differences not covered in this list (more than one extra piece, for * example), or if the index isn't legal in the foreign tablebase, the function returns -1. * Otherwise, the return value is a 32 bit integer split into four eight bit fields: * * bits 0-7: local tb piece number of missing piece #1 * bits 8-15: local tb piece number of restricted piece * bits 16-23: square on chessboard of extra piece * bits 24-31: local tb piece number of missing piece #2 * * If any of the fields are unused (because there is no corresponding piece), it's value is 0x80. * Also, if there are two missing pieces and only one of them is a pawn, the pawn will always be * returned as missing piece #1. * * The function does not depend on the indexing scheme used by the foreign tablebase. Instead, it * uses index_to_local_position() on the foreign tablebase. * * The only thing I don't like about this function right now is that it returns -1 if there is more * than one restricted piece, and we certainly could have liberal tablebases with lots of restricted * pieces that we want to back-prop from. */ #define NONE 0x80 int translate_foreign_index_to_local_position(tablebase_t *tb1, int32 index1, tablebase_t *tb2, local_position_t *local, int invert_colors) { local_position_t foreign_position; int foreign_piece; int piece; int restricted_piece = NONE; int missing_piece1 = NONE; int missing_piece2 = NONE; int extra_piece = NONE; short pieces_processed_bitvector = 0; if (! index_to_local_position(tb1, index1, &foreign_position)) return -1; bzero(local, sizeof(local_position_t)); for (piece = 0; piece < tb2->num_mobiles; piece ++) local->piece_position[piece] = -1; local->en_passant_square = foreign_position.en_passant_square; local->side_to_move = foreign_position.side_to_move; if (invert_colors) flip_side_to_move_local(local); for (foreign_piece = 0; foreign_piece < tb1->num_mobiles; foreign_piece ++) { int sq = foreign_position.piece_position[foreign_piece]; if (invert_colors) sq = square(7 - ROW(sq), COL(sq)); for (piece = 0; piece < tb2->num_mobiles; piece ++) { if ((tb1->piece_type[foreign_piece] == tb2->piece_type[piece]) && (invert_colors ? (tb1->piece_color[foreign_piece] != tb2->piece_color[piece]) : (tb1->piece_color[foreign_piece] == tb2->piece_color[piece])) && !(pieces_processed_bitvector & (1 << piece))) { local->piece_position[piece] = sq; local->board_vector |= BITVECTOR(sq); if (tb2->piece_color[piece] == WHITE) local->white_vector |= BITVECTOR(sq); else local->black_vector |= BITVECTOR(sq); pieces_processed_bitvector |= (1 << piece); break; } } if (piece == tb2->num_mobiles) { if (extra_piece != NONE) { fprintf(stderr, "More than one extra piece in translation\n"); return -1; } /* XXX I'd like to change this (for consistency) to be the piece index in the * futurebase, but since there is still an intermediate global position, that will * have to wait. */ extra_piece = sq; } } /* Make sure all the pieces but one have been accounted for. We count a piece as "free" if * either it hasn't been processed at all, or if it was processed but was outside its move * restriction. */ for (piece = 0; piece < tb2->num_mobiles; piece ++) { if (!(pieces_processed_bitvector & (1 << piece))) { if (missing_piece1 == NONE) { missing_piece1 = piece; } else if (missing_piece2 == NONE) { if (tb2->piece_type[piece] == PAWN) { missing_piece2 = missing_piece1; missing_piece1 = piece; } else { missing_piece2 = piece; } } else { fprintf(stderr, "More than one missing piece in translation\n"); return -1; } } else if (!(tb2->piece_legal_squares[piece] & BITVECTOR(local->piece_position[piece]))) { if (restricted_piece == NONE) restricted_piece = piece; else { fprintf(stderr, "More than one restricted piece in translation\n"); return -1; } } } return ((missing_piece2 << 24) | (extra_piece << 16) | (restricted_piece << 8) | missing_piece1); } /* This function works just like previous one. So much so that I've considered wrapping them * together, but since this one is already written, I'll just leave it alone for now. * * It's only use now is by the probing code (see next function). */ int32 global_position_to_local_position(tablebase_t *tb, global_position_t *global, local_position_t *local) { int piece; int restricted_piece = NONE; int missing_piece1 = NONE; int missing_piece2 = NONE; int extra_piece = NONE; int square; short pieces_processed_bitvector = 0; bzero(local, sizeof(local_position_t)); for (piece = 0; piece < tb->num_mobiles; piece ++) local->piece_position[piece] = -1; local->en_passant_square = global->en_passant_square; local->side_to_move = global->side_to_move; for (square = 0; square < NUM_SQUARES; square ++) { if ((global->board[square] != 0) && (global->board[square] != ' ')) { for (piece = 0; piece < tb->num_mobiles; piece ++) { if ((global->board[square] == global_pieces[tb->piece_color[piece]][tb->piece_type[piece]]) && !(pieces_processed_bitvector & (1 << piece))) { local->piece_position[piece] = square; local->board_vector |= BITVECTOR(square); if (tb->piece_color[piece] == WHITE) local->white_vector |= BITVECTOR(square); else local->black_vector |= BITVECTOR(square); pieces_processed_bitvector |= (1 << piece); break; } } if (piece == tb->num_mobiles) { if (extra_piece != NONE) { /* This can happen if we're probing a whole bunch of radically different tablebases. */ /* fprintf(stderr, "More than one extra piece in translation\n"); */ return -1; } /* XXX I'd like to change this (for consistency) to be the piece index in the * futurebase, but since there is still an intermediate global position, that will * have to wait. */ extra_piece = square; } } } /* Make sure all the pieces but one have been accounted for. We count a piece as "free" if * either it hasn't been processed at all, or if it was processed but was outside its move * restriction. */ for (piece = 0; piece < tb->num_mobiles; piece ++) { if (!(pieces_processed_bitvector & (1 << piece))) { if (missing_piece1 == NONE) { missing_piece1 = piece; } else if (missing_piece2 == NONE) { if (tb->piece_type[piece] == PAWN) { missing_piece2 = missing_piece1; missing_piece1 = piece; } else { missing_piece2 = piece; } } else { /* This can happen if we're probing a whole bunch of radically different tablebases. */ /* fprintf(stderr, "More than one missing piece in translation\n"); */ return -1; } } else if (!(tb->piece_legal_squares[piece] & BITVECTOR(local->piece_position[piece]))) { if (restricted_piece == NONE) restricted_piece = piece; else { /* This can happen if we're probing a whole bunch of radically different tablebases. */ /* fprintf(stderr, "More than one restricted piece in translation\n"); */ return -1; } } } return ((missing_piece2 << 24) | (extra_piece << 16) | (restricted_piece << 8) | missing_piece1); } int32 global_position_to_index(tablebase_t *tb, global_position_t *global) { local_position_t local; if (global_position_to_local_position(tb, global, &local) != 0x80808080) return -1; return local_position_to_index(tb, &local); } /* index_to_global_position() * * Used during Nalimov tablebase verification (by running through all indices in a tablebase), as * well as during probe code to consider possible captures and promotions because they may lead out * of the current tablebase. * * Massively simplified from an earlier implementation because I want to contain the details of * indexing to the local position routines. Probably a little bit slower now, but not too much. * * Seems never to be used on a tablebase under construction; only on a finished one. */ boolean index_to_global_position(tablebase_t *tb, int32 index, global_position_t *global) { local_position_t local; int piece; if (! index_to_local_position(tb, index, &local)) return 0; bzero(global, sizeof(global_position_t)); global->side_to_move = local.side_to_move; global->en_passant_square = local.en_passant_square; for (piece = 0; piece < tb->num_mobiles; piece++) { global->board[local.piece_position[piece]] = global_pieces[tb->piece_color[piece]][tb->piece_type[piece]]; global->board_vector |= BITVECTOR(local.piece_position[piece]); } return 1; } /***** PARSING FEN TO/FROM POSITION STRUCTURES *****/ boolean place_piece_in_local_position(tablebase_t *tb, local_position_t *pos, int square, int color, int type) { int piece; if (pos->board_vector & BITVECTOR(square)) return 0; for (piece = 0; piece < tb->num_mobiles; piece ++) { if ((tb->piece_type[piece] == type) && (tb->piece_color[piece] == color)) { pos->piece_position[piece] = square; pos->board_vector |= BITVECTOR(square); if (color == WHITE) pos->white_vector |= BITVECTOR(square); else pos->black_vector |= BITVECTOR(square); return 1; } } return 0; } boolean place_piece_in_global_position(global_position_t *position, int square, int color, int type) { position->board[square] = global_pieces[color][type]; return 1; } boolean parse_FEN_to_local_position(char *FEN_string, tablebase_t *tb, local_position_t *pos) { int row, col; bzero(pos, sizeof(local_position_t)); pos->en_passant_square = -1; for (row=7; row>=0; row--) { for (col=0; col<=7; col++) { switch (*FEN_string) { case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': /* subtract one here since the 'for' loop will bump col by one */ col += *FEN_string - '0' - 1; if (col > 7) return 0; break; case 'k': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, KING)) return 0; break; case 'K': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, KING)) return 0; break; case 'q': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, QUEEN)) return 0; break; case 'Q': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, QUEEN)) return 0; break; case 'r': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, ROOK)) return 0; break; case 'R': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, ROOK)) return 0; break; case 'b': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, BISHOP)) return 0; break; case 'B': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, BISHOP)) return 0; break; case 'n': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, KNIGHT)) return 0; break; case 'N': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, KNIGHT)) return 0; break; case 'p': if (!place_piece_in_local_position(tb, pos, square(row, col), BLACK, PAWN)) return 0; break; case 'P': if (!place_piece_in_local_position(tb, pos, square(row, col), WHITE, PAWN)) return 0; break; } FEN_string++; } if (row > 0) { if (*FEN_string != '/') return 0; else FEN_string++; } } if (*FEN_string != ' ') return 0; while (*FEN_string == ' ') FEN_string ++; if (*FEN_string == 'w') { pos->side_to_move = WHITE; } else if (*FEN_string == 'b') { pos->side_to_move = BLACK; } else { return 0; } while (*FEN_string == ' ') FEN_string ++; /* skip castling rights (if they exist) */ while ((*FEN_string == '-') || (*FEN_string == 'K') || (*FEN_string == 'Q') || (*FEN_string == 'k') || (*FEN_string == 'q')) FEN_string ++; while (*FEN_string == ' ') FEN_string ++; /* If en passant square was specified, parse it */ if ((FEN_string[0] >= 'a') && (FEN_string[0] <= 'h') && (FEN_string[1] >= '1') && (FEN_string[1] <= '8')) { pos->en_passant_square = square(FEN_string[1] - '1', FEN_string[0] - 'a'); } return 1; } boolean parse_FEN_to_global_position(char *FEN_string, global_position_t *pos) { int row, col; bzero(pos, sizeof(global_position_t)); pos->en_passant_square = -1; for (row=7; row>=0; row--) { for (col=0; col<=7; col++) { switch (*FEN_string) { case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': /* subtract one here since the 'for' loop will bump col by one */ col += *FEN_string - '0' - 1; if (col > 7) return 0; break; case 'k': if (!place_piece_in_global_position(pos, square(row, col), BLACK, KING)) return 0; break; case 'K': if (!place_piece_in_global_position(pos, square(row, col), WHITE, KING)) return 0; break; case 'q': if (!place_piece_in_global_position(pos, square(row, col), BLACK, QUEEN)) return 0; break; case 'Q': if (!place_piece_in_global_position(pos, square(row, col), WHITE, QUEEN)) return 0; break; case 'r': if (!place_piece_in_global_position(pos, square(row, col), BLACK, ROOK)) return 0; break; case 'R': if (!place_piece_in_global_position(pos, square(row, col), WHITE, ROOK)) return 0; break; case 'b': if (!place_piece_in_global_position(pos, square(row, col), BLACK, BISHOP)) return 0; break; case 'B': if (!place_piece_in_global_position(pos, square(row, col), WHITE, BISHOP)) return 0; break; case 'n': if (!place_piece_in_global_position(pos, square(row, col), BLACK, KNIGHT)) return 0; break; case 'N': if (!place_piece_in_global_position(pos, square(row, col), WHITE, KNIGHT)) return 0; break; case 'p': if (!place_piece_in_global_position(pos, square(row, col), BLACK, PAWN)) return 0; break; case 'P': if (!place_piece_in_global_position(pos, square(row, col), WHITE, PAWN)) return 0; break; } FEN_string++; } if (row > 0) { if (*FEN_string != '/') return 0; else FEN_string++; } } if (*FEN_string != ' ') return 0; while (*FEN_string == ' ') FEN_string ++; if (*FEN_string == 'w') { pos->side_to_move = WHITE; } else if (*FEN_string == 'b') { pos->side_to_move = BLACK; } else { return 0; } while (*FEN_string == ' ') FEN_string ++; /* skip castling rights (if they exist) */ while ((*FEN_string == '-') || (*FEN_string == 'K') || (*FEN_string == 'Q') || (*FEN_string == 'k') || (*FEN_string == 'q')) FEN_string ++; while (*FEN_string == ' ') FEN_string ++; /* If en passant square was specified, parse it */ if ((FEN_string[0] >= 'a') && (FEN_string[0] <= 'h') && (FEN_string[1] >= '1') && (FEN_string[1] <= '8')) { pos->en_passant_square = square(FEN_string[1] - '1', FEN_string[0] - 'a'); } return 1; } /* Note that the buffer in this function is static... */ char * global_position_to_FEN(global_position_t *position) { static char buffer[256]; char *ptr = buffer; int empty_squares; int row, col; for (row=7; row>=0; row--) { empty_squares=0; for (col=0; col<=7; col++) { if ((position->board[square(row, col)] == ' ') || (position->board[square(row,col)] == 0)) { empty_squares++; } else { if (empty_squares > 0) { *(ptr++) = '0' + empty_squares; empty_squares = 0; } *(ptr++) = position->board[square(row,col)]; } } if (empty_squares > 0) { *(ptr++) = '0' + empty_squares; } if (row > 0) *(ptr++) = '/'; } *(ptr++) = ' '; *(ptr++) = (position->side_to_move == WHITE) ? 'w' : 'b'; /* no castling rights */ *(ptr++) = ' '; *(ptr++) = '-'; *(ptr++) = ' '; if (position->en_passant_square == -1) { *(ptr++) = '-'; } else { *(ptr++) = 'a' + COL(position->en_passant_square); *(ptr++) = '1' + ROW(position->en_passant_square); } *(ptr++) = '\0'; return buffer; } /* This routine looks at "movestr" to try and figure out if it is a valid move from this global * position. If so, it changes the global position to reflect the move and returns true. * Otherwise, it leaves the global position alone and returns false. */ boolean parse_move_in_global_position(char *movestr, global_position_t *global) { int origin_square, destination_square; int is_capture = 0; unsigned char promotion_piece = '\0'; if (movestr[0] >= 'a' && movestr[0] <= 'h' && movestr[1] >= '1' && movestr[1] <= '8') { origin_square = movestr[0]-'a' + (movestr[1]-'1')*8; movestr += 2; } else { return 0; } if (movestr[0] == 'x') { is_capture = 1; movestr ++; } if (movestr[0] >= 'a' && movestr[0] <= 'h' && movestr[1] >= '1' && movestr[1] <= '8') { destination_square = movestr[0]-'a' + (movestr[1]-'1')*8; movestr += 2; } else { return 0; } if (movestr[0] == '=') { movestr ++; promotion_piece = movestr[0]; } if (!(global->board[origin_square] >= 'A' && global->board[origin_square] <= 'Z') && global->side_to_move == WHITE) return 0; if (!(global->board[origin_square] >= 'a' && global->board[origin_square] <= 'z') && global->side_to_move == BLACK) return 0; if (global->board[destination_square] >= 'A' && !is_capture) return 0; if (!(global->board[destination_square] >= 'A' && global->board[destination_square] <= 'Z') && is_capture && global->side_to_move == BLACK) return 0; if (!(global->board[destination_square] >= 'a' && global->board[destination_square] <= 'z') && is_capture && global->side_to_move == WHITE) return 0; global->board[destination_square] = promotion_piece ? promotion_piece : global->board[origin_square]; global->board[origin_square] = 0; if (global->side_to_move == WHITE) global->side_to_move = BLACK; else global->side_to_move = WHITE; global->en_passant_square = -1; if ((global->board[destination_square] == 'P') && (origin_square == destination_square - 16)) { global->en_passant_square = destination_square - 8; } if ((global->board[destination_square] == 'p') && (origin_square == destination_square + 16)) { global->en_passant_square = destination_square + 8; } /* XXX doesn't modify board vector */ return 1; } /* MORE TABLEBASE OPERATIONS - those that probe and manipulate individual position entries * * "Designed to multi-thread" * * Keep atomic operations confined to single functions. Design functions so that functions calling * them don't need to know the details of table format, either. * * These "add one" functions (atomically) add one to the count in question, subtract one from the * total move count, and flag the position as 'ready for propagation' (maybe this is just a move * count of zero) if the total move count goes to zero. * * PTM = Player to Move * PNTM = Player not to Move * */ inline short does_PTM_win(tablebase_t *tb, int32 index) { return (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_NEEDED) || (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_DONE); } inline short does_PNTM_win(tablebase_t *tb, int32 index) { return (tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_NEEDED) || (tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_DONE); } inline boolean needs_propagation(tablebase_t *tb, int32 index) { return (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_NEEDED) || (tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_NEEDED); } inline boolean is_position_valid(tablebase_t *tb, int32 index) { return (! (does_PTM_win(tb, index) && (tb->entries[index].mate_in_cnt == 0))); } inline void mark_propagated(tablebase_t *tb, int32 index) { if (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_NEEDED) { tb->entries[index].movecnt = PTM_WINS_PROPAGATION_DONE; } else if (tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_NEEDED) { tb->entries[index].movecnt = PNTM_WINS_PROPAGATION_DONE; } else { fprintf(stderr, "Propagation attempt on a completed or unresolved position\n"); /* BREAKPOINT */ } } /* get_mate_in_count() is also used as basically (does_PTM_win() || does_PNTM_win()), so it has * to return -1 if there is no mate from this position */ inline int get_mate_in_count(tablebase_t *tb, int32 index) { if (tb->entries[index].movecnt >= 1 && tb->entries[index].movecnt <= MAX_MOVECNT) { return -1; } else { return tb->entries[index].mate_in_cnt; } } inline int get_stalemate_count(tablebase_t *tb, int32 index) { return tb->entries[index].stalemate_cnt; } /* DEBUG_MOVE can be used to print more verbose debugging information about what the program is * doing to process a single move. */ /* #define DEBUG_MOVE 262273 */ /* Five possible ways we can initialize an index for a position: * - it's illegal * - white's mated (black is to move) * - black's mated (white is to move) * - stalemate * - any other position, with 'movecnt' possible moves out the position */ void initialize_index_as_illegal(tablebase_t *tb, int32 index) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("initialize_index_as_illegal; index=%d\n", index); #endif tb->entries[index].movecnt = ILLEGAL_POSITION; tb->entries[index].mate_in_cnt = 255; tb->entries[index].stalemate_cnt = 255; tb->entries[index].futuremove_cnt = 0; } void initialize_index_with_white_mated(tablebase_t *tb, int32 index) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("initialize_index_with_white_mated; index=%d\n", index); #endif #if 0 if (WHITE_TO_MOVE(index)) { fprintf(stderr, "initialize_index_with_white_mated in a white to move position!\n"); } #endif tb->entries[index].movecnt = PTM_WINS_PROPAGATION_NEEDED; tb->entries[index].mate_in_cnt = 0; tb->entries[index].stalemate_cnt = 0; tb->entries[index].futuremove_cnt = 0; } void initialize_index_with_black_mated(tablebase_t *tb, int32 index) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("initialize_index_with_black_mated; index=%d\n", index); #endif #if 0 if (BLACK_TO_MOVE(index)) { fprintf(stderr, "initialize_index_with_black_mated in a black to move position!\n"); } #endif tb->entries[index].movecnt = PTM_WINS_PROPAGATION_NEEDED; tb->entries[index].mate_in_cnt = 0; tb->entries[index].stalemate_cnt = 0; tb->entries[index].futuremove_cnt = 0; } void initialize_index_with_stalemate(tablebase_t *tb, int32 index) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("initialize_index_with_stalemate; index=%d\n", index); #endif tb->entries[index].movecnt = 251; /* use this as stalemate for now */ tb->entries[index].mate_in_cnt = 255; tb->entries[index].stalemate_cnt = 0; tb->entries[index].futuremove_cnt = 0; } void initialize_index_with_movecnt(tablebase_t *tb, int32 index, int movecnt, int futuremove_cnt) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("initialize_index_with_movecnt; index=%d movecnt=%d\n", index, movecnt); #endif tb->entries[index].movecnt = movecnt; tb->entries[index].mate_in_cnt = 255; tb->entries[index].stalemate_cnt = 255; tb->entries[index].futuremove_cnt = futuremove_cnt; } inline void PTM_wins(tablebase_t *tb, int32 index, int mate_in_count, int stalemate_count) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("PTM_wins; index=%d; movecnt=%d; old mate_in=%d, mate_in=%d\n", index, tb->entries[index].movecnt, tb->entries[index].mate_in_cnt, mate_in_count); #endif if (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_DONE) { if (mate_in_count < tb->entries[index].mate_in_cnt) { fprintf(stderr, "Mate in count dropped in PTM_wins after propagation done!?\n"); /* BREAKPOINT */ } } else if (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_NEEDED) { if (mate_in_count < tb->entries[index].mate_in_cnt) { /* This can happen if we're propagating in from a futurebase, since the propagation runs * through the futurebase in index order, not mate-in order. */ /* fprintf(stderr, "Mate in count dropped in PTM_wins!?\n"); */ tb->entries[index].mate_in_cnt = mate_in_count; tb->entries[index].stalemate_cnt = stalemate_count; } } else if ((tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_NEEDED) || (tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_DONE)) { fprintf(stderr, "PTM_wins in a position where PNTM already won?!\n"); /* BREAKPOINT */ } else { tb->entries[index].movecnt = PTM_WINS_PROPAGATION_NEEDED; tb->entries[index].mate_in_cnt = mate_in_count; tb->entries[index].stalemate_cnt = stalemate_count; } } inline void add_one_to_PNTM_wins(tablebase_t *tb, int32 index, int mate_in_count, int stalemate_count) { #ifdef DEBUG_MOVE if (index == DEBUG_MOVE) printf("add_one_to_PNTM_wins; index=%d; movecnt=%d; old mate_in=%d, mate_in=%d\n", index, tb->entries[index].movecnt, tb->entries[index].mate_in_cnt, mate_in_count); #endif if ((tb->entries[index].movecnt == PTM_WINS_PROPAGATION_NEEDED) || (tb->entries[index].movecnt == PTM_WINS_PROPAGATION_DONE)) { /* This is OK. PTM already found a way to win. Do nothing. */ } else if ((tb->entries[index].movecnt == 0) || (tb->entries[index].movecnt > MAX_MOVECNT)) { fprintf(stderr, "add_one_to_PNTM_wins in an already won position!?\n"); /* BREAKPOINT */ } else { /* since PNTM_WIN_PROPAGATION_NEEDED is 0, this decrements right into the special flag, * no extra check needed here */ tb->entries[index].movecnt --; if ((mate_in_count < tb->entries[index].mate_in_cnt) && (tb->entries[index].mate_in_cnt != 255)) { /* (255 means we haven't found any mates yet in this position) As above, this can * happen during a futurebase back propagation, and if it does... we do nothing! * Since this is PNTM wins, PTM will make the move leading to the slowest mate. */ /* XXX need to think more about the stalemates */ /* fprintf(stderr, "mate-in count dropped in add_one_to_PNTM_wins?\n"); */ /* tb->entries[index].mate_in_cnt = mate_in_count; */ /* tb->entries[index].stalemate_cnt = stalemate_count; */ } else { tb->entries[index].mate_in_cnt = mate_in_count; tb->entries[index].stalemate_cnt = stalemate_count; } if ((tb->entries[index].movecnt == PNTM_WINS_PROPAGATION_NEEDED) && (tb->entries[index].mate_in_cnt == 1)) { /* In this case, the only moves at PTM's disposal move him into check (mate_in_cnt is * now one, so it would drop to zero on next move). So we need to distinguish here * between being in check (it's checkmate) and not being in check (stalemate). The * simplest way to do this is to flip the side-to-move flag and look at the position * with the other side to move. If the king can be taken, then that other position * will be PTM_WINS (of either flavor) with a zero mate_in_cnt. */ /* XXX assumes that flipping lowest bit in index flips side-to-move flag */ if (does_PTM_win(tb, index^1) && (tb->entries[index^1].mate_in_cnt == 0)) { } else { initialize_index_with_stalemate(tb, index); } } /* XXX not sure about this stalemate code */ if (stalemate_count < tb->entries[index].stalemate_cnt) { tb->entries[index].stalemate_cnt = stalemate_count; } } } /***** MOVEMENT VECTORS *****/ /* The idea here is to calculate piece movements, and to do it FAST. * * We build a table of "movements" organized into "directions". Each direction is just that - the * direction that a piece (like a queen) moves. When we want to check for what movements are * possible in a given direction, we run through the direction until we "hit" another pieces - until * the bit in the vector matches something already in the position vector. At the end of the * direction, an all-ones vector will "hit" the end of the board and end the direction. I know, * kinda confusing. It's because it's designed to be fast; we have to do this a lot. */ struct movement { int64 vector; short square; }; /* we add one to NUM_MOVEMENTS to leave space at the end for the all-ones bitmask that signals the * end of the list */ struct movement movements[NUM_PIECES][NUM_SQUARES][NUM_DIR][NUM_MOVEMENTS+1]; /* Pawns are, of course, special. We have seperate vectors for different types of pawn movements. * Each array is indexed first by square number, then by side (WHITE or BLACK - this doesn't exist * for other pieces), then by the number of possibilities (at most two normal movements, at most two * captures, and one more for the all-ones bitvector to terminate) * * All of these are FORWARD motions. */ struct movement normal_pawn_movements[NUM_SQUARES][2][3]; struct movement capture_pawn_movements[NUM_SQUARES][2][3]; struct movement normal_pawn_movements_bkwd[NUM_SQUARES][2][3]; struct movement capture_pawn_movements_bkwd[NUM_SQUARES][2][3]; /* How many different directions can each piece move in? Knights have 8 directions because they * can't be blocked in any of them. Pawns are handled separately. */ int number_of_movement_directions[NUM_PIECES] = {8,8,4,4,8,0}; int maximum_movements_in_one_direction[NUM_PIECES] = {1,7,7,7,1,0}; enum {RIGHT, LEFT, UP, DOWN, DIAG_UL, DIAG_UR, DIAG_DL, DIAG_DR, KNIGHTmove} movementdir[5][8] = { {RIGHT, LEFT, UP, DOWN, DIAG_UL, DIAG_UR, DIAG_DL, DIAG_DR}, /* King */ {RIGHT, LEFT, UP, DOWN, DIAG_UL, DIAG_UR, DIAG_DL, DIAG_DR}, /* Queen */ {RIGHT, LEFT, UP, DOWN}, /* Rook */ {DIAG_UL, DIAG_UR, DIAG_DL, DIAG_DR}, /* Bishop */ {KNIGHTmove, KNIGHTmove, KNIGHTmove, KNIGHTmove, KNIGHTmove, KNIGHTmove, KNIGHTmove, KNIGHTmove}, /* Knights are special... */ }; char algebraic_notation[64][3]; void init_movements() { int square, piece, dir, mvmt, color; for (square=0; square < NUM_SQUARES; square++) { bitvector[square] = 1ULL << square; algebraic_notation[square][0] = 'a' + square%8; algebraic_notation[square][1] = '1' + square/8; algebraic_notation[square][2] = '\0'; } for (piece=KING; piece <= KNIGHT; piece++) { for (square=0; square < NUM_SQUARES; square++) { for (dir=0; dir < number_of_movement_directions[piece]; dir++) { int current_square = square; for (mvmt=0; mvmt < maximum_movements_in_one_direction[piece]; mvmt ++) { #define RIGHT_MOVEMENT_POSSIBLE ((current_square%8)<7) #define RIGHT2_MOVEMENT_POSSIBLE ((current_square%8)<6) #define LEFT_MOVEMENT_POSSIBLE ((current_square%8)>0) #define LEFT2_MOVEMENT_POSSIBLE ((current_square%8)>1) #define UP_MOVEMENT_POSSIBLE (current_square<56) #define UP2_MOVEMENT_POSSIBLE (current_square<48) #define DOWN_MOVEMENT_POSSIBLE (current_square>7) #define DOWN2_MOVEMENT_POSSIBLE (current_square>15) switch (movementdir[piece][dir]) { case RIGHT: if (RIGHT_MOVEMENT_POSSIBLE) { current_square++; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case LEFT: if (LEFT_MOVEMENT_POSSIBLE) { current_square--; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case UP: if (UP_MOVEMENT_POSSIBLE) { current_square+=8; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case DOWN: if (DOWN_MOVEMENT_POSSIBLE) { current_square-=8; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case DIAG_UL: if (LEFT_MOVEMENT_POSSIBLE && UP_MOVEMENT_POSSIBLE) { current_square+=8; current_square--; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case DIAG_UR: if (RIGHT_MOVEMENT_POSSIBLE && UP_MOVEMENT_POSSIBLE) { current_square+=8; current_square++; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case DIAG_DL: if (LEFT_MOVEMENT_POSSIBLE && DOWN_MOVEMENT_POSSIBLE) { current_square-=8; current_square--; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case DIAG_DR: if (RIGHT_MOVEMENT_POSSIBLE && DOWN_MOVEMENT_POSSIBLE) { current_square-=8; current_square++; movements[piece][square][dir][mvmt].square = current_square; movements[piece][square][dir][mvmt].vector = BITVECTOR(current_square); } else { movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } break; case KNIGHTmove: current_square=square; switch (dir) { case 0: if (RIGHT2_MOVEMENT_POSSIBLE && UP_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square + 2 + 8; movements[piece][square][dir][0].vector = BITVECTOR(square + 2 + 8); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 1: if (RIGHT2_MOVEMENT_POSSIBLE && DOWN_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square + 2 - 8; movements[piece][square][dir][0].vector = BITVECTOR(square + 2 - 8); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 2: if (LEFT2_MOVEMENT_POSSIBLE && UP_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square - 2 + 8; movements[piece][square][dir][0].vector = BITVECTOR(square - 2 + 8); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 3: if (LEFT2_MOVEMENT_POSSIBLE && DOWN_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square - 2 - 8; movements[piece][square][dir][0].vector = BITVECTOR(square - 2 - 8); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 4: if (RIGHT_MOVEMENT_POSSIBLE && UP2_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square + 1 + 16; movements[piece][square][dir][0].vector = BITVECTOR(square + 1 + 16); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 5: if (RIGHT_MOVEMENT_POSSIBLE && DOWN2_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square + 1 - 16; movements[piece][square][dir][0].vector = BITVECTOR(square + 1 - 16); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 6: if (LEFT_MOVEMENT_POSSIBLE && UP2_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square - 1 + 16; movements[piece][square][dir][0].vector = BITVECTOR(square - 1 + 16); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; case 7: if (LEFT_MOVEMENT_POSSIBLE && DOWN2_MOVEMENT_POSSIBLE) { movements[piece][square][dir][0].square = square - 1 - 16; movements[piece][square][dir][0].vector = BITVECTOR(square - 1 - 16); movements[piece][square][dir][1].square = -1; movements[piece][square][dir][1].vector = allones_bitvector; } else { movements[piece][square][dir][0].square = -1; movements[piece][square][dir][0].vector = allones_bitvector; } break; } break; } } /* Always put an allones_bitvector at the end of the movement vector * to make sure we stop! */ movements[piece][square][dir][mvmt].square = -1; movements[piece][square][dir][mvmt].vector = allones_bitvector; } } } /* Now for the pawns... */ for (square=0; square < NUM_SQUARES; square ++) { for (color = WHITE; color <= BLACK; color ++) { int forwards_pawn_move = ((color == WHITE) ? 8 : -8); int backwards_pawn_move = ((color == WHITE) ? -8 : 8); /* Forward pawn movements * * An ordinary pawn move... unless its a white pawn on the second rank, or a black * pawn on the seventh. In these two cases, there is a possible double move as * well. */ mvmt = 0; if ((ROW(square) >= 1) && (ROW(square) <= 6)) { normal_pawn_movements[square][color][mvmt].square = square + forwards_pawn_move; normal_pawn_movements[square][color][mvmt].vector = BITVECTOR(square + forwards_pawn_move); mvmt ++; } if (((color == WHITE) && (ROW(square) == 1)) || ((color == BLACK) && (ROW(square) == 6))) { normal_pawn_movements[square][color][mvmt].square = square + 2*forwards_pawn_move; normal_pawn_movements[square][color][mvmt].vector = BITVECTOR(square + 2*forwards_pawn_move); mvmt ++; } normal_pawn_movements[square][color][mvmt].square = -1; normal_pawn_movements[square][color][mvmt].vector = allones_bitvector; /* Backwards pawn movements */ mvmt = 0; if (((color == WHITE) && (ROW(square) > 1)) || ((color == BLACK) && (ROW(square) < 6))) { normal_pawn_movements_bkwd[square][color][mvmt].square = square + backwards_pawn_move; normal_pawn_movements_bkwd[square][color][mvmt].vector = BITVECTOR(square + backwards_pawn_move); mvmt ++; } if (((color == WHITE) && (ROW(square) == 3)) || ((color == BLACK) && (ROW(square) == 4))) { normal_pawn_movements_bkwd[square][color][mvmt].square = square + 2*backwards_pawn_move; normal_pawn_movements_bkwd[square][color][mvmt].vector = BITVECTOR(square + 2*backwards_pawn_move); mvmt ++; } normal_pawn_movements_bkwd[square][color][mvmt].square = -1; normal_pawn_movements_bkwd[square][color][mvmt].vector = allones_bitvector; /* Forward pawn captures. */ mvmt = 0; if ((ROW(square) >= 1) && (ROW(square) <= 6)) { if (COL(square) > 0) { capture_pawn_movements[square][color][mvmt].square = square + forwards_pawn_move - 1; capture_pawn_movements[square][color][mvmt].vector = BITVECTOR(square + forwards_pawn_move - 1); mvmt ++; } if (COL(square) < 7) { capture_pawn_movements[square][color][mvmt].square = square + forwards_pawn_move + 1; capture_pawn_movements[square][color][mvmt].vector = BITVECTOR(square + forwards_pawn_move + 1); mvmt ++; } } capture_pawn_movements[square][color][mvmt].square = -1; capture_pawn_movements[square][color][mvmt].vector = allones_bitvector; /* Backwards pawn captures */ mvmt = 0; if (((color == WHITE) && (ROW(square) > 1)) || ((color == BLACK) && (ROW(square) < 6))) { if (COL(square) > 0) { capture_pawn_movements_bkwd[square][color][mvmt].square = square + backwards_pawn_move - 1; capture_pawn_movements_bkwd[square][color][mvmt].vector = BITVECTOR(square + backwards_pawn_move - 1); mvmt ++; } if (COL(square) < 7) { capture_pawn_movements_bkwd[square][color][mvmt].square = square + backwards_pawn_move + 1; capture_pawn_movements_bkwd[square][color][mvmt].vector = BITVECTOR(square + backwards_pawn_move + 1); mvmt ++; } } capture_pawn_movements_bkwd[square][color][mvmt].square = -1; capture_pawn_movements_bkwd[square][color][mvmt].vector = allones_bitvector; } } } /* This routine is pretty fast, so I just call it once every time the program runs. It has to be * used after any changes to the code above to verify that those complex movement vectors are * correct, or at least consistent. We're using this in a game situation. We can't afford bugs in * this code. */ void verify_movements() { int piece; int squareA, squareB; int dir; int color; struct movement * movementptr; int pawn_option; /* For everything except pawns, if it can move from A to B, then it better be able to move from * B to A... */ for (piece=KING; piece <= KNIGHT; piece ++) { for (squareA=0; squareA < NUM_SQUARES; squareA ++) { for (squareB=0; squareB < NUM_SQUARES; squareB ++) { int movement_possible = 0; int reverse_movement_possible = 0; /* check for possible self-movement, if A and B are the same square */ if (squareA == squareB) { for (dir = 0; dir < number_of_movement_directions[piece]; dir++) { for (movementptr = movements[piece][squareA][dir]; (movementptr->vector & BITVECTOR(squareB)) == 0; movementptr++) ; if ((movementptr->square != -1) || (movementptr->vector != allones_bitvector)) { fprintf(stderr, "Self movement possible!? %s %d %d\n", piece_name[piece], squareA, movementptr->square); } } continue; } /* check for possible A to B move */ for (dir = 0; dir < number_of_movement_directions[piece]; dir++) { for (movementptr = movements[piece][squareA][dir]; (movementptr->vector & BITVECTOR(squareB)) == 0; movementptr++) { if ((movementptr->square < 0) || (movementptr->square >= NUM_SQUARES)) { fprintf(stderr, "Bad movement square: %s %d %d %d\n", piece_name[piece], squareA, squareB, movementptr->square); } } if (movementptr->square == -1) { if (movementptr->vector != allones_bitvector) { fprintf(stderr, "-1 movement lacks allones_bitvector: %s %d %d\n", piece_name[piece], squareA, squareB); } } else if ((movementptr->square < 0) || (movementptr->square >= NUM_SQUARES)) { fprintf(stderr, "Bad movement square: %s %d %d\n", piece_name[piece], squareA, squareB); } else { if (movementptr->square != squareB) { fprintf(stderr, "bitvector does not match destination square: %s %d %d\n", piece_name[piece], squareA, squareB); } if (movement_possible) { fprintf(stderr, "multiple idential destinations from same origin: %s %d %d\n", piece_name[piece], squareA, squareB); } movement_possible = 1; if (movementptr->vector == allones_bitvector) { fprintf(stderr, "allones_bitvector on a legal movement: %s %d %d\n", piece_name[piece], squareA, squareB); } } } for (dir = 0; dir < number_of_movement_directions[piece]; dir++) { for (movementptr = movements[piece][squareB][dir]; (movementptr->vector & BITVECTOR(squareA)) == 0; movementptr++) ; if (movementptr->square != -1) reverse_movement_possible=1; } if (movement_possible && !reverse_movement_possible) { fprintf(stderr, "reverse movement impossible: %s %d %d\n", piece_name[piece], squareA, squareB); } } } } /* Pawns are special */ piece = PAWN; for (pawn_option = 0; pawn_option < 4; pawn_option ++) { struct movement * fwd_movement; struct movement * rev_movement; for (color = WHITE; color <= BLACK; color ++) { /* fprintf(stderr, "Pawn option %d; color %s\n", pawn_option, colors[color]); */ for (squareA=0; squareA < NUM_SQUARES; squareA ++) { for (squareB=0; squareB < NUM_SQUARES; squareB ++) { int movement_possible = 0; int reverse_movement_possible = 0; switch (pawn_option) { case 0: fwd_movement = normal_pawn_movements[squareA][color]; rev_movement = normal_pawn_movements_bkwd[squareB][color]; break; case 1: fwd_movement = normal_pawn_movements_bkwd[squareA][color]; rev_movement = normal_pawn_movements[squareB][color]; break; case 2: fwd_movement = capture_pawn_movements[squareA][color]; rev_movement = capture_pawn_movements_bkwd[squareB][color]; break; case 3: fwd_movement = capture_pawn_movements_bkwd[squareA][color]; rev_movement = capture_pawn_movements[squareB][color]; break; } /* check for self-movement */ if (squareA == squareB) { for (movementptr = fwd_movement; (movementptr->vector & BITVECTOR(squareB)) == 0; movementptr++) ; if ((movementptr->square != -1) || (movementptr->vector != allones_bitvector)) { fprintf(stderr, "Self movement possible!? PAWN %d %d\n", squareA, movementptr->square); } } /* check for possible A to B move */ for (movementptr = fwd_movement; (movementptr->vector & BITVECTOR(squareB)) == 0; movementptr++) { if ((movementptr->square < 0) || (movementptr->square >= NUM_SQUARES)) { fprintf(stderr, "Bad movement square: %s %d %d %d\n", piece_name[piece], squareA, squareB, movementptr->square); } } if (movementptr->square == -1) { if (movementptr->vector != allones_bitvector) { fprintf(stderr, "-1 movement lacks allones_bitvector: %s %d %d\n", piece_name[piece], squareA, squareB); } } else if ((movementptr->square < 0) || (movementptr->square >= NUM_SQUARES)) { fprintf(stderr, "Bad movement square: %s %d %d\n", piece_name[piece], squareA, squareB); } else { if (movementptr->square != squareB) { fprintf(stderr, "bitvector does not match destination square: %s %d %d\n", piece_name[piece], squareA, squareB); } if (movement_possible) { fprintf(stderr, "multiple idential destinations from same origin: %s %d %d\n", piece_name[piece], squareA, squareB); } movement_possible = 1; if (movementptr->vector == allones_bitvector) { fprintf(stderr, "allones_bitvector on a legal movement: %s %d %d\n", piece_name[piece], squareA, squareB); } } /* check for possible B to A reverse move */ for (movementptr = rev_movement; (movementptr->vector & BITVECTOR(squareA)) == 0; movementptr++) ; if (movementptr->square != -1) reverse_movement_possible=1; if (movement_possible && !reverse_movement_possible) { fprintf(stderr, "reverse movement impossible: %s %d %d\n", piece_name[piece], squareA, squareB); } } } } } } /***** FUTUREBASES *****/ /* Subroutines to backpropagate an individual index, or an individual local position (these are the * "mini" routines), or a set of local positions that differ only in the en passant square. * * The idea behind the en passant handling is this. If we back propagate a position with the en * passant square set, then that's the only position we process. If we back prop a position without * the en passant square set, then we process not only that position, but also any positions just * like it that have en passant set. The idea being that we set en passant if we actually need it, * and we clear it if we don't need it, so if it's clear we need to process positions where it was * set, but we didn't use it. */ void propagate_index_from_futurebase(tablebase_t *tb, tablebase_t *futurebase, int32 future_index, int32 current_index, int *mate_in_limit) { /* Skip everything else if the position isn't valid. In particular, * we don't track futuremove propagation for illegal positions. */ if (is_position_valid(tb, current_index)) { /* ...note that we've handled one of the futuremoves out of this position... */ if (tb->entries[current_index].futuremove_cnt == 0) { fprintf(stderr, "Back proping into a position with no futuremoves left!\n"); /* BREAKPOINT */ } tb->entries[current_index].futuremove_cnt --; /* ...and propagate the win */ /* XXX might want to look more closely at the stalemate options here */ if (does_PTM_win(futurebase, future_index)) { add_one_to_PNTM_wins(tb, current_index, get_mate_in_count(futurebase, future_index)+1, 0); } else if (does_PNTM_win(futurebase, future_index)) { PTM_wins(tb, current_index, get_mate_in_count(futurebase, future_index)+1, 0); } /* This is pretty primitive, but we need some way to figure how deep to look during * intra-table propagation. */ if (get_mate_in_count(futurebase, future_index) > *mate_in_limit) *mate_in_limit = get_mate_in_count(futurebase, future_index); } } void propagate_minilocal_position_from_futurebase(tablebase_t *tb, tablebase_t *futurebase, int32 future_index, local_position_t *current_position, int *mate_in_limit) { int32 current_index; /* Look up the position in the current tablebase... */ current_index = local_position_to_index(tb, current_position); if (current_index == -1) { /* This can happen if we don't fully check en passant legality (but right now, we do) */ fprintf(stderr, "Can't lookup local position in futurebase propagation!\n"); /* BREAKPOINT */ return; } propagate_index_from_futurebase(tb, futurebase, future_index, current_index, mate_in_limit); } void propagate_local_position_from_futurebase(tablebase_t *tb, tablebase_t *futurebase, int32 future_index, local_position_t *position, int *mate_in_limit) { int piece; /* We may need to consider a bunch of additional positions here that are identical to the base * position except that a single one of the pawns on the fourth or fifth ranks was capturable en * passant. * * We key off the en_passant flag in the position that was passed in. If it's set, then we're * back propagating a position that requires en passant, so we just do it. Otherwise, we're * back propagating a position that doesn't require en passant, so we check for additional * en passant positions. */ propagate_minilocal_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); if (position->en_passant_square == -1) { for (piece = 0; piece < tb->num_mobiles; piece ++) { if (tb->piece_color[piece] == position->side_to_move) continue; if (tb->piece_type[piece] != PAWN) continue; #if 1 /* XXX I've taken care to update board_vector specifically so we can check for en * passant legality here. */ if ((tb->piece_color[piece] == WHITE) && (ROW(position->piece_position[piece]) == 3) && !(position->board_vector & BITVECTOR(position->piece_position[piece] - 8)) && !(position->board_vector & BITVECTOR(position->piece_position[piece] - 16))) { position->en_passant_square = position->piece_position[piece] - 8; propagate_minilocal_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); } if ((tb->piece_color[piece] == BLACK) && (ROW(position->piece_position[piece]) == 4) && !(position->board_vector & BITVECTOR(position->piece_position[piece] + 8)) && !(position->board_vector & BITVECTOR(position->piece_position[piece] + 16))) { position->en_passant_square = position->piece_position[piece] + 8; propagate_minilocal_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); } #else /* XXX The problem is that the board vector might not be correct, because we moved the * capturing piece without updating it. We get around this by checking in * local_position_to_index() for illegal en passant positions. */ if ((tb->piece_color[piece] == WHITE) && (ROW(position->piece_position[piece]) == 3)) { position->en_passant_square = position->piece_position[piece] - 8; propagate_minilocal_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); } if ((tb->piece_color[piece] == BLACK) && (ROW(position->piece_position[piece]) == 4)) { position->en_passant_square = position->piece_position[piece] + 8; propagate_minilocal_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); } #endif position->en_passant_square = -1; } } } /* Back propagate promotion moves * * Passed a piece (a global position character) that the pawn is promoting into. Searches * futurebase for positions with that piece on the last rank and back-props. */ void propagate_moves_from_promotion_futurebase(tablebase_t *tb, tablebase_t *futurebase, int invert_colors_of_futurebase, unsigned char promoted_piece, int pawn, int *mate_in_limit) { int32 future_index; local_position_t position; int32 conversion_result; int extra_piece, restricted_piece, missing_piece1, missing_piece2; int promotion_color = ((promoted_piece < 'a') ? WHITE : BLACK); int first_back_rank_square = ((promotion_color == WHITE) ? 56 : 0); int last_back_rank_square = ((promotion_color == WHITE) ? 63 : 7); int promotion_move = ((promotion_color == WHITE) ? 8 : -8); /* We could limit the range of future_index here */ for (future_index = 0; future_index <= futurebase->max_index; future_index ++) { /* It's tempting to break out the loop here if the position isn't a win, but if we want to * track futuremoves in order to make sure we don't miss one (probably a good idea), then * the simplest way to do that is to run this loop even for draws. */ /* Take the position from the futurebase and translate it into a local position for the * current tablebase. If the futurebase index was illegal, the function will return -1. * Otherwise, there should be one piece missing from the local position (the pawn that * promoted) and one piece extra (what it promoted into). There can be no pieces on * restricted squares. */ conversion_result = translate_foreign_index_to_local_position(futurebase, future_index, tb, &position, invert_colors_of_futurebase); if (conversion_result != -1) { extra_piece = (conversion_result >> 16) & 0xff; restricted_piece = (conversion_result >> 8) & 0xff; missing_piece1 = conversion_result & 0xff; missing_piece2 = (conversion_result >> 24) & 0xff; if ((extra_piece == NONE) || missing_piece1 != pawn) { fprintf(stderr, "Conversion error during promotion back-prop\n"); /* BREAKPOINT */ continue; } /* This can happen if the futurebase is more liberal than the current tablebase. */ if (restricted_piece != NONE) continue; /* Since the last move had to have been a promotion move, there is absolutely no way we * could have en passant capturable pawns in the futurebase position. */ if (position.en_passant_square != -1) continue; /* Whatever color the promoted piece is, after the promotion it must be the other side * to move. */ if (position.side_to_move == promotion_color) continue; /* The extra piece has to be on the back rank */ if ((extra_piece < first_back_rank_square) || (extra_piece > last_back_rank_square)) continue; /* There has to be an empty square right behind where the pawn came from. */ if (position.board_vector & BITVECTOR(extra_piece - promotion_move)) continue; /* And it has to be a legal (i.e, non-restricted) square for the pawn in our tablebase. */ if (!(tb->piece_legal_squares[pawn] & BITVECTOR(extra_piece - promotion_move))) continue; /* We're going to back step a half move now */ flip_side_to_move_local(&position); /* Because the promoted piece was 'extra' it doesn't appear in the local position, so we * don't have to worry about taking it off the board. Put the missing pawn on the * seventh (or second). */ position.piece_position[pawn] = extra_piece - promotion_move; position.board_vector |= BITVECTOR(extra_piece - promotion_move); /* Back propagate the resulting position */ /* This function also back props any similar positions with one of the pawns * from the side that didn't promote in an en passant state. */ propagate_local_position_from_futurebase(tb, futurebase, future_index, &position, mate_in_limit); /* Don't bother to put anything back since we recompute a new position next time around. */ } } } void propagate_moves_from_promotion_capture_futurebase(tablebase_t *tb, tablebase_t *futurebase, int invert_colors_of_futurebase, unsigned char promoted_piece, unsigned char captured_piece, int pawn, int *mate_in_limit) { int32 future_index; local_position_t position; int32 conversion_result; int extra_piece, restricted_piece, missing_piece1, missing_piece2; int promotion_color = ((promoted_piece < 'a') ? WHITE : BLACK); int first_back_rank_square = ((promotion_color == WHITE) ? 56 : 0); int last_back_rank_square = ((promotion_color == WHITE) ? 63 : 7); int promotion_move = ((promotion_color == WHITE) ? 8 : -8); /* We could limit the range of future_index here */ for (future_index = 0; future_index <= futurebase->max_index; future_index ++) { /* It's tempting to break out the loop here if the position isn't a win, but if we want to * track futuremoves in order to make sure we don't miss one (probably a good idea), then * the simplest way to do that is to run this loop even for draws. */ /* Take the position from the futurebase and translate it into a local position for the * current tablebase. If the futurebase index was illegal, the function will return -1. * Otherwise, there should be two pieces missing from the local position (the pawn that * promoted and the piece it captured) and one piece extra (what it promoted into). There * can be no pieces on restricted squares. */ conversion_result = translate_foreign_index_to_local_position(futurebase, future_index, tb, &position, invert_colors_of_futurebase); if (conversion_result != -1) { extra_piece = (conversion_result >> 16) & 0xff; restricted_piece = (conversion_result >> 8) & 0xff; missing_piece1 = conversion_result & 0xff; missing_piece2 = (conversion_result >> 24) & 0xff; if ((extra_piece == NONE) || (missing_piece1 != pawn) || (missing_piece2 == NONE)) { fprintf(stderr, "Conversion error during promotion capture back-prop\n"); /* BREAKPOINT */ continue; } /* This can happen if the futurebase is more liberal than the current tablebase. */ if (restricted_piece != NONE) continue; /* Since the last move had to have been a promotion move, there is absolutely no way we * could have en passant capturable pawns in the futurebase position. */ if (position.en_passant_square != -1) continue; /* Whatever color the promoted piece is, after the promotion it must be the other side * to move. */ if (position.side_to_move == promotion_color) continue; /* The extra piece has to be on the back rank */ if ((extra_piece < first_back_rank_square) || (extra_piece > last_back_rank_square)) continue; /* We're going to back step a half move now */ flip_side_to_move_local(&position); /* Put the piece that was captured onto the board on the queening square. */ position.piece_position[missing_piece2] = extra_piece; position.board_vector |= BITVECTOR(extra_piece); /* Consider first a capture to the left (white's left). There has to be an empty square * where the pawn came from, and it has to be a legal (i.e, non-restricted) square for * the pawn in our tablebase. */ if ((COL(extra_piece) != 0) && !(position.board_vector & BITVECTOR(extra_piece - promotion_move - 1)) && (tb->piece_legal_squares[pawn] & BITVECTOR(extra_piece - promotion_move - 1))) { /* Because the promoted piece was 'extra' it doesn't appear in the local position, * so we don't have to worry about taking it off the board. Put the missing pawn on * the seventh (or second). */ position.piece_position[pawn] = extra_piece - promotion_move - 1; position.board_vector |= BITVECTOR(extra_piece - promotion_move - 1); /* Back propagate the resulting position */ /* This function also back props any similar positions with one of the pawns from * the side that didn't promote in an en passant state. */ propagate_local_position_from_futurebase(tb, futurebase, future_index, &position, mate_in_limit); /* We're about to use this position again, so put the board_vector back... */ position.board_vector &= ~BITVECTOR(extra_piece - promotion_move - 1); } /* Now consider a capture to the right (white's right). Again, there has to be an empty * square where the pawn came from, and it has to be a legal (i.e, non-restricted) * square for the pawn in our tablebase. */ if ((COL(extra_piece) != 7) && !(position.board_vector & BITVECTOR(extra_piece - promotion_move + 1)) && (tb->piece_legal_squares[pawn] & BITVECTOR(extra_piece - promotion_move + 1))) { /* Because the promoted piece was 'extra' it doesn't appear in the local position, * so we don't have to worry about taking it off the board. Put the missing pawn on * the seventh (or second). */ position.piece_position[pawn] = extra_piece - promotion_move + 1; position.board_vector |= BITVECTOR(extra_piece - promotion_move + 1); /* Back propagate the resulting position */ /* This function also back props any similar positions with one of the pawns from * the side that didn't promote in an en passant state. */ propagate_local_position_from_futurebase(tb, futurebase, future_index, &position, mate_in_limit); /* And we don't have to bother about putting things back... */ } } } } /* Propagate moves from a futurebase that resulted from capturing one of the mobile * pieces in the current tablebase. * * I'm thinking of changing that "invert_colors_of_futurebase" flag to be a subroutine that gets * passed in. It could be a pointer to invert_colors_of_global_position to do what it does now. Or * it could be a "reflect board around vertical axis" to move a d4 pawn to e4. Also see my comments * on invert_colors_of_global position. */ void consider_possible_captures(tablebase_t *tb, tablebase_t *futurebase, int32 future_index, local_position_t *position, int capturing_piece, int captured_piece, int *mate_in_limit) { int dir; struct movement *movementptr; /* We only want to consider pieces of the side which captured... */ if (tb->piece_color[capturing_piece] == tb->piece_color[captured_piece]) return; /* Put the captured piece on the capturing piece's square (from the future position). */ position->piece_position[captured_piece] = position->piece_position[capturing_piece]; /* Now consider all possible backwards movements of the capturing piece. */ if (tb->piece_type[capturing_piece] != PAWN) { /* If the square we put the captured piece on isn't legal for it, then don't consider this * capturing piece in this future position any more. This is after the "if" instead of * before it because an en passant pawn capture is special, since then the capturing piece * ends up on a different square from the captured piece. */ if (!(tb->piece_legal_squares[captured_piece] & BITVECTOR(position->piece_position[captured_piece]))) { return; } for (dir = 0; dir < number_of_movement_directions[tb->piece_type[capturing_piece]]; dir++) { /* Make sure we start each movement of the capturing piece from the capture square */ position->piece_position[capturing_piece] = position->piece_position[captured_piece]; for (movementptr = movements[tb->piece_type[capturing_piece]][position->piece_position[capturing_piece]][dir]; (movementptr->vector & position->board_vector) == 0; movementptr++) { /* We already checked that the captured piece was on a legal square * for it. Now check the capturing piece. */ if (! (tb->piece_legal_squares[capturing_piece] & movementptr->vector)) continue; /* Move the capturing piece... */ /* I update board_vector here because I want to check for en passant legality before * I call local_position_to_index(). It just makes the code a little more robust at * this point, because then there should be no reason for local_position_to_index() * to return -1. * * By the way, the piece didn't "come from" anywhere other than the capture square, * which will have the captured piece on it (this is back prop), so we don't need to * clear anything in board_vector. */ position->piece_position[capturing_piece] = movementptr->square; position->board_vector |= BITVECTOR(movementptr->square); /* This function also back props any similar positions with one of the pawns from * the side that didn't capture in an en passant state. */ propagate_local_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); position->board_vector &= ~BITVECTOR(movementptr->square); } } } else { /* Yes, pawn captures are special */ for (movementptr = capture_pawn_movements_bkwd[position->piece_position[capturing_piece]][tb->piece_color[capturing_piece]]; movementptr->square != -1; movementptr++) { /* Is there anything on the square the pawn had to capture from? */ if ((movementptr->vector & position->board_vector) != 0) continue; /* Move back the capturing pawn and see if it came from a legal square for it. */ position->piece_position[capturing_piece] = movementptr->square; if (! (tb->piece_legal_squares[capturing_piece] & movementptr->vector)) continue; /* And if the captured piece is also on a legal square for it... */ if ((tb->piece_legal_squares[captured_piece] & BITVECTOR(position->piece_position[captured_piece]))) { /* I update board_vector here because I want to check for en passant legality before * I call local_position_to_index(). It just makes the code a little more robust at * this point, because then there should be no reason for local_position_to_index() * to return -1. * * By the way, the piece didn't "come from" anywhere other than the capture square, * which will have the captured piece on it (this is back prop), so we don't need to * clear anything in board_vector. */ position->board_vector |= BITVECTOR(movementptr->square); /* This function also back props any similar positions with one of the pawns from * the side that didn't capture in an en passant state. */ propagate_local_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); position->board_vector &= ~BITVECTOR(movementptr->square); } /* The en passant special case: if both the piece that captured and the piece that was * captured are both pawns, and either a white pawn captured from the fifth rank, or a * black pawn captured from the fourth, then there are two possible back prop positions * - the obvious one we just handled, and the one where the captured pawn was in an en * passant state. We also make sure right away that the rank is clear where the pawn * had to come from, and the rank is clear where the pawn had to go to, ensuring that an * en passant move was even possible. */ if ((tb->piece_type[captured_piece] == PAWN) && !(position->board_vector & BITVECTOR(position->piece_position[captured_piece]-8)) && !(position->board_vector & BITVECTOR(position->piece_position[captured_piece]+8))) { if ((tb->piece_color[capturing_piece] == BLACK) && (ROW(movementptr->square) == 3)) { /* A black pawn capturing a white one (en passant) * * The white pawn is actually a rank higher than usual. */ position->en_passant_square = position->piece_position[captured_piece]; position->piece_position[captured_piece] += 8; if ((tb->piece_legal_squares[captured_piece] & BITVECTOR(position->piece_position[captured_piece]))) { position->board_vector &= ~BITVECTOR(position->en_passant_square); position->board_vector |= BITVECTOR(position->piece_position[captured_piece]); position->board_vector |= BITVECTOR(movementptr->square); propagate_local_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); position->board_vector |= BITVECTOR(position->en_passant_square); position->board_vector &= ~BITVECTOR(position->piece_position[captured_piece]); position->board_vector &= ~BITVECTOR(movementptr->square); } /* Yes, we're in a for loop and could might this position again, so put things * back where they came from... */ position->en_passant_square = -1; position->piece_position[captured_piece] -= 8; } if ((tb->piece_color[capturing_piece] == WHITE) && (ROW(movementptr->square) == 4)) { /* A white pawn capturing a black one (en passant) * * The black pawn is actually a rank lower than usual. */ position->en_passant_square = position->piece_position[captured_piece]; position->piece_position[captured_piece] -= 8; if ((tb->piece_legal_squares[captured_piece] & BITVECTOR(position->piece_position[captured_piece]))) { position->board_vector &= ~BITVECTOR(position->en_passant_square); position->board_vector |= BITVECTOR(position->piece_position[captured_piece]); position->board_vector |= BITVECTOR(movementptr->square); propagate_local_position_from_futurebase(tb, futurebase, future_index, position, mate_in_limit); position->board_vector |= BITVECTOR(position->en_passant_square); position->board_vector &= ~BITVECTOR(position->piece_position[captured_piece]); position->board_vector &= ~BITVECTOR(movementptr->square); } /* Yes, we're in a for loop and could might this position again, so put things * back where they came from... */ position->en_passant_square = -1; position->piece_position[captured_piece] += 8; } } } } /* Put the capturing piece back where it came from (on the capture square) so that we can use * this local position again (on another call to this function) to consider other potential * capturing pieces without having to copy or recreate the entire local position structure. */ position->piece_position[capturing_piece] = position->piece_position[captured_piece]; } void propagate_moves_from_mobile_capture_futurebase(tablebase_t *tb, tablebase_t *futurebase, int invert_colors_of_futurebase, int captured_piece, int *mate_in_limit) { int32 future_index; local_position_t current_position; int piece; int32 conversion_result; int extra_piece, restricted_piece, missing_piece1, missing_piece2; for (future_index = 0; future_index <= futurebase->max_index; future_index ++) { /* It's tempting to break out the loop here if the position isn't a win, but if we want to * track futuremoves in order to make sure we don't miss one (probably a good idea), then * the simplest way to do that is to run this loop even for draws. */ /* Take the position from the futurebase and translate it into a local position for the * current tablebase. If the futurebase index was illegal, the function will return -1. * Otherwise, there should be one piece missing from the local position: the piece that was * captured. There could possibly be one piece on a restricted square, as well. If so, * then it must be the piece that moved in order to capture. */ /* XXX If the futurebase is more liberal than the tablebase, then there will be positions * with multiple restricted pieces that should be quietly ignored. */ conversion_result = translate_foreign_index_to_local_position(futurebase, future_index, tb, ¤t_position, invert_colors_of_futurebase); if (conversion_result != -1) { extra_piece = (conversion_result >> 16) & 0xff; restricted_piece = (conversion_result >> 8) & 0xff; missing_piece1 = conversion_result & 0xff; missing_piece2 = (conversion_result >> 24) & 0xff; if ((extra_piece != NONE) || (missing_piece1 != captured_piece) || (missing_piece2 != NONE)) { fprintf(stderr, "Conversion error during capture back-prop\n"); /* BREAKPOINT */ continue; } /* Since the last move had to have been a capture move, there is absolutely no way we * could have en passant capturable pawns in the futurebase position. */ if (current_position.en_passant_square != -1) continue; /* Since the position resulted from a capture, we only want to consider future positions * where the side to move is not the side that captured. */ if (current_position.side_to_move != tb->piece_color[captured_piece]) continue; /* We're going to back step a half move now */ flip_side_to_move_local(¤t_position); if (restricted_piece == NONE) { /* No pieces were on restricted squares. Check them all. */ for (piece = 0; piece < tb->num_mobiles; piece++) { consider_possible_captures(tb, futurebase, future_index, ¤t_position, piece, captured_piece, mate_in_limit); } } else { /* One piece was on a restricted square. It's the only possible capturing piece. */ consider_possible_captures(tb, futurebase, future_index, ¤t_position, restricted_piece, captured_piece, mate_in_limit); } } } } /* A "normal" futurebase is one that's identical to our own in terms of the number and types * of pieces. It differs only in the frozen positions of the pieces. */ void propagate_moves_from_normal_futurebase(tablebase_t *tb, tablebase_t *futurebase, int invert_colors_of_futurebase, int *mate_in_limit) { int32 future_index; local_position_t parent_position; local_position_t current_position; /* i.e, last position that moved to parent_position */ int32 conversion_result; int extra_piece, restricted_piece, missing_piece1, missing_piece2; int piece; int dir; struct movement *movementptr; for (future_index = 0; future_index <= futurebase->max_index; future_index ++) { /* Translate the futurebase index into a local position. We have exactly the same number * and type of pieces here, but exactly one of them is on a restricted square (according to * the current tablebase). If more than one of them was on a restricted square, then * there'd be no way we could get to this futurebase with a single move. On the other hand, * if none of them were on restricted squares, then this would be a position in the current * tablebase. */ /* XXX If the futurebase is more liberal than the tablebase, then there will be positions * with multiple restricted pieces that should be quietly ignored. */ conversion_result = translate_foreign_index_to_local_position(futurebase, future_index, tb, ¤t_position, invert_colors_of_futurebase); if (conversion_result != -1) { extra_piece = (conversion_result >> 16) & 0xff; restricted_piece = (conversion_result >> 8) & 0xff; missing_piece1 = conversion_result & 0xff; missing_piece2 = (conversion_result >> 24) & 0xff; if ((missing_piece1 != NONE) || (extra_piece != NONE) || (restricted_piece == NONE)) { fprintf(stderr, "Conversion error during normal back-prop\n"); /* BREAKPOINT */ continue; } piece = restricted_piece; /* We've moving BACKWARDS in the game, so this has to be a piece of the player who is * NOT TO PLAY here - this is the LAST move we're considering, not the next move. */ if (tb->piece_color[piece] == current_position.side_to_move) continue; /* If there are any en passant capturable pawns in the position, then the last move had * to have been a pawn move. In fact, in this case, we already know exactly what the * last move had to have been. */ if (current_position.en_passant_square != -1) { if (tb->piece_type[piece] != PAWN) continue; if (((tb->piece_color[piece] == WHITE) && (current_position.piece_position[piece] != current_position.en_passant_square + 8)) || ((tb->piece_color[piece] == BLACK) && (current_position.piece_position[piece] != current_position.en_passant_square - 8))) { /* No reason to complain here. Maybe some other pawn was the en passant pawn. */ continue; } flip_side_to_move_local(¤t_position); current_position.en_passant_square = -1; /* I go to the trouble to update board_vector here so we can check en passant * legality in propagate_one_move_within_table(). */ current_position.board_vector &= ~BITVECTOR(current_position.piece_position[piece]); if (tb->piece_color[piece] == WHITE) current_position.piece_position[piece] -= 16; else current_position.piece_position[piece] += 16; current_position.board_vector |= BITVECTOR(current_position.piece_position[piece]); /* We never back out into a restricted position. Since we've already decided * that this is the only legal back-move from this point, well... */ if (! (tb->piece_legal_squares[piece] & BITVECTOR(current_position.piece_position[piece]))) { continue; } propagate_local_position_from_futurebase(tb, futurebase, future_index, ¤t_position, mate_in_limit); continue; } /* Abuse of notation here. We just want to keep a copy of current_position because we * change it around a lot during the loops below. */ parent_position = current_position; if (tb->piece_type[piece] != PAWN) { for (dir = 0; dir < number_of_movement_directions[tb->piece_type[piece]]; dir++) { /* What about captures? Well, first of all, there are no captures here! We're * moving BACKWARDS in the game... and pieces don't appear out of thin air. * Captures are handled by back-propagation from futurebases, not here in the * movement code. The piece moving had to come from somewhere, and that * somewhere will now be an empty square, so once we've hit another piece along * a movement vector, there's absolutely no need to consider anything further. */ for (movementptr = movements[tb->piece_type[piece]][parent_position.piece_position[piece]][dir]; (movementptr->vector & parent_position.board_vector) == 0; movementptr++) { /* We never back out into a restricted position (obviously) */ if (! (tb->piece_legal_squares[piece] & movementptr->vector)) continue; /* Back stepping a half move here involves several things: flipping the * side-to-move flag, clearing any en passant pawns into regular pawns, moving * the piece (backwards), and considering a bunch of additional positions * identical to the base position except that a single one of the pawns on the * fourth or fifth ranks was capturable en passant. * * Of course, the only way we could have gotten an en passant pawn is if THIS * MOVE created it. Since this isn't a pawn move, that can't happen. Checking * additional en passant positions is taken care of in * propagate_one_move_within_table() */ flip_side_to_move_local(¤t_position); /* I go to the trouble to update board_vector here so we can check en passant * legality in propagate_one_move_within_table(). */ current_position.board_vector &= ~BITVECTOR(current_position.piece_position[piece]); current_position.piece_position[piece] = movementptr->square; current_position.board_vector |= BITVECTOR(movementptr->square); propagate_local_position_from_futurebase(tb, futurebase, future_index, ¤t_position, mate_in_limit); } } } else { /* Usual special case for pawns */ for (movementptr = normal_pawn_movements_bkwd[parent_position.piece_position[piece]][tb->piece_color[piece]]; (movementptr->vector & parent_position.board_vector) == 0; movementptr++) { /* We never back out into a restricted position (obviously) */ if (! (tb->piece_legal_squares[piece] & movementptr->vector)) continue; /* Do we have a backwards pawn move here? * * Back stepping a half move here involves several things: flipping the * side-to-move flag, clearing any en passant pawns into regular pawns, moving * the piece (backwards), and considering a bunch of additional positions * identical to the base position except that a single one of the pawns on the * fourth or fifth ranks was capturable en passant. * * Of course, the only way we could have gotten an en passant pawn is if THIS MOVE * created it. We handle that as a special case above, so we shouldn't have to * worry about clearing en passant pawns here - there should be none. Checking * additional en passant positions is taken care of in * propagate_one_move_within_table() * * But we start with an extra check to make sure this isn't a double pawn move, it * which case it would result in an en passant position, not the non-en passant * position we are in now (en passant got taken care of in the special case above). */ if (((movementptr->square - parent_position.piece_position[piece]) == 16) || ((movementptr->square - parent_position.piece_position[piece]) == -16)) { continue; } current_position = parent_position; flip_side_to_move_local(¤t_position); /* I go to the trouble to update board_vector here so we can check en passant * legality in propagate_one_move_within_table(). */ current_position.board_vector &= ~BITVECTOR(current_position.piece_position[piece]); current_position.piece_position[piece] = movementptr->square; current_position.board_vector |= BITVECTOR(current_position.piece_position[piece]); propagate_local_position_from_futurebase(tb, futurebase, future_index, ¤t_position, mate_in_limit); } } } } } /* Back propagates from all the futurebases. * * Should be called after the tablebase has been initialized, but before intra-table propagation. * * Runs through the parsed XML control file, pulls out all the futurebases, and back-propagates each * one. * * Returns maximum mate_in value, or -1 if something went wrong */ int back_propagate_all_futurebases(tablebase_t *tb) { xmlXPathContextPtr context; xmlXPathObjectPtr result; int mate_in_limit = 0; /* Fetch the futurebases from the XML */ context = xmlXPathNewContext(tb->xml); result = xmlXPathEvalExpression((const xmlChar *) "//futurebase", context); if ((tb->num_mobiles > 2) && xmlXPathNodeSetIsEmpty(result->nodesetval)) { fprintf(stderr, "No futurebases!\n"); } else { int i; for (i=0; i < result->nodesetval->nodeNr; i++) { xmlChar * filename; xmlChar * colors_property; xmlChar * type; tablebase_t * futurebase; int invert_colors = 0; int future_piece; int piece; int color; int piece_vector; int pawn; int promoted_piece = -1; unsigned char captured_piece_char; unsigned char promoted_piece_char; filename = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "filename"); colors_property = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "colors"); if (colors_property != NULL) { if (!strcasecmp((char *) colors_property, "invert")) invert_colors = 1; xmlFree(colors_property); } futurebase = load_futurebase_from_file((char *) filename); /* load_futurebase_from_file() already printed some kind of error message */ if (futurebase == NULL) return -1; /* Check futurebase to make sure its move restriction(s) match our own */ for (color = 0; color < 2; color ++) { if ((futurebase->move_restrictions[color] != RESTRICTION_NONE) && (futurebase->move_restrictions[color] != tb->move_restrictions[invert_colors ? 1 - color : color])) { fprintf(stderr, "'%s': Futurebase doesn't match move restrictions!\n", filename); return -1; } } type = xmlGetProp(result->nodesetval->nodeTab[i], (const xmlChar *) "type"); if ((type != NULL) && !strcasecmp((char *) type, "capture")) { /* It's a capture futurebase. Futurebase should have exactly one less mobile than * the current tablebase. Find it. */ /* piece_vector - set a bit for every mobile piece in current tablebase */ piece_vector = (1 << tb->num_mobiles) - 1; for (future_piece = 0; future_piece < futurebase->num_mobiles; future_piece ++) { for (piece = 0; piece < tb->num_mobiles; piece ++) { if (! (piece_vector & (1 << piece))) continue; if ((tb->piece_type[piece] == futurebase->piece_type[future_piece]) && ((!invert_colors && (tb->piece_color[piece] == futurebase->piece_color[future_piece