Threes! AI — Game Representation

Please note that this article contains spoilers about the internal workings of Threes! such as the next tile generator.

Threes!

Threes! is a puzzle game about combining numbers.  To start with, 1 and 2 become 3.   After 1 and 2, you can only combine tiles of the same value, so 3 and 3 would become 6, and 6 and 6 would become 12.   You may be familiar with this concept of combining numbers, which is featured in the popular game 2048 (derived from Threes, and in which powers of 2 are combined).

I played the game for a while, and having reached a fairly meagre high score of 27,351, I wondered if I could create an AI which would play Threes better than me.  I chose to use C++ rather than Python to create this AI to take advantage of the threading features in C++11, and also to have more control over how the game state was stored and passed around.

This article will discuss how I represented the game, namely the storage of the game state, the possible moves, the tile generator, and the scoring system.

Tiles

There are 16 tiles in Threes, each of which can take on a value of either 0 (empty), 1, 2, or \( 3 \times 2^n \) (where n is a non-negative integer).  So I coded the tile value as below:

\[ c(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 + \log_2\left(\frac{x}{3}\right) & \mbox{if } x > 3 \end{array} \right. \]

A coded tile value can then be decoded in the following way:

\[ c^{-1}(x) = \left\{ \begin{array}{ll} x & \mbox{if } x \leq 3 \\ 3 \times 2^{x-3} & \mbox{if } x > 3 \end{array} \right. \]

In this way, tile values up to 12288 (\( 3 \times 2^{15-3} \)) can be stored in a nibble. The game state contains 16 tiles of 4 bits, so a total of 64 bits is needed to store the game state. I chose to store the game state as a 64 bit integer.

We can now define a function which determines whether two tiles can be paired, and finds the value of the combined tile if they can be paired:

const int CANNOT_PAIR = -1;

static int pair_result(int x, int y) {
    if (x > 2 && y > 2 && x == y) {
        return x + y;
    } else if (x == 0 || y == 0) {
        return max(x, y);
    } else if (x + y == 3) {
        return 3;
    }
    return CANNOT_PAIR;
}

The first conditional allows two tiles with a value of the same multiple of 3 to be paired. The second conditional allows a tile to move into an empty space. For example, if a 6 tile is being moved into an empty space, pair_result(6, 0) will be called, which will give a result of 6, so the value of the empty space becomes 6. The tile value for the initial position of the 6 tile is then set to 0. The last conditional allows 1 and 2 to be paired to make 3. If none of these cases apply, then the tiles cannot be paired.

Moves

There are four moves in Threes, which are up, down, left, and right. I could have implemented these moves with one function, however for readability purposes and because there are only four moves, I decided to implement a function for each move. Here, I’ll describe the up move.

When the board is slid up, the top row is immobile and cannot move. So we skip the first row and start from the second row. We then try to slide each tile onto the one above it. If they don’t pair, then we leave the tile as it is. If they do pair, then we set the top tile to the combined value and we set the bottom tile to 0 (to represent an empty tile location). Having finished the second row, we repeat this for the third row and finally the last row.

If we manage to pair at least one tile (including pairing a tile with an empty space) during this process, then the move is possible. At least one tile needs to move for the slide to be considered valid: if no tiles move, the game state doesn’t change.

Here is the function which is called to slide the board up:

bool Board::slide_up() {
    bool can_move = false;
    for (int i=1; i < 4; i++) {
        for (int j=0; j < 4; j++) {
            if (tile(i, j) == 0) {
                continue;
            }
            
            int pair_res = pair_result(tile(i, j), tile(i-1, j));
            
            if (pair_res != CANNOT_PAIR) {
                set_tile(i-1, j, pair_res);
                set_tile(i, j, 0);
                if (pair_res != 0) {
                    can_move = true;
                }
            }
        }
    }
    
    if (can_move) {
        last_slide = SLIDE_UP;
    }
    
    return can_move;
}

If the move is valid, then the player’s turn is finished, and the computer will then place the next tile onto the board (we’ll discuss how the AI does this in a later article).

Tile Generator

In Threes, the tile generator algorithm decides the next tile to be put in play (which is then displayed at the top of the screen). It is also used to select the starting tiles for a new game. The AI I created uses the description of the algorithm posted to Touch Arcade by kamikaze28. Tile generation is divided into two parts: the basic tiles, and the bonus tiles.

The basic tiles are 1, 2, and 3. These are generated by the following procedure, as described by kamikaze28:

The mechanic for drawing basic cards is best described with a face-down stack of cards as one would use in card games like Mau Mau or Gin rummy. In the case of Threes! this stack is comprised of the following cards:

  • 4x blue 1s
  • 4x red 2s
  • 4x white 3s

As with the physical analogy, card stacks in Threes! are also shuffled upon creation. …With every move the top card of the stack is drawn which reveals the next card. When the last card of a stack is drawn after a move, a new stack is instantly created and shuffled. The top card of the fresh stack is then displayed as the next card.

Tiles above 3 are considered bonus tiles. The highest bonus tile that can be generated is the highest tile value on the board divided by 8, so bonus tiles can only be generated when a 48 tile or higher is on the board.

When bonus tiles are available, there is a 1/21 chance that the tile generated will be a bonus tile. Each bonus tile available has an equal chance of being generated, so the chance of a 6 being generated is the same as the chance of a 12 being generated (if both 6 and 12 are available).

Basic tile generation

To implement the basic tile mechanism, I created an array called rem_tile_count. This stores the number of each of the 1, 2, and 3 tiles left in the stack. The following function returns the total number of remaining tiles, and regenerates the stack of tiles if it is empty:

int Board::total_tiles_rem() {
    int total_rem = std::accumulate(rem_tile_count, rem_tile_count+3, 0);
    
    if (total_rem == 0) {
        for (int i=0; i<3; i++) {
            rem_tile_count[i] = 4;
        }
        total_rem = 12;
    }
    return total_rem;
}

The basic tile is then generated by picking a random integer n, 0 ≤ n < total_tiles_remaining(). This can then be mapped to a tile value. The way that I do this can be visualised as assigning indexes to each tile, then generating the tile at index n. Let r(x) indicate the number of tiles of value x that remain in the stack. The 1 tile is assigned indexes 0 ≤ m < r(1). The 2 tile is then assigned indexes r(1) ≤ m < r(1) + r(2). Finally, the 3 tile is assigned indexes r(1) + r(2) ≤ m < r(1) + r(2) + r(3). Once the tile has been generated, we remove it from the stack and return its value. Here is an implementation of the basic tile generator (note that the r(x) function is denoted by rem_tile_count[x-1] due to the zero-indexing of arrays):

int Board::new_standard_tile() {
    int total_rem = total_tiles_rem();
    
    if (total_rem > 12) {
        throw "Total number of remaining tiles is too great.";
    }
    
    int rand_num = arc4random() % total_rem;
    
    if (rand_num < rem_tile_count[0]) {
        rem_tile_count[0]--;
        return 1;
    }
    
    if (rand_num < total_rem - rem_tile_count[2]) {
        rem_tile_count[1]--;
        return 2;
    }
    
    rem_tile_count[2]--;
    return 3;
}

Bonus tile generation

Because each bonus tile available has an equal chance of being generated, the bonus tile generator is much easier to implement. My implementation uses the fact that the bonus tiles 6, 12, 24, 48 etc have codes 4, 5, 6, 7 etc. First, we determine the maximum bonus tile value b (this is just the highest tile value on the board divided by 8). We then pick a random integer m, 4 ≤ m ≤ c(b). m is the coded value of the bonus tile, so the generated bonus tile value is \( c^{-1}(m) \).

I implemented this method slightly differently so that the random integer I need is of the format produced by arc4random().

First I found the number of bonus tiles available, s. This is equal to c(b) - 3 because the bonus tiles have codes 4, 5, 6 and so on. Now I can pick an random integer q, 0 ≤ q < s. This inequality is equivalent to 0 ≤ q < c(b) - 3, which is equivalent to 0 ≤ q ≤ c(b) - 4 because we are dealing with integers.

Therefore, to obtain the tile code of the generated tile, we can manipulate the inequality so it takes the form of the inequality 4 ≤ m ≤ c(b) that we found earlier. Adding 4 to each part of the inequality, we get 4 ≤ q + 4 ≤ c(b). It is now easy to see that m = q + 4, so the generated bonus tile value is \( c^{-1}(q+4) \).

This function defines the number of cards in the bonus pool, s:

int Board::bonus_pool_size() {
    int max_card = encode_tile_val(high_tile_val / 8);
    return std::max(0, max_card - 3);
}

And here is the function which generates the bonus tile, \( c^{-1}(m) \):

int Board::new_bonus_tile() {
    uint8_t tile_code = 4 + arc4random() % bonus_pool_size();
    return decode_tile_val(tile_code);
}

 

We can now generate a tile like so:

int Board::generate_new_tile_val() {
    if (high_tile_val >= 48 && arc4random() % 21 == 0) {
        return new_bonus_tile();
    }
    
    return new_standard_tile();
}

Scoring

Our representation of the game is coming along well, however we need to be able to differentiate between game states so that the AI can choose the move that will lead to the best game state. We do this by scoring the board. For now, we will implement the scoring that Threes uses itself, however we could define heuristics so that the AI will prefer certain characteristics such as empty spaces or a uniform gradient of tiles.

Threes scores each individual tile, so that the score of the board is the sum of all the individual tiles. Tiles less than 3 are worth nothing. For tiles 3 and over, a tile value of x will score \( 3^{\log_2(\frac{x}{3}) + 1} \) points.

Here is an implementation of a function to give the score of an individual tile:

int tile_score(int tile_val) {
    if (tile_val < 3) {
        return 0;
    }
    return pow(3, intlog2(tile_val/3) + 1);
}

Hence, the score of a game state can then be evaluated using the following function:

int Board::score() {
    int board_score = 0;
    for (int i = 0; i < 16; i++) {
        board_score += tile_score(tile(i/4, i%4));
    }
    return board_score;
}

 

We can now store the game state, execute moves, generate new tiles using the correct procedure, and evaluate the score of particular game states. An AI can now be implemented on top of this core logic.