X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.h;h=65e93dda6fe3c1eb0d0b52ce7d66c1609e47c502;hb=2d0237db3f0e596fb06e3ffbadba84dcc4e018f6;hp=41a83604e09e99b768360ebb66b382d7510918a8;hpb=ae6a4ebf1f44cb05e96f8f33342ec281b41b0cc0;p=stockfish diff --git a/src/movepick.h b/src/movepick.h index 41a83604..65e93dda 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-2017 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 @@ -22,111 +20,154 @@ #define MOVEPICK_H_INCLUDED #include +#include +#include +#include +#include +#include // IWYU pragma: keep #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> { +namespace Stockfish { +class Position; - void fill(const T& v) { - T* p = &(*this)[0][0]; - std::fill(p, p + sizeof(*this) / sizeof(*p), v); - } -}; - -/// 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; - -/// PieceToBoards are addressed by a move's [piece][to] information -typedef StatBoards PieceToBoards; +// 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 { -/// 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 { + T entry; - void update(Color c, Move m, int bonus) { + public: + void operator=(const T& v) { entry = v; } + T* operator&() { return &entry; } + T* operator->() { return &entry; } + operator const T&() const { return entry; } - const int D = 324; - auto& entry = (*this)[c][from_to(m)]; + void operator<<(int bonus) { + assert(abs(bonus) <= D); // Ensure range is [-D, D] + static_assert(D <= std::numeric_limits::max(), "D overflows T"); - assert(abs(bonus) <= D); // Consistency check for below formula - assert([&]{ - int v = entry + bonus * 32 - entry * abs(bonus) / D; - return INT16_MIN < v && v < INT16_MAX; - }()); + entry += (bonus * D - entry * abs(bonus)) / (D * 5 / 4); - entry += bonus * 32 - entry * abs(bonus) / D; - - assert(abs(entry) <= 32 * D); - } + assert(abs(entry) <= D); + } }; -/// PieceToHistory is like ButterflyHistory, but is based on PieceToBoards -struct PieceToHistory : public PieceToBoards { +// 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(Piece pc, Square to, int bonus) { + void fill(const T& v) { - const int D = 936; - auto& entry = (*this)[pc][to]; + // For standard-layout 'this' points to the first struct member + assert(std::is_standard_layout_v); - assert(abs(bonus) <= D); // Consistency check for below formula - assert([&]{ - int v = entry + bonus * 32 - entry * abs(bonus) / D; - return INT16_MIN < v && v < INT16_MAX; - }()); + using entry = StatsEntry; + entry* p = reinterpret_cast(this); + std::fill(p, p + sizeof(*this) / sizeof(entry), v); + } +}; - entry += bonus * 32 - entry * abs(bonus) / D; +template +struct Stats: public std::array, Size> {}; - assert(abs(entry) <= 32 * D); - } +// 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; -/// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous -/// move, see chessprogramming.wikispaces.com/Countermove+Heuristic -typedef StatBoards CounterMoveHistory; +// CapturePieceToHistory is addressed by a move's [piece][to][captured piece type] +using CapturePieceToHistory = Stats; -/// ContinuationHistory is the history of a given pair of moves, usually the -/// current one given a previous one. History table is based on PieceToBoards -/// instead of ButterflyBoards. -typedef StatBoards ContinuationHistory; +// 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; -/// 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. +// 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, const ButterflyHistory*, const PieceToHistory**, Square); - MovePicker(const Position&, Move, Depth, const ButterflyHistory*, const PieceToHistory**, Move, Move*); - Move next_move(bool skipQuiets = false); - -private: - template void score(); - ExtMove* begin() { return cur; } - ExtMove* end() { return endMoves; } - - const Position& pos; - const ButterflyHistory* mainHistory; - const PieceToHistory** contHistory; - Move ttMove, countermove, killers[2]; - ExtMove *cur, *endMoves, *endBadCaptures; - int stage; - Square recaptureSquare; - Value threshold; - Depth depth; - 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**, + Move, + const Move*); + MovePicker(const Position&, + Move, + Depth, + const ButterflyHistory*, + const CapturePieceToHistory*, + const PieceToHistory**, + Square); + 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; + Move ttMove; + ExtMove refutations[3], *cur, *endMoves, *endBadCaptures; + int stage; + Square recaptureSquare; + Value threshold; + Depth depth; + ExtMove moves[MAX_MOVES]; }; -#endif // #ifndef MOVEPICK_H_INCLUDED +} // namespace Stockfish + +#endif // #ifndef MOVEPICK_H_INCLUDED