2048 in OCaml: New Game

Introduction

For the past two years, every time I'm learning a new language, I try to re-implement the 2048 game to get a feel for the language. I've done it in Rust, Clojure, and now OCaml! In this post, I'll explain my thought process for the later.

If you're unfamiliar with the game, it's usually composed of a 4×4 board where numbered cells can spawn and slide. You can slide in either cardinal direction, and all cells will move in that direction. Two adjacent cells with the same value that move in the same line will merge together into a new cell with a higher value. After every move, the game generates a new cell in a random empty space. The values are usually powers of two, and the goal is to reach the 10th value, that is, 2¹⁰ = 2048.

Quick OCaml introduction

If you're unfamiliar with OCaml, it's a heavily functional (albeit technically multi-paradigm), statically typed programming language with the best type inference I've ever had the pleasure of working with. Most of the time you don't really need to declare variable types, as the compiler can infer each type from the actual use of the variable. Take, for example, the snippet of code below:

let str = "this is a string!"
let add a b = a + b
let invalid = add str 1 (* compilation error *)

In the code above, the compiler understands that str must be a string, as it's assigned a string value; it also understands that the add function must receive two int variables a and b, because the infix + can only be applied to int values. Because of that, the compiler will throw an error while evaluating the third line of code, complaining that it expected an int but received a string for the first argument of the add function, all without any explicit type annotations at all!

Module type signatures

Now, going back to the 2048 clone and jumping straight into the code, my OCaml implementation starts with a module type signature:

module type Game = sig
    type direction = Up | Down | Left | Right
    type cell = { value : int ; position : int } 
    type t = cell list

    val new_game : unit -> t
    val move : direction -> t -> t
end

In the above code, we're declaring a module type called Game, which has a signature exposing three types: direction, cell, and t, as well as two functions: new_game and move.

• direction is the type that's used to control the game movement action

• cell represents each cell in the game board, and contains a value of type int that starts at 0 and increments by one, as well as a position that's also of type int and represents the cell position in the board

• t^[1] represents the actual game state, which is a list of every cell

• new_game is a function that expects an unit ^[2] value and returns a Game.t structure

• move is a function that expects both a direction and a Game.t structure, and returns a new Game.t with the new game state

Besides the Game module type, we also need a secondary GameParams module type, which will be used to configure the game size and RNG seed:

module type GameParams = sig
    val size : int
    val seed : int option
end

This module type declares two values:

• size, which has type int and controls the game board size so that for a size of n a game board that can fit at most n * n cells will be generated

• seed, which is an int option ^[3] parameter; if it exists, the game will use the value as its RNG seed; if not, the game will self-generate a new random seed

Actual implementation

Now that we have declared the module types, we can finally create our module implementation, which looks something like this:

module Game(Params : GameParams) : Game = struct
    type direction = Up | Down | Left | Right
    type cell = { value : int ; position : int } 
    type t = cell list

    let new_game () = empty_game
    let move _dir game = game
end

The module above receives a GameParams module as a constructor argument, and creates a new module Game with the given params as an internal state. The module re-declares the same types the module type has, and also two functions: new_game and move, that satisfy the module type definitions, but don't actually execute any game logic yet.

Initialise everything!

In order to generate random numbers for the new cells that spawn after every move, we first need to initialise the Random module state. We do that using the seed value of the GameParams module:

let () = 
    Option.map Random.init Params.seed 
    |? Random.self_init ()

The line above initialises the Random module by calling Random.init with the Params.seed value if it exists, otherwise it will call Random.self_init. The |?^[4] Infix operator is explained on this article's footnotes.

We also need to initialise some support values inside our module:

let cell_qty = Params.size * Params.size
let empty_game = []
let all_pos_set = 0 --^ cell_qty |> IntSet.of_enum

I believe cell_qty and empty_game are self-explanatory: the former squares the Params.size value, while the later is just an empty list. all_pos_set, however, is a bit more complicated.

The function all_post_set first creates an Enum ^[5] of all values starting at 0 up to, but not including, cell_qty, and then creates a Set of all those numbers. For example, if Params.size is 4, then cell_qty will be 16, and all_pos_set will be a set of all integers from 0 to 15. If you're curious about the --^ ^[6] and |> ^[7] infix operators, you can check their respective footnotes at the end of this article.

With all of that out of the way, now is the time to actually implement the new_game logic!

Generating a new cell

For us to implement the actual new_game logic, we only need to generate a new random cell with a value of 0 or 1 on any empty space. To do that, first we need to find all empty spaces for a given game state:

let empty_pos game =
    game
    |> List.map (fun { position ; _ } -> position)
    |> List.fold (flip IntSet.remove) all_pos_set
    |> IntSet.to_array

The function above receives a game value of type Game.t, maps every cell to their position, and then removes those positions from the all_pos_set we previously declared. Then the remaining set is converted into an array which we will use later.

Now that we have a function that identifies every possible space where the new cell can be generated, we can finally implement a method that generates a new cell:

let generate_cell game =
    let empty_pos =
        game
        |> List.map (fun { position ; _ } -> position)
        |> List.fold (flip IntSet.remove) all_pos_set
        |> IntSet.to_array in
    if Array.length empty_pos = 0
    then game
    else
    let position =
        empty_pos
        |> Array.length
        |> Random.int
        |> Array.get empty_pos in 
    let value = if Random.int 16 = 0 then 1 else 0 in
    { value ; position }::game

After getting an array with all empty spaces, we check if the array is empty. If it is, we just return the game object as it is, as there's no space for a new cell to be put in. If there is, however, at least one element in the array, we get a random element in the array, then generate a value of 1 or 0, with 0 being way more common, and append the new cell with the chosen value and position onto the game cell list. The :: ^[8] infix operator is also explained in the footnotes.

Now that we have a generate_cell function, we can finish our new_game implementation:

let new_game () = generate_cell empty_game

Calling Game.new_game () will now return a list with a single cell, which should have a random position between 0 and 15, and also a value of 0 or 1:

Game.new_game ()
(* [ { value = 0 ; position = 7 } ] *)

Game.new_game ()
(* [ { value = 0 ; position = 13 } ] *)

Game.new_game ()
(* [ { value = 1 ; position = 3 } ] *)

Final code

The final code for this part looks like this:

open Batteries

module IntSet = Set.Make(Int)

module type Game = sig
    type direction = Up | Down | Left | Right
    type cell = { value : int ; position : int } 
    type t = cell list

    val new_game : unit -> t
    val move : direction -> t -> t
end

module type GameParams = sig
    (** defines the size of the game board *)
    val size : int

    (** defines the seed for the `Random.init` call. 
        if `None`, will call `Random.self_init` instead. *)
    val seed : int option
end

module Game(Params : GameParams) : Game = struct
    type direction = Up | Down | Left | Right
    type cell = { value : int ; position : int } 
    type t = cell list

    (** initialises the Random module according to the
        passed Params *)
    let () = 
        Option.map Random.init Params.seed 
        |? Random.self_init ()

    let cell_qty = Params.size * Params.size

    (** empty game structure, with both 
        value and position lists empty *)
    let empty_game = []

    (** set of all possible positions a cell can have *)
    let all_pos_set = 0 --^ cell_qty |> IntSet.of_enum

    (** generates a new cell with a value
        between 0 and 1 on any random empty space *)
    let generate_cell game =
        let empty_pos =
            game
            |> List.map (fun { position ; _ } -> position)
            |> List.fold (flip IntSet.remove) all_pos_set
            |> IntSet.to_array in
        if Array.length empty_pos = 0
        then game
        else
        let position =
            empty_pos
            |> Array.length
            |> Random.int
            |> Array.get empty_pos in 
        let value = if Random.int 16 = 0 then 1 else 0 in
        { value ; position }::game

    (** creates a new game with a single random cell *)
    let new_game () = generate_cell empty_game

    (** TODO *)
    let move _dir game = game
end

Closing thoughts

With that, we've reached the end of the first part of this series. We've explored a bit of OCaml syntax, declared our module types, and implemented the new_game function. In the next entry, we'll implement the move function, and with that we'll have a functioning game!

If you've reached this point in the article, I'd like to thank you for taking your time to read it! Also, if you know OCaml, and have any suggestions on how I can improve the code, I'd be glad to hear from you, so feel free to send me an email at midori@shibukawa.io. If you want to have a look at the actual repository, this branch has the full code for this article.

Until next time!

Footnotes

t ^[1]: When a module revolves around a type it declares, it's an OCaml convention for that type to be called t inside the module itself, as Game.t is cleaner than calling it Game.game.

unit or ()^[2]: This is OCaml's equivalent to void, and is used here so we can differentiate between a function reference and its actual execution (Game.new_game is a reference that can be passed as an argument to higher-order functions, while Game.new_game () actually executes the new_game function and returns a new Game.t structure.

option^[3]: This type is OCaml's way of representing null values of other languages such as Java or JavaScript. It is defined as Some 'a | None, which means a value of type 'a option can be either a Some 'a or a None, that is, an int option will either look like Some 1, Some 99, or None.

|?^[4]: This infix operator is provided by the Batteries community module, and will return the value boxed inside the left side option if it exists, and the right side value otherwise. So Some 1 |? 0 will return 1, while None |? 0 will return 0.

Enum^[5]: This type is provided by the Batteries module, and is used to represent finite or infinite sequences of elements. The main reason for us to use it here is due to its infix --^ operator, which makes it very easy to initialise Enum ranges.

--^^[6]: This infix operator is provided by the Batteries module, and it creates a new Enum that starts at its left side value and ends right before its right side value, so 0 --^ 2 creates an Enum of 0, 1, while 1 --^ 1000 creates an Enum of 1, 2, 3 ... 999.

|>^[7]: This infix operator gets the value that's on its left side and passes it as the last argument to the function that's on its right side, so a |> f b is the same as f b a. You can also chain them together, so a |> f1 b |> f2 is the same as f2 (f1 b a).

::^[8]: This infix operator appends its left side value to its right side list. For instance, 1::[2 ; 3] creates a new list with values [1 ; 2 ; 3].