A simple game of Tic-Tac-Toe in Julia

Because why not?
Published

July 18, 2021

As I am primarily a python developer, I was suprised by how easy Julia has been to pick up for scripting and day to day data science work. The DataFrames.jl package feels like a love child between pandas and R, and basic langauge features like control flow, etc have felt very natural. Adding the end keyword hasn’t been a difficult transition, but the 1-based indexing has definitely bit me a few times!

Basic scripting and analysis work isn’t software development, and I have been meaning to dive into some of the more foundational aspects that make Julia unique. As such, I decided to write a quick Tic-Tac-Toe implementation in Julia.

The basic setup

The clear cut pythonic implementation of Tic-Tac-Toe would be to use a class. Since a game of Tic-Tac-Toe requires us to record the state of the game after each player moves, a class provides a nice “bundled” way for us to provide encapsulation (bundling data with methods). In theory object-oriented design also can provide modularity via various design patterns. In practice I’ve seen this break down more often than not, with classes often becoming “god objects”. This isn’t always a bad thing. A Pandas DataFrame is a ubuiquitous and highly productive god object, that also has been designed to interface nicely with many other libraries. I’ve also seen OO patterns done really well such as scikit-learn’s various MixIn patterns. Anyways, this isn’t a blog post about OO patterns, so I digress.

Let’s dive into the basic high level overview of my implementation of Tic-Tac-Toe in Julia.

mutable struct TicTacToe
    board::Matrix
    current_move::String
    game_over::Bool
    move_count::Int
    function TicTacToe()
        first_move = rand(["X", "o"])
        println("$first_move's goes first!")
        return new(
            reshape([" " for i in 1:9], 3, 3),
            first_move,
            false,
            1
        )
    end
end

Julia doesn’t have classes. Instead it uses structs to provide composite types bound to a single object. A few interesting observations about the code above:

  • Embarassingly it took me awhile to figure out how constructors work in structs. Essentially, you just define a function of the same name as the struct, and it will instantiate an object with the defaults specified within the new keyword.
  • Note when a struct is defined it creates a new type that Julia recognizes. The interesting thing about this is it allows us to harness the power of multiple dispatch. This is a core difference coming from a langauge like python. In python you often do things like some_object.some_method(), whereas is Julia the pattern is some_method(some_object). The benefit of the Julia way of doing things is that we can have N definitions of some_method that are dispatched depending on the type of the arguments. While this might not seem beneficial at first, it is actually hugely powerful since it frees us from needing to know the internals of objects and enables a ton of code reuse that is hard to replicate in an OO paradigm.
  • The board, current_move, game_over, and move_count fields are all the core components of the game. We need a board to move around on that stores the state of the game, current_move simply keeps track of which player’s turn it is, game_over is a flag for when to terminate the game, and move_count is some data I keep around to make it easier to tell when the game is a draw (more to come on that).

Ok so that’s the data we need to keep track of, but it’s not the actual game flow. Tic-Tac-Toe is potentially the simplest “board game” known to man. Every 4 year old can competently play the game. The game control flow reflects this simplicity:

function play()
    game = TicTacToe()
    while !game.game_over
        println("Enter a move (e.g. '1, 2')")
        user_move = readline()
        x, y = parse_input(user_move)
        move!(game, x, y)
    end
end
play (generic function with 1 method)

The function above is short and sweet. It instantiates a game of Tic-Tac-Toe, and while the game is “not over” it queries for user input, and then mutates the state of the game by making a move. The bulk of the complexity is hidden in the single function move!. Note in Julia the ! at the end of the function is convention that signifies that the function mutates it’s argument rather than returning a copy.

Making moves and checking win criteria

The move! function in turn is also very basic. It implements the following: - If the player move is already taken, warn and return - Otherwise set the selected move on the board - Check if the new move results in a win or a draw - If it does not result in a terminal game state, switch the current player - Print the game board

The real meat of the program lies in checking the terminal state conditions in check_win_or_draw. This part was actually more interesting than I thought it would be. It turns out there are several sufficient criteria for determining whether a player has won the game. One particularly interesting sufficient criteria is the magic squares criteria. A magic square is a square matrix whose elements sum up to a constant along rows, columns, and both the diagonal and antidiagonal. We can actually harness this along with some clever masking to quickly determine if a player has won the game. This saves us from needing to tabulate the occurance of items along each potential “win axis” and instead simplifies the win criteria to a sum assertion.

Another hack I took to determine whether a draw occurred was to simply keep track of the number of move that have taken place. I think a sufficient condition for a draw is that the number of moves made reaches N-1 without a win. Although I didn’t bother to do the combinatorial proof of that hunch it seems to work out in the case of a 3x3 game board.

import LinearAlgebra:diag
import Base:display


function move!(game::TicTacToe, x::Int, y::Int)
    if game.board[x, y] != " " 
        @warn "Move already taken! Select another move."
        return
    end
    
    game.board[x, y] = game.current_move
    check_win_or_draw(game)
    game.move_count += 1
    switch!(game, game.current_move)
    display(game)
end


function check_win_or_draw(game::TicTacToe)
    # A sufficient condition for winning is accumulating a sum of 15
    # along any axis/diagonal of the 3x3 "magic square"
    magic_square = reshape([8, 1, 6, 3, 5, 7, 4, 9, 2], 3, 3)
    # This is the masking procedure
    magic_square[findall(x -> x != game.current_move, game.board)] .= 0
    current_move = game.current_move
    
    magic_square_win_sum = 15
    draw_criteria = prod(size(magic_square)) - 1
    
    # Check row-wise potential wins
    for i in 1:3
        if sum(magic_square[i, :]) == magic_square_win_sum
            game.game_over = true
            println("Game Over! $current_move's wins!")
            return
        end
    end
        
    # Check column-wise potential wins
    for i in 1:3
        if sum(magic_square[:, i]) == magic_square_win_sum
            game.game_over = true
            println("Game Over! $current_move's wins!")
            return
        end
    end
    
    # Check diagonal wins
    if sum(diag(magic_square)) == magic_square_win_sum ||
        sum(diag(reverse(magic_square, dims=1))) == magic_square_win_sum
        game.game_over = true
            println("Game Over! $current_move's wins!")
        return
    end
    
    # Finally check to ensure that the game is not a draw
    if game.move_count == draw_criteria
        println("Game over: draw.")
        game.game_over = true
        return
    end
    
end


function switch!(game::TicTacToe, current_move::String)
    if current_move == "X"
        game.current_move = "o"
    else
       game.current_move = "X" 
    end
end


function parse_input(s::String)
    x, y = [parse(Int, i) for i in split(s, ",")]
    return x, y
end


# Yay multiple dispatch!
function display(game::TicTacToe)
    
    b = reshape(game.board, 9)
    println("""
    -------------
    | $(b[1]) | $(b[4]) | $(b[7]) |
    -------------
    | $(b[2]) | $(b[5]) | $(b[8]) |
    -------------
    | $(b[3]) | $(b[6]) | $(b[9]) |
    -------------
    """)
end
display (generic function with 31 methods)

Ok! So now we should have a fully working instance of Tic-Tac-Toe in Julia. Let’s play a round against ourselves (how exciting).

play()
o's goes first!
Enter a move (e.g. '1, 2')
-------------
| o |   |   |
-------------
|   |   |   |
-------------
|   |   |   |
-------------

Enter a move (e.g. '1, 2')
-------------
| o |   |   |
-------------
|   | X |   |
-------------
|   |   |   |
-------------

Enter a move (e.g. '1, 2')
-------------
| o |   |   |
-------------
|   | X |   |
-------------
|   |   | o |
-------------

Enter a move (e.g. '1, 2')
-------------
| o |   | X |
-------------
|   | X |   |
-------------
|   |   | o |
-------------

Enter a move (e.g. '1, 2')
-------------
| o | o | X |
-------------
|   | X |   |
-------------
|   |   | o |
-------------

Enter a move (e.g. '1, 2')
Game Over! X's wins!
-------------
| o | o | X |
-------------
|   | X |   |
-------------
| X |   | o |
-------------

stdin>  1,1
stdin>  2,2
stdin>  3,3
stdin>  1,3
stdin>  1,2
stdin>  3,1

So there you have it: Tic-Tac-Toe in pure Julia. In no way am I claiming this is the optimal Julia implementation of the game, but hopefully it illustrated some of the core ideas that makes Julia a bit different than more traditional languages like python.