Tic Tac Toe: Implementing Artificial Intelligence

There are a few ways to implement turn based games as apps. You can either set up networking to play against a live opponent or you can set up an artificial intelligence to play against.

I am working under the assumption that no one is ever going to be super eager to play against a live opponent in tic tac toe, so the best option for a minimum viable product is to implement an AI. Setting up a network for live gameplay is a goal I have for my next project, but it’s overkill for this prototype project.

I want to make the AI good enough as opposed to perfect. It’s no fun playing tic tac toe where you can’t ever win. But it is also important that the AI behave somewhat logically, as opposed to these people.

GamplayKit AI

In 2015, Apple introduced a framework called Gameplay Kit. This framework took a bunch of commonly used concepts in game development and abstracted them out into a framework that could be used universally across the SDK instead of marooning it in either SpriteKit or SceneKit. The randomization algorithms are incredibly popular for applications outside of games.

One of their modules within Gameplay Kit is a set of strategists for opponent AI. The two strategists allow for both deterministic and probabilistic opponent gameplay to be added easily to a game.

I am opting not to use Apple’s built in AI implementation. I have two specific reasons for doing so:

  • I would have to refactor my application: Gameplay Kit was specifically designed around strong object oriented programming principles. In order to utilize any of Apple’s strategists, you have to have an object representing the game model, the player, and the game update. Right now, I am handling all of these things with stand alone functions and enums. In order to take advantage of Apple’s framework I would need to add a bunch of classes and code to my project and it is my personal preference to not do this.
  • I want to understand the math: I am interested in having an understanding of the math behind various strategists. In the next game I want to implement, I would like to be able to roll custom AIs based on various criteria to give virtual players their own personality. Even if that goal is unrealistic or could be accomplished using one of Apple’s built in classes, I want to gain the understanding of how this works by building it on my own.

The remainder of this post will be explaining the strategist algorithm I want to implement and how I was able to integrate it into my existing gameplay.

MiniMax Algorithm

One of the foundational algorithms in AI is the Minimax algorithm. This isn’t a “true” AI as it’s simply a decision tree generated algorithmically. This algorithm was the original AI strategist available when GameplayKit was introduced. It’s still the basis for most AI for games with “perfect” knowledge. Perfect knowledge means that everyone involved in the game knows everything about it. Poker does not involve perfect knowledge because each player only knows the cards they have in their own hands and there is an element of randomness associated with how the cards are dealt. Chess, checkers, and tic tac toe have perfect knowledge because all the pieces and moves can be seen and known by each player.

I based my implementation of the Minimax algorithm from the chapter on adversarial search in Artificial Intelligence: A Modern Approach, Second Edition.

The normal MiniMax decision tree is exhaustive, generating every possible outcome of any given game. This becomes overly complex for even a simple game like tic tac toe. Apple gets around this by allowing you to set a depth for the tree based on number of moves it has to plan ahead. The more moves you plan ahead, the better your AI will be, but each level grows the time exponentially.

This shows MiniMax in a pared down state to give the general idea of how it is implemented.

In order to implement an AI for a board game, you need the following pieces of information:

  • The current state of the board
  • A dictionary of legal moves along with their resulting board state
  • A test to determine if the game has ended (reached terminal state)
  • A payoff function that assigns values to terminal states. In a zero sum game like checkers the states would be +1 for a win, -1 for a loss, and 0 for a draw.

I am already tracking the board state for the UI and game logic and I already have a function checking for a win or a loss. I can reuse these but I still need to add a dictionary of legal moves/state and how to calculate those values.

Modifying the Algorithm in Swift

One of the main features of the MinMax strategist is that it builds decision trees multiple moves ahead. This is great and useful for games like chess where there are a vast multitude of contingencies that the players must keep track of. However, tic tac toe has a maximum of nine moves total. If you’re playing the game properly then no one can ever win. I want to create an AI that plays properly most of the time but doesn’t always play perfectly strategically.

When I play tic tac toe, I go through three levels of processing:

  1. Can I win on this move?
  2. Could my opponent win on this move?
  3. Outside of those outcomes, what is the best strategic move I can make?

My optimal move is to win the game on this move. If that is not possible, then my next best move is preventing my opponent from winning on this turn. After these possibilities are exhausted, there are some moderately strategic moves you can make. If you’re going first, it makes the most sense to squat on the center square. If you’re not going first, then choosing a corner tends to give you more options and opportunities.

I don’t really want my AI to be as sophisticated as a human player because it would be nice to win every once and a while. While creating my decision tree, I wanted to preserve the first two questions as the game would be idiotic if I didn’t. If you can neither win nor lose on this turn, then I wanted to add an element of randomness where the AI simply chooses an empty square. This introduces enough of an opening for the AI to play badly enough that the human player may be able to win every once in a while.

Integrating the Algorithm Into the Project

First up, I want to figure out whether a particular move is a good move or not. If a move results in me winning, that’s awesome and I want that to have a positive value. If a move results in my opponent winning, that’s kind of a bummer and I want to assign that a negative value. If the move doesn’t really impact things one way or another, then I don’t really care and it has a neutral value.

func moveState(currentPlayer: GameState, 
                currentBoard: [TileState], 
			move: Int) -> Int {
    var moveValue = 0
	
    let newState = makeMove(tile: move, 
                   currentPlayer: currentPlayer, 
                           board: currentBoard)

    guard let isWin = checkForWin(currentPlayer: currentPlayer, 
                                          board: newState) else {
        return moveValue
    }
	
    switch isWin {
    case .playerAWin:
	moveValue = -1
    case .playerBWin:
	moveValue = 1
    case .draw:
	moveValue = 0
    }
	
    return moveValue
}

The return value of this function will act as the value for our state dictionary. We’re going to create that next.

We now need our key to go with its value. The key is going to be the index of the move we are making. This allows us to keep track of which tile we are actually changing. We also need to make sure we are only checking valid moves. Finally we need to return a dictionary of valid moves and their correlating values:

func possibleMoveValues(currentPlayer: GameState, 
                         currentBoard: [TileState]) -> [Int:Int] {
    var moveValueTable = [Int:Int]()
	
    for (index, tile) in currentBoard.enumerated() {
	if tile == .notSelected {
	    let moveValue = moveState(currentPlayer: currentPlayer, 
                                       currentBoard: currentBoard, 
                                               move: tile.hashValue)
	    moveValueTable[index] = moveValue
	}
    }
	
    return moveValueTable
}

Finally, we need a way to make an AI move. We can utilize the function we already created for the player making a move. But in this case, instead of checking for a touch from the UI, we are generating it using the previous methods:

func makeAIMove(currentPlayer: GameState, board: [TileState]) -> ([TileState], Int) {
    var newBoard = board
    var move:Int
	
    let possibleImmediateWinValues = possibleMoveValues(
        currentPlayer: .playerB,
        currentBoard: board)

    let possibleImmediateLossValues = possibleMoveValues(
        currentPlayer: .playerA,
        currentBoard: board)
	
    if let immediateWin = possibleImmediateWinValues.
        filter({$1 == 1}).first {
	move = immediateWin.key
    } else if let immediateLoss = possibleImmediateLossValues.
        filter({$1 == -1}).first {
	move = immediateLoss.key
    } else {
	let possibleMoves = Array(possibleImmediateWinValues.keys)
	move = possibleMoves[Int(
               arc4random_uniform(UInt32(possibleMoves.count)))]
    }
	
    newBoard = makeMove(tile: move, 
               currentPlayer: currentPlayer, 
                       board: board)

    return (newBoard, move)
}

First I am creating a new board and a move value for our return tuple. We will be populating those later in the function.

Next, I am running the possibleMoveValues method twice, once for each player. The way I structured the possibleMoveValues method was to check for a specific player’s move. Based on how I structured checkForWin, it only checks against the current player, which is passed in as a parameter. This means that by passing in Player A as a parameter, you will only check for wins for Player A. To get the wins for Player B, you need to run the method again to check for those results. I know, this is complicated and I probably could have written this differently, but that had its own complexity. Every method has tradeoffs.

Next we need to check for wins and losses. We have a preference for a win for Player B, so we check the dictionary for any values that equal 1. Once we find one, we don’t care if there are any more because a win is a win. If a win value is found, we set our move to that.

If there are no wins possible, we check for the next best thing, which is preventing our opponent from winning. We check for a move that our opponent could make to win and if one is found, we make that move to block them from winning. Again, we don’t care if there is more than one winning move for our opponent because if there is, we can’t prevent it anyway.

If nothing we do immediately results in a win or a loss, we simply choose a random square as our move. This allows just enough wiggle room that it’s possible that the AI may choose a really poor strategic value.

So we have a new board and the index of the tile that needs to be changed. This needs to be updated in the UI.

Updating and Modifying the UI

Right now, we are assuming that both players are humans and are swapping the phone back and forth. We update the UI as follows:

if board[tiles.index(of: node)!] == .notSelected {
    switch currentPlayer {
    case .playerA:
	let playerTile = SKSpriteNode(imageNamed: "pastry_donut_320")
	playerTile.setScale(0)
	playerTile.position = spritePosition
	node.addChild(playerTile)
	playerTile.run(actionGroup)
	board[tiles.index(of: node)!] = .playerA
    case .playerB:
	let playerTile = SKSpriteNode(imageNamed: "pastry_starcookie02_320")
	playerTile.setScale(0)
	playerTile.position = spritePosition
	node.addChild(playerTile)
	playerTile.run(actionGroup)
	board[tiles.index(of: node)!] = .playerB
    case .notPlaying:
	node.color = UIColor.white
	board[tiles.index(of: node)!] = .notSelected
    }
}

Basically we have a Player object that tracks the current player. This is used to determine what cookie goes on a tile and who is winning. We don’t want to keep this switch statement any more because we want a move to happen automatically after the player is able to successfully complete a valid move. This requires us to disable user interaction until after the AI has completed its move and to replicate the animation on the tile chosen by the AI.

I updated this section of the code to look like this:

if board[tiles.index(of: node)!] == .notSelected {
    isUserInteractionEnabled = false
			
    // Human player's turn
    let playerTile = SKSpriteNode(imageNamed: "pastry_donut_320")
    playerTile.setScale(0)
    playerTile.position = spritePosition
    node.addChild(playerTile)
    playerTile.run(actionGroup)
    board[tiles.index(of: node)!] = .playerA

This part concerning the human player’s turn is mostly untouched. I simply pulled it out of the switch statement and put it directly in the block. It is being run if the player touches a tile that isn’t already selected. Next, I need to check if the player has won:

// Check for Human Player Win
if let isWin = checkForWin(currentPlayer: currentPlayer, board: board) {
    label.text = isWin.rawValue
    return
} else {
    currentPlayer = switchPlayer(currentPlayer: currentPlayer)
    label.text = "\(currentPlayer.rawValue)'s Turn"
}

If the player has won, we don’t want the AI to make a move. If the player has not won, we still want the UI to update to reflect the current player. Next, I had to modify the code used for the player’s move to work for how the AI is functioning:

    // AI's turn
    let aimove = makeAIMove(currentPlayer: currentPlayer, 
                                    board: board)
    board = aimove.board
    let aiTile = SKSpriteNode(imageNamed: "pastry_starcookie02_320")
    aiTile.setScale(0)
    aiTile.position = spritePosition
    tiles[aimove.move].addChild(aiTile)
    aiTile.run(aiActionGroup)
			
    if let isWin = checkForWin(currentPlayer: currentPlayer, 
                                       board: board) {
	label.text = isWin.rawValue
    } else {
	currentPlayer = switchPlayer(currentPlayer: currentPlayer)
	label.text = "\(currentPlayer.rawValue)'s Turn"
	isUserInteractionEnabled = true
    }
}

Instead of getting the chosen node through touch and then updating the game board, we are running a method that selects a move and returns a new board state. We need to set that board state to be the new board state. We also have to use the index of the move to tell the UI which tile to update. I added a new SKAction to wait a second before implementing the animations to make it look like the AI is thinking about the move.

Again, we need to check for an AI win. If the AI wins, we again show in the UI that the game has finished. If the game hasn’t finished, we need to switch the current player back to the human and reenable touch so that they can make their next move.

Conclusions

This blog post took a while to get done. I had a lot of travel and I had a rough couple of weeks recovering from travel. I find getting off of my routine makes it difficult for me to motivate myself to get things done. So that isn’t really part of the code, but it is part of my life. I have to do a lot of things to curate my mental health and when I don’t I am not able to get things done. I am trying to do better at self care so that I can get things done and feel good about it.

I think if I were doing a more complicated game than tic tac toe the Minimax algorithm looking more than a move ahead would work well. I have feelings about the game theory and economics that gave us this theorem, but it works effectively in this game. I have been deeply interested in game AI for a while and I was really excited to get a chance to implement one for this project. I am looking forward to getting more in depth with these algorithms in future projects.

The hardest part for me in dealing with this was changing how I think about how the UI gets updated. It was difficult wrapping my head around how the UI would respond to touch and know what the specific tile was. When I got to the part updating the AI’s tile, I had a similar cognitive issue of figuring out how we are tracking things. It was actually less complicated, but there are so many moving parts that are contained within one another that it can be difficult keeping everything straight in one’s mental map.

With this section completed, I have two more features I want to add to the game before I ship it. I want multiple scene for the app, so you have a main menu screen that you see before you begin playing. One reason I want this main menu scene is for the other feature, which is variations on tic tac toe. I want to add two variations. One will be simple and the other will be slightly more complicated.

When I have completed these features, I intend to submit this as a free app to the App Store. I want to be able to catalog what I needed to do on this blog. I think it’s likely that Apple will not allow this game on the store as it’s not particularly original. They have been cracking down on student projects and highly derivative apps on the store to try and keep the clutter down.

I understand their perspective, but it’s unfortunate because many employers require you to have an app on the store before they will consider hiring you. There is a limit to the complexity of an app you can create on your own in a limited amount of time without a paying job. By removing this as a platform where students can put portfolio projects, they’re hurting people who are just starting out and are not actually trying to gain a massive audience. There is no other distribution network for iOS applications and it’s onerous to expect employers to have Xcode and to build source code to device. I will see if I am able to get through this barrier or not. Until next time!

I bought this to be the featured image at the top, but WordPress cropped it so all you saw were boobs. Gall and brimstone!