私のミニマックスアルゴリズムは、すべての動きを元に戻すのはなぜですか？

Question

私が作ったオリジナルの4人用ボードゲームのAIを作成しています。ボードゲームに関する

詳細：

4選手は、東西南北方向のいずれかに同時に自分の色の駒を移動するためにターンを取ります。作品はボードから外すことができます。各プレイヤーは、開始時に5人の命を持ちます。ボードから外された各部分につき、プレイヤーは1人の命を失う。新しいピースが決定的にゲーム全体を通して生まれます。

ミニマックスアルゴリズムの実行方法を調べて、thisが見つかりました。私はそれを読んですべてを理解していると思ったので、1.5節のJavaコードをSwiftに翻訳しようとしました。ここで

は私の思考プロセスである：

• 私のゲームは4人の選手を持っているので、私は選手たちを最小限に抑えるよう皆を扱っていました。
• Javaコードには、移動が取り消された行があります。私のゲームのゲーム状態はそれぞれの動きで大きく変わることがあるので、すべてのゲーム状態を配列に格納するだけで、何かを元に戻す必要があるときは配列のdropLastに電話することができます。
• 私のゲームの動きはDirection enumと表されているので、代わりにJavaコードのようなint配列なら(Int, Direction)タプルを返します。
• gameはちょうど私がgame上moveUp/Down/Left/Rightのいずれかの方法で呼び出すたびに変更されますgameStates.last!
• game.currentPlayerを返す計算されたプロパティですので、私は次の選手だ誰かを決定するために余分なコードを記述する必要はありません。
• 最後の行で(bestScore, bestDirection)を返す必要がありますが、bestDirectionが割り当てられていないことがあります。したがって、私はbestDirectionをオプションにしました。 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({$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()

編集

何が本当にしたいことは、スタックデータ構造です。ここに1つあります。

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