TicTacToe - should the winner be part of the model?

[maticzav]

I’ve been trying to write a Tic Tac Toe game, and I couldn’t get my head around how to write a data model which would serve me best. Briefly, Tic Tac Toe consists of nine tiles grouped into three rows of three tiles. Two players interchangeably place crosses and circles on the board until either they’ve filled the board, or one of the players managed to put three symbols of the same type in a line. Henceforth it seems reasonable to deduce that

1. the model should include nine tiles and the active player,
2. and that we should somehow calculate whether the game is still in progress or has ended with a tie or one of the players has won.

What about the winner?

I have seen a few examples of Tic Tac Toe which featured game state as a part of the model. I feel like featuring the “state” of the game in the model contradicts with the idea of making impossible states impossible since we could have a board which isn’t full yet and the “state” indicating that the game has ended with a tie (i.e. the board is full).

Moreover, it doesn’t make much sense to have a “state” of the state.

On the other hand, having a state of the game as part of the model could significantly improve performance. Or at least, it feels like it should enhance it since we wouldn’t be calculating the winner over and over again.

Back to the model!

Regardless of the winner, the current state of the model seems very vague. More specifically, how would you structure the board (i.e. the nine tiles)? We know that we need to show three rows of three columns, we also know that there need be a way to identify the tile on click, and we also want to make sure we don’t have to turn the model upside down to calculate the winner.

Approach #1

The first approach is more of an illustrative idea since (I would guess) people coming from JS-ish communities could imagine the state of the game as [[1, 2, 3], [4, 5, 6], [7, 8, 9]] which leads to the following model.

type alias Board = List (List Tile)
type Tile = Tile ID (Maybe Symbol)

pickTile : ID -> Board -> Board
pickTile id board =
   List.map (List.map selectTheTileIfIdsMatch) board

Pros: “intuitively” seems like the right approach,
Cons: logic in the model (i.e. the structure of the view), hard to write the update function since we have to map over a list of lists, we could have two tiles with the same id or more than nine tiles and the compiler wouldn’t complain.

Approach #2

Considering that we don’t want to have a list of lists and also want to make impossible impossible, we could try with the 9-tuple.

type alias Board = (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
type Tile = Tile ID (Maybe Symbol)

pickTile : ID -> Board -> Board
pickTile id board =
   case id of
      0 -> select
      1 -> select
      2 -> select
      ...
      8 -> select

Which simply seems weird.

Approach #3

Have a list of tiles.

type alias Board = List Tile
type Tile = Tile ID (Maybe Symbol)

pickTile : ID -> Board -> Board
pickTile id board =
   List.map selectTheTileIfIdsMatch board

Pros: it’s cleaner than the first one, no logic in the model, a simple update function
Cons: we could have two tiles with the same id or more than nine tiles, and the compiler wouldn’t complain.

To determine the winner: have a list of winning combinations (List (List ID)) and check whether either of the two players satisfies any of them.

The third approach seems very reasonable, yet, we need to find the tiles when performing the winner calculation which seems very cumbersome, especially considering that we shaped the model to help us prevent situations like that and be deterministic of itself.

---

My primary goal of this post was to see how I could structure the game to write the model with the least edge cases (i.e. as few Maybes in the logic as possible) and make the compiler as useful as it can be. How would you structure the model of Tic Tac Toe to achieve that?

[Y0hy0h]

Another approach to the model is to store columns. First of all, the model does not need to be how the user thinks about it. In this case, typically you view the game as a grid. But you’re storing empty cells, which you logically do not care about. Also, the user can only put stones into columnes, not cells, therefore a column-based model seems to make sense.

Now you could limit each column’s height by writing out Column (Maybe Player) (Maybe Player).... But you could also make a module out of Column, initialize a Column with a certain height, and have the module ensure that you cannot add more stones when the Column is full.

Then you could build your board out of multiple columns of the same height. Each column would need accessors for the tiles. Then you are kind of back to the grid model you had before, where you have access to each cell.

Maybe there are clever ways for checking who won. I don’t know them. But I agree, that this seemingly easy tic-tac-toe example shows that some things cannot practically be expressed in types. The winning state fully depends on the game’s board, and therefore should not be redundant. But there is value in caching the winning state, notably in performance. I would, again, encapsulate that responsibility in a module, e. g. TicTacToe. It exposes a model of the form Model = Playing Board | Won Board Player. Every time you want to insert a stone, you call a function, and TicTacToe checks if that leads to a winning state. This way you can guarantee to all users of TicTacToe that the Won Board Player never has an invalid Board, since TicTacToe will ensure that.

My conclusion would be: I agree, this isn’t as straightforward as one initially thinks. But encapsulation into a module is the key to handling the guarantees you’re after.

[Viir]

I tried to come up with a model based on your description of the game. Here is my first idea of how to model this game:

The game state would be modeled as a sequence of placements. This is a list of the coordinates where placements happened.
Since the players take alternating turns, the owning player is implicated by the index of the placement. In other words, we know that placements with an even index were made by player FirstPlayer and uneven ones by player SecondPlayer.
So the Elm code for the game state could look like this:

type alias TileLocation = { x: Int, y: Int }
type alias GameState = { placements : List TileLocation }

@maticzav

the model should include nine tiles and the active player,

To get the active player we have this function:

activePlayer : GameState -> Player
activePlayer gameState = if gameState.placements |> modBy 2 == 0 then FirstPlayer else SecondPlayer

The nine tiles can be modeled with this function:

allTilesLocations : List TileLocation
allTilesLocations = List.range 0 2 |> List.concatMap (\x -> List.range 0 2 |> List.map (\y -> (x, y))

@maticzav

and that we should somehow calculate whether the game is still in progress or has ended with a tie or one of the players has won.

Can be done like this:

isGameInProgress : GameState -> Bool
isGameInProgress gameState = (winningPlayer gameState) == Nothing && 0 < (freeTilesLocations gameState) |> List.length

type Player = FirstPlayer | SecondPlayer

winningPlayer : GameState -> Maybe Player

-- Shared functions
freeTilesLocations : GameState -> List TileLocation
freeTilesLocations gameState = allTilesLocations |> listRemoveSet gameState.placements

-- Common helper functions not specific to TicTacToe

listRemoveSet : List a -> List a -> List a
listRemoveSet elementsToRemove =
    List.filter (\element -> elementsToRemove |> List.member element |> not)

Intuitively, I would model the filtering of inputs in the update function. When an attempt is made to add a placement for a tile location, the update function decides whether this is allowed based on the current game state.
It checks if isGameInProgress and if the tile location is contained in freeTilesLocations. If both conditions are true, we can accept the new placement.

[Y0hy0h]

I just realized that I mixed up connect four with tic tac toe.

Well, apparently you still managed to make sense out of my answer… Sorry for the confusion.

[perty]

This was a fun kata! I opted for using Array as I never used it before.

type alias Model =
    { board : Board
    , currentPlayer : Player
    }


type Player
    = Blank
    | X
    | O


type alias Board =
    { rows : Array (Array Player)
    }


initBoard : Board
initBoard =
    { rows = Array.repeat 3 (Array.repeat 3 Blank)
    }

However, an Array of Arrays is not straightforward to update:

updateBoard : Board -> Int -> Int -> Player -> Board
updateBoard board x y p =
    let
        newRow =
            case Array.get y board.rows of
                Just aRow ->
                    Array.set x p aRow

                Nothing ->
                    Array.repeat 3 Blank
    in
    { board | rows = Array.set y newRow board.rows }

Sorry for being OT but I just got feeling.

The Ellie: https://ellie-app.com/5pMrgshVx36a1