Building a ClojureScript game: Tribolo Game logic

This post is the third in the series of posts focused on the design and implementation of a port in ClojureScript of the game named Tribolo.

In our first post, we discussed the game, described its rules and came up with a basic target architecture. In our second post, we tested this architecture on a Proof-Of-Concept. We built a Tic Tac Toe to make sure the architecture was sound.

This post will go through the development of the game logic of our Tribolo game, from the definition of the main entities and relationships, to the implementation choices made. The full game is available and playable at this address.

Note: This post builds on top of the previous two posts. In particular, it assumes the reader understands the rules of Tribolo. You can refer to our first post to review these rules.

 

Entities and relationships


Our first step before going into the implementation will be to think about the different concepts that make up the Tribolo game. Each of the words in bold below underlines an important concept of the game.

Cells and board

Like the Tic Tac Toe game we built in our earlier post, the game is all about player fighting for the ownership of cells. Cells can be identified by a two dimension coordinate. The board is the collection of the the cells of the game.

Turn and game

Like the Tic Tac Toe, a game is made of a succession of turn. Each turn represents a valid point in time in a complete game. Unlike the Tic Tac Toe though, cells can change owners over the course of the game. The rules to transfer ownership of cells are specific enough to deserve a name.

Transitions

We will designate as transition a valid progression from one turn a next turn. There might be several transitions available from a given turn. Each of these transition leads to a new turn. Playing a move can be viewed as following a transition.

Jumps

A transition between turns consists in realizing one or several jump. Each jump does convert the set of cells it went over. A given jump can only convert cells belonging to one opponent.

Score

The score of a player is the total amount of cells owned by the player. The player with the highest score at the final turn is the winner.

 

High Level Design


In the previous section, we figured the concepts we want to represent. Let us try to refine them by associated them some kind of high level API. This API will be our guide during the implementation.

 

Board

The Board allows to represent the concept of ownership of a cell. Much like in the Tic Tac Toe game, its main goal is to maintain a set of associations from coordinates to their associated owner. The main operations are:

  • The creation of a new board
  • The conversion of a cell to a new owner
  • The retrieval of a cell’s associated owner
  • The traversal of all associations (for rendering)

In Haskell-ish notation, it would match the following function prototypes (where IO characterizes impure functions):

 

Turn

A turn represents a given state of the game. It gives access to the board, the scores, and the next player to play.

The main operations on a turn are:

  • To create a new starting turn (when we create a new game)
  • To compute the transitions available from this turn
  • To follow one of these transitions (playing a move)

 

Game

To finish up, we can provide a very simple API for the game. From a game, we should be able to extract the current turn, play a move at a given coordinate, and go back to the previous player move (undo).

 

Board


We will start with the implementation of the board. The goal of this component is to maintain a list of associations from coordinates to their respective owners.

 

Data structure

In the Tic Tac Toe, we choose to implement the Board with an associative container from coordinates to players. For the sake of experimenting something else, we will settle for a vector of vector of owners.

The outer vector stores the column by column index. The inner vectors stores the player by row index. The main advantages of using this representation is that we can give it a nice spec with the size included in it:

We can provide an instance of an empty board, which will be helpful when we will need to instantiate a new board:

 

Specs for the API

Given the high level API we provided in the last section, we can derive the following specs for our board API:

These specifications make use of the specification for coordinates (which makes use of the fact that sets are predicates in Clojure):

 

Implementation

Most of the implementation for the board API is straightforward. The only interesting bit is the implementation of the new-board function.

A new board must contain 12 randomly located walls, and 12 randomly chosen cells owned by each player. These four sets of 12 cells must be disjoint.

We implement a generic algorithm that will handle the task of picking n elements and attribute them to each element of groups. The core algorithm pick-n-for-each is free of randomness:

 
Because we isolated the randomness side-effect from the core algorithm, we can convince ourselves that it works properly by writing some tests around it:

 
We can then use the algorithm to implement our new-board function by choosing as elements the coordinates on the board, and as groups the players plus the wall:

 

Turn


We will continue our implementation with the turn. The turn is the component that hosts most of the game logic of our Tribolo. It is quite large. So we will split its implementation in two:

  • This section will deal with the turn itself and its representation
  • The next section will zoom on the computation of the transitions

 

Data structure

A turn gives us access to current state of the board, the next player to play and the scores. We will use a simple map to store that information, and encode its schema in the following spec:

 
The representation of transitions is a bit trickier. There are many different possible implementations available. We could represent transitions as functions from turn to turn. We could try to create a protocol for it.

But because Clojure loves data, we will represent these transitions as data. A transition will be a collection jumps, with each jump being a standard map, holding:

  • The destination of the jump (an empty cell)
  • The player winning the cells jumped over
  • The player loosing the cells jumped over
  • The coordinates of the cells jumped over

We can therefore describe a jump and a transition using the specs that follow:

 

Specs for the API

We can also spec the main functions of our Turn API, based on the previous specs for jump and transitions (which we isolated to the namespace transition):

 

Implementation (transition)

We might expect the transitions function to be quite complex. Its implementation is in fact quite simple: we only access the field of the turn data structure:

 
This is due to the rules of Tribolo. A player may not have any available transition to play. If so, he passes his turn and we consider the next player in the list. We must then repeat the same again or move to the next player.

As a consequence, to implement next-turn and find the next player to play, we must compute the transitions of the newly created turn. We keep this computation cached inside the turn for optimization purposes.

 

Implementation (next turn)

To compute the next turn of a game from a previous turn and a transition, we will go through three steps:

  • We modify the board to take into account the jumps
  • We modify the scores to be aligned with the new board
  • We find the next player to play by looking at available transitions

The functions apply-transitions and update-scores scan the transitions and update the board and the scores respectively. The interesting part is the computation of the next player, which we will describe below.

 

Implementation (next player)

As discussed earlier, finding the next player to play requires to evaluate the transitions available from our current turn.

We search for the first player that has at least a move to play. We temporarily assume the existence of a function transition/all-transitions that return a map from player to their respective available transitions.

 
This ends up the implementation of the turn. The only missing part is the implementation of all-transitions. This is the subject of the next section.

 

Computing transitions


We will now discuss the implementation of the Tribolo game logic core: the identification of all the valid transitions from a given board. This means identifying all the possible jumps that can be done by any player, before grouping them by winning player and jump destination coordinate.

 

Performance constraints

The computation of the transitions from a given turn is the most CPU intensive task of the whole game. This will be especially true when we will go into the design and implementation of our AI.

As a consequence, the code that follows makes use of JavaScript arrays over ClojureScript vectors. This simple optimization trick brought nearly a 2X improvement on the AI. The same motivation is behind the use of low level loop-recur constructs in the following algorithms.

 

Algorithm purpose

The goal of the algorithm is to identify the jumps and then to group them by jump destination and player.

A potential jump is a contiguous sequence of cells owned by the same player. It becomes a real jump if it is surrounded by:

  • A cell with no owner: the destination of the jump
  • A cell with another owner: the winner of the jump

This contiguous sequence of cell must follow an row, a column, or a diagonal of the board. A wall on either side means there can be no jump.

 

Though on implementation

We can visualize an implementation based on the use of the partition and partition-by algorithms:

  • Using partition-by on cells to identify contiguous sequences of owners
  • Using partition to group contiguous sequences by window of three

This idea is demonstrated below in the REPL on the first row of a sample board. It would have to be done for each row, each column, and each diagonal:

 
This algorithm would “touch” every cell 4 times (one for each direction), leading to 16 times 11 times 4 cell reads, for a total of 704. This algorithm is nice and fine, but it is not the one we will implement. I could not find a way to make it fast enough.

 

Chosen algorithm

The algorithm we will implement is much more naive than the one described above. We will scan each empty cell and check in each direction if it is the destination of a jump.

This is not optimal: we will touch the cells more times than with our previous algorithm. It will require around 1200 cell reads at the start of the game, going down when the number of empty cells decreases.

This also looks quite naive as we could try to keep some of that computation between turns. It would require tracing what jumps are invalidated by another jump, which does not seem trivial.

 

Scanning and grouping

We will start by the implementation of the outer loop of the algorithm. This loop will scan every single cell of the board, compute all the available jumps from this position, and group them by player and jump destination.

As indicated before in the performance constraints section, this algorithm needs to be pretty fast, and makes use of a conversion to a JavaScript array at the start:

 
This code makes use of the group-by-reducer helper function, which allows to group elements by on several projections into a nested map as output:

 

Finding jumps from a destination point

To find the jumps available at a given position, the destination of the jump, we start at an empty cell (not owned by any player).

We then move from the destination point in a fixed direction. The first player we meet is the looser of the potential jump. We continue until we find a cell with a different owner. This player is the winner of the jump.

We collect the coordinates along the way to identify the “jumped over” cells (in the taken vector) until we reach the second player. In case we hit a wall or another empty cell first, we stop the exploration: there is no valid jump in the searched direction. We also watch for going out of the board.

This algorithm translates to the following code, which searches for a jump in a fixed direction from the destination of the jump:

 
We have to repeat this algorithm for each possible jump direction. We ignore the empty cells since they cannot be the destination of a jump:

 

Game


The last missing piece of the game logic is the implementation of the game. The game is simply a succession of turn. We can translate the high level API we gave to it into the following specs:

 
Its implementation is not terribly thrilling. It is like the implementation we used for Tic Tac Toe with one twist: the undo may go back several turns to find the last turn of the human player. The implementation is listed in this GitHub Gist for completeness.

 

Conclusion and what’s next


In this (pretty long) post, we went over the complete game logic of the Tribolo game, from the high level design to the implementation.

In the next posts, we will continue this journey and see how we can implement the other aspects of the game (Artificial Intelligence, User Interface, Game Loop, etc.).

But before we do that, we will spend the next post on discussing the use we made of Clojure Spec inside the game logic we implemented today.

4 thoughts on “Building a ClojureScript game: Tribolo Game logic

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s