Othello Alpha-Beta Pruning Playing Badly Python
質問
私は現在、Othelloの良いAIを作成しようとしており、Minimaxアルゴリズムを使用してそうしています。しかし、Alpha-Beta Pruningを使用してより深い検索をしようとしたとき、アルゴリズムがひどく再生されているように見えました。 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
解決
あなたのアルファベータコードはおそらく間違っています。プレーヤーが「ターンを通過する」ときに何が起こるか(つまり、利用可能な動きがない)に注意してください。これにより、コードにトリッキーなバグがありました。
アルファ値とベータ値を切り替えた状態で再帰を呼び出しましたか?鉱山はこのように機能します(Java Code):
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()は「ダミーの動き」を返しますが、ボードがまったく変更されず、ターンをパスするだけです。
それが役に立てば幸い!
他のヒント
あなたのAlphabetaの実装は私には健全に見えます。 MinimaxとAlphabetaは、正しく実装されたときに同じ結果を生成するため、少なくとも控えめな検索深度のために、古いMinimaxコードをAlphabetaに対するチェックとして使用できるはずです。同じゲームツリーを検索するときに結果が異なる場合、あなたは何か間違ったことをしたことを知っています。
しかし、おそらく、貧弱な遊びはあなたの「heur」評価機能の何かの結果です。
所属していません StackOverflow