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