X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.h;h=f210f5387fcb222bb8a0728e4a9e413a2a7b583b;hb=b0658f09b93185e2b43d4b2d6f0daa30c36ebcc2;hp=b488313a446833db0b5a8a2d1e8a3fa495964252;hpb=8fd34d7763072fc3ec7216729c1f7b7354bfa470;p=stockfish diff --git a/src/movepick.h b/src/movepick.h index b488313a..f210f538 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -1,7 +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) 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 @@ -20,99 +19,164 @@ #ifndef MOVEPICK_H_INCLUDED #define MOVEPICK_H_INCLUDED -#include // For std::max -#include // For std::memset +#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 { +constexpr int PAWN_HISTORY_SIZE = 512; - static const Value Max = Value(1<<28); +inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); } - const T* operator[](Piece pc) const { return table[pc]; } - T* operator[](Piece pc) { return table[pc]; } - void clear() { std::memset(table, 0, sizeof(table)); } +// 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(Piece pc, Square to, Move m) { + T entry; - if (m != table[pc][to]) - table[pc][to] = m; - } + public: + void operator=(const T& v) { entry = v; } + T* operator&() { return &entry; } + T* operator->() { return &entry; } + operator const T&() const { return entry; } - void updateH(Piece pc, Square to, Value v) { + void operator<<(int bonus) { + assert(abs(bonus) <= D); // Ensure range is [-D, D] + static_assert(D <= std::numeric_limits::max(), "D overflows T"); - if (abs(int(v)) >= 324) - return; - table[pc][to] -= table[pc][to] * abs(int(v)) / 324; - table[pc][to] += int(v) * 32; - } + entry += (bonus * D - entry * abs(bonus)) / (D * 5 / 4); - void updateCMH(Piece pc, Square to, Value v) { + assert(abs(entry) <= D); + } +}; - if (abs(int(v)) >= 324) - return; - table[pc][to] -= table[pc][to] * abs(int(v)) / 512; - table[pc][to] += int(v) * 64; - } +// 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; -private: - T table[PIECE_NB][SQUARE_NB]; -}; + void fill(const T& v) { + + // For standard-layout 'this' points to the first struct member + assert(std::is_standard_layout_v); -typedef Stats HistoryStats; -typedef Stats MovesStats; -typedef Stats CounterMovesHistoryStats; + using entry = StatsEntry; + entry* p = reinterpret_cast(this); + std::fill(p, p + sizeof(*this) / sizeof(entry), v); + } +}; +template +struct Stats: public std::array, Size> {}; -/// 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. +// 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; + +// PawnStructureHistory 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, Depth, const HistoryStats&, const CounterMovesHistoryStats&, Square); - MovePicker(const Position&, Move, const HistoryStats&, const CounterMovesHistoryStats&, Value); - MovePicker(const Position&, Move, Depth, const HistoryStats&, const CounterMovesHistoryStats&, Move, Search::Stack*); - - template Move next_move(); - -private: - template void score(); - void generate_next_stage(); - ExtMove* begin() { return moves; } - ExtMove* end() { return endMoves; } - - const Position& pos; - const HistoryStats& history; - const CounterMovesHistoryStats& counterMovesHistory; - Search::Stack* ss; - Move countermove; - Depth depth; - Move ttMove; - ExtMove killers[3]; - Square recaptureSquare; - Value threshold; - int stage; - ExtMove *endQuiets, *endBadCaptures = moves + MAX_MOVES - 1; - ExtMove moves[MAX_MOVES], *cur = moves, *endMoves = 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&, + Square); + MovePicker(const Position&, Move, Value, const CapturePieceToHistory*, const PawnHistory&); + 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; + Square recaptureSquare; + Value threshold; + Depth depth; + ExtMove moves[MAX_MOVES]; }; -#endif // #ifndef MOVEPICK_H_INCLUDED +} // namespace Stockfish + +#endif // #ifndef MOVEPICK_H_INCLUDED