0

我正在尝试将 Alpha beta 修剪的递归版本转换为非递归版本，因为我必须在 CUDA 上实现它。这是递归版本

int Bot::minimaxAlphaBeta(Board & board, int depth, bool isMax, int alpha, int beta, int x , int y){
if (depth == 0){
    int value = 0;
    if (isVisited(board) == true){
        value = getEval(board); 
    }else{
        value = Evaluation(board, isMax); 
        // value = 0;
        insertToMem(board, value); 
    }
    board.setValue(x,y,'.');
    // cout << "evaluation value: " << value << endl;
    return value;
}

vector<int> firstCoord;
vector<int> secondCoord;
for (int i = 0; i < BOARD_SIZE; i++){
    for (int j = 0; j < BOARD_SIZE; j++){
        if (board.getValue(i,j) == '.' && isEmptyAround(board,i,j)){
            firstCoord.push_back(i);
            secondCoord.push_back(j);
        }
    }
}

int len = (int) firstCoord.size();
if (isMax == true){ // try to minimize because now is player's turn
    int m = INT_MAX;
    for (int i = 0; i < len; i++){
        int temp = minimaxAlphaBeta(board,depth - 1, false, alpha, beta, firstCoord[i], secondCoord[i]);
        // cout << "isMax = true: " << temp << endl;
        if (m > temp){
            m = temp;
        }
        if (beta > m){
            beta = m;
         }  
         if (alpha >= beta){
            break;
         }
    }
    return m;

}else {//try to maximize
    int M = INT_MIN;
    for (int i = 0; i < len; i++){
        int temp = minimaxAlphaBeta(board, depth - 1, true, alpha, beta, firstCoord[i], secondCoord[i]);
        // cout << "isMax = false: " << temp << endl;
        if (M < temp){
            M = temp;
        }
        if (alpha < M){
            alpha = M;
         }
         if (alpha >= beta){
            break;
         }
    }
    return M;
}

}

现在，我正在使用自制的堆栈来实现非递归的，更详细的，我按照这里的说明进行操作

到目前为止我已经归档的内容

int Bot::minimaxAlphaBeta(Board & board, int depth, bool isMax, int alpha, int beta, int x , int y){

struct SnapShotStruct {
    int depth;
    bool isMax;
    int alpha;
    int beta;
    int x;
    int y;
    int m;
    int M;
    vector<int> firstCoord;
    vector<int> secondCoord;
    int length;
    int stage;
};

int value;
stack<SnapShotStruct> SnapShotStack;
SnapShotStruct currentSnapShot;
currentSnapShot.depth = depth;
currentSnapShot.isMax = isMax;
currentSnapShot.alpha = alpha;
currentSnapShot.beta = beta;
currentSnapShot.x = x;
currentSnapShot.y = y;
currentSnapShot.m = INT_MAX;
currentSnapShot.M = INT_MIN;
for (int i = 0; i < BOARD_SIZE; i++){
    for(int j = 0; j < BOARD_SIZE; j++){
        if (board.getValue(i,j) == '.' && isEmptyAround(board,i,j)){
            currentSnapShot.firstCoord.push_back(i);
            currentSnapShot.secondCoord.push_back(j);
        }
    }
}
currentSnapShot.length = (int) currentSnapShot.firstCoord.size();
currentSnapShot.stage = 0;
SnapShotStack.push(currentSnapShot);

while(!SnapShotStack.empty()){
    currentSnapShot = SnapShotStack.top();
    SnapShotStack.pop();

    switch(currentSnapShot.stage){
        case 0:
            if(currentSnapShot.depth == 0){
                value = 0;
                if(isVisited(board) == true){
                    value = getEval(board);
                } else {
                    value = Evaluation(board,currentSnapShot.isMax);
                    insertToMem(board, value);
                }
                board.setValue(currentSnapShot.x, currentSnapShot.y, '.');
                // return value;
                continue;
            } else if (currentSnapShot.depth > 0){
                if(currentSnapShot.isMax == true){
                    SnapShotStruct newSnapShot;
                    for(int i = 0; i < currentSnapShot.length; i++){
                        newSnapShot.depth = currentSnapShot.depth - 1;
                        newSnapShot.isMax = false;
                        newSnapShot.x = currentSnapShot.firstCoord[i];
                        newSnapShot.y = currentSnapShot.secondCoord[i];
                    }
                    newSnapShot.stage = 1;
                    SnapShotStack.push(newSnapShot);
                    continue;
                }
            }
        case 1:
            if(currentSnapShot.isMax == false){
                SnapShotStruct newSnapShot;
                for(int i = 0; i < currentSnapShot.length; i++){
                    newSnapShot.depth = currentSnapShot.depth - 1;
                    newSnapShot.isMax = true;
                    newSnapShot.x = currentSnapShot.firstCoord[i];
                    newSnapShot.y = currentSnapShot.secondCoord[i];
                }
                newSnapShot.stage = 0;
                SnapShotStack.push(newSnapShot);
                continue;
            }
    }   
}

}

我在这里很迷茫，不知道如何将 alpha 和 beta 的值更新到堆栈中？任何想法 ？

4

0 回答 0