3

チェスのようなゲーム用に negamax アルゴリズムを作成しましたが、最終的なボード値の結果を使用する方法を知りたいです。ネガマックス アルゴリズムの最終リターンは、プレイヤーが最善の手を打った後のボードの値を表していることは理解していますが、それは正確には有用な情報ではありません。私はその動きが何であるかを知る必要があります。

コードは次のとおりです。

public int negamax(Match match, int depth, int alpha, int beta, int color) {
    if(depth == 0) {
        return color*stateScore(match);
    }

    ArrayList<Match> matches = getChildren(match, color);

    if(matches.size() == 0) {
        return color*stateScore(match);
    }

    int bestValue = Integer.MIN_VALUE;

    for(int i = 0; i != matches.size(); i++) {
        int value = -negamax(matches.get(i), depth-1, -beta, -alpha, -color);

        if(value > bestValue) {
            bestValue = value;
        }

        if(value > alpha) {
            alpha = value;
        }

        if(alpha >= beta) {
            break;
        }
    }

    return bestValue;
}

public void getBestMove(Match match, int color) {

    int bestValue = negamax(match, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, color);

    // What to do with bestValue???

}

bestValue が決定された後、現在の一致状態の子を再評価することを考えました。次に、それらを反復処理して、stateScore が bestValue に等しい子を見つけます。しかし、それらの多くはとにかく同じstateScoreを持つため、それは機能しません。それは、それらがどのカウントにつながるかです...

4

1 に答える 1

3

qsearch と alpha-beta を行っていることがわかります。あなたのアルゴリズムはよく知られていますが、重要な部分がありません。

チェス検索の基本的なアルゴリズムを大まかに説明しましょう。これは Stockfish (世界最強のエンジン) にも適用されます。

search(Position p) {

    if (leaf node)
        qsearch(p)

    if (need to do move reduction)
        do_move_reduction_and_cut_off(p)

    moves = generate_moves(p)

    for_each(move in moves) {            
        p.move(move)
        v = -search(p, -beta, -alpha)
        p.undo(move)

        store the score and move into a hash table

        if (v > beta)
           cutoff break;           
    }

これは非常に簡単なスケッチにすぎませんが、すべてのチェス アルゴリズムはこれに従います。あなたのバージョンとそれを比較してください。p.move(move) と p.undo(move) を行っていないことに気づきましたか?

基本的に、従来のアプローチでは、特定の位置の動きのリストが生成されます。動きをループし、再生して元に戻し、検索します。そうすれば、どの動きがどのスコアを生み出すかを正確に知ることができます。

また、移動とスコアをハッシュ テーブルに格納するための行にも注意してください。これを行うと、ルート ノードから主要なバリエーション全体を簡単に再構築できます。

Java クラスの Match の中に正確に何があるかはわかりませんが、いずれにせよ、あなたの試みは近いものでしたが、検索を行うための古典的な方法ではありませんでした。検索アルゴリズムで位置オブジェクトを指定する必要がありますが、代わりに Match オブジェクトを指定したことを思い出してください。これは間違っています。

于 2014-09-02T05:07:44.983 に答える