gnushogi/search.c

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