home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / dbmsg / mapi / checkers.frm / engine / check.cpp next >
Encoding:
Text File  |  1996-04-11  |  15.6 KB  |  376 lines
  1. /* function prototyping for internal functions */
  2. long CheckMiniMaxAlphaBeta(BOARD b, int t, int j, int d, long c, long p);
  3.  
  4. #define JUMP_CONT_DEEPER 1
  5.  
  6. /* --------------------------------------------------------------------------
  7. true if previous level should prune
  8. else false
  9.  
  10. note: it would be possible to not prune equal qualities becuase they
  11.       may be used to increase the number of available suggestions
  12.  
  13. statistics: 02:42:00  3-13-1994
  14.             if this function is return 0, six levels takes 33 seconds
  15.             if this function is implemented, six levels takes 9 seconds
  16. -------------------------------------------------------------------------- */
  17. inline int AlphaBeta(int t,long q, long c)
  18. {
  19.     pdebug(stddbg,"alpha-beta pruning t=%d q=%ld c=%ld %s(%d)\n",t,q,c,__FILE__,__LINE__);
  20.  
  21.     if (c > 0)
  22.         {
  23.         if (computer_color & t)
  24.             {
  25.             if (q > c)
  26.                 {
  27.                 pdebug(stddbg,"alpha-beta COMP pruning t=%d q=%ld c=%ld %s(%d)\n",t,q,c,__FILE__,__LINE__);
  28.                 return 1;
  29.                 }
  30.             }
  31.         else
  32.             {
  33.             if (q < c)
  34.                 {
  35.                 pdebug(stddbg,"alpha-beta USER pruning t=%d q=%ld c=%ld %s(%d)\n",t,q,c,__FILE__,__LINE__);
  36.                 return 1;
  37.                 }
  38.             }
  39.         }
  40.     return 0;
  41. }
  42.  
  43.  
  44. /* --------------------------------------------------------------------------
  45. The algorithm is basically a min-max tree
  46. This function takes care of whether or no we remember the Min or the Max
  47. In checkers terms this means the following:
  48.     if it is my (the computers) move, pick the move that results in the highest quality
  49.     if it is your move, remember the move that does the most damage (min quality)
  50.  
  51. Parameters:
  52.     t    - whos turn it is (RED or BLACK)
  53.     type - the move type.  this parameter should be a constant from check.h
  54.            it says if it the move is a black or red move, and if the move is
  55.            a sliding or jumping move.  This also indicates if the move is a
  56.            move towards the left or towards the right.
  57.     number - this is the index into the move table derived from 'type'
  58.     d      - current recursion depth (debugging purposes only)
  59.     besttype    - type corresponding with bestquality
  60.     bestnumber  - number corresponding with bestquality
  61.     bestquality - either a min or a max of qualities depending on current turn
  62. -------------------------------------------------------------------------- */
  63. inline void RememberMove(int t,int type, int number, long q,int d,
  64.                          int* besttype, int* bestnumber, long* bestquality,
  65.                          long c, long p, int* fBreak)
  66. {
  67.     *fBreak = AlphaBeta(t,q,c);
  68.     if (q == *bestquality)
  69.         {
  70.         pdebug(stddbg,"evaluation (equal move) t=%d type=%d num=%d q=%ld d=%d %s(%d)\n",t,type,number,q,d,__FILE__,__LINE__);
  71.         if (1 & rand()) return;
  72.         }
  73.     else if (computer_color & t)
  74.         {
  75.         pdebug(stddbg,"evaluation (computer) t=%d type=%d num=%d q=%ld d=%d %s(%d)\n",t,type,number,q,d,__FILE__,__LINE__);
  76.         if (q < *bestquality) return;
  77.         }
  78.     else
  79.         {
  80.         pdebug(stddbg,"evaluation (opponent) t=%d type=%d num=%d q=%ld d=%d %s(%d)\n",t,type,number,q,d,__FILE__,__LINE__);
  81.         if (*bestquality > 0 && q > *bestquality) return;
  82.         }
  83.  
  84.     pdebug(stddbg,"RememberMove! evaluated t=%d type=%d num=%d q=%ld d=%d %s(%d)\n",t,type,number,q,d,__FILE__,__LINE__);
  85.     *besttype = type;
  86.     *bestnumber = number;
  87.     *bestquality = q;
  88.     return;
  89. }
  90.  
  91. /* --------------------------------------------------------------------------
  92. This function calls recurse for each possible jumping move for t's turn
  93. starting from the start position
  94.  
  95. Note: there is special logic to crown men since landing in a crown position
  96.       can not continue the jump, but having a man that is already a king land
  97.       in a crown position can continue a jump.
  98. If the piece I am moving is a king, I look at both BLACK and RED moves.
  99.  
  100. Parameters:
  101.     b     - board (value is not changed)
  102.     start - starting position
  103.     t     - whos turn it is (RED or BLACK)
  104.     besttype    - type corresponding with bestquality
  105.     bestnumber  - number corresponding with bestquality
  106.     bestquality - either a min or a max of qualities depending on current turn
  107. -------------------------------------------------------------------------- */
  108. int IterateJumps(BOARD b, int start, int t, int d,
  109.                  int* besttype, int* bestnumber, long* bestquality,
  110.                  long c, long p, int *fBreak)
  111. {
  112.     int moves_made=0;
  113.     long q;
  114.     SQUARE play_board[SQRS_MAX];
  115.  
  116.     if ((RED == t) || (KING & b[start]))
  117.         {
  118.         AssertSz(b[start] & t, "chicken");
  119.         if (0 == b[red_jump_lut[start][1]] && red_jump_lut[start][1] && (next(t) & b[red_jump_lut[start][0]]))
  120.             {
  121.             pdebug(stddbg,"trying RED_JUMP0 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  122.             CopyBoard(b,play_board);
  123.             MakeMoveNoKing_RED_JUMP0(play_board,start);
  124.             if (0 == red_jump_lut[start][4] || (KING & play_board[red_jump_lut[start][1]]))
  125.                 {
  126.                 q = CheckMiniMaxAlphaBeta(play_board,t,red_jump_lut[start][1],JUMP_CONT_DEEPER+d,c,p);
  127.                 }
  128.             else
  129.                 {
  130.                 AssertSz(play_board[red_jump_lut[start][1]], "what the?");
  131.                 play_board[red_jump_lut[start][1]] |= red_jump_lut[start][4];
  132.                 q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  133.                 }
  134.             RememberMove(t,TYPE_RED_JUMP0,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  135.             ++moves_made;
  136.             }
  137.         if (0 == b[red_jump_lut[start][3]] && red_jump_lut[start][3] && (next(t) & b[red_jump_lut[start][2]]))
  138.             {
  139.             pdebug(stddbg,"trying RED_JUMP2 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  140.             CopyBoard(b,play_board);
  141.             MakeMoveNoKing_RED_JUMP2(play_board,start);
  142.             if (0 == red_jump_lut[start][4] || (KING & play_board[red_jump_lut[start][3]]))
  143.                 {
  144.                 q = CheckMiniMaxAlphaBeta(play_board,t,red_jump_lut[start][3],JUMP_CONT_DEEPER+d,c,p);
  145.                 }
  146.             else
  147.                 {
  148.                 AssertSz(play_board[red_jump_lut[start][3]], "this stupid piece");
  149.                 play_board[red_jump_lut[start][3]] |= red_jump_lut[start][4];
  150.                 q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  151.                 }
  152.             RememberMove(t,TYPE_RED_JUMP2,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  153.             ++moves_made;
  154.             }
  155.         }
  156.     if ((BLACK == t) || (KING & b[start]))
  157.         {
  158.         AssertSz(b[start] & t, "but... I thought it was my turn");
  159.         if (0 == b[black_jump_lut[start][1]] && black_jump_lut[start][1] && (next(t) & b[black_jump_lut[start][0]]))
  160.             {
  161.             pdebug(stddbg,"trying BLACK_JUMP0 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  162.             CopyBoard(b,play_board);
  163.             MakeMoveNoKing_BLACK_JUMP0(play_board,start);
  164.             if (0 == black_jump_lut[start][4] || (KING & play_board[black_jump_lut[start][1]]))
  165.                 {
  166.                 q = CheckMiniMaxAlphaBeta(play_board,t,black_jump_lut[start][1],JUMP_CONT_DEEPER+d,c,p);
  167.                 }
  168.             else
  169.                 {
  170.                 AssertSz(play_board[black_jump_lut[start][1]], "you thought it was who's turn?");
  171.                 play_board[black_jump_lut[start][1]] |= black_jump_lut[start][4];
  172.                 q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  173.                 }
  174.             RememberMove(t,TYPE_BLACK_JUMP0,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  175.             ++moves_made;
  176.             }
  177.         if (0 == b[black_jump_lut[start][3]] && black_jump_lut[start][3] && (next(t) & b[black_jump_lut[start][2]]))
  178.             {
  179.             pdebug(stddbg,"trying BLACK_JUMP2 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  180.             CopyBoard(b,play_board);
  181.             MakeMoveNoKing_BLACK_JUMP2(play_board,start);
  182.             if (0 == black_jump_lut[start][4] || (KING & play_board[black_jump_lut[start][3]]))
  183.                 {
  184.                 q = CheckMiniMaxAlphaBeta(play_board,t,black_jump_lut[start][3],JUMP_CONT_DEEPER+d,c,p);
  185.                 }
  186.             else
  187.                 {
  188.                 AssertSz(play_board[black_jump_lut[start][3]], "maggots");
  189.                 play_board[black_jump_lut[start][3]] |= black_jump_lut[start][4];
  190.                 q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  191.                 }
  192.             RememberMove(t,TYPE_BLACK_JUMP2,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  193.             ++moves_made;
  194.             }
  195.         }
  196.     return moves_made;
  197. }
  198.  
  199. /* --------------------------------------------------------------------------
  200. This function calls recurse after making each possible sliding move for t's turn
  201. starting from the start position
  202.  
  203. If the piece I am moving is a king, I look at both BLACK and RED moves.
  204.  
  205. Parameters:
  206.     b     - board (value is not changed)
  207.     start - starting position
  208.     t     - whos turn it is (RED or BLACK)
  209.     besttype    - type corresponding with bestquality
  210.     bestnumber  - number corresponding with bestquality
  211.     bestquality - either a min or a max of qualities depending on current turn
  212. -------------------------------------------------------------------------- */
  213. int IterateMoves(BOARD b, int start, int t, int d,
  214.                  int* besttype, int* bestnumber, long* bestquality,
  215.                  long c, long p, int *fBreak)
  216. {
  217.     int moves_made=0;
  218.     long q;
  219.     SQUARE play_board[SQRS_MAX];
  220.  
  221.     if ((RED == t) || (KING & b[start]))
  222.         {
  223.         AssertSz(b[start] & t, "I wish I could fly");
  224.         if (0 == b[red_lut[start][0]] && red_lut[start][0])
  225.             {
  226.             pdebug(stddbg,"trying RED0 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  227.             CopyBoard(b,play_board);
  228.             MakeMove_RED0(play_board,start);
  229.             q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  230.             RememberMove(t,TYPE_RED0,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  231.             ++moves_made;
  232.             }
  233.         if (0 == b[red_lut[start][2]] && red_lut[start][2])
  234.             {
  235.             pdebug(stddbg,"trying RED2 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  236.             CopyBoard(b,play_board);
  237.             MakeMove_RED2(play_board,start);
  238.             q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  239.             RememberMove(t,TYPE_RED2,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  240.             ++moves_made;
  241.             }
  242.         }
  243.  
  244.  
  245.     if ((BLACK == t) || (KING & b[start]))
  246.         {
  247.         AssertSz(b[start] & t, "what are you... ");
  248.         if (0 == b[black_lut[start][0]] && black_lut[start][0])
  249.             {
  250.             pdebug(stddbg,"trying BLACK0 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  251.             CopyBoard(b,play_board);
  252.             MakeMove_BLACK0(play_board,start);
  253.             q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  254.             RememberMove(t,TYPE_BLACK0,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  255.             ++moves_made;
  256.             }
  257.         if (0 == b[black_lut[start][2]] && black_lut[start][2])
  258.             {
  259.             pdebug(stddbg,"trying BLACK2 std move %d %s(%d)\n",start,__FILE__,__LINE__);
  260.             CopyBoard(b,play_board);
  261.             MakeMove_BLACK2(play_board,start);
  262.             q = CheckMiniMaxAlphaBeta(play_board,next(t),0,1+d,p,*bestquality);
  263.             RememberMove(t,TYPE_BLACK2,start,q,d,besttype,bestnumber,bestquality,c,p,fBreak);
  264.             ++moves_made;
  265.             }
  266.         }
  267.     return moves_made;
  268. }
  269.  
  270.  
  271. /* --------------------------------------------------------------------------
  272.  
  273. RECURSIVE MIN MAX ALGORITHM
  274.  
  275. Parameters:
  276.     b - pointer to the board
  277.     t - whos turn it is (RED or BLACK)
  278.     j - space on board in which jump landed or zero if this
  279.         is not a jump continuation
  280.     d - depth of recursion
  281.  
  282.     alpha-beta pruning parameters:
  283.  
  284.     c - cutoff value for min max algorithm
  285.     p - threshold to be passed on to next level
  286.  
  287. always returns the value of the best outcome of the board
  288.  
  289. note: this function is to be called from within the checkers engine only
  290. note: this function evaluates moves based on the piece order structure defined
  291.       in lut.cpp.  The reason for this is that we gain two things by looking
  292.       at the best moves first:
  293.         1) pruning is more effective
  294.         2) if we must give up due to time constraint, we have already
  295.            evaluated some of the best moves.
  296.  
  297. -------------------------------------------------------------------------- */
  298. long CheckMiniMaxAlphaBeta(BOARD b, int t, int j, int d, long c, long p)
  299. {
  300.     /* ----- stack variables ----- */
  301.     int  moves_made        = 0;
  302.     int  best_move_type    = -1;
  303.     int  best_move_number  = -1;
  304.     long best_move_quality = -1;
  305.     int  fBreak            = 0;
  306.  
  307.     /* ----- debug ----- */
  308.     #ifdef DEBUG
  309.     debug=1;
  310.     if (debug && d < 7) PrintBoard(b,d);
  311.     #endif
  312.  
  313.     AssertSz(b[0] == 0, "no b for my b my for my be my");
  314.     AssertSz(d >= 0, "i am so tired of this");
  315.  
  316.     /* ----- if we have reached maximum depth, return now ----- */
  317.     if (d >= depth_maximum) return QualityOfBoard(b,next(t));
  318.  
  319.     /* ----- iterate through all possible moves ----- */
  320.     if (0 == j)
  321.         {
  322.         int i;
  323.         pdebug(stddbg,"standard iteration d=%d %s(%d)\n",d,__FILE__,__LINE__);
  324.         for (i=0;i<SQRS_MAX; i++)
  325.             {
  326.             int piece;
  327.             piece = (int) piece_order[i].m;
  328.             if (0 == (b[piece] & t)) continue; /* not our piece */
  329.             moves_made += IterateJumps(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,c,p,&fBreak);
  330.             if (fBreak)
  331.                 {
  332.                 AssertSz(moves_made,"I'm pruning something I have not looked at...");
  333.                 break;
  334.                 }
  335.             }
  336.         if (0 == moves_made /* enforce the must jump rule */
  337.             #ifndef HIGH_PERFORMANCE
  338.                 || 0==rConfig.iMustJump
  339.             #endif
  340.             )
  341.             {
  342.             pdebug(stddbg,"could not find a jumping move to make %s(%d)\n",__FILE__,__LINE__);
  343.             for (i=0;i<SQRS_MAX; i++)
  344.                 {
  345.                 int piece;
  346.                 piece = (int) piece_order[i].m;
  347.                 if (0 == (b[piece] & t)) continue; /* not our piece */
  348.                 moves_made += IterateMoves(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,c,p,&fBreak);
  349.                 if (fBreak)
  350.                     {
  351.                     AssertSz(moves_made,"to Scottland, I have not been");
  352.                     break;
  353.                     }
  354.                 }
  355.             }
  356.         if (0 == moves_made)
  357.             {
  358.             pdebug(stddbg,"could not find a move to make (error not handled) %s(%d)\n",__FILE__,__LINE__);
  359.             return QualityOfBoard(b,next(t));
  360.             }
  361.  
  362.         return best_move_quality;
  363.         }
  364.  
  365.     /* ----- handle jump continuation ----- */
  366.     pdebug(stddbg,"jump continuation d=%d %s(%d)\n",d,__FILE__,__LINE__);
  367.     moves_made = IterateJumps(b,j,t,d,&best_move_type,&best_move_number,&best_move_quality,c,p,&fBreak);
  368.     // AssertSz(0==fBreak,"is this a valid assert?");
  369.     if (0==moves_made)
  370.         {
  371.         return CheckMiniMaxAlphaBeta(b,next(t),0,d,p,best_move_quality);
  372.         }
  373.     return best_move_quality;
  374.  
  375. } /* end CheckMiniMaxAlphaBeta */
  376.