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