home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c082_122 / 3.ddi / CHESS.ZIP / MOVGEN.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-10  |  16.4 KB  |  583 lines
  1. // ObjectWindows - (C) Copyright 1992 by Borland International
  2.  
  3. #include <math.h>
  4. #include "wcdefs.h"
  5. #include "externs.h"
  6.  
  7. /*
  8.  *  Globals
  9.  */
  10.  
  11. static ATTACKTABTYPE attack[240];
  12. ATTACKTABTYPE *AttackTab = &attack[120];
  13. SETOFPIECE BitTab[7] = {0, 1, 2, 4, 8, 0x10, 0x20};
  14. int DirTab[8] = { 1, -1, 0x10, -0x10, 0x11, -0x11, 0x0f, -0x0f};
  15. int KnightDir[8] = {0x0E, -0x0E, 0x12, -0x12, 0x1f, -0x1f, 0x21, -0x21};
  16. int PawnDir[2] = {0x10, -0x10};
  17. MOVETYPE Next;
  18. int BufCount, BufPnt;
  19. MOVETYPE Buffer[81];
  20. CASTMOVETYPE  CastMove[2][2] = { {{2, 4}, {6, 4}}, {{0x72, 0x74}, {0x76, 0x74}} };
  21.  
  22.  
  23. void CalcAttackTab(void)
  24. {
  25.     DIRTYPE dir;
  26.     int sq;
  27.     unsigned char i;
  28.  
  29.     for (sq = -0x77; sq <= 0x77; sq++)
  30.     {
  31.         AttackTab[sq].pieceset = 0;
  32.         AttackTab[sq].direction = 0;        
  33.     }
  34.     for (dir = 7; dir >=0; dir--)
  35.     {
  36.         for (i = 1; i < 8; i++)
  37.         {
  38.             if (dir < 4)
  39.                 AttackTab[DirTab[dir]*i].pieceset = BitTab[queen]+BitTab[rook];
  40.             else
  41.                 AttackTab[DirTab[dir]*i].pieceset = BitTab[queen]+BitTab[bishop];
  42.             AttackTab[DirTab[dir]*i].direction = DirTab[dir];
  43.         }
  44.         AttackTab[DirTab[dir]].pieceset += BitTab[king];
  45.         AttackTab[KnightDir[dir]].pieceset = BitTab[knight];
  46.         AttackTab[KnightDir[dir]].direction = KnightDir[dir];
  47.     }
  48. }
  49.  
  50.  
  51. /*
  52.  *  calculate whether apiece placed on asquare attacks the square
  53.  */
  54.  
  55. short PieceAttacks(PIECETYPE apiece, COLORTYPE acolor,
  56.                      SQUARETYPE asquare, SQUARETYPE square)
  57. {
  58.     EDGESQUARETYPE sq;
  59.     int x;
  60.  
  61.     x = square - asquare;
  62.     if (apiece == pawn)   /*  pawn attacks  */
  63.         return (abs(x - PawnDir[acolor]) == 1);
  64.     /*  other attacks: can the piece move to the square?  */
  65.     else if (AttackTab[x].pieceset & BitTab[apiece])
  66.     {
  67.         if (apiece == king || apiece == knight)
  68.             return 1;
  69.         else
  70.         {
  71.         /*  are there any blocking pieces in between?  */
  72.             sq = asquare;
  73.             do
  74.             {
  75.                 sq += AttackTab[x].direction;
  76.             } while (sq != square && Board[sq].piece == empty );
  77.             return (sq == square);
  78.         }
  79.     }
  80.     else
  81.         return 0;
  82. }
  83.  
  84.  
  85. /*
  86.  *  calculate whether acolor attacks the square with at pawn
  87.  */
  88.  
  89. short PawnAttacks(COLORTYPE acolor, SQUARETYPE square)
  90. {
  91.     EDGESQUARETYPE sq;
  92.  
  93.     sq = square - PawnDir[acolor] - 1;  /*  left square  */
  94.     if (!(sq & 0x88))
  95.         if (Board[sq].piece == pawn && Board[sq].color == acolor)
  96.             return 1;
  97.     sq += 2;   /*  right square  */
  98.     if (!(sq & 0x88))
  99.         if (Board[sq].piece == pawn && Board[sq].color == acolor)
  100.             return 1;
  101.     return 0;
  102. }
  103.  
  104.  
  105. /*
  106.  *  Calculates whether acolor attacks the square
  107.  */
  108.  
  109. short Attacks(COLORTYPE acolor, SQUARETYPE square)
  110. {
  111.     INDEXTYPE i;
  112.  
  113.     if (PawnAttacks(acolor, square))    /*  pawn attacks  */
  114.         return 1;
  115.     /*  Other attacks:  try all pieces, starting with the smallest  */
  116.     for (i = OfficerNo[acolor]; i >= 0; i--)
  117.         if (PieceTab[acolor][i].ipiece != empty)
  118.             if (PieceAttacks(PieceTab[acolor][i].ipiece, acolor,
  119.                     PieceTab[acolor][i].isquare, square))
  120.                 return 1;
  121.     return 0;
  122. }
  123.  
  124.  
  125. /*
  126.  *  check whether inpiece is placed on square and has never moved
  127.  */
  128.  
  129. short Check(SQUARETYPE square, PIECETYPE inpiece, COLORTYPE incolor)
  130. {
  131.     DEPTHTYPE dep;
  132.  
  133.     if(Board[square].piece == inpiece && Board[square].color == incolor)
  134.     {
  135.         dep = Depth - 1;
  136.         while (MovTab[dep].movpiece != empty)
  137.         {
  138.             if (MovTab[dep].new1 == square)
  139.                 return 0;
  140.             dep--;
  141.         }
  142.         return 1;
  143.     }
  144.     return 0;
  145. }
  146.  
  147.  
  148. /*
  149.  *  Calculate whether incolor can castle
  150.  */
  151.  
  152. void CalcCastling(COLORTYPE incolor,  CASTDIRTYPE *cast)
  153. {
  154.     SQUARETYPE square = 0;
  155.  
  156.     if (incolor == black) square = 0x70;
  157.     *cast = zero;
  158.     if (Check(square + 4, king, incolor))  /*  check king  */
  159.     {
  160.         if (Check(square, rook, incolor))
  161.             ((int)*cast) += lng;  /*  check a-rook  */
  162.         if (Check(square + 7, rook, incolor))
  163.             ((int)*cast) += shrt;  /*  check h-rook  */
  164.     }
  165. }
  166.  
  167.  
  168. /*
  169.  *  check if move is a pawn move or a capture
  170.  */
  171.  
  172. inline short RepeatMove(MOVETYPE *move)
  173. {
  174.     return (move->movpiece != empty && move->movpiece != pawn &&
  175.               move->content == empty && !move->spe);
  176. }
  177.  
  178. /****************************************************************************/
  179.  
  180. /*
  181.  *  Count the number of moves since last capture or pawn move
  182.  *  The game is a draw when fiftymovecnt = 100
  183.  */
  184.  
  185. FIFTYTYPE FiftyMoveCnt(void)
  186. {
  187.     FIFTYTYPE cnt = 0;
  188.  
  189.     while (RepeatMove(&MovTab[Depth - cnt]))
  190.         cnt++;
  191.     return cnt;
  192. }
  193.  
  194.  
  195. /*
  196.  *  Calculate how many times the position has occured before
  197.  *  The game is a draw when repetition = 3;
  198.  *  movetab[back..Depth] contains the previous moves
  199.  *  When immediate is set, only immediate repetion is checked
  200.  */
  201.  
  202. REPEATTYPE Repetition(short immediate)
  203. {
  204.     DEPTHTYPE lastdep, compdep, tracedep, checkdep, samedepth;
  205.     SQUARETYPE tracesq, checksq;
  206.     REPEATTYPE repeatcount;
  207.  
  208.     repeatcount = 1;
  209.     lastdep = samedepth = Depth + 1;    /*  current postion  */
  210.     compdep = samedepth - 4;            /*  First position to compare  */
  211.  
  212.     /*  MovTab[lastdep..Depth] contains previous relevant moves  */
  213.     while (RepeatMove(&MovTab[lastdep - 1]) && (compdep < lastdep ||
  214.                  !immediate))
  215.         lastdep--;
  216.     if (compdep < lastdep)
  217.         return repeatcount;
  218.     checkdep = samedepth;
  219.     do
  220.     {
  221.         checkdep--;
  222.         checksq = MovTab[checkdep].new1;
  223.         for (tracedep = checkdep + 2; tracedep < samedepth; tracedep += 2)
  224.             if (MovTab[tracedep].old == checksq) goto TEN;
  225.  
  226.         /*  Trace the move backward to see if it has been 'undone' earlier  */
  227.         tracedep = checkdep;
  228.         tracesq = MovTab[tracedep].old;
  229.         do
  230.         {
  231.             if (tracedep-2 < lastdep) return repeatcount;
  232.             tracedep -= 2;
  233.             /*  Check if piece has been moved before  */
  234.             if (tracesq == MovTab[tracedep].new1) tracesq =
  235.                     MovTab[tracedep].old;
  236.         } while (tracesq != checksq || tracedep > compdep + 1);
  237.         if (tracedep < compdep)    /*  Adjust evt. compdep  */
  238.         {
  239.             compdep = tracedep;
  240.             if ((samedepth - compdep) % 2 == 1)
  241.             {
  242.                 if (compdep == lastdep) return repeatcount;
  243.                 compdep --;
  244.             }
  245.             checkdep = samedepth;
  246.         }
  247.         /*  All moves between SAMEDEP and compdep have been checked,
  248.             so a repetition is found  */
  249. TEN :   if (checkdep <= compdep)
  250.         {
  251.             repeatcount++;
  252.             if (compdep - 2 < lastdep) return repeatcount;
  253.             checkdep = samedepth = compdep;
  254.             compdep -= 2;
  255.         }
  256.     } while (1);
  257. }
  258.  
  259.  
  260. /*
  261.  *  Test whether a move is possible
  262.  *
  263.  *  On entry:
  264.  *    Move contains a full description of a move, which
  265.  *    has been legally generated in a different position.
  266.  *    MovTab[Depth - 1] contains last performed move.
  267.  *
  268.  *  On exit:
  269.  *    KillMovGen indicates whether the move is possible
  270.  */
  271.  
  272. short KillMovGen(MOVETYPE *move)
  273. {
  274.     SQUARETYPE castsq;
  275.     PIECETYPE promote;
  276.     CASTDIRTYPE castdir;
  277.     CASTTYPE cast;
  278.     short killmov;
  279.  
  280.     killmov = 0;
  281.     if (move->spe && (move->movpiece == king))
  282.     {
  283.         CalcCastling(Player, &cast);     /*  Castling  */
  284.         if (move->new1 > move->old)
  285.             castdir = shrt;
  286.         else
  287.             castdir = lng;
  288.  
  289.         if (cast & castdir)    /*  Has king or rook moved before  */
  290.         {
  291.             castsq = (int)((move->new1 + move->old) / 2);
  292.             /*  Are the squares empty ?  */
  293.             if  (Board[move->new1].piece == empty)
  294.               if (Board[castsq].piece == empty)
  295.                 if ((move->new1 > move->old) || (Board[move->new1-1].piece
  296.                              == empty))
  297.                   /*  Are the squares unattacked  */
  298.                   if (!Attacks(Opponent, move->old))
  299.                     if (!Attacks(Opponent, move->new1))
  300.                       if (!Attacks(Opponent, castsq))
  301.                         killmov = 1;
  302.         }
  303.     }
  304.     else
  305.     {
  306.     if (move->spe && (move->movpiece == pawn))
  307.     {
  308.             /*  E.p. capture  */
  309.             /*  Was the Opponent's move a 2 square move?  */
  310.         if (MovTab[Depth-1].movpiece == pawn)
  311.             if (abs(MovTab[Depth-1].new1 - MovTab[Depth-1].old) >= 0x20)
  312.                 if ((Board[move->old].piece == pawn) && (Board[move->old].color
  313.                         == Player))
  314.                         killmov = (move->new1 == ((MovTab[Depth-1].new1
  315.                             + MovTab[Depth-1].old) / 2));
  316.     }
  317.     else
  318.     {
  319.         if (move->spe)                  /*  Normal test  */
  320.         {
  321.             promote = move->movpiece;   /*  Pawnpromotion  */
  322.             move->movpiece = pawn;
  323.         }
  324.  
  325.         /*  Is the content of Old and New1 squares correct?  */
  326.         if (Board[move->old].piece == move->movpiece)
  327.           if (Board[move->old].color == Player)
  328.             if (Board[move->new1].piece == move->content)
  329.               if (move->content == empty || Board[move->new1].color == Opponent)
  330.               {
  331.                 if (move->movpiece == pawn)   /*  Is the move possible?  */
  332.                 {
  333.                   if (abs(move->new1 - move->old) < 0x20)
  334.                     killmov = 1;
  335.                   else
  336.                     killmov = Board[(move->new1+move->old) / 2].piece == empty;
  337.                 }
  338.                 else
  339.                   killmov = PieceAttacks(move->movpiece, Player,
  340.                                  move->old, move->new1);
  341.               }
  342.               if (move->spe)
  343.                 move->movpiece = promote;
  344.     }
  345.     }
  346.     return killmov;
  347. }
  348.  
  349.  
  350. /*
  351.  *  Store a move in buffer
  352.  */
  353.  
  354. static void Generate(void)
  355. {
  356.     BufCount++;
  357.     Buffer[BufCount] = Next;
  358. }
  359.  
  360.  
  361. /*
  362.  *  Generates pawnpromotion
  363.  */
  364.  
  365. static void PawnPromotionGen(void)
  366. {
  367.     PIECETYPE promote;
  368.  
  369.     Next.spe = 1;
  370.     for (promote = queen; promote <= knight; ((int)promote)++)
  371.     {
  372.         Next.movpiece = promote;
  373.         Generate();
  374.     }
  375.     Next.spe = 0;
  376. }
  377.  
  378.  
  379. /*
  380.  *  Generates captures of the piece on new1 using PieceTab
  381.  */
  382.  
  383. static void CapMovGen(void)
  384. {
  385.     EDGESQUARETYPE nextsq, sq;
  386.     INDEXTYPE i;
  387.  
  388.     Next.spe = 0;
  389.     Next.content = Board[Next.new1].piece;
  390.     Next.movpiece = pawn;
  391.     nextsq = Next.new1 - PawnDir[Player];
  392.     for (sq = nextsq-1; sq <= nextsq+1; sq++)
  393.         if (sq != nextsq)
  394.           if ((sq & 0x88) == 0)
  395.             if (Board[sq].piece == pawn && Board[sq].color == Player)
  396.             {
  397.                 Next.old = sq;
  398.                 if (Next.new1 < 8 || Next.new1 >= 0x70)
  399.                     PawnPromotionGen();
  400.                 else
  401.                     Generate();
  402.             }
  403.             /*  Other captures, starting with the smallest pieces  */
  404.     for (i = OfficerNo[Player]; i >= 0; i--)
  405.         if (PieceTab[Player][i].ipiece != empty && PieceTab[Player][i].ipiece
  406.                 != pawn)
  407.           if (PieceAttacks(PieceTab[Player][i].ipiece, Player,
  408.                 PieceTab[Player][i].isquare, Next.new1))
  409.           {
  410.               Next.old = PieceTab[Player][i].isquare;
  411.               Next.movpiece = PieceTab[Player][i].ipiece;
  412.               Generate();
  413.           }
  414. }
  415.  
  416.  
  417. /*
  418.  *  generates non captures for the piece on old
  419.  */
  420.  
  421. static void NonCapMovGen(void)
  422. {
  423.     DIRTYPE  first, last, dir;
  424.     int direction;
  425.     EDGESQUARETYPE  newsq;
  426.  
  427.     Next.spe = 0;
  428.     Next.movpiece = Board[Next.old].piece;
  429.     Next.content = empty;
  430.     switch (Next.movpiece)
  431.     {
  432.         case king :
  433.             for (dir = 7; dir >= 0; dir--)
  434.             {
  435.                 newsq = Next.old + DirTab[dir];
  436.                 if (!(newsq & 0x88))
  437.                   if (Board[newsq].piece == empty)
  438.                   {
  439.                       Next.new1 = newsq;
  440.                       Generate();
  441.                   }
  442.             }
  443.             break;
  444.         case knight :
  445.             for (dir = 7; dir >= 0; dir--)
  446.             {
  447.                 newsq = Next.old + KnightDir[dir];
  448.                 if (!(newsq & 0x88))
  449.                   if (Board[newsq].piece == empty)
  450.                   {
  451.                       Next.new1 = newsq;
  452.                       Generate();
  453.                   }
  454.             }
  455.             break;
  456.         case queen :
  457.         case rook  :
  458.         case bishop:
  459.             first = 7;
  460.             last = 0;
  461.             if (Next.movpiece == rook) first = 3;
  462.             if (Next.movpiece == bishop) last = 4;
  463.             for (dir = first; dir >= last; dir--)
  464.             {
  465.                 direction = DirTab[dir];
  466.                 newsq = Next.old + direction;
  467.                 /*  Generate all non captures in the direction  */
  468.                 while (!(newsq & 0x88))
  469.                 {
  470.                     if (Board[newsq].piece != empty) goto TEN;
  471.                     Next.new1 = newsq;
  472.                     Generate();
  473.                     newsq = Next.new1 + direction;
  474.                 }
  475. TEN:            continue;
  476.             }
  477.             break;
  478.         case pawn :
  479.             Next.new1 = Next.old + PawnDir[Player];  /*  one square forward  */
  480.             if (Board[Next.new1].piece == empty)
  481.             {
  482.                 if (Next.new1 < 8 || Next.new1 >= 0x70)
  483.                     PawnPromotionGen();
  484.                 else
  485.                 {
  486.                     Generate();
  487.                     if (Next.old < 0x18 || Next.old >= 0x60)
  488.                     {
  489.                         Next.new1 += (Next.new1 - Next.old); /* 2 squares forward */
  490.                         if (Board[Next.new1].piece == empty) Generate();
  491.                     }
  492.                 }
  493.             }
  494.     }  /* switch */
  495. }
  496.  
  497.  
  498. /*
  499.  *  The move generator.
  500.  *  InitMovGen generates all possible moves and places them in a buffer.
  501.  *  Movgen will the generate the moves one by one and place them in next.
  502.  *
  503.  *  On entry:
  504.  *    Player contains the color to move.
  505.  *    MovTab[Depth-1] the las performed move.
  506.  *
  507.  *  On exit:
  508.  *    Buffer contains the generated moves.
  509.  *
  510.  *    The moves are generated in the order :
  511.  *      Captures
  512.  *      Castlings
  513.  *      Non captures
  514.  *      E.p. captures
  515.  */
  516.  
  517. void InitMovGen(void)
  518. {
  519.     CASTDIRTYPE castdir;
  520.     EDGESQUARETYPE sq;
  521.     INDEXTYPE index;
  522.  
  523.     BufCount = BufPnt = 0;
  524.     /*  generate all captures starting with captures of
  525.         largest pieces  */
  526.     for (index = 1; index <= PawnNo[Opponent]; index++)
  527.         if (PieceTab[Opponent][index].ipiece != empty)
  528.         {
  529.             Next.new1 = PieceTab[Opponent][index].isquare;
  530.             CapMovGen();
  531.         }
  532.     Next.spe = 1;
  533.     Next.movpiece = king;
  534.     Next.content = empty;
  535.     for (castdir = CASTDIRTYPE(lng-1); castdir <= shrt-1; ((int)castdir)++)
  536.     {
  537.         Next.new1 = CastMove[Player][castdir].castnew;
  538.         Next.old = CastMove[Player][castdir].castold;
  539.         if (KillMovGen(&Next)) Generate();
  540.     }
  541.  
  542.     /*  generate non captures, starting with pawns  */
  543.     for (index = PawnNo[Player]; index >= 0; index--)
  544.         if (PieceTab[Player][index].ipiece != empty)
  545.         {
  546.             Next.old = PieceTab[Player][index].isquare;
  547.             NonCapMovGen();
  548.         }
  549.     if (MovTab[Depth-1].movpiece == pawn)   /*  E.p. captures  */
  550.         if (abs(MovTab[Depth-1].new1 - MovTab[Depth-1].old) >= 0x20)
  551.         {
  552.             Next.spe = 1;
  553.             Next.movpiece = pawn;
  554.             Next.content = empty;
  555.             Next.new1 = (MovTab[Depth-1].new1 + MovTab[Depth-1].old) / 2;
  556.             for (sq = MovTab[Depth-1].new1-1; sq <= MovTab[Depth-1].new1+1;
  557.                              sq++)
  558.                 if (sq != MovTab[Depth-1].new1)
  559.                     if (!(sq & 0x88))
  560.                     {
  561.                         Next.old = sq;
  562.                         if (KillMovGen(&Next)) Generate();
  563.                     }
  564.         }
  565. }
  566.  
  567.  
  568. /*
  569.  *  place next move from the buffer in next.  Generate zeromove when there
  570.  *  are no more moves.
  571.  */
  572.  
  573. void MovGen(void)
  574. {
  575.     if (BufPnt >= BufCount)
  576.         Next = ZeroMove;
  577.     else
  578.     {
  579.         BufPnt++;
  580.         Next = Buffer[BufPnt];
  581.     }
  582. }
  583.