src/probe.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     probe.c
   8
   9 Abstract:
  10
  11     Routines for probing endgame tablebases; much of this code is
  12     "borrowed" from crafty.
  13
  14 Author:
  15
  16     Scott Gasch ([email protected]) 02 Jul 2004
  17
  18 Revision History:
  19
  20     $Id: probe.c 355 2008-07-01 15:46:43Z scott $
  21
  22 **/
  23
  24 #include "chess.h"
  25
  26 #define XX (127)                              // sq not on the board
  27 #define C_PIECES (3)                          // max num pieces of one color
  28
  29 ULONG g_uEgtbLock = 0;
  30
  31 //
  32 // define INDEX type
  33 //
  34 #define T_INDEX64                             // use 64 bit indexes
  35 #if defined (T_INDEX64) && defined (_MSC_VER)
  36 typedef unsigned __int64 INDEX;
  37 #elif defined (T_INDEX64)
  38 typedef unsigned long long INDEX;
  39 #else
  40 typedef unsigned long INDEX;
  41 #endif
  42
  43 //
  44 // define square type and tb type
  45 //
  46 typedef unsigned int squaret;
  47 typedef signed char tb_t;
  48
  49 //
  50 // define color
  51 //
  52 typedef int color;
  53 #define x_colorWhite    0
  54 #define x_colorBlack    1
  55 #define x_colorNeutral  2
  56 #define COLOR_DECLARED
  57
  58 //
  59 // define pieces
  60 //
  61 typedef int piece;
  62 #define x_pieceNone    0
  63 #define x_piecePawn    1
  64 #define x_pieceKnight  2
  65 #define x_pieceBishop  3
  66 #define x_pieceRook    4
  67 #define x_pieceQueen   5
  68 #define x_pieceKing    6
  69 #define PIECES_DECLARED
  70
  71 //
  72 // scores returned from egtb.cpp
  73 //
  74 #define pageL       65536
  75 #define tbbe_ssL    ((pageL-4)/2)
  76 #define bev_broken  (tbbe_ssL+1)        /* illegal or busted */
  77 #define bev_mi1     tbbe_ssL    /* mate in 1 move */
  78 #define bev_mimin   1   /* mate in max moves */
  79 #define bev_draw    0   /* draw */
  80 #define bev_limax   (-1)        /* mated in max moves */
  81 #define bev_li0     (-tbbe_ssL) /* mated in 0 moves */
  82
  83 //
  84 // define PfnCalcIndex
  85 //
  86 typedef INDEX(TB_FASTCALL * PfnCalcIndex)(squaret *,
  87                                           squaret *,
  88                                           squaret,
  89                                           int fInverse);
  90
  91 //
  92 // prototypes for functions in egtb.cpp
  93 //
  94 extern int IDescFindFromCounters(int *);
  95 extern int FRegisteredFun(int, color);
  96 extern PfnCalcIndex PfnIndCalcFun(int, color);
  97 extern int TB_FASTCALL L_TbtProbeTable(int, color, INDEX);
  98 #define PfnIndCalc PfnIndCalcFun
  99 #define FRegistered FRegisteredFun
 100 extern int IInitializeTb(char *);
 101 extern int FTbSetCacheSize(void *buffer, unsigned long size);
 102 extern int TB_CRC_CHECK;
 103
 104 //
 105 // Globals
 106 //
 107 static int EGTBMenCount = 0;
 108 void *egtb_cache = NULL;
 109 #define EGTB_CACHE_SIZE (8*1024*1024)
 110
 111
 112 void
 113 InitializeEGTB(void)
 114 /**
 115
 116 Routine description:
 117
 118     [Re]Initialize the Nalimov EGTB system.  Called during system
 119     startup and when the user uses "set" to change the EGTB path.
 120
 121 Parameters:
 122
 123     void (uses g_OPtionz.szEGTBPath)
 124
 125 Return value:
 126
 127     void
 128
 129 **/
 130 {
 131     CHAR *szPath = g_Options.szEGTBPath;
 132
 133     if ((szPath != NULL) && strlen(szPath) > 0) {
 134         // TB_CRC_CHECK = 1;
 135         EGTBMenCount = IInitializeTb(szPath);
 136         if (0 != EGTBMenCount)
 137         {
 138             Trace("Found %d-men endgame tablebases.\n\n", EGTBMenCount);
 139             if (NULL != egtb_cache)
 140             {
 141                 SystemFreeMemory(egtb_cache);
 142                 egtb_cache = NULL;
 143             }
 144             egtb_cache = SystemAllocateMemory(EGTB_CACHE_SIZE);
 145             if (NULL != egtb_cache)
 146             {
 147                 FTbSetCacheSize(egtb_cache, EGTB_CACHE_SIZE);
 148             }
 149         }
 150     }
 151 }
 152
 153 void
 154 CleanupEGTB(void)
 155 /**
 156
 157 Routine description:
 158
 159     Cleanup the Nalimov EGTB system.
 160
 161 Parameters:
 162
 163     void
 164
 165 Return value:
 166
 167     void
 168
 169 **/
 170 {
 171     if (NULL != egtb_cache)
 172     {
 173         SystemFreeMemory(egtb_cache);
 174         egtb_cache = NULL;
 175     }
 176 }
 177
 178
 179 FLAG
 180 ProbeEGTB(SEARCHER_THREAD_CONTEXT *ctx,
 181           SCORE *piScore)
 182 /**
 183
 184 Routine description:
 185
 186     Search for a board position in the EGTB files on disk.
 187
 188 Parameters:
 189
 190     SEARCHER_THREAD_CONTEXT *ctx,
 191     SCORE *piScore
 192
 193 Return value:
 194
 195     FLAG
 196
 197 **/
 198 {
 199     POSITION *pos = &(ctx->sPosition);
 200     int pcCount[10];
 201     int wSquares[C_PIECES*5+1], bSquares[C_PIECES*5+1];
 202     int iTB;
 203     ULONG uColor;
 204     int invert;
 205     int *wp, *bp;
 206     int ep;
 207     INDEX index;
 208     int value;
 209     FLAG fResult;
 210     ULONG x;
 211     int y;
 212     COOR c;
 213     PIECE p;
 214     PfnCalcIndex fp;
 215
 216     //
 217     // EGTB initialized?
 218     //
 219     ULONG wcount = (pos->uNonPawnCount[WHITE][0] +
 220                     pos->uPawnCount[WHITE]);
 221     ULONG bcount = (pos->uNonPawnCount[BLACK][0] +
 222                     pos->uPawnCount[BLACK]);
 223     if ((wcount + bcount > (ULONG)EGTBMenCount) ||
 224         (wcount > 3) ||
 225         (bcount > 3))
 226     {
 227         return(FALSE);
 228     }
 229     INC(ctx->sCounters.egtb.uProbes);
 230     memset(pcCount, 0, sizeof(pcCount));
 231
 232     for (x = 0;
 233          x < pos->uPawnCount[WHITE];
 234          x++)
 235     {
 236         c = pos->cPawns[WHITE][x];
 237         ASSERT (IS_ON_BOARD(c));
 238         ASSERT(pos->rgSquare[c].pPiece && IS_PAWN(pos->rgSquare[c].pPiece));
 239
 240         c = TO64(c);
 241         ASSERT((c >= 0) && (c <= 64));
 242
 243         y = pcCount[0];
 244         ASSERT(y >= 0);
 245         ASSERT(y < (C_PIECES * 5 + 1));
 246         wSquares[y] = c;
 247         pcCount[0]++;
 248     }
 249
 250     for (x = 1;
 251          x < pos->uNonPawnCount[WHITE][0];
 252          x++)
 253     {
 254         c = pos->cNonPawns[WHITE][x];
 255         ASSERT (IS_ON_BOARD(c));
 256
 257         p = pos->rgSquare[c].pPiece;
 258         ASSERT(p && !IS_PAWN(p) && !IS_KING(p));
 259
 260         //
 261         // convert:               into:
 262         // XXX_PAWN               0
 263         // XXX_KNIGHT             1
 264         // XXX_BISHOP             2
 265         // XXX_ROOK               3
 266         // XXX_QUEEN              4
 267         //
 268         p = ((p >> 1) & 0x7) - 1;
 269         ASSERT(p > 0);
 270         ASSERT(p < 5);
 271
 272         c = TO64(c);
 273         ASSERT((c >= 0) && (c <= 64));
 274
 275         y = p * C_PIECES + pcCount[p];
 276         ASSERT(y >= 0);
 277         ASSERT(y < (C_PIECES * 5 + 1));
 278         wSquares[y] = c;
 279         pcCount[p]++;
 280     }
 281
 282     for (x = 0;
 283          x < pos->uPawnCount[BLACK];
 284          x++)
 285     {
 286         c = pos->cPawns[BLACK][x];
 287         ASSERT(IS_ON_BOARD(c));
 288         ASSERT(pos->rgSquare[c].pPiece && IS_PAWN(pos->rgSquare[c].pPiece));
 289
 290         c = TO64(c);
 291         ASSERT(c >= 0);
 292         ASSERT(c <= 64);
 293
 294         y = pcCount[5];
 295         ASSERT(y >= 0);
 296         ASSERT(y < (C_PIECES * 5 + 1));
 297         bSquares[y] = c;
 298         pcCount[5]++;
 299     }
 300
 301     for (x = 1;
 302          x < pos->uNonPawnCount[BLACK][0];
 303          x++)
 304     {
 305         c = pos->cNonPawns[BLACK][x];
 306         ASSERT(IS_ON_BOARD(c));
 307
 308         p = pos->rgSquare[c].pPiece;
 309         ASSERT(p && !IS_PAWN(p) && !IS_KING(p));
 310
 311         //
 312         // convert:               into:
 313         // XXX_PAWN               0
 314         // XXX_KNIGHT             1
 315         // XXX_BISHOP             2
 316         // XXX_ROOK               3
 317         // XXX_QUEEN              4
 318         //
 319         p = ((p >> 1) & 0x7) - 1;
 320         ASSERT(p > 0);
 321         ASSERT(p < 5);
 322
 323         c = TO64(c);
 324         ASSERT(c >= 0);
 325         ASSERT(c <= 64);
 326
 327         y = p * C_PIECES + pcCount[5 + p];
 328         ASSERT(y >= 0);
 329         ASSERT(y < (C_PIECES * 5 + 1));
 330         bSquares[y] = c;
 331         pcCount[5 + p]++;
 332     }
 333
 334     AcquireSpinLock(&g_uEgtbLock);
 335     iTB = IDescFindFromCounters(pcCount);
 336     if (iTB == 0)
 337     {
 338         fResult = FALSE;
 339         goto end;
 340     }
 341
 342     //
 343     // Add the kings to the piece lists
 344     //
 345     ASSERT(pos->rgSquare[pos->cNonPawns[WHITE][0]].pPiece == WHITE_KING);
 346     wSquares[C_PIECES * 5] = TO64(pos->cNonPawns[WHITE][0]);
 347     ASSERT(wSquares[C_PIECES * 5] >= 0);
 348     ASSERT(wSquares[C_PIECES * 5] <= 64);
 349
 350     ASSERT(pos->rgSquare[pos->cNonPawns[BLACK][0]].pPiece == BLACK_KING);
 351     bSquares[C_PIECES * 5] = TO64(pos->cNonPawns[BLACK][0]);
 352     ASSERT(bSquares[C_PIECES * 5] >= 0);
 353     ASSERT(bSquares[C_PIECES * 5] <= 64);
 354
 355     if (iTB > 0)
 356     {
 357         uColor = (pos->uToMove == WHITE) ? 0 : 1;
 358         invert = 0;
 359         wp = wSquares;
 360         bp = bSquares;
 361     }
 362     else
 363     {
 364         uColor = (pos->uToMove == WHITE) ? 1 : 0;
 365         invert = 1;
 366         wp = bSquares;
 367         bp = wSquares;
 368         iTB = -iTB;
 369     }
 370
 371     if (!FRegisteredFun(iTB, uColor))
 372     {
 373         fResult = FALSE;
 374         goto end;
 375     }
 376     ep = XX;
 377     if (IS_ON_BOARD(pos->cEpSquare))
 378     {
 379         ASSERT((IS_ON_BOARD(pos->cEpSquare + 1) &&
 380                 IS_PAWN(pos->rgSquare[pos->cEpSquare + 1].pPiece)) ||
 381                (IS_ON_BOARD(pos->cEpSquare - 1) &&
 382                 IS_PAWN(pos->rgSquare[pos->cEpSquare - 1].pPiece)));
 383         ep = TO64(pos->cEpSquare);
 384     }
 385
 386 #if 0
 387     DumpPosition(pos);
 388     Trace("iTB = %d, uColor = %u, ep = %u, invert = %u\n",
 389           iTB, uColor, ep, invert);
 390     Trace("wp =\t\t\tbp =\n");
 391     for(x = 0; x < 16; x++)
 392     {
 393         Trace("%u\t\t\t%u\n", wSquares[x], bSquares[x]);
 394     }
 395 #endif
 396     ASSERT(IS_VALID_COLOR(uColor));
 397     fp = PfnIndCalcFun(iTB, uColor);
 398     index = fp((squaret *)wp,
 399                (squaret *)bp,
 400                (squaret)ep,
 401                invert);
 402     value = L_TbtProbeTable(iTB, uColor, index);
 403     if (value == bev_broken)
 404     {
 405         fResult = FALSE;
 406         goto end;
 407     }
 408
 409     if (value > 0)
 410     {
 411         *piScore = INFINITY + (2*(-bev_mi1+value)) - 1;
 412     }
 413     else if (value < 0)
 414     {
 415         *piScore = -INFINITY + (2*(bev_mi1+value));
 416     }
 417     else
 418     {
 419         *piScore = 0; // g_iDrawValue[pos->uToMove];
 420     }
 421     fResult = TRUE;
 422
 423  end:
 424     ReleaseSpinLock(&g_uEgtbLock);
 425 #ifdef PERF_COUNTERS
 426     if (fResult == TRUE)
 427     {
 428         INC(ctx->sCounters.egtb.uHits);
 429     }
 430 #endif
 431     return(fResult);
 432 }