Why is my minimax algorithm not undoing every move?

Question

I am creating an AI for an original 4-player board game that I made.

Details about the board game:

4 players take turns to move their coloured pieces simultaneously in one of the four cardinal directions. Pieces can be moved off the board. Players each have 5 lives at the start. For each piece moved off the board, the player lose 1 life. New pieces will spawn deterministically throughout the game.

I looked up how to do a minimax algorithm and found this. I read through that and thought I understood everything, so I tried to translate the Java code in Section 1.5 to Swift.

Here is my thought process:

• Since my game has 4 players, I would treat everyone else as minimising players.
• In the Java code, there is a line where the move is undone. Since my game's game state can change drastically in each move, I would just store all the game states in an array, and when something needs to be undone, I can just call dropLast on the array.
• Since a move in my game is represented as a Direction enum, I will return a (Int, Direction) tuple instead if an int array like the Java code.
• game is a computed property that just returns gameStates.last!
• game.currentPlayer will change every time I call one of the moveUp/Down/Left/Right methods on game, so I don't need to write extra code to decide who's the next player.
• In the last line, I need to return (bestScore, bestDirection), but I realised sometimes bestDirection is not assigned. Therefore, I made bestDirection an optional. If it is not assigned at the return statement, I'll just return an arbitrary direction.

And here is my attempt:

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

When I test out this AI with a depth of 4, it seems to either do stupid moves, like moving his pieces off the board, or move his pieces in one direction only.

I also noticed that gameStates has a length of about 90 when the recursive call returns. Normally it should be 1 right? Because all the moves the AI tried should have been undone by the time the recursive call returns, and gameStates will only contain the initial state.

What did I do wrong?

Answer 1

dropLast() returns an array slice containing all but the last element of the array. It does not modify the original array. Use removeLast()

Edit

What you really want is a stack data structure. Here's one.

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