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