X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbook.cpp;h=caf2b0663ec76987720231e29360c6d434238d27;hp=a98acf491f24dba4f4a29562d6ddce7d730f06b9;hb=45b0aea875860e9f0fe2d0435ee6163906639194;hpb=afadc33fb430abd2ba2783a62180cf971b13652f
diff --git a/src/book.cpp b/src/book.cpp
index a98acf49..caf2b066 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 Marco Costalba
+ Copyright (C) 2008-2013 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,45 +17,44 @@
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 "mersenne.h"
+#include "misc.h"
#include "movegen.h"
-
-////
-//// Global variables
-////
-
-Book OpeningBook;
-
-
-////
-//// Local definitions
-////
+using namespace std;
namespace {
- /// Book entry size in bytes
- const int EntrySize = 16;
-
-
- /// Random numbers from PolyGlot, used to compute book hash keys.
+ // 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 Entry {
+ uint64_t key;
+ uint16_t move;
+ uint16_t count;
+ uint32_t learn;
+ };
- const uint64_t Random64[781] = {
+ // Random numbers from PolyGlot, used to compute book hash keys
+ const union {
+ Key PolyGlotRandoms[781];
+ struct {
+ Key psq[12][64]; // [piece][square]
+ Key castle[4]; // [castle right]
+ Key enpassant[8]; // [file]
+ Key turn;
+ } Zobrist;
+ } PG = {{
0x9D39247E33776D41ULL, 0x2AF7398005AAA5C7ULL, 0x44DB015024623547ULL,
0x9C15F73E62A76AE2ULL, 0x75834465489C0C89ULL, 0x3290AC3A203001BFULL,
0x0FBBAD1F61042279ULL, 0xE83A908FF2FB60CAULL, 0x0D7E765D58755C10ULL,
@@ -317,295 +316,163 @@ namespace {
0x003A93D8B2806962ULL, 0x1C99DED33CB890A1ULL, 0xCF3145DE0ADD4289ULL,
0xD0E4427A5514FB72ULL, 0x77C621CC9FB3A483ULL, 0x67A34DAC4356550BULL,
0xF8D626AAAF278509ULL
- };
+ }};
+ // polyglot_key() returns the PolyGlot hash key of the given position
+ Key polyglot_key(const Position& pos) {
- /// Indices to the Random64[] array
-
- const int RandomPiece = 0;
- const int RandomCastle = 768;
- const int RandomEnPassant = 772;
- const int RandomTurn = 780;
+ Key key = 0;
+ Bitboard b = pos.pieces();
+ while (b)
+ {
+ Square s = pop_lsb(&b);
+ Piece p = pos.piece_on(s);
- /// Prototypes
+ // PolyGlot pieces are: BP = 0, WP = 1, BN = 2, ... BK = 10, WK = 11
+ key ^= PG.Zobrist.psq[2 * (type_of(p) - 1) + (color_of(p) == WHITE)][s];
+ }
- 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);
+ b = pos.can_castle(ALL_CASTLES);
- uint16_t read_integer16(std::ifstream& file);
- uint64_t read_integer64(std::ifstream& file);
- uint64_t read_integer(std::ifstream& file, int size);
-}
+ while (b)
+ key ^= PG.Zobrist.castle[pop_lsb(&b)];
+ if (pos.ep_square() != SQ_NONE)
+ key ^= PG.Zobrist.enpassant[file_of(pos.ep_square())];
-////
-//// Functions
-////
+ if (pos.side_to_move() == WHITE)
+ key ^= PG.Zobrist.turn;
+ return key;
+ }
-/// Constructor
+} // namespace
-Book::Book() : bookSize(0) {}
+PolyglotBook::PolyglotBook() : rkiss(Time::now() % 10000) {}
+PolyglotBook::~PolyglotBook() { if (is_open()) close(); }
-/// Book::open() opens a book file with a given file name
-void Book::open(const std::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.
- fileName = fName;
- bookFile.open(fileName.c_str(), std::ifstream::in | std::ifstream::binary);
- if (!bookFile.is_open())
- return;
+template PolyglotBook& PolyglotBook::operator>>(T& n) {
- // get the book size in number of entries
- bookFile.seekg(0, std::ios::end);
- bookSize = bookFile.tellg() / EntrySize;
- bookFile.seekg(0, std::ios::beg);
+ n = 0;
+ for (size_t i = 0; i < sizeof(T); i++)
+ n = T((n << 8) + ifstream::get());
- if (!bookFile.good())
- {
- std::cerr << "Failed to open book file " << fileName << std::endl;
- bookFile.close();
- exit(EXIT_FAILURE);
- }
+ return *this;
}
-
-/// Book::close() closes the currently open book file
-
-void Book::close() {
-
- if (bookFile.is_open())
- bookFile.close();
+template<> PolyglotBook& PolyglotBook::operator>>(Entry& e) {
+ return *this >> e.key >> e.move >> e.count >> e.learn;
}
-/// Book::is_open() tests whether a book file has been opened.
-
-bool Book::is_open() const {
-
- return bookFile.is_open() && bookSize != 0;
-}
+/// open() tries to open a book file with the given name after closing any
+/// exsisting one.
+bool PolyglotBook::open(const char* fName) {
-/// Book::file_name() returns the file name of the currently active book,
-/// or the empty string if no book is open.
+ if (is_open()) // Cannot close an already closed file
+ close();
-const std::string Book::file_name() const {
+ ifstream::open(fName, ifstream::in | ifstream::binary);
- return is_open() ? fileName : "";
+ 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) const {
+Move PolyglotBook::probe(const Position& pos, const string& fName, bool pickBest) {
- if (!is_open())
+ if (fileName != fName && !open(fName.c_str()))
return MOVE_NONE;
- int bookMove = 0, scoresSum = 0;
- uint64_t key = book_key(pos);
- BookEntry entry;
-
- // Choose a book move among the possible moves for the given position
- for (int i = find_key(key); i < bookSize; i++)
- {
- read_entry(entry, i);
- if (entry.key != key)
- break;
+ Entry e;
+ uint16_t best = 0;
+ unsigned sum = 0;
+ Move move = MOVE_NONE;
+ Key key = polyglot_key(pos);
- int score = entry.count;
+ seekg(find_first(key) * sizeof(Entry), ios_base::beg);
- assert(score > 0);
+ while (*this >> e, e.key == key && good())
+ {
+ 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 (int(genrand_int32() % 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;
- MoveStack moves[256];
- int n = generate_legal_moves(pos, moves);
- for (int j = 0; j < n; j++)
- if ((int(moves[j].move) & 07777) == bookMove)
- return moves[j].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 it(pos); *it; ++it)
+ if (move == (*it ^ type_of(*it)))
+ return *it;
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.
-
-int Book::find_key(uint64_t key) const {
-
- int left, right, mid;
- BookEntry entry;
-
- // Binary search (finds the leftmost entry)
- left = 0;
- right = bookSize - 1;
-
- assert(left <= right);
-
- while(left < right)
- {
- mid = (left + right) / 2;
-
- assert(mid >= left && mid < right);
-
- read_entry(entry, mid);
- if (key <= entry.key)
- right = mid;
- else
- left = mid + 1;
- }
- assert(left == right);
+/// 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.
- read_entry(entry, left);
- return (entry.key == key)? left : bookSize;
-}
+size_t PolyglotBook::find_first(Key key) {
+ seekg(0, ios::end); // Move pointer to end, so tellg() gets file's size
-/// 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.
+ size_t low = 0, mid, high = (size_t)tellg() / sizeof(Entry) - 1;
+ Entry e;
-void Book::read_entry(BookEntry& entry, int n) const {
+ assert(low <= high);
- assert(n >= 0 && n < bookSize);
- assert(is_open());
-
- bookFile.seekg(n * EntrySize, std::ios_base::beg);
- if (!bookFile.good())
+ while (low < high && good())
{
- std::cerr << "Failed to read book entry at index " << n << std::endl;
- bookFile.close();
- exit(EXIT_FAILURE);
- }
- entry.key = read_integer64(bookFile);
- entry.move = read_integer16(bookFile);
- entry.count = read_integer16(bookFile);
- entry.n = read_integer16(bookFile);
- entry.sum = read_integer16(bookFile);
-}
-
-
-////
-//// Local definitions
-////
+ mid = (low + high) / 2;
-namespace {
-
- uint64_t book_key(const Position& pos) {
-
- uint64_t result = 0ULL;
-
- for (Color c = WHITE; c <= BLACK; c++)
- {
- Bitboard b = pos.pieces_of_color(c);
-
- while (b != EmptyBoardBB)
- {
- Square s = pop_1st_bit(&b);
- Piece p = pos.piece_on(s);
-
- assert(piece_is_ok(p));
- assert(color_of_piece(p) == c);
-
- result ^= book_piece_key(p, 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[RandomPiece + (PieceTo12[int(p)]^1) * 64 + int(s)];
- }
-
-
- uint64_t book_castle_key(const Position& pos) {
-
- uint64_t result = 0ULL;
-
- if (pos.can_castle_kingside(WHITE))
- result ^= Random64[RandomCastle+0];
-
- if (pos.can_castle_queenside(WHITE))
- result ^= Random64[RandomCastle+1];
-
- if (pos.can_castle_kingside(BLACK))
- result ^= Random64[RandomCastle+2];
+ assert(mid >= low && mid < high);
- if (pos.can_castle_queenside(BLACK))
- result ^= Random64[RandomCastle+3];
+ seekg(mid * sizeof(Entry), ios_base::beg);
+ *this >> e;
- return result;
- }
-
-
- uint64_t book_ep_key(const Position& pos) {
- return (pos.ep_square() == SQ_NONE ? 0ULL : Random64[RandomEnPassant + square_file(pos.ep_square())]);
- }
-
-
- uint64_t book_color_key(const Position& pos) {
- return (pos.side_to_move() == WHITE ? Random64[RandomTurn] : 0ULL);
- }
-
-
- uint16_t read_integer16(std::ifstream& file) {
-
- uint64_t n = read_integer(file, 2);
- assert(n == (uint16_t)n);
- return (uint16_t)n;
- }
-
-
- uint64_t read_integer64(std::ifstream& file) {
-
- return read_integer(file, 8);
+ if (key <= e.key)
+ high = mid;
+ else
+ low = mid + 1;
}
+ assert(low == high);
- uint64_t read_integer(std::ifstream& file, int size) {
-
- char buf[8];
- file.read(buf, size);
-
- if (!file.good())
- {
- std::cerr << "Failed to read " << size << " bytes from book file" << std::endl;
- file.close();
- exit(EXIT_FAILURE);
- }
-
- // Numbers are stored on disk in big endian format
- uint64_t n = 0ULL;
- for (int i = 0; i < size; i++)
- n = (n << 8) + (unsigned char)buf[i];
-
- return n;
- }
+ return low;
}