/*
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-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
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-
/*
The code in this file is based on the opening book code in PolyGlot
by Fabien Letouzey. PolyGlot is available under the GNU General
Public License, and can be downloaded from http://wbec-ridderkerk.nl
*/
+#include <algorithm>
#include <cassert>
#include <iostream>
#include "book.h"
+#include "misc.h"
#include "movegen.h"
using namespace std;
namespace {
+ // 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;
+ };
+
// Random numbers from PolyGlot, used to compute book hash keys
- const uint64_t Random64[781] = {
+ 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,
0x003A93D8B2806962ULL, 0x1C99DED33CB890A1ULL, 0xCF3145DE0ADD4289ULL,
0xD0E4427A5514FB72ULL, 0x77C621CC9FB3A483ULL, 0x67A34DAC4356550BULL,
0xF8D626AAAF278509ULL
- };
-
- // Indices to the Random64[] array
- const int PieceIdx = 0;
- const int CastleIdx = 768;
- const int EnPassantIdx = 772;
- const int TurnIdx = 780;
-
- // book_key() builds up a PolyGlot hash key out of a position
- uint64_t book_key(const Position& pos) {
+ }};
- // Piece offset is calculated as (64 * PolyPieceType + square), where
- // PolyPieceType is: BP = 0, WP = 1, BN = 2, WN = 3 .... BK = 10, WK = 11
- static const int PieceToPoly[] = { 0, 1, 3, 5, 7, 9, 11, 0, 0, 0, 2, 4, 6, 8, 10 };
+ // polyglot_key() returns the PolyGlot hash key of the given position
+ Key polyglot_key(const Position& pos) {
- uint64_t result = 0;
- Bitboard b = pos.occupied_squares();
+ Key key = 0;
+ Bitboard b = pos.pieces();
while (b)
{
- Square s = pop_1st_bit(&b);
- int p = PieceToPoly[int(pos.piece_on(s))];
- result ^= Random64[PieceIdx + 64 * p + int(s)];
- }
-
- if (pos.can_castle_kingside(WHITE))
- result ^= Random64[CastleIdx + 0];
+ Square s = pop_lsb(&b);
+ Piece p = pos.piece_on(s);
- if (pos.can_castle_queenside(WHITE))
- result ^= Random64[CastleIdx + 1];
+ // 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];
+ }
- if (pos.can_castle_kingside(BLACK))
- result ^= Random64[CastleIdx + 2];
+ b = pos.can_castle(ALL_CASTLES);
- if (pos.can_castle_queenside(BLACK))
- result ^= Random64[CastleIdx + 3];
+ while (b)
+ key ^= PG.Zobrist.castle[pop_lsb(&b)];
if (pos.ep_square() != SQ_NONE)
- result ^= Random64[EnPassantIdx + square_file(pos.ep_square())];
+ key ^= PG.Zobrist.enpassant[file_of(pos.ep_square())];
if (pos.side_to_move() == WHITE)
- result ^= Random64[TurnIdx];
+ key ^= PG.Zobrist.turn;
- return result;
+ return key;
}
-}
+} // namespace
+PolyglotBook::PolyglotBook() : rkiss(Time::now() % 10000) {}
-/// Book c'tor. Make random number generation less deterministic, for book moves
-Book::Book() {
+PolyglotBook::~PolyglotBook() { if (is_open()) close(); }
- for (int i = abs(get_system_time() % 10000); i > 0; i--)
- RKiss.rand<unsigned>();
-}
+/// 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.
-/// Book destructor. Be sure file is closed before we leave.
+template<typename T> PolyglotBook& PolyglotBook::operator>>(T& n) {
-Book::~Book() {
+ n = 0;
+ for (size_t i = 0; i < sizeof(T); i++)
+ n = T((n << 8) + ifstream::get());
- close();
+ return *this;
}
-
-/// 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.
-
-void Book::close() {
-
- if (bookFile.is_open())
- bookFile.close();
-
- bookName = "";
+template<> PolyglotBook& PolyglotBook::operator>>(Entry& e) {
+ return *this >> e.key >> e.move >> e.count >> e.learn;
}
-/// Book::open() opens a book file with a given file name
-
-void Book::open(const string& fileName) {
-
- // Close old file before opening the new
- close();
+/// open() tries to open a book file with the given name after closing any
+/// exsisting one.
- bookFile.open(fileName.c_str(), ifstream::in | ifstream::binary);
+bool PolyglotBook::open(const char* fName) {
- // Silently return when asked to open a non-exsistent file
- if (!bookFile.is_open())
- return;
+ if (is_open()) // Cannot close an already closed file
+ close();
- // Get the book size in number of entries
- bookFile.seekg(0, ios::end);
- bookSize = long(bookFile.tellg()) / sizeof(BookEntry);
-
- if (!bookFile.good())
- {
- cerr << "Failed to open book file " << fileName << endl;
- exit(EXIT_FAILURE);
- }
+ ifstream::open(fName, ifstream::in | ifstream::binary);
- // Set only if successful
- bookName = 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. If findBestMove is true then
-/// return always the highest rated book move.
+/// 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 (!bookFile.is_open() || bookSize == 0)
+ if (fileName != fName && !open(fName.c_str()))
return MOVE_NONE;
- BookEntry entry;
- int bookMove = MOVE_NONE;
- unsigned score, scoresSum = 0, bestScore = 0;
- uint64_t key = book_key(pos);
+ Entry e;
+ uint16_t best = 0;
+ unsigned sum = 0;
+ Move move = MOVE_NONE;
+ Key key = polyglot_key(pos);
- // Choose a book move among the possible moves for the given position
- for (int idx = find_entry(key); idx < bookSize; idx++)
+ seekg(find_first(key) * sizeof(Entry), ios_base::beg);
+
+ while (*this >> e, e.key == key && good())
{
- entry = read_entry(idx);
-
- if (entry.key != key)
- break;
-
- score = entry.count;
-
- if (!findBestMove)
- {
- // 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<unsigned>() % scoresSum < score)
- bookMove = entry.move;
- }
- else if (score > bestScore)
- {
- bestScore = score;
- bookMove = entry.move;
- }
+ 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 higher probability to be choosen than a move
+ // with lower score. Note that first entry is always chosen.
+ if ( (sum && rkiss.rand<unsigned>() % sum < e.count)
+ || (pickBest && e.count == best))
+ move = Move(e.move);
}
+ if (!move)
+ return MOVE_NONE;
+
// 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-13-14: promotion piece (from KNIGHT == 1 to QUEEN == 4)
+ // 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 other cases we can directly compare with a Move after having
- // masked out special Move's flags that are not supported by PolyGlot.
- int p = (bookMove >> 12) & 7;
-
- if (p)
- bookMove = int(make_promotion_move(move_from(Move(bookMove)),
- move_to(Move(bookMove)), PieceType(p + 1)));
-
- // Verify the book move (if any) is legal
- MoveStack mlist[MAX_MOVES];
- MoveStack* last = generate<MV_LEGAL>(pos, mlist);
- for (MoveStack* cur = mlist; cur != last; cur++)
- if ((int(cur->move) & ~(3 << 14)) == bookMove) // Mask out special flags
- return cur->move;
+ // 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<PROMOTION>(from_sq(move), to_sq(move), PieceType(pt + 1));
+
+ // Add 'special move' flags and verify it is legal
+ for (MoveList<LEGAL> it(pos); *it; ++it)
+ if (move == (*it ^ type_of(*it)))
+ return *it;
return MOVE_NONE;
}
-/// Book::find_entry() 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_entry(uint64_t key) {
+size_t PolyglotBook::find_first(Key key) {
- int left, right, mid;
+ 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(Entry) - 1;
+ Entry 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);
- if (key <= read_entry(mid).key)
- right = mid;
+ seekg(mid * sizeof(Entry), ios_base::beg);
+ *this >> e;
+
+ if (key <= e.key)
+ high = mid;
else
- left = mid + 1;
+ low = mid + 1;
}
- assert(left == right);
-
- return read_entry(left).key == key ? left : bookSize;
-}
-
-
-/// Book::operator>>() reads sizeof(T) chars from the file's binary byte
-/// stream and converts them in a number of type T.
-template<typename T>
-Book& Book::operator>>(T& n) {
-
- n = 0;
-
- for (size_t i = 0; i < sizeof(T); i++)
- n = (n << 8) + (T)bookFile.get();
-
- return *this;
-}
-
-
-/// Book::read_entry() takes an integer index, and returns the BookEntry
-/// at the given index in the book file.
-
-BookEntry Book::read_entry(int idx) {
+ assert(low == high);
- assert(idx >= 0 && idx < bookSize);
- assert(bookFile.is_open());
-
- BookEntry e;
-
- bookFile.seekg(idx * sizeof(BookEntry), ios_base::beg);
-
- *this >> e.key >> e.move >> e.count >> e.learn;
-
- if (!bookFile.good())
- {
- cerr << "Failed to read book entry at index " << idx << endl;
- exit(EXIT_FAILURE);
- }
- return e;
+ return low;
}
projects / stockfish / blobdiff