AI for the Columns Game

Written by Gwen Weinholt on 2016-12-10

In the early part of the 1990’s there was a Windows game that I was playing on my father’s computer. I remember it quite fondly and recently found it in the Internet Archive. The game was Jewel Master by Peter Siamidis and it can be played online. I didn’t know it at the time, but it’s apparently a clone of a Sega game called Columns. Go figure. Even though I enjoyed it quite a lot I wasn’t quite good at it, and I’ve wondered what a good player would do. After my previous success with coded crosswords, I decided to give AI another go.

The strategy for this AI is simply called search, meaning it searches for the best possible move. This is how AIs work for a lot of games, even chess. To a layman it may look like the machine is thinking like a human. Like a lot of things that computers do, it turns out to mostly be an illusion. The AI sometimes seems very clever but it’s just search. If you’re reading this article in a web browser then you should be able to see the AI playing here, pretending to be clever. It’s still very impressive if you turn it up to 11, but perhaps that says more about people than about machines.



Score:
0

Game logic

The AI needs access to the game logic, so the first step is to write the game code. If you’re only interested in the search algorithm, you can skip to the next section. The game will be organized in a class that stores the jewels in an array. It also keeps track of the bottom coordinates of the falling column, the jewels in the next column, and the current score.

// Board dimensions.
const COLUMN_H = 3;             // this is also hardcoded
const BOARD_W = 6;
const BOARD_H = 14 + COLUMN_H;

// Jewels.
const JEWEL_BASE = 0x01;
const JEWEL_CLEAR = 0x00;
const JEWEL_MAGIC = 0x7f;
const JEWEL_COLORS = 6;
const MAGIC_CHANCE = 0.01;

class ColumnsGame {
    constructor() {
        this.next_column = new Uint8Array(COLUMN_H).
            fill(JEWEL_CLEAR);
        this.board = new Uint8Array(BOARD_W * BOARD_H).
            fill(JEWEL_CLEAR);
        this.column_x = 0;
        this.column_y = 0;
        this.score = 0;
    }

    board_ref(y, x) {
        return this.board[x * BOARD_H + y];
    }

    board_set(y, x, v) {
        this.board[x * BOARD_H + y] = v;
    }
}

The board_ref and board_set methods turn the flat board array into a C-style multidimensional byte array. This is perhaps not very JavaScripty, but that’s just because I didn’t write this in JavaScript the first time around. The jewels are stored as bytes. The empty parts of the board are JEWEL_CLEAR, a magic column contains JEWEL_MAGIC and the other jewels begin at JEWEL_BASE (1-6).

The board has extra space for a column above the normal board height, so that it will be easier to place the next column on the board (this part of the board can be skipped in the rendering). If everything has stopped falling and there are still jewels in this hidden area, then the game is over.

class ColumnsGame {
    // ...

    is_game_over() {
        // If any column can fall then the game is not over.
        for (let y = BOARD_H - 1; y > 0; y--)
            for (let x = 0; x < BOARD_W; x++)
                if (this.board_ref(y, x) === JEWEL_CLEAR &&
                    this.board_ref(y - 1, x) !== JEWEL_CLEAR)
                    return false;  // the column can fall to line y

        // If no column can fall and there are still columns in the
        // hidden area -- game over.
        for (let y = 0; y < COLUMN_H; y++)
            for (let x = 0; x < BOARD_W; x++)
                if (this.board_ref(y, x) !== JEWEL_CLEAR)
                    return true;

        return false;
    }
}

I hope this has given a feel for how the game logic works. These are the remaining parts:

  • The game needs to create new columns and place them on the board. This is done using a combination of two methods: make_next_column and place_next_column. When the game starts it will make the next column, place it, and then make the next column again.

  • The method fall makes all jewels fall down one row and returns how many jewels fell. This is used to move the falling column and it’s also used after jewels have been removed from the board.

  • The method rotate is used to rotate/cycle the jewels inside the falling column. The bottom jewel may be moved to the top, shifting the other jewels down one line (it could also be done in reverse).

  • After the column has stopped falling there are two ways to remove jewels from the board. The magic column is handled by remove_magic and lines are handled by remove_lines. After one of these has run and the jewels have fallen down there may be an opportunity for even more lines to be removed. This is handled by remove_until_fixpoint, which runs remove_lines in a loop until nothing changes. Finally it returns an increment in the score of the game. Lines that are removed in later loop iterations are given a bonus.

  • It should be possible to move the falling column to a new x coordinate. This is handled by move_falling_column, which is used by the AI, but it would also be used by a real player.

The full code is available here.

Searching for the best solution

In order to play the game the AI needs to pick an x coordinate for the falling column. Although it’s somehow optional, it should also consider which way to rotate the jewels inside the column. A simple search is straight-forward: loop over all x coordinates and all rotations; use those values and see what happens; if the score is better than any previous one then use those values; and then restore the board to its previous state. At the end use the best values and let the game continue. (Initially the best score is -1 so that the AI will not chose x = 0 until it has seen that it will not lose the game by doing that).

class ColumnsGame {
    // ...

    simple_ai() {
        let best_x = 0, best_rotate = 0, best_score = -1;

        // Save everything so it can be restored.
        const backup_x = this.column_x, backup_y = this.column_y;
        const backup_board = this.board.slice();

        // The falling column should be placed somewhere on
        // the board. Consider every x coordinate and rotation.
        for (let x = 0; x < BOARD_W; x++) {
            for (let rotations = 0; rotations < COLUMN_H;
                 rotations++) {
                // Move to column x, rotate and let the column
                // fall down.
                this.move_falling_column(x);
                for (let i = 0; i < rotations; i++)
                    this.rotate();
                while (this.fall() > 0)
                    ;

                // Sum up the score for this x and rotation.
                const score = this.remove_until_fixpoint();

                if (!this.is_game_over() && score > best_score) {
                    // This is better than any other x and
                    // rotation so far.
                    best_x = x;
                    best_rotate = rotations;
                    best_score = score;
                }

                // Restore the board.
                for (let i = 0; i < this.board.length; i++)
                    this.board[i] = backup_board[i];
                this.column_x = backup_x; this.column_y = backup_y;
            }
        }

        // Move and rotate.
        this.move_falling_column(best_x);
        for (let i = 0; i < best_rotate; i++)
            this.rotate();
    }
}

Does this work? If you scroll up to the running game and press Simple and crank it up to 11, you should see that it doesn’t play very well. It tends to build a tall tower to the left of the board and it eventually loses control.

The smart AI has the same core logic, except it additionally considers what it can do with the next column. How many possibilities does the AI need to consider? For the x coordinate there are 6 possibilities, and for the rotations there are 3 possibilities. Combine this with doing the same for the next column and there are only 6⋅3⋅6⋅3 = 324 possibilities. Easy! Another modification is that the initial x coordinate is random. This is merely a cosmetic feature that spreads out the jewels evenly across the board.

The full code for the smart AI is available here. All that has been added is two loops inside the already existing loop. These loops do the same thing as presented above, except for the next column.

An even deeper search strategy is possible, but I did not investigate this. The AI knows what the next column is, but it could additionally investigate every possible column that could follow that one. It can’t know for sure what column will follow, so it’s not such a good idea to use the values that lead to the maximum score in this case. Perhaps it could instead be used to avoid bad situations.

Morale of the story

I learned a few things from watching the AI playing. It’s better than me at changing its mind when it sees a better opportunity (even though that’s because it has no memory) and it’s better at seeing the consequences of its actions. And of course it considers every possible action, something that can just take too much time for me in even this simple game. It turns out that I’m more like the simple AI, and I enjoy watching the smart AI playing on Slow.

I also find it interesting that the smart AI plays so well. There’s nothing intrinsic in its design that guarantees that it will not lose a game, no property that makes it a winner every time. In fact, it should not be very difficult to make a crooked random number generator that observes the AI and gives it the worst possible (yet seemingly random) columns. But with normal randomness that doesn’t seem to happen. If some of the game parameters are changed (smaller board, different number of colors, etc) then even the smart search will lose. It looks like the game designer tried out a few variations and came up with one that works.