为什么我的 minimax 算法不撤消每一步？

Question

我正在为我制作的原创 4 人棋盘游戏创建 AI。

桌游详情：

4 名玩家轮流在四个主要方向之一同时移动他们的彩色棋子。棋子可以从棋盘上移开。每个玩家在开始时都有 5 条生命。对于每从棋盘上移走的棋子，玩家都会失去 1 点生命。新棋子将在整个游戏过程中确定性地产生。

我查找了极小极大算法的实现方法并找到了 this。我通读了它并认为我理解了一切，所以我尝试将第 1.5 节中的 Java 代码翻译成 Swift.

这是我的思考过程：

由于我的游戏有 4 个玩家，我会将其他所有人视为最小化玩家。
在Java代码中，有一行是撤消移动的地方。由于我的游戏的游戏状态会在每次移动中发生巨大变化，所以我会将所有游戏状态存储在一个数组中，当需要撤消某些操作时，我可以在数组上调用 dropLast。
由于我游戏中的移动表示为 Direction 枚举，如果像 Java 代码这样的 int 数组，我将 return 一个 (Int, Direction) 元组代替。
game 是计算得到的属性，它只是 returns gameStates.last!

game

moveUp/Down/Left/Right

game.currentPlayer 都会改变，所以我不需要编写额外的代码来决定谁是下一个玩家。
在最后一行，我需要 return (bestScore, bestDirection)，但我意识到有时 bestDirection 没有被分配。因此，我将 bestDirection 设为可选。如果在return语句中没有赋值，我就return一个任意方向。

这是我的尝试：

private func minimax(depth: Int, color: Color) -> (score: Int, direction: Direction) {
    var bestScore = color == myColor ? Int.min : Int.max
    var currentScore: Int
    var bestDirection: Direction?
    if game.players.filter({[=10=].lives > 0}).count < 2 || depth == 0 {
        // This is a call to my heuristic evaluation function
        bestScore = evaluateHeuristics()
    } else {
        // if the player has no pieces on the board, just move up since moving in any direction won't change anything
        for move in (game.board.indicesOf(color: color).count == 0 ? [Direction.up] : [Direction.up, .down, .left, .right]) {
            let gameCopy = game.createCopy()
            switch move {
            case .up: gameCopy.moveUp()
            case .down: gameCopy.moveDown()
            case .left: gameCopy.moveLeft()
            case .right: gameCopy.moveRight()
            }
            gameStates.append(gameCopy)
            // myColor is like mySeed in the original Java code
            if color == myColor {
                currentScore = minimax(depth: depth - 1, color: game.currentPlayer.color).score
                if currentScore > bestScore {
                    bestScore = currentScore
                    bestDirection = move
                }
            } else {
                currentScore = minimax(depth: depth - 1, color: game.currentPlayer.color).score
                if currentScore < bestScore {
                    bestScore = currentScore
                    bestDirection = move
                }
            }
            _ = gameStates.dropLast()
        }
    }
    return (bestScore, bestDirection ?? .left)
}

当我用 depth 为 4 测试这个 AI 时，它似乎要么做出愚蠢的举动，比如将他的棋子移出棋盘，要么只向一个方向移动他的棋子。

我也注意到在递归调用return时gameStates的长度大约是90。通常它应该是 1 对吧？因为在递归调用 return 时 AI 尝试的所有动作都应该已经撤消，并且 gameStates 将只包含初始状态。

我做错了什么？

Answer 1

dropLast() returns an array slice containing all but the last element of the array. It does not modify the original array. Use removeLast()

编辑

你真正想要的是一个栈数据结构。这是一个。

public struct Stack<Element>
{
    fileprivate var elements: [Element] = []

    public init() {}

    ///    Push an element onto the top of the stack
    ///
    /// - parameter newElement: The element to push
    public mutating func push(_ newElement: Element)
    {
        elements.append(newElement)
    }

    ///    Pops the top element off the stack
    ///
    ///    - returns: The top element or nil if the stack is empty.
    public mutating func pop() -> Element?
    {
        let ret = elements.last
        if ret != nil
        {
            elements.removeLast()
        }
        return ret
    }

    ///  The top element of the stack. Will be nil if the stack is empty
    public var top: Element?
    {
        return elements.last
    }

    /// Number of items in the stack
    public var count: Int
    {
        return elements.count
    }

    /// True if the stack is empty
    public var isEmpty: Bool
    {
        return elements.isEmpty
    }
}

为什么我的 minimax 算法不撤消每一步？

Why is my minimax algorithm not undoing every move?

artificial-intelligence

minimax

swift