src/search.c

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