为什么我的极小极大算法不会撤消每一步？

Question

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

详情：

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

我抬起头如何做一个minimax算法，发现this。我通读了这篇文章，并认为我理解了所有内容，所以我试图将第1.5节中的Java代码翻译成Swift。

这里是我的思维过程：

• 由于我的游戏有4名球员，我会像对待其他人尽量减少球员。
• 在Java代码中，有一行代表移动。由于我的游戏的游戏状态在每次移动中都会发生剧烈变化，因此我只会将所有游戏状态存储在数组中，并且在需要撤消某些操作时，我可以在数组上调用dropLast。
• 由于在我的游戏中的移动被表示为Direction枚举，我将返回一个(Int, Direction)元组，而不是像Java代码那样的int数组。
• game是计算属性，它只是返回gameStates.last!
• game.currentPlayer我每次调用上game的moveUp/Down/Left/Right方法之一，时间会改变，所以我不需要编写额外的代码来决定谁是未来的球员。
• 在最后一行，我需要返回(bestScore, bestDirection)，但我意识到有时bestDirection未分配。所以我做了bestDirection一个可选。如果它没有在返回语句中分配，我只会返回任意方向。

这里是我的尝试：

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({$0.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) 
} 

当我与4的depth测试这个AI，似乎无论做愚蠢的举动，如移动他的棋子落板，或将他的件只在一个方向。

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

我做错了什么？

Answer 1

dropLast()返回一个包含除数组最后一个元素以外所有元素的数组。它不会修改原始数组。使用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 
    } 
}