Line data Source code
1 : #include "moveSort.hpp"
2 :
3 : #include "logging.hpp"
4 : #include "searcher.hpp"
5 : #include "searchConfig.hpp"
6 :
7 : /* Moves are sorted this way
8 : * 1°) previous best (from current thread previousBest)
9 : * 2°) TT move
10 : * --3°) king evasion if in check and king moves--
11 : * 4°) prom cap
12 : * 5°) good capture (not prom) based on SEE if not in check, based on MVV LVA if in check
13 : * 6°) prom
14 : * 7°) killer 0, then killer 1, then killer 0 from previous move, then counter
15 : * 8°) other quiet based on various history score (from/to, piece/to, CMH)
16 : * 9°) bad cap
17 : */
18 :
19 : #pragma GCC diagnostic push
20 : #pragma GCC diagnostic ignored "-Wconversion"
21 :
22 : template<Color C>
23 27803368 : void MoveSorter::computeScore(Move& m) const {
24 0 : assert(isValidMove(m));
25 : //std::cout << ToString(m) << std::endl;
26 27803368 : if (Move2Score(m) != 0) return; // prob cut may have already computed captures score
27 : const MType t = Move2Type(m);
28 : assert(isValidMoveType(t));
29 27798897 : const Square from = Move2From(m);
30 27798897 : assert(isValidSquare(from));
31 27798897 : const Square to = Move2To(m);
32 27798897 : assert(isValidSquare(to));
33 :
34 : // apply default score based on type
35 27798897 : ScoreType s = MoveScoring[t];
36 :
37 : // previous root best at root
38 27798897 : if (height == 0 && sameMove(context.previousBest, m)){
39 1223 : s += 15000;
40 : }
41 : // TT move
42 27797674 : else if (e && sameMove(e->m, m)){
43 266518 : s += 14000;
44 : }
45 : else {
46 : // king evasion ///@todo try again ??
47 : //if (isInCheck && from == p.king[C]) s += 10000;
48 :
49 : // capture that are not promotion
50 27531156 : if (isCapture(t) && !isPromotion(t)) {
51 4094861 : const Piece pp = PieceTools::getPieceType(p, from);
52 4094861 : const Piece ppOpp = (t != T_ep) ? PieceTools::getPieceType(p, to) : P_wp;
53 4094861 : assert(pp > 0);
54 4094861 : assert(ppOpp > 0);
55 :
56 4094861 : const std::span<const EvalScore> pst = EvalConfig::PST[pp - 1];
57 4094861 : const std::span<const EvalScore> pstOpp = EvalConfig::PST[ppOpp - 1];
58 : // always use PST as a hint
59 4094861 : const ScoreType pstScore = (ScaleScore(pst[ColorSquarePstHelper<C>(to)] - pst[ColorSquarePstHelper<C>(from)] + pstOpp[ColorSquarePstHelper<~C>(to)], gp));
60 4094861 : s += pstScore/SearchConfig::capPSTScoreDivisor;
61 :
62 4094861 : if (useSEE && !isInCheck) {
63 1864855 : const ScoreType see = Searcher::SEE(p, m);
64 1864855 : s += see;
65 : // recapture bonus
66 3618315 : if (isValidMove(p.lastMove) && isCapture(p.lastMove) && to == Move2To(p.lastMove)) s += 512;
67 : // too bad capture are ordered last (-7000)
68 1864855 : if (/*see + pstScore < 0 &&*/ see < DynamicConfig::badCapLimit) s -= 2 * MoveScoring[T_capture];
69 : }
70 : else { // without SEE
71 : // recapture (> max MVVLVA value)
72 4203993 : if (isValidMove(p.lastMove) && isCapture(p.lastMove) && to == Move2To(p.lastMove)) s += 512;
73 : // MVVLVA [0 400]
74 2230006 : s += SearchConfig::capMMLVAMultiplicator * SearchConfig::MvvLvaScores[ppOpp - 1][pp - 1];
75 : // cap history (HISTORY_MAX = 1024)
76 2230006 : s += context.historyT.historyCap[PieceIdx(p.board_const(from))][to][ppOpp-1] / SearchConfig::capHistoryDivisor;
77 : }
78 : }
79 :
80 : // standard moves and castling
81 23436295 : else if (t == T_std || isCastling(m)) {
82 23412994 : if (sameMove(m, context.killerT.killers[height][0])) s += 1900; // quiet killer
83 23260688 : else if (sameMove(m, context.killerT.killers[height][1]))
84 47712 : s += 1300; // quiet killer
85 23212976 : else if (height > 1 && sameMove(m, context.killerT.killers[height - 2][0]))
86 134729 : s += 1700; // quiet killer
87 : //else if (height > 1 && sameMove(m, context.killerT.killers[height - 2][1]))
88 : // s += 1400; // quiet killer
89 66744295 : else if (isValidMove(p.lastMove) && sameMove(context.counterT.counter[Move2From(p.lastMove)][correctedMove2ToKingDest(p.lastMove)], m)) // in sync with CounterT::update()
90 222076 : s += 1500; // quiet counter
91 : else {
92 : ///@todo give another try to tune those ratio!
93 : // History
94 : const Square correctedTo = correctedMove2ToKingDest(m);
95 22856171 : const Piece pp = p.board_const(from);
96 22856171 : s += context.historyT.history[p.c][from][correctedTo] / SearchConfig::quietHistoryDivisor1; // +/- HISTORY_MAX = 1024
97 22856171 : s += context.historyT.historyP[PieceIdx(pp)][correctedTo] / SearchConfig::quietHistoryDivisor2; // +/- HISTORY_MAX = 1024
98 22856171 : s += context.getCMHScore(p, from, correctedTo, cmhPtr) / SearchConfig::quietHistoryDivisor3; // +/- HISTORY_MAX = 1024
99 22856171 : if (!isCastling(m)) {
100 : // move (safely) leaving threat square from null move search
101 23820898 : if (!isInCheck && refutation != INVALIDMINIMOVE && from == correctedMove2ToKingDest(refutation) && Searcher::SEE_GE(p, m, -80)) s += 512;
102 : // always use PST to compensate low value history
103 22855370 : const std::span<const EvalScore> pst = EvalConfig::PST[Abs(pp) - 1];
104 22855370 : s += (ScaleScore(pst[ColorSquarePstHelper<C>(correctedTo)] - pst[ColorSquarePstHelper<C>(from)], gp))/2;
105 : }
106 : }
107 : }
108 : }
109 27798897 : m = ToMove(from, to, t, (ScoreType)s);
110 : }
111 :
112 : #pragma GCC diagnostic pop
113 :
114 2336262 : void MoveSorter::score(const Searcher& context,
115 : MoveList& moves,
116 : const Position& p,
117 : const float gp,
118 : const DepthType height,
119 : const CMHPtrArray& cmhPtr,
120 : const bool useSEE,
121 : const bool isInCheck,
122 : const TT::Entry* e,
123 : const MiniMove refutation) {
124 : START_TIMER
125 2336262 : if (moves.size() < 2) return;
126 : const MoveSorter ms(context, p, gp, height, cmhPtr, useSEE, isInCheck, e, refutation);
127 1938211 : if (p.c == Co_White) {
128 16548564 : for (auto & it : moves) { ms.computeScore<Co_White>(it); }
129 : }
130 : else {
131 13193015 : for (auto & it : moves) { ms.computeScore<Co_Black>(it); }
132 : }
133 : STOP_AND_SUM_TIMER(MoveScoring)
134 : }
135 :
136 2 : void MoveSorter::scoreAndSort(const Searcher& context,
137 : MoveList& moves,
138 : const Position& p,
139 : const float gp,
140 : const DepthType height,
141 : const CMHPtrArray& cmhPtr,
142 : const bool useSEE,
143 : const bool isInCheck,
144 : const TT::Entry* e,
145 : const MiniMove refutation) {
146 2 : score(context, moves, p, gp, height, cmhPtr, useSEE, isInCheck, e, refutation);
147 : sort(moves);
148 2 : }
149 :
150 0 : void MoveSorter::sort(MoveList& moves) {
151 : START_TIMER
152 : std::ranges::sort(moves, MoveSortOperator());
153 : STOP_AND_SUM_TIMER(MoveSorting)
154 0 : }
155 :
156 16283053 : const Move* MoveSorter::pickNext(MoveList& moves, size_t& begin, bool skipSort) {
157 16283053 : if (moves.begin() + begin == moves.end()) return nullptr;
158 : START_TIMER
159 14949825 : if(!skipSort){
160 9938672 : const auto it = std::min_element(moves.begin() + begin, moves.end(), MoveSortOperator());
161 : std::iter_swap(moves.begin() + begin, it);
162 : }
163 : STOP_AND_SUM_TIMER(MoveSorting)
164 14949825 : return &*(moves.begin() + (begin++)); // increment begin !
165 : }
|
