/*
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
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
+ by Fabien Letouzey. PolyGlot is available under the GNU General
Public License, and can be downloaded from http://wbec-ridderkerk.nl
*/
-
-////
-//// Includes
-////
-
+#include <algorithm>
#include <cassert>
+#include <iostream>
#include "book.h"
+#include "misc.h"
#include "movegen.h"
using namespace std;
-////
-//// Local definitions
-////
-
namespace {
- // Book entry size in bytes
- const int EntrySize = 16;
-
// 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,
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 + 0;
+ const Key* ZobCastle = PolyGlotRandoms + 768;
+ const Key* ZobEnPassant = PolyGlotRandoms + 772;
+ const Key* ZobTurn = PolyGlotRandoms + 780;
+ // PieceOffset is calculated as 64 * (PolyPiece ^ 1) where PolyPiece
+ // is: BP = 0, WP = 1, BN = 2, WN = 3 ... BK = 10, WK = 11
+ const int PieceOffset[] = { 0, 64, 192, 320, 448, 576, 704, 0,
+ 0, 0, 128, 256, 384, 512, 640 };
-////
-//// 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.occupied_squares();
- for (int i = abs(get_system_time() % 10000); i > 0; i--)
- RKiss.rand<unsigned>();
-}
+ while (b)
+ {
+ Square s = pop_1st_bit(&b);
+ key ^= ZobPiece[PieceOffset[pos.piece_on(s)] + s];
+ }
+ b = (pos.can_castle(WHITE_OO) << 0) | (pos.can_castle(WHITE_OOO) << 1)
+ | (pos.can_castle(BLACK_OO) << 2) | (pos.can_castle(BLACK_OOO) << 3);
-/// Destructor. Be sure file is closed before we leave.
+ while (b)
+ key ^= ZobCastle[pop_1st_bit(&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() {
+Book::Book() : size(0) {
- if (is_open())
- ifstream::close();
+ for (int i = abs(system_time() % 10000); i > 0; i--)
+ RKiss.rand<unsigned>(); // Make random number generation less deterministic
}
+Book::~Book() { if (is_open()) close(); }
-/// Book::open() opens a book file with a given file name
-void Book::open(const string& fName) {
+/// Book::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<typename T> Book& Book::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);
-
- if (good())
- return;
- }
- cerr << "Failed to open book file " << fileName << endl;
- Application::exit_with_failure();
+ return *this;
}
-
-/// Book::file_name() returns the file name of the currently active book,
-/// or the empty string if no book is open.
-
-const string Book::file_name() { // Not const to compile on HP-UX 11.X
-
- return is_open() ? fileName : "";
+template<> Book& Book::operator>>(BookEntry& e) {
+ return *this >> e.key >> e.move >> e.count >> e.learn;
}
-/// Book::get_move() gets a book move for a given position. Returns
-/// MOVE_NONE if no book move is found.
-
-Move Book::get_move(const Position& pos, bool findBestMove) {
-
- if (!is_open() || bookSize == 0)
- return MOVE_NONE;
-
- BookEntry entry;
- int bookMove = MOVE_NONE;
- unsigned scoresSum = 0, bestScore = 0;
- 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++)
- {
- 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;
- }
-
- // 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;
- }
- if (!bookMove)
- 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;
-
- return MOVE_NONE;
-}
+/// Book::open() tries to open a book file with the given name after closing
+/// any exsisting one.
+bool Book::open(const char* fName) {
-/// 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.
+ fileName = "";
-int Book::find_key(uint64_t key) {
+ if (is_open()) // Cannot close an already closed file
+ close();
- int left, right, mid;
- BookEntry entry;
+ ifstream::open(fName, ifstream::in | ifstream::binary | ios::ate);
- // Binary search (finds the leftmost entry)
- left = 0;
- right = bookSize - 1;
+ if (!is_open())
+ return false; // Silently fail if the file is not found
- assert(left <= right);
+ // Get the book size in number of entries, we are already at the end of file
+ size = (size_t)tellg() / sizeof(BookEntry);
- while (left < right)
+ if (!good())
{
- mid = (left + right) / 2;
-
- assert(mid >= left && mid < right);
-
- read_entry(entry, mid);
-
- if (key <= entry.key)
- right = mid;
- else
- left = mid + 1;
+ cerr << "Failed to open book file " << fName << endl;
+ exit(EXIT_FAILURE);
}
- assert(left == right);
-
- read_entry(entry, left);
- return entry.key == key ? left : bookSize;
+ fileName = fName; // Set only if successful
+ return true;
}
-/// 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.
+/// Book::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.
-void Book::read_entry(BookEntry& entry, int idx) {
+Move Book::probe(const Position& pos, const string& fName, bool pickBest) {
- assert(idx >= 0 && idx < bookSize);
- assert(is_open());
+ BookEntry e;
+ uint16_t best = 0;
+ unsigned sum = 0;
+ Move move = MOVE_NONE;
+ uint64_t key = book_key(pos);
- seekg(idx * EntrySize, ios_base::beg);
+ if (fileName != fName && !open(fName.c_str()))
+ return MOVE_NONE;
- *this >> entry;
+ binary_search(key);
- if (!good())
+ while (*this >> e, e.key == key && good())
{
- cerr << "Failed to read book entry at index " << idx << endl;
- Application::exit_with_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);
- }
+ best = max(best, e.count);
+ sum += e.count;
- result ^= book_castle_key(pos);
- result ^= book_ep_key(pos);
- result ^= book_color_key(pos);
- return result;
+ // 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 ( (RKiss.rand<unsigned>() % sum < e.count)
+ || (pickBest && e.count == best))
+ move = Move(e.move);
}
+ if (!move)
+ return MOVE_NONE;
- 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)];
- }
+ // 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_promotion(from_sq(move), to_sq(move), PieceType(pt + 1));
+
+ // Add 'special move' flags and verify it is legal
+ for (MoveList<MV_LEGAL> ml(pos); !ml.end(); ++ml)
+ if (move == (ml.move() & 0x3FFF))
+ return ml.move();
+ return MOVE_NONE;
+}
- uint64_t book_castle_key(const Position& pos) {
- uint64_t result = 0;
+/// Book::binary_search() takes a book key as input, and does a binary search
+/// through the book file for the given key. File stream current position is set
+/// to the leftmost book entry with the same key as the input.
- if (pos.can_castle_kingside(WHITE))
- result ^= Random64[CastleIdx + 0];
+void Book::binary_search(uint64_t key) {
- if (pos.can_castle_queenside(WHITE))
- result ^= Random64[CastleIdx + 1];
+ size_t low, high, mid;
+ BookEntry e;
- if (pos.can_castle_kingside(BLACK))
- result ^= Random64[CastleIdx + 2];
+ low = 0;
+ high = size - 1;
- if (pos.can_castle_queenside(BLACK))
- result ^= Random64[CastleIdx + 3];
+ assert(low <= high);
- return result;
- }
+ while (low < high && good())
+ {
+ mid = (low + high) / 2;
+ assert(mid >= low && mid < high);
- uint64_t book_ep_key(const Position& pos) {
+ seekg(mid * sizeof(BookEntry), ios_base::beg);
+ *this >> e;
- return pos.ep_square() == SQ_NONE ? 0 : Random64[EnPassantIdx + square_file(pos.ep_square())];
+ if (key <= e.key)
+ high = mid;
+ else
+ low = mid + 1;
}
+ assert(low == high);
- uint64_t book_color_key(const Position& pos) {
-
- return pos.side_to_move() == WHITE ? Random64[TurnIdx] : 0;
- }
+ seekg(low * sizeof(BookEntry), ios_base::beg);
}
projects / stockfish / blobdiff