gnushogi/search.c

   1 /*
   2  * FILE: search.c
   3  *
   4  * ----------------------------------------------------------------------
   5  * Copyright (c) 1993, 1994, 1995 Matthias Mutz
   6  * Copyright (c) 1999 Michael Vanier and the Free Software Foundation
   7  * Copyright (c) 2008, 2013, 2014 Yann Dirson and the Free Software Foundation
   8  *
   9  * GNU SHOGI is based on GNU CHESS
  10  *
  11  * Copyright (c) 1988, 1989, 1990 John Stanback
  12  * Copyright (c) 1992 Free Software Foundation
  13  *
  14  * This file is part of GNU SHOGI.
  15  *
  16  * GNU Shogi is free software; you can redistribute it and/or modify it
  17  * under the terms of the GNU General Public License as published by the
  18  * Free Software Foundation; either version 3 of the License,
  19  * or (at your option) any later version.
  20  *
  21  * GNU Shogi is distributed in the hope that it will be useful, but WITHOUT
  22  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  23  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  24  * for more details.
  25  *
  26  * You should have received a copy of the GNU General Public License along
  27  * with GNU Shogi; see the file COPYING. If not, see
  28  * <http://www.gnu.org/licenses/>.
  29  * ----------------------------------------------------------------------
  30  *
  31  */
  32
  33 #include "gnushogi.h"
  34
  35 short background = 0;
  36 static short DepthBeyond;
  37 unsigned short PrVar[MAXDEPTH];
  38 extern short recycle, ISZERO;
  39 extern void FlagString(unsigned short flags, char *s);
  40
  41 #ifdef NULLMOVE
  42 short null;         /* Null-move already made or not */
  43 short PVari;        /* Is this the PV */
  44 #endif
  45
  46 short zwndw;
  47 short movesLeft, currentMove;
  48
  49
  50
  51 /* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
  52
  53
  54
  55 /*
  56  *  Check for draw by fourfold repetition
  57  *  (same side, same captures, same board).
  58  *  WARNING: this is not save (sp? safe?) yet due to possible hash collisions.
  59  */
  60
  61 short
  62 repetition()
  63 {
  64     short i, cnt = 0;
  65
  66 #ifndef NOREPETITION
  67     struct GameRec  *g;
  68
  69     if (GameCnt > Game50 + 6)
  70     {
  71         for (i = GameCnt - 1; i >= Game50; i -= 2)
  72         {
  73             g = &GameList[i];
  74
  75             if (g->hashkey == hashkey && g->hashbd == hashbd)
  76                 cnt++;
  77         }
  78     }
  79 #endif
  80
  81     return cnt;
  82 }
  83
  84
  85
  86 int plyscore, globalscore;
  87
  88
  89 /*
  90  * Find the best move in the tree between indexes p1 and p2. Swap the best
  91  * move into the p1 element.
  92  */
  93
  94 int
  95 pick(short p1, short p2)
  96 {
  97     struct leaf  *p, *q, *r, *k;
  98     short s0;
  99     struct leaf temp;
 100
 101     k = p = &Tree[p1];
 102     q = &Tree[p2];
 103     s0 = p->score;
 104
 105     for (r = p + 1; r <= q; r++)
 106     {
 107         if ((r->score) > s0)
 108         {
 109             s0 = r->score;
 110             p = r;
 111         }
 112     }
 113
 114     if (p != k)
 115     {
 116         temp = *p;
 117         *p = *k;
 118         *k = temp;
 119         return true;
 120     }
 121
 122     return false;
 123 }
 124
 125 int bookflag = false;
 126 int Jscore = 0;
 127
 128 int TCcount;
 129 long TCleft = 0;
 130
 131
 132
 133
 134 /*
 135  * Select a move by calling function search() at progressively deeper ply
 136  * until time is up or a mate or draw is reached. An alpha-beta window of
 137  * -Awindow to +Bwindow points is set around the score returned from the
 138  * previous iteration. If Sdepth != 0 then the program has correctly
 139  * predicted the opponents move and the search will start at a depth of
 140  * Sdepth + 1 rather than a depth of 1.
 141  */
 142
 143 void
 144 SelectMove(short side, SelectMove_mode iop)
 145 {
 146     static short i, tempb, tempc, tempsf, tempst, xside, rpt;
 147     static short alpha, beta, score;
 148     static struct GameRec  *g;
 149     short sqking, in_check, blockable;
 150
 151 #ifdef BOOKTEST
 152     printf("hashbd = %ld (hashkey >> 16)|side = %d\n",
 153            hashbd, (hashkey >> 16)|side);
 154 #endif
 155
 156     flag.timeout = false;
 157     flag.back = false;
 158     flag.musttimeout = false;
 159
 160     xside = side ^ 1;
 161
 162 #if ttblsz
 163     recycle = (GameCnt % rehash) - rehash;
 164 #endif
 165
 166     ExaminePosition(side);
 167
 168     /* if background mode set to infinite */
 169     if (iop == BACKGROUND_MODE)
 170     {
 171         background = true;
 172         /* if background mode set response time to infinite */
 173         ResponseTime = 9999999;
 174     }
 175     else
 176     {
 177         background = false; /* [HGM] with ponder on we did not switch back to foreground mode??? */
 178         player = side;
 179         SetResponseTime(side);
 180     }
 181
 182 #ifdef QUIETBACKGROUND
 183     if (!background)
 184 #endif /* QUIETBACKGROUND */
 185         dsp->ShowResponseTime();
 186
 187     ExtraTime = 0;
 188
 189     score = ScorePosition(side);
 190
 191 #ifdef QUIETBACKGROUND
 192     if (!background)
 193 #endif /* QUIETBACKGROUND */
 194         dsp->ShowSidetoMove();
 195
 196 #ifdef QUIETBACKGROUND
 197     if (!background)
 198 #endif /* QUIETBACKGROUND */
 199         dsp->SearchStartStuff(side);
 200
 201 #ifdef HISTORY
 202     array_zero(history, sizeof_history);
 203 #endif
 204
 205     FROMsquare = TOsquare = -1;
 206     PV = 0;
 207
 208     if (iop == FOREGROUND_MODE)
 209         hint = 0;
 210
 211     /*
 212      * If the last move was the hint, select the computed answer to the
 213      * hint as first move to examine.
 214      */
 215
 216 #if MAXDEPTH > 3
 217     if (GameCnt > 0)
 218     {
 219         SwagHt = (GameList[GameCnt].gmove == PrVar[2]) ? PrVar[3] : 0;
 220     }
 221     else
 222 #endif
 223         SwagHt = 0;
 224
 225
 226     for (i = 0; i < MAXDEPTH; i++)
 227         PrVar[i] = killr0[i] = killr1[i] = killr2[i] = killr3[i] = 0;
 228
 229     /* set initial window for search */
 230
 231     if (flag.tsume)
 232     {
 233         alpha =  -(SCORE_LIMIT + 999);
 234         beta = SCORE_LIMIT + 999;
 235     }
 236     else
 237     {
 238         alpha = score - ((computer == white) ? BAwindow : WAwindow);
 239         beta  = score + ((computer == white) ? BBwindow : WBwindow);
 240     }
 241
 242     rpt = 0;
 243     TrPnt[1] = 0;
 244     root = &Tree[0];
 245
 246     sqking = PieceList[side][0];
 247     in_check = (board[sqking] == king)
 248         ? SqAttacked(sqking, side^1, &blockable)
 249         : false;
 250
 251     MoveList(side, 1, in_check, blockable);
 252
 253     for (i = TrPnt[1]; i < TrPnt[2]; i++)
 254     {
 255         if (!pick(i, TrPnt[2] - 1))
 256             break;
 257     }
 258
 259     /* Can I get a book move? */
 260
 261     if (flag.regularstart && Book)
 262     {
 263         flag.timeout = bookflag = OpeningBook(&hint);
 264
 265         if (TCflag)
 266             ResponseTime += ResponseTime;
 267     }
 268
 269     /* Zero stats for hash table. */
 270
 271     reminus = replus = 0;
 272     GenCnt = NodeCnt = ETnodes = EvalNodes = HashCnt
 273         = FHashAdd = HashAdd = FHashCnt = THashCol = HashCol = 0;
 274
 275     globalscore = plyscore = score;
 276     Jscore = 0;
 277     zwndw = 20;
 278
 279
 280     /********************* main loop ********************************/
 281
 282     Sdepth = (MaxSearchDepth < (MINDEPTH - 1))
 283         ? MaxSearchDepth
 284         : (MINDEPTH - 1);
 285
 286     while (!flag.timeout)
 287     {
 288         /* go down a level at a time */
 289         Sdepth++;
 290
 291 #ifdef NULLMOVE
 292         null = 0;
 293         PVari = 1;
 294 #endif
 295
 296         /* terminate search at DepthBeyond ply past goal depth */
 297         if (flag.tsume)
 298             DepthBeyond = Sdepth;
 299         else
 300 #if defined SLOW_CPU
 301             DepthBeyond = Sdepth + ((Sdepth == 1) ? 3 : 5);
 302 #else
 303         DepthBeyond = Sdepth + ((Sdepth == 1) ? 7 : 11);
 304 #endif
 305
 306 # ifdef QUIETBACKGROUND
 307         if (!background)
 308 #endif /* QUIETBACKGROUND */
 309             dsp->ShowDepth(' ');
 310
 311         /* search at this level returns score of PV */
 312         score = search(side, 1, Sdepth, alpha, beta, PrVar, &rpt);
 313
 314         /* save PV as killer */
 315         for (i = 1; i <= Sdepth; i++)
 316             killr0[i] = PrVar[i];
 317
 318         /* low search failure re-search with (-inf, score) limits  */
 319         if (score < alpha)
 320         {
 321             reminus++;
 322 #ifdef QUIETBACKGROUND
 323             if (!background)
 324 #endif /* QUIETBACKGROUND */
 325                 dsp->ShowDepth('-');
 326
 327             if (TCflag && TCcount < MAXTCCOUNTR)
 328             {
 329                 if (hard_time_limit)
 330                     ExtraTime += (MAXTCCOUNTR - TCcount) * TCleft;
 331                 else
 332                     ExtraTime += (8 * TCleft);
 333
 334                 TCcount = MAXTCCOUNTR - 1;
 335             }
 336
 337             score = search(side, 1, Sdepth, -(SCORE_LIMIT + 999),
 338                            (SCORE_LIMIT + 999), PrVar, &rpt);
 339         }
 340         /* high search failure re-search with (score, +inf) limits */
 341         else if (score > beta && !(root->flags & exact))
 342         {
 343             replus++;
 344 #ifdef QUIETBACKGROUND
 345             if (!background)
 346 #endif /* QUIETBACKGROUND */
 347                 dsp->ShowDepth('+');
 348
 349             score = search(side, 1, Sdepth, -(SCORE_LIMIT + 999),
 350                            (SCORE_LIMIT + 999), PrVar, &rpt);
 351         }
 352
 353         /**************** out of search ***********************************/
 354         CheckForTimeout(score, globalscore, Jscore, zwndw);
 355
 356         /************************ time control ****************************/
 357
 358         /* save PV as killer */
 359         for (i = 1; i <= Sdepth + 1; i++)
 360             killr0[i] = PrVar[i];
 361
 362         if (!flag.timeout)
 363             Tscore[0] = score;
 364
 365         /* if (!flag.timeout) */
 366         /*
 367           for (i = TrPnt[1] + 1; i < TrPnt[2]; i++)
 368           if (!pick (i, TrPnt[2] - 1))
 369           break;
 370         */
 371
 372         /* if done or nothing good to look at quit */
 373         if ((root->flags & exact) || (score < -SCORE_LIMIT))
 374             flag.timeout = true;
 375
 376         /* find the next best move put below root */
 377
 378         if (!flag.timeout)
 379         {
 380 #if !defined NODYNALPHA
 381             Jscore = (plyscore + score) >> 1;
 382 #endif
 383             zwndw = 20 + abs(Jscore / 12);
 384             plyscore = score;
 385
 386             /* recompute search window */
 387             beta = score + ((computer == white) ? BBwindow : WBwindow);
 388 #if !defined NODYNALPHA
 389             alpha = ((Jscore < score) ? Jscore : score)
 390                 - ((computer == white) ? BAwindow : WAwindow)
 391                 - zwndw;
 392 #else
 393             alpha = score - ((computer == white) ? BAwindow : WAwindow);
 394 #endif
 395         }
 396
 397 #ifdef QUIETBACKGROUND
 398         if (!background)
 399 #endif /* QUIETBACKGROUND */
 400             dsp->ShowResults(score, PrVar, '.');
 401     }
 402
 403     /********************** end of main loop ***************************/
 404
 405     /* background mode */
 406     if (background) /* originally: if (iop == BACKGROUND_MODE) */
 407         return;
 408
 409     if (rpt >= 3)
 410     {
 411         root->flags |= draw;
 412         DRAW = DRAW_REPETITION;
 413     }
 414     else
 415     {
 416         /*
 417          * If there are no moves and we're not in check (stalemate) then
 418          * it's mate in shogi (whereas it's a draw in chess).
 419          */
 420
 421         if (GameCnt == MAXMOVES)
 422         {
 423             root->flags |= draw;
 424             DRAW = DRAW_MAXMOVES;
 425         }
 426     }
 427
 428     /* not in book so set hint to guessed move for other side */
 429     if (!bookflag)
 430         hint = ((PrVar[1]) ? PrVar[2] : 0);
 431
 432     /* if not mate or draw make move and output it */
 433     if (((score > -(SCORE_LIMIT + 999))
 434          && (rpt <= 3)) || (root->flags & draw))
 435     {
 436         MakeMove(side, &Tree[0], &tempb, &tempc,
 437                  &tempsf, &tempst, &INCscore);
 438         algbr(root->f, root->t, (short) root->flags);
 439     }
 440     else
 441     {
 442         algbr(0, 0, 0);       /* Zero move string when mate. */
 443         root->score = score;  /* When mate, ignore distinctions!
 444                                * --SMC */
 445     }
 446
 447     g = &GameList[GameCnt];
 448
 449     if ((g->flags & capture) && (g->piece == king))
 450         flag.mate = flag.illegal = true;
 451
 452     /* If Time Control get the elapsed time */
 453     if (TCflag)
 454         ElapsedTime(COMPUTE_AND_INIT_MODE);
 455
 456     /* update time control info */
 457     dsp->OutputMove();
 458
 459     /* if mate set flag */
 460     if ((score == -(SCORE_LIMIT + 999) || score == (SCORE_LIMIT + 998)))
 461         flag.mate = true;
 462
 463     /* add move to game list */
 464     g->score = score;
 465     g->nodes = NodeCnt;
 466     g->time = (et +50)/100;
 467     /* g->time = TCcount; */
 468     g->depth = Sdepth;
 469
 470     /* update time control info */
 471     if (TCflag)
 472     {
 473         TimeControl.clock[side] -= (et + OperatorTime);
 474         timecomp[compptr] = (et + OperatorTime);
 475
 476         /* finished our required moves - setup the next set */
 477         --TimeControl.moves[side];
 478     }
 479
 480     /* check for end conditions */
 481     if ((root->flags & draw) /* && flag.bothsides */)
 482     {
 483         flag.mate = true;
 484     }
 485     else if (GameCnt == MAXMOVES)
 486     {
 487         flag.mate = true;
 488     }
 489     /* out of move store, you lose */
 490     else
 491     {
 492         /* switch to other side */
 493         player = xside;
 494     }
 495
 496     /* if mate clear hint */
 497     if (flag.mate)
 498         hint = 0;
 499
 500     Sdepth = 0;
 501 }
 502
 503
 504
 505 /*
 506  * Perform an alpha-beta search to determine the score for the current
 507  * board position.  If depth <= 0 only capturing moves and responses to
 508  * check are generated and searched, otherwise all moves are processed. The
 509  * search depth is modified for check evasions, certain re-captures and
 510  * threats.  Extensions may continue for up to 11 ply beyond the nominal
 511  * search depth.
 512  */
 513
 514 int
 515 search(short side,
 516        short ply,
 517        short depth,
 518        short alpha,
 519        short beta,
 520        unsigned short *bstline,
 521        short *rpt)
 522 {
 523     short j, pnt;
 524     short tempb, tempc, tempsf, tempst;
 525     short xside, pbst, score, rcnt, in_check, blockable;
 526     unsigned short mv, nxtline[MAXDEPTH];
 527     struct leaf  *node, tmp;
 528     short best = -(SCORE_LIMIT + 3000);
 529     short bestwidth = 0;
 530     short mustcut;
 531
 532 #ifdef NULLMOVE
 533     short PVsave;
 534     short PVarisave;
 535 #endif
 536
 537     NodeCnt++;
 538
 539     /* look every ZNODE nodes for a timeout */
 540 #ifdef NULLMOVE
 541     if (!null)
 542     {
 543 #endif
 544         if (NodeCnt > ETnodes)
 545         {
 546             ElapsedTime(COMPUTE_MODE);
 547
 548             if (flag.back)
 549             {
 550                 flag.back = false;
 551                 flag.timeout = true;
 552                 flag.musttimeout = false;
 553             }
 554             else if (TCflag || MaxResponseTime)
 555             {
 556                 if ((et >= (ResponseTime + ExtraTime))
 557                     && (Sdepth > MINDEPTH))
 558                 {
 559                     /* try to extend to finish ply */
 560                     if (flag.back || (TCflag && TCcount < MAXTCCOUNTX))
 561                     {
 562                         flag.back = false;
 563                         flag.musttimeout = true;
 564                         TCcount++;
 565                         ExtraTime += TCleft;
 566                     }
 567                     else
 568                     {
 569                         flag.back = false;
 570                         flag.timeout = true;
 571                         flag.musttimeout = false;
 572                     }
 573                 }
 574             }
 575             else if (flag.back)
 576             {
 577                 flag.back = false;
 578                 flag.timeout = true;
 579                 flag.musttimeout = false;
 580             }
 581
 582 #ifdef QUIETBACKGROUND
 583             if (!background)
 584 #endif
 585                 dsp->ShowResponseTime();
 586         }
 587         else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
 588         {
 589             flag.timeout = true;
 590             flag.musttimeout = false;
 591         }
 592 #ifdef NULLMOVE
 593     }
 594 #endif
 595
 596     xside = side ^ 1;
 597     score = evaluate(side, ply, alpha, beta,
 598                      INCscore, &in_check, &blockable);
 599
 600     /*
 601      * check for possible repitition if so call repitition - rpt is
 602      * repeat count
 603      */
 604
 605     if ((ply <= Sdepth + 3) && rpthash[side][hashkey & 0xFF] > 0)
 606     {
 607         *rpt = repetition();
 608
 609         /*
 610          * repeat position >3 don't need to return score it's taken
 611          * care of above
 612          */
 613
 614         if (*rpt == 1)
 615         {
 616             score /= 3;
 617             score *= 2;
 618         }
 619         else if (*rpt == 2)
 620             score /= 2;
 621     }
 622     else
 623     {
 624         *rpt = 0;
 625     }
 626
 627     /* score > SCORE_LIMIT its a draw or mate */
 628     if (score > SCORE_LIMIT)
 629     {
 630         bstline[ply] = 0;
 631         return score;
 632     }
 633
 634     /* Do we need to add depth because of special conditions */
 635     /* if in check or in capture sequence search deeper */
 636
 637     /***************** depth extensions *****************/
 638
 639     if (depth > 0)
 640     {
 641         /* Allow opponent a chance to check again */
 642         if (in_check)
 643         {
 644             if (depth < 2)
 645                 depth = 2;
 646         }
 647         else if (flag.rcptr
 648                  && (score > alpha) && (score < beta)
 649                  && (ply > 2)
 650                  && CptrFlag[ply - 1] && CptrFlag[ply - 2])
 651         {
 652             if (hard_time_limit)
 653             {
 654                 if (!flag.timeout)
 655                     ++depth;
 656             }
 657             else
 658             {
 659                 ++depth;
 660             }
 661
 662         }
 663     }
 664     else
 665     {
 666         short timeout = 0;
 667
 668         if (hard_time_limit)
 669             timeout = flag.timeout;
 670
 671         if ((score >= alpha)
 672             && (in_check
 673                 || ((!timeout && (hung[side] > 1))
 674                     && (ply == Sdepth + 1))))
 675         {
 676             depth = 1;
 677         }
 678         else if ((score <= beta)
 679                  && (((ply < Sdepth + 4) && (ply > 4))
 680                      && ChkFlag[ply - 2]
 681                      && ChkFlag[ply - 4]
 682                      && (ChkFlag[ply - 2] != ChkFlag[ply - 4])))
 683         {
 684             depth = 1;
 685         }
 686     }
 687
 688     /***************************************************/
 689     /* try the local transition table if it's there */
 690
 691 #if ttblsz
 692     if (/* depth > 0 && */ flag.hash && ply > 1)
 693     {
 694         if (use_ttable
 695             && ProbeTTable(side, depth, ply, &alpha, &beta, &score) == true)
 696         {
 697             bstline[ply] = PV;
 698             bstline[ply + 1] = 0;
 699
 700             if (beta == -((SCORE_LIMIT + 1000) * 2))
 701                 return score;
 702
 703             if (alpha > beta)
 704                 return alpha;
 705         }
 706
 707 #ifdef HASHFILE
 708         /* ok try the transition file if its there */
 709         else if (hashfile
 710                  && (depth > HashDepth)
 711                  && (GameCnt < HashMoveLimit)
 712                  && (ProbeFTable(side, depth, ply, &alpha, &beta, &score)
 713                      == true))
 714         {
 715             PutInTTable(side, score, depth, ply, beta, PV);
 716             bstline[ply] = PV;
 717             bstline[ply + 1] = 0;
 718
 719             if (beta == -((SCORE_LIMIT + 1000) * 2))
 720                 return score;
 721
 722             if (alpha > beta)
 723             {
 724                 return alpha;
 725             }
 726         }
 727 #endif /* HASHFILE */
 728     }
 729 #endif /* ttblsz */
 730
 731     if (TrPnt[ply] > (TREE - 300))
 732         mustcut = true;
 733     else
 734         mustcut = false;
 735
 736     /*
 737      * If more then DepthBeyond ply past goal depth or at goal depth and
 738      * score > beta quit - means we are out of the window.
 739      */
 740
 741     if (mustcut || (ply > DepthBeyond) || ((depth < 1) && (score > beta)))
 742         return score;
 743
 744     /*
 745      * If below first ply and not at goal depth generate all moves else
 746      * only capture moves.
 747      */
 748
 749     if (ply > 1)
 750     {
 751         if ((depth > 0) || (ply < (SDEPTHLIM))
 752             || (background && (ply < Sdepth + 2)))
 753             MoveList(side, ply, in_check, blockable);
 754         else
 755             CaptureList(side, ply, in_check, blockable);
 756     }
 757
 758     /* no moves return what we have */
 759
 760     /*
 761      * normally a search will continue til past goal and no more capture
 762      * moves exist
 763      */
 764
 765     /* unless it hits DepthBeyond */
 766     if (TrPnt[ply] == TrPnt[ply + 1])
 767         return score;
 768
 769     /* if not at goal set best = -inf else current score */
 770     best = (depth > 0) ? -(SCORE_LIMIT + 3000) : score;
 771
 772 #ifdef NULLMOVE
 773
 774     PVarisave = PVari;
 775
 776     /* CHECKME: is the & really an && here? */
 777     if (!null  &&                        /* no previous null-move */
 778         !PVari &&                        /* no null-move during the PV */
 779         (ply > 2) &                      /* not at ply 1 */
 780         (ply <= Sdepth) &&
 781         (depth > 3) &&
 782         !in_check)                       /* no check */
 783         /* enough material such that zugzwang is unlikely
 784          * but who knows which value is suitable? */
 785     {
 786         /*
 787            OK, we make a null move, i.e.  this means we have nothing to do
 788            but we have to keep the some arrays up to date otherwise gnushogi
 789            gets confused.  Maybe somebody knows exactly which information is
 790            important and which isn't.
 791
 792            Another idea is that we try the null-move first and generate the
 793            moves later.  This may save time but we have to take care that
 794            PV and other variables contain the right value so that the move
 795            ordering works right.
 796         */
 797
 798         struct GameRec  *g;
 799
 800         nxtline[ply + 1] = 0;
 801         CptrFlag[ply] = 0;
 802         TesujiFlag[ply] = 0;
 803         Tscore[ply] = score;
 804         PVsave = PV;
 805         PV = 0;
 806         null = 1;
 807         g = &GameList[++GameCnt];
 808         g->hashkey = hashkey;
 809         g->hashbd = hashbd;
 810         FROMsquare = TOsquare = -1;
 811         g->Game50 = Game50;
 812         g->gmove = -1;
 813         g->flags = 0;
 814         g->piece = 0;
 815         g->color = neutral;
 816
 817         best = -search(xside, ply + 1, depth - 2,
 818                        -beta - 1, -beta, nxtline, &rcnt);
 819         null = 0;
 820         PV = PVsave;
 821         GameCnt--;
 822
 823         if (best < alpha)
 824         {
 825             best = -(SCORE_LIMIT + 3000);
 826         }
 827         else if (best > beta)
 828         {
 829             return best;
 830         }
 831         else
 832         {
 833             best = -(SCORE_LIMIT + 3000);
 834         }
 835     }
 836 #endif
 837
 838     /* if best so far is better than alpha set alpha to best */
 839     if (best > alpha)
 840         alpha = best;
 841
 842     /********************** main loop ****************************/
 843
 844     /* look at each move until no more or beta cutoff */
 845     for (pnt = pbst = TrPnt[ply];
 846          (pnt < TrPnt[ply + 1]) && (best <= beta);
 847          pnt++)
 848     {
 849         /* find the most interesting looking of the remaining moves */
 850         if (ply > 1)
 851             pick(pnt, TrPnt[ply + 1] - 1);
 852
 853 #ifdef NULLMOVE
 854         PVari = PVarisave && (pnt == TrPnt[ply]);  /* Is this the PV? */
 855 #endif
 856
 857         node = &Tree[pnt];
 858
 859         /* is this a forbidden move */
 860         if (/* ply == 1 && */ node->score <= DONTUSE)
 861             continue;
 862
 863         nxtline[ply + 1] = 0;
 864
 865         /* if at top level */
 866         if (ply == 1)
 867         {
 868 /* at the top update search status */
 869             if (flag.post)
 870             {
 871 #ifdef QUIETBACKGROUND
 872                 if (!background)
 873 #endif /* QUIETBACKGROUND */
 874                     dsp->ShowCurrentMove(pnt, node->f, node->t);
 875             }
 876             movesLeft = TrPnt[2] - pnt; /* to report with XBoard periodic updates */
 877             currentMove = node->f << 8 | node->t;
 878         }
 879
 880         if (!(node->flags & exact))
 881         {
 882             /* make the move and go deeper */
 883
 884             MakeMove(side, node, &tempb, &tempc, &tempsf,
 885                      &tempst, &INCscore);
 886             CptrFlag[ply] = ((node->flags & capture) != 0);
 887             TesujiFlag[ply] = (node->flags & tesuji)
 888                 && (node->flags & dropmask);
 889             Tscore[ply] = node->score;
 890             PV = node->reply;
 891
 892             node->score = -search(xside, ply + 1,
 893                                   (depth > 0) ? (depth - 1) : 0,
 894                                   -beta, -alpha,
 895                                   nxtline, &rcnt);
 896
 897             /*
 898              * if(!flag.timeout)
 899              *     node->score = score;
 900              */
 901
 902             node->width = ((ply % 2) == 1)
 903                 ? (TrPnt[ply + 2] - TrPnt[ply + 1])
 904                 : 0;
 905
 906             if ((node->score > SCORE_LIMIT) || (node->score < -SCORE_LIMIT) )
 907                 node->flags |= exact;
 908             else if (rcnt == 1)
 909                 node->score /= 2;
 910
 911             if (((rcnt >= 3)
 912                  || ((node->score == (SCORE_LIMIT + 999) - ply)
 913                      && !ChkFlag[ply])))
 914             {
 915                 node->flags |= (draw | exact);
 916                 DRAW = DRAW_JUSTDRAW;
 917                 node->score = ((side == computer) ? contempt : -contempt);
 918             }
 919
 920             node->reply = nxtline[ply + 1];
 921
 922             /* reset to try next move */
 923             UnmakeMove(side, node, &tempb, &tempc, &tempsf, &tempst);
 924         }
 925
 926         /* if best move so far */
 927         /* CHECKME: flag.timeout isn't valid if no hard time limit */
 928         if (!flag.timeout
 929             && ((node->score > best)
 930                 || ((node->score == best) && (node->width > bestwidth))))
 931         {
 932             /*
 933              * All things being equal pick the denser part of the
 934              * tree.
 935              */
 936             bestwidth = node->width;
 937
 938             /*
 939              * If not at goal depth and better than alpha and not
 940              * an exact score increment by depth.
 941              */
 942
 943             if ((depth > 0) && (node->score > alpha)
 944                 && !(node->flags & exact))
 945             {
 946                 node->score += depth;
 947             }
 948
 949             best = node->score;
 950             pbst = pnt;
 951
 952             if (best > alpha)
 953                 alpha = best;
 954
 955             /* update best line */
 956             for (j = ply + 1; nxtline[j] > 0; j++)
 957                 bstline[j] = nxtline[j];
 958
 959             bstline[j] = 0;
 960             bstline[ply] = (node->f << 8) | node->t;
 961
 962             /* if at the top */
 963             if (ply == 1)
 964             {
 965                 /*
 966                  * If it's better than the root score make it the root.
 967                  */
 968                 if ((best > root->score)
 969                     || ((best == root->score)
 970                         && (bestwidth > root->width)))
 971                 {
 972                     tmp = Tree[pnt];
 973
 974                     for (j = pnt - 1; j >= 0; j--)
 975                         Tree[j + 1] = Tree[j];
 976
 977                     Tree[0] = tmp;
 978                     pbst = 0;
 979                 }
 980
 981 #ifdef QUIETBACKGROUND
 982                 if (!background)
 983                 {
 984 #endif /* QUIETBACKGROUND */
 985                     if (Sdepth > 2)
 986                     {
 987                         if (best > beta)
 988                         {
 989                             dsp->ShowResults(best, bstline, '+');
 990                         }
 991                         else if (best < alpha)
 992                         {
 993                             dsp->ShowResults(best, bstline, '-');
 994                         }
 995                         else
 996                         {
 997                             dsp->ShowResults(best, bstline, '&');
 998                         }
 999                     }
1000 #ifdef QUIETBACKGROUND
1001                 }
1002 #endif
1003             }
1004         }
1005
1006         if (flag.timeout)
1007             return Tscore[ply - 1];
1008     }
1009
1010     /******************************************************/
1011
1012     node = &Tree[pbst];
1013     mv = (node->f << 8) | node->t;
1014
1015 #ifdef NULLMOVE
1016     PVari = PVarisave;
1017 #endif
1018
1019     /*
1020      * We have a move so put it in local table - if it's already there
1021      * done else if not there or needs to be updated also put it in
1022      * hashfile
1023      */
1024
1025 #if ttblsz
1026     if (flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
1027     {
1028 #  ifdef HASHFILE /* MCV: warning: this confuses the formatter. */
1029         if (use_ttable
1030             && PutInTTable(side, best, depth, ply, beta, mv)
1031             && hashfile
1032             && (depth > HashDepth)
1033             && (GameCnt < HashMoveLimit))
1034 #  else
1035         if (use_ttable
1036             && PutInTTable(side, best, depth, ply, beta, mv))
1037 #  endif
1038         {
1039             PutInFTable(side, best, depth, ply,
1040                         alpha, beta, node->f, node->t);
1041         }
1042     }
1043 #endif /* ttblsz */
1044
1045     if (depth > 0)
1046     {
1047 #if defined HISTORY
1048         unsigned short h, x;
1049         h = mv;
1050
1051         if (history[x = hindex(side, h)] < HISTORYLIM)
1052             history[x] += (unsigned short) 1 << depth;
1053 #endif
1054
1055         if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
1056         {
1057             if (best <= beta)
1058             {
1059                 killr3[ply] = mv;
1060             }
1061             else if (mv != killr1[ply])
1062             {
1063                 killr2[ply] = killr1[ply];
1064                 killr1[ply] = mv;
1065             }
1066         }
1067
1068         killr0[ply] = ((best > SCORE_LIMIT) ? mv : 0);
1069     }
1070
1071     return best;
1072 }
1073
1074
1075
1076 /*
1077  * Update the PieceList and Pindex arrays when a piece is captured or when a
1078  * capture is unmade.
1079  */
1080
1081 void
1082 UpdatePieceList(short side, short sq, UpdatePieceList_mode iop)
1083 {
1084     short i;
1085
1086     if (iop == REMOVE_PIECE)
1087     {
1088         PieceCnt[side]--;
1089
1090         for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
1091         {
1092             PieceList[side][i] = PieceList[side][i + 1];
1093             Pindex[PieceList[side][i]] = i;
1094         }
1095     }
1096     else if (board[sq] == king)
1097     {
1098         /* king must have index 0 */
1099         for (i = PieceCnt[side]; i >= 0; i--)
1100         {
1101             PieceList[side][i + 1] = PieceList[side][i];
1102             Pindex[PieceList[side][i + 1]] = i + 1;
1103         }
1104
1105         PieceCnt[side]++;
1106         PieceList[side][0] = sq;
1107         Pindex[sq] = 0;
1108     }
1109     else
1110     {
1111         PieceCnt[side]++;
1112         PieceList[side][PieceCnt[side]] = sq;
1113         Pindex[sq] = PieceCnt[side];
1114     }
1115 }
1116
1117
1118
1119 /* Make or Unmake drop move. */
1120
1121 static void
1122 drop(short side, short piece, short t, short iop)
1123 {
1124     if (iop == 1)
1125     {
1126         short n;
1127         board[t] = piece;
1128         color[t] = side;
1129
1130 #if !defined SAVE_SVALUE
1131         svalue[t] = 0;
1132 #endif
1133
1134         n = Captured[side][piece]--;
1135
1136         UpdateDropHashbd(side, piece, n);
1137         UpdateHashbd(side, piece, -1, t);
1138         UpdatePieceList(side, t, ADD_PIECE);
1139
1140         if (piece == pawn)
1141         {
1142             ++PawnCnt[side][column(t)];
1143         }
1144
1145         Mvboard[t]++;
1146         HasPiece[side][piece]++;
1147     }
1148     else
1149     {
1150         short n;
1151         board[t] = no_piece;
1152         color[t] = neutral;
1153         n = ++Captured[side][piece];
1154
1155         UpdateDropHashbd(side, piece, n);
1156         UpdateHashbd(side, piece, -1, t);
1157         UpdatePieceList(side, t, REMOVE_PIECE);
1158
1159         if (piece == pawn)
1160             --PawnCnt[side][column(t)];
1161
1162         Mvboard[t]--;
1163         HasPiece[side][piece]--;
1164     }
1165 }
1166
1167
1168 #ifdef HASHKEYTEST
1169 int
1170 CheckHashKey()
1171 {
1172     unsigned long chashkey, chashbd;
1173     short side, sq;
1174     chashbd = chashkey = 0;
1175
1176     for (sq = 0; sq < NO_SQUARES; sq++)
1177     {
1178         if (color[sq] != neutral)
1179         {
1180             chashbd ^= (*hashcode)[color[sq]][board[sq]][sq].bd;
1181             chashkey ^= (*hashcode)[color[sq]][board[sq]][sq].key;
1182         }
1183
1184         /* hashcodes for initial board are 0 ! */
1185         if (Stcolor[sq] != neutral)
1186         {
1187             chashbd ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].bd;
1188             chashkey ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].key;
1189         }
1190     }
1191
1192     for (side = 0; side <= 1; side++)
1193     {
1194         short piece;
1195
1196         for (piece = 0; piece < NO_PIECES; piece++)
1197         {
1198             short n = Captured[side][piece];
1199
1200             if (n > 0)
1201             {
1202                 short i;
1203
1204                 for (i = 1; i <= n; i++)
1205                 {
1206                     chashbd ^= (*drop_hashcode)[side][piece][i].bd;
1207                     chashkey ^= (*drop_hashcode)[side][piece][i].key;
1208                 }
1209             }
1210         }
1211     }
1212
1213     if (chashbd != hashbd)
1214         printf("chashbd %lu != hashbd %lu\n", chashbd, hashbd);
1215
1216     if (chashkey != hashkey)
1217         printf("chashkey %lu != hashkey %lu\n", chashkey, hashkey);
1218
1219     if (chashbd != hashbd || chashkey != hashkey)
1220         return 1;
1221
1222     return 0;
1223 }
1224 #endif
1225
1226
1227
1228
1229 /*
1230  * Update Arrays board[], color[], and Pindex[] to reflect the new board
1231  * position obtained after making the move pointed to by node. Also update
1232  * miscellaneous stuff that changes when a move is made.
1233  */
1234
1235 void
1236 MakeMove(short side,
1237          struct leaf  *node,
1238          short *tempb,  /* piece at to square */
1239          short *tempc,  /* color of to square */
1240          short *tempsf, /* static value of piece on from */
1241          short *tempst, /* static value of piece on to */
1242          short *INCscore)   /* score increment */
1243 {
1244     short f, t, xside;
1245     struct GameRec  *g;
1246     short fromb, fromc;
1247
1248     xside = side ^ 1;
1249     g = &GameList[++GameCnt];
1250     g->hashkey = hashkey;
1251     g->hashbd = hashbd;
1252     FROMsquare = f = node->f;
1253     TOsquare = t = (node->t & 0x7f);
1254     *INCscore = (short)node->INCscore;
1255     g->Game50 = Game50;
1256     g->gmove = (f << 8) | node->t;
1257     g->flags = node->flags;
1258
1259 #ifdef HASHKEYTEST
1260     if (CheckHashKey())
1261     {
1262         short i;
1263         algbr(f, t, node->flags);
1264         printf("error before MakeMove: %s\n", mvstr[0]);
1265         UpdateDisplay(0, 0, 1, 0);
1266
1267         for (i = 1; i <= GameCnt; i++)
1268         {
1269             movealgbr(GameList[i].gmove, mvstr[0]);
1270             printf("%d: %s\n", i, mvstr[0]);
1271         }
1272
1273         exit(1);
1274     }
1275 #endif
1276
1277     rpthash[side][hashkey & 0xFF]++, ISZERO++;
1278
1279     if (f > NO_SQUARES)
1280     {
1281         g->fpiece = (node->flags & pmask);
1282         g->piece = *tempb = no_piece;
1283         g->color = *tempc = neutral;
1284
1285 #if !defined SAVE_SVALUE
1286         *tempsf = 0;
1287         *tempst = svalue[t];
1288 #endif
1289
1290         (void)drop(side, g->fpiece, t, 1);
1291     }
1292     else
1293     {
1294 #if !defined SAVE_SVALUE
1295         *tempsf = svalue[f];
1296         *tempst = svalue[t];
1297 #endif
1298
1299         g->fpiece = board[f];
1300         g->piece = *tempb = board[t];
1301         g->color = *tempc = color[t];
1302         fromb = board[f];
1303         fromc = color[f];
1304
1305         if (*tempc != neutral)
1306         {
1307             /* Capture a piece */
1308             UpdatePieceList(*tempc, t, REMOVE_PIECE);
1309
1310             /* if capture decrement pawn count */
1311             if (*tempb == pawn)
1312                 --PawnCnt[*tempc][column(t)];
1313
1314             mtl[xside] -= (*value)[stage][*tempb];
1315             HasPiece[xside][*tempb]--;
1316
1317             {
1318                 short n, upiece = unpromoted[*tempb];
1319
1320                 /* add "upiece" captured by "side" */
1321                 n = ++Captured[side][upiece];
1322
1323                 UpdateDropHashbd(side, upiece, n);
1324                 mtl[side] += (*value)[stage][upiece];
1325             }
1326
1327             /* remove "*tempb" of "xside" from board[t] */
1328             UpdateHashbd(xside, *tempb, -1, t);
1329
1330 #if !defined SAVE_SVALUE
1331             *INCscore += *tempst; /* add value of catched piece
1332                                    * to own score */
1333 #endif
1334
1335             Mvboard[t]++;
1336         }
1337
1338         color[t] = fromc;
1339
1340 #if !defined SAVE_SVALUE
1341         svalue[t] = svalue[f];
1342         svalue[f] = 0;
1343 #endif
1344
1345         Pindex[t] = Pindex[f];
1346         PieceList[side][Pindex[t]] = t;
1347         color[f] = neutral;
1348         board[f] = no_piece;
1349
1350         if (node->flags & promote)
1351         {
1352             short tob;
1353
1354             board[t] = tob = promoted[fromb];
1355
1356             /* remove unpromoted piece from board[f] */
1357             UpdateHashbd(side, fromb, f, -1);
1358
1359             /* add promoted piece to board[t] */
1360             UpdateHashbd(side, tob, -1, t);
1361             mtl[side] += value[stage][tob] - value[stage][fromb];
1362
1363             if (fromb == pawn)
1364                 --PawnCnt[side][column(f)];
1365
1366             HasPiece[side][fromb]--;
1367             HasPiece[side][tob]++;
1368
1369 #if !defined SAVE_SVALUE
1370             *INCscore -= *tempsf;
1371 #endif
1372         }
1373         else
1374         {
1375             board[t] = fromb;
1376             /* remove piece from board[f] and add it to board[t] */
1377             UpdateHashbd(side, fromb, f, t);
1378         }
1379
1380         Mvboard[f]++;
1381     }
1382
1383 #ifdef HASHKEYTEST
1384     algbr(f, t, node->flags);
1385
1386     if (CheckHashKey())
1387     {
1388         printf("error in MakeMove: %s\n", mvstr[0]);
1389         exit(1);
1390     }
1391 #endif
1392 }
1393
1394
1395
1396
1397 /*
1398  * Take back a move.
1399  */
1400
1401 void
1402 UnmakeMove(short side,
1403            struct leaf  *node,
1404            short *tempb,
1405            short *tempc,
1406            short *tempsf,
1407            short *tempst)
1408 {
1409     short f, t, xside;
1410
1411     xside = side ^ 1;
1412     f = node->f;
1413     t = node->t & 0x7f;
1414     Game50 = GameList[GameCnt].Game50;
1415
1416     if (node->flags & dropmask)
1417     {
1418         (void)drop(side, (node->flags & pmask), t, 2);
1419
1420 #if !defined SAVE_SVALUE
1421         svalue[t] = *tempst;
1422 #endif
1423     }
1424     else
1425     {
1426         short tob, fromb;
1427
1428         color[f] = color[t];
1429         board[f] = tob = fromb = board[t];
1430
1431 #if !defined SAVE_SVALUE
1432         svalue[f] = *tempsf;
1433 #endif
1434
1435         Pindex[f] = Pindex[t];
1436         PieceList[side][Pindex[f]] = f;
1437         color[t] = *tempc;
1438         board[t] = *tempb;
1439
1440 #if !defined SAVE_SVALUE
1441         svalue[t] = *tempst;
1442 #endif
1443
1444         /* Undo move */
1445         if (node->flags & promote)
1446         {
1447             board[f] = fromb = unpromoted[tob];
1448             mtl[side] += value[stage][fromb] - value[stage][tob];
1449
1450             if (fromb == pawn)
1451                 ++PawnCnt[side][column(f)];
1452
1453             HasPiece[side][fromb]++;
1454             HasPiece[side][tob]--;
1455
1456             /* add unpromoted piece to board[f] */
1457             UpdateHashbd(side, fromb, f, -1);
1458
1459             /* remove promoted piece from board[t] */
1460             UpdateHashbd(side, tob, -1, t);
1461         }
1462         else
1463         {
1464             if (fromb == pawn)
1465             {
1466                 --PawnCnt[side][column(t)];
1467                 ++PawnCnt[side][column(f)];
1468             };
1469
1470             /* remove piece from board[t] and add it to board[f] */
1471             UpdateHashbd(side, fromb, f, t);
1472         }
1473
1474         /* Undo capture */
1475         if (*tempc != neutral)
1476         {
1477             short n, upiece = unpromoted[*tempb];
1478
1479             UpdatePieceList(*tempc, t, ADD_PIECE);
1480
1481             if (*tempb == pawn)
1482                 ++PawnCnt[*tempc][column(t)];
1483
1484             mtl[xside] += (*value)[stage][*tempb];
1485             HasPiece[xside][*tempb]++;
1486             mtl[side] -= (*value)[stage][upiece];
1487
1488             /* remove "upiece" captured by "side" */
1489             n = Captured[side][upiece]--;
1490
1491             UpdateDropHashbd(side, upiece, n);
1492
1493             /* replace captured piece on board[t] */
1494             UpdateHashbd(xside, *tempb, -1, t);
1495             Mvboard[t]--;
1496         }
1497
1498         Mvboard[f]--;
1499     }
1500
1501     GameCnt--;
1502     rpthash[side][hashkey & 0xFF]--, ISZERO--;
1503
1504 #ifdef HASHKEYTEST
1505     algbr(f, t, node->flags);
1506
1507     if (CheckHashKey())
1508     {
1509         printf("error in UnmakeMove: %s\n", mvstr[0]);
1510         exit(1);
1511     }
1512 #endif
1513 }
1514
1515
1516
1517 /*
1518  * Scan thru the board seeing what's on each square. If a piece is found,
1519  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
1520  * determine the material for each side and set the hashkey and hashbd
1521  * variables to represent the current board position. Array
1522  * PieceList[side][indx] contains the location of all the pieces of either
1523  * side. Array Pindex[sq] contains the indx into PieceList for a given
1524  * square.
1525  */
1526
1527 void
1528 InitializeStats(void)
1529 {
1530     short i, sq;
1531
1532     for (i = 0; i < NO_COLS; i++)
1533         PawnCnt[black][i] = PawnCnt[white][i] = 0;
1534
1535     mtl[black] = mtl[white] = 0;
1536     PieceCnt[black] = PieceCnt[white] = 0;
1537     hashbd = hashkey = 0;
1538
1539     for (sq = 0; sq < NO_SQUARES; sq++)
1540     {
1541         if (color[sq] != neutral)
1542         {
1543             mtl[color[sq]] += (*value)[stage][board[sq]];
1544
1545             if (board[sq] == pawn)
1546                 ++PawnCnt[color[sq]][column(sq)];
1547
1548             Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
1549             PieceList[color[sq]][Pindex[sq]] = sq;
1550             UpdateHashbd(color[sq], board[sq], sq, -1);
1551         }
1552
1553         /* hashcodes for initial board are 0 ! */
1554         if (Stcolor[sq] != neutral)
1555             UpdateHashbd(Stcolor[sq], Stboard[sq], sq, -1);
1556     }
1557
1558     {
1559         short side;
1560
1561         for (side = 0; side <= 1; side++)
1562         {
1563             short piece;
1564
1565             for (piece = 0; piece < NO_PIECES; piece++)
1566             {
1567                 short n = Captured[side][piece];
1568
1569                 if (n > 0)
1570                 {
1571                     Captured[side][piece] = 0;
1572
1573                     for (i = 1; i <= n; i++)
1574                     {
1575                         ++Captured[side][piece];
1576                         UpdateDropHashbd(side, piece, i);
1577                         mtl[side] += (*value)[stage][piece];
1578                     }
1579                 }
1580             }
1581         }
1582     }
1583
1584 #ifdef HASHKEYTEST
1585     if (CheckHashKey())
1586     {
1587         printf("error in InitializeStats\n");
1588         exit(1);
1589     }
1590 #endif
1591 }