2

ミニマックスアルゴリズムがどのように機能するかをよりよく理解するために、私は三目並べプログラムに取り組んできました。次の実装は、コンピューターがゲームに負ける可能性があるため、正しく機能していません。プログラムが正しく動作している場合、理論的にはこれは不可能なはずです...

ミニマックスの実装、または最善の手の取得で間違いを犯しましたか?

私は以前にアルゴリズムを実装したことがありません:s

評価関数

public static int evaluate(char[] board, char turn) {
    if (isWinFor('x', board)) {
        return -1;
    } else if (isWinFor('o', board)) {
        return 1;
    } 
    return 0;
}

ミニマックス

public static int alphabeta(char[] board, int depth, char turn, int alpha, int beta) {
    if (depth == 0 || gameOver(board)) {
        return evaluate(board, turn);
    } else {
        for (int move : possibleMoves(board)) {
            makeMove(board, turn, move);
            turn = changeTurn(turn);
            int value = alphabeta(board, depth--, turn, alpha, beta);   
            makeMove(board, ' ', move);
            if (turn == 'o') {
                if (value > alpha) {
                    alpha = value;
                }
                if (alpha >= beta) {
                    return beta;
                }
            } else if (turn == 'x') {
                if (value < beta) {
                    beta = value;
                }
                if (beta <= alpha) {
                    return alpha;
                }
            }               
        }
        if (turn == 'o') {
            return  alpha;
        } else {
            return  beta;
        }             
    }
}

最善の動きを見つける

public static void getBestMove(char[] board, char turn) {
    Random random  = new Random();
    int bestValue = -10000;
    List<Integer> choices = new ArrayList<Integer>();
    for (int move : possibleMoves(board)) {
        makeMove(board, turn, move);
        turn = changeTurn(turn);
        int value = alphabeta(board, 3, turn, -10000, 10000);   
        makeMove(board, ' ', move);
        if (value > bestValue) {
            bestValue = value;
            //start code edit
            choices.clear();
            //end code edit
            choices.add(move);
        } else if (value == bestValue) {
            choices.add(move);
        }
    }
    makeMove(board, turn, choices.get(random.nextInt(choices.size())));
}

ありがとうございました。

4

2 に答える 2

0

それは簡単です: 完璧なプレーヤーはツリー全体を最大の深さ (カットオフ ノードを除く) まで検索する必要がありますが、プログラムを 4 プライのみに制限しました!

find best move に誤りがあります:

int value = alphabeta(board, 3, turn, -10000, 10000);

に変更するだけです

int value = alphabeta(board, 8, turn, -10000, 10000);
于 2015-08-29T07:17:35.047 に答える