Tic Tac Toe: Creating Multiple Views/Scenes

This game is coming along well as a sample project, but not as a real game. There are things I expect as a player when playing an actual game I bought on the App Store. One of those things is having more than one screen. You usually have a main menu screen, a settings screen, etc…

I don’t want to go overboard on this project, but I do want this to look like a real game. The point of this exercise was to take a simple set of requirements and execute them fully. For me a minimum viable product would have at least a main menu scene. I have other ways I would like to handle a game ending, but I am behind schedule on this project and I don’t want to get stuck polishing it forever when a simpler solution will suffice.

I want my game to have the following scenes:

  • Main Menu
  • Variant Menu
  • Main Game Scene (already created)
  • Game Over Scene

The main menu should be simple. You tap on it and it brings you to the menu where you choose what variation of tic tac toe you want to play. This leads to the main game scene where you play the game. After the game ends one way or another, this leads to a final game over scene announcing how the game ended. After a set period of time, this reloads the main menu.

SpriteKit Scene Editor

When all of this stuff was in an immutable single scene, placing objects programmatically made a modicum of sense. But right now I want to place objects as I would if I were doing a traditional iOS app. I want to create a better UI for menus and asking questions. I don’t generally do my UI in code because it’s difficult to debug. I was trying to figure out how to create buttons and layouts and was starting to freak out. At this point I am bringing in the SpriteKit scene editor.

The scene editor is SpriteKit’s version of storyboards. They provide a WYSIWYG interface for laying out game elements. This makes all kinds of sense. Games are even more visually intensive than normal UIVew based applications. I find storyboards invaluable for laying out my UI elements. Not having something like this would be idiotic.

Game Over

I actually created this one first. I have been working through the 2D games book published by Ray Wenderlich’s company. They created both the main menu and the game over menu programatically. Neither required any user interaction beyond tapping the screen or waiting. I have put myself on a personal deadline of wanting to ship this project before Sunday, May 6th. There are a lot of more custom interactions I would like to add, but I need to see if I have time or not. This is minimum viable product time.

I originally intended to custom create different end scenes based on the winner of the game, but I started to get discombobulated by trying to figure out how to adjust things for different screens. I also realized this was inherently limiting and that I could use animations if I did everything in code.

First I need my properties that are going to be used to determine how this scene looks:

import Foundation
import SpriteKit

class GameOverScene: SKScene {
    let endState:GameEndState 
    let background = SKSpriteNode(imageNamed: "bg_ipad_portrait")
    let label = SKLabelNode(fontNamed: "Noteworthy-Bold")
    var iconNode = SKSpriteNode()

I need the end state to know who won the game or if it was a draw. I need to set the background as I did for all the other scenes in the game. I need a label showing who one. Lastly, I need an icon representing the winner.

I need to initialize these properties:

init(size: CGSize, endState: GameEndState) {
    self.endState = endState
    super.init(size: size)
		
    isUserInteractionEnabled = false
		
    anchorPoint = CGPoint(x: 0.5, y: 0.5)
		
    background.zPosition = -1
    addChild(background)
		
    let labelBackground = SKSpriteNode(
        imageNamed: "headerBacking")
    labelBackground.zPosition = 2
    labelBackground.size = CGSize(
        width: self.size.width, 
        height: 60.0)
    labelBackground.position = CGPoint(
        x: 0.0, 
        y: (self.size.width / 2.0) + 100)
    labelBackground.anchorPoint = CGPoint(x: 0.5, 
                                          y: 0.5)
    addChild(labelBackground)
		
    label.fontColor = SKColor.black
    label.fontSize = 40
    label.zPosition = 10
    label.position = CGPoint(x: 0.0, y: -20.0)
    labelBackground.addChild(label)
}

required init(coder aDecoder: NSCoder) {
    fatalError("init(coder:) has not been implemented")
}

I need to set the winner label and the icon based on what game state is passed in:

override func didMove(to view: SKView) {
		
    switch endState {
	case .playerAWin:
	    iconNode = SKSpriteNode(imageNamed: 
                "pastry_donut_320")
	    label.text = "Player A Wins!"
	case .playerBWin:
	    iconNode = SKSpriteNode(imageNamed: 
                "pastry_starcookie02_320")
	    label.text = "Player B Wins!"
	case .draw:
	    iconNode = SKSpriteNode(imageNamed: 
                "pastry_starcookie02_320")
	    label.text = "Draw"
    }

I already had actions for animating a sprite into the scene that I could reuse for the game ending scene:

    let spritePosition = CGPoint(x: 0.0, y: 0.0)
    let spriteSize = CGSize(width: 320, height: 320)
		
    // Actions
    let fadeAction = SKAction.fadeIn(withDuration: 0.75)
    let scaleUpAction = SKAction.scale(to: 
	CGSize(width: spriteSize.width * 
	1.5, height: spriteSize.height * 1.5), 
	duration: 0.5)
    let scaleDownAction = SKAction.scale(to: spriteSize, 
                                   duration: 0.25)
    let soundEffect = SKAction.playSoundFileNamed(
	"pop.wav", 
	waitForCompletion: false)
    let scaleSequence = SKAction.sequence(
	[scaleUpAction, soundEffect, scaleDownAction])
    let actionGroup = SKAction.group(
        [fadeAction, scaleSequence])
		
    iconNode.setScale(0)
    iconNode.position = spritePosition
    iconNode.zPosition = 10
    addChild(iconNode)
    iconNode.run(actionGroup)
		
    let wait = SKAction.wait(forDuration: 5.0)
    let block = SKAction.run {
	if let scene = SKScene(fileNamed: "MainMenuScene") {
	    let reveal = SKTransition.flipHorizontal(withDuration:0.5)
	    self.view?.presentScene(scene, transition: reveal)
	}
    }
    self.run(SKAction.sequence([wait, block]))
}

This scene basically hangs around long enough to display the current winner. Then, after a sufficient amount of time, it navigates back to the main menu to allow the user to begin a new game.

This was a bit more code that I particularly wanted to have to maintain. One goal on this learning project was to try and get things done faster, so for the future scenes I wanted to try and take advantage of the SceneKit Editor.

Main Menu

I had an idea about how I wanted the main menu laid out, but I didn’t want to have to do this in code. Since I only need the user to tap on the screen, I just wanted to get things generally laid out.

I created a MainMenuScene.sks file along with a MainMenuScene.swift file. All of the graphics and UI stuff will be laid out in the .sks file while all of the user interactions and behaviors live in the .swift file.

I laid out the main menu to look like this:

Scene editor, very much like Interface Builder

For a while I could not get this to load and I couldn’t figure out why. I had forgotten that in IB and the Scene editor you need to connect objects to their correlating class. So be sure to set your scenes/custom nodes/etc… to their correlating class in the Inspector.

The only think I need the main menu to do is listen for a touch. If the player touches the screen, I want it to launch a new game. Here is the code for this:

import Foundation
import SpriteKit

class MainMenuScene: SKScene {
	
    override func didMove(to view: SKView) {

    }
	
    func sceneTapped() {
	let myScene = GameScene(size: size)
	myScene.scaleMode = scaleMode
	let reveal = SKTransition.doorway(withDuration: 1.5)
	view?.presentScene(myScene, transition: reveal)
    }
	
    override func touchesBegan(_ touches: Set,
	with event: UIEvent?) {
	sceneTapped()
    }
	
}

Choose Variation

For my variations scene I want the same background as the rest of the application but I want three buttons. SpriteKit doesn’t have SKButton objects. So far my understanding of how SpriteKit works is that everything is a node. I need three nodes with textures that look like buttons indicating each variation. I need to name them so that I can use touch recognition to see which version the player chose.

The class needs to keep track of which version of tic tac toe the user wants to play. I created a new enum to hold these values:

enum GameVariation {
    case normal
    case reversed
    case swap
}

Right now these are not doing anything. The last feature I want to add to the application is the ability to actually have different rules and functionality for these variations. Right now, this is basically a stubbed out method:

import SpriteKit
import GameplayKit

class TypeChoiceMenu: SKScene {
    override func didMove(to view: SKView) {

    }
	
    // Check for node type and pass into the initializer
    func sceneTapped(_ type: GameVariation) {
	// Update GameScene init for game type
	let myScene = GameScene(size: size, variation: type)
	myScene.scaleMode = scaleMode
	let reveal = SKTransition.doorway(withDuration: 1.5)
	view?.presentScene(myScene, transition: reveal)
    }
	
    override func touchesBegan(_ touches: Set,
	with event: UIEvent?) {
		
        guard let touch = touches.first else {return}
	let location = touch.location(in: self)
	let rawNodes = nodes(at: location)
	let tappedNodes = rawNodes.filter{return $0.name != nil}
		
	guard let node = tappedNodes.first as? SKSpriteNode else {
            return
        }
		
	switch node.name {
	case "RegularButton":
	    sceneTapped(.normal)
	case "ReverseButton":
	    sceneTapped(.reversed)
	case "TileSwap":
	    sceneTapped(.swap)
	default:
	    break
	}
    }
}

As with the code to check which tile is tapped in the main game, this checks the node name of the buttons in the scene. If one is selected, then it triggers a load of the main game scene and passes that choice along to the scene.

Conclusions

This wound up being a bit harder than I expected. After having done a few scenes in the editor, I am wondering why I didn’t do this sooner. However, when I first started this feature I was incredibly frustrated by the editor and wanted to scrap my plans to use it.

Sometimes you need to work through something that seems difficult or counterintuitive in order to find a better way to do things. If I had to do this project over again I would set up the entire game in the scene editor.

The final feature I want to implement before I declare this project ready to ship is a few variations on tic tac toe to make this game slightly more interesting. Playing through this I keep seeing more and more refinements I would like to make to this project, but the point of this was to get something done and to ship it. I don’t want to get sidetracked endlessly refining this learning project rather than moving on to a more complex project.

So far there has been a lot more to this game that I anticipated when I started. But part of the point of this was to work on all the non-obvious stuff. Until next time!

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!