home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / CHESS.PAK / SEARCH.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  24.3 KB  |  919 lines
  1. //----------------------------------------------------------------------------
  2. // ObjectWindows - (C) Copyright 1991, 1993 by Borland International
  3. //----------------------------------------------------------------------------
  4. #include <owl/pch.h>
  5. #include <owl/defs.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <dos.h>
  9. #include <stdio.h>
  10. #include "wcdefs.h"
  11. #include "wchess.h"
  12. #include "externs.h"
  13. #include "info.h"
  14.  
  15. #undef max
  16. #undef min
  17. #define max(a, b)  (((a) > (b)) ? (a) : (b))
  18. #define min(a, b)  (((a) < (b)) ? (a) : (b))
  19.  
  20. BOOL      ComputerThinking = false;
  21. BOOL      GotValidMove = false;
  22. COLORTYPE Player, Opponent;
  23. DEPTHTYPE Depth;
  24. LINETYPE  MainLine;
  25. MAXTYPE   MainEvalu;
  26. int       MaxDepth;
  27. int       LegalMoves;
  28. PIECETAB  PieceTab[2][16];
  29. WORD      MessageToPost;
  30. BOOL      NoComputerMove = false;
  31.  
  32. extern double WantedTime;
  33.  
  34. static MOVETYPE movetemp[MAXPLY - BACK + 2];
  35.  
  36. MOVETYPE* MovTab = &movetemp[-BACK];
  37.  
  38. #define TOLERANCE       8
  39. #define IF_EQMOVE(a, b) if (a.movpiece == b.movpiece && a.new1 == b.new1 &&\
  40.                             a.old == b.old && a.content == b.content &&\
  41.                             a.spe == b.spe)
  42.  
  43. struct INFTYPE {
  44.   short   principvar;         // Principal variation search
  45.   MAXTYPE value;              // Static incremental evaluation
  46.   MAXTYPE evaluation;         // Evaluation of position
  47. };
  48. enum MOVGENTYPE { mane, specialcap, kill, norml };  //  move type
  49. struct SEARCHTYPE {
  50.   LINETYPE   line;            // best line at next ply
  51.   short      capturesearch;   // indicates capture search
  52.   MAXTYPE    maxval;          // maximal evaluation returned in search
  53.   int        nextply;         // Depth of search at next ply
  54.   INFTYPE    next;            // information at Next ply
  55.   short      zerowindow;      // Zero-width alpha-beta-window
  56.   MOVGENTYPE movgentype;
  57. };
  58.  
  59. struct PARAMTYPE {
  60.   MAXTYPE     alpha;
  61.   MAXTYPE     beta;
  62.   int         ply;
  63.   INFTYPE*    inf;
  64.   MOVETYPE*   bestline;
  65.   SEARCHTYPE* s;
  66. };
  67.  
  68. //
  69. //  Global Variables for this module
  70. //
  71. MOVETYPE killingmove[MAXPLY+1][2];
  72. short    chcktb[MAXPLY+3];
  73. short*   checktab = &chcktb[1];
  74.  
  75. //  Square of eventual pawn on 7th rank
  76. EDGESQUARETYPE  passdpawn[MAXPLY+4];
  77. EDGESQUARETYPE* passedpawn = &passdpawn[2];
  78. BOOL            SkipSearch;
  79.  
  80.  
  81. inline void
  82. DisplayMove()
  83. {
  84.   if (!Depth) {
  85.     sprintf(buf, "%-7d%7s", MaxDepth, MoveStr(&MovTab[0]));
  86.     TInfo->SetDepthText(buf);
  87.   }
  88. }
  89.  
  90. //
  91. //  Initialize killingmove, checktab and passedpawn
  92. //
  93. static void
  94. clearkillmove()
  95. {
  96.   const SQUARETYPE rank7[2] = {0x60, 0x10};
  97.   DEPTHTYPE dep;
  98.   COLORTYPE col;
  99.   SQUARETYPE sq;
  100.   unsigned char i;
  101.  
  102.   for (dep = 0; dep <= MAXPLY; dep++)
  103.     for (i = 0; i < 2; i++)
  104.       killingmove[dep][i] = ZeroMove;
  105.   checktab[-1] = 0;
  106.   passedpawn[-2] = -1;  //  No check at first ply
  107.   passedpawn[-1] = -1;
  108.  
  109.   //  Place eventual pawns on 7th rank in passedpawn
  110.   for (col = white; col <= black; ((int)col)++)
  111.     for (sq = rank7[col]; sq <= rank7[col] + 7; sq++)
  112.       if ((Board[sq].piece == pawn) && (Board[sq].color == col))
  113.         if (col == Player)
  114.           passedpawn[-2] = sq;
  115.         else
  116.           passedpawn[-1] = sq;
  117. }
  118.  
  119. static DEPTHTYPE searchstatedepth;
  120.  
  121. //
  122. //  Backup the search and setup talk surroundings
  123. //
  124. static void
  125. getprogramstate()
  126. {
  127.   COLORTYPE oldplayer;
  128.  
  129.   searchstatedepth = Depth;
  130.   while (Depth > 0) {
  131.     Depth--;
  132.     oldplayer = Opponent;
  133.     Opponent = Player;
  134.     Player = oldplayer;
  135.     Perform(&MovTab[Depth], 1);
  136.   }
  137.   Depth--;
  138.   if (Opan)
  139.     TakeBackMove(&MovTab[Depth]);
  140. }
  141.  
  142.  
  143. //
  144. //  Restore the search surroundings
  145. //
  146. static void
  147. getsearchstate()
  148. {
  149.   COLORTYPE oldplayer;
  150.  
  151.   if (Opan) MakeMove(&MovTab[Depth+1]);
  152.   Depth++;
  153.   while (Depth < searchstatedepth) {
  154.     Perform(&MovTab[Depth], 0);
  155.     oldplayer = Player;
  156.     Player = Opponent;
  157.     Opponent = oldplayer;
  158.     Depth++;
  159.   }
  160. }
  161.  
  162. inline bool
  163. UsableMessage(MSG msg)
  164. {
  165.   if (msg.hwnd != hWndMain || msg.message != WM_COMMAND)
  166.     return false;
  167.   return true;
  168. }
  169.  
  170. static void
  171. MessageScan()
  172. {
  173.   MSG msg;
  174.   extern HACCEL hAccel;
  175.  
  176.   if (!::PeekMessage(&msg, hWndMain, 0, 0, PM_REMOVE))
  177.     return;
  178.   if (::TranslateAccelerator(hWndMain, hAccel, &msg)) {
  179.     PostMessage(hWndMain, WM_COMMAND, MessageToPost, 0L);
  180.     MessageToPost = 0;
  181.     SkipSearch = false;
  182.     return;
  183.   }
  184.  
  185.   if (Analysis) {
  186.     switch (msg.message) {
  187.       case WM_SETCURSOR:
  188.         DispatchMessage(&msg);
  189.         break;
  190.       case WM_COMMAND:
  191.         switch (msg.wParam) {
  192.           case CM_STOP:
  193.             SkipSearch = true;
  194.             AutoPlay = false;
  195.             break;
  196.         }
  197.         break;
  198.       default:
  199.         TranslateMessage(&msg);
  200.         DispatchMessage(&msg);
  201.         break;
  202.     }
  203.  
  204.   } else {
  205.     switch (msg.message) {
  206.       case WM_LBUTTONDOWN:
  207.         getprogramstate();
  208.         NoComputerMove = true;
  209.         GotValidMove = false;
  210.         DispatchMessage(&msg);
  211.         NoComputerMove = false;
  212.         if (Opan && !MultiMove && GotValidMove) {
  213.           IF_EQMOVE(KeyMove, MovTab[Depth + 1]) {
  214.             SkipSearch = false;
  215.             GotValidMove = false;
  216.             EnterKeyMove();
  217.             StartAnalysis();
  218.             PrintBestMove(&MainLine[0], MainEvalu);
  219.             ::SetMenu(hWndMain, ThinkMenu);
  220.             ::SetClassWindowCursor(hWndMain, hWaitCursor);
  221.  
  222.           } else
  223.             SkipSearch = true;
  224.         }
  225.         getsearchstate();
  226.         break;
  227.       default:
  228.         if (UsableMessage(msg)) {
  229.           SkipSearch = true;
  230.           if (msg.message != WM_PAINT)
  231.             PostMessage(msg.hwnd, msg.message, msg.wParam, msg.lParam);
  232.  
  233.         } else {
  234.           TranslateMessage(&msg);
  235.           DispatchMessage(&msg);
  236.         }
  237.         break;
  238.     }
  239.   }
  240. }
  241.  
  242.  
  243. static INFTYPE startinf;     //  Inf at first ply
  244. static MAXTYPE alphawindow;  //  alpha window value
  245. static MAXTYPE repeatevalu;  //  MainEvalu at ply one
  246.  
  247. static MAXTYPE search(MAXTYPE alpha, MAXTYPE beta, int ply, INFTYPE* inf,
  248.     MOVETYPE* bestline);
  249.  
  250. //
  251. //  Update killingmove using bestmove
  252. //
  253. inline void
  254. updatekill(MOVETYPE* bestmove)
  255. {
  256.   if (bestmove->movpiece != empty) {
  257.     // Update killingmove unless the move is a capture of last
  258.     // piece moved
  259.     if (MovTab[Depth - 1].movpiece == empty || bestmove->new1 != MovTab[Depth-1].new1)
  260.       if (killingmove[Depth][0].movpiece == empty || EqMove(bestmove, &killingmove[Depth][1])) {
  261.         killingmove[Depth][1] = killingmove[Depth][0];
  262.         killingmove[Depth][0] = *bestmove;
  263.  
  264.       } else if (!EqMove(bestmove, &killingmove[Depth][0]))
  265.         killingmove[Depth][1] = *bestmove;
  266.   }
  267. }
  268.  
  269. //
  270. //  Test if move has been generated before
  271. //
  272. short
  273. generatedbefore(PARAMTYPE* p)
  274. {
  275.   if (p->s->movgentype != mane) {
  276.     IF_EQMOVE(MovTab[Depth], p->bestline[Depth])
  277.       return 1;
  278.  
  279.     if (!p->s->capturesearch)
  280.       if (p->s->movgentype != kill)
  281.         for (char i = 0; i < 2; i++)
  282.           IF_EQMOVE(MovTab[Depth], killingmove[Depth][i])
  283.             return 1;
  284.   }
  285.   return 0;
  286. }
  287.  
  288. //
  289. //  Test cut-off.  Cutval cantains the maximal possible evaluation
  290. //
  291. inline short
  292. cut(MAXTYPE cutval, PARAMTYPE* p)
  293. {
  294.   short ct = 0;
  295.  
  296.   if (cutval <= p->alpha) {
  297.     ct = 1;
  298.     if (p->s->maxval < cutval)
  299.       p->s->maxval = cutval;
  300.   }
  301.   return ct;
  302. }
  303.  
  304. //
  305. //  Perform move, calculate evaluation, test cut-off, etc
  306. //
  307. static short
  308. update(PARAMTYPE* p)
  309. {
  310.   short selection;
  311.  
  312.   IncNode(&Nodes);
  313.   p->s->nextply = p->ply - 1;    //  Calculate next ply
  314.   if (Level == matesearch) {     //  Matesearch
  315.     Perform(&MovTab[Depth], 0);  //  Perform Move on the board
  316.     //  Check if Move is legal
  317.     if (Attacks(Opponent, PieceTab[Player][0].isquare))
  318.       goto TAKEBACKMOVE;
  319.     if (!Depth)
  320.       LegalMoves++;
  321.     checktab[Depth] = 0;
  322.     passedpawn[Depth] = -1;
  323.     p->s->next.value = p->s->next.evaluation = 0;
  324.     if (p->s->nextply <= 0) {    //  Calculate chech and perform evt. cut-off
  325.       if (!p->s->nextply)
  326.         checktab[Depth] = Attacks(Player,
  327.           PieceTab[Opponent][0].isquare);
  328.       if (!checktab[Depth])
  329.         if (cut(p->s->next.value, p))
  330.           goto TAKEBACKMOVE;
  331.     }
  332.     goto ACCEPTMOVE;
  333.   }
  334.  
  335.   //  Make special limited capturesearch at first iteration
  336.   //
  337.   if (MaxDepth <= 1)
  338.     if (p->s->capturesearch && Depth >= 2)
  339.       if (!(MovTab[Depth].content < MovTab[Depth].movpiece ||
  340.             p->s->movgentype == specialcap ||
  341.             MovTab[Depth].old == MovTab[Depth-2].new1))
  342.         goto CUTMOVE;
  343.  
  344.   //  Calculate nxt static incremental evaluation
  345.   p->s->next.value = -p->inf->value + StatEvalu(&MovTab[Depth]);
  346.  
  347.   //  Calculate checktab (only checks with moved piece are calculated)
  348.   //  Giving Check does not count as a ply
  349.   checktab[Depth] = PieceAttacks(MovTab[Depth].movpiece, Player,
  350.     MovTab[Depth].new1, PieceTab[Opponent][0].isquare);
  351.   if (checktab[Depth])
  352.     p->s->nextply = p->ply;
  353.  
  354.   //  Calculate passedpawn.  Moving a pawn to 7th rank does not
  355.   //  count as a ply
  356.   passedpawn[Depth] = passedpawn[Depth - 2];
  357.   if (MovTab[Depth].movpiece == pawn)
  358.     if (MovTab[Depth].new1 < 0x18 || MovTab[Depth].new1 >= 0x60) {
  359.       passedpawn[Depth] = MovTab[Depth].new1;
  360.       p->s->nextply = p->ply;
  361.     }
  362.  
  363.   //  Perform selection at last ply and in capture search
  364.   selection = (p->s->nextply <= 0 && !checktab[Depth] && Depth > 0);
  365.   if (selection)   //  check evaluation
  366.     if (cut(p->s->next.value + 0, p))
  367.       goto CUTMOVE;
  368.   Perform(&MovTab[Depth], 0);  //  perform move on the board
  369.  
  370.   //  check if move is legal
  371.   if (Attacks(Opponent, PieceTab[Player][0].isquare))
  372.     goto TAKEBACKMOVE;
  373.   if (passedpawn[Depth] >= 0)  //  check passedpawn
  374.     if (Board[passedpawn[Depth]].piece != pawn ||
  375.         Board[passedpawn[Depth]].color != Player)
  376.       passedpawn[Depth] = -1;
  377.   if (!Depth) {
  378.     LegalMoves++;
  379.     p->s->next.value += random(4);
  380.   }
  381.   p->s->next.evaluation = p->s->next.value;
  382.  
  383. ACCEPTMOVE:
  384.   if (Analysis)
  385.     DisplayMove();
  386.   return 0;
  387.  
  388. TAKEBACKMOVE:
  389.   Perform(&MovTab[Depth], 1);
  390.  
  391. CUTMOVE:
  392.   if (Analysis)
  393.     DisplayMove();
  394.   return 1;
  395. }
  396.  
  397. //
  398. //  Calculate draw bonus/penalty, and set draw if the game is a draw
  399. //
  400. static short
  401. drawgame(SEARCHTYPE* s)
  402. {
  403.   int        drawcount;
  404.   REPEATTYPE searchrepeat;
  405.   FIFTYTYPE  searchfifty;
  406.  
  407.   if (Depth == 1) {
  408.     searchfifty = FiftyMoveCnt();
  409.     searchrepeat = Repetition(0);
  410.     if (searchrepeat >= 3) {
  411.       s->next.evaluation = 0;
  412.       return 1;
  413.     }
  414.     drawcount = 0;
  415.     if (searchfifty >= 96)         //  48 moves without pawn moves or captures
  416.       drawcount = 3;
  417.     else {
  418.       if (searchrepeat >= 2)       //  2nd repetition
  419.         drawcount = 2;
  420.       else if (searchfifty >= 20)  //  10 moves without pawn moves or
  421.          drawcount = 1;            //  captures
  422.     }
  423.     s->next.value += (repeatevalu / 4) * drawcount;
  424.     s->next.evaluation += (repeatevalu / 4 ) * drawcount;
  425.   }
  426.   if (Depth >= 3) {
  427.     searchrepeat = Repetition(1);
  428.     if (searchrepeat >= 2) {       //  Immediate repetition counts as a draw
  429.       s->next.evaluation = 0;
  430.       return 1;
  431.     }
  432.   }
  433.   return 0;
  434. }
  435.  
  436.  
  437. //
  438. //  Update bestline and MainEvalu using line and maxval
  439. //
  440. inline void
  441. updatebestline(PARAMTYPE *p)
  442. {
  443.   memcpy(p->bestline, &p->s->line[0], sizeof(LINETYPE));
  444.   // *bestline = p->s->line;
  445.   p->bestline[Depth] = MovTab[Depth];
  446.   if (!Depth) {
  447.     MainEvalu = p->s->maxval;
  448.     if (Level == matesearch)
  449.       p->s->maxval = alphawindow;
  450.     if (Analysis) PrintBestMove(&MainLine[0], MainEvalu);
  451.   }
  452. }
  453.  
  454. //
  455. //  The inner loop of the search procedure.  MovTab[Depth] contains the move.
  456. //
  457. static BOOL
  458. loopbody(PARAMTYPE* p)
  459. {
  460.   COLORTYPE oldplayer;
  461.   BOOL     lastanalysis;
  462.  
  463.   if (generatedbefore(p))
  464.     return 0;
  465.   if (Depth < MAXPLY) {
  466.     p->s->line[Depth + 1] = ZeroMove;
  467.     if (p->s->movgentype == mane)
  468.       memmove(&p->s->line[0], p->bestline, sizeof(LINETYPE));
  469.     // p->s->line = *bestline;
  470.   }
  471.   //  Principvar indicates principal variation search
  472.   //  Zerowindow indicates zero - width alpha - beta window
  473.   p->s->next.principvar = 0;
  474.   p->s->zerowindow = 0;
  475.   if (p->inf->principvar)
  476.     if (p->s->movgentype == mane)
  477.       p->s->next.principvar = p->bestline[Depth+1].movpiece != empty;
  478.     else
  479.       p->s->zerowindow = p->s->maxval >= p->alpha;
  480.  
  481. REPEATSEARCH:
  482.   if (update(p))
  483.     return 0;
  484.   if (Level == matesearch)   //  stop evt. search
  485.     if (p->s->nextply <= 0 && !checktab[Depth])
  486.       goto NOTSEARCH;
  487.   if (drawgame(p->s))
  488.     goto NOTSEARCH;
  489.   if (Depth >= MAXPLY)
  490.     goto NOTSEARCH;
  491.  
  492.   //  Analyse nextply using a recursive call to search
  493.   oldplayer = Player;
  494.   Player = Opponent;
  495.   Opponent = oldplayer;
  496.   Depth++;
  497.   if (p->s->zerowindow)
  498.     p->s->next.evaluation = -search(-p->alpha - 1, -p->alpha, p->s->nextply,
  499.         &p->s->next, &p->s->line[0]);
  500.   else
  501.     p->s->next.evaluation = -search(-p->beta, -p->alpha, p->s->nextply,
  502.         &p->s->next, &p->s->line[0]);
  503.   Depth--;
  504.   oldplayer = Opponent;
  505.   Opponent = Player;
  506.   Player = oldplayer;
  507.  
  508. NOTSEARCH:
  509.   Perform(&MovTab[Depth], 1);  //  take back move
  510.   if (SkipSearch)
  511.     return 1;
  512.   lastanalysis = Analysis;     //  scan messages and test SkipSearch
  513.   MessageScan();
  514.   if (!SkipSearch)
  515.     if (Analysis && !SingleStep && (!Depth || !lastanalysis)) {
  516.       StopTime(&ChessClock);
  517.       if (MainEvalu > alphawindow)
  518.         SkipSearch = ChessClock.totaltime >= WantedTime * 1.5;
  519.     }
  520.   if (Analysis && MaxDepth <= 1)
  521.     SkipSearch = 0;
  522.   p->s->maxval = max(p->s->maxval, p->s->next.evaluation);  //  Update Maxval
  523.   IF_EQMOVE(p->bestline[Depth], MovTab[Depth])         //  Update evt. bestline
  524.     updatebestline(p);
  525.   if (p->alpha < p->s->maxval) {               //  update alpha and test cutoff
  526.     updatebestline(p);
  527.     if (p->s->maxval >= p->beta)
  528.       return 1;
  529.     //  Adjust maxval (tolerance search)
  530.     if (p->ply >= 2 && p->inf->principvar && !p->s->zerowindow)
  531.       p->s->maxval = min(p->s->maxval + TOLERANCE, p->beta - 1);
  532.     p->alpha = p->s->maxval;
  533.     if (p->s->zerowindow && ! SkipSearch) {
  534.       //  repeat search with full window
  535.       p->s->zerowindow = 0;
  536.       goto REPEATSEARCH;
  537.     }
  538.   }
  539.   return SkipSearch;
  540. }
  541.  
  542. //
  543. //  generate  pawn promotions
  544. //
  545. static short
  546. pawnpromotiongen(PARAMTYPE* p)
  547. {
  548.   MovTab[Depth].spe = 1;
  549.   for (PIECETYPE promote = queen; promote <= knight; ((int)promote)++) {
  550.     MovTab[Depth].movpiece = promote;
  551.     if (loopbody(p))
  552.       return 1;
  553.   }
  554.   MovTab[Depth].spe = 0;
  555.   return 0;
  556. }
  557.  
  558. //
  559. //  Generate captures of the piece on Newsq
  560. //
  561. static short
  562. capmovgen(SQUARETYPE newsq, PARAMTYPE* p)
  563. {
  564.   MovTab[Depth].content = Board[newsq].piece;
  565.   MovTab[Depth].spe = 0;
  566.   MovTab[Depth].new1 = newsq;
  567.   MovTab[Depth].movpiece = pawn;  //  pawn captures
  568.   EDGESQUARETYPE nxtsq = MovTab[Depth].new1 - PawnDir[Player];
  569.  
  570.   for (EDGESQUARETYPE sq = nxtsq - 1; sq <= nxtsq + 1; sq++)
  571.     if (sq != nxtsq)
  572.       if (!(sq & 0x88))
  573.         if (Board[sq].piece == pawn && Board[sq].color == Player) {
  574.           MovTab[Depth].old = sq;
  575.           if (MovTab[Depth].new1 < 8 || MovTab[Depth].new1 >= 0x70) {
  576.             if (pawnpromotiongen(p))
  577.               return 1;
  578.           } else if (loopbody(p))
  579.             return 1;
  580.         }
  581.  
  582.   for (INDEXTYPE i = OfficerNo[Player]; i >= 0; i--)  //  other captures
  583.     if (PieceTab[Player][i].ipiece != empty &&
  584.         PieceTab[Player][i].ipiece != pawn)
  585.       if (PieceAttacks(PieceTab[Player][i].ipiece, Player,
  586.           PieceTab[Player][i].isquare, newsq)) {
  587.         MovTab[Depth].old = PieceTab[Player][i].isquare;
  588.         MovTab[Depth].movpiece = PieceTab[Player][i].ipiece;
  589.         if (loopbody(p))
  590.           return 1;
  591.       }
  592.   return 0;
  593. }
  594.  
  595. //
  596. //  Generates non captures for the piece on oldsq
  597. //
  598. static short
  599. noncapmovgen(SQUARETYPE oldsq, PARAMTYPE* p)
  600. {
  601.   DIRTYPE first, last, dir;
  602.   int direction;
  603.   EDGESQUARETYPE newsq;
  604.  
  605.   MovTab[Depth].spe = 0;
  606.   MovTab[Depth].old = oldsq;
  607.   MovTab[Depth].movpiece = Board[oldsq].piece;
  608.   MovTab[Depth].content = empty;
  609.  
  610.   switch (MovTab[Depth].movpiece) {
  611.     case king:
  612.       for (dir = 7; dir >= 0; dir--) {
  613.         newsq = MovTab[Depth].old + DirTab[dir];
  614.         if (!(newsq & 0x88))
  615.           if (Board[newsq].piece == empty) {
  616.             MovTab[Depth].new1 = newsq;
  617.             if (loopbody(p))
  618.                return 1;
  619.           }
  620.       }
  621.       break;
  622.  
  623.     case knight:
  624.       for (dir = 7; dir >= 0; dir--) {
  625.         newsq = MovTab[Depth].old + KnightDir[dir];
  626.         if (!(newsq & 0x88))
  627.           if (Board[newsq].piece == empty) {
  628.             MovTab[Depth].new1 = newsq;
  629.             if (loopbody(p))
  630.               return 1;
  631.           }
  632.       }
  633.       break;
  634.  
  635.     case queen:
  636.     case rook :
  637.     case bishop:
  638.       first = 7;
  639.       last = 0;
  640.       if (MovTab[Depth].movpiece == rook)
  641.         first = 3;
  642.       else if (MovTab[Depth].movpiece == bishop)
  643.         last = 4;
  644.       for (dir = first; dir >= last; dir--) {
  645.         direction = DirTab[dir];
  646.         newsq = MovTab[Depth].old + direction;
  647.         while (!(newsq & 0x88)) {
  648.           if (Board[newsq].piece != empty)
  649.             goto TEN;
  650.           MovTab[Depth].new1 = newsq;
  651.           if (loopbody(p))
  652.             return 1;
  653.           newsq = MovTab[Depth].new1 + direction;
  654.         }
  655. TEN:
  656.         continue;
  657.       }
  658.       break;
  659.  
  660.     case pawn:
  661.       //  One square forward
  662.       MovTab[Depth].new1 = MovTab[Depth].old + PawnDir[Player];
  663.       if (Board[MovTab[Depth].new1].piece == empty)
  664.         if (MovTab[Depth].new1 < 8 || MovTab[Depth].new1 >= 0x70) {
  665.           if (pawnpromotiongen(p))
  666.             return 1;
  667.         } else {
  668.           if (loopbody(p))
  669.             return 1;
  670.           if (MovTab[Depth].old < 0x18 || MovTab[Depth].old >= 0x60) {
  671.             //  two squares forward
  672.             MovTab[Depth].new1 += MovTab[Depth].new1 - MovTab[Depth].old;
  673.             if (Board[MovTab[Depth].new1].piece == empty)
  674.               if (loopbody(p))
  675.                 return 1;
  676.           }
  677.         }
  678.   }
  679.   return 0;
  680. }
  681.  
  682. //
  683. //  castling moves
  684. //
  685. static short
  686. castlingmovgen(PARAMTYPE* p)
  687. {
  688.   MovTab[Depth].spe = 1;
  689.   MovTab[Depth].movpiece = king;
  690.   MovTab[Depth].content = empty;
  691.  
  692.   for (CASTDIRTYPE castdir = (CASTDIRTYPE)(lng-1); castdir <= shrt-1; ((int)castdir)++) {
  693.     MovTab[Depth].new1 = CastMove[Player][castdir].castnew;
  694.     MovTab[Depth].old = CastMove[Player][castdir].castold;
  695.     if (KillMovGen(&MovTab[Depth]))
  696.       if (loopbody(p))
  697.         return 1;
  698.   }
  699.   return 0;
  700. }
  701.  
  702. //
  703. //  e.p. captures
  704. //
  705. static short
  706. epcapmovgen(PARAMTYPE* p)
  707. {
  708.   if (MovTab[Depth-1].movpiece == pawn)
  709.     if (abs(MovTab[Depth-1].new1 - MovTab[Depth-1].old) >= 0x20) {
  710.       MovTab[Depth].spe = 1;
  711.       MovTab[Depth].movpiece = pawn;
  712.       MovTab[Depth].content = empty;
  713.       MovTab[Depth].new1 = (MovTab[Depth - 1].new1 + MovTab[Depth - 1].old) / 2;
  714.       for (EDGESQUARETYPE sq = MovTab[Depth - 1].new1 - 1; sq <= MovTab[Depth - 1].new1 + 1; sq++)
  715.         if (sq != MovTab[Depth-1].new1)
  716.           if (!(sq & 0x88)) {
  717.             MovTab[Depth].old = sq;
  718.             if (KillMovGen(&MovTab[Depth]))
  719.               if (loopbody(p))
  720.                 return 1;
  721.           }
  722.     }
  723.   return 0;
  724. }
  725.  
  726. //
  727. //  Generate the next move to be analysed.
  728. //  Controls the order of the movegeneration.
  729. //  The moves are generated in the order:
  730. //    Main variation
  731. //    Captures of last moved piece
  732. //    Killing moves
  733. //    Other captures
  734. //    Pawnpromovtions
  735. //    Castling
  736. //    Normal moves
  737. //    E.p. captures
  738. //
  739. static void
  740. searchmovgen(PARAMTYPE* p)
  741. {
  742.   INDEXTYPE index;
  743.   char killno;
  744.  
  745.   //  generate move from main variation
  746.   if (p->bestline[Depth].movpiece != empty) {
  747.     MovTab[Depth] = p->bestline[Depth];
  748.     p->s->movgentype = mane;
  749.     if (loopbody(p))
  750.       return;
  751.   }
  752.   if (MovTab[Depth-1].movpiece != empty)
  753.     if (MovTab[Depth-1].movpiece != king) {
  754.       p->s->movgentype = specialcap;
  755.       if (capmovgen(MovTab[Depth-1].new1, p))
  756.         return;
  757.     }
  758.   p->s->movgentype = kill;
  759.   if (!p->s->capturesearch)
  760.     for (killno = 0; killno <= 1; killno++) {
  761.       MovTab[Depth] = killingmove[Depth][killno];
  762.       if (MovTab[Depth - 1].movpiece != empty)
  763.         if (KillMovGen(&MovTab[Depth]))
  764.           if (loopbody(p))
  765.             return;
  766.     }
  767.   p->s->movgentype = norml;
  768.   for (index = 1; index <= PawnNo[Opponent]; index++)
  769.     if (PieceTab[Opponent][index].ipiece != empty)
  770.       if (MovTab[Depth-1].movpiece == empty ||
  771.           PieceTab[Opponent][index].isquare != MovTab[Depth-1].new1)
  772.         if (capmovgen(PieceTab[Opponent][index].isquare, p))
  773.           return;
  774.   if (p->s->capturesearch) {
  775.     if (passedpawn[Depth-2] >= 0)
  776.       if (Board[passedpawn[Depth-2]].piece == pawn &&
  777.           Board[passedpawn[Depth-2]].color == Player)
  778.         if (noncapmovgen(passedpawn[Depth-2], p))
  779.           return;
  780.   }
  781.   if (!p->s->capturesearch) {        //  non-captures
  782.     if (castlingmovgen(p))
  783.       return;                        //  castling
  784.     for (index = PawnNo[Player]; index >= 0; index--)
  785.       if (PieceTab[Player][index].ipiece != empty)
  786.         if (noncapmovgen(PieceTab[Player][index].isquare, p))
  787.           return;
  788.   }
  789.   if (epcapmovgen(p))
  790.     return;  //  e.p. captures
  791. }
  792.  
  793. //
  794. //  Perform the search
  795. //  On entry:
  796. //   Player is next to move
  797. //   MovTab[Depth-1] contains last move
  798. //   alpha, beta contains the alpha - beta window
  799. //   ply contains the Depth of the search
  800. //   inf contains various information
  801. //
  802. //  On exit:
  803. //   Bestline contains the principal variation
  804. //   search contains the evaluation for Player
  805. //
  806. static MAXTYPE
  807. search(MAXTYPE alpha, MAXTYPE beta, int ply, INFTYPE* inf, MOVETYPE* bestline)
  808. {
  809.   SEARCHTYPE s;
  810.   PARAMTYPE p;
  811.   //  Perform capturesearch if ply <= 0 and !check
  812.   s.capturesearch = ply <= 0 && !checktab[Depth-1];
  813.   if (s.capturesearch) {  //  initialize maxval
  814.     s.maxval = -inf->evaluation;
  815.     if (alpha < s.maxval) {
  816.       alpha = s.maxval;
  817.       if (s.maxval >= beta)
  818.         goto STOP;
  819.     }
  820.   } else
  821.     s.maxval = -(LOSEVALUE - Depth*DEPTHFACTOR);
  822.   p.alpha = alpha;
  823.   p.beta = beta;
  824.   p.ply = ply;
  825.   p.inf = inf;
  826.   p.bestline = bestline;
  827.   p.s = &s;
  828.   searchmovgen(&p);   //  The search loop
  829.   if (SkipSearch)
  830.     goto STOP;
  831.   if (s.maxval == -(LOSEVALUE - Depth * DEPTHFACTOR))   //  Test stalemate
  832.     if (!Attacks(Opponent, PieceTab[Player][0].isquare)) {
  833.       s.maxval = 0;
  834.       goto STOP;
  835.     }
  836.   updatekill(&bestline[Depth]);
  837.  
  838. STOP:
  839.   return s.maxval;
  840. }
  841.  
  842. //
  843. //  Begin the search
  844. //
  845. static MAXTYPE
  846. callsearch(MAXTYPE alpha, MAXTYPE beta)
  847. {
  848.   startinf.principvar = MainLine[0].movpiece != empty;
  849.   LegalMoves = 0;
  850.   MAXTYPE maxval = search(alpha, beta, MaxDepth, &startinf, &MainLine[0]);
  851.   if (!LegalMoves)
  852.     MainEvalu = maxval;
  853.   return maxval;
  854. }
  855.  
  856. //
  857. //  Checks whether the search time is used
  858. //
  859. inline short
  860. timeused()
  861. {
  862.   if (Analysis && !SingleStep) {
  863.     StopTime(&ChessClock);
  864.     return ChessClock.totaltime >= WantedTime;
  865.   }
  866.   return 0;
  867. }
  868.  
  869. //
  870. //  setup search
  871. //
  872. void
  873. FindMove(int maxlevel)
  874. {
  875.   MAXTYPE maxval;
  876.   double calcpvtime;
  877.   InitTime(&ChessClock);
  878.   StartTime(&ChessClock);
  879.   InitNode(&Nodes);
  880.   SkipSearch = 0;
  881.   clearkillmove();
  882.   CalcPVTable();
  883.   StopTime(&ChessClock);
  884.   calcpvtime = ChessClock.totaltime;
  885.   startinf.value = startinf.evaluation = -RootValue;
  886.   MaxDepth = 0;
  887.   MainLine[0] = ZeroMove;
  888.   MainEvalu = RootValue;
  889.   alphawindow = MAXINT;
  890.   ComputerThinking = TRUE;
  891.  
  892.   do {
  893.     //  update various variables
  894.     if (MaxDepth <= 1)
  895.       repeatevalu = MainEvalu;
  896.     alphawindow = min(alphawindow, MainEvalu - 0x80);
  897.     if (Level == matesearch) {
  898.       alphawindow = 0x6000;
  899.       if (MaxDepth > 0) MaxDepth++;
  900.     }
  901.     MaxDepth++;
  902.     maxval = callsearch(alphawindow, 0x7f00);  //  perform the search
  903.     if (maxval <= alphawindow && !SkipSearch && Level != matesearch &&
  904.         LegalMoves > 0) {
  905.       //  Repeat the search if the value falls below the
  906.       //  alpha-window
  907.       MainEvalu = alphawindow;
  908.       LegalMoves = 2;
  909.     }
  910.   } while (!SkipSearch && !timeused() && MaxDepth < maxlevel &&
  911.       LegalMoves > 1 && abs(MainEvalu) < MATEVALUE - 24 * DEPTHFACTOR);
  912.  
  913.   ComputerThinking = FALSE;
  914.   StopTime(&ChessClock);
  915.  
  916.   if (Analysis)
  917.     PrintNodes(&Nodes, ChessClock.totaltime - calcpvtime);
  918. }
  919.