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 / prune.cpp < prev    next >
Encoding:
Text File  |  1996-04-11  |  10.8 KB  |  285 lines
  1. /* --------------------------------------------------------------------------
  2. This function is qsort's callback
  3. to sort the moves based on quality
  4. -------------------------------------------------------------------------- */
  5. int __cdecl cmpgle(const void* elem1, const void* elem2)
  6. {
  7.     if (    (*(struct _piece_order_struct *)elem1).q     >
  8.             (*(struct _piece_order_struct *)elem2).q     )
  9.         return -1;
  10.     else if (    (*(struct _piece_order_struct *)elem1).q     <
  11.                  (*(struct _piece_order_struct *)elem2).q     )
  12.         return 1;
  13.     else
  14.         return 0;
  15. }
  16.  
  17. /* --------------------------------------------------------------------------
  18. THIS IS THE CHECKERS ENGINE::
  19.  
  20. b           - is the start board - it will be changed on return to
  21.               reflect the move or moves (in the case of a double jump)
  22.               made
  23. t           - is whos turn it is RED or BLACK
  24. j           - is jump continuation - must be 0
  25. prune_depth - how many levels to recurse to determine what to prune
  26. prune_size  - how many branches of the pruned tree to pursue (note:
  27.               each piece is considered as one branch even though it
  28.               it results in as many as four actual branches
  29. max_depth   - after the tree has been pruned how far should it recurse
  30.               must be greater than the prune_depth
  31.  
  32. side effects:
  33.             Calls PrintBoard (debugio.cpp)
  34.  
  35. note: we may wish to use iterative deepening here and base things on time
  36. -------------------------------------------------------------------------- */
  37. long PlayBestMove(BOARD b, int t, int j, int d,
  38.                     int prune_depth, int prune_size, int max_depth)
  39. {
  40.     /* ----- stack variables ----- */
  41.     int  moves_made        =  0;
  42.     int  best_move_type    = -1;
  43.     int  best_move_number  = -1;
  44.     long best_move_quality = -1;
  45.     long alpha_beta_c      = -1;
  46.     int  fBreak            = 0;
  47.     int  i;
  48.  
  49.     #ifdef DEBUG
  50.     int  jumps_made        =  0;
  51.     #endif
  52.  
  53.     AssertSz(prune_size <= SQRS_MAX, "me. prune size is way to big");
  54.     AssertSz(prune_size > 1, "how much? prune size is way to small");
  55.     AssertSz(0 == b[0], "b sub zero should equal zero");
  56.     AssertSz(0 == b[SQRS_MAX-1], "b sub MAX-1 should equal zero");
  57.  
  58.     /* ----- debug ----- */
  59.     if (debug && d < 3) PrintBoard(b,d);
  60.  
  61.     /* ----- initialize tables and variables ----- */
  62.     depth_maximum = max_depth;
  63.     computer_color = t;
  64.     for (i=0; i<SQRS_MAX; i++)
  65.         {
  66.         piece_order[i].m = (SQUARE) i;
  67.         piece_order[i].q = -1;
  68.         }
  69.  
  70.     /* ----- seed the random number generator ----- */
  71.     #ifdef DEBUG
  72.     srand( 0 );
  73.     #else
  74.     #ifdef TEST
  75.     srand( 0 );
  76.     #else
  77.     srand( (unsigned)time( NULL ) );
  78.     #endif
  79.     #endif
  80.  
  81.     /* ----- iterate through all possible moves AT PRUNE_DEPTH ----- */
  82.     if (prune_depth > 0)
  83.         {
  84.         depth_maximum = prune_depth;
  85.         pdebug(stddbgmin,"PlayBestMove d=%d %s(%d)\n",d,__FILE__,__LINE__);
  86.         for (i=0;i<SQRS_MAX; i++)
  87.             {
  88.             int piece;
  89.             piece = (int) piece_order[i].m;
  90.             if (0 == (b[piece] & t)) continue; /* not our piece */
  91.             moves_made += IterateJumps(b,piece,t,d,&best_move_type,&best_move_number,&piece_order[i].q,alpha_beta_c,best_move_quality,&fBreak);
  92.             AssertSz(0 == fBreak,"I must not prune at the root level of the tree");
  93.             #ifdef DEBUG
  94.             jumps_made += moves_made;
  95.             #endif
  96.             }
  97.         if (0 == moves_made /* enforce the must jump rule */
  98.             #ifndef HIGH_PERFORMANCE
  99.                 || 0==rConfig.iMustJump
  100.             #endif
  101.             )
  102.             {
  103.             pdebug(stddbgmin,"could not find a jumping move to make %s(%d)\n",__FILE__,__LINE__);
  104.             for (i=0;i<SQRS_MAX; i++)
  105.                 {
  106.                 int piece;
  107.                 piece = (int) piece_order[i].m;
  108.                 if (0 == (b[piece] & t)) continue; /* not our piece */
  109.                 moves_made += IterateMoves(b,piece,t,d,&best_move_type,&best_move_number,&piece_order[i].q,alpha_beta_c,best_move_quality,&fBreak);
  110.                 AssertSz(0 == fBreak,"I ought not prune at the root level of the tree");
  111.                 }
  112.             }
  113.         if (0 == moves_made)
  114.             {
  115.             pdebug(stddbgmin,"could not find a move to make (error not handled) %s(%d)\n",__FILE__,__LINE__);
  116.             AssertSz(0, "I give up... why don't you go instead");
  117.             }
  118.         }
  119.     else
  120.         {
  121.         moves_made = 1000;
  122.         prune_size = SQRS_MAX;
  123.         }
  124.  
  125.     /* ----- if we only have one move to make, dont recurse again ----- */
  126.     if (moves_made > 1)
  127.         {
  128.         /* ----- shuffle the moves ----- */
  129.         for (i=SQRS_MAX-1; i > 0; i--)
  130.             {
  131.             int r;
  132.             struct _piece_order_struct temp;
  133.  
  134.             /* ----- pick a random interchange ----- */
  135.             r = ((unsigned int)rand()) % ((unsigned int) i);
  136.  
  137.             /* ----- swap the order ----- */
  138.             temp = piece_order[i];
  139.             piece_order[i] = piece_order[r];
  140.             piece_order[r] = temp;
  141.             }
  142.  
  143.         /* ----- sort the move table based on the move qualities
  144.                 of each move that we tried ----- */
  145.         pdebug(stddbgmin,"sorting... %s(%d)\n",__FILE__,__LINE__);
  146.         qsort(piece_order,SQRS_MAX, sizeof(struct _piece_order_struct), cmpgle);
  147.         pdebug(stddbgmin,"done sorting. %s(%d)\n",__FILE__,__LINE__);
  148.  
  149.  
  150.         /* ----- recurse the pruned board to a deeper level ----- */
  151. continue_jump:
  152.         moves_made = 0;
  153.         depth_maximum = max_depth;
  154.         pdebug(stddbgmin,"recursing pruned PlayBestMove d=%d %s(%d)\n",d,__FILE__,__LINE__);
  155.         for (i=0;i<prune_size; i++)
  156.             {
  157.             int piece;
  158.             piece = (int) piece_order[i].m;
  159.             if (0 == (b[piece] & t)) continue; /* not our piece */
  160.             moves_made += IterateJumps(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,alpha_beta_c,best_move_quality,&fBreak);
  161.             AssertSz(0 == fBreak,"x2 I must not prune at the root level of the tree");
  162.             #ifdef DEBUG
  163.             jumps_made += moves_made;
  164.             #endif
  165.             }
  166.         if ((0 == moves_made
  167.             #ifndef HIGH_PERFORMANCE
  168.                 || 0==rConfig.iMustJump
  169.             #endif
  170.             )&& 0 == j) /* enforce the must jump rule */
  171.             {
  172.             pdebug(stddbgmin,"could not find a jumping move to make %s(%d)\n",__FILE__,__LINE__);
  173.             for (i=0;i<prune_size; i++)
  174.                 {
  175.                 int piece;
  176.                 piece = (int) piece_order[i].m;
  177.                 pdebug(stddbgmin,"Next move piece=%d i=%d %s(%d)\n",piece,i,__FILE__,__LINE__);
  178.                 if (0 == (b[piece] & t)) continue; /* not our piece */
  179.                 moves_made += IterateMoves(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,alpha_beta_c,best_move_quality,&fBreak);
  180.                 AssertSz(0 == fBreak,"x3 I must not prune at the root level of the tree");
  181.                 }
  182.             }
  183.         if (0 == moves_made)
  184.             {
  185.             pdebug(stddbgmin,"could not find a move to make (error ! handled) %s(%d)\n",__FILE__,__LINE__);
  186.             #ifdef DEBUG
  187.             AssertSz(jumps_made, "Your turn.  I mean.  Can I move or something? .. nevermind .. why don't you just go");
  188.             #endif
  189.             }
  190.         }
  191.  
  192.     /* ----- do the first step of any jumps ----- */
  193.     if (best_move_type > TYPE_BLACK2)
  194.         {
  195.         switch (best_move_type)
  196.             {
  197.             case TYPE_RED_JUMP0   :
  198.                 j = red_jump_lut[best_move_number][1]  ;
  199.                 piece_order[0].m = (SQUARE) j;
  200.                 MakeMoveNoKing_RED_JUMP0(b,best_move_number);
  201.                 if (0 != red_jump_lut[best_move_number][4] && !(KING & b[red_jump_lut[best_move_number][1]])) goto no_jump;
  202.                 break;
  203.  
  204.             case TYPE_RED_JUMP2   :
  205.                 j = red_jump_lut[best_move_number][3]  ;
  206.                 piece_order[0].m = (SQUARE) j;
  207.                 MakeMoveNoKing_RED_JUMP2(b,best_move_number);
  208.                 if (0 != red_jump_lut[best_move_number][4] && !(KING & b[red_jump_lut[best_move_number][3]])) goto no_jump;
  209.                 break;
  210.  
  211.             case TYPE_BLACK_JUMP0 :
  212.                 j = black_jump_lut[best_move_number][1];
  213.                 piece_order[0].m = (SQUARE) j;
  214.                 MakeMoveNoKing_BLACK_JUMP0(b,best_move_number);
  215.                 if (0 != black_jump_lut[best_move_number][4] && !(KING & b[black_jump_lut[best_move_number][1]])) goto no_jump;
  216.                 break;
  217.  
  218.             case TYPE_BLACK_JUMP2 :
  219.                 j = black_jump_lut[best_move_number][3];
  220.                 piece_order[0].m = (SQUARE) j;
  221.                 MakeMoveNoKing_BLACK_JUMP2(b,best_move_number);
  222.                 if (0 != black_jump_lut[best_move_number][4] && !(KING & b[black_jump_lut[best_move_number][3]])) goto no_jump;
  223.                 break;
  224.  
  225.             default:
  226.                 AssertSz(0, "end case");
  227.                 break;
  228.             }
  229.  
  230.         /* ----- re-initialize ----- */
  231.         prune_size        =  1; /* ! force it to use only the jump destination as a move */
  232.         moves_made        =  0;
  233.         best_move_type    = -1;
  234.         best_move_number  = -1;
  235.         best_move_quality = -1;
  236.  
  237.         goto continue_jump;
  238.         }
  239. no_jump:
  240.  
  241.     switch (best_move_type)
  242.         {
  243.         case TYPE_RED0        :
  244.             MakeMove_RED0(b,best_move_number);
  245.             break;
  246.  
  247.         case TYPE_RED2        :
  248.             MakeMove_RED2(b,best_move_number);
  249.             break;
  250.  
  251.         case TYPE_BLACK0      :
  252.             MakeMove_BLACK0(b,best_move_number);
  253.             break;
  254.  
  255.         case TYPE_BLACK2      :
  256.             MakeMove_BLACK2(b,best_move_number);
  257.             break;
  258.  
  259.         case TYPE_RED_JUMP0   :
  260.         case TYPE_RED_JUMP2   :
  261.         case TYPE_BLACK_JUMP0 :
  262.         case TYPE_BLACK_JUMP2 :
  263.             pdebug(stddbgmin,"skipping a jump move in IO %s(%d)\n",__FILE__,__LINE__);
  264.             break;
  265.  
  266.         default:
  267.             pdebug(stddbgmin,"printmove did not make the move on the board %s(%d)\n",__FILE__,__LINE__);
  268.             pdebug(stddbgmin,"this could be a jump continuation %s(%d)\n",__FILE__,__LINE__);
  269.             break;
  270.         }
  271.  
  272.     // make sure everything is kinged (in case we jumped to this point)
  273.     if (RED & b[1]) b[1] |= KING;
  274.     if (RED & b[2]) b[2] |= KING;
  275.     if (RED & b[3]) b[3] |= KING;
  276.     if (RED & b[4]) b[4] |= KING;
  277.     if (BLACK & b[32]) b[32] |= KING;
  278.     if (BLACK & b[31]) b[31] |= KING;
  279.     if (BLACK & b[30]) b[30] |= KING;
  280.     if (BLACK & b[29]) b[29] |= KING;
  281.  
  282.     /* ----- return to caller ----- */
  283.     return best_move_quality;
  284. }
  285.