Scid  4.6.5
matsig.cpp
Go to the documentation of this file.
1 //////////////////////////////////////////////////////////////////////
2 //
3 // FILE: matsig.cpp
4 // Material signature routines
5 //
6 // Part of: Scid (Shane's Chess Information Database)
7 // Version: 3.3
8 //
9 // Notice: Copyright (c) 1999-2002 Shane Hudson. All rights reserved.
10 //
11 // Author: Shane Hudson (sgh@users.sourceforge.net)
12 //
13 //////////////////////////////////////////////////////////////////////
14 
15 
16 // A matsig (material signature) is a count of material by piece type,
17 // compacted into three bytes. Because it is compacted, there are limits
18 // that a game with an unusual number of promotions might break.
19 // The maximum count for a non-pawn piece is three.
20 
21 #include "matsig.h"
22 
23 
24 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
25 // matsig_makeString(): Make a string representation of a matsig.
26 std::string
28 {
29  std::string s;
30  s.reserve(32);
31  uint i;
32  for (i=0; i < MATSIG_Count_WQ(m); i++) { s+= 'Q'; }
33  for (i=0; i < MATSIG_Count_WR(m); i++) { s+= 'R'; }
34  for (i=0; i < MATSIG_Count_WB(m); i++) { s+= 'B'; }
35  for (i=0; i < MATSIG_Count_WN(m); i++) { s+= 'N'; }
36  uint wp = MATSIG_Count_WP(m);
37  if (wp > 0) s+= (wp + '0');
38  s+= ':';
39  for (i=0; i < MATSIG_Count_BQ(m); i++) { s+= 'Q'; }
40  for (i=0; i < MATSIG_Count_BR(m); i++) { s+= 'R'; }
41  for (i=0; i < MATSIG_Count_BB(m); i++) { s+= 'B'; }
42  for (i=0; i < MATSIG_Count_BN(m); i++) { s+= 'N'; }
43  uint bp = MATSIG_Count_BP(m);
44  if (bp > 0) s+= (bp + '0');
45  return s;
46 }
47 
48 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
49 // matsig_isReachable():
50 // Return 1 if start could transform into target with
51 // captures and (maybe) promotions. This is used to exclude games
52 // from a material or position search without needing to decode
53 // them, by checking each game's final position matsig.
54 //
55 bool
56 matsig_isReachable (matSigT mStart, matSigT mTarget, bool promos, bool upromo)
57 {
58  if (MATSIG_Count_WP(mStart) < MATSIG_Count_WP(mTarget)) { return false; }
59  if (MATSIG_Count_BP(mStart) < MATSIG_Count_BP(mTarget)) { return false; }
60 
61  // If there are underpromotions, we can only check pawn counts:
62  if (upromo) { return true; }
63 
64  // No underpromotions, so check non-queen piece counts:
65  if (MATSIG_Count_WR(mStart) < MATSIG_Count_WR(mTarget)) { return false; }
66  if (MATSIG_Count_BR(mStart) < MATSIG_Count_BR(mTarget)) { return false; }
67  if (MATSIG_Count_WB(mStart) < MATSIG_Count_WB(mTarget)) { return false; }
68  if (MATSIG_Count_BB(mStart) < MATSIG_Count_BB(mTarget)) { return false; }
69  if (MATSIG_Count_WN(mStart) < MATSIG_Count_WN(mTarget)) { return false; }
70  if (MATSIG_Count_BN(mStart) < MATSIG_Count_BN(mTarget)) { return false; }
71 
72  // If there were promotions we cannot check queen counts:
73  if (promos) { return true; }
74 
75  // Check queen counts:
76  if (MATSIG_Count_WQ(mStart) < MATSIG_Count_WQ(mTarget)) { return false; }
77  if (MATSIG_Count_BQ(mStart) < MATSIG_Count_BQ(mTarget)) { return false; }
78 
79  return true;
80 }
81 
82 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
83 // hpSig_PossibleMatch():
84 // Returns 1 if a game could match the home pawn signature in hpSig.
85 // The argument changeList is the ordered list of pawns that leave
86 // their home rank (by moving or being captured).
87 //
88 // Used to exclude games in exact position searches. For example,
89 // If we are looking for the position after "1.d4 d5 2.c4", the
90 // target hpSig looks like "1100111111101111" (the c2, d2 and d7
91 // pawns are gone from the home ranks).
92 //
93 // The first byte of a changeList is the length (in halfbytes) of the
94 // list, which can be any value from 0 to 16 inclusive.
95 //
96 bool
97 hpSig_PossibleMatch (uint hpSig, const byte * changeList)
98 {
99  // First, the starting sig (all pawns home) can match any game:
100  if (hpSig == HPSIG_StdStart) { return true; }
101 
102  uint hpCurrent = HPSIG_StdStart;
103  uint count = (uint) changeList[0];
104  changeList++;
105  uint halfByte = 0;
106  byte change;
107 
108  for (uint i=0; i < count; i++) {
109  if (halfByte == 0) {
110  change = (*changeList) >> 4;
111  halfByte = 1;
112  } else {
113  change = (*changeList) & 15;
114  halfByte = 0;
115  changeList++;
116  }
117  hpCurrent &= ~(1 << change);
118  if (hpCurrent == hpSig) { return true; }
119 
120  // Here is an optimisation: If the target HP sig contains a home
121  // pawn not in the current HP sig, it could never match since pawns
122  // cannot reappear on their home rank! This test is easy and fast:
123 
124  if ((hpCurrent & hpSig) != hpSig) { return false; }
125  }
126 
127  // Loop finished, no match was found.
128  return false;
129 }
130 
131 
132 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
133 // hpSig_Prefix():
134 // Returns true if one of the changeLists provided is a prefix
135 // of the other or if they are the same.
136 // Used to quickly test if one game is possibly a truncated version
137 // of another game.
138 //
139 bool
140 hpSig_Prefix (const byte * changeListA, const byte * changeListB)
141 {
142  uint countA = changeListA[0];
143  uint countB = changeListB[0];
144  changeListA++;
145  changeListB++;
146  bool halfByte = false;
147  byte changeA;
148  byte changeB;
149 
150  // Use the shorter changeList length:
151  uint count = (countA < countB ? countA : countB);
152 
153  // Check each corresponding value in the lists:
154  for (uint i=0; i < count; i++) {
155  if (halfByte) {
156  changeA = *changeListA & 15;
157  changeB = *changeListB & 15;
158  changeListA++;
159  changeListB++;
160  halfByte = false;
161  } else {
162  changeA = *changeListA >> 4;
163  changeB = *changeListB >> 4;
164  halfByte = true;
165  }
166  if (changeA != changeB) { return false; }
167  }
168  return true;
169 }
170 
171 
172 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
173 // hpSig_Final():
174 // Returns the final home pawn signature value of a changeList.
175 //
176 uint
177 hpSig_Final (const byte * changeList)
178 {
179  uint hpSig = HPSIG_StdStart;
180  uint count = (uint) changeList[0];
181  changeList++;
182  bool halfByte = false;
183  byte change;
184  for (uint i=0; i < count; i++) {
185  if (halfByte == false) {
186  change = (*changeList) >> 4;
187  halfByte = true;
188  } else {
189  change = (*changeList) & 15;
190  halfByte = false;
191  changeList++;
192  }
193  hpSig -= (1 << change);
194  }
195  return hpSig;
196 }
197 
198 //////////////////////////////////////////////////////////////////////
199 // EOF: matsig.cpp
200 //////////////////////////////////////////////////////////////////////
201 
unsigned char byte
Definition: common.h:97
#define MATSIG_Count_WN(x)
Definition: matsig.h:139
std::string matsig_makeString(matSigT m)
Definition: matsig.cpp:27
#define MATSIG_Count_BN(x)
Definition: matsig.h:140
uint32_t matSigT
Definition: matsig.h:25
#define MATSIG_Count_WR(x)
Definition: matsig.h:135
#define MATSIG_Count_BQ(x)
Definition: matsig.h:134
bool hpSig_PossibleMatch(uint hpSig, const byte *changeList)
Definition: matsig.cpp:97
#define MATSIG_Count_BR(x)
Definition: matsig.h:136
bool hpSig_Prefix(const byte *changeListA, const byte *changeListB)
Definition: matsig.cpp:140
const uint HPSIG_StdStart
Definition: matsig.h:251
uint32_t uint
Definition: common.h:99
#define MATSIG_Count_WB(x)
Definition: matsig.h:137
#define MATSIG_Count_WQ(x)
Definition: matsig.h:133
#define MATSIG_Count_WP(x)
Definition: matsig.h:141
#define MATSIG_Count_BP(x)
Definition: matsig.h:142
uint hpSig_Final(const byte *changeList)
Definition: matsig.cpp:177
#define MATSIG_Count_BB(x)
Definition: matsig.h:138
bool matsig_isReachable(matSigT mStart, matSigT mTarget, bool promos, bool upromo)
Definition: matsig.cpp:56