Warum macht mein Minimax-Algorithmus nicht jede Bewegung rückgängig?

Question

Ich erstelle eine KI für ein original 4-Spieler-Brettspiel, das ich gemacht habe.

Details zum Brettspiel:

4 Spieler abwechselnd ihre farbigen Stücke gleichzeitig in einer der vier Himmelsrichtungen zu bewegen. Stücke können von der Tafel bewegt werden. Die Spieler haben jeweils 5 Leben am Start. Für jedes vom Brett entfernte Stück verliert der Spieler 1 Lebenspunkt. Neue Teile werden während des Spiels deterministisch erscheinen.

Ich suchte nach einem Minimax-Algorithmus und fand this. Ich las das durch und dachte, ich würde alles verstehen, also habe ich versucht, den Java-Code in Abschnitt 1.5 in Swift zu übersetzen.

Hier ist mein Denkprozess:

• Da mein Spiel 4 Spieler hat, würde ich alle anderen als die Minimierung Spieler behandeln.
• Im Java-Code gibt es eine Zeile, in der die Verschiebung rückgängig gemacht wird. Da sich der Spielzustand meines Spiels bei jedem Zug drastisch ändern kann, würde ich einfach alle Spielstände in einem Array speichern. Wenn etwas rückgängig gemacht werden muss, kann ich einfach dropLast auf dem Array aufrufen.
• Da ein Zug in meinem Spiel als Direction enum dargestellt wird, werde ich stattdessen ein (Int, Direction) Tupel zurückgeben, wenn ein int-Array wie der Java-Code.
• game ist eine berechnete Eigenschaft, die gerade gameStates.last!
• game.currentPlayer zurück wird jedes Mal, wenn ich eine der moveUp/Down/Left/Right Methoden auf game nennen ändern, so dass ich nicht brauchen keine zusätzlichen Code zu schreiben, um zu entscheiden, wer der nächste Spieler ist.
• In der letzten Zeile muss ich (bestScore, bestDirection) zurückgeben, aber ich erkannte manchmal bestDirection ist nicht zugewiesen. Daher habe ich bestDirection optional gemacht. Wenn es bei der Return-Anweisung nicht zugewiesen ist, gebe ich einfach eine beliebige Richtung zurück.

Und hier ist mein Versuch:

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

Wenn ich diese AI testen mit einem depth von 4, so scheint es entweder zu dumm bewegt zu tun, wie seine Stücke weg vom Brett bewegt oder zu bewegen sein Stücke nur in einer Richtung.

Ich bemerkte auch, dass gameStates eine Länge von etwa 90 hat, wenn der rekursive Aufruf zurückgibt. Normalerweise sollte es 1 sein oder? Weil alle Bewegungen, die die KI versucht hat, zu dem Zeitpunkt rückgängig gemacht werden sollten, zu dem der rekursive Aufruf zurückkehrt, und gameStates wird nur den Anfangszustand enthalten.

Was habe ich falsch gemacht?

Answer 1

dropLast() gibt ein Array-Segment zurück, das alle bis auf das letzte Element des Arrays enthält. Es ändert das ursprüngliche Array nicht. Verwenden removeLast()

bearbeiten

Was Sie wirklich wollen, ist ein Stapel-Datenstruktur. Hier ist eins.

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