src/dynamic.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     dynamic.c
   8
   9 Abstract:
  10
  11     Dynamic move ordering functions/structures.  By "dynamic move
  12     ordering" I mean killer moves and history heuristic stuff.
  13
  14     Note 1: there are two history tables here.  One is used for move
  15     ordering and the other is used for pruning decisions.  Both only
  16     contain data about non-capture/promote moves.  The former is
  17     updated with roughly remaining_depth^2 at a fail high while the
  18     latter is updated so as to maintain an approximate answer to "what
  19     percent of the time does this move fail high."
  20
  21     Note 2: the globals in this module may be accessed by more than
  22     one searcher thread at the same time; spinlocks used to
  23     synchronize.
  24
  25     Note 3: All of these tables must be cleared when a new game is
  26     started or a new position is loaded onto the board.
  27
  28 Author:
  29
  30     Scott Gasch ([email protected]) 24 Jun 2004
  31
  32 Revision History:
  33
  34     $Id: dynamic.c 345 2007-12-02 22:56:42Z scott $
  35
  36 **/
  37
  38 #include "chess.h"
  39
  40 ULONG g_HistoryCounters[14][128];
  41 #define FH_STATS_TABLE_SIZE (0x20000)
  42
  43 typedef struct _FH_STATS
  44 {
  45     union
  46     {
  47         ULONG uWholeThing;
  48         struct
  49         {
  50             USHORT u16FailHighs;
  51             USHORT u16Attempts;
  52         };
  53     };
  54 } FH_STATS;
  55
  56 FH_STATS g_FailHighs[FH_STATS_TABLE_SIZE];
  57
  58 #ifdef MP
  59 volatile static ULONG g_uDynamicLock;
  60 #define DYN_IS_LOCKED (g_uDynamicLock != 0)
  61 #define LOCK_DYN \
  62     AcquireSpinLock(&g_uDynamicLock); \
  63     ASSERT(DYN_IS_LOCKED)
  64 #define UNLOCK_DYN \
  65     ASSERT(DYN_IS_LOCKED); \
  66     ReleaseSpinLock(&g_uDynamicLock)
  67 #else // no MP
  68 #define DYN_IS_LOCKED (1)
  69 #define LOCK_DYN
  70 #define UNLOCK_DYN
  71 #endif
  72
  73
  74 FLAG
  75 InitializeDynamicMoveOrdering(void)
  76 /**
  77
  78 Routine description:
  79
  80     Initialize dynamic move ordering structures.
  81
  82 Parameters:
  83
  84     void
  85
  86 Return value:
  87
  88     FLAG
  89
  90 **/
  91 {
  92 #ifdef MP
  93     g_uDynamicLock = 0;
  94 #endif
  95     ClearDynamicMoveOrdering();
  96     return(TRUE);
  97 }
  98
  99 void
 100 ClearDynamicMoveOrdering(void)
 101 /**
 102
 103 Routine description:
 104
 105     Clear the global history table.  Killer moves are per-context
 106     structures and must be cleared on a per-context basis.
 107
 108 Parameters:
 109
 110     void
 111
 112 Return value:
 113
 114     void
 115
 116 **/
 117 {
 118     ULONG u;
 119
 120     memset(g_HistoryCounters, 0, sizeof(g_HistoryCounters));
 121     for (u = 0; u < FH_STATS_TABLE_SIZE; u++)
 122     {
 123         g_FailHighs[u].uWholeThing = 0x00010001;
 124     }
 125 }
 126
 127
 128 static void
 129 _RecordMoveFailHigh(MOVE mv)
 130 /**
 131
 132 Routine description:
 133
 134     Update the "fail high percentage" history table for this move.
 135     The table is used to make pruning decisions, not to rank moves.
 136
 137 Parameters:
 138
 139     MOVE mv
 140
 141 Return value:
 142
 143     static void
 144
 145 **/
 146 {
 147     ULONG u = MOVE_TO_INDEX(mv);
 148     ULONG v = g_FailHighs[u].uWholeThing;
 149
 150     ASSERT(DYN_IS_LOCKED);
 151     if (((v & 0x0000FFFF) == 0x0000FFFF) || ((v & 0xFFFF0000) == 0xFFFF0000))
 152     {
 153         g_FailHighs[u].u16FailHighs >>= 1;
 154         g_FailHighs[u].u16Attempts >>= 1;
 155     }
 156     g_FailHighs[u].u16FailHighs++;
 157     g_FailHighs[u].u16Attempts++;
 158     ASSERT(g_FailHighs[u].u16FailHighs != 0);
 159     ASSERT(g_FailHighs[u].u16Attempts != 0);
 160     ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs);
 161 }
 162
 163
 164 static void
 165 _RecordMoveFailure(MOVE mv)
 166 /**
 167
 168 Routine description:
 169
 170     Update the fail high percentage table with the information that a
 171     move has not produced a fail high cutoff when it was considered.
 172
 173 Parameters:
 174
 175     MOVE mv
 176
 177 Return value:
 178
 179     static void
 180
 181 **/
 182 {
 183     ULONG u = MOVE_TO_INDEX(mv);
 184
 185     ASSERT(DYN_IS_LOCKED);
 186     if (g_FailHighs[u].u16Attempts == 0xFFFF)
 187     {
 188         g_FailHighs[u].u16FailHighs >>= 1;
 189         g_FailHighs[u].u16Attempts >>= 1;
 190     }
 191     g_FailHighs[u].u16Attempts++;
 192     ASSERT(g_FailHighs[u].u16Attempts != 0);
 193     ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs);
 194 }
 195
 196
 197 static void
 198 _NewKillerMove(SEARCHER_THREAD_CONTEXT *ctx,
 199                MOVE mv,
 200                SCORE iScore)
 201 /**
 202
 203 Routine description:
 204
 205     Add a new killer move at a ply.
 206
 207 Parameters:
 208
 209     SEARCHER_THREAD_CONTEXT *ctx,
 210     MOVE mv,
 211     SCORE iScore
 212
 213 Return value:
 214
 215     void
 216
 217 **/
 218 {
 219     ULONG uPly = ctx->uPly;
 220
 221     ASSERT(uPly >= 0);
 222     ASSERT(uPly < MAX_PLY_PER_SEARCH);
 223     ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
 224     ASSERT(mv.uMove);
 225
 226     if (mv.bvFlags & MOVE_FLAG_ESCAPING_CHECK)
 227     {
 228         if (!IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][0]))
 229         {
 230             ctx->mvKillerEscapes[uPly][1] = ctx->mvKillerEscapes[uPly][0];
 231             ctx->mvKillerEscapes[uPly][0] = mv;
 232         }
 233         ASSERT(!IS_SAME_MOVE(ctx->mvKillerEscapes[uPly][0],
 234                              ctx->mvKillerEscapes[uPly][1]));
 235     }
 236     else
 237     {
 238         mv.bvFlags |= ((iScore >= +NMATE) * MOVE_FLAG_KILLERMATE);
 239         if (!IS_SAME_MOVE(mv, ctx->mvKiller[uPly][0]))
 240         {
 241             ctx->mvKiller[uPly][1] = ctx->mvKiller[uPly][0];
 242             ctx->mvKiller[uPly][0] = mv;
 243             if (ctx->mvKiller[uPly][1].uMove == 0)
 244             {
 245                 ctx->mvKiller[uPly][1] = ctx->mvNullmoveRefutations[uPly];
 246             }
 247         }
 248         ASSERT(!IS_SAME_MOVE(ctx->mvKiller[uPly][0], ctx->mvKiller[uPly][1]));
 249     }
 250 }
 251
 252
 253 static void
 254 _IncrementMoveHistoryCounter(MOVE mv,
 255                              ULONG uDepth)
 256 /**
 257
 258 Routine description:
 259
 260     Increase a move's history counter in the global history table.
 261     Also affect the history pruning counters in prune.c.
 262
 263 Parameters:
 264
 265     MOVE mv,
 266     ULONG uDepth
 267
 268 Return value:
 269
 270     void
 271
 272 **/
 273 {
 274     ULONG x, y;
 275     ULONG uVal;
 276     ULONG *pu;
 277
 278     ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
 279     uVal = uDepth / ONE_PLY;
 280     ASSERT(uVal >= 0);
 281     ASSERT(uVal <= MAX_PLY_PER_SEARCH);
 282     uVal += 1;
 283     uVal *= uVal;
 284     ASSERT(uVal > 0);
 285
 286     pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]);
 287     LOCK_DYN;
 288     *pu += uVal;
 289
 290     //
 291     // Make sure that the history weight doesn't get large enough to
 292     // affect the move flags or else our move ordering algorithm is
 293     // screwed.
 294     //
 295     while (*pu & ~STRIP_OFF_FLAGS)
 296     {
 297         for (x = 0; x <= WHITE_KING; x++)
 298         {
 299             FOREACH_SQUARE(y)
 300             {
 301                 g_HistoryCounters[x][y] >>= 4;
 302             }
 303         }
 304     }
 305
 306 #ifdef MP
 307     //
 308     // The purpose of this restriction is to ease contention for the
 309     // memory bandwidth of the machine on dual-core / dual proc
 310     // systems.  The net result is positive.
 311     //
 312     if (uDepth > THREE_PLY)
 313     {
 314         _RecordMoveFailHigh(mv);
 315     }
 316 #else
 317     _RecordMoveFailHigh(mv);
 318 #endif
 319     UNLOCK_DYN;
 320 }
 321
 322 static void
 323 _DecrementMoveHistoryCounter(MOVE mv,
 324                              ULONG uDepth)
 325 /**
 326
 327 Routine description:
 328
 329     Decrease a move's history counter in the global history table.
 330
 331 Parameters:
 332
 333     MOVE mv,
 334     ULONG uDepth
 335
 336 Return value:
 337
 338     void
 339
 340 **/
 341 {
 342     ULONG uVal;
 343     ULONG *pu;
 344
 345     ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
 346     uVal = uDepth / ONE_PLY;
 347     ASSERT(uVal >= 0);
 348     ASSERT(uVal <= MAX_PLY_PER_SEARCH);
 349     uVal /= 4;
 350     uVal += 1;
 351     ASSERT(uVal > 0);
 352
 353     pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]);
 354     LOCK_DYN;
 355     if (*pu >= uVal)
 356     {
 357         *pu -= uVal;
 358     }
 359     else
 360     {
 361         *pu = 0;
 362     }
 363     _RecordMoveFailure(mv);
 364     UNLOCK_DYN;
 365 }
 366
 367
 368 void
 369 UpdateDynamicMoveOrdering(IN SEARCHER_THREAD_CONTEXT *ctx,
 370                           IN ULONG uRemainingDepth,
 371                           IN MOVE mvBest,
 372                           IN SCORE iScore,
 373                           IN ULONG uCurrent)
 374 /**
 375
 376 Routine description:
 377
 378     Update dynamic move ordering structs for a particular move (and,
 379     possibly, the other moves that were considered prior to this move
 380     in the move ordering).  This is called when a move beats alpha at
 381     the root or in Search (but not in QSearch).
 382
 383 Parameters:
 384
 385     SEARCHER_THREAD_CONTEXT *ctx,
 386     ULONG uRemainingDepth,
 387     MOVE mvBest,
 388     SCORE iScore,
 389     ULONG uCurrent
 390
 391 Return value:
 392
 393     void
 394
 395 **/
 396 {
 397     ULONG u;
 398     MOVE mv;
 399
 400     //
 401     // Add this move to the killer list and increment its history count
 402     //
 403     if (!IS_CAPTURE_OR_PROMOTION(mvBest))
 404     {
 405         _NewKillerMove(ctx, mvBest, iScore);
 406         _IncrementMoveHistoryCounter(mvBest, uRemainingDepth);
 407     }
 408
 409     //
 410     // If this move was not the first we considered at this node,
 411     // decrement the history counters of moves we considered before
 412     // it.
 413     //
 414     uCurrent -= (uCurrent != 0);
 415     for (u = ctx->sMoveStack.uBegin[ctx->uPly];
 416          u < uCurrent;
 417          u++)
 418     {
 419         ASSERT(IS_SAME_MOVE(ctx->sMoveStack.mvf[uCurrent].mv, mvBest));
 420         mv = ctx->sMoveStack.mvf[u].mv;
 421         ASSERT(!IS_SAME_MOVE(mv, mvBest));
 422         if (!IS_CAPTURE_OR_PROMOTION(mv))
 423         {
 424             _DecrementMoveHistoryCounter(mv, uRemainingDepth);
 425         }
 426     }
 427 }
 428
 429
 430
 431
 432 ULONG
 433 GetMoveFailHighPercentage(IN MOVE mv)
 434 /**
 435
 436 Routine description:
 437
 438     Lookup a move in the fail high percentage history table and return
 439     its approximate fail high percentage.
 440
 441 Parameters:
 442
 443     MOVE mv
 444
 445 Return value:
 446
 447     ULONG
 448
 449 **/
 450 {
 451     ULONG u = MOVE_TO_INDEX(mv);
 452     ULONG n, d;
 453
 454     n = g_FailHighs[u].u16FailHighs;
 455     d = g_FailHighs[u].u16Attempts;
 456     if (d == 0)
 457     {
 458         return(0);
 459     }
 460     n *= 100;
 461     return(n / d);
 462 }
 463
 464
 465 void
 466 CleanupDynamicMoveOrdering(void)
 467 /**
 468
 469 Routine description:
 470
 471     Cleanup dynamic move ordering structs -- basically a noop for now.
 472
 473 Parameters:
 474
 475     void
 476
 477 Return value:
 478
 479     void
 480
 481 **/
 482 {
 483     NOTHING;
 484 }
 485
 486
 487 void
 488 MaintainDynamicMoveOrdering(void)
 489 /**
 490
 491 Routine description:
 492
 493     Perform routine maintenance on dynamic move ordering data by
 494     reducing the magnitude of the history counters.
 495
 496 Parameters:
 497
 498 Return value:
 499
 500     void
 501
 502 **/
 503 {
 504     ULONG x, y;
 505
 506     LOCK_DYN;
 507     for (x = 0; x <= WHITE_KING; x++)
 508     {
 509         FOREACH_SQUARE(y)
 510         {
 511             g_HistoryCounters[x][y] >>= 1;
 512         }
 513     }
 514     UNLOCK_DYN;
 515 }