Line data Source code
1 : /*
2 : * Copyright (C) 2013-2018 Fulvio Benini
3 :
4 : * This file is part of Scid (Shane's Chess Information Database).
5 : *
6 : * Scid is free software: you can redistribute it and/or modify
7 : * it under the terms of the GNU General Public License as published by
8 : * the Free Software Foundation.
9 : *
10 : * Scid 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 Scid. If not, see <http://www.gnu.org/licenses/>.
17 : */
18 :
19 : /** @file
20 : * Defines the classes used to search for positions.
21 : */
22 :
23 : #ifndef SEARCHPOS_H
24 : #define SEARCHPOS_H
25 :
26 : #include "common.h"
27 : #include "fastgame.h"
28 : #include "matsig.h"
29 : #include "position.h"
30 : #include "scidbase.h"
31 : #include "stored.h"
32 : #include <algorithm>
33 : #include <memory>
34 :
35 : /// Return true if there is a piece's count in @e a which is less than its
36 : /// counterpart in @e b.
37 : /// @param promo: pawns' difference is considered when comparing queen.
38 : /// @param upromo: minor pieces' count is not compared.
39 : template <typename TMaterialCount>
40 16 : bool less_mat(const TMaterialCount& a, matSigT b, bool promo, bool upromo) {
41 16 : int wp_diff = a.count(WHITE, PAWN) - static_cast<int>(MATSIG_Count_WP(b));
42 16 : int bp_diff = a.count(BLACK, PAWN) - static_cast<int>(MATSIG_Count_BP(b));
43 16 : if (wp_diff < 0 || bp_diff < 0)
44 0 : return true;
45 :
46 16 : int wq_diff = a.count(WHITE, QUEEN) - static_cast<int>(MATSIG_Count_WQ(b));
47 16 : int bq_diff = a.count(BLACK, QUEEN) - static_cast<int>(MATSIG_Count_BQ(b));
48 16 : if (promo) {
49 8 : wq_diff += wp_diff;
50 8 : bq_diff += bp_diff;
51 : }
52 16 : if (wq_diff < 0 || bq_diff < 0)
53 8 : return true;
54 :
55 8 : if (upromo)
56 4 : return false;
57 :
58 8 : return a.count(WHITE, ROOK) < static_cast<int>(MATSIG_Count_WR(b)) ||
59 8 : a.count(WHITE, BISHOP) < static_cast<int>(MATSIG_Count_WB(b)) ||
60 8 : a.count(WHITE, KNIGHT) < static_cast<int>(MATSIG_Count_WN(b)) ||
61 8 : a.count(BLACK, ROOK) < static_cast<int>(MATSIG_Count_BR(b)) ||
62 12 : a.count(BLACK, BISHOP) < static_cast<int>(MATSIG_Count_BB(b)) ||
63 8 : a.count(BLACK, KNIGHT) < static_cast<int>(MATSIG_Count_BN(b));
64 : }
65 :
66 : /// Search for an exact position (same material in the same squares).
67 : class SearchPos {
68 : MaterialCount nPieces_;
69 : pieceT board_[64];
70 : std::unique_ptr<StoredLine> storedLine_;
71 : std::pair<uint16_t, uint16_t> hpSig_;
72 : colorT toMove_;
73 : bool isStdStard_;
74 :
75 : public:
76 : explicit SearchPos(const Position* pos) {
77 : std::copy_n(pos->GetBoard(), 64, board_);
78 :
79 : for (auto piece : board_) {
80 : if (piece != EMPTY) {
81 : nPieces_.incr(piece_Color(piece), piece_Type(piece));
82 : }
83 : }
84 :
85 : hpSig_ = hpSig_make(board_);
86 : toMove_ = pos->GetToMove();
87 : isStdStard_ = pos->IsStdStart();
88 :
89 : if ((board_[E1] == WK || board_[G1] == WK) &&
90 : (board_[E8] == BK || board_[G8] == BK)) {
91 : storedLine_ = std::make_unique<StoredLine>(board_, toMove_);
92 : }
93 : }
94 :
95 : /// Disable the stored lines optimization
96 : void disableOptStoredLine() { storedLine_ = nullptr; }
97 :
98 : /// Disable the home pawn optimization
99 : void disableOptHpSig() { hpSig_ = {0, 0}; }
100 :
101 : /// Search for the position using the optimizations in a game's index.
102 : /// @returns
103 : /// -2 : the game cannot reach the searched position
104 : /// -1 : the game can reach the searched position
105 : /// >=0: the game reach the searched position at the returned ply
106 : int index_match(const IndexEntry& ie) const {
107 : if (!ie.GetStartFlag()) {
108 : if (storedLine_) {
109 : int ply = storedLine_->match(ie.GetStoredLineCode());
110 : if (ply != -1)
111 : return ply;
112 : }
113 : if (!hpSig_match(hpSig_.first, hpSig_.second, ie.GetHomePawnData()))
114 : return -2;
115 : }
116 : if (less_mat(nPieces_, ie.GetFinalMatSig(), ie.GetPromotionsFlag(),
117 : ie.GetUnderPromoFlag())) {
118 : return -2;
119 : }
120 : return -1;
121 : }
122 :
123 : /// Reset @e filter to include only the games that reached the searched
124 : /// position in their main line.
125 : bool setFilter(scidBaseT* base, HFilter& filter, const Progress& progress) {
126 : if (toMove_ == BLACK)
127 : return SetFilter<BLACK>(base, filter, progress);
128 :
129 : if (!isStdStard_)
130 : return SetFilter<WHITE>(base, filter, progress);
131 :
132 : return setFilterStdStart(base, filter);
133 : }
134 :
135 : private:
136 : bool setFilterStdStart(scidBaseT* base, HFilter& filter) {
137 : filter->includeAll();
138 : for (gamenumT i = 0, n = base->numGames(); i < n; i++) {
139 : const IndexEntry* ie = base->getIndexEntry(i);
140 : if (ie->GetStartFlag()) {
141 : int ply = base->getGame(ie).search<WHITE>(board_, nPieces_);
142 : filter.set(i, (ply > 255) ? 255 : ply);
143 : }
144 : }
145 : return true;
146 : }
147 :
148 : template <colorT TOMOVE>
149 : bool SetFilter(scidBaseT* base, HFilter& filter, const Progress& prg) {
150 : filter->clear();
151 : long long progress = 0;
152 : for (gamenumT i = 0, n = base->numGames(); i < n; i++) {
153 : const IndexEntry* ie = base->getIndexEntry(i);
154 : int ply = index_match(*ie);
155 : if (ply >= 0) {
156 : filter.set(i, static_cast<byte>(ply + 1));
157 : } else if (ply == -1) {
158 : ply = base->getGame(ie).search<TOMOVE>(board_, nPieces_);
159 : if (ply != 0)
160 : filter.set(i, (ply > 255) ? 255 : ply);
161 :
162 : if ((progress++ % 256) == 0 && !prg.report(i, n))
163 : return false;
164 : }
165 : }
166 : return true;
167 : }
168 : };
169 :
170 : #endif
|
