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