Windows编程

开发平台：
Visual C++

PRUNE.CPP：源码内容
							/* --------------------------------------------------------------------------
This function is qsort's callback
to sort the moves based on quality
-------------------------------------------------------------------------- */
int __cdecl cmpgle(const void* elem1, const void* elem2)
{
    if (    (*(struct _piece_order_struct *)elem1).q     >
            (*(struct _piece_order_struct *)elem2).q     )
        return -1;
    else if (    (*(struct _piece_order_struct *)elem1).q     <
                 (*(struct _piece_order_struct *)elem2).q     )
        return 1;
    else
        return 0;
}
/* --------------------------------------------------------------------------
THIS IS THE CHECKERS ENGINE::
b           - is the start board - it will be changed on return to
              reflect the move or moves (in the case of a double jump)
              made
t           - is whos turn it is RED or BLACK
j           - is jump continuation - must be 0
prune_depth - how many levels to recurse to determine what to prune
prune_size  - how many branches of the pruned tree to pursue (note:
              each piece is considered as one branch even though it
              it results in as many as four actual branches
max_depth   - after the tree has been pruned how far should it recurse
              must be greater than the prune_depth
side effects:
            Calls PrintBoard (debugio.cpp)
note: we may wish to use iterative deepening here and base things on time
-------------------------------------------------------------------------- */
long PlayBestMove(BOARD b, int t, int j, int d,
                    int prune_depth, int prune_size, int max_depth)
{
    /* ----- stack variables ----- */
    int  moves_made        =  0;
    int  best_move_type    = -1;
    int  best_move_number  = -1;
    long best_move_quality = -1;
    long alpha_beta_c      = -1;
    int  fBreak            = 0;
    int  i;
    #ifdef DEBUG
    int  jumps_made        =  0;
    #endif
    AssertSz(prune_size <= SQRS_MAX, "me. prune size is way to big");
    AssertSz(prune_size > 1, "how much? prune size is way to small");
    AssertSz(0 == b[0], "b sub zero should equal zero");
    AssertSz(0 == b[SQRS_MAX-1], "b sub MAX-1 should equal zero");
    /* ----- debug ----- */
    if (debug && d < 3) PrintBoard(b,d);
    /* ----- initialize tables and variables ----- */
    depth_maximum = max_depth;
    computer_color = t;
    for (i=0; i<SQRS_MAX; i++)
        {
        piece_order[i].m = (SQUARE) i;
        piece_order[i].q = -1;
        }
    /* ----- seed the random number generator ----- */
    #ifdef DEBUG
    srand( 0 );
    #else
    #ifdef TEST
    srand( 0 );
    #else
    srand( (unsigned)time( NULL ) );
    #endif
    #endif
    /* ----- iterate through all possible moves AT PRUNE_DEPTH ----- */
    if (prune_depth > 0)
        {
        depth_maximum = prune_depth;
        pdebug(stddbgmin,"PlayBestMove d=%d %s(%d)n",d,__FILE__,__LINE__);
        for (i=0;i<SQRS_MAX; i++)
            {
            int piece;
            piece = (int) piece_order[i].m;
            if (0 == (b[piece] & t)) continue; /* not our piece */
            moves_made += IterateJumps(b,piece,t,d,&best_move_type,&best_move_number,&piece_order[i].q,alpha_beta_c,best_move_quality,&fBreak);
            AssertSz(0 == fBreak,"I must not prune at the root level of the tree");
            #ifdef DEBUG
            jumps_made += moves_made;
            #endif
            }
        if (0 == moves_made /* enforce the must jump rule */
            #ifndef HIGH_PERFORMANCE
                || 0==rConfig.iMustJump
            #endif
            )
            {
            pdebug(stddbgmin,"could not find a jumping move to make %s(%d)n",__FILE__,__LINE__);
            for (i=0;i<SQRS_MAX; i++)
                {
                int piece;
                piece = (int) piece_order[i].m;
                if (0 == (b[piece] & t)) continue; /* not our piece */
                moves_made += IterateMoves(b,piece,t,d,&best_move_type,&best_move_number,&piece_order[i].q,alpha_beta_c,best_move_quality,&fBreak);
                AssertSz(0 == fBreak,"I ought not prune at the root level of the tree");
                }
            }
        if (0 == moves_made)
            {
            pdebug(stddbgmin,"could not find a move to make (error not handled) %s(%d)n",__FILE__,__LINE__);
            AssertSz(0, "I give up... why don't you go instead");
            }
        }
    else
        {
        moves_made = 1000;
        prune_size = SQRS_MAX;
        }
    /* ----- if we only have one move to make, dont recurse again ----- */
    if (moves_made > 1)
        {
        /* ----- shuffle the moves ----- */
        for (i=SQRS_MAX-1; i > 0; i--)
            {
            int r;
            struct _piece_order_struct temp;
            /* ----- pick a random interchange ----- */
            r = ((unsigned int)rand()) % ((unsigned int) i);
            /* ----- swap the order ----- */
            temp = piece_order[i];
            piece_order[i] = piece_order[r];
            piece_order[r] = temp;
            }
        /* ----- sort the move table based on the move qualities
                of each move that we tried ----- */
        pdebug(stddbgmin,"sorting... %s(%d)n",__FILE__,__LINE__);
        qsort(piece_order,SQRS_MAX, sizeof(struct _piece_order_struct), cmpgle);
        pdebug(stddbgmin,"done sorting. %s(%d)n",__FILE__,__LINE__);
        /* ----- recurse the pruned board to a deeper level ----- */
continue_jump:
        moves_made = 0;
        depth_maximum = max_depth;
        pdebug(stddbgmin,"recursing pruned PlayBestMove d=%d %s(%d)n",d,__FILE__,__LINE__);
        for (i=0;i<prune_size; i++)
            {
            int piece;
            piece = (int) piece_order[i].m;
            if (0 == (b[piece] & t)) continue; /* not our piece */
            moves_made += IterateJumps(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,alpha_beta_c,best_move_quality,&fBreak);
            AssertSz(0 == fBreak,"x2 I must not prune at the root level of the tree");
            #ifdef DEBUG
            jumps_made += moves_made;
            #endif
            }
        if ((0 == moves_made
            #ifndef HIGH_PERFORMANCE
                || 0==rConfig.iMustJump
            #endif
            )&& 0 == j) /* enforce the must jump rule */
            {
            pdebug(stddbgmin,"could not find a jumping move to make %s(%d)n",__FILE__,__LINE__);
            for (i=0;i<prune_size; i++)
                {
                int piece;
                piece = (int) piece_order[i].m;
                pdebug(stddbgmin,"Next move piece=%d i=%d %s(%d)n",piece,i,__FILE__,__LINE__);
                if (0 == (b[piece] & t)) continue; /* not our piece */
                moves_made += IterateMoves(b,piece,t,d,&best_move_type,&best_move_number,&best_move_quality,alpha_beta_c,best_move_quality,&fBreak);
                AssertSz(0 == fBreak,"x3 I must not prune at the root level of the tree");
                }
            }
        if (0 == moves_made)
            {
            pdebug(stddbgmin,"could not find a move to make (error ! handled) %s(%d)n",__FILE__,__LINE__);
            #ifdef DEBUG
            AssertSz(jumps_made, "Your turn.  I mean.  Can I move or something? .. nevermind .. why don't you just go");
            #endif
            }
        }
    /* ----- do the first step of any jumps ----- */
    if (best_move_type > TYPE_BLACK2)
        {
        switch (best_move_type)
            {
            case TYPE_RED_JUMP0   :
                j = red_jump_lut[best_move_number][1]  ;
                piece_order[0].m = (SQUARE) j;
                MakeMoveNoKing_RED_JUMP0(b,best_move_number);
                if (0 != red_jump_lut[best_move_number][4] && !(KING & b[red_jump_lut[best_move_number][1]])) goto no_jump;
                break;
            case TYPE_RED_JUMP2   :
                j = red_jump_lut[best_move_number][3]  ;
                piece_order[0].m = (SQUARE) j;
                MakeMoveNoKing_RED_JUMP2(b,best_move_number);
                if (0 != red_jump_lut[best_move_number][4] && !(KING & b[red_jump_lut[best_move_number][3]])) goto no_jump;
                break;
            case TYPE_BLACK_JUMP0 :
                j = black_jump_lut[best_move_number][1];
                piece_order[0].m = (SQUARE) j;
                MakeMoveNoKing_BLACK_JUMP0(b,best_move_number);
                if (0 != black_jump_lut[best_move_number][4] && !(KING & b[black_jump_lut[best_move_number][1]])) goto no_jump;
                break;
            case TYPE_BLACK_JUMP2 :
                j = black_jump_lut[best_move_number][3];
                piece_order[0].m = (SQUARE) j;
                MakeMoveNoKing_BLACK_JUMP2(b,best_move_number);
                if (0 != black_jump_lut[best_move_number][4] && !(KING & b[black_jump_lut[best_move_number][3]])) goto no_jump;
                break;
            default:
                AssertSz(0, "end case");
                break;
            }
        /* ----- re-initialize ----- */
        prune_size        =  1; /* ! force it to use only the jump destination as a move */
        moves_made        =  0;
        best_move_type    = -1;
        best_move_number  = -1;
        best_move_quality = -1;
        goto continue_jump;
        }
no_jump:
    switch (best_move_type)
        {
        case TYPE_RED0        :
            MakeMove_RED0(b,best_move_number);
            break;
        case TYPE_RED2        :
            MakeMove_RED2(b,best_move_number);
            break;
        case TYPE_BLACK0      :
            MakeMove_BLACK0(b,best_move_number);
            break;
        case TYPE_BLACK2      :
            MakeMove_BLACK2(b,best_move_number);
            break;
        case TYPE_RED_JUMP0   :
        case TYPE_RED_JUMP2   :
        case TYPE_BLACK_JUMP0 :
        case TYPE_BLACK_JUMP2 :
            pdebug(stddbgmin,"skipping a jump move in IO %s(%d)n",__FILE__,__LINE__);
            break;
        default:
            pdebug(stddbgmin,"printmove did not make the move on the board %s(%d)n",__FILE__,__LINE__);
            pdebug(stddbgmin,"this could be a jump continuation %s(%d)n",__FILE__,__LINE__);
            break;
        }
    // make sure everything is kinged (in case we jumped to this point)
    if (RED & b[1]) b[1] |= KING;
    if (RED & b[2]) b[2] |= KING;
    if (RED & b[3]) b[3] |= KING;
    if (RED & b[4]) b[4] |= KING;
    if (BLACK & b[32]) b[32] |= KING;
    if (BLACK & b[31]) b[31] |= KING;
    if (BLACK & b[30]) b[30] |= KING;
    if (BLACK & b[29]) b[29] |= KING;
    /* ----- return to caller ----- */
    return best_move_quality;
}

						