# Tic-tac-toe in FP Scala Source: https://pixabay.com/photos/tic-tac-toe-love-heart-play-1777859/

It tends to be hard to understand functional concepts without a context. And what’s a better setting than a simple game of TicTacToe. A quick reminder: TicTacToe is a game where you have a board of 9 squares, and you and your opponent are trying to fill the board with X’s or O’s in specific configurations. You can learn more about the rules and strategies on Wikipedia https://en.wikipedia.org/wiki/Tic-tac-toe.

# Game Algebra

Let’s start by defining our basic building block of the game as ADT:

`sealed trait Squareobject X extends Squareobject O extends Square`

If we imagine the board at the beginning of the game, it can also be empty, so we need a notion of an empty Square. We can represent it with `Option[Square]` . Where `Some[Square]` is a Square with a set value and `None: Option[Square]` is a square with an empty value. A Row would look like this:

`case class Row(col1: Option[Square], col2: Option[Square], col3: Option[Square])`

As mentioned before our Game has nine squares, so 3 x 3 squares. So the game might look like:

`case class Game(row1: Row, row2: Row, row3: Row)`

The only thing missing for game-related logic is to define a way to talk about a Square position on the game board. So let’s define the concept of Coordinates.

`sealed trait ColumnCoordinatecase object Col1 extends ColumnCoordinatecase object Col2 extends ColumnCoordinatecase object Col3 extends ColumnCoordinatesealed trait RowCoordinatecase object Row1 extends RowCoordinatecase object Row2 extends RowCoordinatecase object Row3 extends RowCoordinatecase class Coordinate(column: ColumnCoordinate, row: RowCoordinate)`

Because we will use either X or O, our decision also needs to have information about the Square. We can define a Move in the game as:

`case class Move(square: Square, coordinates: Coordinate)`

# Game mechanics

So now we have all of our building blocks, and we can start working on game mechanics. One of the first things we can start working on is the ability to progress in the game. Let’s describe our move function by taking into account that we want only to fill non-empty squares:

`def move(game: Game, move: Move): Option[Game] = {  import game._  move.coordinates match {    case Coordinate(Col1, Row1) if row1.col1.isEmpty => Some(copy(row1 = row1.copy(col1 = Some(move.square))))    case Coordinate(Col2, Row1) if row1.col2.isEmpty => Some(copy(row1 = row1.copy(col2 = Some(move.square))))    case Coordinate(Col3, Row1) if row1.col3.isEmpty => Some(copy(row1 = row1.copy(col3 = Some(move.square))))case Coordinate(Col1, Row2) if row2.col1.isEmpty => Some(copy(row2 = row2.copy(col1 = Some(move.square))))    case Coordinate(Col2, Row2) if row2.col2.isEmpty => Some(copy(row2 = row2.copy(col2 = Some(move.square))))    case Coordinate(Col3, Row2) if row2.col3.isEmpty => Some(copy(row2 = row2.copy(col3 = Some(move.square))))case Coordinate(Col1, Row3) if row3.col1.isEmpty => Some(copy(row3 = row3.copy(col1 = Some(move.square))))    case Coordinate(Col2, Row3) if row3.col2.isEmpty => Some(copy(row3 = row3.copy(col2 = Some(move.square))))    case Coordinate(Col3, Row3) if row3.col3.isEmpty => Some(copy(row3 = row3.copy(col3 = Some(move.square))))case _ => None  }}`

Now let’s start thinking about how can we complete the game. There are two basic ways. Either someone wins, or there is a draw when the board is full. Let’s start from draw case because it only requires us to know if we can make any more moves. To figure that out, we need to know if each Row in the Game is full.

`def full(row: Row): Boolean = Seq(row.col1, row.col2, row.col3).forall(_.isDefined)def full(game: Game): Boolean = Seq(game.row1, game.row2, game.row3).forall(Row.full)`

The winning case is a bit more involved. It requires us to test if either one of the rows/columns/diagonals I filled with the same symbol:

`def winner(game: Game): Option[Square] = {  import game._def winnerRow(row: Row): Option[Square] = row match {    case Row(Some(X), Some(X), Some(X)) => Some(X)    case Row(Some(O), Some(O), Some(O)) => Some(O)    case _ => None  } def winnerColumn(colNr: Int): Option[Square] = if(colNr > 0 && colNr < 4) {    winnerRow(colNr match {      case 1 => Row(row1.col1, row2.col1, row3.col1)      case 2 => Row(row1.col2, row2.col2, row3.col2)      case 3 => Row(row1.col3, row2.col3, row3.col3)    })  } else {    None  }lazy val diagonalWinner = (row1, row2, row3) match {  case (Row(Some(X), _, _),         Row(_, Some(X), _),         Row(_, _, Some(X))) => Some(X)  case (Row(Some(O), _, _),         Row(_, Some(O), _),         Row(_, _, Some(O))) => Some(O)case (Row(_, _, Some(X)),         Row(_, Some(X), _),         Row(Some(X), _, _)) => Some(X)  case (Row(_, _, Some(O)),         Row(_, Some(O), _),         Row(Some(O), _, _)) => Some(O)  case _ => None}winnerRow(row1) <+>    winnerRow(row2) <+>    winnerRow(row3) <+>    winnerColumn(1) <+>    winnerColumn(2) <+>    winnerColumn(3) <+>    diagonalWinner}`

The last few bits of mechanics we need is a way to have an empty game ready quickly, and a list of all the possibles moves:

`val empty = Game(  Row(None, None, None),  Row(None, None, None),  Row(None, None, None))val combinations: List[Coordinate] = for {  column <- List(Col1, Col2, Col3)  row <- List(Row1, Row2, Row3)} yield Coordinate(column, row)`

# Displaying the game

To be able to interact with the Console, we need a way to encode our game into a String. Let’s use `TypeClasses` for that:

`trait Encoder[T] {  def encode(value: T): String}object Encoder {  def apply[T](implicit ev: Encoder[T]): Encoder[T] = evimplicit class EncoderClass[T: Encoder](value: T) {    def encode: String = Encoder[T].encode(value)  }}val empty = '.'val x = 'X'val o = 'O'def toSymbol(value: Square): Char = value match {  case X => x  case O => o}implicit val squareEncoder: Encoder[Square] = (value: Square) => toSymbol(value).toStringimplicit val squareOptEncoder: Encoder[Option[Square]] = (t: Option[Square]) => t.map(_.encode).getOrElse(empty.toString)implicit val rowEncoder: Encoder[Row] = (t: Row) => Seq(t.col1, t.col2, t.col3).map(_.encode).mkString(" ")// and for the game movesimplicit val columnCoordinatesEncoder: Encoder[ColumnCoordinate] = {  case Col1 => "A"  case Col2 => "B"  case Col3 => "C"}implicit val rowCoordinatesEncoder: Encoder[RowCoordinate] = {  case Row1 => "1"  case Row2 => "2"  case Row3 => "3"}implicit val coordinatesEncoder: Encoder[Coordinate] = (t: Coordinate) => t.column.encode + t.row.encode`

We also need a decoder to read inputs from the Console. They might fail, so the result needs to be an Option type:

`trait Decoder[T] {  def decode(value: String): Option[T]}object Decoder {  def apply[T](implicit ev: Decoder[T]): Decoder[T] = evimplicit class DecoderClass[T: Decoder](value: String) {    def decode: Option[T] = Decoder[T].decode(value)  }}implicit val squareDecoder: Decoder[Square] = (value: String) => value.headOption.flatMap {  case Square.x => Some(X)  case Square.o => Some(O)  case _ => None}implicit val coordinatesDecoder: Decoder[Coordinate] = (value: String) => if (value.length == 2) {  Applicative[Option].map2(    Decoder[ColumnCoordinate].decode(value.charAt(0).toString),    Decoder[RowCoordinate].decode(value.charAt(1).toString)  )(Coordinate)} else {  None}`

The last, but not least thing is we want to display our game in a way that would let the user decide what move to make.

`def displayGameOnConsole(game: Game): String = {  def encodeRow(row: Row, coordinate: RowCoordinate) = s"\${coordinate.encode} \${row.encode}"Seq(    "  " + Seq[ColumnCoordinate](Col1, Col2, Col3).map(_.encode).mkString(" "),    encodeRow(game.row1, Row1),    encodeRow(game.row2, Row2),    encodeRow(game.row3, Row3)  ).mkString("\n")// this make it look like://  A B C//1 X . O//2 . X O//3 . . X`

# Interacting with the world

The last bit for us to interact with the world is to define constraints on how we talk to the Console:

`trait Console[F[_]] {  def readLine: F[String]def printLine(text: String): F[Unit]}`

Also, let’s keep all the text not related to game mechanics in one place:

`object Text {  val invalidChoice = "Invalid choice, try again"  val draw = "It was a draw"  def winner(square: Square) = s"\${square.encode} won"  def nextMove(square: Square) = s"Your next move with \${square.encode}:"  def chooseText(square: Square) = s"Choose initial symbol: \${square.encode} or \${Square.opposite(square).encode}"val validInputs: String = coordinates.combinations.map(_.encode).mkString(" ")}`

And finally, the game interaction with the Console:

`def run[F[_]: Monad](implicit console: Console[F], applicative: Applicative[F]): F[ExitCode] = {  import console._, applicative._// we retry if user input was invalid  def retry[T](readValue: F[Option[T]]): F[T] = readValue.flatMap { element =>    if(element.isDefined) pure(element.get) else printLine(Text.invalidChoice) *> retry(readValue)  }// we show current state of the game and take user input  def readGame(square: Square, currentGame: Game): F[Game] = for {    _ <- printLine(displayGameOnConsole(currentGame))    _ <- printLine(Text.nextMove(square))    _ <- printLine(Text.validInputs)    nextStage <- retry(readLine.map(Decoder[Coordinate].decode).map(_.flatMap(coordinates => game.move(currentGame, Move(square, coordinates)))))  } yield nextStage// we loop the game until someone wins or there is a draw  def gameLoop(square: Square, gameState: Game): F[Option[Square]] = readGame(square, gameState).flatMap{ currentGame =>    if(game.full(currentGame))      pure(None: Option[Square])    else {      val winner = game.winner(currentGame)      if(winner.isDefined)        pure(winner)      else        gameLoop(Square.opposite(square), currentGame)    }  }for {    _ <- printLine(Text.chooseText(X)) // choose symbol    square <- retry(readLine.map(Decoder[Square].decode))    result <- gameLoop(square, game.empty)    _ <- printLine(result.map(Text.winner).getOrElse(Text.draw))  } yield ExitCode.Success}`

To run the game, we can provide it with an interpreter and Main method:

`object Main extends IOApp {implicit val ioInstance: Console[IO] = new Console[IO] {    import scala.io.StdInoverride def readLine: IO[String] = IO(StdIn.readLine)    override def printLine(text: String): IO[Unit] = IO(println(text))  }override def run(args: List[String]): IO[ExitCode] = {    TicTacToe.run[IO]  }}`

# Conclusion

When learning any programming concept, it’s common to look for simple problems to solve that would gradually increase in complexity. You might try Project Euler, HackerRank, Codility or Exercism. If you reach a plateau, try building some simple games you love like Chess, TicTacToe, Hangman.

# Resources

## Wix Engineering

Architecture, scaling, mobile and web development…

## Wix Engineering

Architecture, scaling, mobile and web development, management and more, this publication aggregates blog posts written by our very own Wix engineers. Visit our official blog here: https://www.wix.engineering/

Written by

## Algimantas Krasauskas

Engineer that strives for excellence and growth. Currently working at @Wix and loving it! ## Wix Engineering

Architecture, scaling, mobile and web development, management and more, this publication aggregates blog posts written by our very own Wix engineers. Visit our official blog here: https://www.wix.engineering/

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium