1 /* 2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1 3 Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file) 4 5 Stockfish is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 Stockfish is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef MOVEPICK_H_INCLUDED 20 #define MOVEPICK_H_INCLUDED 21 22 #include <array> 23 #include <limits> 24 #include <type_traits> 25 26 #include "movegen.h" 27 #include "position.h" 28 #include "types.h" 29 30 namespace Stockfish { 31 32 /// StatsEntry stores the stat table value. It is usually a number but could 33 /// be a move or even a nested history. We use a class instead of naked value 34 /// to directly call history update operator<<() on the entry so to use stats 35 /// tables at caller sites as simple multi-dim arrays. 36 template<typename T, int D> 37 class StatsEntry { 38 39 T entry; 40 41 public: 42 void operator=(const T& v) { entry = v; } 43 T* operator&() { return &entry; } 44 T* operator->() { return &entry; } 45 operator const T&() const { return entry; } 46 47 void operator<<(int bonus) { 48 assert(abs(bonus) <= D); // Ensure range is [-D, D] 49 static_assert(D <= std::numeric_limits<T>::max(), "D overflows T"); 50 51 entry += bonus - entry * abs(bonus) / D; 52 53 assert(abs(entry) <= D); 54 } 55 }; 56 57 /// Stats is a generic N-dimensional array used to store various statistics. 58 /// The first template parameter T is the base type of the array, the second 59 /// template parameter D limits the range of updates in [-D, D] when we update 60 /// values with the << operator, while the last parameters (Size and Sizes) 61 /// encode the dimensions of the array. 62 template <typename T, int D, int Size, int... Sizes> 63 struct Stats : public std::array<Stats<T, D, Sizes...>, Size> 64 { 65 typedef Stats<T, D, Size, Sizes...> stats; 66 fillStats67 void fill(const T& v) { 68 69 // For standard-layout 'this' points to first struct member 70 assert(std::is_standard_layout<stats>::value); 71 72 typedef StatsEntry<T, D> entry; 73 entry* p = reinterpret_cast<entry*>(this); 74 std::fill(p, p + sizeof(*this) / sizeof(entry), v); 75 } 76 }; 77 78 template <typename T, int D, int Size> 79 struct Stats<T, D, Size> : public std::array<StatsEntry<T, D>, Size> {}; 80 81 /// In stats table, D=0 means that the template parameter is not used 82 enum StatsParams { NOT_USED = 0 }; 83 enum StatsType { NoCaptures, Captures }; 84 85 /// ButterflyHistory records how often quiet moves have been successful or 86 /// unsuccessful during the current search, and is used for reduction and move 87 /// ordering decisions. It uses 2 tables (one for each color) indexed by 88 /// the move's from and to squares, see www.chessprogramming.org/Butterfly_Boards 89 typedef Stats<int16_t, 13365, COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyHistory; 90 91 /// At higher depths LowPlyHistory records successful quiet moves near the root 92 /// and quiet moves which are/were in the PV (ttPv). It is cleared with each new 93 /// search and filled during iterative deepening. 94 constexpr int MAX_LPH = 4; 95 typedef Stats<int16_t, 10692, MAX_LPH, int(SQUARE_NB) * int(SQUARE_NB)> LowPlyHistory; 96 97 /// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous 98 /// move, see www.chessprogramming.org/Countermove_Heuristic 99 typedef Stats<Move, NOT_USED, PIECE_NB, SQUARE_NB> CounterMoveHistory; 100 101 /// CapturePieceToHistory is addressed by a move's [piece][to][captured piece type] 102 typedef Stats<int16_t, 10692, PIECE_NB, SQUARE_NB, PIECE_TYPE_NB> CapturePieceToHistory; 103 104 /// PieceToHistory is like ButterflyHistory but is addressed by a move's [piece][to] 105 typedef Stats<int16_t, 29952, PIECE_NB, SQUARE_NB> PieceToHistory; 106 107 /// ContinuationHistory is the combined history of a given pair of moves, usually 108 /// the current one given a previous one. The nested history table is based on 109 /// PieceToHistory instead of ButterflyBoards. 110 typedef Stats<PieceToHistory, NOT_USED, PIECE_NB, SQUARE_NB> ContinuationHistory; 111 112 113 /// MovePicker class is used to pick one pseudo-legal move at a time from the 114 /// current position. The most important method is next_move(), which returns a 115 /// new pseudo-legal move each time it is called, until there are no moves left, 116 /// when MOVE_NONE is returned. In order to improve the efficiency of the 117 /// alpha-beta algorithm, MovePicker attempts to return the moves which are most 118 /// likely to get a cut-off first. 119 class MovePicker { 120 121 enum PickType { Next, Best }; 122 123 public: 124 MovePicker(const MovePicker&) = delete; 125 MovePicker& operator=(const MovePicker&) = delete; 126 MovePicker(const Position&, Move, Value, const CapturePieceToHistory*); 127 MovePicker(const Position&, Move, Depth, const ButterflyHistory*, 128 const CapturePieceToHistory*, 129 const PieceToHistory**, 130 Square); 131 MovePicker(const Position&, Move, Depth, const ButterflyHistory*, 132 const LowPlyHistory*, 133 const CapturePieceToHistory*, 134 const PieceToHistory**, 135 Move, 136 const Move*, 137 int); 138 Move next_move(bool skipQuiets = false); 139 140 private: 141 template<PickType T, typename Pred> Move select(Pred); 142 template<GenType> void score(); 143 ExtMove* begin() { return cur; } 144 ExtMove* end() { return endMoves; } 145 146 const Position& pos; 147 const ButterflyHistory* mainHistory; 148 const LowPlyHistory* lowPlyHistory; 149 const CapturePieceToHistory* captureHistory; 150 const PieceToHistory** continuationHistory; 151 Move ttMove; 152 ExtMove refutations[3], *cur, *endMoves, *endBadCaptures; 153 int stage; 154 Square recaptureSquare; 155 Value threshold; 156 Depth depth; 157 int ply; 158 ExtMove moves[MAX_MOVES]; 159 }; 160 161 } // namespace Stockfish 162 163 #endif // #ifndef MOVEPICK_H_INCLUDED 164