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