17

アルファベータ法の基本的な実装はありますが、移動順序を改善する方法がわかりません。浅い検索、反復深化、またはbestMovesから遷移表への格納で実行できることを読みました。

このアルゴリズムでこれらの改善の1つを実装する方法について何か提案はありますか？

 public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) {
    if (depth == 0) {
        return board.evaluateBoard();
    }

    Collection<Move> children = board.generatePossibleMoves(player);
    if (player == 0) {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result > alpha)) {
                alpha = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (alpha >= beta) {
                break;
            }
        }
        return alpha;
    } else {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result < beta)) {
                beta = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (beta <= alpha) {
                break;
            }
        }
        return beta;
    }
}

public int next(int player) {
    if (player == 0) {
        return 4;
    } else {
        return 0;
    }
}
4

2 に答える 2

23

  • 浅い検索を使用したノードの並べ替えは簡単です。再帰的にチェックする前に、状態の各子のヒューリスティック値を計算します。次に、これらの状態の値を並べ替え[最大頂点の場合は降順、最小頂点の場合は昇順]、並べ替えられたリストでアルゴリズムを再帰的に呼び出します。アイデアは、状態が浅い深さで良好である場合、それは深い状態でも良好である可能性が高く、それが真実である場合、より多くの剪定を取得するということです。

    並べ替えは、この前に行う必要があります[ifとelse句の両方で]

    for (Move move : children) {

  • 動きの保存も簡単です。多くの状態は2回計算されます。状態の計算が終了したら、[計算の深さとともに保存してください。それは重要です！] HashMap。頂点で計算を開始するときに最初に行うことは、計算済みかどうかを確認することです。計算済みの場合は、キャッシュされた値を返します。その背後にある考え方は、さまざまなパスから多くの状態に到達できるということです。したがって、このようにして、冗長な計算を排除できます。

    変更は、メソッドの最初の行の両方で行う必要があります[のようなものif (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))][優雅さと効率の欠如のためにすみません-ここでアイデアを説明するだけです]。 また、各ステートメントの前に
    追加する必要があります。cache.put(...)return

于 2012-04-01T13:00:18.367 に答える
4

まず第一に、アルファベータプルーニングアルゴリズムにおける移動順序の背後にある理由を理解する必要があります。アルファベータはミニマックスと同じ結果を生成しますが、多くの場合、無関係なブランチを検索しないため、より高速に実行できます。

剪定が保証されていないため、常に高速であるとは限りません。最悪の場合、剪定がまったく行われず、ミニマックスとまったく同じツリーが検索され、a/b値の簿記のために遅くなります。最良の場合（最大剪定）では、同時に2倍の深さの木を検索できます。ランダムツリーの場合、同時に4/3倍深く検索できます。

移動順序は、いくつかの方法で実装できます。

  1. ドメインの専門家がいて、どの動きが優れているかを提案してくれます。たとえば、ポーンのチェスプロモーションでは、価値の高いピースを価値の低いピースでキャプチャすることは、平均して良い動きです。チェッカーでは、チェッカーを少なくするよりも、移動するチェッカーを多く殺す方が適切であり、クイーンを作成する方が適切です。したがって、移動生成関数は前により良い移動を返します
  2. 深さ1レベルでの位置を評価することで、移動がどれだけ優れているかをヒューリスティックに取得できます（浅い検索/反復深化）。深さn-1で評価を計算し、動きを並べ替えてから、深さnで評価しました。

あなたが言及した2番目のアプローチは、移動順序とは何の関係もありません。それは、評価関数が高価であり、多くのポジションが何度も評価されるという事実と関係があります。これを回避するために、計算した位置の値をハッシュに保存し、後で再利用できます。

于 2015-10-16T03:04:38.783 に答える