gnushogi/search.c

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