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