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