X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.h;h=4c0ad55172d15101466b53babba99c2b9ea90f08;hp=1e1b8e6d1f721a3f5701d4e6e0301cf43b692bc8;hb=HEAD;hpb=438805aee853de93b2ed0f24a51fae873509b885 diff --git a/src/movepick.h b/src/movepick.h index 1e1b8e6d..5077f4e3 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -1,8 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad - Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -21,106 +19,165 @@ #ifndef MOVEPICK_H_INCLUDED #define MOVEPICK_H_INCLUDED -#include // For std::max -#include // For std::memset +#include +#include +#include +#include +#include +#include +#include // IWYU pragma: keep #include "movegen.h" -#include "position.h" -#include "search.h" #include "types.h" +#include "position.h" +namespace Stockfish { -/// The Stats struct stores moves statistics. According to the template parameter -/// the class can store History and Countermoves. History records how often -/// different moves have been successful or unsuccessful during the current search -/// and is used for reduction and move ordering decisions. -/// Countermoves store the move that refute a previous one. 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 { - - static const Value Max = Value(1 << 28); +constexpr int PAWN_HISTORY_SIZE = 512; // has to be a power of 2 - const T* operator[](Piece pc) const { return table[pc]; } - T* operator[](Piece pc) { return table[pc]; } - void clear() { std::memset(table, 0, sizeof(table)); } +static_assert((PAWN_HISTORY_SIZE & (PAWN_HISTORY_SIZE - 1)) == 0, + "PAWN_HISTORY_SIZE has to be a power of 2"); - void update(Piece pc, Square to, Move m) { table[pc][to] = m; } +inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); } - void update(Piece pc, Square to, Value v) { +// StatsEntry stores the stat table value. It is usually a number but could +// be a move or even a nested history. We use a class instead of a naked value +// to directly call history update operator<<() on the entry so to use stats +// tables at caller sites as simple multi-dim arrays. +template +class StatsEntry { - if (abs(int(v)) >= 324) - return; + T entry; - table[pc][to] -= table[pc][to] * abs(int(v)) / (CM ? 936 : 324); - table[pc][to] += int(v) * 32; - } + public: + void operator=(const T& v) { entry = v; } + T* operator&() { return &entry; } + T* operator->() { return &entry; } + operator const T&() const { return entry; } -private: - T table[PIECE_NB][SQUARE_NB]; -}; + void operator<<(int bonus) { + assert(std::abs(bonus) <= D); // Ensure range is [-D, D] + static_assert(D <= std::numeric_limits::max(), "D overflows T"); -typedef Stats MoveStats; -typedef Stats HistoryStats; -typedef Stats CounterMoveStats; -typedef Stats CounterMoveHistoryStats; + entry += bonus - entry * std::abs(bonus) / D; -struct FromToStats { + assert(std::abs(entry) <= D); + } +}; - Value get(Color c, Move m) const { return table[c][from_sq(m)][to_sq(m)]; } - void clear() { std::memset(table, 0, sizeof(table)); } +// Stats is a generic N-dimensional array used to store various statistics. +// The first template parameter T is the base type of the array, and the second +// template parameter D limits the range of updates in [-D, D] when we update +// values with the << operator, while the last parameters (Size and Sizes) +// encode the dimensions of the array. +template +struct Stats: public std::array, Size> { + using stats = Stats; - void update(Color c, Move m, Value v) - { - if (abs(int(v)) >= 324) - return; + void fill(const T& v) { - Square f = from_sq(m); - Square t = to_sq(m); + // For standard-layout 'this' points to the first struct member + assert(std::is_standard_layout_v); - table[c][f][t] -= table[c][f][t] * abs(int(v)) / 324; - table[c][f][t] += int(v) * 32; + using entry = StatsEntry; + entry* p = reinterpret_cast(this); + std::fill(p, p + sizeof(*this) / sizeof(entry), v); } - -private: - Value table[COLOR_NB][SQUARE_NB][SQUARE_NB]; }; -/// MovePicker class is used to pick one pseudo legal move at a time from the -/// current position. The most important method is next_move(), which returns a -/// new pseudo legal move each time it is called, until there are no moves left, -/// when MOVE_NONE is returned. In order to improve the efficiency of the alpha -/// beta algorithm, MovePicker attempts to return the moves which are most likely -/// to get a cut-off first. +template +struct Stats: public std::array, Size> {}; + +// In stats table, D=0 means that the template parameter is not used +enum StatsParams { + NOT_USED = 0 +}; +enum StatsType { + NoCaptures, + Captures +}; +// 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 2 tables (one for each color) indexed by the move's from and to squares, +// see www.chessprogramming.org/Butterfly_Boards (~11 elo) +using ButterflyHistory = Stats; + +// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous +// move, see www.chessprogramming.org/Countermove_Heuristic +using CounterMoveHistory = Stats; + +// CapturePieceToHistory is addressed by a move's [piece][to][captured piece type] +using CapturePieceToHistory = Stats; + +// PieceToHistory is like ButterflyHistory but is addressed by a move's [piece][to] +using PieceToHistory = Stats; + +// ContinuationHistory is the combined history of a given pair of moves, usually +// the current one given a previous one. The nested history table is based on +// PieceToHistory instead of ButterflyBoards. +// (~63 elo) +using ContinuationHistory = Stats; + +// PawnHistory is addressed by the pawn structure and a move's [piece][to] +using PawnHistory = Stats; + +// MovePicker class is used to pick one pseudo-legal move at a time from the +// current position. The most important method is next_move(), which returns a +// new pseudo-legal move each time it is called, until there are no moves left, +// when MOVE_NONE is returned. In order to improve the efficiency of the +// alpha-beta algorithm, MovePicker attempts to return the moves which are most +// likely to get a cut-off first. class MovePicker { -public: - MovePicker(const MovePicker&) = delete; - MovePicker& operator=(const MovePicker&) = delete; - - MovePicker(const Position&, Move, Value); - MovePicker(const Position&, Move, Depth, Square); - MovePicker(const Position&, Move, Depth, Search::Stack*); - - Move next_move(); - int see_sign() const; - -private: - template void score(); - ExtMove* begin() { return cur; } - ExtMove* end() { return endMoves; } - - const Position& pos; - const Search::Stack* ss; - Move countermove; - Depth depth; - Move ttMove; - Square recaptureSquare; - Value threshold; - int stage; - ExtMove* cur, *endMoves, *endBadCaptures; - ExtMove moves[MAX_MOVES]; + + enum PickType { + Next, + Best + }; + + public: + MovePicker(const MovePicker&) = delete; + MovePicker& operator=(const MovePicker&) = delete; + MovePicker(const Position&, + Move, + Depth, + const ButterflyHistory*, + const CapturePieceToHistory*, + const PieceToHistory**, + const PawnHistory*, + Move, + const Move*); + MovePicker(const Position&, + Move, + Depth, + const ButterflyHistory*, + const CapturePieceToHistory*, + const PieceToHistory**, + const PawnHistory*); + MovePicker(const Position&, Move, Value, const CapturePieceToHistory*); + Move next_move(bool skipQuiets = false); + + private: + template + Move select(Pred); + template + void score(); + ExtMove* begin() { return cur; } + ExtMove* end() { return endMoves; } + + const Position& pos; + const ButterflyHistory* mainHistory; + const CapturePieceToHistory* captureHistory; + const PieceToHistory** continuationHistory; + const PawnHistory* pawnHistory; + Move ttMove; + ExtMove refutations[3], *cur, *endMoves, *endBadCaptures; + int stage; + Value threshold; + Depth depth; + ExtMove moves[MAX_MOVES]; }; -#endif // #ifndef MOVEPICK_H_INCLUDED +} // namespace Stockfish + +#endif // #ifndef MOVEPICK_H_INCLUDED