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