Chapter 12. Tic Tac Toe

This chapter presents a program implementing the Tic Tac Toe game. You can play it here (TicTacToe.html) using your mouse to select the field where you want to make a move. To start a new game click the “New Game” button. If the game is not over, you can undo your last move (and the computer’s move that followed it) by clicking the “Undo” button.

The code is divided into three modules:

We start our analysis with the TicTacToeModel module defined in the TicTacToeModel.elm file. The module contains several data type declarations.

File TicTacToeModel.elm (fragment):
module TicTacToeModel where


import List exposing ((::), all, drop, filter, head, isEmpty, length, map)
import Maybe exposing (withDefault)


type Player = O | X


type Result = Draw | Winner Player


type alias Field = { col: Int, row: Int }


type alias Move = (Field,Player)


type alias Moves = List Move


type GameState =
      FinishedGame Result Moves
    | NotFinishedGame Player Moves

The Player data type represents the two players. The Result data type represents the result of the game — either a draw or a victory of one of the players. The Field data type is a record containing the coordinates (column and row) of a field. The Move type is a pair of a Field and a Player. The Moves type is a list of Move values. The GameState represents the game state, which can be either a finished game, which has a result and a list of moves that were made, or a not yet finished game, which contains the player which is to make the next move, and a list of moves made so far.

The data types are followed by definitions of several functions. The first one of them takes a player as argument and returns the “other” player.

File TicTacToeModel.elm (fragment):
other : Player -> Player
other player =
    case player of
        X -> O
        O -> X

The moves function extracts the list of moves from the game state.

File TicTacToeModel.elm (fragment):
moves : GameState -> Moves
moves state =
    case state of
        (NotFinishedGame _ moves) -> moves
        (FinishedGame _ moves) -> moves

The initialState function returns the initial game state. We have assumed that the player X always starts.

File TicTacToeModel.elm (fragment):
initialState : GameState
initialState = NotFinishedGame X []

The isFieldEmpty function verifies whether a given field is not yet occupied, given the list of moves made so far.

File TicTacToeModel.elm (fragment):
isFieldEmpty : Moves -> Field -> Bool
isFieldEmpty moves field = all (\move -> not (fst move == field)) moves

The function uses the all function, which takes a predicate function (a function that takes an argument and returns a boolean value) and a list and returns True if the predicate returns True for each individual element of the list. Our predicate verifies whether the field of the given move is the same as the field given as argument to the isFieldEmpty function. Let’s test the function in the REPL.

> import TicTacToeModel exposing (..)
> isFieldEmpty [({col=1,row=1},X),({col=3,row=2},O)] {col=1,row=1}
False : Bool
> isFieldEmpty [({col=1,row=1},X),({col=3,row=2},O)] {col=1,row=2}
True : Bool

The subsequences function is a helper function that works on lists, but is not available in the standard library List module.

File TicTacToeModel.elm (fragment):
subsequences : List a -> List (List a)
subsequences lst =
    case lst of
        []  -> [[]]
        h::t -> let st = subsequences t
                in
                    st ++ map (\x -> h::x) st

It returns all subsequences of a given list.

> subsequences []
[[]] : List (List a)
> subsequences [1]
[[],[1]] : List (List number)
> subsequences [1,2]
[[],[2],[1],[1,2]] : List (List number)
> subsequences [1,2,4]
[[],[4],[2],[2,4],[1],[1,4],[1,2],[1,2,4]] : List (List number)

Notice how the empty list [] and a non-empty list consisting of the head h and tail t are used as patterns in the case expression.

The playerWon function verifies whether the given player won, considering the list of moves made so far.

File TicTacToeModel.elm (fragment):
playerWon : Player -> Moves -> Bool
playerWon player =
    let fieldsAreInLine fields =
            all (\{col} -> col == 1) fields ||
            all (\{col} -> col == 2) fields ||
            all (\{col} -> col == 3) fields ||
            all (\{row} -> row == 1) fields ||
            all (\{row} -> row == 2) fields ||
            all (\{row} -> row == 3) fields ||
            all (\{col,row} -> col == row) fields ||
            all (\{col,row} -> col + row == 4) fields
    in  subsequences
            >> filter (\x -> length x == 3)
            >> filter (all (\(_,p) -> p == player))
            >> map (map fst)
            >> filter fieldsAreInLine
            >> isEmpty
            >> not

The function has one argument (called player), yet the type declaration seems to declare two arguments. That means, that the function takes one argument of type Player and returns another function, of type Moves -> Bool.

The fieldsAreInLine helper function verifies whether the given list of fields has only fields that are on the same line (vertical, horizontal or diagonal).

The function returned by playerWon is composed from several smaller functions using the >>, which composes two functions together. We will analyze the individual functions starting from the first one — subsequences — which returns all subsequences of the list of moves. The next function filters those subsequences, leaving only those that have three elements. The next one filters them even more, leaving only those, which only have the moves of the player equal to the first argument of the playerWon function. The next one turns the list of moves into a list of fields by extracting the first element of each move. The next function filters the list even more using the helper function fieldsAreInLine. Finally, the last two functions verify whether the list which is the result of all the previous filtering is not empty.

> playerWon X []
False : Bool
> playerWon X [({col=1,row=3},X),({col=3,row=3},O),({col=3,row=1},X),({col=1,row=1},O),({col=2,row=2},X)]
True : Bool

The addMove function takes a move and a state and returns a new game state.

File TicTacToeModel.elm (fragment):
addMove : Move -> GameState -> GameState
addMove move state =
    let newMoves = move :: (moves state)
        player = snd move
    in
        if  | playerWon player newMoves -> FinishedGame (Winner player) newMoves
            | length newMoves == 9 -> FinishedGame Draw newMoves
            | otherwise -> NotFinishedGame (other player) newMoves

The function adds the move to the existing state and then verifies whether the new situation corresponds to a finished game, either because one of the players won, or because there is no more place left on the board. In that case a FinishedGame state is returned.

> addMove ({ col = 3, row = 1 },X) (NotFinishedGame X [({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
FinishedGame (Winner X) ([({ col = 3, row = 1 },X),({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState

Otherwise, if the game is not finished, a new NotFinishedGame value is returned.

> addMove ({ col = 3, row = 1 },X) (NotFinishedGame X [({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
NotFinishedGame O ([({ col = 3, row = 1 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState

The makeComputerMove function implements the algorithm used by the computer to choose the next move.

File TicTacToeModel.elm (fragment):
makeComputerMove : GameState -> GameState
makeComputerMove state = case state of
    FinishedGame _ _ -> state
    NotFinishedGame player moves ->
        let fields = [
                {col=2,row=2},
                {col=1,row=1},
                {col=3,row=3},
                {col=1,row=3},
                {col=3,row=1},
                {col=1,row=2},
                {col=2,row=1},
                {col=2,row=3},
                {col=3,row=2}
            ]
            newField = filter (isFieldEmpty moves) fields |> head |> withDefault {col=0,row=0}
            newMoves = (newField, player) :: moves
        in
            addMove (newField, player) state

The algorithm is very simple, and is not the optimal one. An optimal algorithm would not leave a chance for the human player to win. This algorithm however is not optimal for the game, so the player has a change to win with the computer. The computer simply takes moves from a predefined list. The moves that cannot be performed, because the given field is not empty, are discarded, and the first one of the remaining moves is selected.

> makeComputerMove (NotFinishedGame X [])
NotFinishedGame O ([({ col = 2, row = 2 },X)]) : TicTacToeModel.GameState
> makeComputerMove (NotFinishedGame O [({ col = 2, row = 2 },X)])
NotFinishedGame X ([({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState

The makeHumanAndComputerMove function takes a field selected by the player, and the current game state, and returns a new game state.

File TicTacToeModel.elm (fragment):
makeHumanAndComputerMove : Field -> GameState -> GameState
makeHumanAndComputerMove field state =
    case state of
        FinishedGame _ _ -> state
        NotFinishedGame player moves -> 
            if isFieldEmpty moves field
                then addMove (field,player) state |> makeComputerMove
                else state

The function first verifies if the next move is allowed to be made on the provided field. The move is not allowed if the game is already finished, or if the field is not empty.

> makeHumanAndComputerMove { col = 2, row = 1 } (FinishedGame (Winner X) [({ col = 3, row = 1 },X),({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
FinishedGame (Winner X) ([({ col = 3, row = 1 },X),({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState
> makeHumanAndComputerMove { col = 2, row = 2 } (NotFinishedGame O [({ col = 2, row = 2 },X)])
NotFinishedGame O ([({ col = 2, row = 2 },X)]) : TicTacToeModel.GameState

If the move is allowed, the addMove is used for adding the move to the game state, and returning the new state. The new state is then passed to makeComputerMove to make the subsequent move by the computer.

> makeHumanAndComputerMove { col = 2, row = 2 } (NotFinishedGame O [])
NotFinishedGame O ([({ col = 1, row = 1 },X),({ col = 2, row = 2 },O)])
    : TicTacToeModel.GameState

The undoMoves function modifies the state to undo two moves — the last computer move and the user move preceding it.

File TicTacToeModel.elm (fragment):
undoMoves : GameState -> GameState
undoMoves state =
    case state of
        NotFinishedGame _ [] -> state
        NotFinishedGame player moves ->
            NotFinishedGame player (moves |> drop 2)
        FinishedGame _ _ -> state

The moves are only removed if the game is not finished, and only if there are actually moves that can be removed (the list of moves is not empty).

> undoMoves (FinishedGame (Winner X) [({ col = 3, row = 1 },X),({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
FinishedGame (Winner X) ([({ col = 3, row = 1 },X),({ col = 3, row = 3 },O),({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState
> undoMoves initialState
NotFinishedGame X [] : TicTacToeModel.GameState
> undoMoves (NotFinishedGame O [({ col = 1, row = 3 },X),({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
NotFinishedGame O ([({ col = 2, row = 2 },X)]) : TicTacToeModel.GameState

The processClick function modifies the game state in reaction to a mouse click by the user.

File TicTacToeModel.elm (fragment):
processClick : (Int,Int) -> GameState -> GameState
processClick (x,y) =
    let col = 1 + x // 100
        row = 1 + y // 100
    in
        if col >= 1 && col <= 3 && row >= 1 && row <= 3
            then makeHumanAndComputerMove {col=col,row=row}
            else identity

The function uses the standard identity function, which returns its input unchanged.

> identity
<function> : a -> a
> identity 4
4 : number
> identity "abc"
"abc" : String

The coordinates of the click position are translated into the coordinates of one of the board fields. If the click is indeed inside the board, the makeHumanAndComputerMove function is used for returning the state-modifying function. Otherwise the id function is used in order to (not) modify the state.

> processClick (150,150) initialState
NotFinishedGame X ([({ col = 1, row = 1 },O),({ col = 2, row = 2 },X)])
    : TicTacToeModel.GameState
> processClick (1500,150) initialState
NotFinishedGame X [] : TicTacToeModel.GameState

The [TicTacToeView](TicTacToeView.elm) module defines the drawing functions.

File TicTacToeView.elm (fragment):
module TicTacToeView where


import Color exposing (black, white)
import Graphics.Collage exposing (circle, collage, filled, group, move, rect, rotate)
import Graphics.Element exposing (Element, container, down, flow, layers, leftAligned, middle, right, spacer)
import Graphics.Input exposing (button)
import List exposing (map)
import Signal exposing (Mailbox, mailbox, message)
import Text exposing (fromString)
import TicTacToeModel exposing (..)

The drawLines function draws the two vertical and two horizontal lines of the game board.

File TicTacToeView.elm (fragment):
drawLines : Element
drawLines =
    collage 300 300 [
        filled black (rect 3 300) |> move (-50,0),
        filled black (rect 3 300) |> move (50,0),
        filled black (rect 300 3) |> move (0,-50),
        filled black (rect 300 3) |> move (0,50)
    ]

The drawMoves function draws the moves of both players.

File TicTacToeView.elm (fragment):
drawMoves : GameState -> Element
drawMoves state =
    let moveSign player =
            group (case player of
                      X ->
                          let xline = filled black (rect 5 64)
                          in  [ rotate (degrees 45) xline
                              , rotate (degrees 135) xline
                              ]
                      O ->
                          [ filled black <| circle 30
                          , filled white <| circle 25
                          ]
                  )
        playerMove ({col,row}, player) =
            moveSign player |> move (toFloat <| 100*col-200,toFloat <| -100*row+200)
    in
        collage 300 300 (map playerMove <| moves state)

The stateDescription returns the text of the message that the user sees below the board.

File TicTacToeView.elm (fragment):
stateDescription : GameState -> String
stateDescription state =
    case state of
      FinishedGame Draw _ -> "Game Over. Draw"
      FinishedGame (Winner p) _ -> "Game Over. Winner: " ++ toString p
      NotFinishedGame p _ -> "Next move: " ++ toString p

The newGameMailbox function creates a mailbox for sending messages in response to clicking the “New Game” button. The newGameButton creates a clickable button using the button function from the Graphics.Input module.

button : Message -> String -> Element

The Message object is created using the message function, which takes the mailbox as one of its arguments

File TicTacToeView.elm (fragment):
newGameMailbox : Mailbox ()
newGameMailbox = mailbox ()


newGameButton : Element
newGameButton = button (message newGameMailbox.address ()) "New Game"

There are also two similar functions related to the “Undo” button.

File TicTacToeView.elm (fragment):
undoMailbox : Mailbox ()
undoMailbox = mailbox ()


undoButton : Element
undoButton = button (message undoMailbox.address ()) "Undo"

The view function collects the complete view, by drawing the board lines and the player moves on top of each other, and the state description message and the two buttons below.

File TicTacToeView.elm (fragment):
view : GameState -> Element
view state =
    flow down [
        layers [drawLines, drawMoves state],
        container 300 60 middle <| leftAligned <| fromString <| stateDescription state,
        container 300 60 middle <| flow right [undoButton, spacer 20 20, newGameButton]
    ]

The [TicTacToe](TicTacToe.elm) module implements the remainder of the game.

File TicTacToe.elm (fragment):
module TicTacToe where


import Graphics.Element exposing (Element)
import Mouse
import Signal exposing ((<~), Signal, foldp, mergeMany, sampleOn)
import TicTacToeModel exposing (..)
import TicTacToeView exposing (..)

The module creates several signals and combines them together. The following figure presents how the individual signals are combined together to produce the main game signal.

The first three functions create the basic input signals that are then transformed into other signals. The clickSignal function creates a signal which outputs the mouse pointer position on every click. The newGameButtonSignal function returns the signal associated with newGameMailbox. The undoButtonSignal function returns the signal associated with undoMailbox.

File TicTacToe.elm (fragment):
clickSignal : Signal (Int,Int)
clickSignal = sampleOn Mouse.clicks Mouse.position


newGameButtonSignal : Signal ()
newGameButtonSignal = newGameMailbox.signal


undoButtonSignal : Signal ()
undoButtonSignal = undoMailbox.signal

The next three functions transform each of the above signals into a signal of state-transforming functions. Those signals have the type of Signal (GameState -> GameState). The functions carried by the signal events will then be applied to the game state.

The newGameSignal creates a signal of functions that return the initial game state regardless of the current state.

File TicTacToe.elm (fragment):
newGameSignal : Signal (GameState -> GameState)
newGameSignal = always (always initialState) <~ newGameButtonSignal

The always function returns a function that disregards its input and always outputs a certain value.

> always
<function> : a -> b -> a
> f = always 1
<function> : a -> number
> f 2
1 : number
> f 6
1 : number

It is used twice. The outer always disregards the () values of the newGameButtonSignal signal, while the inner always disregards the current state.

The undoSignal function creates a signal of undoMoves functions.

File TicTacToe.elm (fragment):
undoSignal : Signal (GameState -> GameState)
undoSignal = always undoMoves <~ undoButtonSignal

The moveSignal function returns a signal of state-transforming functions created by calling the processClick function with mouse click positions. The processClick function is partially applied here — only its first argument is applied.

File TicTacToe.elm (fragment):
moveSignal : Signal (GameState -> GameState)
moveSignal = processClick <~ clickSignal

The inputSignal function merges the three signals described above into one.

File TicTacToe.elm (fragment):
inputSignal : Signal (GameState -> GameState)
inputSignal = mergeMany [ moveSignal, newGameSignal, undoSignal ]

The gameStateSignal uses the foldp function to modify the game state.

File TicTacToe.elm (fragment):
gameStateSignal : Signal GameState
gameStateSignal = foldp (<|) initialState inputSignal

Recall the foldp signature.

foldp : (a -> b -> b) -> b -> Signal a -> Signal b

In our case the input signal has the Signal (GameState -> GameState) type, thus a is GameState -> GameState. The output signal has the type Signal GameState, and thus b is GameState. We can conclude therefore, that the function that we need to pass as the first argument to foldp needs to have the following signature:

(GameState -> GameState) -> GameState -> GameState

Well, that signature looks like a function application operator (<|) — we can thus use it in the foldp call.

(<|) : (a -> b) -> a -> b

So, the way how the foldp function works in our game is that it receives state-transforming functions as input, and applies each of them to the current state that it maintains and outputs.

The main function simply combines the signal of state values with the view function from the TicTacToeView module.

File TicTacToe.elm (fragment):
main : Signal Element
main = view <~ gameStateSignal

The [next](Chapter13Snake.html) chapter presents another game.

Elm by Example. Copyright © Grzegorz Balcerek 2015.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.