奥赛罗极小极大算法

Question

我正在尝试使用Minimax算法为黑白棋实现一个人工智能玩家。电脑的表现还不错，但并不是很好。请问我在下面的代码中是否正确实现了它？

Coordinate bestCoordinate = null;
public int minimax(MyButton[][] gameBoard, int depth, boolean maximizingPlayer) {
    if (depth == 0) {
        return evaluateBoard(gameBoard);
    }

    if (maximizingPlayer) {
        int bestValue = Integer.MIN_VALUE;
        LinkedList<Coordinate> moves = generateMoves(gameBoard);
        for (Coordinate move : moves) {
            MyButton[][] newBoard = cloneBoard(gameBoard);
            processMove(newBoard, newBoard[move.getxCoordinate()][move.getyCoordinate()]);
            int v = minimax(newBoard, depth - 1, !maximizingPlayer);
            if (v > bestValue) {
                bestValue = v;
                bestCoordinate = move;
            }
        }
        return bestValue;
    }
    else {
        int bestValue = Integer.MAX_VALUE;
        LinkedList<Coordinate> moves = generateMoves(gameBoard);
        for (Coordinate move : moves) {
            MyButton[][] newBoard = cloneBoard(gameBoard);
            processMove(newBoard, newBoard[move.getxCoordinate()][move.getyCoordinate()]);
            int v = minimax(newBoard, depth - 1, !maximizingPlayer);
            if (v < bestValue) {
                bestValue = v;
                bestCoordinate = move;
            }
        }
        return bestValue;
    }
}

此外，这是我的评估函数：

public int evaluateBoard(MyButton[][] gameBoard) {

    int blackPieces = 0;
    int whitePiecess = 0;

    for (MyButton[] array : gameBoard) {
        for (MyButton button : array) {
            if (button.getBackground().equals(Color.black)) {
                blackPieces++;
            } else if (button.getBackground().equals(Color.WHITE)) {
                whitePiecess++;
            }
        }
    }

    int cornerBonus = 10;
    if (gameBoard[0][0].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[0][getBoardWidth() - 1].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][0].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][getBoardWidth() - 1].getBackground().equals(Color.BLACK)) {
        blackPieces += cornerBonus;
    }
    if (gameBoard[0][0].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[0][getBoardWidth() - 1].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][0].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    if (gameBoard[getBoardHeight() - 1][getBoardWidth() - 1].getBackground().equals(Color.WHITE)) {
        whitePiecess += cornerBonus;
    }
    return whitePiecess - blackPieces;
}

电脑总是执白先手，而人类执黑后手。我主要不确定的是，尽管保护角落可以得到加分，但电脑似乎并没有这样做。我的代码或逻辑有什么问题吗？

- 100001

---

我的极小化极大算法中的递归有问题吗？我注意到计算机总是选择第一个可用的移动（在数组中最高的那个），但我不知道问题出在哪里。 - 100001

一个问题和一个提示。首先，你的generateMoves如何能够在不知道哪一方移动的情况下做出它的事情？其次，evaluateBoard的结果必须对黑色进行符号反转。也就是说，如果某个位置得分为27，从白色的角度来看，则从黑色的角度来看，它必须是-27，依此类推。 - 500 - Internal Server Error

但是这不是由我的极小化极大算法处理的吗？我允许棋盘评估保持不变，但在最大化和最小化该数字之间交替。 - 100001

我尝试过了，但似乎并没有改变游戏的行为。我有点困惑，因为无论我将角落奖励设置多大，计算机仍然让我占据角落方块。我不确定为什么会这样。 - 100001

我认为您只想在深度为初始深度时更新最佳坐标。 - Jared

Answer 1

你正在更新每个深度的最佳移动。在函数外部定义一个名为SEARCH_DEPTH的常量，每次调用函数时使用它并进行if检查：

if(depth == SEARCH_DEPTH) {
    bestCoordinate = move;
}

此外，假设您是最大化玩家，您只想在if(maximizingPlayer)块中设置移动。

- Jared

Answer 2

我自己没有测试过你的代码，但那是极小化算法，看起来写得正确（假设你的辅助函数实现正确）。我有一些观点可能会让你了解为什么你的代理程序没有表现最佳：

1. 我看到你的目标函数是代理程序拥有的棋子数减去对手拥有的棋子数，再加上角落棋子的奖励。这似乎是最好的策略，但我建议你阅读一下优秀的黑白棋玩家如何下棋。通常，他们会尽可能地翻转一颗棋子，直到晚期，因为这样他们有更多的机会。
2. 极小化算法不一定会返回导致占据角落的移动，即使你高度评价它们，因为它可能会被对手的移动所破坏。例如，假设你的算法在计算机的回合中向前看三个回合，因此它首先查看一个具有高目标函数的状态，其中它可以占据一个角落。然而，你的对手将选择最小化你的目标函数的路线，因此计算机不会认为朝着占据角落的棋子的移动是最优的，因为存在风险。我不知道这有多容易，但如果你能以某种方式可视化树形结构，你可能能够弄清楚这是否是问题所在。

- Brown Philip

---

在回答之前，您应该至少测试代码。 - Pika Supports Ukraine

没有辅助函数，无法测试代码。它们并不简单。但是我可以说，这是正确的算法。根据您的回复，我自己编写了这个算法并进行了测试。唯一的区别是我使用了max/min函数来更新本地变量“bestValue”，而不是条件语句。看起来它正在工作。 - Brown Philip