1 |
/* |
2 |
* Copyright (C) 1998-2002 Gary Wong <gtw@gnu.org> |
3 |
* Copyright (C) 2000-2014 the AUTHORS |
4 |
* |
5 |
* This program is free software: you can redistribute it and/or modify |
6 |
* it under the terms of the GNU General Public License as published by |
7 |
* the Free Software Foundation, either version 3 of the License, or |
8 |
* (at your option) any later version. |
9 |
* |
10 |
* This program 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 this program. If not, see <https://www.gnu.org/licenses/>. |
17 |
* |
18 |
* |
19 |
* An implementation of the legacy position key/ID described at: |
20 |
* https://www.gnu.org/software/gnubg/manual/gnubg.html#gnubg-tech_postionid |
21 |
* |
22 |
* This encoding creates IDs as compact as possible. |
23 |
* |
24 |
* For internal use in moves generation and evaluation we now use another |
25 |
* key, much faster to encode or decode, that is essentially the raw board |
26 |
* squeezed down to 4 bits/point. |
27 |
* |
28 |
* This library also calculates bearoff IDs, which are enumerations of the |
29 |
* |
30 |
* c+6 |
31 |
* C |
32 |
* 6 |
33 |
* |
34 |
* combinations of (up to c) chequers among 6 points. |
35 |
* |
36 |
* |
37 |
* $Id: positionid.c,v 1.56 2021/01/26 22:09:24 plm Exp $ |
38 |
*/ |
39 |
|
40 |
#include "config.h" |
41 |
#include <glib.h> |
42 |
#include <errno.h> |
43 |
#include <string.h> |
44 |
#include "positionid.h" |
45 |
|
46 |
extern void |
47 |
PositionKey(const TanBoard anBoard, positionkey * pkey) |
48 |
{ |
49 |
unsigned int i, j; |
50 |
unsigned int *anpBoard = pkey->data; |
51 |
|
52 |
for (i = 0, j = 0; i < 3; i++, j += 8) { |
53 |
anpBoard[i] = anBoard[1][j] + (anBoard[1][j + 1] << 4) |
54 |
+ (anBoard[1][j + 2] << 8) + (anBoard[1][j + 3] << 12) |
55 |
+ (anBoard[1][j + 4] << 16) + (anBoard[1][j + 5] << 20) |
56 |
+ (anBoard[1][j + 6] << 24) + (anBoard[1][j + 7] << 28); |
57 |
anpBoard[i + 3] = anBoard[0][j] + (anBoard[0][j + 1] << 4) |
58 |
+ (anBoard[0][j + 2] << 8) + (anBoard[0][j + 3] << 12) |
59 |
+ (anBoard[0][j + 4] << 16) + (anBoard[0][j + 5] << 20) |
60 |
+ (anBoard[0][j + 6] << 24) + (anBoard[0][j + 7] << 28); |
61 |
} |
62 |
anpBoard[6] = anBoard[0][24] + (anBoard[1][24] << 4); |
63 |
} |
64 |
|
65 |
extern void |
66 |
PositionFromKey(TanBoard anBoard, const positionkey * pkey) |
67 |
{ |
68 |
unsigned int i, j; |
69 |
unsigned int const *anpBoard = pkey->data; |
70 |
|
71 |
for (i = 0, j = 0; i < 3; i++, j += 8) { |
72 |
anBoard[1][j] = anpBoard[i] & 0x0f; |
73 |
anBoard[1][j + 1] = (anpBoard[i] >> 4) & 0x0f; |
74 |
anBoard[1][j + 2] = (anpBoard[i] >> 8) & 0x0f; |
75 |
anBoard[1][j + 3] = (anpBoard[i] >> 12) & 0x0f; |
76 |
anBoard[1][j + 4] = (anpBoard[i] >> 16) & 0x0f; |
77 |
anBoard[1][j + 5] = (anpBoard[i] >> 20) & 0x0f; |
78 |
anBoard[1][j + 6] = (anpBoard[i] >> 24) & 0x0f; |
79 |
anBoard[1][j + 7] = (anpBoard[i] >> 28) & 0x0f; |
80 |
|
81 |
anBoard[0][j] = anpBoard[i + 3] & 0x0f; |
82 |
anBoard[0][j + 1] = (anpBoard[i + 3] >> 4) & 0x0f; |
83 |
anBoard[0][j + 2] = (anpBoard[i + 3] >> 8) & 0x0f; |
84 |
anBoard[0][j + 3] = (anpBoard[i + 3] >> 12) & 0x0f; |
85 |
anBoard[0][j + 4] = (anpBoard[i + 3] >> 16) & 0x0f; |
86 |
anBoard[0][j + 5] = (anpBoard[i + 3] >> 20) & 0x0f; |
87 |
anBoard[0][j + 6] = (anpBoard[i + 3] >> 24) & 0x0f; |
88 |
anBoard[0][j + 7] = (anpBoard[i + 3] >> 28) & 0x0f; |
89 |
} |
90 |
anBoard[0][24] = anpBoard[6] & 0x0f; |
91 |
anBoard[1][24] = (anpBoard[6] >> 4) & 0x0f; |
92 |
} |
93 |
|
94 |
/* In evaluations, the function above is often followed by swapping |
95 |
* the board. This is expensive (SwapSides is about as costly as |
96 |
* PositionFromKey itself). |
97 |
* Provide one that fills the board already swapped. */ |
98 |
|
99 |
extern void |
100 |
PositionFromKeySwapped(TanBoard anBoard, const positionkey * pkey) |
101 |
{ |
102 |
unsigned int i, j; |
103 |
unsigned int const *anpBoard = pkey->data; |
104 |
|
105 |
for (i = 0, j = 0; i < 3; i++, j += 8) { |
106 |
anBoard[0][j] = anpBoard[i] & 0x0f; |
107 |
anBoard[0][j + 1] = (anpBoard[i] >> 4) & 0x0f; |
108 |
anBoard[0][j + 2] = (anpBoard[i] >> 8) & 0x0f; |
109 |
anBoard[0][j + 3] = (anpBoard[i] >> 12) & 0x0f; |
110 |
anBoard[0][j + 4] = (anpBoard[i] >> 16) & 0x0f; |
111 |
anBoard[0][j + 5] = (anpBoard[i] >> 20) & 0x0f; |
112 |
anBoard[0][j + 6] = (anpBoard[i] >> 24) & 0x0f; |
113 |
anBoard[0][j + 7] = (anpBoard[i] >> 28) & 0x0f; |
114 |
|
115 |
anBoard[1][j] = anpBoard[i + 3] & 0x0f; |
116 |
anBoard[1][j + 1] = (anpBoard[i + 3] >> 4) & 0x0f; |
117 |
anBoard[1][j + 2] = (anpBoard[i + 3] >> 8) & 0x0f; |
118 |
anBoard[1][j + 3] = (anpBoard[i + 3] >> 12) & 0x0f; |
119 |
anBoard[1][j + 4] = (anpBoard[i + 3] >> 16) & 0x0f; |
120 |
anBoard[1][j + 5] = (anpBoard[i + 3] >> 20) & 0x0f; |
121 |
anBoard[1][j + 6] = (anpBoard[i + 3] >> 24) & 0x0f; |
122 |
anBoard[1][j + 7] = (anpBoard[i + 3] >> 28) & 0x0f; |
123 |
} |
124 |
anBoard[1][24] = anpBoard[6] & 0x0f; |
125 |
anBoard[0][24] = (anpBoard[6] >> 4) & 0x0f; |
126 |
} |
127 |
|
128 |
static inline void |
129 |
addBits(unsigned char auchKey[10], unsigned int bitPos, unsigned int nBits) |
130 |
{ |
131 |
unsigned int k = bitPos / 8; |
132 |
unsigned int r = (bitPos & 0x7); |
133 |
unsigned int b = (((unsigned int) 0x1 << nBits) - 1) << r; |
134 |
|
135 |
auchKey[k] |= (unsigned char) b; |
136 |
|
137 |
if (k < 8) { |
138 |
auchKey[k + 1] |= (unsigned char) (b >> 8); |
139 |
auchKey[k + 2] |= (unsigned char) (b >> 16); |
140 |
} else if (k == 8) { |
141 |
auchKey[k + 1] |= (unsigned char) (b >> 8); |
142 |
} |
143 |
} |
144 |
|
145 |
extern void |
146 |
oldPositionKey(const TanBoard anBoard, oldpositionkey * pkey) |
147 |
{ |
148 |
unsigned int i, iBit = 0; |
149 |
const unsigned int *j; |
150 |
|
151 |
memset(pkey, 0, sizeof(oldpositionkey)); |
152 |
|
153 |
for (i = 0; i < 2; ++i) { |
154 |
const unsigned int *const b = anBoard[i]; |
155 |
for (j = b; j < b + 25; ++j) { |
156 |
const unsigned int nc = *j; |
157 |
|
158 |
if (nc) { |
159 |
addBits(pkey->auch, iBit, nc); |
160 |
iBit += nc + 1; |
161 |
} else { |
162 |
++iBit; |
163 |
} |
164 |
} |
165 |
} |
166 |
} |
167 |
|
168 |
extern void |
169 |
oldPositionFromKey(TanBoard anBoard, const oldpositionkey * pkey) |
170 |
{ |
171 |
int i = 0, j = 0, k; |
172 |
const unsigned char *a; |
173 |
|
174 |
memset(anBoard[0], 0, sizeof(anBoard[0])); |
175 |
memset(anBoard[1], 0, sizeof(anBoard[1])); |
176 |
|
177 |
for (a = pkey->auch; a < pkey->auch + 10; ++a) { |
178 |
unsigned char cur = *a; |
179 |
|
180 |
for (k = 0; k < 8; ++k) { |
181 |
if ((cur & 0x1)) { |
182 |
if (i >= 2 || j >= 25) { /* Error, so return - will probably show error message */ |
183 |
return; |
184 |
} |
185 |
++anBoard[i][j]; |
186 |
} else { |
187 |
if (++j == 25) { |
188 |
++i; |
189 |
j = 0; |
190 |
} |
191 |
} |
192 |
cur >>= 1; |
193 |
} |
194 |
} |
195 |
} |
196 |
|
197 |
|
198 |
static char * |
199 |
oldPositionIDFromKey(const oldpositionkey * pkey) |
200 |
{ |
201 |
unsigned char const *puch = pkey->auch; |
202 |
static char szID[L_POSITIONID + 1]; |
203 |
char *pch = szID; |
204 |
static const char aszBase64[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; |
205 |
int i; |
206 |
|
207 |
for (i = 0; i < 3; i++) { |
208 |
*pch++ = aszBase64[puch[0] >> 2]; |
209 |
*pch++ = aszBase64[((puch[0] & 0x03) << 4) | (puch[1] >> 4)]; |
210 |
*pch++ = aszBase64[((puch[1] & 0x0F) << 2) | (puch[2] >> 6)]; |
211 |
*pch++ = aszBase64[puch[2] & 0x3F]; |
212 |
|
213 |
puch += 3; |
214 |
} |
215 |
|
216 |
*pch++ = aszBase64[*puch >> 2]; |
217 |
*pch++ = aszBase64[(*puch & 0x03) << 4]; |
218 |
|
219 |
*pch = 0; |
220 |
|
221 |
return szID; |
222 |
} |
223 |
|
224 |
extern char * |
225 |
PositionIDFromKey(const positionkey * pkey) |
226 |
{ |
227 |
TanBoard anBoard; |
228 |
oldpositionkey okey; |
229 |
|
230 |
PositionFromKey(anBoard, pkey); |
231 |
oldPositionKey((ConstTanBoard) anBoard, &okey); |
232 |
|
233 |
return oldPositionIDFromKey(&okey); |
234 |
} |
235 |
|
236 |
extern char * |
237 |
PositionID(const TanBoard anBoard) |
238 |
{ |
239 |
oldpositionkey key; |
240 |
|
241 |
oldPositionKey(anBoard, &key); |
242 |
|
243 |
return oldPositionIDFromKey(&key); |
244 |
} |
245 |
|
246 |
extern int |
247 |
PositionFromXG(TanBoard anBoard, const char *pos) |
248 |
{ |
249 |
int i; |
250 |
|
251 |
for (i = 0; i < 26; i++) { |
252 |
int p0, p1; |
253 |
|
254 |
if (i == 0) { |
255 |
p0 = 24; |
256 |
p1 = -1; |
257 |
} else if (i == 25) { |
258 |
p0 = -1; |
259 |
p1 = 24; |
260 |
} else { |
261 |
p0 = 24 - i; |
262 |
p1 = i - 1; |
263 |
} |
264 |
|
265 |
if (pos[i] >= 'A' && pos[i] <= 'P') { |
266 |
if (p0 > -1) |
267 |
anBoard[0][p0] = 0; |
268 |
anBoard[1][p1] = (unsigned int) (pos[i] - 'A' + 1); |
269 |
} else if (pos[i] >= 'a' && pos[i] <= 'p') { |
270 |
anBoard[0][p0] = (unsigned int) (pos[i] - 'a' + 1); |
271 |
if (p1 > -1) |
272 |
anBoard[1][p1] = 0; |
273 |
} else if (pos[i] == '-') { |
274 |
if (p0 > -1) |
275 |
anBoard[0][p0] = 0; |
276 |
if (p1 > -1) |
277 |
anBoard[1][p1] = 0; |
278 |
} else { |
279 |
return 1; |
280 |
} |
281 |
} |
282 |
return 0; |
283 |
} |
284 |
|
285 |
extern int |
286 |
CheckPosition(const TanBoard anBoard) |
287 |
{ |
288 |
unsigned int ac[2], i; |
289 |
|
290 |
/* Check for a player with over 15 chequers */ |
291 |
for (i = ac[0] = ac[1] = 0; i < 25; i++) |
292 |
if ((ac[0] += anBoard[0][i]) > 15 || (ac[1] += anBoard[1][i]) > 15) { |
293 |
errno = EINVAL; |
294 |
return 0; |
295 |
} |
296 |
|
297 |
/* Check for both players having chequers on the same point */ |
298 |
for (i = 0; i < 24; i++) |
299 |
if (anBoard[0][i] && anBoard[1][23 - i]) { |
300 |
errno = EINVAL; |
301 |
return 0; |
302 |
} |
303 |
|
304 |
/* Check for both players on the bar against closed boards */ |
305 |
for (i = 0; i < 6; i++) |
306 |
if (anBoard[0][i] < 2 || anBoard[1][i] < 2) |
307 |
return 1; |
308 |
|
309 |
if (!anBoard[0][24] || !anBoard[1][24]) |
310 |
return 1; |
311 |
|
312 |
errno = EINVAL; |
313 |
return 0; |
314 |
} |
315 |
|
316 |
extern void |
317 |
ClosestLegalPosition(TanBoard anBoard) |
318 |
{ |
319 |
unsigned int i, j, ac[2]; |
320 |
|
321 |
/* Limit each player to 15 chequers */ |
322 |
for (i = 0; i < 2; i++) { |
323 |
ac[i] = 15; |
324 |
for (j = 0; j < 25; j++) { |
325 |
if (anBoard[i][j] <= ac[i]) |
326 |
ac[i] -= anBoard[i][j]; |
327 |
else { |
328 |
anBoard[i][j] = ac[i]; |
329 |
ac[i] = 0; |
330 |
} |
331 |
} |
332 |
} |
333 |
|
334 |
/* Forbid both players having a chequer on the same point */ |
335 |
for (i = 0; i < 24; i++) |
336 |
if (anBoard[0][i]) |
337 |
anBoard[1][23 - i] = 0; |
338 |
|
339 |
/* If both players have closed boards, let at least one of them off |
340 |
* the bar */ |
341 |
for (i = 0; i < 6; i++) |
342 |
if (anBoard[0][i] < 2 || anBoard[1][i] < 2) |
343 |
/* open board */ |
344 |
return; |
345 |
|
346 |
if (anBoard[0][24]) |
347 |
anBoard[1][24] = 0; |
348 |
} |
349 |
|
350 |
extern unsigned char |
351 |
Base64(const unsigned char ch) |
352 |
{ |
353 |
if (ch >= 'A' && ch <= 'Z') |
354 |
return (unsigned char)(ch - 'A'); |
355 |
|
356 |
if (ch >= 'a' && ch <= 'z') |
357 |
return (unsigned char)(ch - 'a' + 26); |
358 |
|
359 |
if (ch >= '0' && ch <= '9') |
360 |
return (unsigned char)(ch - '0' + 52); |
361 |
|
362 |
if (ch == '+') |
363 |
return 62; |
364 |
|
365 |
if (ch == '/') |
366 |
return 63; |
367 |
|
368 |
return 255; |
369 |
} |
370 |
|
371 |
extern int |
372 |
PositionFromID(TanBoard anBoard, const char *pchEnc) |
373 |
{ |
374 |
oldpositionkey key; |
375 |
unsigned char ach[L_POSITIONID + 1], *pch = ach, *puch = key.auch; |
376 |
int i; |
377 |
|
378 |
memset(ach, 0, L_POSITIONID + 1); |
379 |
|
380 |
for (i = 0; i < L_POSITIONID && pchEnc[i]; i++) |
381 |
pch[i] = Base64((unsigned char) pchEnc[i]); |
382 |
|
383 |
for (i = 0; i < 3; i++) { |
384 |
*puch++ = (unsigned char) (pch[0] << 2) | (pch[1] >> 4); |
385 |
*puch++ = (unsigned char) (pch[1] << 4) | (pch[2] >> 2); |
386 |
*puch++ = (unsigned char) (pch[2] << 6) | pch[3]; |
387 |
|
388 |
pch += 4; |
389 |
} |
390 |
|
391 |
*puch = (unsigned char) (pch[0] << 2) | (pch[1] >> 4); |
392 |
|
393 |
oldPositionFromKey(anBoard, &key); |
394 |
|
395 |
return CheckPosition((ConstTanBoard) anBoard); |
396 |
} |
397 |
|
398 |
extern int |
399 |
EqualBoards(const TanBoard anBoard0, const TanBoard anBoard1) |
400 |
{ |
401 |
|
402 |
int i; |
403 |
|
404 |
for (i = 0; i < 25; i++) |
405 |
if (anBoard0[0][i] != anBoard1[0][i] || anBoard0[1][i] != anBoard1[1][i]) |
406 |
return 0; |
407 |
|
408 |
return 1; |
409 |
} |
410 |
|
411 |
#define MAX_N 40 |
412 |
#define MAX_R 25 |
413 |
|
414 |
static unsigned int anCombination[MAX_N][MAX_R], fCalculated = 0; |
415 |
|
416 |
static void |
417 |
InitCombination(void) |
418 |
{ |
419 |
unsigned int i, j; |
420 |
|
421 |
for (i = 0; i < MAX_N; i++) |
422 |
anCombination[i][0] = i + 1; |
423 |
|
424 |
for (j = 1; j < MAX_R; j++) |
425 |
anCombination[0][j] = 0; |
426 |
|
427 |
for (i = 1; i < MAX_N; i++) |
428 |
for (j = 1; j < MAX_R; j++) |
429 |
anCombination[i][j] = anCombination[i - 1][j - 1] + anCombination[i - 1][j]; |
430 |
|
431 |
fCalculated = 1; |
432 |
} |
433 |
|
434 |
extern unsigned int |
435 |
Combination(const unsigned int n, const unsigned int r) |
436 |
{ |
437 |
g_assert(n <= MAX_N && r <= MAX_R); |
438 |
|
439 |
if (!fCalculated) |
440 |
InitCombination(); |
441 |
|
442 |
return anCombination[n - 1][r - 1]; |
443 |
} |
444 |
|
445 |
static unsigned int |
446 |
PositionF(unsigned int fBits, unsigned int n, unsigned int r) |
447 |
{ |
448 |
if (n == r) |
449 |
return 0; |
450 |
|
451 |
return (fBits & (1u << (n - 1))) ? Combination(n - 1, r) + |
452 |
PositionF(fBits, n - 1, r - 1) : PositionF(fBits, n - 1, r); |
453 |
} |
454 |
|
455 |
extern unsigned int |
456 |
PositionBearoff(const unsigned int anBoard[], unsigned int nPoints, unsigned int nChequers) |
457 |
{ |
458 |
unsigned int i, fBits, j; |
459 |
|
460 |
if (nPoints == 0) { |
461 |
g_assert_not_reached(); |
462 |
return 0; |
463 |
} |
464 |
|
465 |
for (j = nPoints - 1, i = 0; i < nPoints; i++) |
466 |
j += anBoard[i]; |
467 |
|
468 |
fBits = 1u << j; |
469 |
|
470 |
for (i = 0; i < nPoints - 1; i++) { |
471 |
j -= anBoard[i] + 1; |
472 |
fBits |= (1u << j); |
473 |
} |
474 |
|
475 |
return PositionF(fBits, nChequers + nPoints, nPoints); |
476 |
} |
477 |
|
478 |
static unsigned int |
479 |
PositionInv(unsigned int nID, unsigned int n, unsigned int r) |
480 |
{ |
481 |
unsigned int nC; |
482 |
|
483 |
if (!r) |
484 |
return 0; |
485 |
else if (n == r) |
486 |
return (1u << n) - 1; |
487 |
|
488 |
nC = Combination(n - 1, r); |
489 |
|
490 |
return (nID >= nC) ? (1u << (n - 1)) | PositionInv(nID - nC, n - 1, r - 1) : PositionInv(nID, n - 1, r); |
491 |
} |
492 |
|
493 |
extern void |
494 |
PositionFromBearoff(unsigned int anBoard[], unsigned int usID, unsigned int nPoints, unsigned int nChequers) |
495 |
{ |
496 |
unsigned int fBits = PositionInv(usID, nChequers + nPoints, nPoints); |
497 |
unsigned int i, j; |
498 |
|
499 |
for (i = 0; i < nPoints; i++) |
500 |
anBoard[i] = 0; |
501 |
|
502 |
j = nPoints - 1; |
503 |
for (i = 0; i < (nChequers + nPoints); i++) { |
504 |
if (fBits & (1u << i)) { |
505 |
if (j == 0) |
506 |
break; |
507 |
j--; |
508 |
} else |
509 |
anBoard[j]++; |
510 |
} |
511 |
} |
512 |
|
513 |
extern unsigned short |
514 |
PositionIndex(unsigned int g, const unsigned int anBoard[6]) |
515 |
{ |
516 |
unsigned int i, fBits; |
517 |
unsigned int j; |
518 |
|
519 |
if (g == 0) { |
520 |
g_assert_not_reached(); |
521 |
return 0; |
522 |
} |
523 |
|
524 |
j = g - 1; |
525 |
|
526 |
for (i = 0; i < g; i++) |
527 |
j += anBoard[i]; |
528 |
|
529 |
fBits = 1u << j; |
530 |
|
531 |
for (i = 0; i < g - 1; i++) { |
532 |
j -= anBoard[i] + 1; |
533 |
fBits |= (1u << j); |
534 |
} |
535 |
|
536 |
/* FIXME: 15 should be replaced by nChequers, but the function is |
537 |
* only called from bearoffgammon, so this should be fine. */ |
538 |
return (unsigned short) PositionF(fBits, 15, g); |
539 |
} |