爲什麼我的極小極大算法不會撤消每一步？

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 
    } 
}