book.c

Go to the documentation of this file.

 
#include "book.h"
#include "base.h"
#include "search.h"
#include "const.h"
#include "bit.h"
#include "options.h"
#include "util.h"
 
#include <assert.h>
#include <time.h>
#include <stdarg.h>
#include <limits.h>
 
#define BOOK_DEBUG 0
static const int BOOK_INFO_RESOLUTION = 100000;
 
#define clear_line() bprint("                                                                                \r")
 
bool book_verbose = false;
 
static void bprint(const char *format, ...)
{
        if (book_verbose) {
                va_list args;
 
                va_start(args, format);
                vprintf(format, args);
                va_end(args);
                fflush (stdout);
                
        }
}
 
const Link BAD_LINK = {-SCORE_INF, NOMOVE};
 
static inline bool link_read(Link *link, FILE *f)
{
        int r;
        r  = fread(&link->score, 1, 1, f);
        r += fread(&link->move, 1, 1, f);
        return r == 2;
}
 
static inline bool link_write(const Link *link, FILE *f)
{
        int r;
        r  = fwrite(&link->score, 1, 1, f);
        r += fwrite(&link->move, 1, 1, f);
        return r == 2;
}
 
static inline bool link_is_bad(const Link *link)
{
        return link->score == -SCORE_INF;
}
 
static Position* book_probe(const Book*, const Board*);
static void book_add(Book*, const Position*);
static void position_print(const Position*, const Board*, FILE*);
 
#define foreach_link(l, p)  \
        for ((l) = (p)->link; (l) < (p)->link + (p)->n_link; ++(l))
 
static int get_book_depth(const int depth)
{
        if (depth <= 10) return 60 - 2 * depth;
        else if (depth <= 18) return 39;
        else if (depth <= 24) return 36;
        else if (depth < 30) return 33;
        else if (depth < 36) return 30;
        else if (depth < 42) return 66 - depth;
        else return 24;
}
 
 
static bool position_is_ok(const Position *position)
{
        Board board[1];
        Move move[1];
        const Link *l;
        int i, j;
        char s[4];
 
        // board is legal ?
        if (position->board->player & position->board->opponent) {
                warn("Board is illegal: Two discs on the same square?\n");
                board_print(position->board, BLACK, stderr);
                return false;
        }
        if (((position->board->player|position->board->opponent) & 0x0000001818000000ULL) != 0x0000001818000000ULL) {
                warn("Board is illegal: Empty center?\n");
                board_print(position->board, BLACK, stderr);
                return false;
        }
 
        // is board unique
        board_unique(position->board, board);
        if (!board_equal(position->board, board)) {
                warn("board is not unique\n");
                position_print(position, position->board, stdout);
                return false;
        }
 
        // are moves legal ?
        foreach_link(l, position) {
                if (l->move == PASS) {
                        if (position->n_link > 1
                         || can_move(board->player, board->opponent)
                         || !can_move(board->opponent, board->player)) {
                                warn("passing move is wrong\n");
                                position_print(position, position->board, stdout);
                                return false;
                        }
                } else {
                        if (/*l->move < A1 ||*/ l->move > H8
                         || board_is_occupied(board, l->move)
                         || board_get_move(board, l->move, move) == 0) {
                                warn("link %s is wrong\n", move_to_string(l->move, WHITE, s));
                                position_print(position, position->board, stdout);
                                return false;
                        }
                }
        }
 
        l = &position->leaf;
        if (l->move == PASS) {
                if (position->n_link > 0
                 || can_move(board->player, board->opponent)
                 || !can_move(board->opponent, board->player)) {
                        warn("passing move is wrong\n");
                        position_print(position, position->board, stdout);
                        return false;
                }
        } else if (l->move == NOMOVE) {
                if (get_mobility(position->board->player, position->board->opponent) != position->n_link && !(position->n_link == 1 && position->link->move == PASS)) {
                        warn("nomove is wrong\n");
                        position_print(position, position->board, stdout);
                        return false;
                }
        } else if (/*l->move < A1 ||*/ l->move > H8
                 || board_is_occupied(board, l->move)
                 || board_get_move(board, l->move, move) == 0) {
                        warn("leaf %s is wrong\n", move_to_string(l->move, WHITE, s));
                        position_print(position, position->board, stdout);
                        return false;
        }
 
        // doublons ?
        for (i = 0; i < position->n_link; ++i) {
                for (j = i + 1; j < position->n_link; ++j) {
                        if (position->link[j].move == position->link[i].move) {
                                warn("doublon found in links\n");
                                position_print(position, position->board, stdout);
                                return false;
                        }
                }
                if (position->leaf.move == position->link[i].move) {
                        warn("doublon found in links/leaf\n");
                        position_print(position, position->board, stdout);
                        return false;
                }
        }
        return true;
}
 
static void position_init(Position *position)
{
        position->board->player = position->board->opponent = 0;
 
        position->leaf = BAD_LINK;
        position->link = NULL;
 
        position->n_wins = position->n_draws = position->n_losses = position->n_lines = 0;
        position->score.value = position->score.lower = -SCORE_INF;
        position->score.upper = +SCORE_INF;
 
        position->n_link = 0;
        position->level = 0;
        //position->done = true;
        //position->todo = false;
    position->flag = FLAG_DONE;
    
    // add by lavox 2021/8/22
    position->n_player_bestpaths = position->n_opponent_bestpaths = 0;
}
 
static void position_merge(Position *dest, const Position *src)
{
        Link *l;
 
        position_init(dest);
        *dest->board = *src->board;
        if (dest->level == src->level) { 
                foreach_link(l, dest) {
                        if (l->move == src->leaf.move) return;
                }
                dest->leaf = src->leaf;
        } else if (dest->level > src->level) {
                return;
        } else {
                dest->leaf = src->leaf;
                dest->level = src->level;
        }
}
 
static void position_free(Position *position)
{
        free(position->link);
}
 
static bool position_read(Position *position, FILE *f)
{
        int i;
        int r;
 
        r  = fread(&position->board->player, sizeof (unsigned long long), 1, f);
        r += fread(&position->board->opponent, sizeof (unsigned long long), 1, f);
 
        r += fread(&position->n_wins, sizeof (unsigned int), 1, f);
        r += fread(&position->n_draws, sizeof (unsigned int), 1, f);
        r += fread(&position->n_losses,  sizeof (unsigned int), 1, f);
        r += fread(&position->n_lines,  sizeof (unsigned int), 1, f);
 
        r += fread(&position->score.value, sizeof (short), 1, f);
        r += fread(&position->score.lower, sizeof (short), 1, f);
        r += fread(&position->score.upper, sizeof (short), 1, f);
 
        r += fread(&position->n_link, 1, 1, f);
        r += fread(&position->level, 1, 1, f);
 
        if (r != 11) return false;
 
        //position->done = position->todo = false;
    position->flag = 0;
    // add by lavox 2021/8/22
    position->n_player_bestpaths = position->n_opponent_bestpaths = 0;
 
        if (position->n_link) {
                position->link = (Link*) malloc(sizeof (Link) * position->n_link);
                if (position->link == NULL) error("cannot allocate opening book position's moves\n");
                for (i = 0; i < position->n_link; ++i) {
                        if (!link_read(position->link + i, f)) return false;
                }
        } else {
                position->link = NULL;
        }
        if (!link_read(&position->leaf, f)) return false;
 
        return true;
}
 
static bool position_import(Position *position, FILE *f)
{
        char *line, *s, *old;
        int value;
        Move move[1];
        bool ok = false;
 
        if ((line = string_read_line(f)) != NULL) {
                position_init(position);
                s = parse_board(line, position->board, &value);
                if (s != line) {
                        s = parse_find(s, ',');
                        if (*s == ',') {
                                value = -1;     s = parse_int(old = s + 1, &value); BOUND(value, -1, 60, "level");
                                if (s != old && value != -1) {
                                        position->level = value;
                                        s = parse_find(s, ',');
                                        if (*s == ',') {
                                                s = parse_move(old = s + 1, position->board, move);
                                                if (s != old) {
                                                        s = parse_find(s, ',');
                                                        if (*s == ',') {
                                                                s = parse_int(old = s + 1, &value);
                                                                if (s != old) {
                                                                        position->leaf.move = move->x;
                                                                        position->leaf.score = value;
                                                                }
                                                        }
                                                }
                                        }
                                        ok = true;
                                } else {
                                        warn("wrong level: %s\n", line);
                                }
                        } else {
                                warn("missing ',' after board setting\n");
                        }
                } else {
                        warn("wrong board: %s\n", line);
                }
        }
 
        if (!ok) warn("=> wrong position\n");
 
        free(line);
        return ok;
}
 
static bool position_write(const Position *position, FILE* f)
{
        int i;
        int r;
 
        r  = fwrite(&position->board->player, sizeof (unsigned long long), 1, f);
        r += fwrite(&position->board->opponent, sizeof (unsigned long long), 1, f);
 
        r += fwrite(&position->n_wins, sizeof (unsigned int), 1, f);
        r += fwrite(&position->n_draws, sizeof (unsigned int), 1, f);
        r += fwrite(&position->n_losses,  sizeof (unsigned int), 1, f);
        r += fwrite(&position->n_lines,  sizeof (unsigned int), 1, f);
 
        r += fwrite(&position->score.value, sizeof (short), 1, f);
        r += fwrite(&position->score.lower, sizeof (short), 1, f);
        r += fwrite(&position->score.upper, sizeof (short), 1, f);
 
        r += fwrite(&position->n_link, 1, 1, f);
        r += fwrite(&position->level, 1, 1, f);
 
        if (r != 11) return false;
 
        for (i = 0; i < position->n_link; ++i)
                if (!link_write(position->link + i, f)) return false;
        if (!link_write(&position->leaf, f)) return false;
 
        return true;
}
 
static bool position_export(const Position *p, FILE* f)
{
        char b[80], m[4];
 
        board_to_string(p->board, BLACK, b);
        move_to_string(p->leaf.move, BLACK, m);
        return (fprintf(f, "%s,%d,%s,%d\n", b, p->level, m, p->leaf.score) > 0);
}
 
static void position_unique(Position *position)
{
        Board board[1];
        int i, s;
 
        *board = *position->board;
        if ((s = board_unique(board, position->board)) != 0) {
                for (i = 0; i < position->n_link; ++i) {
                        position->link[i].move = symetry(position->link[i].move, s);
                }
                position->leaf.move = symetry(position->leaf.move, s);
        }
}
 
static int position_get_moves(const Position *position, const Board *board, MoveList *movelist)
{
        Move *previous = movelist->move;
        Move *move = movelist->move + 1;
        Board sym[1];
        int i, x, s;
 
        for (s = 0; s < 8; ++s) {
                board_symetry(position->board, s, sym);
 
                if (board_equal(sym, board)) {
                        for (i = 0; i < position->n_link; ++i) {
                                x = symetry(position->link[i].move, s);
                                board_get_move(board, x, move);
                                move->score = position->link[i].score;
                                previous = previous->next = move;
                                ++move;
                        }
                        x = symetry(position->leaf.move, s);
                        if (x != NOMOVE) {
                                board_get_move(board, x, move);
                                move->score = position->leaf.score;
                                previous = previous->next = move;
                                ++move;
                        }
                        previous->next = NULL;
                        movelist->n_moves = move - movelist->move - 1;
                        movelist_sort(movelist);
                        return s;
                }
        }
 
        fatal_error("unreachable code\n");
        return -1;
}
 
static void position_show(const Position *position, const Board *board, FILE *f)
{
        MoveList movelist[1];
        Move *move;
        const int n_empties = board_count_empties(board);
        const int color = n_empties & 1;
        int sym;
        char s[4];
 
        board_print(board, color, f);
 
        fprintf(f, "\nLevel: %d\n", position->level);
        fprintf(f, "Best score: %+02d [%+02d, %+02d]\n", position->score.value, position->score.lower, position->score.upper);
        fprintf(f, "Moves:");
        sym = position_get_moves(position, board, movelist);
        foreach_move(move, movelist) {
                move_to_string(move->x, color, s);
                if (symetry(position->leaf.move, sym) == move->x) {
                        fprintf(f, " <%s:%+02d>", s, move->score);
                } else {
                        fprintf(f, " [%s:%+02d]", s, move->score);
                }
        }
}
 
static void position_print(const Position *position, const Board *board, FILE *f)
{
        MoveList movelist[1];
        Move *move;
        int color = board_count_empties(board) & 1, sym;
        char b[80], m[4];
 
        board_to_string(board, color, b);
        fprintf(f, "{board:%s; ", b);
        fprintf(f, "level:%d; ", position->level);
        fprintf(f, "best: %+02d [%+02d, %+02d];", position->score.value, position->score.lower, position->score.upper);
        fprintf(f, "moves:");
        sym = position_get_moves(position, board, movelist);
        foreach_move(move, movelist) {
                move_to_string(move->x, color, m);
                if (symetry(position->leaf.move, sym) == move->x) {
                        fprintf(f, " <%s:%+02d>", m, move->score);
                } else {
                        fprintf(f, " [%s:%+02d]", m, move->score);
                }
        }
        fprintf(f, "}\n");
}
 
static void position_get_random_move(const Position *position, const Board *board, Move *move, Random *r, const int randomness)
{
        MoveList movelist[1];
        Move *m;
        int i, n;
 
        position_get_moves(position, board, movelist);
 
        n = 0;
        foreach_best_move(m, movelist) {
                if (position->score.value <= m->score + randomness) {
                        ++n;
                } else break;
        }
 
        if (n == 0) { // no move
                move->x = NOMOVE;
                move->flipped = 0;
                return;
        } else {
                i = (random_get(r) % n); // is good enough here
        }
 
        foreach_best_move(m, movelist) {
                if (i-- == 0) break;
        }
 
        *move = *m;
}
 
static bool position_add_link(Position *position, const Link *link)
{
        Link *l;
        int last = position->n_link;
 
        foreach_link (l, position) {
                if (l->move == link->move) {
                        l->score = link->score; // update the link ?
                        return false;
                }
        }
 
        l = (Link*) realloc(position->link, sizeof (Link) * (++position->n_link));
        if (l == NULL) {
                --position->n_link;
                error("cannot allocate opening book position's moves\n");
                return false;
        }
        position->link = l;
        position->link[last] = *link;
 
        if (link->score > position->score.value) position->score.value = link->score;
 
        if (link->move == position->leaf.move) position->leaf = BAD_LINK;
 
        return true;
}
 
static void position_sort(Position *position)
{
        Link *i, *j, *best;
 
        if (position->n_link > 1) {
                for (i = position->link; i < position->link + position->n_link - 1; ++i) {
                        best = i;
                        for (j = i + 1; j < position->link + position->n_link; ++j) {
                                if (j->score > best->score) best = j;
                        }
                        if (best > i) {
                                Link tmp = *best;
                                *best = *i;
                                *i = tmp;
                        }
                }
        }
}
 
static void position_search(Position *position, Book *book)
{
        Search *search = book->search;
        Link *l;
        const int n_moves = get_mobility(position->board->player, position->board->opponent);
        long long time;
        bool time_per_move;
 
        if (position->leaf.move != NOMOVE && position_add_link(position, &position->leaf)) {
                book->need_saving = true;
                ++book->stats.n_links;
        }
 
        if (position->n_link < n_moves || (position->n_link == 0 && n_moves == 0 && position->score.value == -SCORE_INF)) {
                search_set_board(search, position->board, BLACK);
                search_set_level(search, position->level, search->n_empties);
 
                foreach_link (l, position) {
                        movelist_exclude(search->movelist, l->move);
                }
 
                if (search->options.verbosity >= 2) {
                        board_print(search->board, search->player, stdout);
                        puts(search->options.header);
                        puts(search->options.separator);
                }
 
                time = search->options.time;
                time_per_move = search->options.time_per_move;
                search->options.time = TIME_MAX;
                search->options.time_per_move = true;
 
                search_run(search);
 
                search->options.time = time;
                search->options.time_per_move = time_per_move;
 
                position->leaf.score = search->result->score;
                position->leaf.move = search->result->move;
                if (position->leaf.score > position->score.value) {
                        position->score.value = position->leaf.score;
                }
                book->need_saving = true;
        }
}
 
static void position_link(Position *position, Book *book)
{
        int x;
        unsigned long long moves = get_moves(position->board->player, position->board->opponent);
        Board next[1];
        Link link[1];
        Position *child;
 
        if (moves) {
                foreach_bit(x, moves) {
                        board_next(position->board, x, next);
                        child = book_probe(book, next);
                        if (child) {
                                link->score = -child->score.value;
                                link->move = x;
                                book->stats.n_links += position_add_link(position, link);
                        }
                }
        } else if (can_move(position->board->opponent, position->board->player)) {// pass ?
                next->player = position->board->opponent;
                next->opponent = position->board->player;
                child = book_probe(book, next);
                if (child) {
                        link->score = -child->score.value;
                        link->move = PASS;
                        book->stats.n_links += position_add_link(position, link);
                }
        }
}
 
static void position_expand(Position *position, Book *book)
{
        Position child[1];
 
        if (position->leaf.move != NOMOVE) {
                position_init(child);
 
                board_next(position->board, position->leaf.move, child->board);
 
                child->level = position->level;
                position_link(child, book);
                search_cleanup(book->search);
                position_search(child, book);
                position->leaf.score = -child->score.value;
                position_search(position, book);
                position_unique(child);
                book_add(book, child);
        }
}
 
static int position_negamax(Position *position, Book *book)
{
        Link *l;
        Board target[1];
        Position *child;
    int tmp_upper, tmp_lower;
 
        //if (!position->done) {
    if (!(position->flag & FLAG_DONE) ) {
                GameStats stat = {0,0,0,0};
                const int n_empties = board_count_empties(position->board);
                const int search_depth = LEVEL[position->level][n_empties].depth;
                const int bias = (search_depth & 1) - (n_empties & 1);
 
                //position->done = 1;
        position->flag |= FLAG_DONE;
 
                position->score.value = position->score.lower = position->score.upper = -SCORE_INF;
 
                if (position->leaf.score > -SCORE_INF) {
                        position->score.value = position->leaf.score;
                        // is solving
                        if (search_depth == n_empties && LEVEL[position->level][n_empties].selectivity == NO_SELECTIVITY) {
                                position->score.lower = position->score.upper = position->score.value;
                                if (position->leaf.score > 0) ++stat.n_wins;
                                else if (position->leaf.score < 0) ++stat.n_losses;
                                else ++stat.n_draws;
                        // is pre-solving
                        } else if (search_depth == n_empties) {
                                position->score.lower = position->score.value - book->options.endcut_error;
                                position->score.upper = position->score.value + book->options.endcut_error;
                        } else { // midgame
                                position->score.lower = position->score.value - book->options.midgame_error - bias;
                                position->score.upper = position->score.value + book->options.midgame_error - bias;
                        }
                        ++stat.n_lines;
                }
 
                foreach_link(l, position) {
                        board_next(position->board, l->move, target);
                        child = book_probe(book, target);
            if ( child ) {
                position_negamax(child, book);
                if (l->score != -child->score.value) {
                    l->score = -child->score.value;
                    book->need_saving = true;
                }
                if (l->score > position->score.value) position->score.value = l->score;
                if (-child->score.upper > position->score.lower) position->score.lower = -child->score.upper;
                if (-child->score.lower > position->score.upper) position->score.upper = -child->score.lower;
 
                stat.n_wins += child->n_losses;
                stat.n_draws += child->n_draws;
                stat.n_losses += child->n_wins;
                stat.n_lines += child->n_lines;
            } else if (l->score > -SCORE_INF) {
                if (l->score > position->score.value) position->score.value = l->score;
 
                // is solving
                if (search_depth == n_empties && LEVEL[position->level][n_empties].selectivity == NO_SELECTIVITY) {
                    tmp_lower = tmp_upper = position->score.value;
                    if (l->score > 0) ++stat.n_wins;
                    else if (l->score < 0) ++stat.n_losses;
                    else ++stat.n_draws;
                // is pre-solving
                } else if (search_depth == n_empties) {
                    tmp_lower = position->score.value - book->options.endcut_error;
                    tmp_upper = position->score.value + book->options.endcut_error;
                } else { // midgame
                    tmp_lower = position->score.value - book->options.midgame_error - bias;
                    tmp_upper = position->score.value + book->options.midgame_error - bias;
                }
                ++stat.n_lines;
 
                if (tmp_upper > position->score.lower) position->score.lower = tmp_upper;
                if (tmp_lower > position->score.upper) position->score.upper = tmp_lower;
            }
                }
 
                position->n_wins = (unsigned int) MIN(UINT_MAX, stat.n_wins);
                position->n_draws = (unsigned int) MIN(UINT_MAX, stat.n_draws);
                position->n_losses = (unsigned int) MIN(UINT_MAX, stat.n_losses);
                position->n_lines = (unsigned int) MIN(UINT_MAX, stat.n_lines);
        }
 
        return position->score.value;
}
 
 
static void position_prune(Position *position, Book *book, const int player_deviation, const int opponent_deviation, const int lower, const int upper)
{
        Link *l;
        Board target[1];
        Position *child;
 
        // if position is not done yet & good enough & inside the book height limit
        if (lower <= position->score.value && position->score.value <= upper && board_count_empties(position->board) >= book->options.n_empties - 1) {
                //position->done = true; book->stats.n_todo++;
        position->flag |= FLAG_DONE; book->stats.n_todo++;
 
                // prune all children close to the best move
                foreach_link(l, position) {
                        if (position->score.value - l->score <= player_deviation && lower <= l->score && l->score <= upper) {
                                board_next(position->board, l->move, target);
                                child = book_probe(book, target);
                                position_prune(child, book, opponent_deviation, player_deviation, -upper, -lower);
                        }
                }
                if (book->stats.n_todo % BOOK_INFO_RESOLUTION == 0) {
                        bprint("Book prune %d to keep\r", book->stats.n_todo);
                        
                }
        }
}
 
static void position_remove_links(Position *position, Book *book)
{
        int i, j;
        Link *l = position->link;
        Board target[1];
 
        for (i = 0; i < position->n_link; ++i) {
                board_next(position->board, l[i].move, target);
                if (!book_probe(book, target)) {
                        if (l[i].score > position->leaf.score) position->leaf = l[i];
                        for (j = i + 1; j < position->n_link; ++j) l[j - 1] = l[j];
                        --position->n_link;
                        --i;
                }
        }
}
 
static void position_deviate(Position *position, Book *book, const int player_deviation, const int opponent_deviation, const int lower, const int upper)
{
        Link *l;
        Board target[1];
        Position *child;
 
        // if position is not done yet & good enough & inside the book height limit
        //if (!position->done && lower <= position->score.value && position->score.value <= upper && board_count_empties(position->board) >= book->options.n_empties && !board_is_game_over(position->board)) {
    if (!(position->flag & FLAG_DONE) && lower <= position->score.value && position->score.value <= upper && board_count_empties(position->board) >= book->options.n_empties && !board_is_game_over(position->board)) {
                //position->done = true;
        position->flag |= FLAG_DONE;
 
                // deviate all children close to the best move
                foreach_link(l, position) {
                        if (position->score.value - l->score <= player_deviation && lower <= l->score && l->score <= upper) {
                                board_next(position->board, l->move, target);
                                child = book_probe(book, target);
                                position_deviate(child, book, opponent_deviation, player_deviation, -upper, -lower);
                        }
                }
 
                // expand the best remaining move
                if (position->score.value - position->leaf.score <= player_deviation && lower <= position->leaf.score && position->leaf.score <= upper) {
                        //position->todo = true; book->stats.n_todo++;
            position->flag |= FLAG_TODO; book->stats.n_todo++;
                        if (book->stats.n_todo % 10 == 0) bprint("Book deviate %d todo\r", book->stats.n_todo);
                }
        }
}
 
static void position_enhance(Position *position, Book *book)
{
        Link *l;
        Board target[1];
        Position *child;
 
        //if (!position->done && board_count_empties(position->board) >= book->options.n_empties && !board_is_game_over(position->board)) {
    if (!(position->flag & FLAG_DONE) && board_count_empties(position->board) >= book->options.n_empties && !board_is_game_over(position->board)) {
                //position->done = true;
        position->flag |= FLAG_DONE;
 
                foreach_link(l, position) {
                        board_next(position->board, l->move, target);
                        child = book_probe(book, target);
                        if (-child->score.upper >= position->score.lower || -child->score.lower >= position->score.upper) {
                                position_enhance(child, book);
                        }
                }
 
                if (position->leaf.score > -SCORE_INF) {
                        const int n_empties = board_count_empties(position->board);
                        const int search_depth = LEVEL[position->level][n_empties].depth;
                        const int bias = (search_depth & 1) - (n_empties & 1);
                        int lower, upper;
                        // is solving
                        if (search_depth == n_empties && LEVEL[position->level][n_empties].selectivity == NO_SELECTIVITY) {
                                lower = upper = position->leaf.score;
                        // is pre-solving
                        } else if (search_depth == n_empties) {
                                lower = position->leaf.score - book->options.endcut_error;
                                upper = position->leaf.score + book->options.endcut_error;
                        } else { // midgame
                                lower = position->leaf.score - book->options.midgame_error - bias;
                                upper = position->leaf.score + book->options.midgame_error - bias;
                        }
 
                        if (lower >= position->score.lower || upper >= position->score.upper) {
                                //position->todo = true;
                position->flag |= FLAG_TODO;
                        }
                }
        }
}
 
static void board_feed_hash(Board *board, const Book *book, Search *search, const bool is_pv)
{
        Position *position;
        const unsigned long long hash_code = board_get_hash_code(board);
        MoveList movelist[1];
        Move *m;
 
        position = book_probe(book, board);
        if (position) {
                const int n_empties = board_count_empties(position->board);
                const int depth = LEVEL[position->level][n_empties].depth;
                const int selectivity = LEVEL[position->level][n_empties].selectivity;
                const int score = position->score.value;
                int move = NOMOVE;
 
                position_get_moves(position, board, movelist);
                foreach_move(m, movelist) {
                        if (move == NOMOVE) move = m->x;
                        board_update(board, m);
                                board_feed_hash(board, book, search, is_pv && m->score == score);
                        board_restore(board, m);
                }
                hash_feed(search->hash_table, board, hash_code, depth, selectivity, score, score, move);
                if (is_pv) hash_feed(search->pv_table, board, hash_code, depth, selectivity, score, score, move);
        }
}
 
static bool board_fill(Board *board, Book *book, int depth)
{
        if (depth > 0) {
                MoveList movelist[1];
                Move *m;
                bool filled = false;
 
                movelist_get_moves(movelist, board);
                if (movelist->n_moves == 0 && can_move(board->opponent, board->player)) {
                        board_pass(board);
                        if (board_fill(board, book, depth - 1)) {
                                book_add_board(book, board);
                                filled = true;
                        }
                        board_pass(board);                                                      
                } else {
                        foreach_move(m, movelist) {
                                board_update(board, m);
                                if (board_fill(board, book, depth - 1)) {
                                        book_add_board(book, board);
                                        filled = true;
                                }
                                board_restore(board, m);                                        
                        }
                }
                return filled;
        }
        return book_probe(book, board) != NULL;
}
 
static void position_fix(Position *position, Book *book)
{
        Board board[1];
 
        if ((position->board->player & position->board->opponent) || 
            ((position->board->player | position->board->opponent) & 0x0000001818000000ULL) != 0x0000001818000000ULL) {
                position_free(position);
                position_init(position);
                return;
        }
        board_unique(position->board, board);
        position_free(position);
        position_init(position);
        *position->board = *board;
        position->level = book->options.level;
        position_link(position, book);
        position_search(position, book);
}
 
typedef struct PositionArray {
        Position *positions;
        int n;
        int size;
} PositionArray;
 
 
static void position_array_init(PositionArray *a)
{
        a->size = a->n = 0;
        a->positions = NULL;
}
 
static bool position_array_add(PositionArray *a, const Position *p)
{
        int i;
 
        board_check(p->board);
        assert(position_is_ok(p));
 
        for (i = 0; i < a->n; ++i) if (board_equal(a->positions[i].board, p->board)) return false;
        if (a->n == a->size) {
                Position *n;
                a->size += a->size / 2 + 1;
                n = (Position*) realloc(a->positions, a->size * sizeof (Position));
                if (n == NULL) {
                        error("cannot add a position to the book\n");
                        a->size = a->n;
                        return false;
                }
                a->positions = n;
        }
        a->positions[a->n] = *p;
        //a->positions[a->n].done = true;
        //a->positions[a->n].todo = false;
    a->positions[a->n].flag |= FLAG_DONE;
    a->positions[a->n].flag &= ~FLAG_TODO;
    // add by lavox 2021/8/21
    a->positions[a->n].n_player_bestpaths = 0;
    a->positions[a->n].n_opponent_bestpaths = 0;
        ++a->n;
        return true;
}
 
static bool position_array_remove(PositionArray *a, const Position *p)
{
        int i, j;
 
        for (i = 0; i < a->n; ++i) {
                if (board_equal(a->positions[i].board, p->board)) {
                        position_free(a->positions + i);
                        for (j = i + 1; j < a->n; ++j) {
                                a->positions[j - 1] = a->positions[j];
                        }
                        --a->n;
                        return true;
                }
        }
        return false;
}
 
static void position_array_free(PositionArray *a)
{
        int i;
        for (i = 0; i < a->n; ++i) position_free(a->positions + i);
        free(a->positions);
}
 
static Position* position_array_probe(PositionArray *a, const Board *board)
{
        int i;
        for (i = 0; i < a->n; ++i) if (board_equal(a->positions[i].board, board)) return a->positions + i;
        return NULL;
}
 
#define foreach_position(p, a, b) \
        for (a = b->array; a < b->array + b->n; ++a) \
        for (p = a->positions; p < a->positions + a->n; ++p)
 
static void book_set_date(Book *book)
{
        time_t t = time(NULL);
        struct tm *tm = localtime(&t);
 
        book->date.year = tm->tm_year + 1900;
        book->date.month = tm->tm_mon + 1;
        book->date.day = tm->tm_mday;
        book->date.hour = tm->tm_hour;
        book->date.minute = tm->tm_min;
        book->date.second = tm->tm_sec;
}
 
static double book_get_age(Book *book)
{
        struct tm tm;
        double t;
 
        tm.tm_year = book->date.year - 1900;
        tm.tm_mon = book->date.month - 1;
        tm.tm_mday = book->date.day;
        tm.tm_hour = book->date.hour;
        tm.tm_min = book->date.minute;
        tm.tm_sec = book->date.second;
        tm.tm_isdst = -1;
 
        t = difftime(time(NULL), mktime(&tm));
 
        return t;
}
 
 
 
static Position* book_probe(const Book *book, const Board *board)
{
        Board unique[1];
        board_unique(board, unique);
        return position_array_probe(book->array + (board_get_hash_code(unique) & (book->n - 1)), unique);
}
 
static void book_add(Book *book, const Position *p)
{
        const unsigned long long i = board_get_hash_code(p->board) & (book->n - 1);
 
        if (position_array_add(book->array + i, p)) {
                ++book->n_nodes;
                ++book->stats.n_nodes;
        }
}
 
static void book_remove(Book *book, const Position *p)
{
        const unsigned long long i = board_get_hash_code(p->board) & (book->n - 1);
 
        if (position_array_remove(book->array + i, p)) {
                --book->n_nodes;
                --book->stats.n_nodes;
        }
}
 
static void book_clean(Book *book)
{
        PositionArray *a;
        Position *p;
        book->stats.n_nodes = book->stats.n_links = book->stats.n_todo = 0;
    foreach_position(p, a, book) {
        //p->done = p->todo = false;
        p->flag &= ~(FLAG_DONE|FLAG_TODO|FLAG_BESTPATH_BLACK);
        p->n_player_bestpaths = p->n_opponent_bestpaths = 0;  // add by lavox 2021/8/22
    }
}
 
void book_stats_clean(Book *book)
{
    book_clean(book);
}
 
static Position *book_root(Book *book)
{
        Board board[1];
 
        board_init(board);
        return book_probe(book, board);
}
 
void book_init(Book *book)
{
        int i;
 
        book_set_date(book);
 
        book->options.level = 21;
        book->options.n_empties = 24;
        book->options.midgame_error = 2;
        book->options.endcut_error = 1;
 
        book->n = 65536;
        book->array = (PositionArray*) malloc(book->n * sizeof *book->array);
        if (book->array == NULL) fatal_error("cannot allocate space to store the positions");
        for (i = 0; i < book->n; ++i) position_array_init(book->array + i);
 
        book->n_nodes = 0;
        random_seed(book->random, real_clock());
        book->need_saving = false;
}
 
void book_free(Book *book)
{
        int i;
        for (i = 0; i < book->n; ++i) {
                position_array_free(book->array + i);
        }
        free(book->array);
}
 
void book_preprocess(Book *book)
{
    book_clean(book);
}
 
void book_new(Book *book, int level, int n_empties)
{
        Board board[1];
 
        bprint("New book %d %d...", level, n_empties);
        book_init(book);
        book->options.level = level;
        book->options.n_empties = n_empties;
 
        board_init(board);
        book_add_board(book, board);
        bprint("...done>\n");
        book->need_saving = true;
}
 
void book_load(Book *book, const char *file)
{
        FILE *f = fopen(file, "rb");
        if (f) {
                Position p;
                unsigned int header_edax, header_book;
                unsigned char header_version, header_release;
                int i;
                int r;
 
                info("Loading book from %s...", file);
                r = fread(&header_edax, sizeof (unsigned int), 1, f);
                r += fread(&header_book, sizeof (unsigned int), 1, f);
                if (r != 2 || header_edax != EDAX || header_book != BOOK) {
                        error("%s is not an edax opening book", file);
                        book_new(book, options.level, 61 - get_book_depth(options.level));
                        return;
                }
 
                r = fread(&header_version, 1, 1, f);
                r += fread(&header_release, 1, 1, f);
                if (r != 2 || header_version != VERSION) {
                        error("%s is not a compatible version", file);
                        book_new(book, options.level, 61 - get_book_depth(options.level));
                        return;
                }
 
                r = fread(&book->date, sizeof book->date, 1, f);
                r += fread(&book->options, sizeof book->options, 1, f);
                r += fread(&book->n_nodes, sizeof book->n_nodes, 1, f);
                if (r != 3) {
                        error("Cannot read book settings from %s", file);
                        book_new(book, options.level, 61 - get_book_depth(options.level));
                        return;
                }
 
                book->n = 65536;
                while ((book->n << 4) < book->n_nodes) book->n <<= 1;
 
                book->array = (PositionArray*) malloc(book->n * sizeof (PositionArray));
                if (book->array == NULL) {
                        error("cannot allocate space to store the positions");
                        book_new(book, options.level, 61 - get_book_depth(options.level));
                        return;
                }
                for (i = 0; i < book->n; ++i) position_array_init(book->array + i);
 
                book->n_nodes = 0;
                while (position_read(&p, f)) {
                        book_add(book, &p);
                }
 
                if (!feof(f)) {
                        error("error while reading %s", file);
                }
 
                random_seed(book->random, real_clock());
                book->need_saving = false;
 
                info("done\n");
                fclose(f);
        } else {
                book_new(book, options.level, 60 - get_book_depth(options.level));
        }
}
 
void book_import(Book *book, const char *file)
{
        FILE *f = fopen(file, "r");
        if (f) {
                PositionArray *a;
                Position *p, position;
                int n_empties;
 
                book_init(book);
                while (position_import(&position, f)) {
                        book_add(book, &position);
                        if (book->n_nodes % BOOK_INFO_RESOLUTION == 0) bprint("importing book from %s... %d positions\r", file, book->n_nodes);
                }
                bprint("importing book from %s... %d positions", file, book->n_nodes);
 
                book->options.n_empties = 60;
                book->options.level = 0;
                foreach_position(p, a, book) {
                        n_empties = board_count_empties(p->board);
                        if (p->level > book->options.level) book->options.level = p->level;
                        if (n_empties < book->options.n_empties) book->options.n_empties = n_empties;
                }
 
                random_seed(book->random, real_clock());
                book->need_saving = true;
 
                bprint("...done\n");
                fclose(f);
        } else {
                error("cannot open \"%s\" to import the opening book\n", file);
                book_new(book, options.level, 61 - get_book_depth(options.level));
        }
}
 
void book_export(Book *book, const char *file)
{
        FILE *f;
        PositionArray *a;
        Position *p;
 
        f = fopen(file, "w");
        if (f == NULL) {
                error("cannot open file %s", file);
                return;
        }
        
        info("Exporting book to %s...", file);
        foreach_position(p, a, book) {
                if (!position_export(p, f)) {
                        error("cannot export book to %s", file);
                        goto book_export_end;
                }
        }
        info("done\n");
 
book_export_end:
        fclose(f);
}
 
void book_save(Book *book, const char *file)
{
        unsigned int header_edax = EDAX, header_book = BOOK;
        unsigned char header_version = VERSION, header_release = RELEASE;
        FILE *f = fopen(file, "wb");
        int r;
        PositionArray *a;
        Position *p;
 
        info("Saving book to %s...", file);
        book_set_date(book);
 
        r = fwrite(&header_edax, sizeof (unsigned int), 1, f);
        r += fwrite(&header_book, sizeof (unsigned int), 1, f);
        r += fwrite(&header_version, 1, 1, f);
        r += fwrite(&header_release, 1, 1, f);
        r += fwrite(&book->date, sizeof book->date, 1, f);
        r += fwrite(&book->options, sizeof book->options, 1, f);
        r += fwrite(&book->n_nodes, sizeof book->n_nodes, 1, f);
 
        if (r == 7) {
                foreach_position(p, a, book) {
                        if (!position_write(p, f)) {
                                error("\nCannot save book to %s", file);
                                goto book_write_end;
                        }
                }
        }
        info("done\n");
 
book_write_end:
        fclose(f);
}
 
void book_merge(Book *dest, const Book *src)
{
        PositionArray *a;
        const Position *p_src;
        Position p_dest[1];
 
        foreach_position(p_src, a, src) {
                if (!book_probe(dest, p_src->board)) {
                        position_merge(p_dest, p_src);
                        book_add(dest, p_dest);
                }
        }
}
 
void book_negamax(Book *book)
{
        Position *root = book_root(book);
 
        if (root) {
                bprint("Negamaxing book...");
                book_clean(book);
                position_negamax(root, book);
                bprint("done\n");
        }
}
 
void book_link(Book *book)
{
        PositionArray *a;
        Position *p;
        int i = 0;
 
        bprint("Linking book...\r");
        foreach_position(p, a, book) {
                position_link(p, book);
                if (p->leaf.move == NOMOVE) {
                        position_search(p, book);
                }
                if (++i % BOOK_INFO_RESOLUTION == 0) bprint("Linking book...%d\r", i);
        }
        bprint("Linking book...%d done\n", i);
}
 
void book_fix(Book *book)
{
        PositionArray *a;
        Position *p;
        int i = 0;
 
        bprint("Fixing book...\r"); 
        foreach_position(p, a, book) {
                if (!position_is_ok(p)) {
                        position_fix(p, book);
                        if (++i % BOOK_INFO_RESOLUTION == 0) { bprint("fixing book...%d\r", i);  }
                }
        }
        bprint("Fixing book...%d done\n", i);
}
 
void book_deepen(Book *book)
{
        PositionArray *a;
        Position *p;
        int i = 0;
        unsigned long long t = real_clock();
        char file[FILENAME_MAX + 1];
        
        file_add_ext(options.book_file, ".dep", file);
 
        bprint("Deepening book...\r"); 
        foreach_position(p, a, book) {
                int n_empties = board_count_empties(p->board);
                if (LEVEL[p->level][n_empties].depth != LEVEL[book->options.level][n_empties].depth
                 || LEVEL[p->level][n_empties].selectivity != LEVEL[book->options.level][n_empties].selectivity) { // No! compare depth & selectivity;
                        p->leaf = BAD_LINK;
                        position_search(p, book);
                        if (++i % 10 == 0) {
                                bprint("Deepening book...%d\r", i); 
                        }
                        if (real_clock() - t > HOUR) {
                                book_save(book, file); // save every hour
                                t = real_clock();
                        }
                }
        }
        bprint("Deepening book...%d done\n", i);
}
 
void book_correct_solved(Book *book)
{
        PositionArray *a;
        Position *p;
        int i = 0;
        unsigned long long t = real_clock();
        char file[FILENAME_MAX + 1];
        Link old_leaf;
        int n_error = 0;
        char s[4];
        
        file_add_ext(options.book_file, ".err", file);
 
        bprint("Correcting solved positions...\r"); 
        foreach_position(p, a, book) {
                int n_empties = board_count_empties(p->board);
                if (LEVEL[p->level][n_empties].depth == n_empties && LEVEL[p->level][n_empties].selectivity == NO_SELECTIVITY) { // No! compare depth & selectivity;
                        old_leaf = p->leaf;
                        p->leaf = BAD_LINK;
                        position_search(p, book);
                        if (p->leaf.score != old_leaf.score) {
                                ++n_error;
                                bprint("\nError found:\n");
                                position_print(p, p->board, stdout);
                                move_to_string(old_leaf.move, n_empties & 1, s);
                                bprint("instead of <%s:%d>\n\n", s, old_leaf.score);
                        }
                        if (++i % 10 == 0 || p->leaf.score != old_leaf.score) {
                                bprint("Correcting solved positions...%d (%d error found)\r", i, n_error); 
                        }
                        if (real_clock() - t > HOUR) {
                                book_save(book, file); // save every hour
                                t = real_clock();
                        }
                }
        }
        bprint("Correcting solved positions...%d done (%d error found)\n", i, n_error);
}
 
static void book_expand(Book *book, const char *action, const char *tmp_file)
{
        PositionArray *a;
        Position *p;
        int i = 0, k;
        unsigned long long t = real_clock();
 
        bprint("%s...\r", action);
        
        for (a = book->array; a < book->array + book->n; ++a)
        for (k = 0; k < a->n; ++k) { // do not use foreach_positions here! a->positions may change!
                p = a->positions + k;
                //if (p->todo) {
        if (p->flag & FLAG_TODO) {
                        position_expand(p, book);
                        bprint("%s...%d/%d done: %d positions, %d links\r", action, ++i, book->stats.n_todo, book->stats.n_nodes, book->stats.n_links);
                        if (book->search->options.verbosity >= 2) putchar('\n'); else putchar('\r');
                        
                        if (real_clock() - t > HOUR) {
                                book_save(book, tmp_file); // save every hour
                                t = real_clock();
                        }
                }
        }
        bprint("%s...%d/%d done: %d positions, %d links\n", action, i, book->stats.n_todo, book->stats.n_nodes, book->stats.n_links);
}
 
void book_sort(Book *book)
{
        PositionArray *a;
        Position *p;
 
        bprint("Sorting book...");
        foreach_position(p, a, book) {
                position_sort(p);
        }
        bprint("done>\n");
}
 
void book_play(Book *book)
{
        PositionArray *a;
        Position *p;
        int n_diffs;
        char file[FILENAME_MAX + 1];
 
        file_add_ext(options.book_file, ".play", file);
        do {
                n_diffs = 0;
                book->stats.n_nodes = book->stats.n_links = book->stats.n_todo = 0;
                foreach_position(p, a, book) {
                        if (p->n_link == 0 && board_count_empties(p->board) >= book->options.n_empties && !board_is_game_over(p->board)) {
                                //p->todo = true; ++book->stats.n_todo;
                p->flag |= FLAG_TODO; ++book->stats.n_todo;
                        } else {
                                //p->todo = false;
                p->flag &= ~FLAG_TODO;
                        }
                        if (book->stats.n_todo && book->stats.n_todo % BOOK_INFO_RESOLUTION == 0) bprint("Book play...%d todo\r", book->stats.n_todo);
                }
                bprint("Book play...%d todo\n", book->stats.n_todo);
 
                book_expand(book, "Book play", file);
 
                n_diffs = book->stats.n_nodes + book->stats.n_links;
                if (n_diffs) {
                        book_negamax(book);
                        book_save(book, file);
                }
        } while (n_diffs);
        bprint("Book play... finished\n");
}
 
void book_fill(Book *book, const int depth)
{
        PositionArray *a;
        Position *p;
        int n_diffs, n_empties, k;
        char file[FILENAME_MAX + 1];
 
        file_add_ext(options.book_file, ".fill", file);
 
        do {
                n_diffs = 0;
                book->stats.n_nodes = book->stats.n_links = 0;
                for (a = book->array; a < book->array + book->n; ++a)
                for (k = 0; k < a->n; ++k) { // do not use foreach_positions here! a->positions may change!
                        p = a->positions + k;
                        n_empties = board_count_empties(p->board);
                        if (n_empties >= book->options.n_empties) {
                                board_fill(p->board, book, depth);
                                if (n_diffs < book->stats.n_nodes + book->stats.n_links) {
                                        n_diffs = book->stats.n_nodes + book->stats.n_links;
                                        bprint("Book fill...%d %d done\r", book->stats.n_nodes, book->stats.n_links); 
                                }
                        }
                }
                bprint("Book fill...%d %d done\n", book->stats.n_nodes, book->stats.n_links);
                if (n_diffs) {
                        book_negamax(book);
                        book_save(book, file);
                }
        } while (n_diffs);
        bprint("Book fill... finished\n");
}
 
void book_deviate(Book *book, Board *board, const int relative_error, const int absolute_error)
{
        Position *root = book_probe(book, board);
        if (root) {
                int score;
                int n_diffs;
                char file[FILENAME_MAX + 1];
 
                file_add_ext(options.book_file, ".dev", file);
                book_clean(book);
                position_negamax(root, book);
 
                do {
                        score = root->score.value;
 
                        bprint("Book deviate %d %d:\n", relative_error, absolute_error);
                        book_clean(book);
                        position_deviate(root, book, relative_error, 0, score - absolute_error, score + absolute_error);
                        bprint("Book deviate %d todo\n", book->stats.n_todo);
 
                        book_expand(book, "Book deviate", file);
                        n_diffs = book->stats.n_nodes + book->stats.n_links;
 
                        bprint("Book deviate %d %d:\n", relative_error, absolute_error);
                        book_clean(book);
                        position_deviate(root, book, 0, relative_error, score - absolute_error, score + absolute_error);
                        bprint("Book deviate %d todo\n", book->stats.n_todo);
 
                        book_expand(book, "Book deviate", file);
                        n_diffs += book->stats.n_nodes + book->stats.n_links;
 
                        root = book_probe(book, board);
                        book_clean(book);
                        position_negamax(root, book);
                        if (n_diffs) book_save(book, file);
                } while (n_diffs);
                bprint("Book deviate %d %d...finished\n", relative_error, absolute_error);
        }
}
 
void book_prune(Book *book)
{
        PositionArray *a;
        Position *p;
        Position *root = book_root(book);
        int i;
 
        if (root) {
                book_clean(book);
                position_negamax(root, book);
 
                book_clean(book);
                position_prune(root, book, 2*SCORE_INF, 0, -SCORE_INF, SCORE_INF);
                position_print(root, root->board, stdout);
                bprint("Book prune %d... done\n", book->stats.n_todo);
 
                position_prune(root, book, 0, 2*SCORE_INF, -SCORE_INF, SCORE_INF);
                bprint("Book prune %d... done\n", book->stats.n_todo);
                for (a = book->array; a < book->array + book->n; ++a)
                //for (i = 0; i < a->n; ++i) if (!a->positions[i].done) {book_remove(book, a->positions + i); --i;}
        for (i = 0; i < a->n; ++i) if (!(a->positions[i].flag & FLAG_DONE)) {book_remove(book, a->positions + i); --i;}
                foreach_position(p, a, book) position_remove_links(p, book);
                bprint("done\n");
        }
}
 
void book_subtree(Book *book, const Board *board)
{
        PositionArray *a;
        Position *p;
        Position *root = book_probe(book, board);
        int i;
 
        if (root) {
                book_clean(book);
                position_negamax(root, book);
 
                book_clean(book);
                position_prune(root, book, 2*SCORE_INF, 2*SCORE_INF, -SCORE_INF, SCORE_INF);
                position_print(root, root->board, stdout);
                bprint("Book subtree %d... done\n", book->stats.n_todo);
                for (a = book->array; a < book->array + book->n; ++a)
                //for (i = 0; i < a->n; ++i) if (!a->positions[i].done) {book_remove(book, a->positions + i); --i;}
        for (i = 0; i < a->n; ++i) if (!(a->positions[i].flag & FLAG_DONE)) {book_remove(book, a->positions + i); --i;}
                foreach_position(p, a, book) position_remove_links(p, book);
                bprint("done\n");
        }
}
 
 
void book_enhance(Book *book, Board *board, const int midgame_error, const int endcut_error)
{
        Position *root = book_probe(book, board);
        if (root) {
                int n_diffs;
                char file[FILENAME_MAX + 1];
 
                file_add_ext(options.book_file, ".enh", file);
 
                book->options.midgame_error = midgame_error;
                book->options.endcut_error = endcut_error;
 
                book_clean(book);
                position_negamax(root, book);
 
                do {
                        bprint("Book enhance %d %d...%d %d:\n", midgame_error, endcut_error, book->stats.n_nodes, book->stats.n_links);
                        book_clean(book);
                        position_enhance(root, book);
                        n_diffs = book->stats.n_nodes + book->stats.n_links;
                        book_expand(book, "Book enhance", file);
 
                        root = book_probe(book, board);
                        book_clean(book);
                        position_negamax(root, book);
                        if (n_diffs) book_save(book, file);
                } while (n_diffs);
                bprint("Book enhance %d %d...finished\n", midgame_error, endcut_error);
        }
}
 
void book_info(Book *book)
{
        PositionArray *a;
        Position *p;
        unsigned long long n_links = 0;
        unsigned long long n_leaves = 0;
        unsigned long long n_level[61] = {0};
        int min_array = book->n_nodes, max_array = 0;
        int i;
 
        foreach_position(p, a, book) {
                n_links += p->n_link;
                if (p->leaf.move != NOMOVE) ++n_leaves;
                ++n_level[p->level];
                if (p->level != book->options.level) {
                        position_print(p, p->board, stdout);
                }
        }
 
        for (a = book->array; a < book->array + book->n; ++a) {
                if (a->n > max_array) max_array = a->n;
                if (a->n < min_array) min_array = a->n;
        }
 
        bprint("Edax Book %d.%d; ", VERSION, RELEASE);
        bprint("%d-%d-%d ", book->date.year, book->date.month, book->date.day);
        bprint("%d:%02d:%02d;\n", book->date.hour, book->date.minute, book->date.second);
        bprint("Positions: %d (moves = %lld links + %lld leaves);\n", book->n_nodes, n_links, n_leaves);
        for (i = 0; i < 61; ++i) {
                if (n_level[i]) {
                        bprint("Level %d : %lld nodes\n", i, n_level[i]);
                }
        }
        bprint("Depth: %d\n", 61 - book->options.n_empties);
        bprint("Memory occupation: %lld\n", (long long) (book->n_nodes * sizeof (Position) + book->n * sizeof (PositionArray) + n_links * sizeof (Link)));
        bprint("Hash balance: %d < %d < %d\n", min_array, (int) (book->n_nodes / book->n), max_array);
}
 
void book_show(Book *book, Board *board)
{
        GameStats stat = {0,0,0,0};
        Position *position = book_probe(book, board);
        unsigned long long n_games;
 
        if (position) {
                position_show(position, board, stdout);
                book_get_game_stats(book, board, &stat);
                n_games = stat.n_wins + stat.n_draws + stat.n_losses;
                if (n_games) {
                        bprint("\nLines: %lld full games", n_games);
                        bprint(" with %.2f%% win, %.2f%% draw, %.2f%% loss",
                                100.0 * stat.n_wins / n_games, 100.0 * stat.n_draws / n_games, 100.0 * stat.n_losses / n_games);
                }
                bprint("\n       %lld incomplete lines.\n\n", stat.n_lines - n_games);
        }
}
 
// add for libedax by lavox. 2018/5/20
Position* book_show_for_api(Book *book, Board *board)
{
    return book_probe(book, board);
}
 
// add by lavox 2021/8/22
void count_bestpath(Book *book, Board *board, unsigned short *n_player, unsigned short *n_opponent, bool verbose)
{
    MoveList movelist[1];
    Move *move;
    int bestscore;
    unsigned short n_next_player;
    unsigned short n_next_opponent;
 
    Position *position = book_probe(book, board);
    if (position) {
        if ( position->n_player_bestpaths != 0 && position->n_opponent_bestpaths != 0 ) {
            *n_player = position->n_player_bestpaths;
            *n_opponent = position->n_opponent_bestpaths;
        } else {
            position_get_moves(position, board, movelist);
            bestscore = position->score.value;
            *n_player = USHRT_MAX;
            *n_opponent = 0;
            foreach_move(move, movelist) {
                if (move->score != bestscore) continue;
                if (book->count_bestpath_stop) break;
                
                board_update(board, move);
                count_bestpath(book, board, &n_next_player, &n_next_opponent, false);
                *n_player = MIN(*n_player, n_next_opponent);
                if ( n_next_player <= USHRT_MAX - *n_opponent ) *n_opponent += n_next_player;
                else *n_opponent = USHRT_MAX;
                board_restore(board, move);
            }
            if (book->count_bestpath_stop) return;
            if ( *n_opponent == 0 ) *n_player = *n_opponent = 1;
            position->n_player_bestpaths = *n_player;
            position->n_opponent_bestpaths = *n_opponent;
        }
    } else {
        *n_player = *n_opponent = 1;
    }
 
    if ( verbose ) {
        bprint("\nplayer bestpaths count   : %d\n", *n_player);
        bprint("opponent bestpaths count : %d\n", *n_opponent);
    }
}
// add by lavox 2022/6/12
void count_board_bestpath(Book *book, Board *board, const int p_lower, const int o_lower, const int turn, unsigned short *n_player, unsigned short *n_opponent, bool verbose)
{
    MoveList movelist[1];
    Move *move;
    unsigned short n_next_player;
    unsigned short n_next_opponent;
    int turn_flag = turn == BLACK ? FLAG_BESTPATH_BLACK : 0;
 
    Position *position = book_probe(book, board);
    if (position) {
        if ( position->n_player_bestpaths != 0 && position->n_opponent_bestpaths != 0 && (position->flag & FLAG_BESTPATH_BLACK) == turn_flag ) {
            *n_player = position->n_player_bestpaths;
            *n_opponent = position->n_opponent_bestpaths;
        } else {
            position_get_moves(position, board, movelist);
            int lower = p_lower == BESTPATH_BEST ? position->score.value : p_lower;
            *n_player = USHRT_MAX;
            *n_opponent = 0;
            foreach_move(move, movelist) {
                if (move->score < lower) continue;
                if (book->count_bestpath_stop) break;
                
                board_update(board, move);
                count_board_bestpath(book, board, o_lower, p_lower, 1 - turn, &n_next_player, &n_next_opponent, false);
                *n_player = MIN(*n_player, n_next_opponent);
                if ( n_next_player <= USHRT_MAX - *n_opponent ) *n_opponent += n_next_player;
                else *n_opponent = USHRT_MAX;
                board_restore(board, move);
            }
            if (book->count_bestpath_stop) return;
            if ( *n_opponent == 0 ) *n_player = *n_opponent = 1;
            position->n_player_bestpaths = *n_player;
            position->n_opponent_bestpaths = *n_opponent;
            if ( turn == BLACK ) {
                position->flag |= FLAG_BESTPATH_BLACK;
            } else {
                position->flag &= ~FLAG_BESTPATH_BLACK;
            }
        }
    } else {
        *n_player = *n_opponent = 1;
    }
 
    if ( verbose ) {
        bprint("\nplayer bestpaths count   : %d\n", *n_player);
        bprint("opponent bestpaths count : %d\n", *n_opponent);
    }
}
 
// add by lavox 2021/8/22
void book_count_bestpath(Book *book, Board *board, Position *position)
{
    unsigned short n_player;
    unsigned short n_opponent;
    
    book->count_bestpath_stop = RUNNING;
    count_bestpath(book, board, &n_player, &n_opponent, false);
    Position *p = book_probe(book, board);
    if (p) {
        memcpy(position, p, sizeof(Position));
    } else {
        position->n_player_bestpaths = position->n_opponent_bestpaths = 1;
    }
}
void book_stop_count_bestpath(Book *book) {
    book->count_bestpath_stop = STOP_PONDERING;
}
 
// add by lavox 2022/6/12
void book_count_board_bestpath(Book *book, Board *board, Position *position, const int p_lower, const int o_lower, const int turn)
{
    unsigned short n_player;
    unsigned short n_opponent;
    
    book->count_bestpath_stop = RUNNING;
    count_board_bestpath(book, board, p_lower, o_lower, turn, &n_player, &n_opponent, false);
    Position *p = book_probe(book, board);
    if (p) {
        memcpy(position, p, sizeof(Position));
    } else {
        position->n_player_bestpaths = position->n_opponent_bestpaths = 1;
    }
}
 
bool book_get_moves(Book *book, const Board *board, MoveList *movelist)
{
        Position *position = book_probe(book, board);
        if (position) {
                position_get_moves(position, board, movelist);
                return true;
        }
 
        return false;
}
 
int book_get_moves_with_position(Book *book, const Board *board, MoveList *movelist, Position *position)
{
    Position *p = book_probe(book, board);
    if (p) {
        int sym;
        sym = position_get_moves(p, board, movelist);
        memcpy(position, p, sizeof(Position));
        return sym;
    }
 
    return -1;
}
 
void book_get_line(Book *book, const Board *board, const Move *move, Line *line)
{
        Position *position;
        Board b[1];
        Move m[1];
 
        line_push(line, move->x);
        board_next(board, move->x, b);
 
        while ((position = book_probe(book, b)) != NULL && !board_is_game_over(position->board)) {
                position_get_random_move(position, b, m, book->random, 0);
                line_push(line, m->x);
                board_update(b, m);
        }
}
 
 
bool book_get_random_move(Book *book, const Board *board, Move *move, const int randomness)
{
        Position *position = book_probe(book, board);
        if (position) {
                position_get_random_move(position, board, move, book->random, randomness);
                return true;
        }
 
        return false;
}
 
void book_get_game_stats(Book *book, const Board *board, GameStats *stat)
{
        Position *position;
 
        assert(book != NULL);
        assert(board !=NULL);
        assert(stat != NULL);
        
        stat->n_wins = stat->n_losses = stat->n_draws = stat->n_lines = 0;
 
        position = book_probe(book, board);
        if (position) {
                if (position->n_wins == UINT_MAX || position->n_losses == UINT_MAX || position->n_draws == UINT_MAX || position->n_lines == UINT_MAX) {
                        Board target[1];
                        Link *l;
                        GameStats child;
                        
                        foreach_link(l, position) {
                                board_next(position->board, l->move, target);
                                book_get_game_stats(book, target, &child);
                                stat->n_wins += child.n_losses;
                                stat->n_draws += child.n_draws;
                                stat->n_losses += child.n_wins;
                                stat->n_lines += child.n_lines;
                        }
                } else {
                        stat->n_wins = position->n_wins;
                        stat->n_draws = position->n_draws;
                        stat->n_losses = position->n_losses;
                        stat->n_lines = position->n_lines;
                }
        }
}
 
 
void book_add_board(Book *book, const Board *board)
{
        Position position[1];
        Position *probe;
 
        if (board_count_empties(board) >= book->options.n_empties - 1) {
                probe = book_probe(book, board);
                if (probe) {
                        position_link(probe, book);
                        if (probe->leaf.move == NOMOVE) position_search(probe, book);
                        if (BOOK_DEBUG) {printf("update: "); position_print(probe, board, stdout);}
                } else {
                        position_init(position);
                        *position->board = *board;
                        position->level = book->options.level;
                        position_link(position, book);
                        position_search(position, book);
                        if (BOOK_DEBUG) {printf("new: "); position_print(position, board, stdout);}
                        position_unique(position);
                        book_add(book, position);
                }
        }
}
 
void book_add_game(Book *book, const Game *game)
{
        Board board[1];
        Move stack[99];
        int i, n_moves;
        char file[FILENAME_MAX + 1];
        const int n_stats = book->stats.n_nodes + book->stats.n_links;
 
        file_add_ext(options.book_file, ".gam", file);
        
        board_init(board);
        if (!board_equal(board, game->initial_board)) return; // skip non standard game
        for (i = n_moves = 0; i < 60 - book->options.n_empties && game->move[i] != NOMOVE; ++i) {
                if (!can_move(board->player, board->opponent)) {
                        stack[n_moves++] = MOVE_PASS;
                        board_pass(board);
                }
                if (!board_is_occupied(board, game->move[i]) && board_get_move(board, game->move[i], &stack[n_moves])) {
                        board_update(board, stack + n_moves);
                        ++n_moves;
                } else {
                        warn("illegal move in game");
                        break; // stop, illegal moves
                }
        }
 
        search_cleanup(book->search);
        while (--n_moves >= 0) {
                book_add_board(book, board);
                board_restore(board, stack + n_moves);
        }
 
        if (book->stats.n_nodes + book->stats.n_links > n_stats && book_get_age(book) > 3600) book_save(book, file);
}
 
void book_add_base(Book *book, const Base *base)
{
        int i;
        char file[FILENAME_MAX + 1];
        long long t0, t;
 
        file_add_ext(options.book_file, ".gam", file);
 
        book_clean(book);
        bprint("Adding %d games to book...\n", base->n_games);
        t0 = real_clock();
        for (i = 0; i < base->n_games; ++i) {
                book_add_game(book, base->game + i);
                t = real_clock();
                if (t - t0 > 1000) {
                    bprint("Adding games...%d/%d done: %d positions, %d links\r", i + 1, base->n_games, book->stats.n_nodes, book->stats.n_links);
                        t0 = t;
                }
                if (book->search->options.verbosity) putchar('\n');
                
        }
        bprint("Adding games...%d/%d done: %d positions, %d links\n", i, base->n_games, book->stats.n_nodes, book->stats.n_links);
        bprint("%d games added to book\n", i);
 
        book_save(book, file);
}
 
typedef struct BookCheckGame {
        unsigned long long missing;
        unsigned long long good;
        unsigned long long bad;
} BookCheckGame;
 
void book_check_game(Book *book, MoveHash *hash, const Game *game, BookCheckGame *stat)
{
        Board board[1];
        Move stack[99], *iter;
        MoveList movelist[1];
        int i, n_moves;
        int bestscore;
 
        board_init(board);
        if (!board_equal(board, game->initial_board)) return; // skip non standard game
        for (i = n_moves = 0; i <= 60 - book->options.n_empties && game->move[i] != NOMOVE; ++i) {
                if (!can_move(board->player, board->opponent)) {
                        stack[n_moves++] = MOVE_PASS;
                        board_pass(board);
                }
                if (!board_is_occupied(board, game->move[i]) && board_get_move(board, game->move[i], &stack[n_moves])) {
                        board_update(board, stack + n_moves);
                        ++n_moves;
                } else {
                        warn("illegal move in game");
                        break; // stop, illegal moves
                }
        }
 
        while (--n_moves >= 0) {
                board_restore(board, stack + n_moves);
                if (movehash_append(hash, board, stack[n_moves].x)) {
                        if (book_get_moves(book, board, movelist)) {
                                bestscore = movelist_first(movelist)->score;
                                foreach_move(iter, movelist) {
                                        if (iter->x == stack[n_moves].x) {
                                                if (iter->score < bestscore) ++stat->bad;
                                                else ++stat->good;
                                                break;
                                        }
                                }
                        } else ++stat->missing;         
                }
        }
}
 
void book_check_base(Book *book, const Base *base)
{
        int i;
        BookCheckGame stat = {0, 0, 0};
        MoveHash hash;
 
        bprint("Checking %d games to book...\n", base->n_games);
        movehash_init(&hash, options.hash_table_size);
        for (i = 0; i < base->n_games; ++i) {
                book_check_game(book, &hash, base->game + i, &stat);
        }
        movehash_delete(&hash);
    bprint("Positions : %llu missing, %llu good, %llu bad (%.2f%% bad)\n", stat.missing, stat.good, stat.bad, (100.0 * stat.bad)/(stat.bad + stat.good));
}
 
 
static void extract_skeleton(Book *book, Board *board, Line *pv, Base *base)
{
        MoveList movelist[1];
        Move *move;
        Board init[1];
        Game game[1];
        int bestscore;
 
        if (book_get_moves(book, board, movelist)) {
                bestscore = movelist_best(movelist)->score;
                
                foreach_move(move, movelist) {
                        if (move->score == bestscore) {
                                board_update(board, move); line_push(pv, move->x);
                                        extract_skeleton(book, board, pv, base);
                                board_restore(board, move); line_pop(pv);
                        }
                }
        } else if (pv->n_moves) {
                board_init(init);
                line_to_game(init, pv, game);
                base_append(base, game);
                if (base->n_games % 1000 == 0) {
                        bprint("extracting %d games\r", base->n_games);
                        
                }
        }
}
 
void book_extract_skeleton(Book *book, Base *base)
{
        Line pv[1];
        Board board[1];
 
        line_init(pv, BLACK);
        line_push(pv, F5); line_push(pv, D6); line_push(pv, C4);
        board_init(board);
        board_next(board, F5, board); board_next(board, D6, board); board_next(board, C4, board);
        extract_skeleton(book, board, pv, base);
        
        line_init(pv, BLACK);
        line_push(pv, F5); line_push(pv, F6); line_push(pv, E6); line_push(pv, F4);
        board_init(board);
        board_next(board, F5, board); board_next(board, F6, board);
        board_next(board, E6, board); board_next(board, F4, board);     
        extract_skeleton(book, board, pv, base);
        bprint("%d games extracted   \n", base->n_games);
}
 
 
void book_extract_positions(Book *book, const int n_empties, const int n_positions)
{
        PositionArray *a;
        Position *p;
        MoveList movelist[1];
        Move *best, *second_best;
        int i = 0;
        char s[80];
 
        bprint("Extracting %d positions at %d ...\n", n_positions, n_empties); 
        foreach_position(p, a, book) {
                if (i == n_positions) break;
                if (board_count_empties(p->board) == n_empties) {
                        position_get_moves(p, p->board, movelist);
                        best = movelist_first(movelist);
                        if (best) {
                                second_best = move_next(best);
                                if (second_best && best->score > second_best->score) {
                                        ++i;
                                        board_to_string(p->board, n_empties & 1, s);
                                        bprint("%s %% bm ", s);
                                        move_print(best->x, n_empties & 1, stdout);
                                        bprint(":%+2d; ba ", best->score);
                                        move_print(second_best->x, n_empties & 1, stdout);
                                        bprint(":%+2d;\n", second_best->score);
                                }
                        }
                }
        }
}
 
void book_stats(Book *book)
{
        PositionArray *a;
        Position *p;
        int i;
        unsigned long long n_hash[256];
        unsigned long long n_pos[61], n_leaf[61], n_link[61], n_terminal[61];
        unsigned long long n_score[129];
 
        printf("\n\nBook statistics:\n");
 
        printf("\nHash distribution:\n");
        for (i = 0; i < 256; ++i) n_hash[i] = 0;
        for (a = book->array; a < book->array + book->n; ++a) {
                if (a->n < 256) ++n_hash[a->n];
                else ++n_hash[255];
        }
        printf("index    positions\n");
        for (i = 0; i < 255; ++i) if (n_hash[i]) printf("%5d %12llu\n", i, n_hash[i]);
        if (n_hash[i]) printf(">%4d %12llu\n", i - 1, n_hash[i]);
 
        printf("\nStage distribution:\n");
        printf("stage    positions        links       leaves      terminal nodes\n");
        for (i = 0; i < 61; ++i) n_pos[i] = n_leaf[i] = n_link[i] = n_terminal[i] = 0;
        foreach_position(p, a, book) {
                i = board_count_empties(p->board);
                ++n_pos[i];
                if (p->leaf.move != NOMOVE) ++n_leaf[i];
                if (p->n_link == 0) ++n_terminal[i];
                n_link[i] += p->n_link;
        }
        for (i = 0; i < 61; ++i) if (n_pos[i]) printf("%5d %12llu %12llu %12llu %12llu\n", i, n_pos[i], n_link[i], n_leaf[i], n_terminal[i]);
                
        printf("\nBest Score Distribution:\n");
        printf("Score    positions\n");
        for (i = 0; i < 129; ++i) n_score[i] = 0;
        foreach_position(p, a, book) {
                ++n_score[64 + p->score.value];
        }
        for (i = 0; i < 129; ++i) if (n_score[i]) printf("%+5d %12llu\n", i - 64, n_score[i]);
        printf("\n\n");
        fflush(stdout);
}
 
void book_feed_hash(const Book *book, Board *board, Search *search)
{
        board_feed_hash(board, book, search, true);
}