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         ShowResponseTime();
 185
 186     ExtraTime = 0;
 187
 188     score = ScorePosition(side);
 189
 190 #ifdef QUIETBACKGROUND
 191     if (!background)
 192 #endif /* QUIETBACKGROUND */
 193         ShowSidetoMove();
 194
 195 #ifdef QUIETBACKGROUND
 196     if (!background)
 197 #endif /* QUIETBACKGROUND */
 198         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, side);
 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             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                 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                 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             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     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                 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, alpha, 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 !defined NOPOST
 866         if (ply == 1)
 867         {
 868 /* at the top update search status */
 869             if (flag.post)
 870             {
 871 #ifdef QUIETBACKGROUND
 872                 if (!background)
 873 #endif /* QUIETBACKGROUND */
 874                     ShowCurrentMove(pnt, node->f, node->t);
 875             }
 876         }
 877 #endif
 878
 879         if (!(node->flags & exact))
 880         {
 881             /* make the move and go deeper */
 882
 883             MakeMove(side, node, &tempb, &tempc, &tempsf,
 884                      &tempst, &INCscore);
 885             CptrFlag[ply] = ((node->flags & capture) != 0);
 886             TesujiFlag[ply] = (node->flags & tesuji)
 887                 && (node->flags & dropmask);
 888             Tscore[ply] = node->score;
 889             PV = node->reply;
 890
 891             node->score = -search(xside, ply + 1,
 892                                   (depth > 0) ? (depth - 1) : 0,
 893                                   -beta, -alpha,
 894                                   nxtline, &rcnt);
 895
 896             /*
 897              * if(!flag.timeout)
 898              *     node->score = score;
 899              */
 900
 901             node->width = ((ply % 2) == 1)
 902                 ? (TrPnt[ply + 2] - TrPnt[ply + 1])
 903                 : 0;
 904
 905             if ((node->score > SCORE_LIMIT) || (node->score < -SCORE_LIMIT) )
 906                 node->flags |= exact;
 907             else if (rcnt == 1)
 908                 node->score /= 2;
 909
 910             if (((rcnt >= 3)
 911                  || ((node->score == (SCORE_LIMIT + 999) - ply)
 912                      && !ChkFlag[ply])))
 913             {
 914                 node->flags |= (draw | exact);
 915                 DRAW = DRAW_JUSTDRAW;
 916                 node->score = ((side == computer) ? contempt : -contempt);
 917             }
 918
 919             node->reply = nxtline[ply + 1];
 920
 921             /* reset to try next move */
 922             UnmakeMove(side, node, &tempb, &tempc, &tempsf, &tempst);
 923         }
 924
 925         /* if best move so far */
 926         /* CHECKME: flag.timeout isn't valid if no hard time limit */
 927         if (!flag.timeout
 928             && ((node->score > best)
 929                 || ((node->score == best) && (node->width > bestwidth))))
 930         {
 931             /*
 932              * All things being equal pick the denser part of the
 933              * tree.
 934              */
 935             bestwidth = node->width;
 936
 937             /*
 938              * If not at goal depth and better than alpha and not
 939              * an exact score increment by depth.
 940              */
 941
 942             if ((depth > 0) && (node->score > alpha)
 943                 && !(node->flags & exact))
 944             {
 945                 node->score += depth;
 946             }
 947
 948             best = node->score;
 949             pbst = pnt;
 950
 951             if (best > alpha)
 952                 alpha = best;
 953
 954             /* update best line */
 955             for (j = ply + 1; nxtline[j] > 0; j++)
 956                 bstline[j] = nxtline[j];
 957
 958             bstline[j] = 0;
 959             bstline[ply] = (node->f << 8) | node->t;
 960
 961             /* if at the top */
 962             if (ply == 1)
 963             {
 964                 /*
 965                  * If it's better than the root score make it the root.
 966                  */
 967                 if ((best > root->score)
 968                     || ((best == root->score)
 969                         && (bestwidth > root->width)))
 970                 {
 971                     tmp = Tree[pnt];
 972
 973                     for (j = pnt - 1; j >= 0; j--)
 974                         Tree[j + 1] = Tree[j];
 975
 976                     Tree[0] = tmp;
 977                     pbst = 0;
 978                 }
 979
 980 #ifdef QUIETBACKGROUND
 981                 if (!background)
 982                 {
 983 #endif /* QUIETBACKGROUND */
 984                     if (Sdepth > 2)
 985                     {
 986                         if (best > beta)
 987                         {
 988                             ShowResults(best, bstline, '+');
 989                         }
 990                         else if (best < alpha)
 991                         {
 992                             ShowResults(best, bstline, '-');
 993                         }
 994                         else
 995                         {
 996                             ShowResults (best, bstline, '&');
 997                         }
 998                     }
 999 #ifdef QUIETBACKGROUND
1000                 }
1001 #endif
1002             }
1003         }
1004
1005         if (flag.timeout)
1006             return Tscore[ply - 1];
1007     }
1008
1009     /******************************************************/
1010
1011     node = &Tree[pbst];
1012     mv = (node->f << 8) | node->t;
1013
1014 #ifdef NULLMOVE
1015     PVari = PVarisave;
1016 #endif
1017
1018     /*
1019      * We have a move so put it in local table - if it's already there
1020      * done else if not there or needs to be updated also put it in
1021      * hashfile
1022      */
1023
1024 #if ttblsz
1025     if (flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
1026     {
1027 #  ifdef HASHFILE /* MCV: warning: this confuses the formatter. */
1028         if (use_ttable
1029             && PutInTTable(side, best, depth, ply, alpha, beta, mv)
1030             && hashfile
1031             && (depth > HashDepth)
1032             && (GameCnt < HashMoveLimit))
1033 #  else
1034         if (use_ttable
1035             && PutInTTable(side, best, depth, ply, alpha, beta, mv))
1036 #  endif
1037         {
1038             PutInFTable(side, best, depth, ply,
1039                         alpha, beta, node->f, node->t);
1040         }
1041     }
1042 #endif /* ttblsz */
1043
1044     if (depth > 0)
1045     {
1046 #if defined HISTORY
1047         unsigned short h, x;
1048         h = mv;
1049
1050         if (history[x = hindex(side, h)] < HISTORYLIM)
1051             history[x] += (unsigned short) 1 << depth;
1052 #endif
1053
1054         if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
1055         {
1056             if (best <= beta)
1057             {
1058                 killr3[ply] = mv;
1059             }
1060             else if (mv != killr1[ply])
1061             {
1062                 killr2[ply] = killr1[ply];
1063                 killr1[ply] = mv;
1064             }
1065         }
1066
1067         killr0[ply] = ((best > SCORE_LIMIT) ? mv : 0);
1068     }
1069
1070     return best;
1071 }
1072
1073
1074
1075 /*
1076  * Update the PieceList and Pindex arrays when a piece is captured or when a
1077  * capture is unmade.
1078  */
1079
1080 void
1081 UpdatePieceList(short side, short sq, UpdatePieceList_mode iop)
1082 {
1083     short i;
1084
1085     if (iop == REMOVE_PIECE)
1086     {
1087         PieceCnt[side]--;
1088
1089         for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
1090         {
1091             PieceList[side][i] = PieceList[side][i + 1];
1092             Pindex[PieceList[side][i]] = i;
1093         }
1094     }
1095     else if (board[sq] == king)
1096     {
1097         /* king must have index 0 */
1098         for (i = PieceCnt[side]; i >= 0; i--)
1099         {
1100             PieceList[side][i + 1] = PieceList[side][i];
1101             Pindex[PieceList[side][i + 1]] = i + 1;
1102         }
1103
1104         PieceCnt[side]++;
1105         PieceList[side][0] = sq;
1106         Pindex[sq] = 0;
1107     }
1108     else
1109     {
1110         PieceCnt[side]++;
1111         PieceList[side][PieceCnt[side]] = sq;
1112         Pindex[sq] = PieceCnt[side];
1113     }
1114 }
1115
1116
1117
1118 /* Make or Unmake drop move. */
1119
1120 void
1121 drop(short side, short piece, short f, short t, short iop)
1122 {
1123     if (iop == 1)
1124     {
1125         short n;
1126         board[t] = piece;
1127         color[t] = side;
1128
1129 #if !defined SAVE_SVALUE
1130         svalue[t] = 0;
1131 #endif
1132
1133         n = Captured[side][piece]--;
1134
1135         UpdateDropHashbd(side, piece, n);
1136         UpdateHashbd(side, piece, -1, t);
1137         UpdatePieceList(side, t, ADD_PIECE);
1138
1139         if (piece == pawn)
1140         {
1141             ++PawnCnt[side][column(t)];
1142         }
1143
1144         Mvboard[t]++;
1145         HasPiece[side][piece]++;
1146     }
1147     else
1148     {
1149         short n;
1150         board[t] = no_piece;
1151         color[t] = neutral;
1152         n = ++Captured[side][piece];
1153
1154         UpdateDropHashbd(side, piece, n);
1155         UpdateHashbd(side, piece, -1, t);
1156         UpdatePieceList(side, t, REMOVE_PIECE);
1157
1158         if (piece == pawn)
1159             --PawnCnt[side][column(t)];
1160
1161         Mvboard[t]--;
1162         HasPiece[side][piece]--;
1163     }
1164 }
1165
1166
1167 #ifdef HASHKEYTEST
1168 int
1169 CheckHashKey()
1170 {
1171     unsigned long chashkey, chashbd;
1172     short side, sq;
1173     chashbd = chashkey = 0;
1174
1175     for (sq = 0; sq < NO_SQUARES; sq++)
1176     {
1177         if (color[sq] != neutral)
1178         {
1179             chashbd ^= (*hashcode)[color[sq]][board[sq]][sq].bd;
1180             chashkey ^= (*hashcode)[color[sq]][board[sq]][sq].key;
1181         }
1182
1183         /* hashcodes for initial board are 0 ! */
1184         if (Stcolor[sq] != neutral)
1185         {
1186             chashbd ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].bd;
1187             chashkey ^= (*hashcode)[Stcolor[sq]][Stboard[sq]][sq].key;
1188         }
1189     }
1190
1191     for (side = 0; side <= 1; side++)
1192     {
1193         short piece;
1194
1195         for (piece = 0; piece < NO_PIECES; piece++)
1196         {
1197             short n = Captured[side][piece];
1198
1199             if (n > 0)
1200             {
1201                 short i;
1202
1203                 for (i = 1; i <= n; i++)
1204                 {
1205                     chashbd ^= (*drop_hashcode)[side][piece][i].bd;
1206                     chashkey ^= (*drop_hashcode)[side][piece][i].key;
1207                 }
1208             }
1209         }
1210     }
1211
1212     if (chashbd != hashbd)
1213         printf("chashbd %lu != hashbd %lu\n", chashbd, hashbd);
1214
1215     if (chashkey != hashkey)
1216         printf("chashkey %lu != hashkey %lu\n", chashkey, hashkey);
1217
1218     if (chashbd != hashbd || chashkey != hashkey)
1219         return 1;
1220
1221     return 0;
1222 }
1223 #endif
1224
1225
1226
1227
1228 /*
1229  * Update Arrays board[], color[], and Pindex[] to reflect the new board
1230  * position obtained after making the move pointed to by node. Also update
1231  * miscellaneous stuff that changes when a move is made.
1232  */
1233
1234 void
1235 MakeMove(short side,
1236          struct leaf  *node,
1237          short *tempb,  /* piece at to square */
1238          short *tempc,  /* color of to square */
1239          short *tempsf, /* static value of piece on from */
1240          short *tempst, /* static value of piece on to */
1241          short *INCscore)   /* score increment */
1242 {
1243     short f, t, xside;
1244     struct GameRec  *g;
1245     short fromb, fromc;
1246
1247     xside = side ^ 1;
1248     g = &GameList[++GameCnt];
1249     g->hashkey = hashkey;
1250     g->hashbd = hashbd;
1251     FROMsquare = f = node->f;
1252     TOsquare = t = (node->t & 0x7f);
1253     *INCscore = (short)node->INCscore;
1254     g->Game50 = Game50;
1255     g->gmove = (f << 8) | node->t;
1256     g->flags = node->flags;
1257
1258 #ifdef HASHKEYTEST
1259     if (CheckHashKey())
1260     {
1261         short i;
1262         algbr(f, t, node->flags);
1263         printf("error before MakeMove: %s\n", mvstr[0]);
1264         UpdateDisplay(0, 0, 1, 0);
1265
1266         for (i = 1; i <= GameCnt; i++)
1267         {
1268             movealgbr(GameList[i].gmove, mvstr[0]);
1269             printf("%d: %s\n", i, mvstr[0]);
1270         }
1271
1272         exit(1);
1273     }
1274 #endif
1275
1276     rpthash[side][hashkey & 0xFF]++, ISZERO++;
1277
1278     if (f > NO_SQUARES)
1279     {
1280         g->fpiece = (node->flags & pmask);
1281         g->piece = *tempb = no_piece;
1282         g->color = *tempc = neutral;
1283
1284 #if !defined SAVE_SVALUE
1285         *tempsf = 0;
1286         *tempst = svalue[t];
1287 #endif
1288
1289         (void)drop(side, g->fpiece, f, t, 1);
1290     }
1291     else
1292     {
1293 #if !defined SAVE_SVALUE
1294         *tempsf = svalue[f];
1295         *tempst = svalue[t];
1296 #endif
1297
1298         g->fpiece = board[f];
1299         g->piece = *tempb = board[t];
1300         g->color = *tempc = color[t];
1301         fromb = board[f];
1302         fromc = color[f];
1303
1304         if (*tempc != neutral)
1305         {
1306             /* Capture a piece */
1307             UpdatePieceList(*tempc, t, REMOVE_PIECE);
1308
1309             /* if capture decrement pawn count */
1310             if (*tempb == pawn)
1311                 --PawnCnt[*tempc][column(t)];
1312
1313             mtl[xside] -= (*value)[stage][*tempb];
1314             HasPiece[xside][*tempb]--;
1315
1316             {
1317                 short n, upiece = unpromoted[*tempb];
1318
1319                 /* add "upiece" captured by "side" */
1320                 n = ++Captured[side][upiece];
1321
1322                 UpdateDropHashbd(side, upiece, n);
1323                 mtl[side] += (*value)[stage][upiece];
1324             }
1325
1326             /* remove "*tempb" of "xside" from board[t] */
1327             UpdateHashbd(xside, *tempb, -1, t);
1328
1329 #if !defined SAVE_SVALUE
1330             *INCscore += *tempst; /* add value of catched piece
1331                                    * to own score */
1332 #endif
1333
1334             Mvboard[t]++;
1335         }
1336
1337         color[t] = fromc;
1338
1339 #if !defined SAVE_SVALUE
1340         svalue[t] = svalue[f];
1341         svalue[f] = 0;
1342 #endif
1343
1344         Pindex[t] = Pindex[f];
1345         PieceList[side][Pindex[t]] = t;
1346         color[f] = neutral;
1347         board[f] = no_piece;
1348
1349         if (node->flags & promote)
1350         {
1351             short tob;
1352
1353             board[t] = tob = promoted[fromb];
1354
1355             /* remove unpromoted piece from board[f] */
1356             UpdateHashbd(side, fromb, f, -1);
1357
1358             /* add promoted piece to board[t] */
1359             UpdateHashbd(side, tob, -1, t);
1360             mtl[side] += value[stage][tob] - value[stage][fromb];
1361
1362             if (fromb == pawn)
1363                 --PawnCnt[side][column(f)];
1364
1365             HasPiece[side][fromb]--;
1366             HasPiece[side][tob]++;
1367
1368 #if !defined SAVE_SVALUE
1369             *INCscore -= *tempsf;
1370 #endif
1371         }
1372         else
1373         {
1374             board[t] = fromb;
1375             /* remove piece from board[f] and add it to board[t] */
1376             UpdateHashbd(side, fromb, f, t);
1377         }
1378
1379         Mvboard[f]++;
1380     }
1381
1382 #ifdef HASHKEYTEST
1383     algbr(f, t, node->flags);
1384
1385     if (CheckHashKey())
1386     {
1387         printf("error in MakeMove: %s\n", mvstr[0]);
1388         exit(1);
1389     }
1390 #endif
1391 }
1392
1393
1394
1395
1396 /*
1397  * Take back a move.
1398  */
1399
1400 void
1401 UnmakeMove(short side,
1402            struct leaf  *node,
1403            short *tempb,
1404            short *tempc,
1405            short *tempsf,
1406            short *tempst)
1407 {
1408     short f, t, xside;
1409
1410     xside = side ^ 1;
1411     f = node->f;
1412     t = node->t & 0x7f;
1413     Game50 = GameList[GameCnt].Game50;
1414
1415     if (node->flags & dropmask)
1416     {
1417         (void)drop(side, (node->flags & pmask), f, t, 2);
1418
1419 #if !defined SAVE_SVALUE
1420         svalue[t] = *tempst;
1421 #endif
1422     }
1423     else
1424     {
1425         short tob, fromb;
1426
1427         color[f] = color[t];
1428         board[f] = tob = fromb = board[t];
1429
1430 #if !defined SAVE_SVALUE
1431         svalue[f] = *tempsf;
1432 #endif
1433
1434         Pindex[f] = Pindex[t];
1435         PieceList[side][Pindex[f]] = f;
1436         color[t] = *tempc;
1437         board[t] = *tempb;
1438
1439 #if !defined SAVE_SVALUE
1440         svalue[t] = *tempst;
1441 #endif
1442
1443         /* Undo move */
1444         if (node->flags & promote)
1445         {
1446             board[f] = fromb = unpromoted[tob];
1447             mtl[side] += value[stage][fromb] - value[stage][tob];
1448
1449             if (fromb == pawn)
1450                 ++PawnCnt[side][column(f)];
1451
1452             HasPiece[side][fromb]++;
1453             HasPiece[side][tob]--;
1454
1455             /* add unpromoted piece to board[f] */
1456             UpdateHashbd(side, fromb, f, -1);
1457
1458             /* remove promoted piece from board[t] */
1459             UpdateHashbd(side, tob, -1, t);
1460         }
1461         else
1462         {
1463             if (fromb == pawn)
1464             {
1465                 --PawnCnt[side][column(t)];
1466                 ++PawnCnt[side][column(f)];
1467             };
1468
1469             /* remove piece from board[t] and add it to board[f] */
1470             UpdateHashbd(side, fromb, f, t);
1471         }
1472
1473         /* Undo capture */
1474         if (*tempc != neutral)
1475         {
1476             short n, upiece = unpromoted[*tempb];
1477
1478             UpdatePieceList(*tempc, t, ADD_PIECE);
1479
1480             if (*tempb == pawn)
1481                 ++PawnCnt[*tempc][column(t)];
1482
1483             mtl[xside] += (*value)[stage][*tempb];
1484             HasPiece[xside][*tempb]++;
1485             mtl[side] -= (*value)[stage][upiece];
1486
1487             /* remove "upiece" captured by "side" */
1488             n = Captured[side][upiece]--;
1489
1490             UpdateDropHashbd(side, upiece, n);
1491
1492             /* replace captured piece on board[t] */
1493             UpdateHashbd(xside, *tempb, -1, t);
1494             Mvboard[t]--;
1495         }
1496
1497         Mvboard[f]--;
1498     }
1499
1500     GameCnt--;
1501     rpthash[side][hashkey & 0xFF]--, ISZERO--;
1502
1503 #ifdef HASHKEYTEST
1504     algbr(f, t, node->flags);
1505
1506     if (CheckHashKey())
1507     {
1508         printf("error in UnmakeMove: %s\n", mvstr[0]);
1509         exit(1);
1510     }
1511 #endif
1512 }
1513
1514
1515
1516 /*
1517  * Scan thru the board seeing what's on each square. If a piece is found,
1518  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
1519  * determine the material for each side and set the hashkey and hashbd
1520  * variables to represent the current board position. Array
1521  * PieceList[side][indx] contains the location of all the pieces of either
1522  * side. Array Pindex[sq] contains the indx into PieceList for a given
1523  * square.
1524  */
1525
1526 void
1527 InitializeStats(void)
1528 {
1529     short i, sq;
1530
1531     for (i = 0; i < NO_COLS; i++)
1532         PawnCnt[black][i] = PawnCnt[white][i] = 0;
1533
1534     mtl[black] = mtl[white] = 0;
1535     PieceCnt[black] = PieceCnt[white] = 0;
1536     hashbd = hashkey = 0;
1537
1538     for (sq = 0; sq < NO_SQUARES; sq++)
1539     {
1540         if (color[sq] != neutral)
1541         {
1542             mtl[color[sq]] += (*value)[stage][board[sq]];
1543
1544             if (board[sq] == pawn)
1545                 ++PawnCnt[color[sq]][column(sq)];
1546
1547             Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
1548             PieceList[color[sq]][Pindex[sq]] = sq;
1549             UpdateHashbd(color[sq], board[sq], sq, -1);
1550         }
1551
1552         /* hashcodes for initial board are 0 ! */
1553         if (Stcolor[sq] != neutral)
1554             UpdateHashbd(Stcolor[sq], Stboard[sq], sq, -1);
1555     }
1556
1557     {
1558         short side;
1559
1560         for (side = 0; side <= 1; side++)
1561         {
1562             short piece;
1563
1564             for (piece = 0; piece < NO_PIECES; piece++)
1565             {
1566                 short n = Captured[side][piece];
1567
1568                 if (n > 0)
1569                 {
1570                     Captured[side][piece] = 0;
1571
1572                     for (i = 1; i <= n; i++)
1573                     {
1574                         ++Captured[side][piece];
1575                         UpdateDropHashbd(side, piece, i);
1576                         mtl[side] += (*value)[stage][piece];
1577                     }
1578                 }
1579             }
1580         }
1581     }
1582
1583 #ifdef HASHKEYTEST
1584     if (CheckHashKey())
1585     {
1586         printf("error in InitializeStats\n");
1587         exit(1);
1588     }
1589 #endif
1590 }