Spielwerk 03: Tic-Tac-Toe

Tic-Tac-Toe against a computer that never loses: three by three cells, I am X, the computer is O and searches every move to the end. The board is the interesting part, because every board game asks it the same questions. The new toolbox module is Grid2D, a generic grid that knows its cells, its neighbours and its lines.

Play it · Source: collection-spielwerk/03-tic-tac-toe · Toolbox 5.4.0 or later

The game

I place an X, the computer answers with an O after a short pause. Three in a row, across, down or diagonal, wins and is struck through; a full board is "Unentschieden" (draw). The score card counts wins for both sides and draws, and "Neue Runde" (new round) clears the board and swaps who opens. The computer plays perfectly, so a draw is the best I can get; only its first move of a round is drawn from the seed among the equally good moves.

• Mouse/touch: click a cell, "Neue Runde".
• Keyboard: 1 to 9 in numpad layout (7 8 9 is the top row), Space or Enter for a new round.

New in the toolbox: Grid2D

A Tic-Tac-Toe board written by hand is an array of nine strings and a hard-coded list of the eight winning lines. That works, until the next game: Four in a Row needs a 7x6 board and 69 lines of four, Minesweeper needs the neighbours of a cell, a tile map needs bounds checks. Each of them re-derives the same index arithmetic, and a typo in one of 69 hand-written lines is a bug nobody finds.

The idea: one rectangular grid, stored row-major in a single array, that answers the geometric questions itself. What a cell means (a mark, a mine, a tile) is the type parameter and belongs to the game.

export class Grid2D<T> {
    constructor(width: number, height: number, fill: T | ((x: number, y: number) => T));
    readonly width: number;
    readonly height: number;
    is_inside(x: number, y: number): boolean;
    index_of(x: number, y: number): number;       // y * width + x, not range checked
    get(x: number, y: number): T;                 // throws outside the grid
    set(x: number, y: number, value: T): void;    // throws outside the grid
    cells(): GridCell<T>[];                       // { x, y, value }, row by row
    row(y: number): T[];
    column(x: number): T[];
    lines(length: number): GridPosition[][];      // every straight run of `length` cells
    neighbours(x: number, y: number, diagonal?: boolean): GridCell<T>[];
    map<U>(fn: (value: T, x: number, y: number) => U): Grid2D<U>;
    clone(): Grid2D<T>;                           // same values, independent storage
    fill(value: T): void;
    count(predicate: (value: T) => boolean): number;
}

The method worth reading is lines(n). Instead of listing winning lines, it walks every cell in four directions (right, down, diagonal down, diagonal up) and keeps each run whose end cell is still inside:

public lines(length: number): GridPosition[][] {
    if (!Number.isInteger(length) || length < 1) {
        return [];
    }
    // A run of one cell has no direction: every cell once, not four times.
    const directions: GridPosition[] = length === 1
        ? [{ x: 1, y: 0 }]
        : [{ x: 1, y: 0 }, { x: 0, y: 1 }, { x: 1, y: 1 }, { x: 1, y: -1 }];
    const result: GridPosition[][] = [];
    for (const direction of directions) {
        for (let y = 0; y < this.height; y++) {
            for (let x = 0; x < this.width; x++) {
                const end_x = x + direction.x * (length - 1);
                const end_y = y + direction.y * (length - 1);
                if (!this.is_inside(end_x, end_y)) {
                    continue; // the run would leave the grid
                }
                const line: GridPosition[] = [];
                for (let i = 0; i < length; i++) {
                    line.push({ x: x + direction.x * i, y: y + direction.y * i });
                }
                result.push(line);
            }
        }
    }
    return result;
}

On 3x3 that yields exactly the eight Tic-Tac-Toe lines; on 7x6 the 69 lines of four, without anyone counting them. neighbours(x, y, diagonal) returns the four or eight cells around a position that lie inside, so a corner has two or three. get and set throw outside the grid on purpose: a wrong coordinate should fail loudly, not return undefined.

The game builds its lines once and checks a board with them:

// src/game/Game.ts
this.board = new Grid2D<Mark>(Game.SIZE, Game.SIZE, '');
this.lines = this.board.lines(Game.SIZE);

public static winning_line_of(board: Grid2D<Mark>, lines: GridPosition[][]) {
    for (const line of lines) {
        const first = board.get(line[0].x, line[0].y);
        if (first === '') {
            continue;
        }
        if (line.every((position) => board.get(position.x, position.y) === first)) {
            return { winner: first, line };
        }
    }
    return null;
}

The computer's minimax uses clone(): for every empty cell it copies the board, places a mark on the copy and scores it recursively, while the real board stays untouched. count((value) => value === '') tells whether the board is full. The tree of a 3x3 board is small enough to search completely, without pruning.

The test (src/data/Grid2D.test.ts) pins down the line counts and the independence of copies:

it("lines(3) on a 3x3 grid yields exactly the 8 Tic-Tac-Toe lines", () => {
    const grid = new Grid2D(3, 3, 0);
    const lines = grid.lines(3);
    expect(lines).toHaveLength(8);
    const keys = lines.map((line) => line.map((p) => `${p.x}${p.y}`).join("-"));
    expect(keys).toContain("00-11-22"); // main diagonal
    expect(keys).toContain("02-11-20"); // anti diagonal
    expect(grid.lines(4)).toHaveLength(0);
    expect(new Grid2D(7, 6, 0).lines(4)).toHaveLength(69);
});

it("map and clone are independent of the source", () => {
    const grid = new Grid2D(2, 2, 1);
    const copy = grid.clone();
    copy.set(0, 0, 99);
    expect(grid.get(0, 0)).toBe(1);
});

The trap the second test guards against: a "copy" that shares its array with the original. A minimax on such a board would write its trial moves into the real game.

The module is src/data/Grid2D.ts.

From earlier steps

• SeededRandom from step 01: picks the computer's opening among the equally good moves, so the same init-seed replays the same games.

The scaffold, the GO logo intro, the start screen and the scaling are explained once in Spielwerk 00: The workbench. "Neue Runde" is a toolbox Button on a UiPage. What this step first wrote by hand for hover from the pointer and the ready status is part of the canvas game shell now; the workbench lists it under "Extracted along the way".

Embed it

<script src="https://www.game-object.de/tce-elements/tobidot/dll-tce-assets"></script>
<script src="https://www.game-object.de/tce-elements/tobidot/tce-tic-tac-toe"></script>
<tce-tic-tac-toe init-seed="4711"></tce-tic-tac-toe>

Next

Previous: Spielwerk 02: Galgenraten · Next: Spielwerk 04: Mastermind · All steps