Line data Source code
1 : //////////////////////////////////////////////////////////////////////
2 : //
3 : // FILE: matsig.h
4 : // Material signatures and home-pawn signatures.
5 : //
6 : // Part of: Scid (Shane's Chess Information Database)
7 : // Version: 1.9
8 : //
9 : // Notice: Copyright (c) 2000 Shane Hudson. All rights reserved.
10 : //
11 : // Author: Shane Hudson (sgh@users.sourceforge.net)
12 : //
13 : //////////////////////////////////////////////////////////////////////
14 :
15 :
16 : #ifndef SCID_MATSIG_H
17 : #define SCID_MATSIG_H
18 :
19 : #include "common.h"
20 : #include <algorithm>
21 : #include <string>
22 :
23 : // Matsigs are 32-bit unsigned ints. We only use 24 bits of this.
24 :
25 : typedef uint32_t matSigT;
26 :
27 : // From most significant bits down to least, the matsig layout is:
28 : // Bits 22-33: WQ Bits 10-11: BQ
29 : // Bits 20-21: WN Bits 08-09: BR
30 : // Bits 18-19: WB Bits 06-07: BB
31 : // Bits 16-17: WN Bits 04-05: BN
32 : // Bits 12-15: WP Bits 00-03: BP
33 :
34 : // This means that pawn counts from 0 to 8 are possible, but for other
35 : // pieces only counts up to 3 are possible.
36 :
37 :
38 : // Shifts:
39 :
40 : #define SHIFT_BP 0
41 : #define SHIFT_BN 4
42 : #define SHIFT_BB 6
43 : #define SHIFT_BR 8
44 : #define SHIFT_BQ 10
45 : #define SHIFT_WP 12
46 : #define SHIFT_WN 16
47 : #define SHIFT_WB 18
48 : #define SHIFT_WR 20
49 : #define SHIFT_WQ 22
50 :
51 :
52 : // Masks:
53 : // 28 24 20 16 12 8 4 0
54 : #define MASK_BP 0x0000000F // 0- 3: .... .... .... .... .... .... .... 1111
55 : #define MASK_BN 0x00000030 // 4- 5: .... .... .... .... .... .... ..11 ....
56 : #define MASK_BB 0x000000C0 // 6- 7: .... .... .... .... .... .... 11.. ....
57 : #define MASK_BR 0x00000300 // 8- 9: .... .... .... .... .... ..11 .... ....
58 : #define MASK_BQ 0x00000C00 //10-11: .... .... .... .... .... 11.. .... ....
59 : #define MASK_WP 0x0000F000 //12-15: .... .... .... .... 1111 .... .... ....
60 : #define MASK_WN 0x00030000 //16-17: .... .... .... ..11 .... .... .... ....
61 : #define MASK_WB 0x000C0000 //18-19: .... .... .... 11.. .... .... .... ....
62 : #define MASK_WR 0x00300000 //20-21: .... .... ..11 .... .... .... .... ....
63 : #define MASK_WQ 0x00C00000 //29-31: .... .... 11.. .... .... .... .... ....
64 :
65 :
66 : // The arrays MASK_BY_PIECE and SHIFT_BY_PIECE are useful for setting
67 : // matsigs by piece type:
68 :
69 : const matSigT
70 : MASK_BY_PIECE [16] = {
71 : 0, // 0: Empty
72 : 0, // 1: WK
73 : MASK_WQ, // 2: WQ
74 : MASK_WR, // 3: WR
75 : MASK_WB, // 4: WB
76 : MASK_WN, // 5: WN
77 : MASK_WP, // 6: WP
78 : 0, 0, // 7, 8: Invalid pieces
79 : 0, // 9: BK
80 : MASK_BQ, // 10: BQ
81 : MASK_BR, // 11: BR
82 : MASK_BB, // 12: BB
83 : MASK_BN, // 13: BN
84 : MASK_BP, // 14: BP
85 : 0 // 15: Invalid piece
86 : };
87 :
88 : const uint
89 : SHIFT_BY_PIECE[16] = {
90 : 0, 0, // 0: Empty, 1: WK
91 : SHIFT_WQ, // 2: WQ
92 : SHIFT_WR, // 3: WR
93 : SHIFT_WB, // 4: WB
94 : SHIFT_WN, // 5: WN
95 : SHIFT_WP, // 6: WP
96 : 0, 0, 0, // 7, 8: Invalid pieces, 9: BK
97 : SHIFT_BQ, // 10: BQ
98 : SHIFT_BR, // 11: BR
99 : SHIFT_BB, // 12: BB
100 : SHIFT_BN, // 13: BN
101 : SHIFT_BP, // 14: BP
102 : 0 // 15: Invalid piece
103 : };
104 :
105 :
106 : // Quick way to flip colors: just switch the upper/lower 12 bits
107 :
108 : #define MATSIG_FlipColor(x) ((x) >> 12) | (((x) & 0x00000FFF) << 12)
109 :
110 :
111 : // Quick tests for non-zero counts of a piece type:
112 :
113 : #define MATSIG_Has_WQ(x) ((x) & MASK_WQ)
114 : #define MATSIG_Has_BQ(x) ((x) & MASK_BQ)
115 : #define MATSIG_Has_WR(x) ((x) & MASK_WR)
116 : #define MATSIG_Has_BR(x) ((x) & MASK_BR)
117 : #define MATSIG_Has_WB(x) ((x) & MASK_WB)
118 : #define MATSIG_Has_BB(x) ((x) & MASK_BB)
119 : #define MATSIG_Has_WN(x) ((x) & MASK_WN)
120 : #define MATSIG_Has_BN(x) ((x) & MASK_BN)
121 : #define MATSIG_Has_WP(x) ((x) & MASK_WP)
122 : #define MATSIG_Has_BP(x) ((x) & MASK_BP)
123 :
124 : #define MATSIG_HasQueens(x) ((x) & (MASK_WQ | MASK_BQ))
125 : #define MATSIG_HasRooks(x) ((x) & (MASK_WR | MASK_BR))
126 : #define MATSIG_HasBishops(x) ((x) & (MASK_WB | MASK_BB))
127 : #define MATSIG_HasKnights(x) ((x) & (MASK_WN | MASK_BN))
128 : #define MATSIG_HasPawns(x) ((x) & (MASK_WP | MASK_BP))
129 :
130 :
131 : // Macros to extract a particular count:
132 :
133 : #define MATSIG_Count_WQ(x) (((x) & MASK_WQ) >> SHIFT_WQ)
134 : #define MATSIG_Count_BQ(x) (((x) & MASK_BQ) >> SHIFT_BQ)
135 : #define MATSIG_Count_WR(x) (((x) & MASK_WR) >> SHIFT_WR)
136 : #define MATSIG_Count_BR(x) (((x) & MASK_BR) >> SHIFT_BR)
137 : #define MATSIG_Count_WB(x) (((x) & MASK_WB) >> SHIFT_WB)
138 : #define MATSIG_Count_BB(x) (((x) & MASK_BB) >> SHIFT_BB)
139 : #define MATSIG_Count_WN(x) (((x) & MASK_WN) >> SHIFT_WN)
140 : #define MATSIG_Count_BN(x) (((x) & MASK_BN) >> SHIFT_BN)
141 : #define MATSIG_Count_WP(x) (((x) & MASK_WP) >> SHIFT_WP)
142 : #define MATSIG_Count_BP(x) (((x) & MASK_BP) >> SHIFT_BP)
143 :
144 : //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
145 : // matsig_getCount():
146 : // Inline routine to extract a count of a certain piece type.
147 : //
148 : inline uint
149 : matsig_getCount (matSigT m, pieceT p)
150 : {
151 : return (m & MASK_BY_PIECE[p]) >> SHIFT_BY_PIECE[p];
152 : }
153 :
154 : //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
155 : // matsig_setCount():
156 : // Inline routine to set a particular count.
157 : //
158 : inline matSigT
159 : matsig_setCount (matSigT m, pieceT p, uint count)
160 : {
161 : // First we clear the old mask for this piece:
162 : m &= ~(MASK_BY_PIECE[p]);
163 :
164 : // Avoid overflow.
165 : if (p != PAWN && count > 3)
166 : count = 3;
167 :
168 : // Now we OR to add the new value in:
169 : m |= ((uint) count) << SHIFT_BY_PIECE[p];
170 : return m;
171 : }
172 :
173 :
174 : // Common constant matsigs:
175 :
176 : const matSigT MATSIG_Empty = 0;
177 :
178 : const matSigT MATSIG_StdStart =
179 : ((1 << SHIFT_WQ) | (1 << SHIFT_BQ) | (2 << SHIFT_WR) | (2 << SHIFT_BR) |
180 : (2 << SHIFT_WB) | (2 << SHIFT_BB) | (2 << SHIFT_WN) | (2 << SHIFT_BN) |
181 : (8 << SHIFT_WP) | (8 << SHIFT_BP));
182 :
183 :
184 : //
185 : // Public functions found in matsig.cpp:
186 : //
187 :
188 :
189 : // matsig_makeString: sets s to be a string representation of the sig,
190 : std::string
191 : matsig_makeString (matSigT matsig);
192 :
193 :
194 : // matsig_isReachable: returns true if a game currently
195 : // at a position with the signature <start>, could possibly reach
196 : // the signature <target>. This is useful for quick tests for material
197 : // searches. For example, if we store the final matsig of every game,
198 : // we can speedup a material search by ONLY searching the games that
199 : // have matsig_isReachable(searchsig, finalsig) = 1, or have promotions.
200 : // Example: if searchsig requires neither side to have queens, but
201 : // finalsig for a game shows a WQ (and no promotions), the game could
202 : // not possibly match.
203 : // If promos is true, only the pawn counts are checked, since other
204 : // material could reappear on the board due to a promotion.
205 : // If upromo is true, there are underpromotions (to R, B or N) but
206 : // if only promos is true, all promotions are to Queens only.
207 : bool
208 : matsig_isReachable (matSigT mStart, matSigT mTarget, bool promos, bool upromo);
209 :
210 : // matsig_isReachablePawns:
211 : // like matsig_isReachable, but considering pawns only.
212 : inline bool
213 : matsig_isReachablePawns (matSigT mStart, matSigT mTarget)
214 : {
215 : if (MATSIG_Count_WP(mStart) < MATSIG_Count_WP(mTarget)) { return false; }
216 : if (MATSIG_Count_BP(mStart) < MATSIG_Count_BP(mTarget)) { return false; }
217 : return true;
218 : }
219 :
220 : //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
221 : // matsig_Make():
222 : // Make a material sig, given an array of material counts as
223 : // stored in a Position.
224 : //
225 9016 : inline matSigT matsig_Make(const byte* materialCounts) {
226 9016 : matSigT m = 0;
227 9016 : m |= std::min<matSigT>(3, materialCounts[WQ]) << SHIFT_WQ;
228 9016 : m |= std::min<matSigT>(3, materialCounts[WR]) << SHIFT_WR;
229 9016 : m |= std::min<matSigT>(3, materialCounts[WB]) << SHIFT_WB;
230 9016 : m |= std::min<matSigT>(3, materialCounts[WN]) << SHIFT_WN;
231 9016 : m |= matSigT(materialCounts[WP]) << SHIFT_WP;
232 9016 : m |= std::min<matSigT>(3, materialCounts[BQ]) << SHIFT_BQ;
233 9016 : m |= std::min<matSigT>(3, materialCounts[BR]) << SHIFT_BR;
234 9016 : m |= std::min<matSigT>(3, materialCounts[BB]) << SHIFT_BB;
235 9016 : m |= std::min<matSigT>(3, materialCounts[BN]) << SHIFT_BN;
236 9016 : m |= matSigT(materialCounts[BP]) << SHIFT_BP;
237 9016 : return m;
238 : }
239 :
240 :
241 : // Common HPSigs:
242 : // 0 => no pawns still on their original 2nd/7th rank squares.
243 : // 0xFFFF => all 16 pawns still on their original 2nd/7th rank squares.
244 :
245 : const uint
246 : HPSIG_Empty = 0x0;
247 :
248 : const uint
249 : HPSIG_StdStart = 0xFFFF;
250 :
251 :
252 : bool
253 : hpSig_PossibleMatch (uint hpSig, const byte * changeList);
254 :
255 : bool
256 : hpSig_Prefix (const byte * changeListA, const byte * changeListB);
257 :
258 : uint
259 : hpSig_Final (const byte * changeList);
260 :
261 : // hpSig_bitMask[]: used to add or clear bits in an hpSig.
262 : //
263 : static const uint hpSig_bitMask [16] = {
264 : // a2 to h2:
265 : 0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100,
266 : // a7 to h7:
267 : 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
268 : };
269 :
270 : inline uint
271 : hpSig_AddPawn (uint hpSig, colorT color, fyleT fyle)
272 : {
273 : ASSERT (color == WHITE || color == BLACK);
274 : ASSERT (fyle <= H_FYLE);
275 :
276 : uint val = (uint) fyle;
277 : if (color == BLACK) val += 8;
278 : return hpSig | hpSig_bitMask [val];
279 : }
280 :
281 : inline uint
282 : hpSig_ClearPawn (uint hpSig, colorT color, fyleT fyle)
283 : {
284 : ASSERT (color == WHITE || color == BLACK);
285 : ASSERT (fyle <= H_FYLE);
286 :
287 : uint val = (uint) fyle;
288 : if (color == BLACK) val += 8;
289 : return hpSig & ~(hpSig_bitMask [val]);
290 : }
291 :
292 : /**
293 : * Creates a 16-bits bitmap of the missing pawns in the home ranks.
294 : *
295 : * Used to speed up the searches of positions with the same pawn structure.
296 : * @returns a std::pair containing the bitmap and the number of moved pawns.
297 : */
298 : inline std::pair<uint16_t, uint16_t> hpSig_make(const pieceT* board) {
299 : int hpSig = 0;
300 : int nMoved = 0;
301 : const pieceT* b = board + A2;
302 : // clang-format off
303 : if (*b != WP) { hpSig |= 0x8000; ++nMoved; } b++; /* a2 */
304 : if (*b != WP) { hpSig |= 0x4000; ++nMoved; } b++; /* b2 */
305 : if (*b != WP) { hpSig |= 0x2000; ++nMoved; } b++; /* c2 */
306 : if (*b != WP) { hpSig |= 0x1000; ++nMoved; } b++; /* d2 */
307 : if (*b != WP) { hpSig |= 0x0800; ++nMoved; } b++; /* e2 */
308 : if (*b != WP) { hpSig |= 0x0400; ++nMoved; } b++; /* f2 */
309 : if (*b != WP) { hpSig |= 0x0200; ++nMoved; } b++; /* g2 */
310 : if (*b != WP) { hpSig |= 0x0100; ++nMoved; } /* h2 */
311 : b = board + A7;
312 : if (*b != BP) { hpSig |= 0x0080; ++nMoved; } b++; /* a7 */
313 : if (*b != BP) { hpSig |= 0x0040; ++nMoved; } b++; /* b7 */
314 : if (*b != BP) { hpSig |= 0x0020; ++nMoved; } b++; /* c7 */
315 : if (*b != BP) { hpSig |= 0x0010; ++nMoved; } b++; /* d7 */
316 : if (*b != BP) { hpSig |= 0x0008; ++nMoved; } b++; /* e7 */
317 : if (*b != BP) { hpSig |= 0x0004; ++nMoved; } b++; /* f7 */
318 : if (*b != BP) { hpSig |= 0x0002; ++nMoved; } b++; /* g7 */
319 : if (*b != BP) { hpSig |= 0x0001; ++nMoved; } /* h7 */
320 : // clang-format on
321 :
322 : return {static_cast<uint16_t>(hpSig), static_cast<uint16_t>(nMoved)};
323 : }
324 :
325 : inline bool hpSig_match(int hpSig, int nMoved, const byte* changeList) {
326 : // The first byte of a changeList is the length (in halfbytes) of the
327 : // list, which can be any value from 0 to 16 inclusive.
328 : if (*changeList == 16 && nMoved == 16)
329 : return true;
330 : if (*changeList++ < nMoved)
331 : return false;
332 :
333 : int sig = 0;
334 : for (int i = 0, n = nMoved / 2; i < n; ++i) {
335 : sig |= 1 << (*changeList >> 4);
336 : sig |= 1 << (*changeList++ & 0x0F);
337 : }
338 : if (nMoved & 1)
339 : sig |= 1 << (*changeList >> 4);
340 :
341 : return sig == hpSig;
342 : }
343 :
344 : #endif
345 :
346 : //////////////////////////////////////////////////////////////////////
347 : // EOF: matsig.h
348 : //////////////////////////////////////////////////////////////////////
349 :
|
