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