TicTacToe.scala Part II

I was interviewing recently and we discussed ways to improve my TicTacToe code. Here’s version two!

The Code

import scala.annotation.tailrec
import scala.util.{Try, Success, Failure}

sealed trait Player
case object X extends Player {
  override def toString: String = {
    "X"
  }
}
case object O extends Player {
  override def toString: String = {
    "O"
  }
}

sealed trait Status
case class Winner(player: Player) extends Status
case object InProgress extends Status
case object Draw extends Status

case class Tile(loc: Int, owner: Option[Player]) {
  override def toString: String = owner.map(_.toString).getOrElse(s"$loc")
}

val boardWidth = 3
val blankState = (0 until boardWidth * boardWidth).map(loc => new Tile(loc, None))

class Board(state: IndexedSeq[Tile], val currentPlayer: Player, val gameStatus: Status) {
  def move(loc: Int) : Board = {
    val (front, back) = state.splitAt(loc)

    val newBack = if (!back.isEmpty && back.head.owner.isEmpty) {
      val newTile = back.head.copy(owner = Some(currentPlayer))
      newTile +: back.tail
    } else {
      throw new Exception(s"Invalid location $loc")
    }

    val newState = front ++ newBack
    val newStatus = getNewStatus(newState, loc)
    new Board(newState, otherPlayer, newStatus)
  }

  private def otherPlayer : Player = {
    currentPlayer match {
      case X => O
      case O => X
    }
  }

  private def getNewStatus(newState: IndexedSeq[Tile], loc: Int) : Status = {
    // val (x, y) = (v % 3, v / 3)
    // 0,0 | 1,0 | 2,0
    // 0,1 | 1,1 | 2,1
    // 0,2 | 1,2 | 2,2
    val (x, y) = (loc % boardWidth, loc / boardWidth)
    val countUp = (0 until boardWidth)
    val countDown = (boardWidth - 1 to 0 by -1)

    def rowVictory : Boolean = countUp.forall { idx =>
      val owner = newState(idx + boardWidth * y).owner
      owner == Some(currentPlayer)
    }

    def columnVictory : Boolean = countUp.forall { idx =>
      val owner = newState(x + boardWidth * idx).owner
      owner == Some(currentPlayer)
    }

    def diagonalVictory : Boolean = {
      val isDiagonal = x == y || x + y == (boardWidth - 1)

      lazy val upDiagonal = countUp.forall { idx =>
        val owner = newState(idx + boardWidth * idx).owner
        owner == Some(currentPlayer)
      }

      lazy val downDiagonal = countUp.zip(countDown).forall { case (idx, idy) =>
        val owner = newState(idx + boardWidth * idy).owner
        owner == Some(currentPlayer)
      }

      isDiagonal && (upDiagonal || downDiagonal)
    }

    if (rowVictory || columnVictory || diagonalVictory) {
      Winner(currentPlayer)
    } else if (newState.exists(_.owner.isEmpty)) {
      InProgress
    } else {
      Draw
    }
  }

  override def toString : String = {
    state.grouped(boardWidth).map(_.mkString("|")).mkString("\n")
  }
}

@tailrec
def playGame(game: Board) : Unit = {
  game.gameStatus match {
    case Winner(player) => println(s"$player is victorious!\n$game")
    case Draw => println(s"There are no moves left. It's a stupid tie.\n$game")
    case InProgress => {
      println(s"Player ${game.currentPlayer}, your move")
      println(s"$game\n")

      val nextMove = scala.io.StdIn.readInt()

      Try(game.move(nextMove)) match {
        case Success(newBoard) => playGame(newBoard)
        case Failure(ex) => {
          println(s"Error making a move\n$ex\n")
          playGame(game)
        }
      }
    }
  }
}

playGame(new Board(blankState, X, InProgress))

Improvements

A bunch of the improvements were insignificant. The entire diff can be viewed here.

• Parentheses were removed from methods that didn’t take any parameters.
• Default values for method parameters were removed to be clearer to the library user.
• The Owner type was removed since it didn’t add any clarity.
• The board length is now a variable, so you could easily play on an X by X game board.
• All internal methods are now private.

Sealed Traits

I thought I knew about this when I first wrote TicTacToe. If the parent object of a case class is sealed, all match statements need to include every case. If every case isn’t covered, the match will throw a compile error.

We’ll never need an instance of the parent class, so we can make the Player a trait.

sealed trait Player

sealed trait Status

Case Objects

The player types, X and O, don’t need to hold a value, so we should use a case object instead of a case class. Case objects are singletons, so there is only ever one of them created.

case object X extends Player {
  override def toString: String = {
    "X"
  }
}
case object O extends Player {
  override def toString: String = {
    "O"
  }
}

Use an IndexedSeq instead of a List

When writing a library, you want to use the most generic type possible. We use an IndexedSeq instead of a Seq because the Range type inherits from IndexedSeq. For our TicTacToe board, no extra work is done to convert our board to an IndexedSeq.

val blankState = (0 until boardWidth * boardWidth).map(loc => new Tile(loc, None))

class Board(state: IndexedSeq[Tile], val currentPlayer: Player, val gameStatus: Status) {

Since we’re using an IndexedSeq instead of a List, we need to change how we check if a tile is empty or not. The syntax for decomposing a Seq is messy and I always forget it. We can use the isEmpty methods to check that the board space exists and that the board space is empty.

val (front, back) = state.splitAt(loc)

val newBack = if (!back.isEmpty && back.head.owner.isEmpty) {
  val newTile = back.head.copy(owner = Some(currentPlayer))
  newTile +: back.tail
} else {
  throw new Exception(s"Invalid location $loc")
}

Give Better Names to Variables

Rename nextPlayer to currentPlayer. I always confuse next Thursday and this coming Thursday. I don’t know why I thought nextPlayer was less confusing.

Make the Game Status a Part of the Board Type

The old TicTacToe would calculate the game status every time Board.gameState was called. This is the most expensive part of TicTacToe. We definitely want to calculate the new status only once when we create a new state for the board.

val newState = front ++ newBack
val newStatus = getNewStatus(newState, loc)
new Board(newState, otherPlayer, newStatus)

One benefit of checking for victory when the user makes a moves is we only have to check the row, column, and diagonals for that move. We can ignore the entire rest of the board. We can split these checks into three different methods. Compare the new way of checking for a victory to the old way. The logic is simpler and we get to keep our immutable variables!

// Old way
def findWinner(values: List[Owner]) : Status = values match {
  case List() => InProgress()
  case head :: tail => head match {
    case Some(x) => Winner(x)
    case None => findWinner(tail)
  }
}

if (movesLeft == 0) {
  Draw()
} else {
  findWinner(placements.values.toList)
}

// New way
if (rowVictory || columnVictory || diagonalVictory) {
  Winner(currentPlayer)
} else if (newState.exists(_.owner.isEmpty)) {
  InProgress
} else {
  Draw
}

Refactor the Game Loop to be Tail Recursive

The TicTacToe game is recursive. We want it to be tail recursive, so it will reuse the same stack frame instead of indefinitely growing the stack. Our entire game logic is wrapped in a try catch block, but only the game.move method can throw an exception. Instead of using a lowercase try, we can use an uppercase Try, specifically a scala.util.Try. By wrapping our execution in a Try, we can assign it to a variable and use a match statement. Now our Try block has a clear execution path and always calls playGame in the tail position.

val nextMove = scala.io.StdIn.readInt()

Try(game.move(nextMove)) match {
  case Success(newBoard) => playGame(newBoard)
  case Failure(ex) => {
    println(s"Error making a move\n$ex\n")
    playGame(game)
  }
}

Asides

1. Using an IndexedSeq instead of a List doesn't make a lot of sense in our example, but it was something I learned when reviewing my TicTacToe implementation with someone who knows Scala better than me. Seqs have worse syntax for decomposing them into a head and a tail than Lists do.