1 /*
2 * positionid.c
3 *
4 * by Gary Wong <gary@cs.arizona.edu>, 1998-1999.
5 *
6 * An implementation of the position "external" key/IDs at:
7 *
8 * http://www.gnu.org/manual/gnubg/html_node/A-technical-description-of-the-Position-ID.html
9 *
10 * Please see that page for more information.
11 *
12 * For internal use, we use another "key", much faster to encode or decode
13 * that is essentially the raw board squeezed down to 4 bits/point.
14 *
15 * This library also calculates bearoff IDs, which are enumerations of the
16 *
17 * c+6
18 * C
19 * 6
20 *
21 * combinations of (up to c) chequers among 6 points.
22 *
23 *
24 * This program is free software; you can redistribute it and/or modify
25 * it under the terms of version 3 or later of the GNU General Public License as
26 * published by the Free Software Foundation.
27 *
28 * This program is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU General Public License for more details.
32 *
33 * You should have received a copy of the GNU General Public License
34 * along with this program; if not, write to the Free Software
35 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
36 *
37 * $Id: positionid.c,v 1.54 2014/10/07 07:14:28 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
PositionKey(const TanBoard anBoard,positionkey * pkey)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
PositionFromKey(TanBoard anBoard,const positionkey * pkey)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
PositionFromKeySwapped(TanBoard anBoard,const positionkey * pkey)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
addBits(unsigned char auchKey[10],unsigned int bitPos,unsigned int nBits)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
oldPositionKey(const TanBoard anBoard,oldpositionkey * pkey)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
oldPositionFromKey(TanBoard anBoard,const oldpositionkey * pkey)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 *
oldPositionIDFromKey(const oldpositionkey * pkey)199 oldPositionIDFromKey(const oldpositionkey * pkey)
200 {
201
202 unsigned char const *puch = pkey->auch;
203 static char szID[L_POSITIONID + 1];
204 char *pch = szID;
205 static char aszBase64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
206 int i;
207
208 for (i = 0; i < 3; i++) {
209 *pch++ = aszBase64[puch[0] >> 2];
210 *pch++ = aszBase64[((puch[0] & 0x03) << 4) | (puch[1] >> 4)];
211 *pch++ = aszBase64[((puch[1] & 0x0F) << 2) | (puch[2] >> 6)];
212 *pch++ = aszBase64[puch[2] & 0x3F];
213
214 puch += 3;
215 }
216
217 *pch++ = aszBase64[*puch >> 2];
218 *pch++ = aszBase64[(*puch & 0x03) << 4];
219
220 *pch = 0;
221
222 return szID;
223 }
224
225 extern char *
PositionIDFromKey(const positionkey * pkey)226 PositionIDFromKey(const positionkey * pkey)
227 {
228
229 TanBoard anBoard;
230 oldpositionkey okey;
231
232 PositionFromKey(anBoard, pkey);
233 oldPositionKey((ConstTanBoard) anBoard, &okey);
234
235 return oldPositionIDFromKey(&okey);
236 }
237
238 extern char *
PositionID(const TanBoard anBoard)239 PositionID(const TanBoard anBoard)
240 {
241
242 oldpositionkey key;
243
244 oldPositionKey(anBoard, &key);
245
246 return oldPositionIDFromKey(&key);
247 }
248
249 extern int
PositionFromXG(TanBoard anBoard,const char * pos)250 PositionFromXG(TanBoard anBoard, const char *pos)
251 {
252 int i;
253
254 for (i = 0; i < 26; i++) {
255 int p0, p1;
256
257 if (i == 0) {
258 p0 = 24;
259 p1 = -1;
260 } else if (i == 25) {
261 p0 = -1;
262 p1 = 24;
263 } else {
264 p0 = 24 - i;
265 p1 = i - 1;
266 }
267
268 if (pos[i] >= 'A' && pos[i] <= 'P') {
269 if (p0 > -1)
270 anBoard[0][p0] = 0;
271 anBoard[1][p1] = pos[i] - 'A' + 1;
272 } else if (pos[i] >= 'a' && pos[i] <= 'p') {
273 anBoard[0][p0] = pos[i] - 'a' + 1;
274 if (p1 > -1)
275 anBoard[1][p1] = 0;
276 } else if (pos[i] == '-') {
277 if (p0 > -1)
278 anBoard[0][p0] = 0;
279 if (p1 > -1)
280 anBoard[1][p1] = 0;
281 } else {
282 return 1;
283 }
284 }
285 return 0;
286 }
287
288 extern int
CheckPosition(const TanBoard anBoard)289 CheckPosition(const TanBoard anBoard)
290 {
291 unsigned int ac[2], i;
292
293 /* Check for a player with over 15 chequers */
294 for (i = ac[0] = ac[1] = 0; i < 25; i++)
295 if ((ac[0] += anBoard[0][i]) > 15 || (ac[1] += anBoard[1][i]) > 15) {
296 errno = EINVAL;
297 return 0;
298 }
299
300 /* Check for both players having chequers on the same point */
301 for (i = 0; i < 24; i++)
302 if (anBoard[0][i] && anBoard[1][23 - i]) {
303 errno = EINVAL;
304 return 0;
305 }
306
307 /* Check for both players on the bar against closed boards */
308 for (i = 0; i < 6; i++)
309 if (anBoard[0][i] < 2 || anBoard[1][i] < 2)
310 return 1;
311
312 if (!anBoard[0][24] || !anBoard[1][24])
313 return 1;
314
315 errno = EINVAL;
316 return 0;
317 }
318
319 extern void
ClosestLegalPosition(TanBoard anBoard)320 ClosestLegalPosition(TanBoard anBoard)
321 {
322 unsigned int i, j, ac[2];
323
324 /* Limit each player to 15 chequers */
325 for (i = 0; i < 2; i++) {
326 ac[i] = 15;
327 for (j = 0; j < 25; j++) {
328 if (anBoard[i][j] <= ac[i])
329 ac[i] -= anBoard[i][j];
330 else {
331 anBoard[i][j] = ac[i];
332 ac[i] = 0;
333 }
334 }
335 }
336
337 /* Forbid both players having a chequer on the same point */
338 for (i = 0; i < 24; i++)
339 if (anBoard[0][i])
340 anBoard[1][23 - i] = 0;
341
342 /* If both players have closed boards, let at least one of them off
343 * the bar */
344 for (i = 0; i < 6; i++)
345 if (anBoard[0][i] < 2 || anBoard[1][i] < 2)
346 /* open board */
347 return;
348
349 if (anBoard[0][24])
350 anBoard[1][24] = 0;
351 }
352
353 extern unsigned char
Base64(const unsigned char ch)354 Base64(const unsigned char ch)
355 {
356 if (ch >= 'A' && ch <= 'Z')
357 return ch - 'A';
358
359 if (ch >= 'a' && ch <= 'z')
360 return (ch - 'a') + 26;
361
362 if (ch >= '0' && ch <= '9')
363 return (ch - '0') + 52;
364
365 if (ch == '+')
366 return 62;
367
368 if (ch == '/')
369 return 63;
370
371 return 255;
372 }
373
374 extern int
PositionFromID(TanBoard anBoard,const char * pchEnc)375 PositionFromID(TanBoard anBoard, const char *pchEnc)
376 {
377 oldpositionkey key;
378 unsigned char ach[L_POSITIONID + 1], *pch = ach, *puch = key.auch;
379 int i;
380
381 memset(ach, 0, L_POSITIONID + 1);
382
383 for (i = 0; i < L_POSITIONID && pchEnc[i]; i++)
384 pch[i] = Base64((unsigned char) pchEnc[i]);
385
386 for (i = 0; i < 3; i++) {
387 *puch++ = (unsigned char) (pch[0] << 2) | (pch[1] >> 4);
388 *puch++ = (unsigned char) (pch[1] << 4) | (pch[2] >> 2);
389 *puch++ = (unsigned char) (pch[2] << 6) | pch[3];
390
391 pch += 4;
392 }
393
394 *puch = (unsigned char) (pch[0] << 2) | (pch[1] >> 4);
395
396 oldPositionFromKey(anBoard, &key);
397
398 return CheckPosition((ConstTanBoard) anBoard);
399 }
400
401 extern int
EqualBoards(const TanBoard anBoard0,const TanBoard anBoard1)402 EqualBoards(const TanBoard anBoard0, const TanBoard anBoard1)
403 {
404
405 int i;
406
407 for (i = 0; i < 25; i++)
408 if (anBoard0[0][i] != anBoard1[0][i] || anBoard0[1][i] != anBoard1[1][i])
409 return 0;
410
411 return 1;
412 }
413
414 #define MAX_N 40
415 #define MAX_R 25
416
417 static unsigned int anCombination[MAX_N][MAX_R], fCalculated = 0;
418
419 static void
InitCombination(void)420 InitCombination(void)
421 {
422 unsigned int i, j;
423
424 for (i = 0; i < MAX_N; i++)
425 anCombination[i][0] = i + 1;
426
427 for (j = 1; j < MAX_R; j++)
428 anCombination[0][j] = 0;
429
430 for (i = 1; i < MAX_N; i++)
431 for (j = 1; j < MAX_R; j++)
432 anCombination[i][j] = anCombination[i - 1][j - 1] + anCombination[i - 1][j];
433
434 fCalculated = 1;
435 }
436
437 extern unsigned int
Combination(const unsigned int n,const unsigned int r)438 Combination(const unsigned int n, const unsigned int r)
439 {
440 g_assert(n <= MAX_N && r <= MAX_R);
441
442 if (!fCalculated)
443 InitCombination();
444
445 return anCombination[n - 1][r - 1];
446 }
447
448 static unsigned int
PositionF(unsigned int fBits,unsigned int n,unsigned int r)449 PositionF(unsigned int fBits, unsigned int n, unsigned int r)
450 {
451 if (n == r)
452 return 0;
453
454 return (fBits & (1u << (n - 1))) ? Combination(n - 1, r) +
455 PositionF(fBits, n - 1, r - 1) : PositionF(fBits, n - 1, r);
456 }
457
458 extern unsigned int
PositionBearoff(const unsigned int anBoard[],unsigned int nPoints,unsigned int nChequers)459 PositionBearoff(const unsigned int anBoard[], unsigned int nPoints, unsigned int nChequers)
460 {
461 unsigned int i, fBits, j;
462
463 for (j = nPoints - 1, i = 0; i < nPoints; i++)
464 j += anBoard[i];
465
466 fBits = 1u << j;
467
468 for (i = 0; i < nPoints - 1; i++) {
469 j -= anBoard[i] + 1;
470 fBits |= (1u << j);
471 }
472
473 return PositionF(fBits, nChequers + nPoints, nPoints);
474 }
475
476 static unsigned int
PositionInv(unsigned int nID,unsigned int n,unsigned int r)477 PositionInv(unsigned int nID, unsigned int n, unsigned int r)
478 {
479 unsigned int nC;
480
481 if (!r)
482 return 0;
483 else if (n == r)
484 return (1u << n) - 1;
485
486 nC = Combination(n - 1, r);
487
488 return (nID >= nC) ? (1u << (n - 1)) | PositionInv(nID - nC, n - 1, r - 1) : PositionInv(nID, n - 1, r);
489 }
490
491 extern void
PositionFromBearoff(unsigned int anBoard[],unsigned int usID,unsigned int nPoints,unsigned int nChequers)492 PositionFromBearoff(unsigned int anBoard[], unsigned int usID, unsigned int nPoints, unsigned int nChequers)
493 {
494 unsigned int fBits = PositionInv(usID, nChequers + nPoints, nPoints);
495 unsigned int i, j;
496
497 for (i = 0; i < nPoints; i++)
498 anBoard[i] = 0;
499
500 j = nPoints - 1;
501 for (i = 0; i < (nChequers + nPoints); i++) {
502 if (fBits & (1u << i)) {
503 if (j == 0)
504 break;
505 j--;
506 } else
507 anBoard[j]++;
508 }
509 }
510
511 extern unsigned short
PositionIndex(unsigned int g,const unsigned int anBoard[6])512 PositionIndex(unsigned int g, const unsigned int anBoard[6])
513 {
514 unsigned int i, fBits;
515 unsigned int j = g - 1;
516
517 for (i = 0; i < g; i++)
518 j += anBoard[i];
519
520 fBits = 1u << j;
521
522 for (i = 0; i < g - 1; i++) {
523 j -= anBoard[i] + 1;
524 fBits |= (1u << j);
525 }
526
527 /* FIXME: 15 should be replaced by nChequers, but the function is
528 * only called from bearoffgammon, so this should be fine. */
529 return (unsigned short) PositionF(fBits, 15, g);
530 }
531