最初に私はわずかに間違ったタイトルのために申し訳ありません、私はちょうどそれが30語の長さにしたくありませんでした。 私が実装したアルファ/ベータのプルーニングは、私がTicTacToeのゲームにそれを適用したときの評価の量を大幅に減らしました。Alpha/Betaプルーニングが私のMiniMaxアルゴリズムに影響しないのはなぜですか?
評価数の各ペアは、入力と同じゲーム状態で測定されます。
私は私が取り組んできたニューラルネットワークをプレイチェッカーズに剪定を実装する際に問題が生じます。私はこれらのアルゴリズムを以前に扱ったことがないので、MiniMax + Alpha/Betaを試すためにTicTacToeゲームを作り上げました。
NNでの同じ種類の実験です。コードのための今
(チェッカー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を試しましたが、評価の数が増えると改善は見られませんでした。私はここの誰かがこの状況にいくつかの光を当てることができれば幸いです!
私はそれが唯一のものだとは考えていますが、理由の1つは移動注文である可能性があります。あなたが最初に良い動きをしようとすると、さらに多くのものが剪定されます。 – maraca
@maracaこんにちは、ありがとうございました。動きは無作為に並べられています。私は多くの実験を行いましたが、α/βの有無にかかわらずミニマムの評価数は全く同じです。コードにはさらに重大な間違いがあります。 評価の数が同じになるように時々それを作るかもしれませんが、いつもそうでないように感じます。 – Daniel
評価の深さは?ボードの良さを測定する定常状態の評価関数は何ですか?チェッカーツリーは深いことがあります。チック - タック - つま先、あまりそうではありません。チェッカーのあなたの評価関数は基本的にすべてのボードに0を与えています。したがって、プルーニングは発生しません。 – tucuxi