]> git.sesse.net Git - stockfish/blob - src/movepick.h
Revert "Adjust stand pat in qsearch on pv nodes"
[stockfish] / src / movepick.h
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2023 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 <cassert>
24 #include <cmath>
25 #include <cstdint>
26 #include <cstdlib>
27 #include <limits>
28 #include <type_traits>  // IWYU pragma: keep
29
30 #include "movegen.h"
31 #include "types.h"
32 #include "position.h"
33
34 namespace Stockfish {
35
36 constexpr int PAWN_HISTORY_SIZE = 512;  // has to be a power of 2
37
38 static_assert((PAWN_HISTORY_SIZE & (PAWN_HISTORY_SIZE - 1)) == 0,
39               "PAWN_HISTORY_SIZE has to be a power of 2");
40
41 inline int pawn_structure(const Position& pos) { return pos.pawn_key() & (PAWN_HISTORY_SIZE - 1); }
42
43 // StatsEntry stores the stat table value. It is usually a number but could
44 // be a move or even a nested history. We use a class instead of a naked value
45 // to directly call history update operator<<() on the entry so to use stats
46 // tables at caller sites as simple multi-dim arrays.
47 template<typename T, int D>
48 class StatsEntry {
49
50     T entry;
51
52    public:
53     void operator=(const T& v) { entry = v; }
54     T*   operator&() { return &entry; }
55     T*   operator->() { return &entry; }
56     operator const T&() const { return entry; }
57
58     void operator<<(int bonus) {
59         assert(std::abs(bonus) <= D);  // Ensure range is [-D, D]
60         static_assert(D <= std::numeric_limits<T>::max(), "D overflows T");
61
62         entry += bonus - entry * std::abs(bonus) / D;
63
64         assert(std::abs(entry) <= D);
65     }
66 };
67
68 // Stats is a generic N-dimensional array used to store various statistics.
69 // The first template parameter T is the base type of the array, and the second
70 // template parameter D limits the range of updates in [-D, D] when we update
71 // values with the << operator, while the last parameters (Size and Sizes)
72 // encode the dimensions of the array.
73 template<typename T, int D, int Size, int... Sizes>
74 struct Stats: public std::array<Stats<T, D, Sizes...>, Size> {
75     using stats = Stats<T, D, Size, Sizes...>;
76
77     void fill(const T& v) {
78
79         // For standard-layout 'this' points to the first struct member
80         assert(std::is_standard_layout_v<stats>);
81
82         using entry = StatsEntry<T, D>;
83         entry* p    = reinterpret_cast<entry*>(this);
84         std::fill(p, p + sizeof(*this) / sizeof(entry), v);
85     }
86 };
87
88 template<typename T, int D, int Size>
89 struct Stats<T, D, Size>: public std::array<StatsEntry<T, D>, Size> {};
90
91 // In stats table, D=0 means that the template parameter is not used
92 enum StatsParams {
93     NOT_USED = 0
94 };
95 enum StatsType {
96     NoCaptures,
97     Captures
98 };
99
100 // ButterflyHistory records how often quiet moves have been successful or unsuccessful
101 // during the current search, and is used for reduction and move ordering decisions.
102 // It uses 2 tables (one for each color) indexed by the move's from and to squares,
103 // see www.chessprogramming.org/Butterfly_Boards (~11 elo)
104 using ButterflyHistory = Stats<int16_t, 7183, COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)>;
105
106 // CounterMoveHistory stores counter moves indexed by [piece][to] of the previous
107 // move, see www.chessprogramming.org/Countermove_Heuristic
108 using CounterMoveHistory = Stats<Move, NOT_USED, PIECE_NB, SQUARE_NB>;
109
110 // CapturePieceToHistory is addressed by a move's [piece][to][captured piece type]
111 using CapturePieceToHistory = Stats<int16_t, 10692, PIECE_NB, SQUARE_NB, PIECE_TYPE_NB>;
112
113 // PieceToHistory is like ButterflyHistory but is addressed by a move's [piece][to]
114 using PieceToHistory = Stats<int16_t, 29952, PIECE_NB, SQUARE_NB>;
115
116 // ContinuationHistory is the combined history of a given pair of moves, usually
117 // the current one given a previous one. The nested history table is based on
118 // PieceToHistory instead of ButterflyBoards.
119 // (~63 elo)
120 using ContinuationHistory = Stats<PieceToHistory, NOT_USED, PIECE_NB, SQUARE_NB>;
121
122 // PawnHistory is addressed by the pawn structure and a move's [piece][to]
123 using PawnHistory = Stats<int16_t, 8192, PAWN_HISTORY_SIZE, PIECE_NB, SQUARE_NB>;
124
125 // MovePicker class is used to pick one pseudo-legal move at a time from the
126 // current position. The most important method is next_move(), which returns a
127 // new pseudo-legal move each time it is called, until there are no moves left,
128 // when MOVE_NONE is returned. In order to improve the efficiency of the
129 // alpha-beta algorithm, MovePicker attempts to return the moves which are most
130 // likely to get a cut-off first.
131 class MovePicker {
132
133     enum PickType {
134         Next,
135         Best
136     };
137
138    public:
139     MovePicker(const MovePicker&)            = delete;
140     MovePicker& operator=(const MovePicker&) = delete;
141     MovePicker(const Position&,
142                Move,
143                Depth,
144                const ButterflyHistory*,
145                const CapturePieceToHistory*,
146                const PieceToHistory**,
147                const PawnHistory*,
148                Move,
149                const Move*);
150     MovePicker(const Position&,
151                Move,
152                Depth,
153                const ButterflyHistory*,
154                const CapturePieceToHistory*,
155                const PieceToHistory**,
156                const PawnHistory*);
157     MovePicker(const Position&, Move, Value, const CapturePieceToHistory*);
158     Move next_move(bool skipQuiets = false);
159
160    private:
161     template<PickType T, typename Pred>
162     Move select(Pred);
163     template<GenType>
164     void     score();
165     ExtMove* begin() { return cur; }
166     ExtMove* end() { return endMoves; }
167
168     const Position&              pos;
169     const ButterflyHistory*      mainHistory;
170     const CapturePieceToHistory* captureHistory;
171     const PieceToHistory**       continuationHistory;
172     const PawnHistory*           pawnHistory;
173     Move                         ttMove;
174     ExtMove                      refutations[3], *cur, *endMoves, *endBadCaptures;
175     int                          stage;
176     Value                        threshold;
177     Depth                        depth;
178     ExtMove                      moves[MAX_MOVES];
179 };
180
181 }  // namespace Stockfish
182
183 #endif  // #ifndef MOVEPICK_H_INCLUDED