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     {
 455         ElapsedTime(COMPUTE_AND_INIT_MODE);
 456         if(xboard) /* In XBoard increment is added after move */
 457             TimeControl.clock[side] += TCadd;
 458     }
 459     /* update time control info */
 460     dsp->OutputMove();
 461
 462     /* if mate set flag */
 463     if ((score == -(SCORE_LIMIT + 999) || score == (SCORE_LIMIT + 998)))
 464         flag.mate = true;
 465
 466     /* add move to game list */
 467     g->score = score;
 468     g->nodes = NodeCnt;
 469     g->time = (et +50)/100;
 470     /* g->time = TCcount; */
 471     g->depth = Sdepth;
 472
 473     /* update time control info */
 474     if (TCflag)
 475     {
 476         TimeControl.clock[side] -= (et + OperatorTime);
 477         timecomp[compptr] = (et + OperatorTime);
 478
 479         /* finished our required moves - setup the next set */
 480         --TimeControl.moves[side];
 481     }
 482
 483     /* check for end conditions */
 484     if ((root->flags & draw) /* && flag.bothsides */)
 485     {
 486         flag.mate = true;
 487     }
 488     else if (GameCnt == MAXMOVES)
 489     {
 490         flag.mate = true;
 491     }
 492     /* out of move store, you lose */
 493     else
 494     {
 495         /* switch to other side */
 496         player = xside;
 497     }
 498
 499     /* if mate clear hint */
 500     if (flag.mate)
 501         hint = 0;
 502
 503     Sdepth = 0;
 504 }
 505
 506
 507
 508 /*
 509  * Perform an alpha-beta search to determine the score for the current
 510  * board position.  If depth <= 0 only capturing moves and responses to
 511  * check are generated and searched, otherwise all moves are processed. The
 512  * search depth is modified for check evasions, certain re-captures and
 513  * threats.  Extensions may continue for up to 11 ply beyond the nominal
 514  * search depth.
 515  */
 516
 517 int
 518 search(short side,
 519        short ply,
 520        short depth,
 521        short alpha,
 522        short beta,
 523        unsigned short *bstline,
 524        short *rpt)
 525 {
 526     short j, pnt;
 527     short tempb, tempc, tempsf, tempst;
 528     short xside, pbst, score, rcnt, in_check, blockable;
 529     unsigned short mv, nxtline[MAXDEPTH];
 530     struct leaf  *node, tmp;
 531     short best = -(SCORE_LIMIT + 3000);
 532     short bestwidth = 0;
 533     short mustcut;
 534
 535 #ifdef NULLMOVE
 536     short PVsave;
 537     short PVarisave;
 538 #endif
 539
 540     NodeCnt++;
 541
 542     /* look every ZNODE nodes for a timeout */
 543 #ifdef NULLMOVE
 544     if (!null)
 545     {
 546 #endif
 547         if (NodeCnt > ETnodes)
 548         {
 549             ElapsedTime(COMPUTE_MODE);
 550
 551             if (flag.back)
 552             {
 553                 flag.back = false;
 554                 flag.timeout = true;
 555                 flag.musttimeout = false;
 556             }
 557             else if (TCflag || MaxResponseTime)
 558             {
 559                 if ((et >= (ResponseTime + ExtraTime))
 560                     && (Sdepth > MINDEPTH))
 561                 {
 562                     /* try to extend to finish ply */
 563                     if (flag.back || (TCflag && TCcount < MAXTCCOUNTX))
 564                     {
 565                         flag.back = false;
 566                         flag.musttimeout = true;
 567                         TCcount++;
 568                         ExtraTime += TCleft;
 569                     }
 570                     else
 571                     {
 572                         flag.back = false;
 573                         flag.timeout = true;
 574                         flag.musttimeout = false;
 575                     }
 576                 }
 577             }
 578             else if (flag.back)
 579             {
 580                 flag.back = false;
 581                 flag.timeout = true;
 582                 flag.musttimeout = false;
 583             }
 584
 585 #ifdef QUIETBACKGROUND
 586             if (!background)
 587 #endif
 588                 dsp->ShowResponseTime();
 589         }
 590         else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
 591         {
 592             flag.timeout = true;
 593             flag.musttimeout = false;
 594         }
 595 #ifdef NULLMOVE
 596     }
 597 #endif
 598
 599     xside = side ^ 1;
 600     score = evaluate(side, ply, alpha, beta,
 601                      INCscore, &in_check, &blockable);
 602
 603     /*
 604      * check for possible repitition if so call repitition - rpt is
 605      * repeat count
 606      */
 607
 608     if ((ply <= Sdepth + 3) && rpthash[side][hashkey & 0xFF] > 0)
 609     {
 610         *rpt = repetition();
 611
 612         /*
 613          * repeat position >3 don't need to return score it's taken
 614          * care of above
 615          */
 616
 617         if (*rpt == 1)
 618         {
 619             score /= 3;
 620             score *= 2;
 621         }
 622         else if (*rpt == 2)
 623             score /= 2;
 624     }
 625     else
 626     {
 627         *rpt = 0;
 628     }
 629
 630     /* score > SCORE_LIMIT its a draw or mate */
 631     if (score > SCORE_LIMIT)
 632     {
 633         bstline[ply] = 0;
 634         return score;
 635     }
 636
 637     /* Do we need to add depth because of special conditions */
 638     /* if in check or in capture sequence search deeper */
 639
 640     /***************** depth extensions *****************/
 641
 642     if (depth > 0)
 643     {
 644         /* Allow opponent a chance to check again */
 645         if (in_check)
 646         {
 647             if (depth < 2)
 648                 depth = 2;
 649         }
 650         else if (flag.rcptr
 651                  && (score > alpha) && (score < beta)
 652                  && (ply > 2)
 653                  && CptrFlag[ply - 1] && CptrFlag[ply - 2])
 654         {
 655             if (hard_time_limit)
 656             {
 657                 if (!flag.timeout)
 658                     ++depth;
 659             }
 660             else
 661             {
 662                 ++depth;
 663             }
 664
 665         }
 666     }
 667     else
 668     {
 669         short timeout = 0;
 670
 671         if (hard_time_limit)
 672             timeout = flag.timeout;
 673
 674         if ((score >= alpha)
 675             && (in_check
 676                 || ((!timeout && (hung[side] > 1))
 677                     && (ply == Sdepth + 1))))
 678         {
 679             depth = 1;
 680         }
 681         else if ((score <= beta)
 682                  && (((ply < Sdepth + 4) && (ply > 4))
 683                      && ChkFlag[ply - 2]
 684                      && ChkFlag[ply - 4]
 685                      && (ChkFlag[ply - 2] != ChkFlag[ply - 4])))
 686         {
 687             depth = 1;
 688         }
 689     }
 690
 691     /***************************************************/
 692     /* try the local transition table if it's there */
 693
 694 #if ttblsz
 695     if (/* depth > 0 && */ flag.hash && ply > 1)
 696     {
 697         if (use_ttable
 698             && ProbeTTable(side, depth, ply, &alpha, &beta, &score) == true)
 699         {
 700             bstline[ply] = PV;
 701             bstline[ply + 1] = 0;
 702
 703             if (beta == -((SCORE_LIMIT + 1000) * 2))
 704                 return score;
 705
 706             if (alpha > beta)
 707                 return alpha;
 708         }
 709
 710 #ifdef HASHFILE
 711         /* ok try the transition file if its there */
 712         else if (hashfile
 713                  && (depth > HashDepth)
 714                  && (GameCnt < HashMoveLimit)
 715                  && (ProbeFTable(side, depth, ply, &alpha, &beta, &score)
 716                      == true))
 717         {
 718             PutInTTable(side, score, depth, ply, beta, PV);
 719             bstline[ply] = PV;
 720             bstline[ply + 1] = 0;
 721
 722             if (beta == -((SCORE_LIMIT + 1000) * 2))
 723                 return score;
 724
 725             if (alpha > beta)
 726             {
 727                 return alpha;
 728             }
 729         }
 730 #endif /* HASHFILE */
 731     }
 732 #endif /* ttblsz */
 733
 734     if (TrPnt[ply] > (TREE - 300))
 735         mustcut = true;
 736     else
 737         mustcut = false;
 738
 739     /*
 740      * If more then DepthBeyond ply past goal depth or at goal depth and
 741      * score > beta quit - means we are out of the window.
 742      */
 743
 744     if (mustcut || (ply > DepthBeyond) || ((depth < 1) && (score > beta)))
 745         return score;
 746
 747     /*
 748      * If below first ply and not at goal depth generate all moves else
 749      * only capture moves.
 750      */
 751
 752     if (ply > 1)
 753     {
 754         if ((depth > 0) || (ply < (SDEPTHLIM))
 755             || (background && (ply < Sdepth + 2)))
 756             MoveList(side, ply, in_check, blockable);
 757         else
 758             CaptureList(side, ply, in_check, blockable);
 759     }
 760
 761     /* no moves return what we have */
 762
 763     /*
 764      * normally a search will continue til past goal and no more capture
 765      * moves exist
 766      */
 767
 768     /* unless it hits DepthBeyond */
 769     if (TrPnt[ply] == TrPnt[ply + 1])
 770         return score;
 771
 772     /* if not at goal set best = -inf else current score */
 773     best = (depth > 0) ? -(SCORE_LIMIT + 3000) : score;
 774
 775 #ifdef NULLMOVE
 776
 777     PVarisave = PVari;
 778
 779     /* CHECKME: is the & really an && here? */
 780     if (!null  &&                        /* no previous null-move */
 781         !PVari &&                        /* no null-move during the PV */
 782         (ply > 2) &                      /* not at ply 1 */
 783         (ply <= Sdepth) &&
 784         (depth > 3) &&
 785         !in_check)                       /* no check */
 786         /* enough material such that zugzwang is unlikely
 787          * but who knows which value is suitable? */
 788     {
 789         /*
 790            OK, we make a null move, i.e.  this means we have nothing to do
 791            but we have to keep the some arrays up to date otherwise gnushogi
 792            gets confused.  Maybe somebody knows exactly which information is
 793            important and which isn't.
 794
 795            Another idea is that we try the null-move first and generate the
 796            moves later.  This may save time but we have to take care that
 797            PV and other variables contain the right value so that the move
 798            ordering works right.
 799         */
 800
 801         struct GameRec  *g;
 802
 803         nxtline[ply + 1] = 0;
 804         CptrFlag[ply] = 0;
 805         TesujiFlag[ply] = 0;
 806         Tscore[ply] = score;
 807         PVsave = PV;
 808         PV = 0;
 809         null = 1;
 810         g = &GameList[++GameCnt];
 811         g->hashkey = hashkey;
 812         g->hashbd = hashbd;
 813         FROMsquare = TOsquare = -1;
 814         g->Game50 = Game50;
 815         g->gmove = -1;
 816         g->flags = 0;
 817         g->piece = 0;
 818         g->color = neutral;
 819
 820         best = -search(xside, ply + 1, depth - 2,
 821                        -beta - 1, -beta, nxtline, &rcnt);
 822         null = 0;
 823         PV = PVsave;
 824         GameCnt--;
 825
 826         if (best < alpha)
 827         {
 828             best = -(SCORE_LIMIT + 3000);
 829         }
 830         else if (best > beta)
 831         {
 832             return best;
 833         }
 834         else
 835         {
 836             best = -(SCORE_LIMIT + 3000);
 837         }
 838     }
 839 #endif
 840
 841     /* if best so far is better than alpha set alpha to best */
 842     if (best > alpha)
 843         alpha = best;
 844
 845     /********************** main loop ****************************/
 846
 847     /* look at each move until no more or beta cutoff */
 848     for (pnt = pbst = TrPnt[ply];
 849          (pnt < TrPnt[ply + 1]) && (best <= beta);
 850          pnt++)
 851     {
 852         /* find the most interesting looking of the remaining moves */
 853         if (ply > 1)
 854             pick(pnt, TrPnt[ply + 1] - 1);
 855
 856 #ifdef NULLMOVE
 857         PVari = PVarisave && (pnt == TrPnt[ply]);  /* Is this the PV? */
 858 #endif
 859
 860         node = &Tree[pnt];
 861
 862         /* is this a forbidden move */
 863         if (/* ply == 1 && */ node->score <= DONTUSE)
 864             continue;
 865
 866         nxtline[ply + 1] = 0;
 867
 868         /* if at top level */
 869         if (ply == 1)
 870         {
 871 /* at the top update search status */
 872             if (flag.post)
 873             {
 874 #ifdef QUIETBACKGROUND
 875                 if (!background)
 876 #endif /* QUIETBACKGROUND */
 877                     dsp->ShowCurrentMove(pnt, node->f, node->t);
 878             }
 879             movesLeft = TrPnt[2] - pnt; /* to report with XBoard periodic updates */
 880             currentMove = node->f << 8 | node->t;
 881         }
 882
 883         if (!(node->flags & exact))
 884         {
 885             /* make the move and go deeper */
 886
 887             MakeMove(side, node, &tempb, &tempc, &tempsf,
 888                      &tempst, &INCscore);
 889             CptrFlag[ply] = ((node->flags & capture) != 0);
 890             TesujiFlag[ply] = (node->flags & tesuji)
 891                 && (node->flags & dropmask);
 892             Tscore[ply] = node->score;
 893             PV = node->reply;
 894
 895             node->score = -search(xside, ply + 1,
 896                                   (depth > 0) ? (depth - 1) : 0,
 897                                   -beta, -alpha,
 898                                   nxtline, &rcnt);
 899
 900             /*
 901              * if(!flag.timeout)
 902              *     node->score = score;
 903              */
 904
 905             node->width = ((ply % 2) == 1)
 906                 ? (TrPnt[ply + 2] - TrPnt[ply + 1])
 907                 : 0;
 908
 909             if ((node->score > SCORE_LIMIT) || (node->score < -SCORE_LIMIT) )
 910                 node->flags |= exact;
 911             else if (rcnt == 1)
 912                 node->score /= 2;
 913
 914             if (((rcnt >= 3)
 915                  || ((node->score == (SCORE_LIMIT + 999) - ply)
 916                      && !ChkFlag[ply])))
 917             {
 918                 node->flags |= (draw | exact);
 919                 DRAW = DRAW_JUSTDRAW;
 920                 node->score = ((side == computer) ? contempt : -contempt);
 921             }
 922
 923             node->reply = nxtline[ply + 1];
 924
 925             /* reset to try next move */
 926             UnmakeMove(side, node, &tempb, &tempc, &tempsf, &tempst);
 927         }
 928
 929         /* if best move so far */
 930         /* CHECKME: flag.timeout isn't valid if no hard time limit */
 931         if (!flag.timeout
 932             && ((node->score > best)
 933                 || ((node->score == best) && (node->width > bestwidth))))
 934         {
 935             /*
 936              * All things being equal pick the denser part of the
 937              * tree.
 938              */
 939             bestwidth = node->width;
 940
 941             /*
 942              * If not at goal depth and better than alpha and not
 943              * an exact score increment by depth.
 944              */
 945
 946             if ((depth > 0) && (node->score > alpha)
 947                 && !(node->flags & exact))
 948             {
 949                 node->score += depth;
 950             }
 951
 952             best = node->score;
 953             pbst = pnt;
 954
 955             if (best > alpha)
 956                 alpha = best;
 957
 958             /* update best line */
 959             for (j = ply + 1; nxtline[j] > 0; j++)
 960                 bstline[j] = nxtline[j];
 961
 962             bstline[j] = 0;
 963             bstline[ply] = (node->f << 8) | node->t;
 964
 965             /* if at the top */
 966             if (ply == 1)
 967             {
 968                 /*
 969                  * If it's better than the root score make it the root.
 970                  */
 971                 if ((best > root->score)
 972                     || ((best == root->score)
 973                         && (bestwidth > root->width)))
 974                 {
 975                     tmp = Tree[pnt];
 976
 977                     for (j = pnt - 1; j >= 0; j--)
 978                         Tree[j + 1] = Tree[j];
 979
 980                     Tree[0] = tmp;
 981                     pbst = 0;
 982                 }
 983
 984 #ifdef QUIETBACKGROUND
 985                 if (!background)
 986                 {
 987 #endif /* QUIETBACKGROUND */
 988                     if (Sdepth > 2)
 989                     {
 990                         if (best > beta)
 991                         {
 992                             dsp->ShowResults(best, bstline, '+');
 993                         }
 994                         else if (best < alpha)
 995                         {
 996                             dsp->ShowResults(best, bstline, '-');
 997                         }
 998                         else
 999                         {
1000                             dsp->ShowResults(best, bstline, '&');
1001                         }
1002                     }
1003 #ifdef QUIETBACKGROUND
1004                 }
1005 #endif
1006             }
1007         }
1008
1009         if (flag.timeout)
1010             return Tscore[ply - 1];
1011     }
1012
1013     /******************************************************/
1014
1015     node = &Tree[pbst];
1016     mv = (node->f << 8) | node->t;
1017
1018 #ifdef NULLMOVE
1019     PVari = PVarisave;
1020 #endif
1021
1022     /*
1023      * We have a move so put it in local table - if it's already there
1024      * done else if not there or needs to be updated also put it in
1025      * hashfile
1026      */
1027
1028 #if ttblsz
1029     if (flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
1030     {
1031 #  ifdef HASHFILE /* MCV: warning: this confuses the formatter. */
1032         if (use_ttable
1033             && PutInTTable(side, best, depth, ply, beta, mv)
1034             && hashfile
1035             && (depth > HashDepth)
1036             && (GameCnt < HashMoveLimit))
1037 #  else
1038         if (use_ttable
1039             && PutInTTable(side, best, depth, ply, beta, mv))
1040 #  endif
1041         {
1042             PutInFTable(side, best, depth, ply,
1043                         alpha, beta, node->f, node->t);
1044         }
1045     }
1046 #endif /* ttblsz */
1047
1048     if (depth > 0)
1049     {
1050 #if defined HISTORY
1051         unsigned short h, x;
1052         h = mv;
1053
1054         if (history[x = hindex(side, h)] < HISTORYLIM)
1055             history[x] += (unsigned short) 1 << depth;
1056 #endif
1057
1058         if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
1059         {
1060             if (best <= beta)
1061             {
1062                 killr3[ply] = mv;
1063             }
1064             else if (mv != killr1[ply])
1065             {
1066                 killr2[ply] = killr1[ply];
1067                 killr1[ply] = mv;
1068             }
1069         }
1070
1071         killr0[ply] = ((best > SCORE_LIMIT) ? mv : 0);
1072     }
1073
1074     return best;
1075 }
1076
1077
1078
1079 /*
1080  * Update the PieceList and Pindex arrays when a piece is captured or when a
1081  * capture is unmade.
1082  */
1083
1084 void
1085 UpdatePieceList(short side, short sq, UpdatePieceList_mode iop)
1086 {
1087     short i;
1088
1089     if (iop == REMOVE_PIECE)
1090     {
1091         PieceCnt[side]--;
1092
1093         for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
1094         {
1095             PieceList[side][i] = PieceList[side][i + 1];
1096             Pindex[PieceList[side][i]] = i;
1097         }
1098     }
1099     else if (board[sq] == king)
1100     {
1101         /* king must have index 0 */
1102         for (i = PieceCnt[side]; i >= 0; i--)
1103         {
1104             PieceList[side][i + 1] = PieceList[side][i];
1105             Pindex[PieceList[side][i + 1]] = i + 1;
1106         }
1107
1108         PieceCnt[side]++;
1109         PieceList[side][0] = sq;
1110         Pindex[sq] = 0;
1111     }
1112     else
1113     {
1114         PieceCnt[side]++;
1115         PieceList[side][PieceCnt[side]] = sq;
1116         Pindex[sq] = PieceCnt[side];
1117     }
1118 }
1119
1120
1121
1122 /* Make or Unmake drop move. */
1123
1124 static void
1125 drop(short side, short piece, short t, short iop)
1126 {
1127     if (iop == 1)
1128     {
1129         short n;
1130         board[t] = piece;
1131         color[t] = side;
1132
1133 #if !defined SAVE_SVALUE
1134         svalue[t] = 0;
1135 #endif
1136
1137         n = Captured[side][piece]--;
1138
1139         UpdateDropHashbd(side, piece, n);
1140         UpdateHashbd(side, piece, -1, t);
1141         UpdatePieceList(side, t, ADD_PIECE);
1142
1143         if (piece == pawn)
1144         {
1145             ++PawnCnt[side][column(t)];
1146         }
1147
1148         Mvboard[t]++;
1149         HasPiece[side][piece]++;
1150     }
1151     else
1152     {
1153         short n;
1154         board[t] = no_piece;
1155         color[t] = neutral;
1156         n = ++Captured[side][piece];
1157
1158         UpdateDropHashbd(side, piece, n);
1159         UpdateHashbd(side, piece, -1, t);
1160         UpdatePieceList(side, t, REMOVE_PIECE);
1161
1162         if (piece == pawn)
1163             --PawnCnt[side][column(t)];
1164
1165         Mvboard[t]--;
1166         HasPiece[side][piece]--;
1167     }
1168 }
1169
1170
1171 #ifdef HASHKEYTEST
1172 int
1173 CheckHashKey()
1174 {
1175     unsigned long chashkey, chashbd;
1176     short side, sq;
1177     chashbd = chashkey = 0;
1178
1179     for (sq = 0; sq < NO_SQUARES; sq++)
1180     {
1181         if (color[sq] != neutral)
1182         {
1183             chashbd ^= (*hashcode)[color[sq]][board[sq]][sq].bd;
1184             chashkey ^= (*hashcode)[color[sq]][board[sq]][sq].key;
1185         }
1186
1187         /* hashcodes for initial board are 0 ! */
1188         if (Stcolor[sq] != neutral)
1189         {
1190             chashbd ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].bd;
1191             chashkey ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].key;
1192         }
1193     }
1194
1195     for (side = 0; side <= 1; side++)
1196     {
1197         short piece;
1198
1199         for (piece = 0; piece < NO_PIECES; piece++)
1200         {
1201             short n = Captured[side][piece];
1202
1203             if (n > 0)
1204             {
1205                 short i;
1206
1207                 for (i = 1; i <= n; i++)
1208                 {
1209                     chashbd ^= (*drop_hashcode)[side][piece][i].bd;
1210                     chashkey ^= (*drop_hashcode)[side][piece][i].key;
1211                 }
1212             }
1213         }
1214     }
1215
1216     if (chashbd != hashbd)
1217         printf("chashbd %lu != hashbd %lu\n", chashbd, hashbd);
1218
1219     if (chashkey != hashkey)
1220         printf("chashkey %lu != hashkey %lu\n", chashkey, hashkey);
1221
1222     if (chashbd != hashbd || chashkey != hashkey)
1223         return 1;
1224
1225     return 0;
1226 }
1227 #endif
1228
1229
1230
1231
1232 /*
1233  * Update Arrays board[], color[], and Pindex[] to reflect the new board
1234  * position obtained after making the move pointed to by node. Also update
1235  * miscellaneous stuff that changes when a move is made.
1236  */
1237
1238 void
1239 MakeMove(short side,
1240          struct leaf  *node,
1241          short *tempb,  /* piece at to square */
1242          short *tempc,  /* color of to square */
1243          short *tempsf, /* static value of piece on from */
1244          short *tempst, /* static value of piece on to */
1245          short *INCscore)   /* score increment */
1246 {
1247     short f, t, xside;
1248     struct GameRec  *g;
1249     short fromb, fromc;
1250
1251     xside = side ^ 1;
1252     g = &GameList[++GameCnt];
1253     g->hashkey = hashkey;
1254     g->hashbd = hashbd;
1255     FROMsquare = f = node->f;
1256     TOsquare = t = (node->t & 0x7f);
1257     *INCscore = (short)node->INCscore;
1258     g->Game50 = Game50;
1259     g->gmove = (f << 8) | node->t;
1260     g->flags = node->flags;
1261
1262 #ifdef HASHKEYTEST
1263     if (CheckHashKey())
1264     {
1265         short i;
1266         algbr(f, t, node->flags);
1267         printf("error before MakeMove: %s\n", mvstr[0]);
1268         UpdateDisplay(0, 0, 1, 0);
1269
1270         for (i = 1; i <= GameCnt; i++)
1271         {
1272             movealgbr(GameList[i].gmove, mvstr[0]);
1273             printf("%d: %s\n", i, mvstr[0]);
1274         }
1275
1276         exit(1);
1277     }
1278 #endif
1279
1280     rpthash[side][hashkey & 0xFF]++, ISZERO++;
1281
1282     if (f > NO_SQUARES)
1283     {
1284         g->fpiece = (node->flags & pmask);
1285         g->piece = *tempb = no_piece;
1286         g->color = *tempc = neutral;
1287
1288 #if !defined SAVE_SVALUE
1289         *tempsf = 0;
1290         *tempst = svalue[t];
1291 #endif
1292
1293         (void)drop(side, g->fpiece, t, 1);
1294     }
1295     else
1296     {
1297 #if !defined SAVE_SVALUE
1298         *tempsf = svalue[f];
1299         *tempst = svalue[t];
1300 #endif
1301
1302         g->fpiece = board[f];
1303         g->piece = *tempb = board[t];
1304         g->color = *tempc = color[t];
1305         fromb = board[f];
1306         fromc = color[f];
1307
1308         if (*tempc != neutral)
1309         {
1310             /* Capture a piece */
1311             UpdatePieceList(*tempc, t, REMOVE_PIECE);
1312
1313             /* if capture decrement pawn count */
1314             if (*tempb == pawn)
1315                 --PawnCnt[*tempc][column(t)];
1316
1317             mtl[xside] -= (*value)[stage][*tempb];
1318             HasPiece[xside][*tempb]--;
1319
1320             {
1321                 short n, upiece = unpromoted[*tempb];
1322
1323                 /* add "upiece" captured by "side" */
1324                 n = ++Captured[side][upiece];
1325
1326                 UpdateDropHashbd(side, upiece, n);
1327                 mtl[side] += (*value)[stage][upiece];
1328             }
1329
1330             /* remove "*tempb" of "xside" from board[t] */
1331             UpdateHashbd(xside, *tempb, -1, t);
1332
1333 #if !defined SAVE_SVALUE
1334             *INCscore += *tempst; /* add value of catched piece
1335                                    * to own score */
1336 #endif
1337
1338             Mvboard[t]++;
1339         }
1340
1341         color[t] = fromc;
1342
1343 #if !defined SAVE_SVALUE
1344         svalue[t] = svalue[f];
1345         svalue[f] = 0;
1346 #endif
1347
1348         Pindex[t] = Pindex[f];
1349         PieceList[side][Pindex[t]] = t;
1350         color[f] = neutral;
1351         board[f] = no_piece;
1352
1353         if (node->flags & promote)
1354         {
1355             short tob;
1356
1357             board[t] = tob = promoted[fromb];
1358
1359             /* remove unpromoted piece from board[f] */
1360             UpdateHashbd(side, fromb, f, -1);
1361
1362             /* add promoted piece to board[t] */
1363             UpdateHashbd(side, tob, -1, t);
1364             mtl[side] += value[stage][tob] - value[stage][fromb];
1365
1366             if (fromb == pawn)
1367                 --PawnCnt[side][column(f)];
1368
1369             HasPiece[side][fromb]--;
1370             HasPiece[side][tob]++;
1371
1372 #if !defined SAVE_SVALUE
1373             *INCscore -= *tempsf;
1374 #endif
1375         }
1376         else
1377         {
1378             board[t] = fromb;
1379             /* remove piece from board[f] and add it to board[t] */
1380             UpdateHashbd(side, fromb, f, t);
1381         }
1382
1383         Mvboard[f]++;
1384     }
1385
1386 #ifdef HASHKEYTEST
1387     algbr(f, t, node->flags);
1388
1389     if (CheckHashKey())
1390     {
1391         printf("error in MakeMove: %s\n", mvstr[0]);
1392         exit(1);
1393     }
1394 #endif
1395 }
1396
1397
1398
1399
1400 /*
1401  * Take back a move.
1402  */
1403
1404 void
1405 UnmakeMove(short side,
1406            struct leaf  *node,
1407            short *tempb,
1408            short *tempc,
1409            short *tempsf,
1410            short *tempst)
1411 {
1412     short f, t, xside;
1413
1414     xside = side ^ 1;
1415     f = node->f;
1416     t = node->t & 0x7f;
1417     Game50 = GameList[GameCnt].Game50;
1418
1419     if (node->flags & dropmask)
1420     {
1421         (void)drop(side, (node->flags & pmask), t, 2);
1422
1423 #if !defined SAVE_SVALUE
1424         svalue[t] = *tempst;
1425 #endif
1426     }
1427     else
1428     {
1429         short tob, fromb;
1430
1431         color[f] = color[t];
1432         board[f] = tob = fromb = board[t];
1433
1434 #if !defined SAVE_SVALUE
1435         svalue[f] = *tempsf;
1436 #endif
1437
1438         Pindex[f] = Pindex[t];
1439         PieceList[side][Pindex[f]] = f;
1440         color[t] = *tempc;
1441         board[t] = *tempb;
1442
1443 #if !defined SAVE_SVALUE
1444         svalue[t] = *tempst;
1445 #endif
1446
1447         /* Undo move */
1448         if (node->flags & promote)
1449         {
1450             board[f] = fromb = unpromoted[tob];
1451             mtl[side] += value[stage][fromb] - value[stage][tob];
1452
1453             if (fromb == pawn)
1454                 ++PawnCnt[side][column(f)];
1455
1456             HasPiece[side][fromb]++;
1457             HasPiece[side][tob]--;
1458
1459             /* add unpromoted piece to board[f] */
1460             UpdateHashbd(side, fromb, f, -1);
1461
1462             /* remove promoted piece from board[t] */
1463             UpdateHashbd(side, tob, -1, t);
1464         }
1465         else
1466         {
1467             if (fromb == pawn)
1468             {
1469                 --PawnCnt[side][column(t)];
1470                 ++PawnCnt[side][column(f)];
1471             };
1472
1473             /* remove piece from board[t] and add it to board[f] */
1474             UpdateHashbd(side, fromb, f, t);
1475         }
1476
1477         /* Undo capture */
1478         if (*tempc != neutral)
1479         {
1480             short n, upiece = unpromoted[*tempb];
1481
1482             UpdatePieceList(*tempc, t, ADD_PIECE);
1483
1484             if (*tempb == pawn)
1485                 ++PawnCnt[*tempc][column(t)];
1486
1487             mtl[xside] += (*value)[stage][*tempb];
1488             HasPiece[xside][*tempb]++;
1489             mtl[side] -= (*value)[stage][upiece];
1490
1491             /* remove "upiece" captured by "side" */
1492             n = Captured[side][upiece]--;
1493
1494             UpdateDropHashbd(side, upiece, n);
1495
1496             /* replace captured piece on board[t] */
1497             UpdateHashbd(xside, *tempb, -1, t);
1498             Mvboard[t]--;
1499         }
1500
1501         Mvboard[f]--;
1502     }
1503
1504     GameCnt--;
1505     rpthash[side][hashkey & 0xFF]--, ISZERO--;
1506
1507 #ifdef HASHKEYTEST
1508     algbr(f, t, node->flags);
1509
1510     if (CheckHashKey())
1511     {
1512         printf("error in UnmakeMove: %s\n", mvstr[0]);
1513         exit(1);
1514     }
1515 #endif
1516 }
1517
1518
1519
1520 /*
1521  * Scan thru the board seeing what's on each square. If a piece is found,
1522  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
1523  * determine the material for each side and set the hashkey and hashbd
1524  * variables to represent the current board position. Array
1525  * PieceList[side][indx] contains the location of all the pieces of either
1526  * side. Array Pindex[sq] contains the indx into PieceList for a given
1527  * square.
1528  */
1529
1530 void
1531 InitializeStats(void)
1532 {
1533     short i, sq;
1534
1535     for (i = 0; i < NO_COLS; i++)
1536         PawnCnt[black][i] = PawnCnt[white][i] = 0;
1537
1538     mtl[black] = mtl[white] = 0;
1539     PieceCnt[black] = PieceCnt[white] = 0;
1540     hashbd = hashkey = 0;
1541
1542     for (sq = 0; sq < NO_SQUARES; sq++)
1543     {
1544         if (color[sq] != neutral)
1545         {
1546             mtl[color[sq]] += (*value)[stage][board[sq]];
1547
1548             if (board[sq] == pawn)
1549                 ++PawnCnt[color[sq]][column(sq)];
1550
1551             Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
1552             PieceList[color[sq]][Pindex[sq]] = sq;
1553             UpdateHashbd(color[sq], board[sq], sq, -1);
1554         }
1555
1556         /* hashcodes for initial board are 0 ! */
1557         if (Stcolor[sq] != neutral)
1558             UpdateHashbd(Stcolor[sq], Stboard[sq], sq, -1);
1559     }
1560
1561     {
1562         short side;
1563
1564         for (side = 0; side <= 1; side++)
1565         {
1566             short piece;
1567
1568             for (piece = 0; piece < NO_PIECES; piece++)
1569             {
1570                 short n = Captured[side][piece];
1571
1572                 if (n > 0)
1573                 {
1574                     Captured[side][piece] = 0;
1575
1576                     for (i = 1; i <= n; i++)
1577                     {
1578                         ++Captured[side][piece];
1579                         UpdateDropHashbd(side, piece, i);
1580                         mtl[side] += (*value)[stage][piece];
1581                     }
1582                 }
1583             }
1584         }
1585     }
1586
1587 #ifdef HASHKEYTEST
1588     if (CheckHashKey())
1589     {
1590         printf("error in InitializeStats\n");
1591         exit(1);
1592     }
1593 #endif
1594 }