/[gnubg]/gnubg/positionid.c
ViewVC logotype

Contents of /gnubg/positionid.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.57 - (show annotations) (download)
Sat Dec 18 22:06:37 2021 UTC (2 years, 4 months ago) by plm
Branch: MAIN
CVS Tags: release-1_08_001, release-1_08_002, release-1_07_001, HEAD
Changes since 1.56: +2 -5 lines
File MIME type: text/plain
Declare const variables as such

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 }

savannah-hackers-public@gnu.org
ViewVC Help
Powered by ViewVC 1.1.26