2017-03-23 8 views
1

最初に私はわずかに間違ったタイトルのために申し訳ありません、私はちょうどそれが30語の長さにしたくありませんでした。 私が実装したアルファ/ベータのプルーニングは、私がTicTacToeのゲームにそれを適用したときの評価の量を大幅に減らしました。Alpha/Betaプルーニングが私のMiniMaxアルゴリズムに影響しないのはなぜですか?

評価数の各ペアは、入力と同じゲーム状態で測定されます。

Pruning vs no pruning

私は私が取り組んできたニューラルネットワークをプレイチェッカーズに剪定を実装する際に問題が生じます。私はこれらのアルゴリズムを以前に扱ったことがないので、MiniMax + Alpha/Betaを試すためにTicTacToeゲームを作り上げました。

NNでの同じ種類の実験です。コードのための今

checkers minimax evalscheckers minimax with pruning evals

(チェッカー1、彼らはしかし、ほぼ同一であり、あなたは三目並べのバージョンでのぞき見を持っているしたい場合は私に知らせて)。

両方のメソッドの最初の部分が一度だけ貼り付けられますが、それらは完全に同一であるため、わずかに異なるため、両方の署名が表示されます。

コードをより明確にするための小さなメモ。

移動がすべて含まれているオブジェクトです...ゲームは勝ってきた場合は/ etc描かれ、それはターン作品のトラック、利用できる移動、 を保つオブジェクトであります移動に関連する情報、私が メソッドの最初の行としてクローンを作成すると、私は単に 与えられたボードのクローンを作成し、コンストラクタはそれに与えられた移動を適用します。

private double miniMax(Board b, Move m, int depth) { 

private double alphaBeta(Board b, Move m, int depth, double alpha, double beta) { 

両方の方法の始まり:

Testboard clone = new Testboard(b, m); 
    // Making a clone of the board in order to 
    // avoid making changes to the original one 

    if (clone.isGameOver()) { 

     if (clone.getLoser() == null) 
      // It's a draw, evaluation = 0 
      return 0; 

     if (clone.getLoser() == Color.BLACK) 
      // White (Max) won, evaluation = 1 
      return 1; 

     // Black (Min) won, evaluation = -1 
     return -1; 
    } 

    if (depth == 0) 
     // Reached the end of the search, returning current Evaluation of the board 
     return getEvaluation(clone); 

通常のミニマックス継続:アルファ/ベータpruninと

// If it's not game over 
    if (clone.getTurn() == Color.WHITE) { 

     // It's white's turn (Maxing player) 
     double max = -1; 
     for (Move move : clone.getMoves()) { 
      // For each children node (available moves) 
      // Their minimax value is calculated 
      double score = miniMax(clone, move, depth-1); 
      // Only the highest score is stored 
      if (score > max) 
       max = score; 
     } 
     // And is returned 
     return max; 
    } 

    // It's black's turn (Min player) 
    double min = 1; 
    for (Move move : clone.getMoves()) { 
     // For each children node (available moves) 
     // Their minimax value is calculated 
     double score = miniMax(clone, move, depth-1); 
     // Only the lowest score is stored 
     if (score < min) 
      min = score; 
    } 
    // And is returned 
    return min; 
} 

MiniMaxのグラムの継続:

// If it's not game over 
    if (clone.getTurn() == Color.WHITE) { 

     // It's white's turn (Maxing player) 
     for (Move move : clone.getMoves()) { 

      // For each children node (available moves) 
      // Their minimax value is calculated     
      double score = alphaBeta(clone, move, depth-1, alpha, beta); 

      if (score > alpha) 
       // If this score is greater than alpha 
       // It is assigned to alpha as the new highest score 
       alpha = score; 
      if (alpha >= beta) 
       // The cycle is interrupted early if the value of alpha equals or is greater than beta 
       break; 
     } 
     // The alpha value is returned 
     return alpha; 
    } 

    // It's black's turn (Min player) 
    for (Move move : clone.getMoves()) { 

     // For each children node (available moves) 
     // Their minimax value is calculated    
     double score = alphaBeta(clone, move, depth-1, alpha, beta); 

     if (score < beta) 
      // If this score is lower than beta 
      // It is assigned to beta as the new lowest score 
      beta = score; 
     if (alpha >= beta) 
      // The cycle is interrupted early if the value of alpha equals or is greater than beta 
      break; 
    } 
    // The beta value is returned 
    return beta; 
} 

私は正直にこだわっていると私は私が試してみて、何が起こっているかを把握するために何ができるかわかりません。私はいくつかの異なるランダムに生成されたニューラルネットワーク上でMiniMax + A/Bを試しましたが、評価の数が増えると改善は見られませんでした。私はここの誰かがこの状況にいくつかの光を当てることができれば幸いです!

+0

私はそれが唯一のものだとは考えていますが、理由の1つは移動注文である可能性があります。あなたが最初に良い動きをしようとすると、さらに多くのものが剪定されます。 – maraca

+0

@maracaこんにちは、ありがとうございました。動きは無作為に並べられています。私は多くの実験を行いましたが、α/βの有無にかかわらずミニマムの評価数は全く同じです。コードにはさらに重大な間違いがあります。 評価の数が同じになるように時々それを作るかもしれませんが、いつもそうでないように感じます。 – Daniel

+2

評価の深さは?ボードの良さを測定する定常状態の評価関数は何ですか?チェッカーツリーは深いことがあります。チック - タック - つま先、あまりそうではありません。チェッカーのあなたの評価関数は基本的にすべてのボードに0を与えています。したがって、プルーニングは発生しません。 – tucuxi

答えて

0

私がこれを理解するのを助けてくれてありがとう、彼がコメントだけで答えたので、自分自身に答えようとしてくれてありがとう。

私が投稿したコードに何も問題はありません。問題は、検索が深度制限に達したときに使用していた評価機能にあります。

私は本質的にちょうどランダムな値を吐き出しているまだ訓練されていないニューラルネットワークを使用していました。これは、必要とされる答えとの一貫性がないので、MiniMax + A/Bを剪定が起こるために。

関連する問題