X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.h;h=44fc51f6263d73ca5a88919ff044e3e6b256cc12;hb=15d47a2b3821b92c4d048f39f7f43c301299d365;hp=ebb78787702a9d0b9c3538aedb978e8d99118126;hpb=9fc602bae74b8e09bd45ace3b42a8ce84d56b23c;p=stockfish diff --git a/src/movepick.h b/src/movepick.h index ebb78787..7828fa19 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-2010 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 @@ -17,71 +16,167 @@ along with this program. If not, see . */ - -#if !defined MOVEPICK_H_INCLUDED +#ifndef MOVEPICK_H_INCLUDED #define MOVEPICK_H_INCLUDED -//// -//// Includes -//// +#include +#include +#include +#include +#include +#include // IWYU pragma: keep -#include "depth.h" -#include "history.h" +#include "movegen.h" +#include "types.h" #include "position.h" +namespace Stockfish { -//// -//// Types -//// +constexpr int PAWN_HISTORY_SIZE = 512; // has to be a power of 2 -struct SearchStack; +static_assert((PAWN_HISTORY_SIZE & (PAWN_HISTORY_SIZE - 1)) == 0, + "PAWN_HISTORY_SIZE has to be a power of 2"); -/// MovePicker is a class which is used to pick one legal move at a time from -/// the current position. It is initialized with a Position object and a few -/// moves we have reason to believe are good. The most important method is -/// MovePicker::pick_next_move(), which returns a new legal move each time it -/// is called, until there are no legal 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 be strongest first. +inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); } -class MovePicker { +// 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 { + + T entry; + + public: + void operator=(const T& v) { entry = v; } + T* operator&() { return &entry; } + T* operator->() { return &entry; } + operator const T&() const { return entry; } + + void operator<<(int bonus) { + assert(abs(bonus) <= D); // Ensure range is [-D, D] + static_assert(D <= std::numeric_limits::max(), "D overflows T"); + + entry += bonus - entry * abs(bonus) / D; + + assert(abs(entry) <= D); + } +}; - MovePicker& operator=(const MovePicker&); // silence a warning under MSVC - -public: - MovePicker(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss = NULL, Value beta = -VALUE_INFINITE); - Move get_next_move(); - int number_of_evasions() const; - -private: - void score_captures(); - void score_noncaptures(); - void score_evasions_or_checks(); - void go_next_phase(); - - const Position& pos; - const History& H; - MoveStack ttMoves[2], killers[2]; - int badCaptureThreshold, phase; - const uint8_t* phasePtr; - MoveStack *curMove, *lastMove, *lastGoodNonCapture, *lastBadCapture; - Bitboard pinned; - MoveStack moves[256], badCaptures[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; + + void fill(const T& v) { + + // For standard-layout 'this' points to the first struct member + assert(std::is_standard_layout_v); + + using entry = StatsEntry; + entry* p = reinterpret_cast(this); + std::fill(p, p + sizeof(*this) / sizeof(entry), v); + } }; +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 +}; -//// -//// Inline functions -//// +// 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 { -/// MovePicker::number_of_evasions() simply returns the number of moves in -/// evasions phase. It is intended to be used in positions where the side to -/// move is in check, for detecting checkmates or situations where there is -/// only a single reply to check. -/// WARNING: It works as long as PH_EVASIONS is the _only_ phase for evasions. + 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]; +}; -inline int MovePicker::number_of_evasions() const { - return int(lastMove - moves); -} +} // namespace Stockfish -#endif // !defined(MOVEPICK_H_INCLUDED) +#endif // #ifndef MOVEPICK_H_INCLUDED