Java Minimax Alpha-Beta Pruning Recursion Return

Question

Javaのチェッカーゲームでalpha-betaプルーニングを使ってminimaxを実装しようとしています。私のミニマックスアルゴリズムは完全に機能します。私のコードは、アルファベットコードで実行されます。残念ながら、私が1000のゲームと標準的なミニマックスのアルゴリズムを比較すると、アルファベットアルゴリズムは常に50ゲーム程度遅れることになります。

アルファベータプルーニングは、ムーブメントの品質を低下させるべきではないため、達成にかかる時間が間違っている必要があります。しかし、私はペンと紙を取り出し、仮説的な葉ノードの値を引いて、アルゴリズムを使って正しい最良の移動を計算するかどうかを予測し、論理​​エラーはないように見せました。このビデオのツリーを使用して：Alpha-Beta Pruning私のアルゴリズムをトレースします。それは論理的に同じ選択肢のすべてを作るべきであり、したがって機能する実装であるべきです。

私もprintステートメントをコードに入れました（クラッタを減らすために削除されています）、値が正しく返されていて、プルーニングが行われます。私の最善の努力にもかかわらず、私は論理エラーがどこにあるのか見つけることができませんでした。これはこれを実装する私の3番目の試みであり、それらのすべてが同じ問題を抱えています。

ここで完全なコードを投稿することはできません。時間がかかりすぎるため、エラーに関連するメソッドが含まれています。私は確信していませんが、問題はおそらく非再帰的move（）メソッドにあると思われますが、論理的なエラーが見つからないので、おそらくそれをもっとスリルして、おそらく韻や理性を持たない方が良いというよりは悪い。

forループで再帰呼び出しから複数の整数値を回復するというトリックはありますか？私のminimaxとnegamaxの両方の実装でうまく動作しますが、アルファベットプルーニングは奇妙な結果を招くようです。

@Override 
public GameState move(GameState state) 
{ 
    int alpha = -INFINITY; 
    int beta = INFINITY; 
    int bestScore = -Integer.MAX_VALUE; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    GameState bestMove = null; 
    for(GameTreeNode child: gameTreeRoot.getChildren()) 
    { 
     if(bestMove == null) 
     { 
      bestMove = child.getState(); 
     } 
     alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta)); 
     if(alpha > bestScore) 
     { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) 
{ 
    if(depth <= 0 || terminalNode(currentNode.getState())) 
    { 
     return getHeuristic(currentNode.getState()); 
    } 
    if(currentNode.getState().getCurrentPlayer().equals(selfColor)) 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return beta; 
      } 
     } 
     return alpha; 
    } 
    else 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return alpha; 
      } 
     } 
     return beta; 
    } 
} 
//Checks to see if the node is terminal 
private boolean terminalNode(GameState state) 
{ 
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw)) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

Answer 1

は、私はあなたが問題を発見したと述べた気づいたが、ミニマックスアルファ・ベータ法は、あなたが書いた

if it is MAX's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result > alpha 
     alpha = result 
     if node is root 
      bestMove = operator of child 
    if alpha >= beta 
     return alpha 
    return alpha 

if it is MIN's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result < beta 
     beta = result 
     if node is root 
      bestMove = operator of child 
    if beta <= alpha 
     return beta 
    return beta 

なるはずの：

if alpha >= beta 
    return beta 
return alpha 

Answer 2

だけ答えるために、あなたの質問

複数の整数vを回復するトリックがありますか？ループの中で再帰的に が呼び出されますか？

はい、Javaでは、オブジェクトを再帰関数呼び出しに渡してから、そのオブジェクトの内容を変更する必要があります。関数が戻ると、変更された値にアクセスすることができます。

例：

class ToBeReturned { 
    int returnValue1; 
    int returnValue2; 
    int returnValue3; 
} 

Answer 3

結果を刈り取るには、ある種の移動命令を実装する必要があります。チェスでは通常キャプチャやチェックです。そのような動きは評価を最も変える傾向があり、剪定に大きな影響を与えます。チェッカーでは、それはあなたの石を取っているかもしれないまたは8位（ごめんなさい使用されている用語を知らない）で自己石を推進している可能性があります。

Answer 4

2013年3月16日には、sage88質問：

はのためのループで再帰呼び出しから複数の整数値を回復するコツはありますか？私のminimaxとnegamaxの両方の実装でうまく動作しますが、アルファベットプルーニングは奇妙な結果を招くようです。

アルファベータプルーニングでは、関心のある出力値はノードのスコアです。最小ノードのベータ値の最終値は、その親の最大ノードのアルファ値であるとみなされます。同様に、最大ノードにおけるアルファの最終値は、その親の最小ノードのベータ値について考慮される。したがって：

あなたの質問に対する答えは最も関連性の高いトリックですので、アルゴリズム自体です。実装における2つのエラーが存在する前記

、：分ノードとその逆からエイドリアンブラックバーンが最初に指摘したように1）、それは間違って返却のアルファは、それによって精度だスキュー、。 2）それは、現在のノードの値の中の親アルファまたはベータを早期に考慮することによって、プルーニングの機会を諦めている。このバージョンでは、戻り値を修正し、剪定を最大化：より多くの楽しみのために楽しく、興味深い質問:)

の貢献のための

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) { 
    if (depth <= 0 || terminalNode(currentNode.getState())) { 
     return getHeuristic(currentNode.getState()); 
    } 
    if (currentNode.getState().getCurrentPlayer().equals(selfColor)) { 
     int currentAlpha = -INFINITY; 
     for (GameTreeNode child : currentNode.getChildren()) { 
      currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta)); 
      alpha = Math.max(alpha, currentAlpha); 
      if (alpha >= beta) { 
       return alpha; 
      } 
     } 
     return currentAlpha; 
    } 
    int currentBeta = INFINITY; 
    for (GameTreeNode child : currentNode.getChildren()) { 
     currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta)); 
     beta = Math.min(beta, currentBeta); 
     if (beta <= alpha) { 
      return beta; 
     } 
    } 
    return currentBeta; 
} 

おかげで、ここでの冗長を取り除く、あなたのmove()方法の明確化ですMath.max()に呼び出す：

@Override 
public GameState move(GameState state) { 
    GameState bestMove = null; 
    int bestScore = -INFINITY; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    for (GameTreeNode child : gameTreeRoot.getChildren()) { 
     int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY); 
     if (alpha > bestScore || bestMove == null) { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

最後に

（さらに楽しく）、私はそれをパラメータなしで呼び出すことができGameStateにこれを移動するものの、terminalNode()の意図を明確にするだけの提案、メソッド名の変更：

private boolean isTerminal(GameState state) { 
    //return Is.any(state.getStatus(), win, lose, draw); 
    return state.getStatus().equals(win) 
     || state.getStatus().equals(lose) 
     || state.getStatus().equals(draw); 
} 

Answer 5

問題は既に解決済みですが、発生した問題はかなり一般的です。したがって、AIエージェントのアルゴリズムの一部を構築するときはいつでも、適切にテストする必要があります。ですから、ミニマックスアルゴリズムが正しいとすれば、多くのランダムツリーを生成し、結果が同じかどうかを確認するだけです。 Pythonでたとえば、あなたがこのような方法でこれを行うことができます：

class Node(): 
    def __init__(self, data, children): 
     self.data = data 
     self.children = children 

def generateTree(depth, branching): 
    total = branching**depth 
    values = [randint(-100, 100) for _ in xrange(total)] 
    level = [Node(values[i], []) for i in xrange(total)] 

    for _ in xrange(depth): 
     total /= branching 
     level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)] 

    return level[0], values 

今、あなたは多くのランダムな木が木を生成し、結果を比較することができます。あなたが実際のゲームに興味があることは動きであるのに対し、

tree, values = generateTree(depth, branching) 
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1) 

---

は、そのミニマックスとα-βリターンだけで最高の価値を忘れないでください。移動を返すことができるように変更するのは簡単ですが、移動がどのように返されるかは開発者が決定します。これは、最良の解決策につながる多くの動きがあるためです（最初のもの、最後のもの、または最も一般的なものはすべての動きを見つけてランダムなものを返すことができます）。あなたのケースでは

問題が返された値のランダムとあったので、良いアプローチをテスト中は、ランダム性を修正することです。