Othello Alpha-Beta修剪玩pyly

我目前正在嘗試爲Othello製作一個好的AI，並且已經使用Minimax算法做了這樣的工作。但是，當我嘗試使用alpha-beta修剪進行更深入的搜索時，它看起來像算法玩的非常糟糕。我檢查了Wiki和Berkely.edu等其他來源，我認爲我已經正確實施了，但我仍然無法找到問題所在。Othello Alpha-Beta修剪玩pyly

def alphabeta(board, player, a, b, lev): 
     h = heur(board, player) 
     if lev == 0: 
       return h, None 
     poss = get_legal_moves(board, player) 
     if len(poss) == 0: 
       return h, None 
     move = 0 
     for x in poss: 
       cpboard = board[:] 
       cpboard[x] = player 
       bracket(cpboard, player, x) 
       a1, q = alphabeta(cpboard, opponent_color(player), a, b, lev-1) 
       if player is me: 
         if a1 > a: 
           a, move = a1, x 
       else: 
         if a1 < b: 
           b, move = a1, x 
       if b <= a: 
         break 
     if player is me: 
       return a, move 
     else: 
       return b, move

來源

2012-01-11 jcolen19

在你開始第二次猜測你的代碼之前，你確定你的'heur'函數是正確的嗎？ – inspectorG4dget 2012-01-11 20:43:06

是的，它適用於我的極大極小算法 – jcolen19 2012-01-21 22:43:26

您的alpha-beta代碼可能是錯誤的。要知道當一個玩家通過轉牌時會發生什麼（即沒有可用的移動），因此我的代碼中有一個棘手的錯誤。

您是否調用alpha和beta值切換的遞歸？礦是這樣的（Java代碼）：

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth) 
{ 
    float bestResult = -Float.MAX_VALUE; 
    OthelloMove garbage = new OthelloMove(); 

    int state = board.getState(); 
    int currentPlayer = board.getCurrentPlayer(); 

    if (state == OthelloBoard.STATE_DRAW) 
     return 0.0f; 
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.BLACK))      
     return INFINITY;   
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE)) 
     return INFINITY; 
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE)) 
     return -INFINITY; 
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK)) 
     return -INFINITY; 

    if (depth == maxDepth) 
     return OthelloHeuristics.eval(currentPlayer, board); 

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer); 

    for (OthelloMove mv : moves) 
    {    
     board.makeMove(mv); 
     alpha = - minimax(board, garbage, -beta, -alpha, depth + 1); 
     board.undoMove(mv); 

     if (beta <= alpha) 
      return alpha; 
     if (alpha > bestResult) 
     {     
      best.setFlipSquares(mv.getFlipSquares()); 
      best.setIdx(mv.getIdx());   
      best.setPlayer(mv.getPlayer()); 
      bestResult = alpha; 
     } 
    } 

    return bestResult; 
}

的調用是這樣的：

OthelloMove bestFound = new OthelloMove(); 
int maxDepth = 8; 
minimax(board, bestFound, -Float.MAX_VALUE, Float.MAX_VALUE, maxDepth); 
//Wait for Thread to finish 
board.makeMove(bestFound);

編輯：如果玩家沒有可用的動作，getAllMoves（）返回一個 '啞移動'，根本沒有改變板子，只是通過轉彎。

希望它有幫助！

來源

2012-02-28 20:25:21 Fernando

你的alphabeta實現對我來說聽起來很合理。由於minimax和alphabeta在正確執行時會產生相同的結果，因此您應該能夠使用舊的minimax代碼作爲對alphabeta的檢查，至少適用於適度的搜索深度。如果搜索同一個遊戲樹時他們的結果不同，那麼你知道你做錯了什麼。

但最有可能的是，糟糕的遊戲是你的「heur」評估函數中某些東西的結果。

來源

2012-01-16 08:05:41

我相信我的極限函數是好的，因爲當我運行極小極大搜索時，它發揮得非常好。 – jcolen19 2012-01-21 22:08:54

然後接下來的步驟是對着同一個黑白棋位置並排運行你的minimax和alphabeta代碼，搜索到相同的深度並查看它們的不同之處。以較淺的深度開始，然後以更高的深度重新運行，直到出現差異。這應該允許您調試問題。 – 2012-01-22 01:03:09

Othello Alpha-Beta修剪玩pyly

回答

相關問題