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
  48
  49
  50 /* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
  51
  52
  53
  54 /*
  55  *  Check for draw by fourfold repetition
  56  *  (same side, same captures, same board).
  57  *  WARNING: this is not save (sp? safe?) yet due to possible hash collisions.
  58  */
  59
  60 short
  61 repetition()
  62 {
  63     short i, cnt = 0;
  64
  65 #ifndef NOREPETITION
  66     struct GameRec  *g;
  67
  68     if (GameCnt > Game50 + 6)
  69     {
  70         for (i = GameCnt - 1; i >= Game50; i -= 2)
  71         {
  72             g = &GameList[i];
  73
  74             if (g->hashkey == hashkey && g->hashbd == hashbd)
  75                 cnt++;
  76         }
  77     }
  78 #endif
  79
  80     return cnt;
  81 }
  82
  83
  84
  85 int plyscore, globalscore;
  86
  87
  88 /*
  89  * Find the best move in the tree between indexes p1 and p2. Swap the best
  90  * move into the p1 element.
  91  */
  92
  93 int
  94 pick(short p1, short p2)
  95 {
  96     struct leaf  *p, *q, *r, *k;
  97     short s0;
  98     struct leaf temp;
  99
 100     k = p = &Tree[p1];
 101     q = &Tree[p2];
 102     s0 = p->score;
 103
 104     for (r = p + 1; r <= q; r++)
 105     {
 106         if ((r->score) > s0)
 107         {
 108             s0 = r->score;
 109             p = r;
 110         }
 111     }
 112
 113     if (p != k)
 114     {
 115         temp = *p;
 116         *p = *k;
 117         *k = temp;
 118         return true;
 119     }
 120
 121     return false;
 122 }
 123
 124 int bookflag = false;
 125 int Jscore = 0;
 126
 127 int TCcount;
 128 long TCleft = 0;
 129
 130
 131
 132
 133 /*
 134  * Select a move by calling function search() at progressively deeper ply
 135  * until time is up or a mate or draw is reached. An alpha-beta window of
 136  * -Awindow to +Bwindow points is set around the score returned from the
 137  * previous iteration. If Sdepth != 0 then the program has correctly
 138  * predicted the opponents move and the search will start at a depth of
 139  * Sdepth + 1 rather than a depth of 1.
 140  */
 141
 142 void
 143 SelectMove(short side, SelectMove_mode iop)
 144 {
 145     static short i, tempb, tempc, tempsf, tempst, xside, rpt;
 146     static short alpha, beta, score;
 147     static struct GameRec  *g;
 148     short sqking, in_check;
 149     bool 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 (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;
 526     bool blockable;
 527     unsigned short mv, nxtline[MAXDEPTH];
 528     struct leaf  *node, tmp;
 529     short best = -(SCORE_LIMIT + 3000);
 530     short bestwidth = 0;
 531     bool mustcut;
 532
 533 #ifdef NULLMOVE
 534     short PVsave;
 535     short PVarisave;
 536 #endif
 537
 538     NodeCnt++;
 539
 540     /* look every ZNODE nodes for a timeout */
 541 #ifdef NULLMOVE
 542     if (!null)
 543     {
 544 #endif
 545         if (NodeCnt > ETnodes)
 546         {
 547             ElapsedTime(COMPUTE_MODE);
 548
 549             if (flag.back)
 550             {
 551                 flag.back = false;
 552                 flag.timeout = true;
 553                 flag.musttimeout = false;
 554             }
 555             else if (TCflag || MaxResponseTime)
 556             {
 557                 if ((et >= (ResponseTime + ExtraTime))
 558                     && (Sdepth > MINDEPTH))
 559                 {
 560                     /* try to extend to finish ply */
 561                     if (flag.back || (TCflag && TCcount < MAXTCCOUNTX))
 562                     {
 563                         flag.back = false;
 564                         flag.musttimeout = true;
 565                         TCcount++;
 566                         ExtraTime += TCleft;
 567                     }
 568                     else
 569                     {
 570                         flag.back = false;
 571                         flag.timeout = true;
 572                         flag.musttimeout = false;
 573                     }
 574                 }
 575             }
 576             else if (flag.back)
 577             {
 578                 flag.back = false;
 579                 flag.timeout = true;
 580                 flag.musttimeout = false;
 581             }
 582
 583 #ifdef QUIETBACKGROUND
 584             if (!background)
 585 #endif
 586                 dsp->ShowResponseTime();
 587         }
 588         else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
 589         {
 590             flag.timeout = true;
 591             flag.musttimeout = false;
 592         }
 593 #ifdef NULLMOVE
 594     }
 595 #endif
 596
 597     xside = side ^ 1;
 598     score = evaluate(side, ply, alpha, beta,
 599                      INCscore, &in_check, &blockable);
 600
 601     /*
 602      * check for possible repitition if so call repitition - rpt is
 603      * repeat count
 604      */
 605
 606     if ((ply <= Sdepth + 3) && rpthash[side][hashkey & 0xFF] > 0)
 607     {
 608         *rpt = repetition();
 609
 610         /*
 611          * repeat position >3 don't need to return score it's taken
 612          * care of above
 613          */
 614
 615         if (*rpt == 1)
 616         {
 617             score /= 3;
 618             score *= 2;
 619         }
 620         else if (*rpt == 2)
 621             score /= 2;
 622     }
 623     else
 624     {
 625         *rpt = 0;
 626     }
 627
 628     /* score > SCORE_LIMIT its a draw or mate */
 629     if (score > SCORE_LIMIT)
 630     {
 631         bstline[ply] = 0;
 632         return score;
 633     }
 634
 635     /* Do we need to add depth because of special conditions */
 636     /* if in check or in capture sequence search deeper */
 637
 638     /***************** depth extensions *****************/
 639
 640     if (depth > 0)
 641     {
 642         /* Allow opponent a chance to check again */
 643         if (in_check)
 644         {
 645             if (depth < 2)
 646                 depth = 2;
 647         }
 648         else if (flag.rcptr
 649                  && (score > alpha) && (score < beta)
 650                  && (ply > 2)
 651                  && CptrFlag[ply - 1] && CptrFlag[ply - 2])
 652         {
 653             if (hard_time_limit)
 654             {
 655                 if (!flag.timeout)
 656                     ++depth;
 657             }
 658             else
 659             {
 660                 ++depth;
 661             }
 662
 663         }
 664     }
 665     else
 666     {
 667         short timeout = 0;
 668
 669         if (hard_time_limit)
 670             timeout = flag.timeout;
 671
 672         if ((score >= alpha)
 673             && (in_check
 674                 || ((!timeout && (hung[side] > 1))
 675                     && (ply == Sdepth + 1))))
 676         {
 677             depth = 1;
 678         }
 679         else if ((score <= beta)
 680                  && (((ply < Sdepth + 4) && (ply > 4))
 681                      && ChkFlag[ply - 2]
 682                      && ChkFlag[ply - 4]
 683                      && (ChkFlag[ply - 2] != ChkFlag[ply - 4])))
 684         {
 685             depth = 1;
 686         }
 687     }
 688
 689     /***************************************************/
 690     /* try the local transition table if it's there */
 691
 692 #if ttblsz
 693     if (/* depth > 0 && */ flag.hash && ply > 1)
 694     {
 695         if (use_ttable
 696             && ProbeTTable(side, depth, ply, &alpha, &beta, &score) == true)
 697         {
 698             bstline[ply] = PV;
 699             bstline[ply + 1] = 0;
 700
 701             if (beta == -((SCORE_LIMIT + 1000) * 2))
 702                 return score;
 703
 704             if (alpha > beta)
 705                 return alpha;
 706         }
 707
 708 #ifdef HASHFILE
 709         /* ok try the transition file if its there */
 710         else if (hashfile
 711                  && (depth > HashDepth)
 712                  && (GameCnt < HashMoveLimit)
 713                  && (ProbeFTable(side, depth, ply, &alpha, &beta, &score)
 714                      == true))
 715         {
 716             PutInTTable(side, score, depth, ply, beta, PV);
 717             bstline[ply] = PV;
 718             bstline[ply + 1] = 0;
 719
 720             if (beta == -((SCORE_LIMIT + 1000) * 2))
 721                 return score;
 722
 723             if (alpha > beta)
 724             {
 725                 return alpha;
 726             }
 727         }
 728 #endif /* HASHFILE */
 729     }
 730 #endif /* ttblsz */
 731
 732     if (TrPnt[ply] > (TREE - 300))
 733         mustcut = true;
 734     else
 735         mustcut = false;
 736
 737     /*
 738      * If more then DepthBeyond ply past goal depth or at goal depth and
 739      * score > beta quit - means we are out of the window.
 740      */
 741
 742     if (mustcut || (ply > DepthBeyond) || ((depth < 1) && (score > beta)))
 743         return score;
 744
 745     /*
 746      * If below first ply and not at goal depth generate all moves else
 747      * only capture moves.
 748      */
 749
 750     if (ply > 1)
 751     {
 752         if ((depth > 0) || (ply < (SDEPTHLIM))
 753             || (background && (ply < Sdepth + 2)))
 754             MoveList(side, ply, in_check, blockable);
 755         else
 756             CaptureList(side, ply, in_check, blockable);
 757     }
 758
 759     /* no moves return what we have */
 760
 761     /*
 762      * normally a search will continue til past goal and no more capture
 763      * moves exist
 764      */
 765
 766     /* unless it hits DepthBeyond */
 767     if (TrPnt[ply] == TrPnt[ply + 1])
 768         return score;
 769
 770     /* if not at goal set best = -inf else current score */
 771     best = (depth > 0) ? -(SCORE_LIMIT + 3000) : score;
 772
 773 #ifdef NULLMOVE
 774
 775     PVarisave = PVari;
 776
 777     if (!null  &&                        /* no previous null-move */
 778         !PVari &&                        /* no null-move during the PV */
 779         (ply > 2) &&                     /* not at ply 1 or 2 */
 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         }
 877
 878         if (!(node->flags & exact))
 879         {
 880             /* make the move and go deeper */
 881
 882             MakeMove(side, node, &tempb, &tempc, &tempsf,
 883                      &tempst, &INCscore);
 884             CptrFlag[ply] = ((node->flags & capture) != 0);
 885             TesujiFlag[ply] = (node->flags & tesuji)
 886                 && (node->flags & dropmask);
 887             Tscore[ply] = node->score;
 888             PV = node->reply;
 889
 890             node->score = -search(xside, ply + 1,
 891                                   (depth > 0) ? (depth - 1) : 0,
 892                                   -beta, -alpha,
 893                                   nxtline, &rcnt);
 894
 895             /*
 896              * if(!flag.timeout)
 897              *     node->score = score;
 898              */
 899
 900             node->width = ((ply % 2) == 1)
 901                 ? (TrPnt[ply + 2] - TrPnt[ply + 1])
 902                 : 0;
 903
 904             if ((node->score > SCORE_LIMIT) || (node->score < -SCORE_LIMIT) )
 905                 node->flags |= exact;
 906             else if (rcnt == 1)
 907                 node->score /= 2;
 908
 909             if (((rcnt >= 3)
 910                  || ((node->score == (SCORE_LIMIT + 999) - ply)
 911                      && !ChkFlag[ply])))
 912             {
 913                 node->flags |= (draw | exact);
 914                 DRAW = DRAW_JUSTDRAW;
 915                 node->score = ((side == computer) ? contempt : -contempt);
 916             }
 917
 918             node->reply = nxtline[ply + 1];
 919
 920             /* reset to try next move */
 921             UnmakeMove(side, node, &tempb, &tempc, &tempsf, &tempst);
 922         }
 923
 924         /* if best move so far */
 925         /* CHECKME: flag.timeout isn't valid if no hard time limit */
 926         if (!flag.timeout
 927             && ((node->score > best)
 928                 || ((node->score == best) && (node->width > bestwidth))))
 929         {
 930             /*
 931              * All things being equal pick the denser part of the
 932              * tree.
 933              */
 934             bestwidth = node->width;
 935
 936             /*
 937              * If not at goal depth and better than alpha and not
 938              * an exact score increment by depth.
 939              */
 940
 941             if ((depth > 0) && (node->score > alpha)
 942                 && !(node->flags & exact))
 943             {
 944                 node->score += depth;
 945             }
 946
 947             best = node->score;
 948             pbst = pnt;
 949
 950             if (best > alpha)
 951                 alpha = best;
 952
 953             /* update best line */
 954             for (j = ply + 1; nxtline[j] > 0; j++)
 955                 bstline[j] = nxtline[j];
 956
 957             bstline[j] = 0;
 958             bstline[ply] = (node->f << 8) | node->t;
 959
 960             /* if at the top */
 961             if (ply == 1)
 962             {
 963                 /*
 964                  * If it's better than the root score make it the root.
 965                  */
 966                 if ((best > root->score)
 967                     || ((best == root->score)
 968                         && (bestwidth > root->width)))
 969                 {
 970                     tmp = Tree[pnt];
 971
 972                     for (j = pnt - 1; j >= 0; j--)
 973                         Tree[j + 1] = Tree[j];
 974
 975                     Tree[0] = tmp;
 976                     pbst = 0;
 977                 }
 978
 979 #ifdef QUIETBACKGROUND
 980                 if (!background)
 981                 {
 982 #endif /* QUIETBACKGROUND */
 983                     if (Sdepth > 2)
 984                     {
 985                         if (best > beta)
 986                         {
 987                             dsp->ShowResults(best, bstline, '+');
 988                         }
 989                         else if (best < alpha)
 990                         {
 991                             dsp->ShowResults(best, bstline, '-');
 992                         }
 993                         else
 994                         {
 995                             dsp->ShowResults(best, bstline, '&');
 996                         }
 997                     }
 998 #ifdef QUIETBACKGROUND
 999                 }
1000 #endif
1001             }
1002         }
1003
1004         if (flag.timeout)
1005             return Tscore[ply - 1];
1006     }
1007
1008     /******************************************************/
1009
1010     node = &Tree[pbst];
1011     mv = (node->f << 8) | node->t;
1012
1013 #ifdef NULLMOVE
1014     PVari = PVarisave;
1015 #endif
1016
1017     /*
1018      * We have a move so put it in local table - if it's already there
1019      * done else if not there or needs to be updated also put it in
1020      * hashfile
1021      */
1022
1023 #if ttblsz
1024     if (flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
1025     {
1026 #  ifdef HASHFILE /* MCV: warning: this confuses the formatter. */
1027         if (use_ttable
1028             && PutInTTable(side, best, depth, ply, beta, mv)
1029             && hashfile
1030             && (depth > HashDepth)
1031             && (GameCnt < HashMoveLimit))
1032 #  else
1033         if (use_ttable
1034             && PutInTTable(side, best, depth, ply, beta, mv))
1035 #  endif
1036         {
1037             PutInFTable(side, best, depth, ply,
1038                         alpha, beta, node->f, node->t);
1039         }
1040     }
1041 #endif /* ttblsz */
1042
1043     if (depth > 0)
1044     {
1045 #if defined HISTORY
1046         unsigned short h, x;
1047         h = mv;
1048
1049         if (history[x = hindex(side, h)] < HISTORYLIM)
1050             history[x] += (unsigned short) 1 << depth;
1051 #endif
1052
1053         if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
1054         {
1055             if (best <= beta)
1056             {
1057                 killr3[ply] = mv;
1058             }
1059             else if (mv != killr1[ply])
1060             {
1061                 killr2[ply] = killr1[ply];
1062                 killr1[ply] = mv;
1063             }
1064         }
1065
1066         killr0[ply] = ((best > SCORE_LIMIT) ? mv : 0);
1067     }
1068
1069     return best;
1070 }
1071
1072
1073
1074 /*
1075  * Update the PieceList and Pindex arrays when a piece is captured or when a
1076  * capture is unmade.
1077  */
1078
1079 void
1080 UpdatePieceList(short side, short sq, UpdatePieceList_mode iop)
1081 {
1082     short i;
1083
1084     if (iop == REMOVE_PIECE)
1085     {
1086         PieceCnt[side]--;
1087
1088         for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
1089         {
1090             PieceList[side][i] = PieceList[side][i + 1];
1091             Pindex[PieceList[side][i]] = i;
1092         }
1093     }
1094     else if (board[sq] == king)
1095     {
1096         /* king must have index 0 */
1097         for (i = PieceCnt[side]; i >= 0; i--)
1098         {
1099             PieceList[side][i + 1] = PieceList[side][i];
1100             Pindex[PieceList[side][i + 1]] = i + 1;
1101         }
1102
1103         PieceCnt[side]++;
1104         PieceList[side][0] = sq;
1105         Pindex[sq] = 0;
1106     }
1107     else
1108     {
1109         PieceCnt[side]++;
1110         PieceList[side][PieceCnt[side]] = sq;
1111         Pindex[sq] = PieceCnt[side];
1112     }
1113 }
1114
1115
1116
1117 /* Make or Unmake drop move. */
1118
1119 static void
1120 drop(short side, short piece, short t, short iop)
1121 {
1122     if (iop == 1)
1123     {
1124         short n;
1125         board[t] = piece;
1126         color[t] = side;
1127
1128 #if !defined SAVE_SVALUE
1129         svalue[t] = 0;
1130 #endif
1131
1132         n = Captured[side][piece]--;
1133
1134         UpdateDropHashbd(side, piece, n);
1135         UpdateHashbd(side, piece, -1, t);
1136         UpdatePieceList(side, t, ADD_PIECE);
1137
1138         if (piece == pawn)
1139         {
1140             ++PawnCnt[side][column(t)];
1141         }
1142
1143         Mvboard[t]++;
1144         HasPiece[side][piece]++;
1145     }
1146     else
1147     {
1148         short n;
1149         board[t] = no_piece;
1150         color[t] = neutral;
1151         n = ++Captured[side][piece];
1152
1153         UpdateDropHashbd(side, piece, n);
1154         UpdateHashbd(side, piece, -1, t);
1155         UpdatePieceList(side, t, REMOVE_PIECE);
1156
1157         if (piece == pawn)
1158             --PawnCnt[side][column(t)];
1159
1160         Mvboard[t]--;
1161         HasPiece[side][piece]--;
1162     }
1163 }
1164
1165
1166 #ifdef HASHKEYTEST
1167 int
1168 CheckHashKey()
1169 {
1170     unsigned long chashkey, chashbd;
1171     short side, sq;
1172     chashbd = chashkey = 0;
1173
1174     for (sq = 0; sq < NO_SQUARES; sq++)
1175     {
1176         if (color[sq] != neutral)
1177         {
1178             chashbd ^= (*hashcode)[color[sq]][board[sq]][sq].bd;
1179             chashkey ^= (*hashcode)[color[sq]][board[sq]][sq].key;
1180         }
1181
1182         /* hashcodes for initial board are 0 ! */
1183         if (Stcolor[sq] != neutral)
1184         {
1185             chashbd ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].bd;
1186             chashkey ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].key;
1187         }
1188     }
1189
1190     for (side = 0; side <= 1; side++)
1191     {
1192         short piece;
1193
1194         for (piece = 0; piece < NO_PIECES; piece++)
1195         {
1196             short n = Captured[side][piece];
1197
1198             if (n > 0)
1199             {
1200                 short i;
1201
1202                 for (i = 1; i <= n; i++)
1203                 {
1204                     chashbd ^= (*drop_hashcode)[side][piece][i].bd;
1205                     chashkey ^= (*drop_hashcode)[side][piece][i].key;
1206                 }
1207             }
1208         }
1209     }
1210
1211     if (chashbd != hashbd)
1212         printf("chashbd %lu != hashbd %lu\n", chashbd, hashbd);
1213
1214     if (chashkey != hashkey)
1215         printf("chashkey %lu != hashkey %lu\n", chashkey, hashkey);
1216
1217     if (chashbd != hashbd || chashkey != hashkey)
1218         return 1;
1219
1220     return 0;
1221 }
1222 #endif
1223
1224
1225
1226
1227 /*
1228  * Update Arrays board[], color[], and Pindex[] to reflect the new board
1229  * position obtained after making the move pointed to by node. Also update
1230  * miscellaneous stuff that changes when a move is made.
1231  */
1232
1233 void
1234 MakeMove(short side,
1235          struct leaf  *node,
1236          short *tempb,  /* piece at to square */
1237          short *tempc,  /* color of to square */
1238          short *tempsf, /* static value of piece on from */
1239          short *tempst, /* static value of piece on to */
1240          short *INCscore)   /* score increment */
1241 {
1242     short f, t, xside;
1243     struct GameRec  *g;
1244     short fromb, fromc;
1245
1246     xside = side ^ 1;
1247     g = &GameList[++GameCnt];
1248     g->hashkey = hashkey;
1249     g->hashbd = hashbd;
1250     FROMsquare = f = node->f;
1251     TOsquare = t = (node->t & 0x7f);
1252     *INCscore = (short)node->INCscore;
1253     g->Game50 = Game50;
1254     g->gmove = (f << 8) | node->t;
1255     g->flags = node->flags;
1256
1257 #ifdef HASHKEYTEST
1258     if (CheckHashKey())
1259     {
1260         short i;
1261         algbr(f, t, node->flags);
1262         printf("error before MakeMove: %s\n", mvstr[0]);
1263         UpdateDisplay(0, 0, 1, 0);
1264
1265         for (i = 1; i <= GameCnt; i++)
1266         {
1267             movealgbr(GameList[i].gmove, mvstr[0]);
1268             printf("%d: %s\n", i, mvstr[0]);
1269         }
1270
1271         exit(1);
1272     }
1273 #endif
1274
1275     rpthash[side][hashkey & 0xFF]++, ISZERO++;
1276
1277     if (f > NO_SQUARES)
1278     {
1279         g->fpiece = (node->flags & pmask);
1280         g->piece = *tempb = no_piece;
1281         g->color = *tempc = neutral;
1282
1283 #if !defined SAVE_SVALUE
1284         *tempsf = 0;
1285         *tempst = svalue[t];
1286 #endif
1287
1288         (void)drop(side, g->fpiece, t, 1);
1289     }
1290     else
1291     {
1292 #if !defined SAVE_SVALUE
1293         *tempsf = svalue[f];
1294         *tempst = svalue[t];
1295 #endif
1296
1297         g->fpiece = board[f];
1298         g->piece = *tempb = board[t];
1299         g->color = *tempc = color[t];
1300         fromb = board[f];
1301         fromc = color[f];
1302
1303         if (*tempc != neutral)
1304         {
1305             /* Capture a piece */
1306             UpdatePieceList(*tempc, t, REMOVE_PIECE);
1307
1308             /* if capture decrement pawn count */
1309             if (*tempb == pawn)
1310                 --PawnCnt[*tempc][column(t)];
1311
1312             mtl[xside] -= (*value)[stage][*tempb];
1313             HasPiece[xside][*tempb]--;
1314
1315             {
1316                 short n, upiece = unpromoted[*tempb];
1317
1318                 /* add "upiece" captured by "side" */
1319                 n = ++Captured[side][upiece];
1320
1321                 UpdateDropHashbd(side, upiece, n);
1322                 mtl[side] += (*value)[stage][upiece];
1323             }
1324
1325             /* remove "*tempb" of "xside" from board[t] */
1326             UpdateHashbd(xside, *tempb, -1, t);
1327
1328 #if !defined SAVE_SVALUE
1329             *INCscore += *tempst; /* add value of catched piece
1330                                    * to own score */
1331 #endif
1332
1333             Mvboard[t]++;
1334         }
1335
1336         color[t] = fromc;
1337
1338 #if !defined SAVE_SVALUE
1339         svalue[t] = svalue[f];
1340         svalue[f] = 0;
1341 #endif
1342
1343         Pindex[t] = Pindex[f];
1344         PieceList[side][Pindex[t]] = t;
1345         color[f] = neutral;
1346         board[f] = no_piece;
1347
1348         if (node->flags & promote)
1349         {
1350             short tob;
1351
1352             board[t] = tob = promoted[fromb];
1353
1354             /* remove unpromoted piece from board[f] */
1355             UpdateHashbd(side, fromb, f, -1);
1356
1357             /* add promoted piece to board[t] */
1358             UpdateHashbd(side, tob, -1, t);
1359             mtl[side] += value[stage][tob] - value[stage][fromb];
1360
1361             if (fromb == pawn)
1362                 --PawnCnt[side][column(f)];
1363
1364             HasPiece[side][fromb]--;
1365             HasPiece[side][tob]++;
1366
1367 #if !defined SAVE_SVALUE
1368             *INCscore -= *tempsf;
1369 #endif
1370         }
1371         else
1372         {
1373             board[t] = fromb;
1374             /* remove piece from board[f] and add it to board[t] */
1375             UpdateHashbd(side, fromb, f, t);
1376         }
1377
1378         Mvboard[f]++;
1379     }
1380
1381 #ifdef HASHKEYTEST
1382     algbr(f, t, node->flags);
1383
1384     if (CheckHashKey())
1385     {
1386         printf("error in MakeMove: %s\n", mvstr[0]);
1387         exit(1);
1388     }
1389 #endif
1390 }
1391
1392
1393
1394
1395 /*
1396  * Take back a move.
1397  */
1398
1399 void
1400 UnmakeMove(short side,
1401            struct leaf  *node,
1402            short *tempb,
1403            short *tempc,
1404            short *tempsf,
1405            short *tempst)
1406 {
1407     short f, t, xside;
1408
1409     xside = side ^ 1;
1410     f = node->f;
1411     t = node->t & 0x7f;
1412     Game50 = GameList[GameCnt].Game50;
1413
1414     if (node->flags & dropmask)
1415     {
1416         (void)drop(side, (node->flags & pmask), t, 2);
1417
1418 #if !defined SAVE_SVALUE
1419         svalue[t] = *tempst;
1420 #endif
1421     }
1422     else
1423     {
1424         short tob, fromb;
1425
1426         color[f] = color[t];
1427         board[f] = tob = fromb = board[t];
1428
1429 #if !defined SAVE_SVALUE
1430         svalue[f] = *tempsf;
1431 #endif
1432
1433         Pindex[f] = Pindex[t];
1434         PieceList[side][Pindex[f]] = f;
1435         color[t] = *tempc;
1436         board[t] = *tempb;
1437
1438 #if !defined SAVE_SVALUE
1439         svalue[t] = *tempst;
1440 #endif
1441
1442         /* Undo move */
1443         if (node->flags & promote)
1444         {
1445             board[f] = fromb = unpromoted[tob];
1446             mtl[side] += value[stage][fromb] - value[stage][tob];
1447
1448             if (fromb == pawn)
1449                 ++PawnCnt[side][column(f)];
1450
1451             HasPiece[side][fromb]++;
1452             HasPiece[side][tob]--;
1453
1454             /* add unpromoted piece to board[f] */
1455             UpdateHashbd(side, fromb, f, -1);
1456
1457             /* remove promoted piece from board[t] */
1458             UpdateHashbd(side, tob, -1, t);
1459         }
1460         else
1461         {
1462             if (fromb == pawn)
1463             {
1464                 --PawnCnt[side][column(t)];
1465                 ++PawnCnt[side][column(f)];
1466             };
1467
1468             /* remove piece from board[t] and add it to board[f] */
1469             UpdateHashbd(side, fromb, f, t);
1470         }
1471
1472         /* Undo capture */
1473         if (*tempc != neutral)
1474         {
1475             short n, upiece = unpromoted[*tempb];
1476
1477             UpdatePieceList(*tempc, t, ADD_PIECE);
1478
1479             if (*tempb == pawn)
1480                 ++PawnCnt[*tempc][column(t)];
1481
1482             mtl[xside] += (*value)[stage][*tempb];
1483             HasPiece[xside][*tempb]++;
1484             mtl[side] -= (*value)[stage][upiece];
1485
1486             /* remove "upiece" captured by "side" */
1487             n = Captured[side][upiece]--;
1488
1489             UpdateDropHashbd(side, upiece, n);
1490
1491             /* replace captured piece on board[t] */
1492             UpdateHashbd(xside, *tempb, -1, t);
1493             Mvboard[t]--;
1494         }
1495
1496         Mvboard[f]--;
1497     }
1498
1499     GameCnt--;
1500     rpthash[side][hashkey & 0xFF]--, ISZERO--;
1501
1502 #ifdef HASHKEYTEST
1503     algbr(f, t, node->flags);
1504
1505     if (CheckHashKey())
1506     {
1507         printf("error in UnmakeMove: %s\n", mvstr[0]);
1508         exit(1);
1509     }
1510 #endif
1511 }
1512
1513
1514
1515 /*
1516  * Scan thru the board seeing what's on each square. If a piece is found,
1517  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
1518  * determine the material for each side and set the hashkey and hashbd
1519  * variables to represent the current board position. Array
1520  * PieceList[side][indx] contains the location of all the pieces of either
1521  * side. Array Pindex[sq] contains the indx into PieceList for a given
1522  * square.
1523  */
1524
1525 void
1526 InitializeStats(void)
1527 {
1528     short i, sq;
1529
1530     for (i = 0; i < NO_COLS; i++)
1531         PawnCnt[black][i] = PawnCnt[white][i] = 0;
1532
1533     mtl[black] = mtl[white] = 0;
1534     PieceCnt[black] = PieceCnt[white] = 0;
1535     hashbd = hashkey = 0;
1536
1537     for (sq = 0; sq < NO_SQUARES; sq++)
1538     {
1539         if (color[sq] != neutral)
1540         {
1541             mtl[color[sq]] += (*value)[stage][board[sq]];
1542
1543             if (board[sq] == pawn)
1544                 ++PawnCnt[color[sq]][column(sq)];
1545
1546             Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
1547             PieceList[color[sq]][Pindex[sq]] = sq;
1548             UpdateHashbd(color[sq], board[sq], sq, -1);
1549         }
1550
1551         /* hashcodes for initial board are 0 ! */
1552         if (Stcolor[sq] != neutral)
1553             UpdateHashbd(Stcolor[sq], Stboard[sq], sq, -1);
1554     }
1555
1556     {
1557         short side;
1558
1559         for (side = 0; side <= 1; side++)
1560         {
1561             short piece;
1562
1563             for (piece = 0; piece < NO_PIECES; piece++)
1564             {
1565                 short n = Captured[side][piece];
1566
1567                 if (n > 0)
1568                 {
1569                     Captured[side][piece] = 0;
1570
1571                     for (i = 1; i <= n; i++)
1572                     {
1573                         ++Captured[side][piece];
1574                         UpdateDropHashbd(side, piece, i);
1575                         mtl[side] += (*value)[stage][piece];
1576                     }
1577                 }
1578             }
1579         }
1580     }
1581
1582 #ifdef HASHKEYTEST
1583     if (CheckHashKey())
1584     {
1585         printf("error in InitializeStats\n");
1586         exit(1);
1587     }
1588 #endif
1589 }