Othello Alpha-Betaプルーニングが間違っているpythonを再生する

Question

現在、私はOthelloのための良いAIを作ろうとしており、Minimaxアルゴリズムを使って行っています。しかし、私がアルファベータプルーニングを使ってより深い検索をしようとすると、アルゴリズムがひどく遊んでいるように思えました。私はWikiやBerkely.eduのような他のソースとチェックしましたが、正しく実装したと思いますが、まだ問題は見つかりません。

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 

Answer 1

アルファベットコードが間違っている可能性があります。プレイヤーがターンを通過したときに何が起こるか（つまり、利用可能な動きがない）、私は自分のコードに厄介なバグがあったことに気をつけてください。

アルファ値とベータ値を切り替えて再帰呼び出しを呼び出しましたか？ 鉱山は、この（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（） 'ダミーの動きを' を返していない場合は、その はボードをまったく変更しないので、ターンを渡すだけです。

希望すると助かります！

Answer 2

あなたのアルファベットの実装は私には見えます。ミニマムとアルファベットは正しく実装されても同じ結果を生み出すので、アルファベットに対するチェックとして古いミニマックスコードを使うことができます。同じゲームツリーを検索するときに結果が異なる場合、間違ったことをしたことがわかります。

しかし、おそらく、貧弱なプレーは、「評価版」評価機能の結果である可能性があります。