Using WaspVM to create a simple Tic-Tac-Toe game

Recently at Elixium we’ve been spending a bunch of time developing a WebAssembly Virtual Machine called WaspVM in Elixir, which we’ll use to power decentralized applications running on the network. The main goals of the VM is to allow for good scalability when running multiple instances at once (as will be the case when running decentralized applications in parallel) and to be able to run fault tolerant instances (removing the need to rely on NIFs which can potentially cause an entire BEAM instance to crash). Although WaspVM will be used within Elixium, it is built with the intention of being general purpose. Here’s a guide on how to use WaspVM to seamlessly integrate WebAssembly into your elixir application.

In this post, we’ll go through building a simple Tic-Tac-Toe application. We’ve chosen Tic-Tac-Toe because it’s simple enough to run through in a blog post, yet complex enough to showcase most of WaspVM’s features.

Initializing the project

In order to quickly get started, let’s generate an application using mix . To create a new project, run mix new wasm_ttt in your terminal. Once mix generates the project structure, open it with your favourite text editor. In the mix.exs file at the root of the project, add WaspVM as a dependency:

defp deps do
[
{:wasp_vm, "~> 0.8.1"}
]
end

While we’re here, lets add an application to the application section of the mix.exs file. This’ll allow us to more simply run the project:

def application do
[
mod: {WasmTtt, []},
extra_applications: [:logger]
]
end

Open up the generated lib/wasm_ttt.ex file, and change it to:

defmodule WasmTtt do
use Application
  def start(_type, _args), do: Task.start(fn -> run_game() end)
  def run_game do 
# Start a fresh VM instance
{:ok, pid} = WaspVM.start()
end
end

Now that we’ve done this, we’ll be able to run the application with mix run , although at this point we aren’t doing anything but initializing the VM. In order to have the VM execute code, we’ll need to give it a WebAssembly module to run.

A primer on WebAssembly

WebAssembly files come in two flavors: human-readable, and binary; their file extensions are .wat and .wasm, respectively. Virtual machines can’t run the human-readable format — this format is made to be used by humans to either debug or write WebAssembly code, this means that VMs can only run the binary format.

The typical workflow for developing a WebAssembly module is to write the module in the human-readable format and then compile that to the equivalent binary format. This can be done with a number of tools — we’ll be using wabt, the WebAssembly Binary toolkit, which has a tool called wat2wasm; this tool compiles .wat (human-readable) WebAssembly files to .wasm (binary) files.

Onward with development

After installing your Wasm compilation tool of choice, we’re ready to begin developing our Tic-Tac-Toe game. This post won’t cover how to write WebAssembly nor it’s syntax, so if you’re unfamiliar with it, stop here and brush up on some basics, and read on once you’re comfortable.

In order to house our WebAssembly modules, let’s create a directory in the root of the project called “priv”, and within that directory two others called “wat” and “wasm”, which will hold .wat and .wasm files, respectively.

In the priv/wat directory, create a file called tic_tac_toe.wat. Here we’ll define the functionality for our game. In this file, let’s define a simple WebAssembly module:

(module
(memory (export "game_mem") 1)
(func (export "play") (result i32)
i32.const 100
)
)

Here we have a basic Wasm module that’ll shape our game. Let’s compile the module to a .wasm binary:

wat2wasm priv/wat/tic_tac_toe.wat -o priv/wasm/tic_tac_toe.wasm

Once the module is compiled, you’ll have a tic_tac_toe.wasm file in your priv/wasm directory. Now that we have a binary WebAssembly module, we can pass it to the VM and have it load the module. Back in our wasm_ttt.ex file:

def run_game do
...
# Load a WebAssembly module into the VM from a .wasm file
WaspVM.load_file(pid, "priv/wasm/tic_tac_toe.wasm")
end

We can also execute the exported “play” function that we defined in the Wasm module:

def run_game do
...
# Load a WebAssembly module into the VM from a .wasm file
WaspVM.load_file(pid, "priv/wasm/tic_tac_toe.wasm")

{:ok, gas, result} = WaspVM.execute(pid, "play")

IO.puts "Result: #{result}"
IO.puts "This game of Tic-Tac-Toe burned #{gas} gas"
end

If we run this now, we should see the output:

Result: 100
This game of Tic-Tac-Toe burned 3 gas

Gas is an internal unit that determines how much computation power was expended to run the module. We can ignore it for the rest of this post, we won’t be needing it. You’ll notice that the result was 100; this is the only value we defined in our “play” function, and since we specified that the function had a return value of an i32, it was implicitly returned.

Board structure

In Tic-Tac-Toe, the game board is usually a 3x3 matrix. Since WebAssembly only has integer and float types, we can’t use an array to represent our board, but we do have a structure that we can use in order to represent abstract data types: linear memory. In our module, we defined a memory called “game_mem” and initialized it with 1 kB of space. 1kB is the minimum memory size for a WebAssembly module, but we’ll only need 9 bytes.

We’ll use 1 byte of memory for each tile on the board. Each tile will be referenced in our program by it’s index on the board, like so:

 0 | 1 | 2
---+---+---
3 | 4 | 5
---+---+---
6 | 7 | 8

We’ll use the integer 120 to represent the character ‘x’ on the board, and 111 to represent ‘o’.

Basic game loop

In order for our game to last multiple rounds, we’ll need to have a game loop that runs until one of the players win. We can define a game loop like so:

(module
(memory (export "game_mem") 1)
(func (export "play") (result i32)
loop $main

br $main
end

i32.const 100
)
)

At this point, our game is just an infinite loop — not very exciting. Since Tic-Tac-Toe just consists of two players taking turns to place a token on the board, we know that the first thing we need to do in the game loop is to ask the first player where on the board they’d like to place their token. To do this, we’ll need a way to ask the user for input directly. Unfortunately, WebAssembly doesn’t have the power to do this on it’s own, but it does have a way of delegating this kind of responsibility to something that does — the host machine (WaspVM in our case).

This delegation is done by importing a function from the outside world into the WebAssembly module. Functions that are imported from the outside are called host functions. Let’s create a host function that will ask the player for the tile number at which they want to place their token and places it onto the WebAssembly VM’s stack. At the top of our tic_tac_toe.wat module, add the import:

(module
(import "WasmTtt" "get_move_for_player" (func $get_move_for_player (param i32) (result i32)))
...
)

This function takes a parameter for the player number (which will be 0 or 1, depending on which player we’re querying), and results in one i32 value getting added to the top of the stack. In our “play” function, we can call this host function just like a normal function:

i32.const 0 ;; Player 0
call $get_move_for_player

We know that each player will get a turn, that each player’s turn will be identical, and that the game can be won after a turn. Let’s define a function called “turn” that will contain this logic. It’ll take in a player number as a parameter and will return a 1 if the game was won during this turn, and a 0 otherwise:

(func $turn (param $player_num i32) (result i32)
get_local $player_num
call $get_move_for_player
)

We still have yet to actually define our “get_move_for_player” host function. Let’s do that now. WaspVM features a Domain-Specific-Language (DSL) that makes defining host functions seamless. In order to use this DSL, we need to add it to our Elixir module. Back in the wasm_ttt.ex file, add

use WaspVM.HostFunction

to the top of the module. Now we have access to a macro called defhost . This macro allows us to define host functions that look pretty similar to normal elixir functions. Let’s define the “get_move_for_player” function as a host function:

defmodule WasmTtt do
...
use WaspVM.HostFunction
  ...
  defhost get_move_for_player(player) do
p = if player == 0, do: "X", else: "O"

{tile, _} =
"\nPlayer #{p}, which tile? > "
|> IO.gets()
|> Integer.parse()

tile
end
end

This function will just ask the player which tile they’d like to place their token on, expecting an integer as a response. Host functions automatically add their return value to the VM’s stack if that return value is a number.

We need to tell WaspVM to use this elixir module as a provider of host functions in order to be able to reference this host function in our WebAssembly module. Up above, where we defined the run_game/0 function, we can do this using WaspVM.HostFunction.create_imports/1 , like so:

def run_game do
# Start a fresh VM instance
{:ok, pid} = WaspVM.start()

# Generate host functions based on the current module
imports = WaspVM.HostFunction.create_imports(__MODULE__)
  # Load a WebAssembly module into the VM from a .wasm file
WaspVM.load_file(pid, "priv/wasm/tic_tac_toe.wasm", imports)
  {:ok, gas, result} = WaspVM.execute(pid, "play")
  IO.puts "This game of Tic-Tac-Toe burned #{gas} gas."
end

Notice that we’re now passing in the imports as a third parameter to WaspVM.load_file . We passed __MODULE__ to the create_imports function because the host function we want to use is defined in this same module — if it were in another module we’d pass in the name of that module instead. It’s important to note that the name of this elixir module is the same as the name we passed in at the top of the WebAssembly module (“WasmTtt”), these must match or else the function will not be imported into the VM and will not be accessible from WebAssembly.

Let’s update our tic_tac_toe.wat file to look like:

(module
(import "WasmTtt" "get_move_for_player" (func $get_move_for_player (param i32) (result i32)))
(memory (export "game_mem") 1)
(func (export "play") (result i32)
loop $main
i32.const 0
call $turn
      i32.const 1
call $turn

br $main
end

i32.const 100
)
  (func $turn (param $player_num i32) (result i32)
get_local $player_num
call $get_move_for_player
)
)

If we compile our .wat file now, and run mix run --no-halt we’ll infinitely get queried for which tile we’d like to place our token on:

Player X, which tile? > 1
Player O, which tile? > 0
Player X, which tile? > 2
Player O, which tile? >

This isn’t very exciting yet, but we’ve successfully defined our host function and made it accessible from within our WebAssembly module — and we’re able to run the game loop successfully.

Move validity checking

We want to ensure that the tile the player has chosen to place their token on is a valid one. This means that a) the number they entered must be a valid tile and b) the tile is empty. We can do this easily enough; we know that the maximum number for a tile is 8, and a tile is empty if it doesn’t have the number 120 or 111 in it (luckily for us, it’s even simpler than this, since Wasm memory is initialized to be all 0s). We can check that the given tile number is less than 9 and that the memory location represented by that tile is equal to zero. Let’s update our $turn function:

(func $turn (param $player_num i32) (result i32) (local $cell i32)
get_local $player_num
call $get_move_for_player
tee_local $cell
  ;; Check if cell is within range (less than 9)
i32.const 9
i32.lt_s
  ;; Check if cell is empty
get_local $cell
i32.load8_s
i32.eqz
  ;; Binary "and" the above results. We want both values to be 1
i32.and
if (result i32)
;; Empty, for now
else
call $invalid_move
get_local $player_num
call $turn
end
)

You’ll notice 2 things about the above: we’re calling a function that we haven’t defined ( $invalid_move ), and that we’re recursively calling $turn if the player makes an invalid move; this’ll just query the player for input again and again until they give us something valid. We want to let the player know when they’ve tried to play an invalid move, but since WebAssembly has no way of doing this we’ll once again need to use host functions to achieve this. Back in our WasmTtt module, let’s define the host function:

...
defhost invalid_move do
IO.puts "Invalid Move! Try again."
end
...

That one was pretty simple. We still need to import the function at the top of our WebAssembly module, let’s add it right below the other import declaration:

(import "WasmTtt" "invalid_move" (func $invalid_move))

This function doesn’t take arguments or return a value so it’s import declaration is simpler.

Valid moves

At this point, we’ve covered what happens when an invalid move is played — now let’s handle what happens when a valid move is played. In the $turn function, within the “if” statement, add the following:

get_local $cell
get_local $player_num
call $player_char_from_number
;; Update the board
i32.store8
call $draw_board
get_local $player_num
call $check_winner

Again, you’ll notice we’re calling a few functions we haven’t defined yet. The first of these is $player_char_from_number . This function will just find the correct corresponding token character based on the player’s number. Player 0 will be X and player 1 will be O. Lets’s create the function now to reflect that:

(func $player_char_from_number (param $player_num i32) (result i32)
get_local $player_num ;; 1 or 0
if (result i32)
i32.const 111 ;; o
else
i32.const 120 ;; x
end
)

This function will return either 111 or 120, depending on the player’s number, then we call i32.store8 , which will store the number as a byte into the module’s linear memory at the memory location of $cell . Once this happens, we need to draw the game board to the screen, so that the players can see what the game board looks like. Thats where the $draw_board function comes in.

Again, since we’re unable to write to the terminal directly from WebAssembly, we’ll use a host function to accomplish this:

defmodule WasmTtt do
...
  defhost draw_board do
board = WaspVM.HostFunction.API.get_memory(ctx, "game_mem", 0, 9)
    IO.puts ""
    rows = for <<a::8, b::8, c::8 <- board>>, do: {<<a>>, <<b>>, <<c>>}
    rows
|> Enum.with_index()
|> Enum.each(fn {{a, b, c}, idx} ->
if idx == 1, do: IO.puts "---+---+---"
        IO.puts " #{charfor(a)} | #{charfor(b)} | #{charfor(c)}"
        if idx == 1, do: IO.puts "---+---+---"
end)
end
  defp charfor(<<0>>), do: " "
defp charfor(i), do: i
  ...
end

You’ll notice the line

board = WaspVM.HostFunction.API.get_memory(ctx, "game_mem", 0, 9)

is reading from the module’s memory. We do this by using WaspVM’s HostFunction API, which gives host functions a few extra tools that can interact with the VM. You’ll also notice that we’re passing in a variable, ctx , which is never defined. This variable is defined by the defhost macro, and is solely used as a reference that’s passed into the HostFunction API.

In the draw_board function above, we’re reading 9 bytes of memory starting at address 0 from the “game_mem” memory that we exported from our WebAssembly module. We’re then enumerating over these bytes and drawing a board onto the screen based on them.

The last function we call in that if statement is $check_winner . We’ll get to this in a bit; for now let’s just stub it like this:

(func $check_winner (param $player_num i32) (result i32) (local $player_char i32)
i32.const 0
)

Finalizing the game loop

Our game loop is pretty simple at this point, but right now the game will run infinitely. In order to check if the game has been won, we need to modify our loop to check the result of each turn. We know that our $turn function returns a 1 or a 0 based on whether the game has been won. We can use this return value in the game loop to check whether the game has ended; if either of the calls to turn return a 1, the game is over — and the player whose turn was most recent has won. We let’s add a few if statements to handle this for us:

loop $main
i32.const 0
call $turn
if
i32.const 0
end
  i32.const 1
call $turn
if
32.const 1
end
  br $main
end

Now we have an if statement that returns the value of which player won onto the stack, but we still need to break out of the loop, or else we’ll keep running the game indefinitely.

If we wrap the whole loop in a block , we can easily break out of the loop whenever we want and return the player number who won:

block $end_game (result i32)
loop $main
i32.const 0
call $turn
if
i32.const 0
br $end_game
end
    i32.const 1
call $turn
if
i32.const 1
br $end_game
end
    br $main
end
  i32.const 100
end

Before we compile this module, we need to add the import for $draw_board to our WebAssembly module:

(import "WasmTtt" "draw_board" (func $draw_board))

If we compile now, and run using mix run --no-halt , we can fill out the game board while alternating players:

Player X, which tile? > 0
 x |   |
---+---+---
| |
---+---+---
| |
Player O, which tile? > 4
 x |   |
---+---+---
| o |
---+---+---
| |
Player X, which tile? > 3
 x |   |
---+---+---
x | o |
---+---+---
| |
Player O, which tile? > 8
x | |
---+---+---
x | o |
---+---+---
| | o
Player X, which tile? > 8
Invalid Move! Try again.
Player X, which tile? > 6
 x |   |
---+---+---
x | o |
---+---+---
x | | o
Player O, which tile? >

You’ll notice we correctly detected invalid moves, and asked the player to try again. The only piece that we’re missing now is checking whether the player has won, as you can see above where X got 3 in a row vertically, but the game didn’t end.

Detecting wins

There are many ways to detect if a player has won in Tic-Tac-Toe. For the sake of simplicity, we’ll be hard-coding all the winning combinations and checking our board against them. There are only 8 ways a player can win at Tic-Tac-Toe, based on cell numbers:

[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]

Let’s write our $check_winner function to reflect this:

(func $check_winner (param $player_num i32) (result i32) (local $player_char i32)
get_local $player_num
call $player_char_from_number
set_local $player_char
  ;; 0, 1, 2 ==============
i32.const 2
i32.const 1
i32.const 0
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 3, 4, 5 ==============
i32.const 5
i32.const 4
i32.const 3
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 6, 7, 8 ==============
i32.const 8
i32.const 7
i32.const 6
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 0, 3, 6 ==============
i32.const 6
i32.const 3
i32.const 0
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 1, 4, 7 ==============
i32.const 7
i32.const 4
i32.const 1
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 2, 5, 8 ==============
i32.const 8
i32.const 5
i32.const 2
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 0, 4, 8 ==============
i32.const 8
i32.const 4
i32.const 0
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; 2, 4, 6 ==============
i32.const 6
i32.const 4
i32.const 2
get_local $player_char
call $check_combo
if
i32.const 1
return
end
;; ======================
  ;; No combitions matched, no win. Return 0
i32.const 0
)

Not exactly pretty, but it works. There’s a function here that we haven’t defined yet: $check_combo . This function will be responsible for checking a combination of 3 cells. If all cells have the player’s token in them, its a valid match; otherwise, it’s not a match. From the above you can probably tell that the $check_combo function will need to take in 4 parameters: the numbers of the 3 cells we’re checking, and the player number that we’re checking for. The function looks like this:

(func $check_combo (param $player_char i32) (param $c1 i32) (param $c2 i32) (param $c3 i32) (result i32)
get_local $c1
get_local $player_char
call $check_cell
  get_local $c2
get_local $player_char
call $check_cell
  i32.and
  get_local $c3
get_local $player_char
call $check_cell
  i32.and
)

We have another function to check each cell individually to see if it’s equivalent to the player’s token (120 or 111). If it is, it’ll return a 1, otherwise a 0. When we ‘and’ all 3 of these together, we’ll have a 1 on the stack if they were all 1, otherwise we’ll have a 0 on the stack. The $check_cell function is as follows:

(func $check_cell (param $player_char i32) (param $cell i32) (result i32)
get_local $cell
i32.load8_s
get_local $player_char
i32.eq
)

At this point, the return value of our “play” function will be the number of the winning player. Let’s update our elixir code to handle what to do once it get’s a result from WaspVM regarding who won the game:

defmodule WasmTtt do
...
  def run_game do
# Start a fresh VM instance
{:ok, pid} = WaspVM.start()
    # Generate host functions based on the current module
imports = WaspVM.HostFunction.create_imports(__MODULE__)
    # Load a WebAssembly module into the VM from a .wasm file
WaspVM.load_file(pid, "priv/wasm/t.wasm", imports)
    {:ok, gas, winning_player} = WaspVM.execute(pid, "play")
    log_winner(winning_player)
    IO.puts "This game of Tic-Tac-Toe burned #{gas} gas."
end
  defp log_winner(player) do
p = if player == 0, do: "X", else: "O"
    IO.puts "Tic Tac Toe, 3 in a row! Player #{p} has won the game."
end
  ...
end

Now we can play a full game of Tic-Tac-Toe that we’ve written in WebAssembly! The final code for this post can be found on Github here.