2

三目並べアプリケーションにネガマックス検索機能を実装しようとしていますが、最適な値が返されず、半ランダムに推測しているように見えます。私のコードの関連部分は次のとおりです。

public int negamax(Result result, Token token) {
    if (result == Result.WIN) {
        return 1;
    } else if (result == Result.DRAW) {
        return 0;
    }

    int best = -1;

    for (Coordinate move : Board.getAvailableMoves()) {
        Token other = token.getOther();
        Result r = Board.makeMove(move, other);
        int eval = -negamax(r, other);
        Board.unmakeMove(move);

        if (eval > best) {
            best = eval;
        }
    }

    return best;
}

public Coordinate getNegamaxMove(Token token) {
    int score = -1;
    Coordinate bestMove = null;

    for (Coordinate move : Board.getAvailableMoves()) {
        Result result = Board.makeMove(move, token);
        int newScore = negamax(result, token);
        Board.unmakeMove(move);

        if (newScore >= score) {
            score = newScore;
            bestMove = move;
        }
    }

    return bestMove;
}

ボードをパラメーターとして渡すのではなく、WIN、DRAW、VALID、または OCCUPIED (最後の 2 つは現在の議論には関係ありません) のいずれかである移動の結果を渡すことに注意することが重要です。自明です。Coordinate クラスは、移動の行と列の値を保持するだけです。

どうもありがとうございました ：）

4

1 に答える 1

2

negamax メソッドには 2 つの問題がありました。まず、ループ内ではなく、利用可能なすべての移動をループする前に、トークンを変更する必要があります。第二に、getNegamaxMove メソッドでベスト ムーブをチェックするため、negamax メソッドでは、ベスト ムーブではなくワースト ムーブを追跡する必要があります。比較のために古い部分をコメントアウトした実際の実装を次に示します。

public int negamax(Result result, Token token) {
    if (result == Result.WIN) {
        return 1;
    } else if (result == Result.DRAW) {
        return 0;
    }

    int worst = 1;
    // int best = -1

    Token other = token.getOther();
    for (Coordinate move : Board.getAvailableMoves()) {
        // Token other = token.getOther();
        Result r = Board.makeMove(move, other);
        int eval = -negamax(r, other);
        Board.unmakeMove(move);

        // if (eval > best) {
        //     best = eval;
        // }

        if (eval < worst) {
            worst = eval;
        }
    }

    // return best
    return worst;
}
于 2015-05-17T12:29:01.283 に答える