1 //////////////////////////////////////////////////////////////////////
2 //
3 // FILE: mtbgen.cpp
4 // Generate memory tablebases for the Scid chess engine.
5 //
6 // Part of: Scid (Shane's Chess Information Database)
7 // Version: 3.5
8 //
9 // Notice: Copyright (c) 2003 Shane Hudson. All rights reserved.
10 //
11 // Author: Shane Hudson (sgh@users.sourceforge.net)
12 //
13 //////////////////////////////////////////////////////////////////////
14
15
16 // This program reads Nalimov-format tablebases to generate selected
17 // compressed in-memory tablebases used by the Scidlet chess program.
18 // It produces the file mtbdata.h. See mtb.h and recog.cpp for details.
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include "../common.h"
23 #include "../error.h"
24 #include "mtb.h"
25 #include "../position.h"
26 #include "../probe.h"
27
28 static const char * SLASHES =
29 "//////////////////////////////////////////////////////////////////////";
30
PAIR(uint x,uint y)31 static inline uint PAIR (uint x, uint y)
32 {
33 return x | (y << 8);
34 }
35
TRIPLET(uint x,uint y,uint z)36 static inline uint TRIPLET (uint x, uint y, uint z)
37 {
38 return x | (y << 8) | (z << 16);
39 }
40
FIRST(uint pair)41 static inline squareT FIRST (uint pair)
42 {
43 return pair & 255;
44 }
45
SECOND(uint pair)46 static inline squareT SECOND (uint pair)
47 {
48 return (pair >> 8) & 255;
49 }
50
THIRD(uint triplet)51 static inline squareT THIRD (uint triplet)
52 {
53 return (triplet >> 16) & 255;
54 }
55
56
tbFailure(const char * material,Position * pos)57 void tbFailure(const char * material, Position * pos)
58 {
59 colorT stm = pos->GetToMove();
60 fprintf (stderr, "%s %ctm: tablebase access failed\n",
61 material, color_Char(stm));
62 pos->DumpBoard (stderr);
63 exit (1);
64 }
65
uniqueSquares(squareT sq1,squareT sq2,squareT sq3)66 inline bool uniqueSquares (squareT sq1, squareT sq2, squareT sq3)
67 {
68 return (sq1 != sq2 && sq1 != sq3 && sq2 != sq3);
69 }
70
uniqueSquares(squareT sq1,squareT sq2,squareT sq3,squareT sq4)71 inline bool uniqueSquares (squareT sq1, squareT sq2, squareT sq3, squareT sq4)
72 {
73 return (sq1 != sq2 && sq1 != sq3 && sq1 != sq4
74 && sq2 != sq3 && sq2 != sq4
75 && sq3 != sq4);
76 }
77
uniqueSquares(squareT sq1,squareT sq2,squareT sq3,squareT sq4,squareT sq5)78 inline bool uniqueSquares (squareT sq1, squareT sq2, squareT sq3,
79 squareT sq4, squareT sq5)
80 {
81 return (sq1 != sq2 && sq1 != sq3 && sq1 != sq4 && sq1 != sq5
82 && sq2 != sq3 && sq2 != sq4 && sq2 != sq5
83 && sq3 != sq4 && sq3 != sq5
84 && sq4 != sq5);
85 }
86
87
88 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
89 // MTBWriter
90 // This class is used to write C++ code to setup a memory tablebase.
91 //
92 class MTBWriter
93 {
94 private:
95
96 struct mtbWriterEntryT {
97 squareT sq1, sq2, sq3;
98 colorT stm;
99 uint packedLength;
100 };
101
102 static const uint MAX_MTB_ENTRIES = 1024;
103 static const uint MAX_PACKED_BYTES = 1 << 18;
104
105 byte * PackedData;
106 uint PackedDataLength;
107 char * Name;
108 uint BitsPerResult;
109 uint NumEntries;
110 mtbWriterEntryT * Entries[MAX_MTB_ENTRIES];
111
112 public:
113 #ifdef WINCE
operator new(size_t sz)114 void* operator new(size_t sz) {
115 void* m = my_Tcl_Alloc(sz);
116 return m;
117 }
operator delete(void * m)118 void operator delete(void* m) {
119 my_Tcl_Free((char*)m);
120 }
operator new[](size_t sz)121 void* operator new [] (size_t sz) {
122 void* m = my_Tcl_AttemptAlloc(sz);
123 return m;
124 }
125
operator delete[](void * m)126 void operator delete [] (void* m) {
127 my_Tcl_Free((char*)m);
128 }
129
130 #endif
MTBWriter(const char * name,uint bitsPerResult)131 MTBWriter (const char * name, uint bitsPerResult)
132 {
133 PackedData = new byte[MAX_PACKED_BYTES];
134 PackedDataLength = 0;
135 Name = strDuplicate(name);
136 BitsPerResult = bitsPerResult;
137 NumEntries = 0;
138 }
139
~MTBWriter()140 ~MTBWriter ()
141 {
142 delete[] PackedData;
143 delete[] Name;
144 }
145
Add(ResultGrid * grid,squareT sq,colorT stm)146 void Add (ResultGrid * grid, squareT sq, colorT stm) {
147 Add (grid, sq, NS, NS, stm);
148 }
149
Add(ResultGrid * grid,squareT sq1,squareT sq2,colorT stm)150 void Add (ResultGrid * grid, squareT sq1, squareT sq2, colorT stm) {
151 Add (grid, sq1, sq2, NS, stm);
152 }
153
154 void Add (ResultGrid * grid, squareT sq1, squareT sq2, squareT sq3,
155 colorT stm);
156
157 void Write (FILE * fp);
158 };
159
160 void
Add(ResultGrid * grid,squareT sq1,squareT sq2,squareT sq3,colorT stm)161 MTBWriter::Add (ResultGrid * grid, squareT sq1, squareT sq2, squareT sq3,
162 colorT stm)
163 {
164 ASSERT (BitsPerResult == grid->GetBitsPerResult())
165 mtbWriterEntryT * entry = new mtbWriterEntryT;
166 if (NumEntries >= MAX_MTB_ENTRIES) {
167 fprintf (stderr, "Full MTBWriter: %s\n", Name);
168 exit(1);
169 }
170 Entries[NumEntries++] = entry;
171 entry->sq1 = sq1;
172 entry->sq2 = sq2;
173 entry->sq3 = sq3;
174 entry->stm = stm;
175 grid->Pack();
176 if (! grid->Verify()) {
177 fprintf (stderr, "%s data verify error\n", Name);
178 exit(1);
179 }
180 entry->packedLength = grid->GetPackedDataLength();
181 if (PackedDataLength + entry->packedLength > MAX_PACKED_BYTES) {
182 fprintf (stderr, "Full MTBWriter: %s\n", Name);
183 exit(1);
184 }
185 const byte * packedData = grid->GetPackedData();
186 for (uint i=0; i < entry->packedLength; i++) {
187 PackedData[PackedDataLength++] = *packedData++;
188 }
189 }
190
191 void
Write(FILE * fp)192 MTBWriter::Write (FILE * fp)
193 {
194 fprintf (fp, "%s\n", SLASHES);
195 fprintf (fp, "//\n");
196 fprintf (fp, "// %s\n\n", Name);
197
198 // Write the compressed data as a constant byte array:
199 fprintf (fp, "static const byte mtbdata_%s[%u] = {\n ",
200 Name, PackedDataLength);
201 uint i, width = 4;
202 for (i=0; i < PackedDataLength; i++) {
203 byte result = PackedData[i];
204 fprintf (fp, "%u", result);
205 width++;
206 if (result >= 10) { width++; }
207 if (result >= 100) { width++; }
208 if (i+1 < PackedDataLength) {
209 fprintf (fp, ",");
210 width++;
211 if (width > 70) {
212 fprintf (fp, "\n ");
213 width = 4;
214 }
215 }
216 }
217 fprintf (fp, "\n};\n\n");
218 fprintf (fp, "static MTB * mtb_%s = NULL;\n\n", Name);
219
220 // Write the MTB initialization function:
221 fprintf (fp, "void initMTB_%s()\n{\n", Name);
222 fprintf (fp, " mtb_%s = new MTB (\"%s\", %u, %u);\n",
223 Name, Name, BitsPerResult, NumEntries);
224 fprintf (fp, " mtb_%s->SetPackedData (mtbdata_%s);\n", Name, Name);
225 for (i=0; i < NumEntries; i++) {
226 mtbWriterEntryT * entry = Entries[i];
227 fprintf (fp, " mtb_%s->Add (", Name);
228 squareT sq1 = entry->sq1;
229 squareT sq2 = entry->sq2;
230 squareT sq3 = entry->sq3;
231 colorT stm = entry->stm;
232 if (sq1 != NS) {
233 fprintf (fp, "%c%c, ",
234 toupper(square_FyleChar(sq1)), square_RankChar(sq1));
235 }
236 if (sq2 != NS) {
237 fprintf (fp, "%c%c, ",
238 toupper(square_FyleChar(sq2)), square_RankChar(sq2));
239 }
240 if (sq3 != NS) {
241 fprintf (fp, "%c%c, ",
242 toupper(square_FyleChar(sq3)), square_RankChar(sq3));
243 }
244 fprintf (fp, "%s, %u);\n", stm == WHITE ? "WHITE" : "BLACK",
245 entry->packedLength);
246 }
247 fprintf (fp, "}\n\n");
248 }
249
250
251 //////////////////////////////////////////////////////////////////////
252
253 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
254 // kqk
255 // Stores every KQ-K result for White to move, 4 bits per result.
256 //
kqk(FILE * fp)257 void kqk (FILE * fp)
258 {
259 const uint bitsPerResult = 4;
260 MTBWriter * writer = new MTBWriter("KQK", bitsPerResult);
261 Position * pos = new Position();
262 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
263
264 // Black king squares:
265 squareT kingSquares[] = {
266 A1, B1, C1, D1, B2, C2, D2, C3, D3, D4,
267 NULL_SQUARE
268 };
269
270 for (colorT stm = WHITE; stm <= WHITE; stm++) {
271 squareT * bkSquares = kingSquares;
272 while (*bkSquares != NULL_SQUARE) {
273 resultGrid->Clear();
274 squareT bk = *bkSquares;
275 uint prevres = 0;
276 for (squareT wk=A1; wk <= H8; wk++) {
277 for (squareT wq=A1; wq <= H8; wq++) {
278 uint result = prevres; // Broken: just use previous result
279 if (uniqueSquares (wk, bk, wq)) {
280 pos->Clear();
281 pos->AddPiece(WK, wk);
282 pos->AddPiece(BK, bk);
283 pos->AddPiece(WQ, wq);
284 pos->SetToMove(stm);
285 if (pos->IsLegal()) {
286 int score = 0;
287 if (scid_TB_Probe (pos, &score) == OK) {
288 result = ((score < 0) ? -score : score);
289 prevres=result;
290 } else {
291 tbFailure("KQK", pos);
292 }
293 }
294 }
295 resultGrid->SetResult (result, wk, wq);
296 }
297 }
298 writer->Add(resultGrid, bk, stm);
299 resultGrid->UpdateStats ();
300 bkSquares++;
301 }
302 }
303 writer->Write(fp);
304 resultGrid->PrintStats (stdout, "KQ-K");
305 delete pos;
306 delete resultGrid;
307 delete writer;
308 }
309
310 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
311 // krk
312 // Stores every KR-K result for White to move, 4 bits per result.
313 //
krk(FILE * fp)314 void krk (FILE * fp)
315 {
316 const uint bitsPerResult = 4;
317 MTBWriter * writer = new MTBWriter("KRK", bitsPerResult);
318 Position * pos = new Position();
319 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
320
321 squareT kingSquares[] = {
322 A1, B1, C1, D1, B2, C2, D2, C3, D3, D4,
323 NULL_SQUARE
324 };
325 for (colorT stm = WHITE; stm <= WHITE; stm++) {
326 squareT * bkSquares = kingSquares;
327 while (*bkSquares != NULL_SQUARE) {
328 resultGrid->Clear();
329 squareT bk = *bkSquares;
330 uint prevResult = 0;
331 for (squareT wk=A1; wk <= H8; wk++) {
332 for (squareT wr=A1; wr <= H8; wr++) {
333 uint result = prevResult; // Broken: repeat previous result
334 if (uniqueSquares (wk, bk, wr)) {
335 pos->Clear();
336 pos->AddPiece(WK, wk);
337 pos->AddPiece(BK, bk);
338 pos->AddPiece(WR, wr);
339 pos->SetToMove(stm);
340 if (pos->IsLegal()) {
341 int score = 0;
342 if (scid_TB_Probe (pos, &score) == OK) {
343 result = ((score < 0) ? -score : score-1);
344 prevResult = result;
345 } else {
346 tbFailure("KRK", pos);
347 }
348 }
349 }
350 // Add the result to the table:
351 resultGrid->SetResult (result, wk, wr);
352 prevResult = result;
353 }
354 }
355 writer->Add(resultGrid, bk, stm);
356 resultGrid->UpdateStats ();
357 bkSquares++;
358 }
359 }
360 writer->Write (fp);
361 resultGrid->PrintStats (stdout, "KR-K");
362 delete pos;
363 delete resultGrid;
364 delete writer;
365 }
366
367 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
368 // kpk
369 // Stores every KP-K result for White or Black to move, 1 bit per result.
370 //
kpk(FILE * fp)371 void kpk (FILE * fp)
372 {
373 const uint bitsPerResult = 1;
374 MTBWriter * writer = new MTBWriter ("KPK", bitsPerResult);
375 Position * pos = new Position();
376 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
377
378 squareT pawnSquares[] = {
379 A2, B2, C2, D2, A3, B3, C3, D3, A4, B4, C4, D4,
380 A5, B5, C5, D5, A6, B6, C6, D6, A7, B7, C7, D7,
381 NULL_SQUARE
382 };
383
384 for (colorT stm = WHITE; stm <= BLACK; stm++) {
385 squareT * wpSquares = pawnSquares;
386 while (*wpSquares != NULL_SQUARE) {
387 resultGrid->Clear();
388 squareT wp = *wpSquares;
389 for (squareT wk=A1; wk <= H8; wk++) {
390 for (squareT bk=A1; bk <= H8; bk++) {
391 uint result = 1; // Broken: use same value as win
392 if (uniqueSquares (wk, bk, wp)) {
393 pos->Clear();
394 pos->AddPiece(WK, wk);
395 pos->AddPiece(BK, bk);
396 pos->AddPiece(WP, wp);
397 pos->SetToMove(stm);
398 if (pos->IsLegal()) {
399 int score = 0;
400 if (scid_TB_Probe (pos, &score) == OK) {
401 result = ((score == 0) ? 0 : 1);
402 } else {
403 tbFailure("KPK", pos);
404 }
405 }
406 }
407 // Add the result to the table:
408 resultGrid->SetResult (result, bk, wk);
409 }
410 }
411 writer->Add (resultGrid, wp, stm);
412 resultGrid->UpdateStats ();
413 wpSquares++;
414 }
415 }
416 writer->Write (fp);
417 resultGrid->PrintStats (stdout, "KP-K");
418 delete resultGrid;
419 delete pos;
420 delete writer;
421 }
422
423 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
424 // kqkq
425 // Selected KQ-KQ results.
426 //
kqkq(FILE * fp)427 void kqkq (FILE * fp)
428 {
429 const uint bitsPerResult = 2;
430 MTBWriter * writer = new MTBWriter ("KQKQ", bitsPerResult);
431 Position * pos = new Position();
432 ResultGrid * resultGrid = new ResultGrid (bitsPerResult);
433
434 // Most KQ-KQ positions are draws or trivial wins that capture the
435 // opposing queen (directly or by a skewer), but there are some mate
436 // threat tactics which can take time to find. Since KQKQ often
437 // occurs in analysis of pawn endings, we use memory tablebases
438 // for selected king configurations where mate threats are possible.
439
440 // KING_SQUARES: array of PAIR(wkSquare,bkSquare) for WK and BK
441 uint KING_SQUARES[] = {
442 // Black king on a1
443 PAIR(C2,A1), PAIR(C3,A1),
444 // Black king on b1
445 PAIR(A3,B1), PAIR(B3,B1), PAIR(C3,B1), PAIR(D2,B1), PAIR(D3,B1),
446 // Black king on c1
447 PAIR(C3,C1), PAIR(D3,C1), PAIR(E2,C1),
448 // Black king on b2
449 PAIR(D2,B2), PAIR(D3,B2), PAIR(D4,B2),
450 // Black king on c2
451 PAIR(C4,C2), PAIR(D4,C2), PAIR(E2,C2), PAIR(E3,C2),
452 PAIR(NULL_SQUARE,NULL_SQUARE)
453 };
454
455 // We only need WTM for KQKQ because material is symmetrical.
456
457 uint * kingSquares = KING_SQUARES;
458 while (*kingSquares != PAIR(NULL_SQUARE,NULL_SQUARE)) {
459 resultGrid->Clear();
460 squareT wk = FIRST(*kingSquares);
461 squareT bk = SECOND(*kingSquares);
462 for (squareT wq = A1; wq <= H8; wq++) {
463 for (squareT bq = A1; bq <= H8; bq++) {
464 uint result = 1; // Broken: same value as White (STM) win
465 if (uniqueSquares (wk, bk, wq, bq)) {
466 pos->Clear();
467 pos->AddPiece(WK, wk);
468 pos->AddPiece(BK, bk);
469 pos->AddPiece(WQ, wq);
470 pos->AddPiece(BQ, bq);
471 pos->SetToMove(WHITE);
472 if (pos->IsLegal()) {
473 int score = 0;
474 if (scid_TB_Probe (pos, &score) == OK) {
475 if (score == 0) { result = 0; } // Draw
476 else if (score > 0) { result = 1; } // STM wins
477 else {result = 2; } // STM loses
478 } else {
479 tbFailure("KQKQ", pos);
480 }
481 }
482 }
483 // Add the result to the table:
484 resultGrid->SetResult (result, wq, bq);
485 }
486 }
487 writer->Add (resultGrid, wk, bk, WHITE);
488 resultGrid->UpdateStats ();
489 kingSquares++;
490 }
491 writer->Write (fp);
492 resultGrid->PrintStats (stdout, "KQ-KQ");
493 delete resultGrid;
494 delete pos;
495 }
496
497 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
498 // kqkp
499 // Selected KQ-KP results for White to move with the black pawn one
500 // square away from queening, one bit per result.
501 // Note that there are a few rare KQ-KP WTM positions where Black wins;
502 // these are checked in the recognizer code.
503 //
kqkp(FILE * fp)504 void kqkp (FILE * fp)
505 {
506 const uint bitsPerResult = 1;
507 MTBWriter * writer = new MTBWriter ("KQKP", bitsPerResult);
508 Position * pos = new Position();
509 ResultGrid * resultGrid = new ResultGrid (bitsPerResult);
510
511 // BLACK_SQUARES: array of PAIR(pawnSquare,kingSquare) for black pieces
512 uint BLACK_SQUARES[] = {
513 PAIR(A2,A1), PAIR(A2,B1), PAIR(A2,C1),
514 PAIR(A2,B2), PAIR(A2,C2),
515
516 PAIR(C2,A1), PAIR(C2,B1), PAIR(C2,C1), PAIR(C2,D1), PAIR(C2,E1),
517 PAIR(C2,A2), PAIR(C2,B2), PAIR(C2,D2), PAIR(C2,E2),
518 PAIR(C2,A3), PAIR(C2,B3), PAIR(C2,C3), PAIR(C2,D3), PAIR(C2,E3),
519
520 PAIR(D2,C1), PAIR(D2,E1), PAIR(D2,C2), PAIR(D2,E2),
521
522 // TODO: BP on c3 as well? it has some draws...
523
524 PAIR(NULL_SQUARE,NULL_SQUARE)
525 };
526
527 for (colorT stm = WHITE; stm <= WHITE; stm++) {
528 uint * blackSquares = BLACK_SQUARES;
529 while (*blackSquares != PAIR(NULL_SQUARE,NULL_SQUARE)) {
530 resultGrid->Clear();
531 uint prevResult = 1; // Default value for initial broken result
532 squareT bp = FIRST(*blackSquares);
533 squareT bk = SECOND(*blackSquares);
534 for (squareT wk = A1; wk <= H8; wk++) {
535 for (squareT wq = A1; wq <= H8; wq++) {
536 uint result = prevResult; // Broken: use previous result
537 if (uniqueSquares (wk, bk, wq, bp)) {
538 pos->Clear();
539 pos->AddPiece(WK, wk);
540 pos->AddPiece(BK, bk);
541 pos->AddPiece(WQ, wq);
542 pos->AddPiece(BP, bp);
543 pos->SetToMove(stm);
544 if (pos->IsLegal()) {
545 int score = 0;
546 if (scid_TB_Probe (pos, &score) == OK) {
547 if (stm == BLACK) { score = -score; }
548 if (score < 0) {
549 printf ("Warning: WTM loss found for KQKP\n");
550 pos->DumpBoard(stdout);
551 }
552 result = (score == 0 ? 0 : 1);
553 prevResult = result;
554 } else {
555 tbFailure("KQKP", pos);
556 }
557 }
558 }
559 // Add the result to the table:
560 resultGrid->SetResult (result, wk, wq);
561 }
562 }
563 writer->Add (resultGrid, bp, bk, stm);
564 resultGrid->UpdateStats ();
565 blackSquares++;
566 }
567 }
568 writer->Write (fp);
569 resultGrid->PrintStats (stdout, "KQ-KP");
570 delete resultGrid;
571 delete pos;
572 }
573
574 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
575 // krkp
576 // Selected KR-KP results, White to move.
577 //
krkp(FILE * fp)578 void krkp (FILE * fp)
579 {
580 const uint bitsPerResult = 2;
581 MTBWriter * writer = new MTBWriter ("KRKP", bitsPerResult);
582 Position * pos = new Position();
583 ResultGrid * resultGrid = new ResultGrid (bitsPerResult);
584
585 // BLACK_SQUARES: array of PAIR(pawnSquare,kingSquare) for black pieces
586 uint BLACK_SQUARES[] = {
587 PAIR(A2,A1), PAIR(A2,B1), PAIR(A2,C1),
588 PAIR(A2,B2), PAIR(A2,C2),
589 PAIR(A2,A3), PAIR(A2,B3), PAIR(A2,C3),
590
591 PAIR(B2,A1), PAIR(B2,B1), PAIR(B2,C1), PAIR(B2,D1),
592 PAIR(B2,A2), PAIR(B2,C2), PAIR(B2,D2),
593 PAIR(B2,A3), PAIR(B2,B3), PAIR(B2,C3), PAIR(B2,D3),
594
595 PAIR(C2,A1), PAIR(C2,B1), PAIR(C2,C1), PAIR(C2,D1), PAIR(C2,E1),
596 PAIR(C2,A2), PAIR(C2,B2), PAIR(C2,D2), PAIR(C2,E2),
597 PAIR(C2,A3), PAIR(C2,B3), PAIR(C2,C3), PAIR(C2,D3), PAIR(C2,E3),
598
599 PAIR(D2,B1), PAIR(D2,C1), PAIR(D2,D1), PAIR(D2,E1), PAIR(D2,F1),
600 PAIR(D2,B2), PAIR(D2,C2), PAIR(D2,E2), PAIR(D2,F2),
601 PAIR(D2,B3), PAIR(D2,C3), PAIR(D2,D3), PAIR(D2,E3), PAIR(D2,F3),
602
603 PAIR(A3,A2), PAIR(A3,B2), PAIR(A3,B3), PAIR(A3,A4), PAIR(A3,B4),
604
605 PAIR(B3,A2), PAIR(B3,B2), PAIR(B3,C2), PAIR(B3,A3), PAIR(B3,C3),
606 PAIR(B3,A4), PAIR(B3,B4), PAIR(B3,C4),
607
608 PAIR(C3,B2), PAIR(C3,C2), PAIR(C3,D2), PAIR(C3,B3), PAIR(C3,D3),
609 PAIR(C3,B4), PAIR(C3,C4), PAIR(C3,D4),
610
611 PAIR(D3,C2), PAIR(D3,D2), PAIR(D3,E2), PAIR(D3,C3), PAIR(D3,E3),
612 PAIR(D3,C4), PAIR(D3,D4), PAIR(D3,E4),
613
614 PAIR(A4,A3), PAIR(A4,B3), PAIR(A4,B4), PAIR(A4,A5), PAIR(A4,B5),
615
616 PAIR(B4,A3), PAIR(B4,B3), PAIR(B4,C3), PAIR(B4,A4), PAIR(B4,C4),
617 PAIR(B4,A5), PAIR(B4,B5), PAIR(B4,C5),
618
619 PAIR(C4,B3), PAIR(C4,C3), PAIR(C4,D3), PAIR(C4,B4), PAIR(C4,D4),
620 PAIR(C4,B5), PAIR(C4,C5), PAIR(C4,D5),
621
622 PAIR(D4,C3), PAIR(D4,D3), PAIR(D4,E3), PAIR(D4,C4), PAIR(D4,E4),
623 PAIR(D4,C5), PAIR(D4,D5), PAIR(D4,E5),
624
625 PAIR(A5,A4), PAIR(A5,B4), PAIR(A5,B5), PAIR(A5,A6), PAIR(A5,B6),
626
627 PAIR(B5,A4), PAIR(B5,B4), PAIR(B5,C4), PAIR(B5,A5), PAIR(B5,C5),
628 PAIR(B5,A6), PAIR(B5,B6), PAIR(B5,C6),
629
630 PAIR(C5,B4), PAIR(C5,C4), PAIR(C5,D4), PAIR(C5,B5), PAIR(C5,D5),
631 PAIR(C5,B6), PAIR(C5,C6), PAIR(C5,D6),
632
633 PAIR(D5,C4), PAIR(D5,D4), PAIR(D5,E4), PAIR(D5,C5), PAIR(D5,E5),
634 PAIR(D5,C6), PAIR(D5,D6), PAIR(D5,E6),
635
636 PAIR(NULL_SQUARE,NULL_SQUARE)
637 };
638
639 for (colorT stm = WHITE; stm <= WHITE; stm++) {
640 uint * blackSquares = BLACK_SQUARES;
641 while (*blackSquares != PAIR(NULL_SQUARE,NULL_SQUARE)) {
642 resultGrid->Clear();
643 uint prevResult = 0; // Default value for previous result
644 squareT bp = FIRST(*blackSquares);
645 squareT bk = SECOND(*blackSquares);
646 for (squareT wk = A1; wk <= H8; wk++) {
647 for (squareT wr = A1; wr <= H8; wr++) {
648 uint result = prevResult; // Broken: use previous result
649 if (uniqueSquares (wk, bk, wr, bp)) {
650 pos->Clear();
651 pos->AddPiece(WK, wk);
652 pos->AddPiece(BK, bk);
653 pos->AddPiece(WR, wr);
654 pos->AddPiece(BP, bp);
655 pos->SetToMove(stm);
656 if (pos->IsLegal()) {
657 int score = 0;
658 if (scid_TB_Probe (pos, &score) == OK) {
659 if (stm == BLACK) { score = -score; }
660 if (score == 0) { result = 0; }
661 else if (score > 0) { result = 1; }
662 else {result = 2; }
663 } else {
664 tbFailure("KRKP", pos);
665 }
666 }
667 }
668 // Add the result to the table:
669 resultGrid->SetResult (result, wk, wr);
670 prevResult = result;
671 }
672 }
673 writer->Add (resultGrid, bp, bk, stm);
674 resultGrid->UpdateStats ();
675 blackSquares++;
676 }
677 }
678 writer->Write (fp);
679 resultGrid->PrintStats (stdout, "KR-KP");
680 delete resultGrid;
681 delete pos;
682 delete writer;
683 }
684
685
686 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
687 // kpkp
688 // Selected KP-KP results.
689 //
kpkp(FILE * fp)690 void kpkp (FILE * fp)
691 {
692 const uint bitsPerResult = 2;
693 MTBWriter * writer = new MTBWriter ("KPKP", bitsPerResult);
694 Position * pos = new Position();
695 ResultGrid * resultGrid = new ResultGrid (bitsPerResult);
696
697 // Database searches indicated that position with pawns on the same file
698 // occur often, and rammed pawns (where neither pawn can move) are
699 // especially common. There are 20 rammed pawn formations (a2a3 ... d6d7).
700
701 // PAWN_SQUARES: array of PAIR(wpSquare,bpSquare) for WP and BP
702 uint PAWN_SQUARES[] = {
703 PAIR(A2,A3), PAIR(B2,B3), PAIR(C2,C3), PAIR(D2,D3),
704 PAIR(A3,A4), PAIR(B3,B4), PAIR(C3,C4), PAIR(D3,D4),
705 PAIR(A4,A5), PAIR(B4,B5), PAIR(C4,C5), PAIR(D4,D5),
706 PAIR(A5,A6), PAIR(B5,B6), PAIR(C5,C6), PAIR(D5,D6),
707 PAIR(A6,A7), PAIR(B6,B7), PAIR(C6,C7), PAIR(D6,D7),
708
709 // TODO: Add more (WP,BP) pairs, but avoid ({x}5,{x+1}5) and
710 // ({x}5,{x-1}5), for example (A5,B5) to avoid all possible
711 // en passant positions.
712
713 // Pawns on adjacent files, neither passed:
714 PAIR(A5,B7), PAIR(A4,B6), PAIR(A3,B5), PAIR(A2,B4),
715 PAIR(B5,A7), PAIR(B4,A6), PAIR(B3,A5), PAIR(B2,A4),
716 PAIR(B5,C7), PAIR(B4,C6), PAIR(B3,C5), PAIR(B2,C4),
717
718 // Pawns on non-adjacent files, or adjacent but passed:
719 PAIR(A5,B4), PAIR(A6,B3), PAIR(A7,B2),
720 PAIR(B5,C4), PAIR(B6,C3), PAIR(B7,C2),
721
722 PAIR(NULL_SQUARE,NULL_SQUARE)
723 };
724
725 // We only need WTM for KPKP because material is symmetrical.
726
727 uint * pawnSquares = PAWN_SQUARES;
728 while (*pawnSquares != PAIR(NULL_SQUARE,NULL_SQUARE)) {
729 resultGrid->Clear();
730 squareT wp = FIRST(*pawnSquares);
731 squareT bp = SECOND(*pawnSquares);
732 uint prevResult = 0; // Default value for a broken result
733 for (squareT wk = A1; wk <= H8; wk++) {
734 for (squareT bk = A1; bk <= H8; bk++) {
735 uint result = prevResult; // Broken: use previous result
736 if (uniqueSquares (wk, bk, wp, bp)) {
737 pos->Clear();
738 pos->AddPiece(WK, wk);
739 pos->AddPiece(BK, bk);
740 pos->AddPiece(WP, wp);
741 pos->AddPiece(BP, bp);
742 pos->SetToMove(WHITE);
743 if (pos->IsLegal()) {
744 int score = 0;
745 if (scid_TB_Probe (pos, &score) == OK) {
746 if (score == 0) { result = 0; } // Draw
747 else if (score > 0) { result = 1; } // STM wins
748 else {result = 2; } // STM loses
749 } else {
750 tbFailure("KPKP", pos);
751 }
752 }
753 }
754 // Add the result to the table:
755 resultGrid->SetResult (result, wk, bk);
756 prevResult = result;
757 }
758 }
759 writer->Add (resultGrid, wp, bp, WHITE);
760 resultGrid->UpdateStats ();
761 pawnSquares++;
762 }
763 writer->Write (fp);
764 resultGrid->PrintStats (stdout, "KP-KP");
765 delete resultGrid;
766 delete pos;
767 delete writer;
768 }
769
770 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
771 // krpkr
772 // Selected KRP-KR results, pawn on 6th/7th rank.
773 //
krpkr(FILE * fp)774 void krpkr (FILE * fp)
775 {
776 const uint bitsPerResult = 2;
777 MTBWriter * writer = new MTBWriter ("KRPKR", bitsPerResult);
778 Position * pos = new Position();
779 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
780
781 // PKK_SQUARES: array of TRIPLET(wpSquare,wkSquare,bkSquare)
782 uint PKK_SQUARES[] = {
783 // White pawn on a7
784 TRIPLET(A7,A8,C8), TRIPLET(A7,A8,C7), TRIPLET(A7,A8,D7),
785 TRIPLET(A7,A6,A8), TRIPLET(A7,B6,A8),
786
787 // White pawn on b7
788 TRIPLET(B7,B8,D7), TRIPLET(B7,B8,D8), TRIPLET(B7,B8,E7),
789 TRIPLET(B7,A6,B8), TRIPLET(B7,A6,C7), TRIPLET(B7,B6,B8),
790 TRIPLET(B7,C6,B8), TRIPLET(B7,C6,A7), TRIPLET(B7,C6,E7),
791
792 // White pawn on c7
793 TRIPLET(C7,C8,A7), TRIPLET(C7,C8,A6), TRIPLET(C7,C8,E7),
794 TRIPLET(C7,C8,E6), TRIPLET(C7,C8,F7),
795
796 // White pawn on d7
797 TRIPLET(D7,D8,B7), TRIPLET(D7,D8,C6), TRIPLET(D7,D8,E6),
798 TRIPLET(D7,D8,F7), TRIPLET(D7,C6,D8),
799
800 // White pawn on a6
801 TRIPLET(A6,A7,C6), TRIPLET(A6,A7,C7), TRIPLET(A6,A7,C8),
802 TRIPLET(A6,A7,D7), TRIPLET(A6,B6,A8), TRIPLET(A6,B5,A7),
803
804 // White pawn on b6
805 TRIPLET(B6,B7,D6), TRIPLET(B6,B7,D7), TRIPLET(B6,B7,D8),
806 TRIPLET(B6,B8,A6), TRIPLET(B6,B8,C6),
807 TRIPLET(B6,A6,B8), TRIPLET(B6,A6,C8), TRIPLET(B6,C6,B8),
808
809 // White pawn on c6
810 TRIPLET(C6,C7,A6), TRIPLET(C6,C7,A7), TRIPLET(C6,C7,E7),
811 TRIPLET(C6,B6,C8), TRIPLET(C6,D6,C8),
812
813 // TODO: White pawn on d6
814
815 TRIPLET(NS,NS,NS)
816 };
817
818 // KRP-KR is an important practical tablebase, so we store results
819 // for both White and Black to move.
820
821 for (colorT stm = WHITE; stm <= BLACK; stm++) {
822 uint * pkkSquares = PKK_SQUARES;
823 while (*pkkSquares != TRIPLET(NS,NS,NS)) {
824 resultGrid->Clear();
825 squareT wp = FIRST(*pkkSquares);
826 squareT wk = SECOND(*pkkSquares);
827 squareT bk = THIRD(*pkkSquares);
828 uint prevResult = 0; // Default value for a broken result
829
830 for (squareT wr = A1; wr <= H8; wr++) {
831 for (squareT br = A1; br <= H8; br++) {
832 uint result = prevResult; // Broken: use previous result
833 if (uniqueSquares (wk, bk, wr, br, wp)) {
834 pos->Clear();
835 pos->AddPiece(WK, wk);
836 pos->AddPiece(BK, bk);
837 pos->AddPiece(WR, wr);
838 pos->AddPiece(BR, br);
839 pos->AddPiece(WP, wp);
840 pos->SetToMove(stm);
841 if (pos->IsLegal()) {
842 int score = 0;
843 if (scid_TB_Probe (pos, &score) == OK) {
844 if (score == 0) { result = 0; }
845 else if (score > 0) { result = 1; }
846 else {result = 2; }
847 } else {
848 tbFailure("KRPKR", pos);
849 }
850 }
851 }
852 // Add the result to the table:
853 resultGrid->SetResult (result, wr, br);
854 prevResult = result;
855 }
856 }
857 writer->Add (resultGrid, wp, wk, bk, stm);
858 resultGrid->UpdateStats ();
859 pkkSquares++;
860 }
861 }
862 writer->Write (fp);
863 resultGrid->PrintStats (stdout, "KRP-KR");
864 delete resultGrid;
865 delete pos;
866 delete writer;
867 }
868
869 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
870 // kppkr
871 // Selected KPP-KR results. We store selected tablebases for White (with
872 // the rook) to move against advanced black pawns with their King nearby.
873 //
kppkr(FILE * fp)874 void kppkr (FILE * fp)
875 {
876 const uint bitsPerResult = 2;
877 MTBWriter * writer = new MTBWriter ("KPPKR", bitsPerResult);
878 Position * pos = new Position();
879 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
880
881 // The most common normalized pawn configurations are: a+b pawns,
882 // then b+c pawns, then a+c pawns.
883
884 // BLACK_SQUARES: array of TRIPLET(bpSquare,bpSquare,bkSquare)
885 uint BLACK_SQUARES[] = {
886 // a+b pawns
887 TRIPLET(A2,B2,C2),
888 TRIPLET(A2,B3,C2), TRIPLET(A2,B3,C3),
889 TRIPLET(A3,B2,B3), TRIPLET(A3,B2,C2), TRIPLET(A3,B2,C3),
890 // TODO: more a+b pawns
891
892 // TODO: b+c pawns
893 // TODO: a+c pawns
894
895 TRIPLET(NS,NS,NS)
896 };
897
898 for (colorT stm = WHITE; stm <= WHITE; stm++) {
899 uint * blackSquares = BLACK_SQUARES;
900 while (*blackSquares != TRIPLET(NS,NS,NS)) {
901 resultGrid->Clear();
902 squareT bp1 = FIRST(*blackSquares);
903 squareT bp2 = SECOND(*blackSquares);
904 squareT bk = THIRD(*blackSquares);
905 uint prevResult = 0; // Default value for a broken result
906
907 for (squareT wk = A1; wk <= H8; wk++) {
908 for (squareT wr = A1; wr <= H8; wr++) {
909 uint result = prevResult; // Broken: use previous result
910 if (uniqueSquares (wk, bk, wr, bp1, bp2)) {
911 pos->Clear();
912 pos->AddPiece(WK, wk);
913 pos->AddPiece(BK, bk);
914 pos->AddPiece(WR, wr);
915 pos->AddPiece(BP, bp1);
916 pos->AddPiece(BP, bp2);
917 pos->SetToMove(stm);
918 if (pos->IsLegal()) {
919 int score = 0;
920 if (scid_TB_Probe (pos, &score) == OK) {
921 if (score == 0) { result = 0; }
922 else if (score > 0) { result = 1; } // STM wins
923 else {result = 2; } // STM loses
924 } else {
925 tbFailure("KPPKR", pos);
926 }
927 }
928 }
929 // Add the result to the table:
930 resultGrid->SetResult (result, wk, wr);
931 prevResult = result;
932 }
933 }
934 writer->Add (resultGrid, bp1, bp2, bk, stm);
935 resultGrid->UpdateStats ();
936 blackSquares++;
937 }
938 }
939 writer->Write (fp);
940 resultGrid->PrintStats (stdout, "KPP-KR");
941 delete resultGrid;
942 delete pos;
943 delete writer;
944 }
945
946 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
947 // kppkp
948 // Selected KPP-KP results.
949 //
kppkp(FILE * fp)950 void kppkp (FILE * fp)
951 {
952 const uint bitsPerResult = 2;
953 MTBWriter * writer = new MTBWriter ("KPPKP", bitsPerResult);
954 Position * pos = new Position();
955 ResultGrid * resultGrid = new ResultGrid(bitsPerResult);
956
957 // The most common pawn file configuration (normalised so the black
958 // pawn is on the queenside) are ab-a, ac-a, and ab-b.
959
960 // PAWN_SQUARES: array of TRIPLET(wpSquare,wpSquare,bpSquare)
961 uint PAWN_SQUARES[] = {
962 // a+b pawns vs a-pawn
963 TRIPLET(A6,B5,A7), TRIPLET(A5,B6,A7), TRIPLET(A5,B5,A7),
964 TRIPLET(A4,B5,A7),
965 TRIPLET(A5,B4,A6), TRIPLET(A4,B4,A6),
966
967 // a+c pawns vs a-pawn
968
969 // a+b pawns vs b-pawn
970
971 TRIPLET(NS,NS,NS)
972 };
973
974 for (colorT stm = WHITE; stm <= BLACK; stm++) {
975 uint * pawnSquares = PAWN_SQUARES;
976 while (*pawnSquares != TRIPLET(NS,NS,NS)) {
977 resultGrid->Clear();
978 squareT wp1 = FIRST(*pawnSquares);
979 squareT wp2 = SECOND(*pawnSquares);
980 squareT bp = THIRD(*pawnSquares);
981 uint prevResult = 0; // Default value for a broken result
982
983 for (squareT wk = A1; wk <= H8; wk++) {
984 for (squareT bk = A1; bk <= H8; bk++) {
985 uint result = prevResult; // Broken: use previous result
986 if (uniqueSquares (wk, bk, wp1, wp2, bp)) {
987 pos->Clear();
988 pos->AddPiece(WK, wk);
989 pos->AddPiece(BK, bk);
990 pos->AddPiece(WP, wp1);
991 pos->AddPiece(WP, wp2);
992 pos->AddPiece(BP, bp);
993 pos->SetToMove(stm);
994 if (pos->IsLegal()) {
995 int score = 0;
996 if (scid_TB_Probe (pos, &score) == OK) {
997 if (score == 0) { result = 0; }
998 else if (score > 0) { result = 1; }
999 else {result = 2; }
1000 } else {
1001 tbFailure("KPPKP", pos);
1002 }
1003 }
1004 }
1005 // Add the result to the table:
1006 resultGrid->SetResult (result, wk, bk);
1007 prevResult = result;
1008 }
1009 }
1010 writer->Add (resultGrid, wp1, wp2, bp, stm);
1011 resultGrid->UpdateStats ();
1012 pawnSquares++;
1013 }
1014 }
1015 writer->Write (fp);
1016 resultGrid->PrintStats (stdout, "KPP-KP");
1017 delete resultGrid;
1018 delete pos;
1019 delete writer;
1020 }
1021
1022 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1023 // main
main(int argc,char ** argv)1024 int main (int argc, char ** argv)
1025 {
1026 if (argc != 2) {
1027 fprintf (stderr, "Usage: mtbgen <TB-paths>\n");
1028 exit(1);
1029 }
1030
1031 // Set a large tablebase cache size and initialize tablebases
1032 scid_TB_SetCacheSize (64 * 1024 * 1024); // 64 MB cache
1033 uint npieces = scid_TB_Init (argv[1]);
1034 printf ("Tablebases with up to %u pieces were found\n", npieces);
1035
1036 FILE * fp = fopen ("mtbdata.h", "wb");
1037 if (fp == NULL) {
1038 fprintf (stderr, "Error opening file\n");
1039 exit(1);
1040 }
1041
1042 fprintf (fp, "%s\n", SLASHES);
1043 fprintf (fp, "//\n");
1044 fprintf (fp, "// FILE: mtbdata.h\n");
1045 fprintf (fp, "// Memory tablebases\n");
1046 fprintf (fp, "//\n");
1047 fprintf (fp, "// Part of: Scid (Shane's Chess Information Database)\n");
1048 fprintf (fp, "// Version: 3.5\n");
1049 fprintf (fp, "//\n");
1050 fprintf (fp, "// Notice: Copyright (c) 2003 Shane Hudson. All rights reserved.\n");
1051 fprintf (fp, "//\n");
1052 fprintf (fp, "// Author: Shane Hudson (sgh@users.sourceforge.net)\n");
1053 fprintf (fp, "//\n");
1054 fprintf (fp, "%s\n", SLASHES);
1055
1056 fprintf (fp, "\n\n");
1057 fprintf (fp, "// This file was automatically generated by the program mtbgen.cpp.\n");
1058 fprintf (fp, "// It contains selected compressed tablebase data used by the endgame\n");
1059 fprintf (fp, "// recognition code in the Scidlet chess engine.\n");
1060 fprintf (fp, "\n");
1061 fprintf (fp, "#ifndef SCID_MTBDATA_H\n");
1062 fprintf (fp, "#define SCID_MTBDATA_H\n");
1063 fprintf (fp, "\n\n");
1064
1065 kqk (fp);
1066 krk (fp);
1067 kpk (fp);
1068
1069 kqkq (fp);
1070 kqkp (fp);
1071 krkp (fp);
1072 kpkp (fp);
1073
1074 // TODO: kqpkq (fp);
1075 krpkr (fp);
1076 // TODO: kppkr (fp);
1077 kppkp (fp);
1078
1079 fprintf (fp, "\n");
1080 fprintf (fp, "%s\n", SLASHES);
1081 fprintf (fp, "\n\n");
1082
1083 // Write the MTB initialization function:
1084 fprintf (fp, "static void initMTBs (void)\n{\n");
1085 fprintf (fp, " initMTB_KQK();\n");
1086 fprintf (fp, " initMTB_KRK();\n");
1087 fprintf (fp, " initMTB_KPK();\n");
1088 fprintf (fp, " initMTB_KQKQ();\n");
1089 fprintf (fp, " initMTB_KQKP();\n");
1090 fprintf (fp, " initMTB_KRKP();\n");
1091 fprintf (fp, " initMTB_KPKP();\n");
1092 fprintf (fp, " initMTB_KRPKR();\n");
1093 // TODO: fprintf (fp, " initMTB_KPPKR();\n");
1094 fprintf (fp, " initMTB_KPPKP();\n");
1095 fprintf (fp, "}\n\n\n");
1096 fprintf (fp, "#endif // SCID_MTBDATA_H\n");
1097 fprintf (fp, "\n");
1098 fprintf (fp, "%s\n", SLASHES);
1099 fprintf (fp, "// EOF: mtbdata.h\n");
1100 fprintf (fp, "%s\n", SLASHES);
1101
1102 fclose (fp);
1103 return 0;
1104 }
1105
1106 //////////////////////////////////////////////////////////////////////
1107 // EOF: mtbgen.cpp
1108 //////////////////////////////////////////////////////////////////////
1109