src/data.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     data.c
   8
   9 Abstract:
  10
  11     Large data structures and the code that creates/verifies them.
  12
  13 Author:
  14
  15     Scott Gasch ([email protected]) 10 May 2004
  16
  17 Revision History:
  18
  19     $Id: data.c 345 2007-12-02 22:56:42Z scott $
  20
  21 **/
  22
  23 #include "chess.h"
  24
  25 // Distance between two squares lookup table
  26 ULONG g_uDistance[256];
  27 ULONG *g_pDistance = &(g_uDistance[128]);
  28
  29 // Who controls the square lookup table
  30 CHAR g_SwapTable[14][32][32];
  31
  32 // Vector (bitvector indicating which pieces can move between squares) and
  33 // Delta (direction to travel to get from square a to square b) lookup table.
  34 VECTOR_DELTA g_VectorDelta[256];
  35 VECTOR_DELTA *g_pVectorDelta = &(g_VectorDelta[128]);
  36
  37 // How many generated moves should we bother to sort
  38 ULONG g_uSearchSortLimits[MAX_PLY_PER_SEARCH];
  39
  40 // Hardcoded move patterns to terminate PVs with
  41 MOVE NULLMOVE = {0};
  42 MOVE HASHMOVE = {0x11118888};
  43 MOVE RECOGNMOVE = {0x22228888};
  44 MOVE DRAWMOVE = {0x33338888};
  45 MOVE MATEMOVE = {0x44448888};
  46
  47 // Is a square white?
  48 FLAG g_fIsWhiteSquare[128];
  49
  50 #ifdef DEBUG
  51 COOR
  52 DistanceBetweenSquares(COOR a, COOR b)
  53 {
  54     int i = (int)a - (int)b + 128;
  55     int j = (int)b - (int)a + 128;
  56     ASSERT(IS_ON_BOARD(a));
  57     ASSERT(IS_ON_BOARD(b));
  58     ASSERT((i >= 0) && (i < 256));
  59     ASSERT(g_uDistance[i] == REAL_DISTANCE(a, b));
  60     ASSERT(g_pDistance[a - b] == g_uDistance[i]);
  61     ASSERT(g_pDistance[b - a] == g_uDistance[i]);
  62     ASSERT(g_uDistance[j] == REAL_DISTANCE(a, b));
  63     return(REAL_DISTANCE(a, b));
  64 }
  65
  66 #define VALID_VECTOR(x) \
  67     (((x) == 0) || \
  68      ((x) == (1 << KNIGHT)) || \
  69      ((x) == ( (1 << BISHOP) | (1 << QUEEN))) || \
  70      ((x) == ( (1 << ROOK) | (1 << QUEEN))) || \
  71      ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING))) || \
  72      ((x) == ( (1 << ROOK) | (1 << QUEEN) | (1 << KING))) || \
  73      ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING) | (1 << PAWN))))
  74
  75
  76 #define VALID_INDEX(x) \
  77     (((x) >= -128) && ((x) <= 127))
  78
  79 ULONG
  80 CheckVectorWithIndex(int i, ULONG uColor)
  81 {
  82         ULONG u;
  83     ASSERT(VALID_INDEX(i));
  84     ASSERT(IS_VALID_COLOR(uColor));
  85     u = g_pVectorDelta[i].iVector[uColor];
  86     ASSERT(VALID_VECTOR(u));
  87     ASSERT(u == g_VectorDelta[i + 128].iVector[uColor]);
  88     ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
  89     return(u);
  90 }
  91
  92 #define VALID_DELTA(x) \
  93     (((x) == 0) || \
  94      ((x) == +1) || ((x) == -1) || \
  95      ((x) == +16) || ((x) == -16) || \
  96      ((x) == +15) || ((x) == -15) || \
  97      ((x) == +17) || ((x) == -17))
  98
  99 int
 100 DirectionBetweenSquaresWithIndex(int i)
 101 {
 102     int iDir;
 103     ASSERT(VALID_INDEX(i));
 104     iDir = g_pVectorDelta[i].iDelta;
 105     ASSERT(iDir == g_VectorDelta[i + 128].iDelta);
 106     ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
 107     ASSERT(VALID_DELTA(iDir));
 108     ASSERT(iDir == -g_pVectorDelta[i].iNegDelta);
 109     return(iDir);
 110 }
 111
 112 int
 113 DirectionBetweenSquaresFromTo(COOR from, COOR to)
 114 {
 115     int i = (int)from - (int)to;
 116     return DirectionBetweenSquaresWithIndex(i);
 117 }
 118
 119 int
 120 NegativeDirectionBetweenSquaresWithIndex(int i)
 121 {
 122     int iDir;
 123     ASSERT(VALID_INDEX(i));
 124     iDir = g_pVectorDelta[i].iNegDelta;
 125     ASSERT(iDir == g_VectorDelta[i + 128].iNegDelta);
 126     ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
 127     ASSERT(VALID_DELTA(iDir));
 128     ASSERT(iDir == -g_pVectorDelta[i].iDelta);
 129     return(iDir);
 130 }
 131
 132 int
 133 DirectionBetweenSquares(COOR cFrom, COOR cTo)
 134 {
 135     int i = (int)cFrom - (int)cTo;
 136     return(DirectionBetweenSquaresWithIndex(i));
 137 }
 138
 139 FLAG
 140 IsSquareWhite(COOR c)
 141 {
 142         BITBOARD bb;
 143     FLAG f = IS_WHITE_SQUARE_COOR(c);
 144     ASSERT(IS_ON_BOARD(c));
 145     ASSERT(f == g_fIsWhiteSquare[c]);
 146     bb = COOR_TO_BB(c);
 147     ASSERT(f == ((bb & BBWHITESQ) != 0));
 148     ASSERT(f == ((bb & BBBLACKSQ) == 0));
 149     return(f);
 150 }
 151 #endif
 152
 153 void
 154 VerifyVectorDelta(void)
 155 {
 156     int iIndex;
 157     int iChecksum = 0;
 158
 159     for (iIndex = 0;
 160          iIndex < 256;
 161          iIndex++)
 162     {
 163         ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[BLACK]));
 164         ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[WHITE]));
 165         ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iDelta));
 166         ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iNegDelta));
 167         ASSERT(-g_VectorDelta[iIndex].iDelta ==
 168                g_VectorDelta[iIndex].iNegDelta);
 169         iChecksum += g_VectorDelta[iIndex].iVector[BLACK] * iIndex;
 170         iChecksum += g_VectorDelta[iIndex].iVector[WHITE] * iIndex;
 171         iChecksum += g_VectorDelta[iIndex].iDelta * iIndex;
 172     }
 173
 174     if (iChecksum != 0xb1b58)
 175     {
 176         UtilPanic(DETECTED_INCORRECT_INITIALIZATION,
 177                   NULL,
 178                   "vector/delta",
 179                   (void *)iChecksum,
 180                   (void *)0xb1b58,
 181                   __FILE__, __LINE__);
 182     }
 183 }
 184
 185 void
 186 InitializeSearchDepthArray(void)
 187 {
 188     ULONG x;
 189
 190     for (x = 0;
 191          x < ARRAY_LENGTH(g_uSearchSortLimits);
 192          x++)
 193     {
 194         g_uSearchSortLimits[x] = 5;
 195     }
 196     g_uSearchSortLimits[0] = 0;
 197     g_uSearchSortLimits[1] = 17;
 198     g_uSearchSortLimits[2] = 12;
 199     g_uSearchSortLimits[3] = 9;
 200     g_uSearchSortLimits[4] = 7;
 201     g_uSearchSortLimits[5] = 6;
 202 }
 203
 204 #ifdef DEBUG
 205 ULONG
 206 GetSearchSortLimit(ULONG uPly)
 207 {
 208     ASSERT(uPly > 0);
 209     ASSERT(uPly < MAX_PLY_PER_SEARCH);
 210     ASSERT(g_uSearchSortLimits[uPly] != 0);
 211     return(g_uSearchSortLimits[uPly]);
 212 }
 213 #endif
 214
 215 void
 216 InitializeWhiteSquaresTable(void)
 217 {
 218     COOR c;
 219
 220     FOREACH_SQUARE(c)
 221     {
 222         g_fIsWhiteSquare[c] = FALSE;
 223         if (!IS_ON_BOARD(c))
 224         {
 225             continue;
 226         }
 227         g_fIsWhiteSquare[c] = IS_WHITE_SQUARE_COOR(c);
 228     }
 229 }
 230
 231 void
 232 InitializeVectorDeltaTable(void)
 233 {
 234     COOR cStart;
 235     COOR cNew;
 236     COOR cRay;
 237     int iIndex;
 238     PIECE p;
 239     int iDir;
 240     ULONG u;
 241     static const BYTE _LOCATIONS[] =
 242     {
 243         D4, A5, A3, G3, C1, B5, H4, E5, E3, A6, C5, A5, A5,
 244         G5, A6, D3, D2, A5, E1, E1, A6, H4, B2, D1, D2, E5
 245     };
 246     static int iNumDirs[7] =    { 0, 0, 8, 4, 4, 8, 8 };
 247     static int iDelta[7][8] =   { {   0,   0,   0,   0,   0,   0,   0,   0 },
 248                                   {   0,   0,   0,   0,   0,   0,   0,   0 },
 249                                   { -33, -31, -18, -14, +14, +18, +31, +33 },
 250                                   { -17, -15, +15, +17,   0,   0,   0,   0 },
 251                                   { -16,  -1,  +1, +16,   0,   0,   0,   0 },
 252                                   { -17, -16, -15,  -1,  +1, +15, +16, +17 },
 253                                   { -17, -16, -15,  -1,  +1, +15, +16, +17 } };
 254
 255     memset(g_VectorDelta, 0, sizeof(g_VectorDelta));
 256     FOREACH_SQUARE(cStart)
 257     {
 258         if (!IS_ON_BOARD(cStart)) continue;
 259         for (u = 0; u < ARRAY_LENGTH(_LOCATIONS); u++)
 260         {
 261             if (cStart == _LOCATIONS[u])
 262             {
 263                 iIndex = 0;
 264             }
 265         }
 266
 267         //
 268         // Do the pawn bits
 269         //
 270         iIndex = (int)cStart - ((int)cStart - 17) + 128;
 271         g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN);
 272         iIndex = (int)cStart - ((int)cStart - 15) + 128;
 273         g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN);
 274
 275         iIndex = (int)cStart - ((int)cStart + 17) + 128;
 276         g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN);
 277         iIndex = (int)cStart - ((int)cStart + 15) + 128;
 278         g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN);
 279
 280         //
 281         // Do the piece bits
 282         //
 283         for (p = KNIGHT; p <= KING; p++)
 284         {
 285             for (iDir = 0;
 286                  iDir < iNumDirs[p];
 287                  iDir++)
 288             {
 289                 cRay = cStart;
 290                 cNew = cRay + iDelta[p][iDir];
 291                 while (IS_ON_BOARD(cNew))
 292                 {
 293                     iIndex = (int)cStart - (int)cNew + 128;
 294
 295                     //
 296                     // Fill in the vector
 297                     //
 298                     g_VectorDelta[iIndex].iVector[WHITE] |= (1 << p);
 299                     g_VectorDelta[iIndex].iVector[BLACK] |= (1 << p);
 300
 301                     //
 302                     // Fill in the delta
 303                     //
 304                     if (FILE(cStart) == FILE(cNew))
 305                     {
 306                         if (cStart < cNew)
 307                         {
 308                             g_VectorDelta[iIndex].iDelta = 16;
 309                             g_VectorDelta[iIndex].iNegDelta = -16;
 310                         }
 311                         else
 312                         {
 313                             g_VectorDelta[iIndex].iDelta = -16;
 314                             g_VectorDelta[iIndex].iNegDelta = 16;
 315                         }
 316                     }
 317                     else if (RANK(cStart) == RANK(cNew))
 318                     {
 319                         if (cStart < cNew)
 320                         {
 321                             g_VectorDelta[iIndex].iDelta = 1;
 322                             g_VectorDelta[iIndex].iNegDelta = -1;
 323                         }
 324                         else
 325                         {
 326                             g_VectorDelta[iIndex].iDelta = -1;
 327                             g_VectorDelta[iIndex].iNegDelta = 1;
 328                         }
 329                     }
 330                     else if ((cStart % 15) == (cNew % 15))
 331                     {
 332                         if (cStart < cNew)
 333                         {
 334                             g_VectorDelta[iIndex].iDelta = +15;
 335                             g_VectorDelta[iIndex].iNegDelta = -15;
 336                         }
 337                         else
 338                         {
 339                             g_VectorDelta[iIndex].iDelta = -15;
 340                             g_VectorDelta[iIndex].iNegDelta = 15;
 341                         }
 342                     }
 343                     else if ((cStart % 17) == (cNew % 17))
 344                     {
 345                         if (cStart < cNew)
 346                         {
 347                             g_VectorDelta[iIndex].iDelta = +17;
 348                             g_VectorDelta[iIndex].iNegDelta = -17;
 349                         }
 350                         else
 351                         {
 352                             g_VectorDelta[iIndex].iDelta = -17;
 353                             g_VectorDelta[iIndex].iNegDelta = 17;
 354                         }
 355                     }
 356                     cNew += iDelta[p][iDir];
 357
 358                     if ((KING == p) || (KNIGHT == p))
 359                     {
 360                         break;
 361                     }
 362                 }
 363             }
 364         }
 365     }
 366
 367     (void)VerifyVectorDelta();
 368 #ifdef OSX
 369     //
 370     // nasm under OSX/macho has a nasty bug that causes the addresses
 371     // of extern symbols to be screwed up.  I only use two extern data
 372     // structs in the x86.asm code: the vector delta table and the
 373     // piece data table.  My workaround to the nasm bug is to copy
 374     // these tables into a symbol in the asm module and access them
 375     // locally on OSX.
 376     //
 377     extern VECTOR_DELTA *g_NasmVectorDelta;
 378     extern PIECE_DATA *g_NasmPieceData;
 379
 380     memcpy(&g_NasmVectorDelta, &g_VectorDelta, sizeof(g_VectorDelta));
 381     memcpy(&g_NasmPieceData, &g_PieceData, sizeof(g_PieceData));
 382 #endif
 383 }
 384
 385 //
 386 // TODO: fix this to use attack counts also
 387 //
 388 void
 389 InitializeSwapTable(void)
 390 {
 391     ULONG GET_HIGH_BIT[32] =
 392     {
 393         0, // 00000 = 0
 394         1, // 00001 = 1
 395         2, // 00010 = 2
 396         2, // 00011 = 3
 397         4, // 00100 = 4
 398         4, // 00101 = 5
 399         4, // 00110 = 6
 400         4, // 00111 = 7
 401         8, // 01000 = 8
 402         8, // 01001 = 9
 403         8, // 01010 = 10
 404         8, // 01011 = 11
 405         8, // 01100 = 12
 406         8, // 01101 = 13
 407         8, // 01110 = 14
 408         8, // 01111 = 15
 409        16, // 10000 = 16
 410        16, // 10001 = 17
 411        16, // 10010 = 18
 412        16, // 10011 = 19
 413        16, // 10100 = 20
 414        16, // 10101 = 21
 415        16, // 10110 = 22
 416        16, // 10111 = 23
 417        16, // 11000 = 24
 418        16, // 11001 = 25
 419        16, // 11010 = 26
 420        16, // 11011 = 27
 421        16, // 11100 = 28
 422        16, // 11101 = 29
 423        16, // 11110 = 30
 424        16  // 11111 = 31
 425     };
 426     ULONG uOnMove;
 427     PIECE p;
 428     ULONG uAtStake;
 429     ULONG uBlack;
 430     ULONG uWhite;
 431     ULONG uOld;
 432     ULONG uGains[2];
 433     ULONG uAttacks[2];
 434     INT iDiff;
 435
 436     for (p = 0; p <= WHITE_KING; p++)
 437     {
 438         if (p > 1)
 439         {
 440             for (uBlack = 0; uBlack < 32; uBlack++)
 441             {
 442                 for (uWhite = 0; uWhite < 32; uWhite++)
 443                 {
 444                     uGains[BLACK] = uGains[WHITE] = 0;
 445                     uAttacks[BLACK] = uBlack;
 446                     uAttacks[WHITE] = uWhite;
 447                     uAtStake = PIECE_VALUE(p);
 448                     uOnMove = WHITE;
 449                     if (GET_COLOR(p) == WHITE)
 450                     {
 451                         uOnMove = BLACK;
 452                     }
 453
 454                     //
 455                     // Ok, if the side on move has an attack, play it
 456                     // and give them credit for some plunder.
 457                     //
 458                     while(uAttacks[uOnMove])
 459                     {
 460                         uOld = uAtStake;
 461                         uGains[uOnMove] += uAtStake;
 462                         uAtStake = GET_HIGH_BIT[uAttacks[uOnMove]];
 463                         if (uAtStake == 16)
 464                         {
 465                             uAtStake = VALUE_PAWN;
 466                         }
 467                         else if (uAtStake == 8)
 468                         {
 469                             uAtStake = VALUE_BISHOP;
 470                         }
 471                         else if (uAtStake == 4)
 472                         {
 473                             uAtStake = VALUE_ROOK;
 474                         }
 475                         else if (uAtStake == 2)
 476                         {
 477                             uAtStake = VALUE_QUEEN;
 478                         }
 479                         else if (uAtStake == 1)
 480                         {
 481                             //
 482                             // Don't let them move into check
 483                             //
 484                             if (uAttacks[FLIP(uOnMove)])
 485                             {
 486                                 uGains[uOnMove] -= uOld;
 487                                 uAtStake = 0;
 488                             }
 489                             break;
 490                         }
 491                         else
 492                         {
 493                             UtilPanic(SHOULD_NOT_GET_HERE,
 494                                       NULL, NULL, NULL, NULL,
 495                                       __FILE__, __LINE__);
 496                         }
 497                         uAttacks[uOnMove] &= ~GET_HIGH_BIT[uAttacks[uOnMove]];
 498                         uOnMove = FLIP(uOnMove);
 499                     }
 500
 501                     //
 502                     // The side on move doesn't have an attack... does
 503                     // the side not on move have an attack?  If so they
 504                     // get a chance to assert some more control.
 505                     //
 506                     if (uAttacks[FLIP(uOnMove)])
 507                     {
 508                         uGains[FLIP(uOnMove)] += 100;
 509                     }
 510
 511                     if (uGains[BLACK] > uGains[WHITE])
 512                     {
 513                         iDiff = uGains[BLACK] - uGains[WHITE];
 514                         iDiff /= 100;
 515                                                 iDiff += (iDiff == 0);
 516                         g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff);
 517                         g_SwapTable[p][uWhite][uBlack] *= -1;
 518                     }
 519                     else if (uGains[WHITE] > uGains[BLACK])
 520                     {
 521                         iDiff = uGains[WHITE] - uGains[BLACK];
 522                         iDiff /= 100;
 523                                                 iDiff += (iDiff == 0);
 524                         g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff);
 525                     }
 526                     else
 527                     {
 528                         g_SwapTable[p][uWhite][uBlack] = 0;
 529                     }
 530                 }
 531             }
 532         }
 533         else                                  // no piece sitting there
 534         {
 535             for (uBlack = 0; uBlack < 32; uBlack++)
 536             {
 537                 for (uWhite = 0; uWhite < 32; uWhite++)
 538                 {
 539                     if (uBlack > uWhite)
 540                     {
 541                         g_SwapTable[p][uWhite][uBlack] = -1;
 542                     }
 543                     else if (uWhite > uBlack)
 544                     {
 545                         g_SwapTable[p][uWhite][uBlack] = +1;
 546                     }
 547                     else
 548                     {
 549                         g_SwapTable[p][uWhite][uBlack] = 0;
 550                     }
 551                 }
 552             }
 553         }
 554     }
 555 }
 556
 557 void
 558 InitializeDistanceTable(void)
 559 {
 560     COOR x, y;
 561     int i;
 562 #ifdef DEBUG
 563         int j;
 564 #endif
 565
 566     for (x = 0; x < 128; x++)
 567     {
 568         if (!IS_ON_BOARD(x)) continue;
 569         for (y = 0; y < 128; y++)
 570         {
 571             if (!IS_ON_BOARD(y)) continue;
 572             i = (int)x - (int)y;
 573             i += 128;
 574             g_uDistance[i] = REAL_DISTANCE(x, y);
 575             ASSERT(g_uDistance[i] >= 0);
 576             ASSERT(g_uDistance[i] <= 7);
 577         }
 578     }
 579
 580 #ifdef DEBUG
 581     for (x = 0; x < 128; x++)
 582     {
 583         if (!IS_ON_BOARD(x)) continue;
 584         for (y = 0; y < 128; y++)
 585         {
 586             if (!IS_ON_BOARD(y)) continue;
 587             i = (int)x - (int)y + 128;
 588             ASSERT(g_uDistance[i] == REAL_DISTANCE(x, y));
 589             ASSERT(g_pDistance[x - y] == g_uDistance[i]);
 590             ASSERT(&(g_pDistance[x - y]) == &(g_uDistance[i]));
 591             j = (int)y - (int)x + 128;
 592             ASSERT(g_uDistance[j] == REAL_DISTANCE(x, y));
 593             ASSERT(g_pDistance[y - x] == g_uDistance[j]);
 594             ASSERT(&(g_pDistance[y - x]) == &(g_uDistance[j]));
 595         }
 596     }
 597 #endif
 598 }