From ecd3218b6b24bb54509dbe6e9b24517b7df7390d Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 26 May 2017 08:42:50 +0200 Subject: [PATCH 1/1] History code rewrite (#1122) Rearrange and rename all history heuristic code. Naming is now based on chessprogramming.wikispaces.com conventions and the relations among the various heuristics are now more clear and consistent. No functional change. --- src/movepick.cpp | 16 +++++------ src/movepick.h | 72 +++++++++++++++++++++++++----------------------- src/search.cpp | 51 +++++++++++++++++----------------- src/search.h | 4 +-- src/thread.h | 6 ++-- src/types.h | 4 +++ 6 files changed, 80 insertions(+), 73 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index 6b9f2be0..55c68547 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -143,11 +143,11 @@ void MovePicker::score() { template<> void MovePicker::score() { - const HistoryStats& history = pos.this_thread()->history; + const ButterflyHistory& history = pos.this_thread()->history; - const CounterMoveStats& cmh = *(ss-1)->counterMoves; - const CounterMoveStats& fmh = *(ss-2)->counterMoves; - const CounterMoveStats& fm2 = *(ss-4)->counterMoves; + const PieceToHistory& cmh = *(ss-1)->history; + const PieceToHistory& fmh = *(ss-2)->history; + const PieceToHistory& fm2 = *(ss-4)->history; Color c = pos.side_to_move(); @@ -155,21 +155,21 @@ void MovePicker::score() { m.value = cmh[pos.moved_piece(m)][to_sq(m)] + fmh[pos.moved_piece(m)][to_sq(m)] + fm2[pos.moved_piece(m)][to_sq(m)] - + history.get(c, m); + + history[c][from_to(m)]; } template<> void MovePicker::score() { // Try captures ordered by MVV/LVA, then non-captures ordered by stats heuristics - const HistoryStats& history = pos.this_thread()->history; + const ButterflyHistory& history = pos.this_thread()->history; Color c = pos.side_to_move(); for (auto& m : *this) if (pos.capture(m)) m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - - Value(type_of(pos.moved_piece(m))) + HistoryStats::Max; + - Value(type_of(pos.moved_piece(m))) + (1 << 28); else - m.value = history.get(c, m); + m.value = history[c][from_to(m)]; } diff --git a/src/movepick.h b/src/movepick.h index 97b1b3ab..34cac635 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -21,68 +21,70 @@ #ifndef MOVEPICK_H_INCLUDED #define MOVEPICK_H_INCLUDED -#include // For std::memset +#include #include "movegen.h" #include "position.h" #include "types.h" +/// StatBoards is a generic 2-dimensional array used to store various statistics +template +struct StatBoards : public std::array, Size1> { -/// HistoryStats records how often quiet moves have been successful or unsuccessful -/// during the current search, and is used for reduction and move ordering decisions. -struct HistoryStats { + void fill(const T& v) { + T* p = &(*this)[0][0]; + std::fill(p, p + sizeof(*this) / sizeof(*p), v); + } +}; - static const int Max = 1 << 28; +/// ButterflyBoards are 2 tables (one for each color) indexed by the move's from +/// and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards +typedef StatBoards ButterflyBoards; - int get(Color c, Move m) const { return table[c][from_sq(m)][to_sq(m)]; } - void clear() { std::memset(table, 0, sizeof(table)); } - void update(Color c, Move m, int v) { +/// PieceToBoards are addressed by a move's [piece][to] information +typedef StatBoards PieceToBoards; - Square from = from_sq(m); - Square to = to_sq(m); +/// ButterflyHistory records how often quiet moves have been successful or +/// unsuccessful during the current search, and is used for reduction and move +/// ordering decisions. It uses ButterflyBoards as backing store. +struct ButterflyHistory : public ButterflyBoards { + + void update(Color c, Move m, int v) { const int D = 324; + int& entry = (*this)[c][from_to(m)]; assert(abs(v) <= D); // Consistency check for below formula - table[c][from][to] -= table[c][from][to] * abs(v) / D; - table[c][from][to] += v * 32; - } + entry += v * 32 - entry * abs(v) / D; -private: - int table[COLOR_NB][SQUARE_NB][SQUARE_NB]; + assert(abs(entry) <= 32 * D); + } }; +/// PieceToHistory is like ButterflyHistory, but is based on PieceToBoards +struct PieceToHistory : public PieceToBoards { -/// A template struct, used to generate MoveStats and CounterMoveHistoryStats: -/// MoveStats store the move that refute a previous one. -/// CounterMoveHistoryStats is like HistoryStats, but with two consecutive moves. -/// Entries are stored using only the moving piece and destination square, hence -/// two moves with different origin but same destination and piece will be -/// considered identical. -template -struct Stats { - const T* operator[](Piece pc) const { return table[pc]; } - T* operator[](Piece pc) { return table[pc]; } - void clear() { std::memset(table, 0, sizeof(table)); } - void update(Piece pc, Square to, Move m) { table[pc][to] = m; } void update(Piece pc, Square to, int v) { const int D = 936; + int& entry = (*this)[pc][to]; assert(abs(v) <= D); // Consistency check for below formula - table[pc][to] -= table[pc][to] * abs(v) / D; - table[pc][to] += v * 32; - } + entry += v * 32 - entry * abs(v) / D; -private: - T table[PIECE_NB][SQUARE_NB]; + assert(abs(entry) <= 32 * D); + } }; -typedef Stats MoveStats; -typedef Stats CounterMoveStats; -typedef Stats CounterMoveHistoryStats; +/// CounterMoveStat stores counter moves indexed by [piece][to] of the previous +/// move, see chessprogramming.wikispaces.com/Countermove+Heuristic +typedef StatBoards CounterMoveStat; + +/// CounterMoveHistoryStat is like CounterMoveStat but instead of a move it +/// stores a full history (based on PieceTo boards instead of ButterflyBoards). +typedef StatBoards CounterMoveHistoryStat; /// MovePicker class is used to pick one pseudo legal move at a time from the diff --git a/src/search.cpp b/src/search.cpp index 2e8d5c6f..aafbf80f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -193,14 +193,15 @@ void Search::clear() { for (Thread* th : Threads) { - th->counterMoves.clear(); - th->history.clear(); - th->counterMoveHistory.clear(); th->resetCalls = true; + th->counterMoves.fill(MOVE_NONE); + th->history.fill(0); - CounterMoveStats& cm = th->counterMoveHistory[NO_PIECE][0]; - auto* t = &cm[NO_PIECE][0]; - std::fill(t, t + sizeof(cm)/sizeof(*t), CounterMovePruneThreshold - 1); + for (auto& to : th->counterMoveHistory) + for (auto& h : to) + h.fill(0); + + th->counterMoveHistory[NO_PIECE][0].fill(CounterMovePruneThreshold - 1); } Threads.main()->previousScore = VALUE_INFINITE; @@ -334,7 +335,7 @@ void Thread::search() { std::memset(ss-4, 0, 7 * sizeof(Stack)); for(int i = 4; i > 0; i--) - (ss-i)->counterMoves = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel + (ss-i)->history = &this->counterMoveHistory[NO_PIECE][0]; // Use as sentinel bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; @@ -558,7 +559,7 @@ namespace { Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); moveCount = quietCount = ss->moveCount = 0; - ss->history = 0; + ss->statScore = 0; bestValue = -VALUE_INFINITE; ss->ply = (ss-1)->ply + 1; @@ -607,7 +608,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - ss->counterMoves = &thisThread->counterMoveHistory[NO_PIECE][0]; + ss->history = &thisThread->counterMoveHistory[NO_PIECE][0]; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; Square prevSq = to_sq((ss-1)->currentMove); @@ -750,7 +751,7 @@ namespace { Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min((eval - beta) / PawnValueMg, 3)) * ONE_PLY; ss->currentMove = MOVE_NULL; - ss->counterMoves = &thisThread->counterMoveHistory[NO_PIECE][0]; + ss->history = &thisThread->counterMoveHistory[NO_PIECE][0]; pos.do_null_move(st); Value nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -beta+1) @@ -794,7 +795,7 @@ namespace { if (pos.legal(move)) { ss->currentMove = move; - ss->counterMoves = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)]; + ss->history = &thisThread->counterMoveHistory[pos.moved_piece(move)][to_sq(move)]; pos.do_move(move, st); value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode, false); @@ -818,9 +819,9 @@ namespace { moves_loop: // When in check search starts from here - const CounterMoveStats& cmh = *(ss-1)->counterMoves; - const CounterMoveStats& fmh = *(ss-2)->counterMoves; - const CounterMoveStats& fm2 = *(ss-4)->counterMoves; + const PieceToHistory& cmh = *(ss-1)->history; + const PieceToHistory& fmh = *(ss-2)->history; + const PieceToHistory& fm2 = *(ss-4)->history; MovePicker mp(pos, ttMove, depth, ss); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc @@ -956,7 +957,7 @@ moves_loop: // When in check search starts from here // Update the current move (this must be done after singular extension search) ss->currentMove = move; - ss->counterMoves = &thisThread->counterMoveHistory[moved_piece][to_sq(move)]; + ss->history = &thisThread->counterMoveHistory[moved_piece][to_sq(move)]; // Step 14. Make the move pos.do_move(move, st, givesCheck); @@ -984,21 +985,21 @@ moves_loop: // When in check search starts from here && !pos.see_ge(make_move(to_sq(move), from_sq(move)))) r -= 2 * ONE_PLY; - ss->history = cmh[moved_piece][to_sq(move)] - + fmh[moved_piece][to_sq(move)] - + fm2[moved_piece][to_sq(move)] - + thisThread->history.get(~pos.side_to_move(), move) - - 4000; // Correction factor + ss->statScore = cmh[moved_piece][to_sq(move)] + + fmh[moved_piece][to_sq(move)] + + fm2[moved_piece][to_sq(move)] + + thisThread->history[~pos.side_to_move()][from_to(move)] + - 4000; // Correction factor // Decrease/increase reduction by comparing opponent's stat score - if (ss->history > 0 && (ss-1)->history < 0) + if (ss->statScore > 0 && (ss-1)->statScore < 0) r -= ONE_PLY; - else if (ss->history < 0 && (ss-1)->history > 0) + else if (ss->statScore < 0 && (ss-1)->statScore > 0) r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history - r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->history / 20000) * ONE_PLY); + r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->statScore / 20000) * ONE_PLY); } Depth d = std::max(newDepth - r, ONE_PLY); @@ -1399,7 +1400,7 @@ moves_loop: // When in check search starts from here for (int i : {1, 2, 4}) if (is_ok((ss-i)->currentMove)) - (ss-i)->counterMoves->update(pc, s, bonus); + (ss-i)->history->update(pc, s, bonus); } @@ -1422,7 +1423,7 @@ moves_loop: // When in check search starts from here if (is_ok((ss-1)->currentMove)) { Square prevSq = to_sq((ss-1)->currentMove); - thisThread->counterMoves.update(pos.piece_on(prevSq), prevSq, move); + thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]=move; } // Decrease all the other played quiet moves diff --git a/src/search.h b/src/search.h index 94b59d2b..55a1bf6b 100644 --- a/src/search.h +++ b/src/search.h @@ -38,13 +38,13 @@ namespace Search { struct Stack { Move* pv; - CounterMoveStats* counterMoves; + PieceToHistory* history; int ply; Move currentMove; Move excludedMove; Move killers[2]; Value staticEval; - int history; + int statScore; int moveCount; }; diff --git a/src/thread.h b/src/thread.h index 86e5565f..7666a34f 100644 --- a/src/thread.h +++ b/src/thread.h @@ -68,9 +68,9 @@ public: Depth rootDepth; Depth completedDepth; std::atomic_bool resetCalls; - MoveStats counterMoves; - HistoryStats history; - CounterMoveHistoryStats counterMoveHistory; + CounterMoveStat counterMoves; + ButterflyHistory history; + CounterMoveHistoryStat counterMoveHistory; }; diff --git a/src/types.h b/src/types.h index 2709d77f..c24f2209 100644 --- a/src/types.h +++ b/src/types.h @@ -421,6 +421,10 @@ inline Square to_sq(Move m) { return Square(m & 0x3F); } +inline int from_to(Move m) { + return m & 0xFFF; +} + inline MoveType type_of(Move m) { return MoveType(m & (3 << 14)); } -- 2.39.2