X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.h;h=7828fa19d975fb9f5e12f4e8a652d487037e6804;hb=15d47a2b3821b92c4d048f39f7f43c301299d365;hp=34cac635cfb01d83d763e8bc55850b1eee15c91e;hpb=ecd3218b6b24bb54509dbe6e9b24517b7df7390d;p=stockfish diff --git a/src/movepick.h b/src/movepick.h index 34cac635..7828fa19 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,106 +20,163 @@ #define MOVEPICK_H_INCLUDED #include +#include +#include +#include +#include +#include // IWYU pragma: keep #include "movegen.h" -#include "position.h" #include "types.h" +#include "position.h" -/// StatBoards is a generic 2-dimensional array used to store various statistics -template -struct StatBoards : public std::array, Size1> { +namespace Stockfish { - void fill(const T& v) { - T* p = &(*this)[0][0]; - std::fill(p, p + sizeof(*this) / sizeof(*p), v); - } -}; +constexpr int PAWN_HISTORY_SIZE = 512; // has to be a power of 2 -/// 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; +static_assert((PAWN_HISTORY_SIZE & (PAWN_HISTORY_SIZE - 1)) == 0, + "PAWN_HISTORY_SIZE has to be a power of 2"); -/// PieceToBoards are addressed by a move's [piece][to] information -typedef StatBoards PieceToBoards; +inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); } -/// 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 { +// 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 { - void update(Color c, Move m, int v) { + T entry; - const int D = 324; - int& entry = (*this)[c][from_to(m)]; + public: + void operator=(const T& v) { entry = v; } + T* operator&() { return &entry; } + T* operator->() { return &entry; } + operator const T&() const { return entry; } - assert(abs(v) <= D); // Consistency check for below formula + void operator<<(int bonus) { + assert(abs(bonus) <= D); // Ensure range is [-D, D] + static_assert(D <= std::numeric_limits::max(), "D overflows T"); - entry += v * 32 - entry * abs(v) / D; + entry += bonus - 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 v) { + void fill(const T& v) { - const int D = 936; - int& entry = (*this)[pc][to]; + // For standard-layout 'this' points to the first struct member + assert(std::is_standard_layout_v); - assert(abs(v) <= D); // Consistency check for below formula - - entry += v * 32 - entry * abs(v) / D; - - assert(abs(entry) <= 32 * D); - } + using entry = StatsEntry; + entry* p = reinterpret_cast(this); + std::fill(p, p + sizeof(*this) / sizeof(entry), v); + } }; -/// 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; +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 +}; -/// 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. -namespace Search { struct Stack; } - +// 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(bool skipQuiets = false); - -private: - template void score(); - ExtMove* begin() { return cur; } - ExtMove* end() { return endMoves; } - - const Position& pos; - const Search::Stack* ss; - Move killers[2]; - 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