board.c

Go to the documentation of this file.

 
#include "board.h"
 
#include "bit.h"
#include "hash.h"
#include "move.h"
#include "settings.h"
#include "util.h"
 
#include <ctype.h>
#include <stdlib.h>
#include <assert.h>
 
 
#if MOVE_GENERATOR == MOVE_GENERATOR_CARRY
        #ifdef HAS_CPU_64
                #include "flip_carry_64.c"
                #include "count_last_flip_carry_64.c"
        #else 
                #include "flip_carry_32.c"
                #include "count_last_flip_carry_32.c"
        #endif
#elif MOVE_GENERATOR == MOVE_GENERATOR_SSE
        #include "flip_sse.c"
        #include "count_last_flip_kindergarten.c"
#elif MOVE_GENERATOR == MOVE_GENERATOR_BITSCAN
        #include "flip_bitscan.c"
        #include "count_last_flip_bitscan.c"
#elif MOVE_GENERATOR == MOVE_GENERATOR_ROXANE
        #include "flip_roxane.c"
        #include "count_last_flip_kindergarten.c"
#else // MOVE_GENERATOR == MOVE_GENERATOR_KINDERGARTEN
        #include "flip_kindergarten.c"
        #include "count_last_flip_kindergarten.c"
#endif
 
 
static unsigned char edge_stability[256][256];
 
static const unsigned long long A1_A8[256] = {
        0x0000000000000000ULL, 0x0000000000000001ULL, 0x0000000000000100ULL, 0x0000000000000101ULL, 0x0000000000010000ULL, 0x0000000000010001ULL, 0x0000000000010100ULL, 0x0000000000010101ULL,
        0x0000000001000000ULL, 0x0000000001000001ULL, 0x0000000001000100ULL, 0x0000000001000101ULL, 0x0000000001010000ULL, 0x0000000001010001ULL, 0x0000000001010100ULL, 0x0000000001010101ULL,
        0x0000000100000000ULL, 0x0000000100000001ULL, 0x0000000100000100ULL, 0x0000000100000101ULL, 0x0000000100010000ULL, 0x0000000100010001ULL, 0x0000000100010100ULL, 0x0000000100010101ULL,
        0x0000000101000000ULL, 0x0000000101000001ULL, 0x0000000101000100ULL, 0x0000000101000101ULL, 0x0000000101010000ULL, 0x0000000101010001ULL, 0x0000000101010100ULL, 0x0000000101010101ULL,
        0x0000010000000000ULL, 0x0000010000000001ULL, 0x0000010000000100ULL, 0x0000010000000101ULL, 0x0000010000010000ULL, 0x0000010000010001ULL, 0x0000010000010100ULL, 0x0000010000010101ULL,
        0x0000010001000000ULL, 0x0000010001000001ULL, 0x0000010001000100ULL, 0x0000010001000101ULL, 0x0000010001010000ULL, 0x0000010001010001ULL, 0x0000010001010100ULL, 0x0000010001010101ULL,
        0x0000010100000000ULL, 0x0000010100000001ULL, 0x0000010100000100ULL, 0x0000010100000101ULL, 0x0000010100010000ULL, 0x0000010100010001ULL, 0x0000010100010100ULL, 0x0000010100010101ULL,
        0x0000010101000000ULL, 0x0000010101000001ULL, 0x0000010101000100ULL, 0x0000010101000101ULL, 0x0000010101010000ULL, 0x0000010101010001ULL, 0x0000010101010100ULL, 0x0000010101010101ULL,
        0x0001000000000000ULL, 0x0001000000000001ULL, 0x0001000000000100ULL, 0x0001000000000101ULL, 0x0001000000010000ULL, 0x0001000000010001ULL, 0x0001000000010100ULL, 0x0001000000010101ULL,
        0x0001000001000000ULL, 0x0001000001000001ULL, 0x0001000001000100ULL, 0x0001000001000101ULL, 0x0001000001010000ULL, 0x0001000001010001ULL, 0x0001000001010100ULL, 0x0001000001010101ULL,
        0x0001000100000000ULL, 0x0001000100000001ULL, 0x0001000100000100ULL, 0x0001000100000101ULL, 0x0001000100010000ULL, 0x0001000100010001ULL, 0x0001000100010100ULL, 0x0001000100010101ULL,
        0x0001000101000000ULL, 0x0001000101000001ULL, 0x0001000101000100ULL, 0x0001000101000101ULL, 0x0001000101010000ULL, 0x0001000101010001ULL, 0x0001000101010100ULL, 0x0001000101010101ULL,
        0x0001010000000000ULL, 0x0001010000000001ULL, 0x0001010000000100ULL, 0x0001010000000101ULL, 0x0001010000010000ULL, 0x0001010000010001ULL, 0x0001010000010100ULL, 0x0001010000010101ULL,
        0x0001010001000000ULL, 0x0001010001000001ULL, 0x0001010001000100ULL, 0x0001010001000101ULL, 0x0001010001010000ULL, 0x0001010001010001ULL, 0x0001010001010100ULL, 0x0001010001010101ULL,
        0x0001010100000000ULL, 0x0001010100000001ULL, 0x0001010100000100ULL, 0x0001010100000101ULL, 0x0001010100010000ULL, 0x0001010100010001ULL, 0x0001010100010100ULL, 0x0001010100010101ULL,
        0x0001010101000000ULL, 0x0001010101000001ULL, 0x0001010101000100ULL, 0x0001010101000101ULL, 0x0001010101010000ULL, 0x0001010101010001ULL, 0x0001010101010100ULL, 0x0001010101010101ULL,
        0x0100000000000000ULL, 0x0100000000000001ULL, 0x0100000000000100ULL, 0x0100000000000101ULL, 0x0100000000010000ULL, 0x0100000000010001ULL, 0x0100000000010100ULL, 0x0100000000010101ULL,
        0x0100000001000000ULL, 0x0100000001000001ULL, 0x0100000001000100ULL, 0x0100000001000101ULL, 0x0100000001010000ULL, 0x0100000001010001ULL, 0x0100000001010100ULL, 0x0100000001010101ULL,
        0x0100000100000000ULL, 0x0100000100000001ULL, 0x0100000100000100ULL, 0x0100000100000101ULL, 0x0100000100010000ULL, 0x0100000100010001ULL, 0x0100000100010100ULL, 0x0100000100010101ULL,
        0x0100000101000000ULL, 0x0100000101000001ULL, 0x0100000101000100ULL, 0x0100000101000101ULL, 0x0100000101010000ULL, 0x0100000101010001ULL, 0x0100000101010100ULL, 0x0100000101010101ULL,
        0x0100010000000000ULL, 0x0100010000000001ULL, 0x0100010000000100ULL, 0x0100010000000101ULL, 0x0100010000010000ULL, 0x0100010000010001ULL, 0x0100010000010100ULL, 0x0100010000010101ULL,
        0x0100010001000000ULL, 0x0100010001000001ULL, 0x0100010001000100ULL, 0x0100010001000101ULL, 0x0100010001010000ULL, 0x0100010001010001ULL, 0x0100010001010100ULL, 0x0100010001010101ULL,
        0x0100010100000000ULL, 0x0100010100000001ULL, 0x0100010100000100ULL, 0x0100010100000101ULL, 0x0100010100010000ULL, 0x0100010100010001ULL, 0x0100010100010100ULL, 0x0100010100010101ULL,
        0x0100010101000000ULL, 0x0100010101000001ULL, 0x0100010101000100ULL, 0x0100010101000101ULL, 0x0100010101010000ULL, 0x0100010101010001ULL, 0x0100010101010100ULL, 0x0100010101010101ULL,
        0x0101000000000000ULL, 0x0101000000000001ULL, 0x0101000000000100ULL, 0x0101000000000101ULL, 0x0101000000010000ULL, 0x0101000000010001ULL, 0x0101000000010100ULL, 0x0101000000010101ULL,
        0x0101000001000000ULL, 0x0101000001000001ULL, 0x0101000001000100ULL, 0x0101000001000101ULL, 0x0101000001010000ULL, 0x0101000001010001ULL, 0x0101000001010100ULL, 0x0101000001010101ULL,
        0x0101000100000000ULL, 0x0101000100000001ULL, 0x0101000100000100ULL, 0x0101000100000101ULL, 0x0101000100010000ULL, 0x0101000100010001ULL, 0x0101000100010100ULL, 0x0101000100010101ULL,
        0x0101000101000000ULL, 0x0101000101000001ULL, 0x0101000101000100ULL, 0x0101000101000101ULL, 0x0101000101010000ULL, 0x0101000101010001ULL, 0x0101000101010100ULL, 0x0101000101010101ULL,
        0x0101010000000000ULL, 0x0101010000000001ULL, 0x0101010000000100ULL, 0x0101010000000101ULL, 0x0101010000010000ULL, 0x0101010000010001ULL, 0x0101010000010100ULL, 0x0101010000010101ULL,
        0x0101010001000000ULL, 0x0101010001000001ULL, 0x0101010001000100ULL, 0x0101010001000101ULL, 0x0101010001010000ULL, 0x0101010001010001ULL, 0x0101010001010100ULL, 0x0101010001010101ULL,
        0x0101010100000000ULL, 0x0101010100000001ULL, 0x0101010100000100ULL, 0x0101010100000101ULL, 0x0101010100010000ULL, 0x0101010100010001ULL, 0x0101010100010100ULL, 0x0101010100010101ULL,
        0x0101010101000000ULL, 0x0101010101000001ULL, 0x0101010101000100ULL, 0x0101010101000101ULL, 0x0101010101010000ULL, 0x0101010101010001ULL, 0x0101010101010100ULL, 0x0101010101010101ULL,
};
 
static const unsigned long long H1_H8[256] = {
        0x0000000000000000ULL, 0x0000000000000080ULL, 0x0000000000008000ULL, 0x0000000000008080ULL, 0x0000000000800000ULL, 0x0000000000800080ULL, 0x0000000000808000ULL, 0x0000000000808080ULL,
        0x0000000080000000ULL, 0x0000000080000080ULL, 0x0000000080008000ULL, 0x0000000080008080ULL, 0x0000000080800000ULL, 0x0000000080800080ULL, 0x0000000080808000ULL, 0x0000000080808080ULL,
        0x0000008000000000ULL, 0x0000008000000080ULL, 0x0000008000008000ULL, 0x0000008000008080ULL, 0x0000008000800000ULL, 0x0000008000800080ULL, 0x0000008000808000ULL, 0x0000008000808080ULL,
        0x0000008080000000ULL, 0x0000008080000080ULL, 0x0000008080008000ULL, 0x0000008080008080ULL, 0x0000008080800000ULL, 0x0000008080800080ULL, 0x0000008080808000ULL, 0x0000008080808080ULL,
        0x0000800000000000ULL, 0x0000800000000080ULL, 0x0000800000008000ULL, 0x0000800000008080ULL, 0x0000800000800000ULL, 0x0000800000800080ULL, 0x0000800000808000ULL, 0x0000800000808080ULL,
        0x0000800080000000ULL, 0x0000800080000080ULL, 0x0000800080008000ULL, 0x0000800080008080ULL, 0x0000800080800000ULL, 0x0000800080800080ULL, 0x0000800080808000ULL, 0x0000800080808080ULL,
        0x0000808000000000ULL, 0x0000808000000080ULL, 0x0000808000008000ULL, 0x0000808000008080ULL, 0x0000808000800000ULL, 0x0000808000800080ULL, 0x0000808000808000ULL, 0x0000808000808080ULL,
        0x0000808080000000ULL, 0x0000808080000080ULL, 0x0000808080008000ULL, 0x0000808080008080ULL, 0x0000808080800000ULL, 0x0000808080800080ULL, 0x0000808080808000ULL, 0x0000808080808080ULL,
        0x0080000000000000ULL, 0x0080000000000080ULL, 0x0080000000008000ULL, 0x0080000000008080ULL, 0x0080000000800000ULL, 0x0080000000800080ULL, 0x0080000000808000ULL, 0x0080000000808080ULL,
        0x0080000080000000ULL, 0x0080000080000080ULL, 0x0080000080008000ULL, 0x0080000080008080ULL, 0x0080000080800000ULL, 0x0080000080800080ULL, 0x0080000080808000ULL, 0x0080000080808080ULL,
        0x0080008000000000ULL, 0x0080008000000080ULL, 0x0080008000008000ULL, 0x0080008000008080ULL, 0x0080008000800000ULL, 0x0080008000800080ULL, 0x0080008000808000ULL, 0x0080008000808080ULL,
        0x0080008080000000ULL, 0x0080008080000080ULL, 0x0080008080008000ULL, 0x0080008080008080ULL, 0x0080008080800000ULL, 0x0080008080800080ULL, 0x0080008080808000ULL, 0x0080008080808080ULL,
        0x0080800000000000ULL, 0x0080800000000080ULL, 0x0080800000008000ULL, 0x0080800000008080ULL, 0x0080800000800000ULL, 0x0080800000800080ULL, 0x0080800000808000ULL, 0x0080800000808080ULL,
        0x0080800080000000ULL, 0x0080800080000080ULL, 0x0080800080008000ULL, 0x0080800080008080ULL, 0x0080800080800000ULL, 0x0080800080800080ULL, 0x0080800080808000ULL, 0x0080800080808080ULL,
        0x0080808000000000ULL, 0x0080808000000080ULL, 0x0080808000008000ULL, 0x0080808000008080ULL, 0x0080808000800000ULL, 0x0080808000800080ULL, 0x0080808000808000ULL, 0x0080808000808080ULL,
        0x0080808080000000ULL, 0x0080808080000080ULL, 0x0080808080008000ULL, 0x0080808080008080ULL, 0x0080808080800000ULL, 0x0080808080800080ULL, 0x0080808080808000ULL, 0x0080808080808080ULL,
        0x8000000000000000ULL, 0x8000000000000080ULL, 0x8000000000008000ULL, 0x8000000000008080ULL, 0x8000000000800000ULL, 0x8000000000800080ULL, 0x8000000000808000ULL, 0x8000000000808080ULL,
        0x8000000080000000ULL, 0x8000000080000080ULL, 0x8000000080008000ULL, 0x8000000080008080ULL, 0x8000000080800000ULL, 0x8000000080800080ULL, 0x8000000080808000ULL, 0x8000000080808080ULL,
        0x8000008000000000ULL, 0x8000008000000080ULL, 0x8000008000008000ULL, 0x8000008000008080ULL, 0x8000008000800000ULL, 0x8000008000800080ULL, 0x8000008000808000ULL, 0x8000008000808080ULL,
        0x8000008080000000ULL, 0x8000008080000080ULL, 0x8000008080008000ULL, 0x8000008080008080ULL, 0x8000008080800000ULL, 0x8000008080800080ULL, 0x8000008080808000ULL, 0x8000008080808080ULL,
        0x8000800000000000ULL, 0x8000800000000080ULL, 0x8000800000008000ULL, 0x8000800000008080ULL, 0x8000800000800000ULL, 0x8000800000800080ULL, 0x8000800000808000ULL, 0x8000800000808080ULL,
        0x8000800080000000ULL, 0x8000800080000080ULL, 0x8000800080008000ULL, 0x8000800080008080ULL, 0x8000800080800000ULL, 0x8000800080800080ULL, 0x8000800080808000ULL, 0x8000800080808080ULL,
        0x8000808000000000ULL, 0x8000808000000080ULL, 0x8000808000008000ULL, 0x8000808000008080ULL, 0x8000808000800000ULL, 0x8000808000800080ULL, 0x8000808000808000ULL, 0x8000808000808080ULL,
        0x8000808080000000ULL, 0x8000808080000080ULL, 0x8000808080008000ULL, 0x8000808080008080ULL, 0x8000808080800000ULL, 0x8000808080800080ULL, 0x8000808080808000ULL, 0x8000808080808080ULL,
        0x8080000000000000ULL, 0x8080000000000080ULL, 0x8080000000008000ULL, 0x8080000000008080ULL, 0x8080000000800000ULL, 0x8080000000800080ULL, 0x8080000000808000ULL, 0x8080000000808080ULL,
        0x8080000080000000ULL, 0x8080000080000080ULL, 0x8080000080008000ULL, 0x8080000080008080ULL, 0x8080000080800000ULL, 0x8080000080800080ULL, 0x8080000080808000ULL, 0x8080000080808080ULL,
        0x8080008000000000ULL, 0x8080008000000080ULL, 0x8080008000008000ULL, 0x8080008000008080ULL, 0x8080008000800000ULL, 0x8080008000800080ULL, 0x8080008000808000ULL, 0x8080008000808080ULL,
        0x8080008080000000ULL, 0x8080008080000080ULL, 0x8080008080008000ULL, 0x8080008080008080ULL, 0x8080008080800000ULL, 0x8080008080800080ULL, 0x8080008080808000ULL, 0x8080008080808080ULL,
        0x8080800000000000ULL, 0x8080800000000080ULL, 0x8080800000008000ULL, 0x8080800000008080ULL, 0x8080800000800000ULL, 0x8080800000800080ULL, 0x8080800000808000ULL, 0x8080800000808080ULL,
        0x8080800080000000ULL, 0x8080800080000080ULL, 0x8080800080008000ULL, 0x8080800080008080ULL, 0x8080800080800000ULL, 0x8080800080800080ULL, 0x8080800080808000ULL, 0x8080800080808080ULL,
        0x8080808000000000ULL, 0x8080808000000080ULL, 0x8080808000008000ULL, 0x8080808000008080ULL, 0x8080808000800000ULL, 0x8080808000800080ULL, 0x8080808000808000ULL, 0x8080808000808080ULL,
        0x8080808080000000ULL, 0x8080808080000080ULL, 0x8080808080008000ULL, 0x8080808080008080ULL, 0x8080808080800000ULL, 0x8080808080800080ULL, 0x8080808080808000ULL, 0x8080808080808080ULL,
};
 
void board_swap_players(Board *board)
{
        const unsigned long long tmp = board->player;
        board->player = board->opponent;
        board->opponent = tmp;
}
 
int board_set(Board *board, const char *string)
{
        int i;
        const char *s = string;
 
        board->player = board->opponent = 0;
        for (i = A1; i <= H8; ++i) {
                if (*s == '\0') break;
                switch (tolower(*s)) {
                case 'b':
                case 'x':
                case '*':
                        board->player |= x_to_bit(i);
                        break;
                case 'o':
                case 'w':
                        board->opponent |= x_to_bit(i);
                        break;
                case '-':
                case '.':
                        break;
                default:
                        i--;
                        break;
                }
                ++s;
        }
        board_check(board);
 
        for (;*s != '\0'; ++s) {
                switch (tolower(*s)) {
                case 'b':
                case 'x':
                case '*':
                        return BLACK;
                case 'o':
                case 'w':
                        board_swap_players(board);
                        return WHITE;
                default:
                        break;
                }
        }
 
        warn("board_set: bad string input\n");
        return EMPTY;
}
 
int board_from_FEN(Board *board, const char *string)
{
        int i;
        const char *s;
 
        board->player = board->opponent = 0;
        i = A8;
        for (s = parse_skip_spaces(string); *s && *s != ' '; ++s) {
                if (isdigit(*s)) {
                        i += (*s - '0');
                } else if (*s == '/') {
                        if (i & 7) return EMPTY;
                        i -= 16;
                } else if (*s == 'p') {
                        board->player |= x_to_bit(i);
                        ++i;
                } else if (*s == 'P') {
                        board->opponent |= x_to_bit(i);
                        ++i;
                } else {
                        return EMPTY;   
                }
        }
 
        s = parse_skip_spaces(s);
        if (*s == 'b') {
                return BLACK;
        } else if (*s == 'w') {
                board_swap_players(board);
                return WHITE;
        }
 
        return EMPTY;
}
 
 
int board_from_obj(Board *board, const Board *obj, const int turn)
{
        board->player = obj->player;
        board->opponent = obj->opponent;
        board_check(board);
        switch (turn) {
        case BLACK:
                return BLACK;
        case WHITE:
                board_swap_players(board);
                return WHITE;
        default:
                break;
        }
        return EMPTY;
}
 
void board_init(Board *board)
{
        board->player   = 0x0000000810000000ULL; // BLACK
        board->opponent = 0x0000001008000000ULL; // WHITE
}
 
void board_check(const Board *board)
{
#ifndef NDEBUG
        if (board->player & board->opponent) {
                error("Two discs on the same square?\n");
                board_print(board, BLACK, stderr);
                bitboard_write(board->player, stderr);
                bitboard_write(board->opponent, stderr);
                abort();
        }
 
        // empty center ?
        if (((board->player|board->opponent) & 0x0000001818000000ULL) != 0x0000001818000000ULL) {
                error("Empty center?\n");
                board_print(board, BLACK, stderr);
        }
#else
        (void) board;
#endif // NDEBUG
}
 
int board_compare(const Board *b1, const Board *b2)
{
        if (b1->player > b2->player) return 1;
        else if (b1->player < b2->player) return -1;
        else if (b1->opponent > b2->opponent) return 1;
        else if (b1->opponent < b2->opponent) return -1;
        else return 0;
}
 
bool board_equal(const Board *b1, const Board *b2)
{
        return (b1->player == b2->player && b1->opponent == b2->opponent);
}
 
void board_symetry(const Board *board, const int s, Board *sym)
{
        register unsigned long long player = board->player;
        register unsigned long long opponent = board->opponent;
 
        if (s & 1) {
                player = horizontal_mirror(player);
                opponent = horizontal_mirror(opponent);
        }
        if (s & 2) {
                player = vertical_mirror(player);
                opponent = vertical_mirror(opponent);
        }
        if (s & 4) {
                player = transpose(player);
                opponent = transpose(opponent);
        }
 
        sym->player = player;
        sym->opponent = opponent;
 
        board_check(sym);
}
 
int board_unique(const Board *board, Board *unique)
{
        Board sym;
        int i, s = 0;
 
        assert(board != unique);
 
        *unique = *board;
        for (i = 1; i < 8; ++i) {
                board_symetry(board, i, &sym);
                if (board_compare(&sym, unique) < 0) {
                        *unique = sym;
                        s = i;
                }
        }
 
        board_check(unique);
        return s;
}
 
void board_rand(Board *board, int n_ply, Random *r)
{
        Move move[1];
        unsigned long long moves;
        int ply;
 
        board_init(board);
        for (ply = 0; ply < n_ply; ply++) {
                moves = get_moves(board->player, board->opponent);
                if (!moves) {
                        board_pass(board);
                        moves = get_moves(board->player, board->opponent);
                        if (!moves) {
                                break;
                        }
                }
                board_get_move(board, get_rand_bit(moves, r), move);
                board_update(board, move);
        }
}
 
 
unsigned long long board_get_move(const Board *board, const int x, Move *move)
{
        move->flipped = flip[x](board->player, board->opponent);
        move->x = x;
        return move->flipped;
}
 
bool board_check_move(const Board *board, Move *move)
{
        if (move->x == PASS) return !can_move(board->player, board->opponent);
        else if ((x_to_bit(move->x) & ~(board->player|board->opponent)) == 0) return false;
        else if (move->flipped != flip[move->x](board->player, board->opponent)) return false;
        else return true;
}
 
void board_update(Board *board, const Move *move)
{
        board->player ^= (move->flipped | x_to_bit(move->x));
        board->opponent ^= move->flipped;
        board_swap_players(board);
 
        board_check(board);
}
 
void board_restore(Board *board, const Move *move)
{
        board_swap_players(board);
        board->player ^= (move->flipped | x_to_bit(move->x));
        board->opponent ^= move->flipped;
 
        board_check(board);
}
 
void board_pass(Board *board)
{
        board_swap_players(board);
        board_check(board);
}
 
unsigned long long board_next(const Board *board, const int x, Board *next)
{
        const unsigned long long flipped = flip[x](board->player, board->opponent);
        const unsigned long long player = board->opponent ^ flipped;
 
        next->opponent = board->player ^ (flipped | x_to_bit(x));
        next->player = player;
 
        return flipped;
}
 
unsigned long long board_pass_next(const Board *board, const int x, Board *next)
{
        const unsigned long long flipped = flip[x](board->opponent, board->player);
 
        next->opponent = board->opponent ^ (flipped | x_to_bit(x));
        next->player = board->player ^ flipped;
 
        return flipped;
}
 
static inline unsigned long long get_some_moves(const unsigned long long P, const unsigned long long mask, const int dir)
{
 
#if PARALLEL_PREFIX & 1
        // 1-stage Parallel Prefix (intermediate between kogge stone & sequential) 
        // 6 << + 6 >> + 7 | + 10 &
        register unsigned long long flip_l, flip_r;
        register unsigned long long mask_l, mask_r;
        const int dir2 = dir + dir;
 
        flip_l  = mask & (P << dir);          flip_r  = mask & (P >> dir);
        flip_l |= mask & (flip_l << dir);     flip_r |= mask & (flip_r >> dir);
        mask_l  = mask & (mask << dir);       mask_r  = mask & (mask >> dir);
        flip_l |= mask_l & (flip_l << dir2);  flip_r |= mask_r & (flip_r >> dir2);
        flip_l |= mask_l & (flip_l << dir2);  flip_r |= mask_r & (flip_r >> dir2);
 
        return (flip_l << dir) | (flip_r >> dir);
 
#elif KOGGE_STONE & 1
        // kogge-stone algorithm
        // 6 << + 6 >> + 12 & + 7 |
        // + better instruction independency
        register unsigned long long flip_l, flip_r;
        register unsigned long long mask_l, mask_r;
        const int dir2 = dir << 1;
        const int dir4 = dir << 2;
 
        flip_l  = P | (mask & (P << dir));    flip_r  = P | (mask & (P >> dir));
        mask_l  = mask & (mask << dir);       mask_r  = mask & (mask >> dir);
        flip_l |= mask_l & (flip_l << dir2);  flip_r |= mask_r & (flip_r >> dir2);
        mask_l &= (mask_l << dir2);           mask_r &= (mask_r >> dir2);
        flip_l |= mask_l & (flip_l << dir4);  flip_r |= mask_r & (flip_r >> dir4);
 
        return ((flip_l & mask) << dir) | ((flip_r & mask) >> dir);
        
#else
        // sequential algorithm
        // 7 << + 7 >> + 6 & + 12 |
        register unsigned long long flip;
 
        flip = (((P << dir) | (P >> dir)) & mask);
        flip |= (((flip << dir) | (flip >> dir)) & mask);
        flip |= (((flip << dir) | (flip >> dir)) & mask);
        flip |= (((flip << dir) | (flip >> dir)) & mask);
        flip |= (((flip << dir) | (flip >> dir)) & mask);
        flip |= (((flip << dir) | (flip >> dir)) & mask);
        return (flip << dir) | (flip >> dir);
 
#endif
}
 
DLL_API unsigned long long get_moves(const unsigned long long P, const unsigned long long O)
{
#if defined(USE_GAS_MMX)
                        /* mm7: P, mm6: O */
        const unsigned long long mask_7e = 0x7e7e7e7e7e7e7e7eULL;
 
  __asm__ volatile(
        "movl   %3, %%esi\n\t"          "movq   %1, %%mm7\n\t"
        "movl   %4, %%edi\n\t"          "movq   %2, %%mm6\n\t"
                        /* shift=+1 */                  /* shift=+8 */
        "movl   %%esi, %%eax\n\t"       "movq   %%mm7, %%mm0\n\t"
        "movq   %5, %%mm5\n\t"
        "shrl   $1, %%eax\n\t"          "psrlq  $8, %%mm0\n\t"
        "andl   $2122219134, %%edi\n\t" "pand   %%mm6, %%mm5\n\t"
        "andl   %%edi, %%eax\n\t"       "pand   %%mm6, %%mm0\n\t"       /* 0 m7&o6 m6&o5 .. m1&o0 */
        "movl   %%eax, %%edx\n\t"       "movq   %%mm0, %%mm1\n\t"
        "shrl   $1, %%eax\n\t"          "psrlq  $8, %%mm0\n\t"
        "movl   %%edi, %%ecx\n\t"       "movq   %%mm6, %%mm3\n\t"
        "andl   %%edi, %%eax\n\t"       "pand   %%mm6, %%mm0\n\t"       /* 0 0 m7&o6&o5 .. m2&o1&o0 */
        "shrl   $1, %%ecx\n\t"          "psrlq  $8, %%mm3\n\t"
        "orl    %%edx, %%eax\n\t"       "por    %%mm1, %%mm0\n\t"       /* 0 m7&o6 (m6&o5)|(m7&o6&o5) .. (m1&o0) */
        "andl   %%edi, %%ecx\n\t"       "pand   %%mm6, %%mm3\n\t"       /* 0 o7&o6 o6&o5 o5&o4 o4&o3 .. */
        "movl   %%eax, %%edx\n\t"       "movq   %%mm0, %%mm4\n\t"
        "shrl   $2, %%eax\n\t"          "psrlq  $16, %%mm0\n\t"
        "andl   %%ecx, %%eax\n\t"       "pand   %%mm3, %%mm0\n\t"       /* 0 0 0 m7&o6&o5&o4 (m6&o5&o4&o3)|(m7&o6&o5&o4&o3) .. */
        "orl    %%eax, %%edx\n\t"       "por    %%mm0, %%mm4\n\t"
        "shrl   $2, %%eax\n\t"          "psrlq  $16, %%mm0\n\t"
        "andl   %%ecx, %%eax\n\t"       "pand   %%mm3, %%mm0\n\t"       /* 0 0 0 0 0 m7&o6&..&o2 (m6&o5&..&o1)|(m7&o6&..&o1) .. */
        "orl    %%edx, %%eax\n\t"       "por    %%mm0, %%mm4\n\t"
        "shrl   $1, %%eax\n\t"          "psrlq  $8, %%mm4\n\t"          /* result of +8 */
        /* shift=-1 */                          /* shift=-8 */
        "movq   %%mm7, %%mm0\n\t"
        "addl   %%esi, %%esi\n\t"       "psllq  $8, %%mm0\n\t"
        "andl   %%edi, %%esi\n\t"       "pand   %%mm6, %%mm0\n\t"
        "movl   %%esi, %%edx\n\t"       "movq   %%mm0, %%mm1\n\t"
        "addl   %%esi, %%esi\n\t"       "psllq  $8, %%mm0\n\t"
        "andl   %%edi, %%esi\n\t"       "pand   %%mm6, %%mm0\n\t"
        "orl    %%esi, %%edx\n\t"       "por    %%mm1, %%mm0\n\t"
        "addl   %%ecx, %%ecx\n\t"       "psllq  $8, %%mm3\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "leal   (,%%edx,4), %%esi\n\t"  "psllq  $16, %%mm0\n\t"
        "andl   %%ecx, %%esi\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%esi, %%edx\n\t"       "por    %%mm0, %%mm1\n\t"
        "shll   $2, %%esi\n\t"          "psllq  $16, %%mm0\n\t"
        "andl   %%ecx, %%esi\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%edx, %%esi\n\t"       "por    %%mm1, %%mm0\n\t"
        "addl   %%esi, %%esi\n\t"       "psllq  $8, %%mm0\n\t"
        "orl    %%eax, %%esi\n\t"       "por    %%mm0, %%mm4\n\t"
        /* Serialize */                         /* shift=+7 */
        "movq   %%mm7, %%mm0\n\t"
        "movd   %%esi, %%mm1\n\t"
        "psrlq  $7, %%mm0\n\t"
        "psllq  $32, %%mm1\n\t"
        "pand   %%mm5, %%mm0\n\t"
        "por    %%mm1, %%mm4\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "psrlq  $7, %%mm0\n\t"
        "pand   %%mm5, %%mm0\n\t"
        "movq   %%mm5, %%mm3\n\t"
        "por    %%mm1, %%mm0\n\t"
        "psrlq  $7, %%mm3\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "pand   %%mm5, %%mm3\n\t"
        "psrlq  $14, %%mm0\n\t"
        "pand   %%mm3, %%mm0\n\t"
        "movl   %1, %%esi\n\t"          "por    %%mm0, %%mm1\n\t"
        "movl   %2, %%edi\n\t"          "psrlq  $14, %%mm0\n\t"
        "andl   $2122219134, %%edi\n\t" "pand   %%mm3, %%mm0\n\t"
        "movl   %%edi, %%ecx\n\t"       "por    %%mm1, %%mm0\n\t"
        "shrl   $1, %%ecx\n\t"          "psrlq  $7, %%mm0\n\t"
        "andl   %%edi, %%ecx\n\t"       "por    %%mm0, %%mm4\n\t"
                        /* shift=+1 */                  /* shift=-7 */
        "movl   %%esi, %%eax\n\t"       "movq   %%mm7, %%mm0\n\t"
        "shrl   $1, %%eax\n\t"          "psllq  $7, %%mm0\n\t"
        "andl   %%edi, %%eax\n\t"       "pand   %%mm5, %%mm0\n\t"
        "movl   %%eax, %%edx\n\t"       "movq   %%mm0, %%mm1\n\t"
        "shrl   $1, %%eax\n\t"          "psllq  $7, %%mm0\n\t"
        "andl   %%edi, %%eax\n\t"       "pand   %%mm5, %%mm0\n\t"
        "orl    %%edx, %%eax\n\t"       "por    %%mm1, %%mm0\n\t"
                                        "psllq  $7, %%mm3\n\t"
        "movl   %%eax, %%edx\n\t"       "movq   %%mm0, %%mm1\n\t"
        "shrl   $2, %%eax\n\t"          "psllq  $14, %%mm0\n\t"
        "andl   %%ecx, %%eax\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%eax, %%edx\n\t"       "por    %%mm0, %%mm1\n\t"
        "shrl   $2, %%eax\n\t"          "psllq  $14, %%mm0\n\t"
        "andl   %%ecx, %%eax\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%edx, %%eax\n\t"       "por    %%mm1, %%mm0\n\t"
        "shrl   $1, %%eax\n\t"          "psllq  $7, %%mm0\n\t"
        "por    %%mm0, %%mm4\n\t"
        /* shift=-1 */                  /* shift=+9 */
        "movq   %%mm7, %%mm0\n\t"
        "addl   %%esi, %%esi\n\t"       "psrlq  $9, %%mm0\n\t"
        "andl   %%edi, %%esi\n\t"       "pand   %%mm5, %%mm0\n\t"
        "movl   %%esi, %%edx\n\t"       "movq   %%mm0, %%mm1\n\t"
        "addl   %%esi, %%esi\n\t"       "psrlq  $9, %%mm0\n\t"
        "andl   %%edi, %%esi\n\t"       "pand   %%mm5, %%mm0\n\t"
        "movq   %%mm5, %%mm3\n\t"
        "orl    %%esi, %%edx\n\t"       "por    %%mm1, %%mm0\n\t"
        "psrlq  $9, %%mm3\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "addl   %%ecx, %%ecx\n\t"       "pand   %%mm5, %%mm3\n\t"
        "leal   (,%%edx,4), %%esi\n\t"  "psrlq  $18, %%mm0\n\t"
        "andl   %%ecx, %%esi\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%esi, %%edx\n\t"       "por    %%mm0, %%mm1\n\t"
        "shll   $2, %%esi\n\t"          "psrlq  $18, %%mm0\n\t"
        "andl   %%ecx, %%esi\n\t"       "pand   %%mm3, %%mm0\n\t"
        "orl    %%edx, %%esi\n\t"       "por    %%mm1, %%mm0\n\t"
        "addl   %%esi, %%esi\n\t"       "psrlq  $9, %%mm0\n\t"
        "orl    %%eax, %%esi\n\t"       "por    %%mm0, %%mm4\n\t"
        /* Serialize */                 /* shift=-9 */
        "movq   %%mm7, %%mm0\n\t"
        "movd   %%esi, %%mm1\n\t"
        "psllq  $9, %%mm0\n\t"
        "por    %%mm1, %%mm4\n\t"
        "pand   %%mm5, %%mm0\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "psllq  $9, %%mm0\n\t"
        "pand   %%mm5, %%mm0\n\t"
        "por    %%mm1, %%mm0\n\t"
        "psllq  $9, %%mm3\n\t"
        "movq   %%mm0, %%mm1\n\t"
        "psllq  $18, %%mm0\n\t"
        "pand   %%mm3, %%mm0\n\t"
        "por    %%mm0, %%mm1\n\t"
        "psllq  $18, %%mm0\n\t"
        "pand   %%mm3, %%mm0\n\t"
        "por    %%mm1, %%mm0\n\t"
        "psllq  $9, %%mm0\n\t"
        "por    %%mm0, %%mm4\n\t"
        /* mm4 is the pseudo-feasible moves at this point. */
        /* Let mm7 be the feasible moves, i.e., mm4 restricted to empty squares. */
        "por    %%mm6, %%mm7\n\t"
        "pandn  %%mm4, %%mm7\n\t"
        "movq   %%mm7, %0\n\t"
        "emms"          /* Reset the FP/MMX unit. */
    : "=g" (moves) : "m" (P), "m" (O), "g" (P >> 32), "g" (O >> 32), "m" (mask_7e) : "eax", "edx", "ecx", "esi", "edi" );
 
#else
        const unsigned long long mask = O & 0x7E7E7E7E7E7E7E7Eull;
 
        return (get_some_moves(P, mask, 1) // horizontal
                | get_some_moves(P, O, 8)   // vertical
                | get_some_moves(P, mask, 7)   // diagonals
                | get_some_moves(P, mask, 9))
                & ~(P|O); // mask with empties
 
#endif
}
 
unsigned long long get_moves_6x6(const unsigned long long P, const unsigned long long O)
{
        const unsigned long long E = (~(P|O) & 0x007E7E7E7E7E7E00ull); // empties
 
        return ((get_some_moves(P, O & 0x003C3C3C3C3C3C00ull, 1) // horizontal
                | get_some_moves(P, O & 0x00007E7E7E7E0000ull, 8)   // vertical
                | get_some_moves(P, O & 0x00003C3C3C3C0000ull, 7)   // diagonals
                | get_some_moves(P, O & 0x00003C3C3C3C0000ull, 9))
                & E); // mask with empties
}
 
DLL_API bool can_move(const unsigned long long P, const unsigned long long O)
{
        const unsigned long long E = ~(P|O); // empties
 
        return (get_some_moves(P, O & 0x007E7E7E7E7E7E00ull, 7) & E)  // diagonals
                || (get_some_moves(P, O & 0x007E7E7E7E7E7E00ull, 9) & E)
                || (get_some_moves(P, O & 0x7E7E7E7E7E7E7E7Eull, 1) & E)  // horizontal
                || (get_some_moves(P, O & 0x00FFFFFFFFFFFF00ull, 8) & E); // vertical
}
 
bool can_move_6x6(const unsigned long long P, const unsigned long long O)
{
        const unsigned long long E = (~(P|O) & 0x007E7E7E7E7E7E00ull); // empties
 
        return (get_some_moves(P, O & 0x00003C3C3C3C0000ull, 7) & E)  // diagonals
                || (get_some_moves(P, O & 0x00003C3C3C3C0000ull, 9) & E)
                || (get_some_moves(P, O & 0x003C3C3C3C3C3C00ull, 1) & E)  // horizontal
                || (get_some_moves(P, O & 0x00007E7E7E7E0000ull, 8) & E); // vertical
}
 
int get_mobility(const unsigned long long P, const unsigned long long O)
{
        return bit_count(get_moves(P, O));
}
 
int get_weighted_mobility(const unsigned long long P, const unsigned long long O)
{
        return bit_weighted_count(get_moves(P, O));
}
 
static inline unsigned long long get_some_potential_moves(const unsigned long long P, const int dir)
{
        return (P << dir | P >> dir);
}
 
static unsigned long long get_potential_moves(const unsigned long long P, const unsigned long long O)
{
        return (get_some_potential_moves(O & 0x7E7E7E7E7E7E7E7Eull, 1) // horizontal
                | get_some_potential_moves(O & 0x00FFFFFFFFFFFF00ull, 8)   // vertical
                | get_some_potential_moves(O & 0x007E7E7E7E7E7E00ull, 7)   // diagonals
                | get_some_potential_moves(O & 0x007E7E7E7E7E7E00ull, 9))
                & ~(P|O); // mask with empties
}
 
int get_potential_mobility(const unsigned long long P, const unsigned long long O)
{
        return bit_weighted_count(get_potential_moves(P, O));
}
 
static int find_edge_stable(const int old_P, const int old_O, int stable)
{
        register int P, O, x, y;
        const int E = ~(old_P | old_O); // empties
 
        stable &= old_P; // mask stable squares with remaining player squares.
        if (!stable || E == 0) return stable;
 
        for (x = 0; x < 8; ++x) {
                if (E & x_to_bit(x)) { //is x an empty square ?
                        O = old_O;
                        P = old_P | x_to_bit(x); // player plays on it
                        if (x > 1) { // flip left discs
                                for (y = x - 1; y > 0 && (O & x_to_bit(y)); --y) ;
                                if (P & x_to_bit(y)) {
                                        for (y = x - 1; y > 0 && (O & x_to_bit(y)); --y) {
                                                O ^= x_to_bit(y); P ^= x_to_bit(y);
                                        }
                                }
                        }
                        if (x < 6) { // flip right discs
                                for (y = x + 1; y < 8 && (O & x_to_bit(y)); ++y) ;
                                if (P & x_to_bit(y)) {
                                        for (y = x + 1; y < 8 && (O & x_to_bit(y)); ++y) {
                                                O ^= x_to_bit(y); P ^= x_to_bit(y);
                                        }
                                }
                        }
                        stable = find_edge_stable(P, O, stable); // next move
                        if (!stable) return stable;
 
                        P = old_P;
                        O = old_O | x_to_bit(x); // opponent plays on it
                        if (x > 1) {
                                for (y = x - 1; y > 0 && (P & x_to_bit(y)); --y) ;
                                if (O & x_to_bit(y)) {
                                        for (y = x - 1; y > 0 && (P & x_to_bit(y)); --y) {
                                                O ^= x_to_bit(y); P ^= x_to_bit(y);
                                        }
                                }
                        }
                        if (x < 6) {
                                for (y = x + 1; y < 8 && (P & x_to_bit(y)); ++y) ;
                                if (O & x_to_bit(y)) {
                                        for (y = x + 1; y < 8 && (P & x_to_bit(y)); ++y) {
                                                O ^= x_to_bit(y); P ^= x_to_bit(y);
                                        }
                                }
                        }
                        stable = find_edge_stable(P, O, stable); // next move
                        if (!stable) return stable;
                }
        }
 
        return stable;
}
 
void edge_stability_init(void)
{
        int P, O;
 
        for (P = 0; P < 256; ++P)
        for (O = 0; O < 256; ++O) {
                if (P & O) { // illegal positions
                        edge_stability[P][O] = 0;
                } else {
                        edge_stability[P][O] = find_edge_stable(P, O, P);
                }
        }
}
 
static inline unsigned long long get_full_lines(const unsigned long long line, const int dir)
{
#if KOGGE_STONE & 2
 
        // kogge-stone algorithm
        // 5 << + 5 >> + 7 & + 10 |
        // + better instruction independency
        register unsigned long long full_l, full_r, edge_l, edge_r;
        const  unsigned long long edge = 0xff818181818181ffULL;
        const int dir2 = dir << 1;
        const int dir4 = dir << 2;
 
        full_l = line & (edge | (line >> dir)); full_r  = line & (edge | (line << dir));
        edge_l = edge | (edge >> dir);        edge_r  = edge | (edge << dir);
        full_l &= edge_l | (full_l >> dir2);  full_r &= edge_r | (full_r << dir2);
        edge_l |= edge_l >> dir2;             edge_r |= edge_r << dir2;
        full_l &= edge_l | (full_l >> dir4);  full_r &= edge_r | (full_r << dir4);
 
        return full_r & full_l;
 
#elif PARALLEL_PREFIX & 2
 
        // 1-stage Parallel Prefix (intermediate between kogge stone & sequential) 
        // 5 << + 5 >> + 7 & + 10 |
        register unsigned long long full_l, full_r;
        register unsigned long long edge_l, edge_r;
        const  unsigned long long edge = 0xff818181818181ffULL;
        const int dir2 = dir + dir;
 
        full_l  = edge | (line << dir);       full_r  = edge | (line >> dir);
        full_l &= edge | (full_l << dir);     full_r &= edge | (full_r >> dir);
        edge_l  = edge | (edge << dir);       edge_r  = edge | (edge >> dir);
        full_l &= edge_l | (full_l << dir2);  full_r &= edge_r | (full_r >> dir2);
        full_l &= edge_l | (full_l << dir2);  full_r &= edge_r | (full_r >> dir2);
 
        return full_l & full_r;
 
#else
 
        // sequential algorithm
        // 6 << + 6 >> + 12 & + 5 |
        register unsigned long long full;
        const unsigned long long edge = line & 0xff818181818181ffULL;
 
        full = (line & (((line >> dir) & (line << dir)) | edge));
        full &= (((full >> dir) & (full << dir)) | edge);
        full &= (((full >> dir) & (full << dir)) | edge);
        full &= (((full >> dir) & (full << dir)) | edge);
        full &= (((full >> dir) & (full << dir)) | edge);
 
        return ((full >> dir) & (full << dir));
 
#endif
}
 
 
#ifdef __X86_64__
#define packA1A8(X)     ((((X) & 0x0101010101010101ULL) * 0x0102040810204080ULL) >> 56)
#define packH1H8(X)     ((((X) & 0x8080808080808080ULL) * 0x0002040810204081ULL) >> 56)
#else
#define packA1A8(X)     (((((unsigned int)(X) & 0x01010101u) + (((unsigned int)((X) >> 32) & 0x01010101u) << 4)) * 0x01020408u) >> 24)
#define packH1H8(X)     (((((unsigned int)((X) >> 32) & 0x80808080u) + (((unsigned int)(X) & 0x80808080u) >> 4)) * 0x00204081u) >> 24)
#endif
 
static inline unsigned long long get_stable_edge(const unsigned long long P, const unsigned long long O)
{
        // compute the exact stable edges (from precomputed tables)
        return edge_stability[P & 0xff][O & 0xff]
            |  ((unsigned long long)edge_stability[P >> 56][O >> 56]) << 56
            |  A1_A8[edge_stability[packA1A8(P)][packA1A8(O)]]
            |  H1_H8[edge_stability[packH1H8(P)][packH1H8(O)]];
}
 
int get_stability(const unsigned long long P, const unsigned long long O)
{
        const unsigned long long disc = (P | O);
        const unsigned long long central_mask = (P & 0x007e7e7e7e7e7e00ULL);
        const unsigned long long full_h = get_full_lines(disc, 1);
        const unsigned long long full_v = get_full_lines(disc, 8);
        const unsigned long long full_d7 = get_full_lines(disc, 7);
        const unsigned long long full_d9 = get_full_lines(disc, 9);
        register unsigned long long stable_h, stable_v, stable_d7, stable_d9, stable, new_stable;
 
        // compute the exact stable edges (from precomputed tables)
        new_stable = get_stable_edge(P, O);
 
        // add full lines
        new_stable |= (full_h & full_v & full_d7 & full_d9 & central_mask);
 
        // now compute the other stable discs (ie discs touching another stable disc in each flipping direction).
        stable = 0;
        while (new_stable & ~stable) {
                stable |= new_stable;
                stable_h = ((stable >> 1) | (stable << 1) | full_h);
                stable_v = ((stable >> 8) | (stable << 8) | full_v);
                stable_d7 = ((stable >> 7) | (stable << 7) | full_d7);
                stable_d9 = ((stable >> 9) | (stable << 9) | full_d9);
                new_stable = (stable_h & stable_v & stable_d7 & stable_d9 & central_mask);
        }
 
        return bit_count(stable);
}
 
int get_edge_stability(const unsigned long long P, const unsigned long long O)
{
        return bit_count(get_stable_edge(P, O));
}
 
int get_corner_stability(const unsigned long long P)
{
        const unsigned long long stable = ((((0x0100000000000001ULL & P) << 1) | ((0x8000000000000080ULL & P) >> 1) | ((0x0000000000000081ULL & P) << 8) | ((0x8100000000000000ULL & P) >> 8) | 0x8100000000000081ULL) & P);
        return bit_count(stable);
}
 
unsigned long long board_get_hash_code(const Board *board)
{
        unsigned long long h1, h2;
        const unsigned char *p = (const unsigned char*)board;
 
        h1  = hash_rank[0][p[0]];
        h2  = hash_rank[1][p[1]];
        h1 ^= hash_rank[2][p[2]];
        h2 ^= hash_rank[3][p[3]];
        h1 ^= hash_rank[4][p[4]];
        h2 ^= hash_rank[5][p[5]];
        h1 ^= hash_rank[6][p[6]];
        h2 ^= hash_rank[7][p[7]];
        h1 ^= hash_rank[8][p[8]];
        h2 ^= hash_rank[9][p[9]];
        h1 ^= hash_rank[10][p[10]];
        h2 ^= hash_rank[11][p[11]];
        h1 ^= hash_rank[12][p[12]];
        h2 ^= hash_rank[13][p[13]];
        h1 ^= hash_rank[14][p[14]];
        h2 ^= hash_rank[15][p[15]];
 
        return h1 ^ h2;
}
 
int board_get_square_color(const Board *board, const int x)
{
        return 2 - 2 * ((board->player >> x) & 1) - ((board->opponent >> x) & 1);
}
 
bool board_is_occupied(const Board *board, const int x)
{
        return (board->player | board->opponent) & x_to_bit(x);
}
 
bool board_is_pass(const Board *board)
{
        return can_move(board->player, board->opponent) == false &&
                can_move(board->opponent, board->player) == true;
}
 
bool board_is_game_over(const Board *board)
{
        return can_move(board->player, board->opponent) == false &&
                can_move(board->opponent, board->player) == false;
}
 
 
int board_count_empties(const Board *board)
{
        return bit_count(~(board->player | board->opponent));
}
 
void board_print(const Board *board, const int player, FILE *f)
{
        int i, j, square, x;
        const char *color = "?*O-." + 1;
        unsigned long long moves = get_moves(board->player, board->opponent);
 
        fputs("  A B C D E F G H\n", f);
        for (i = 0; i < 8; ++i) {
                fputc(i + '1', f);
                fputc(' ', f);
                for (j = 0; j < 8; ++j) {
                        x = i * 8 + j;
                        if (player == BLACK) square = 2 - ((board->opponent >> x) & 1) - 2 * ((board->player >> x) & 1);
                        else square = 2 - ((board->player >> x) & 1) - 2 * ((board->opponent >> x) & 1);
                        if (square == EMPTY && (moves & x_to_bit(x))) ++square;
                        fputc(color[square], f);
                        fputc(' ', f);
                }
                fputc(i + '1', f);
                if (i == 1)
                        fprintf(f, " %c to move", color[player]);
                else if (i == 3)
                        fprintf(f, " %c: discs = %2d    moves = %2d",
                                color[player], bit_count(board->player), get_mobility(board->player, board->opponent));
                else if (i == 4)
                        fprintf(f, " %c: discs = %2d    moves = %2d",
                                color[!player], bit_count(board->opponent), get_mobility(board->opponent, board->player));
                else if (i == 5)
                        fprintf(f, "  empties = %2d      ply = %2d",
                                64 - bit_count(board->opponent|board->player), bit_count(board->opponent|board->player) - 3);
                fputc('\n', f);
        }
        fputs("  A B C D E F G H\n", f);
}
 
char* board_to_string(const Board *board, const int player, char *s)
{
        int square, x;
        const char *color = "XO-?";
 
        for (x = 0; x < 64; ++x) {
                if (player == BLACK) square = 2 - ((board->opponent >> x) & 1) - 2 * ((board->player >> x) & 1);
                else square = 2 - ((board->player >> x) & 1) - 2 * ((board->opponent >> x) & 1);
                s[x] = color[square];
        }
        s[64] = ' ';
        s[65] = color[player];
        s[66] = '\0';
        return s;
}
 
void board_print_FEN(const Board *board, const int player, FILE *f)
{
        char s[256];
        fputs(board_to_FEN(board, player, s), f);
}
 
char* board_to_FEN(const Board *board, const int player, char *string)
{
        int square, x, r, c;
        const char *piece = "pP-?";
        const char *color = "bw";
        int n_empties = 0;
        char *s = string;
        static char local_string[128];
 
        if (s == NULL) s = string = local_string;
 
        for (r = 7; r >= 0; --r)
        for (c = 0; c < 8; ++c) {
                if (c == 0 && r < 7) {
                        if (n_empties) {
                                *s++ = n_empties + '0';
                                n_empties = 0;
                        }
                        *s++ = '/';
                }
                x = 8 * r + c;
                if (player == BLACK) square = 2 - ((board->opponent >> x) & 1) - 2 * ((board->player >> x) & 1);
                else square = 2 - ((board->player >> x) & 1) - 2 * ((board->opponent >> x) & 1);
 
                if (square == EMPTY) {
                        ++n_empties;
                } else {
                        if (n_empties) {
                                *s++ = n_empties + '0';
                                n_empties = 0;
                        }
                        *s++ = piece[square];
                }
        }
        if (n_empties) {
                *s++ = n_empties + '0';
                n_empties = 0;
        }
        *s++ = ' ';
        *s++ = color[player];
        *s++ = ' '; *s++ = '-'; *s++ = ' '; *s++ = '-'; 
        *s++ = ' '; *s++ = '0'; *s++ = ' '; *s++ = '1'; *s = '\0';
 
        return string;
}