Connect4 minimax算法做出了愚蠢的动作

loading...


1

我正在尝试实现一种算法,它将为Connect 4的游戏选择最佳的下一步 . 我只是想确保基本的 minimax 正常工作,我实际上是在4x4字段上测试它就像一个Connect 3 . 这样,当算法做出愚蠢的举动时,我就更加明显了 .

问题是算法 always 以最左边的移动开始游戏,并且在游戏中它也会看到最好的移动 .

我已经彻底测试了方法 makeMove()undoMove()getAvailableColumns()isWinningMove()isLastSpot() 所以我绝对是 sure 问题不存在 .

这是我的算法 .

NextMove.java

private static class NextMove {
    final int evaluation;
    final int moveIndex;

    public NextMove(int eval, int moveIndex) {
        this.evaluation = eval;
        this.moveIndex = moveIndex;
    }

    int getEvaluation() {
        return evaluation;
    }

    public int getMoveIndex() {
        return moveIndex;
    }
}

The Algorithm

private static NextMove max(C4Field field, int movePlayed) {
    // moveIndex previously validated

    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);

    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.RED);
        return new NextMove(DRAW, movePlayed);
    }

    field.playMove(movePlayed, C4Symbol.RED);

    // 2) moveIndex is not a final move
    // --> try all possible next moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MIN_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {           
        field.playMove(moveIndex, C4Symbol.BLUE);

        final int currentEval = min(field, moveIndex).getEvaluation();
        if (currentEval > bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }

        field.undoMove(moveIndex);
    }

    return new NextMove(bestEval, bestMove);
}

private static NextMove min(C4Field field, int movePlayed) {
    // moveIndex previously validated

    // 1) check if moveIndex is a final move to make on a given field
    field.undoMove(movePlayed);

    // check
    if (field.isWinningMove(movePlayed, C4Symbol.BLUE)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(BLUE_WIN, movePlayed);
    }
    if (field.isWinningMove(movePlayed, C4Symbol.RED)) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(RED_WIN, movePlayed);
    }
    if (field.isLastSpot()) {
        field.playMove(movePlayed, C4Symbol.BLUE);
        return new NextMove(DRAW, movePlayed);
    }

    field.playMove(movePlayed, C4Symbol.BLUE);

    // 2) moveIndex is not a final move
    // --> try all other moves
    final List<Integer> possibleMoves = field.getAvailableColumns();
    int bestEval = Integer.MAX_VALUE;
    int bestMove = 0;
    for (int moveIndex : possibleMoves) {
        field.playMove(moveIndex, C4Symbol.RED);

        final int currentEval = max(field, moveIndex).getEvaluation();
        if (currentEval < bestEval) {
            bestEval = currentEval;
            bestMove = moveIndex;
        }

        field.undoMove(moveIndex);
    }

    return new NextMove(bestEval, bestMove);
}

这个想法是算法接受 currentFieldlastPlayedMove 的参数 . 然后它检查最后一次移动是否以某种方式完成了游戏 . 如果确实如此,我只是返回那一步,否则我会深入了解后续的动作 .

蓝色玩家是MAX,红色玩家是MIN .

在每个步骤中,我首先撤消最后一步,因为更容易检查“下一步”移动是否将完成游戏,而不是检查当前字段是否已完成(这将需要分析该字段中所有可能的获胜选项) . 检查后,我只是重做了一下 .

从某种原因,这不起作用 . 我坚持了好几天!我不知道出了什么问题......任何帮助都非常感谢!

0回答

No Data

loading...

评论

暂时没有评论!