Scid  4.7.0
matsig.h
Go to the documentation of this file.
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
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
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
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 
177 
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
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 inline matSigT matsig_Make(const byte* materialCounts) {
226  matSigT m = 0;
227  m |= std::min<matSigT>(3, materialCounts[WQ]) << SHIFT_WQ;
228  m |= std::min<matSigT>(3, materialCounts[WR]) << SHIFT_WR;
229  m |= std::min<matSigT>(3, materialCounts[WB]) << SHIFT_WB;
230  m |= std::min<matSigT>(3, materialCounts[WN]) << SHIFT_WN;
231  m |= matSigT(materialCounts[WP]) << SHIFT_WP;
232  m |= std::min<matSigT>(3, materialCounts[BQ]) << SHIFT_BQ;
233  m |= std::min<matSigT>(3, materialCounts[BR]) << SHIFT_BR;
234  m |= std::min<matSigT>(3, materialCounts[BB]) << SHIFT_BB;
235  m |= std::min<matSigT>(3, materialCounts[BN]) << SHIFT_BN;
236  m |= matSigT(materialCounts[BP]) << SHIFT_BP;
237  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
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
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
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 
unsigned char byte
Definition: common.h:89
#define MASK_WQ
Definition: matsig.h:63
uint hpSig_ClearPawn(uint hpSig, colorT color, fyleT fyle)
Definition: matsig.h:282
const pieceT BB
Definition: common.h:242
#define MASK_WR
Definition: matsig.h:62
uint hpSig_Final(const byte *changeList)
Definition: matsig.cpp:177
const uint HPSIG_Empty
Definition: matsig.h:246
#define MASK_BR
Definition: matsig.h:57
const colorT WHITE
Definition: common.h:207
#define MASK_BQ
Definition: matsig.h:58
const pieceT BN
Definition: common.h:242
#define MASK_WB
Definition: matsig.h:61
bool hpSig_Prefix(const byte *changeListA, const byte *changeListB)
Definition: matsig.cpp:140
#define SHIFT_WR
Definition: matsig.h:48
#define ASSERT(f)
Definition: common.h:59
const pieceT BQ
Definition: common.h:242
#define SHIFT_BR
Definition: matsig.h:43
uint32_t matSigT
Definition: matsig.h:25
#define SHIFT_BP
Definition: matsig.h:40
const pieceT WQ
Definition: common.h:241
#define MASK_WN
Definition: matsig.h:60
const pieceT BP
Definition: common.h:242
const colorT BLACK
Definition: common.h:208
matSigT matsig_setCount(matSigT m, pieceT p, uint count)
Definition: matsig.h:159
byte fyleT
Definition: common.h:108
const fyleT H_FYLE
Definition: common.h:366
#define MASK_BN
Definition: matsig.h:55
const uint SHIFT_BY_PIECE[16]
Definition: matsig.h:89
const uint HPSIG_StdStart
Definition: matsig.h:249
const squareT A7
Definition: common.h:354
#define SHIFT_WP
Definition: matsig.h:45
#define SHIFT_WN
Definition: matsig.h:46
#define MASK_WP
Definition: matsig.h:59
bool hpSig_match(int hpSig, int nMoved, const byte *changeList)
Definition: matsig.h:325
const matSigT MATSIG_Empty
Definition: matsig.h:176
const pieceT WB
Definition: common.h:241
const matSigT MATSIG_StdStart
Definition: matsig.h:178
uint32_t uint
Definition: common.h:91
Definition: board.tcl:276
uint matsig_getCount(matSigT m, pieceT p)
Definition: matsig.h:149
std::string matsig_makeString(matSigT matsig)
Definition: matsig.cpp:27
bool matsig_isReachable(matSigT mStart, matSigT mTarget, bool promos, bool upromo)
Definition: matsig.cpp:56
#define SHIFT_BB
Definition: matsig.h:42
const pieceT PAWN
Definition: common.h:231
#define MASK_BP
Definition: matsig.h:54
bool hpSig_PossibleMatch(uint hpSig, const byte *changeList)
Definition: matsig.cpp:97
bool matsig_isReachablePawns(matSigT mStart, matSigT mTarget)
Definition: matsig.h:213
const matSigT MASK_BY_PIECE[16]
Definition: matsig.h:70
colorpct ?col?
Definition: ptracker.tcl:77
#define SHIFT_WQ
Definition: matsig.h:49
#define MATSIG_Count_WP(x)
Definition: matsig.h:141
const pieceT WP
Definition: common.h:241
#define SHIFT_BQ
Definition: matsig.h:44
#define MASK_BB
Definition: matsig.h:56
const squareT A2
Definition: common.h:349
byte colorT
Definition: common.h:104
#define MATSIG_Count_BP(x)
Definition: matsig.h:142
const pieceT BR
Definition: common.h:242
std::pair< uint16_t, uint16_t > hpSig_make(const pieceT *board)
Creates a 16-bits bitmap of the missing pawns in the home ranks.
Definition: matsig.h:298
const pieceT WN
Definition: common.h:241
#define SHIFT_WB
Definition: matsig.h:47
uint hpSig_AddPawn(uint hpSig, colorT color, fyleT fyle)
Definition: matsig.h:271
matSigT matsig_Make(const byte *materialCounts)
Definition: matsig.h:225
#define SHIFT_BN
Definition: matsig.h:41
byte pieceT
Definition: common.h:103
const pieceT WR
Definition: common.h:241