X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbook.cpp;h=1c2d30e0a41df95358a23cd9bdf1b8ace8944315;hp=95ccd690506251c284dc557905a53d5c1cc6711f;hb=bc8f5fe0bfd2690d1fcfe3541b54193a05322102;hpb=efeb37c33f15a903dbe5706529a7a26511e9ca58 diff --git a/src/book.cpp b/src/book.cpp index 95ccd690..1c2d30e0 100644 --- a/src/book.cpp +++ b/src/book.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -17,36 +17,36 @@ along with this program. If not, see . */ - /* The code in this file is based on the opening book code in PolyGlot - by Fabien Letouzey. PolyGlot is available under the GNU General + by Fabien Letouzey. PolyGlot is available under the GNU General Public License, and can be downloaded from http://wbec-ridderkerk.nl */ - -//// -//// Includes -//// - +#include #include +#include #include "book.h" +#include "misc.h" #include "movegen.h" using namespace std; -//// -//// Local definitions -//// - namespace { - // Book entry size in bytes - const int EntrySize = 16; + // A Polyglot book is a series of "entries" of 16 bytes. All integers are + // stored in big-endian format, with highest byte first (regardless of size). + // The entries are ordered according to the key in ascending order. + struct BookEntry { + uint64_t key; + uint16_t move; + uint16_t count; + uint32_t learn; + }; // Random numbers from PolyGlot, used to compute book hash keys - const uint64_t Random64[781] = { + const Key PolyGlotRandoms[781] = { 0x9D39247E33776D41ULL, 0x2AF7398005AAA5C7ULL, 0x44DB015024623547ULL, 0x9C15F73E62A76AE2ULL, 0x75834465489C0C89ULL, 0x3290AC3A203001BFULL, 0x0FBBAD1F61042279ULL, 0xE83A908FF2FB60CAULL, 0x0D7E765D58755C10ULL, @@ -310,276 +310,172 @@ namespace { 0xF8D626AAAF278509ULL }; - // Indices to the Random64[] array - const int PieceIdx = 0; - const int CastleIdx = 768; - const int EnPassantIdx = 772; - const int TurnIdx = 780; - - // Local functions - uint64_t book_key(const Position& pos); - uint64_t book_piece_key(Piece p, Square s); - uint64_t book_castle_key(const Position& pos); - uint64_t book_ep_key(const Position& pos); - uint64_t book_color_key(const Position& pos); -} - + // Offsets to the PolyGlotRandoms[] array of zobrist keys + const Key* ZobPiece = PolyGlotRandoms; + const Key* ZobCastle = ZobPiece + 12 * 64; // Pieces * squares + const Key* ZobEnPassant = ZobCastle + 4; // Castle flags + const Key* ZobTurn = ZobEnPassant + 8; // Number of files -//// -//// Functions -//// + // book_key() returns the PolyGlot hash key of the given position + uint64_t book_key(const Position& pos) { -// C'tor. Make random number generation less deterministic, for book moves -Book::Book() { + uint64_t key = 0; + Bitboard b = pos.pieces(); - for (int i = abs(get_system_time() % 10000); i > 0; i--) - RKiss.rand(); -} + while (b) + { + // In PolyGlotRandoms[] pieces are stored in the following sequence: + // BP = 0, WP = 1, BN = 2, WN = 3, ... BK = 10, WK = 11 + Square s = pop_lsb(&b); + Piece p = pos.piece_on(s); + int pieceOfs = 2 * (type_of(p) - 1) + (color_of(p) == WHITE); + key ^= ZobPiece[64 * pieceOfs + s]; + } + b = pos.can_castle(ALL_CASTLES); -/// Destructor. Be sure file is closed before we leave. + while (b) + key ^= ZobCastle[pop_lsb(&b)]; -Book::~Book() { + if (pos.ep_square() != SQ_NONE) + key ^= ZobEnPassant[file_of(pos.ep_square())]; - close(); -} + if (pos.side_to_move() == WHITE) + key ^= ZobTurn[0]; + return key; + } -/// Book::close() closes the file only if it is open, otherwise -/// we can end up in a little mess due to how std::ifstream works. +} // namespace -void Book::close() { +PolyglotBook::PolyglotBook() { - if (is_open()) - ifstream::close(); + for (int i = Time::now() % 10000; i > 0; i--) + RKiss.rand(); // Make random number generation less deterministic } +PolyglotBook::~PolyglotBook() { if (is_open()) close(); } -/// Book::open() opens a book file with a given file name -void Book::open(const string& fName) { +/// operator>>() reads sizeof(T) chars from the file's binary byte stream and +/// converts them in a number of type T. A Polyglot book stores numbers in +/// big-endian format. - // Close old file before opening the new - close(); +template PolyglotBook& PolyglotBook::operator>>(T& n) { - fileName = fName; - ifstream::open(fileName.c_str(), ifstream::in | ifstream::binary); + n = 0; + for (size_t i = 0; i < sizeof(T); i++) + n = T((n << 8) + ifstream::get()); - if (is_open()) - { - // Get the book size in number of entries - seekg(0, ios::end); - bookSize = long(tellg()) / EntrySize; - seekg(0, ios::beg); + return *this; +} - if (good()) - return; - } - cerr << "Failed to open book file " << fileName << endl; - exit(EXIT_FAILURE); +template<> PolyglotBook& PolyglotBook::operator>>(BookEntry& e) { + return *this >> e.key >> e.move >> e.count >> e.learn; } -/// Book::file_name() returns the file name of the currently active book, -/// or the empty string if no book is open. +/// open() tries to open a book file with the given name after closing any +/// exsisting one. + +bool PolyglotBook::open(const char* fName) { -const string Book::file_name() { // Not const to compile on HP-UX 11.X + if (is_open()) // Cannot close an already closed file + close(); - return is_open() ? fileName : ""; + ifstream::open(fName, ifstream::in | ifstream::binary); + + fileName = is_open() ? fName : ""; + ifstream::clear(); // Reset any error flag to allow retry ifstream::open() + return !fileName.empty(); } -/// Book::get_move() gets a book move for a given position. Returns -/// MOVE_NONE if no book move is found. +/// probe() tries to find a book move for the given position. If no move is +/// found returns MOVE_NONE. If pickBest is true returns always the highest +/// rated move, otherwise randomly chooses one, based on the move score. -Move Book::get_move(const Position& pos, bool findBestMove) { +Move PolyglotBook::probe(const Position& pos, const string& fName, bool pickBest) { - if (!is_open() || bookSize == 0) + if (fileName != fName && !open(fName.c_str())) return MOVE_NONE; - BookEntry entry; - int bookMove = MOVE_NONE; - unsigned scoresSum = 0, bestScore = 0; + BookEntry e; + uint16_t best = 0; + unsigned sum = 0; + Move move = MOVE_NONE; uint64_t key = book_key(pos); - // Choose a book move among the possible moves for the given position - for (int idx = find_key(key); idx < bookSize; idx++) + seekg(find_first(key) * sizeof(BookEntry), ios_base::beg); + + while (*this >> e, e.key == key && good()) { - read_entry(entry, idx); - if (entry.key != key) - break; - - unsigned score = entry.count; - - // If findBestMove is true choose highest rated book move - if (findBestMove) - { - if (score > bestScore) - { - bestScore = score; - bookMove = entry.move; - } - continue; - } + best = max(best, e.count); + sum += e.count; // Choose book move according to its score. If a move has a very - // high score it has more probability to be choosen then a one with - // lower score. Note that first entry is always chosen. - scoresSum += score; - if (RKiss.rand() % scoresSum < score) - bookMove = entry.move; + // high score it has higher probability to be choosen than a move + // with lower score. Note that first entry is always chosen. + if ( (sum && RKiss.rand() % sum < e.count) + || (pickBest && e.count == best)) + move = Move(e.move); } - if (!bookMove) + + if (!move) return MOVE_NONE; - // Verify the book move is legal - MoveStack mlist[MOVES_MAX]; - MoveStack* last = generate_moves(pos, mlist); - for (MoveStack* cur = mlist; cur != last; cur++) - if ((int(cur->move) & 07777) == bookMove) - return cur->move; + // A PolyGlot book move is encoded as follows: + // + // bit 0- 5: destination square (from 0 to 63) + // bit 6-11: origin square (from 0 to 63) + // bit 12-14: promotion piece (from KNIGHT == 1 to QUEEN == 4) + // + // Castling moves follow "king captures rook" representation. So in case book + // move is a promotion we have to convert to our representation, in all the + // other cases we can directly compare with a Move after having masked out + // the special Move's flags (bit 14-15) that are not supported by PolyGlot. + int pt = (move >> 12) & 7; + if (pt) + move = make(from_sq(move), to_sq(move), PieceType(pt + 1)); + + // Add 'special move' flags and verify it is legal + for (MoveList ml(pos); !ml.end(); ++ml) + if (move == (ml.move() ^ type_of(ml.move()))) + return ml.move(); return MOVE_NONE; } -/// Book::find_key() takes a book key as input, and does a binary search -/// through the book file for the given key. The index to the first book -/// entry with the same key as the input is returned. When the key is not -/// found in the book file, bookSize is returned. +/// find_first() takes a book key as input, and does a binary search through +/// the book file for the given key. Returns the index of the leftmost book +/// entry with the same key as the input. -int Book::find_key(uint64_t key) { +size_t PolyglotBook::find_first(uint64_t key) { - int left, right, mid; - BookEntry entry; + seekg(0, ios::end); // Move pointer to end, so tellg() gets file's size - // Binary search (finds the leftmost entry) - left = 0; - right = bookSize - 1; + size_t low = 0, mid, high = (size_t)tellg() / sizeof(BookEntry) - 1; + BookEntry e; - assert(left <= right); + assert(low <= high); - while (left < right) + while (low < high && good()) { - mid = (left + right) / 2; + mid = (low + high) / 2; - assert(mid >= left && mid < right); + assert(mid >= low && mid < high); - read_entry(entry, mid); + seekg(mid * sizeof(BookEntry), ios_base::beg); + *this >> e; - if (key <= entry.key) - right = mid; + if (key <= e.key) + high = mid; else - left = mid + 1; - } - - assert(left == right); - - read_entry(entry, left); - return entry.key == key ? left : bookSize; -} - - -/// Book::read_entry() takes a BookEntry reference and an integer index as -/// input, and looks up the opening book entry at the given index in the book -/// file. The book entry is copied to the first input parameter. - -void Book::read_entry(BookEntry& entry, int idx) { - - assert(idx >= 0 && idx < bookSize); - assert(is_open()); - - seekg(idx * EntrySize, ios_base::beg); - - *this >> entry; - - if (!good()) - { - cerr << "Failed to read book entry at index " << idx << endl; - exit(EXIT_FAILURE); - } -} - - -/// Book::read_integer() reads size chars from the file stream -/// and converts them in an integer number. - -uint64_t Book::read_integer(int size) { - - char buf[8]; - uint64_t n = 0; - - read(buf, size); - - // Numbers are stored on disk as a binary byte stream - for (int i = 0; i < size; i++) - n = (n << 8) + (unsigned char)buf[i]; - - return n; -} - - -//// -//// Local definitions -//// - -namespace { - - uint64_t book_key(const Position& pos) { - - uint64_t result = 0; - Bitboard b = pos.occupied_squares(); - - while (b) - { - Square s = pop_1st_bit(&b); - result ^= book_piece_key(pos.piece_on(s), s); - } - - result ^= book_castle_key(pos); - result ^= book_ep_key(pos); - result ^= book_color_key(pos); - return result; - } - - - uint64_t book_piece_key(Piece p, Square s) { - - // Convert pieces to the range 0..11 - static const int PieceTo12[] = { 0, 0, 2, 4, 6, 8, 10, 0, 0, 1, 3, 5, 7, 9, 11 }; - - return Random64[PieceIdx + (PieceTo12[int(p)]^1) * 64 + int(s)]; + low = mid + 1; } + assert(low == high); - uint64_t book_castle_key(const Position& pos) { - - uint64_t result = 0; - - if (pos.can_castle_kingside(WHITE)) - result ^= Random64[CastleIdx + 0]; - - if (pos.can_castle_queenside(WHITE)) - result ^= Random64[CastleIdx + 1]; - - if (pos.can_castle_kingside(BLACK)) - result ^= Random64[CastleIdx + 2]; - - if (pos.can_castle_queenside(BLACK)) - result ^= Random64[CastleIdx + 3]; - - return result; - } - - - uint64_t book_ep_key(const Position& pos) { - - return pos.ep_square() == SQ_NONE ? 0 : Random64[EnPassantIdx + square_file(pos.ep_square())]; - } - - - uint64_t book_color_key(const Position& pos) { - - return pos.side_to_move() == WHITE ? Random64[TurnIdx] : 0; - } + return low; }