내 minimax 알고리즘이 매 이동을 취소하지 않는 이유는 무엇입니까?

Question

나는 원래 만든 4 인용 보드 게임 AI를 제작 중입니다. 보드 게임에 대한

세부 사항 :

4 팀의 선수들은 동서남북 중 하나에서 동시에 자신의 색깔의 조각을 이동 번갈아. 조각들을 칠판에서 옮길 수 있습니다. 플레이어는 처음에는 5 명이 있습니다. 보드에서 이동 한 각 조각마다 플레이어는 1 생명을 잃습니다. 새로운 조각은 게임 내내 결정 론적으로 산란합니다.

나는 minimax 알고리즘을 수행하는 방법을 찾아보고 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 문에서 할당되지 않은 경우 임의의 방향을 반환합니다.

그리고 여기 내 시도이다 : 나는 depth 4로이 AI를 테스트 할 때

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

, 보드에서 자신의 조각을 이동처럼 바보 같은 동작을 수행하거나 이동할 중 하나를 보인다 그의 한 방향으로 만 조각.

또한 재귀 호출이 반환 될 때 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 
    } 
}