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