Type Level Tic-Tac-Toe

The TypeScript type system is honestly pretty straightforward on the surface, but it’s also Turing Complete. I mean the type system itself, not TypeScript as a whole. That means the TS type system can do anything a proper “programming language” can do. I say “programming language” in quotes, because today, we’re programming with the type system!

Like the title says, we’re making a Tic-Tac-Toe game with just the type system. The result will be a game that runs entirely on the type system and produces zero runtime code[1].

Why Do This?

Fair question! Beyond just being a fun brain exercise, messing around with type-level programming teaches you how the type system works under the hood and maybe pickup some patterns you can use in real-world apps.

Plus, if you can build Tic-Tac-Toe in types, you can probably figure out how to validate your API responses or build some wild form validation logic.

Core Concepts

Let’s establish a few basics that we’ll be using:

Supertypes and Subtypes

The TypeScript type system has subsets and supersets within types. For example:

  • the type 1 is a subset of the type number, so is 1 | 2 | 3
  • similarly, the boolean type is a superset with two subtypes true and false

Generics as Functions

We will be using generic types like functions in a traditional programming language. They accept inputs and return outputs, much like functions, but on a type level. We’ll be using these a lot.

type Identity<T> = T;
type Result = Identity<string>; // Result is string;

Tuples and Indexed Access

Tuples are fixed size arrays, and we can access elements in a tuple/array with the bracket notation, like we do in JS.

type Tup = [number, string, boolean];
type Result1 = Tup[0]; // Result1 is number
type Result2 = Tup[number]; // Result2 is number | string | boolean

It works similarly with array types too.

type Arr = string[];
type Result = Arr[number]; // Result is string

The extends Keyword

The extends keyword can be used in two different ways.

  1. One is as a type constraint, like in SomeType<T extends string>. This just means that the types passed as T have to be assignable to the types string.

  2. The second way is in a conditional, like in U extends V ? A : B. This is going to evaluate to the type A is the type U can be assignable to V, and B if it can’t. Like a ternary expression.

The seconds one is largely how we will be able to write logic in the TypeScript type system.

Immutability

Unlike the JavaScript code we usually compile TypeScript to, there are no mutable variables in the TypeScript type system, meaning we can’t assign a value to a variable and update it later.

The Code

With all that out of the way, let’s get started.

The Base Types

We’ll start with some base types.
First, the players

type PlayerX = "X";
type PlayerO = "O";

type Player = PlayerX | PlayerO;

And every cell can have either a player, or can be blank.

type Cell = Player | " ";

A Row is a tuple of three cells(Tuples are just fixed size arrays)

type Row = [Cell, Cell, Cell];

And a board is a tuple of three rows

type Board = [Row, Row, Row];

Detecting a Win

Now we’re getting to the good part, the logic for checking who won the board. A player wins when they satisfy one of the following conditions:

  • The player has filled all the cells in a row
  • The player has filled all the cells in a column
  • The player has filled all the cells on either diagonal

Let’s start with the easiest one, checking along a row.

Checking the Rows

type CheckRowWinForPlayer<R extends Row, P extends Player> = R[0] extends P
  ? R[1] extends P
    ? R[2] extends P
      ? true
      : false
    : false
  : false;

Remember when I said that generics are like functions? This is the first example and we’re just getting started.

In the above snippet, we define a generic type, CheckRowWinForPlayer, that takes two parameters, a Row , R and a Player , P, and checks if all three cells in R is P. If they are, it evaluates to true, if not, false. Keep in mind that true and false are largely arbitrary here, we can also use 1 and 2 or 'a' and 'b'. We just need two distinct values. I’m just going to use true and false to keep things simple.

We’ll just write one more generic to figure out which player won for a row. It’s just a wrapper on the previous generic.

type CheckRowWin<R extends Row> =
  CheckRowWinForPlayer<R, PlayerX> extends true
    ? PlayerX
    : CheckRowWinForPlayer<R, PlayerO> extends true
      ? PlayerO
      : never;

This should be a bit easier to follow- we call CheckRowWinForPlayer on the row, for each player and if they evaluate to true, return that player.

As you might have noticed, we’re going to write a lot of conditionals like these, so let’s make an If generic that abstracts that away.

type If<Condition extends boolean, TrueExpr, FalseExpr> = Condition extends true
  ? TrueExpr
  : FalseExpr;

And we’ll refactor CheckRowWin to use If.

type CheckRowWin<R extends Row> = If<
  CheckRowWinForPlayer<R, PlayerX>,
  PlayerX,
  If<CheckRowWinForPlayer<R, PlayerO>, PlayerO, never>
>;

Checking the Columns

Now, we’ll move on to the column checks, it’s a tiny bit more complicated since we need to check the same index across all the rows,so we need access to the whole board. Still, it’s pretty straight forward.

type Columns = 0 | 1 | 2;

type CheckColWinForPlayer<
  B extends Board,
  Col extends Columns,
  P extends Player,
> = B[0][Col] extends P
  ? B[1][Col] extends P
    ? B[2][Col] extends P
      ? true
      : false
    : false
  : false;

type CheckColWin<B extends Board, Col extends Columns> = If<
  CheckColWinForPlayer<B, Col, PlayerX>,
  PlayerX,
  If<CheckColWinForPlayer<B, Col, PlayerO>, PlayerO, never>
>;

Pretty similar to the logic for the rows, we just have another parameter for the column index. Columns is just a type for the valid column indexes.

Next up, the diagonals

Checking the Diagonals

type CheckLeadingDiagonalWinForPlayer<
  B extends Board,
  P extends Player,
> = B[0][0] extends P
  ? B[1][1] extends P
    ? B[2][2] extends P
      ? true
      : false
    : false
  : false;

type CheckAntiDiagonalWinForPlayer<
  B extends Board,
  P extends Player,
> = B[0][2] extends P
  ? B[1][1] extends P
    ? B[2][0] extends P
      ? true
      : false
    : false
  : false;

type CheckDiagonalWinForPlayer<B extends Board, P extends Player> = If<
  CheckLeadingDiagonalWinForPlayer<B, P>,
  true,
  If<CheckAntiDiagonalWinForPlayer<B, P>, true, false>
>;

Again, pretty straightforward, we just have a check for each diagonal.

Next up, we’ll add some more generics to check if anyone has won on any row, column, or diagonal.

Combining the Checks and Getting the Winner

type CheckAnyDiagonalWin<B extends Board> = If<
  CheckDiagonalWinForPlayer<B, PlayerX>,
  PlayerX,
  If<CheckDiagonalWinForPlayer<B, PlayerO>, PlayerO, never>
>;

type CheckAnyRowWin<B extends Board> =
  CheckRowWin<B[0]> extends never
    ? CheckRowWin<B[1]> extends never
      ? CheckRowWin<B[2]> extends never
        ? never
        : CheckRowWin<B[2]>
      : CheckRowWin<B[1]>
    : CheckRowWin<B[0]>;

type CheckAnyColWin<B extends Board> =
  CheckColWin<B, 0> extends never
    ? CheckColWin<B, 1> extends never
      ? CheckColWin<B, 2> extends never
        ? never
        : CheckColWin<B, 2>
      : CheckColWin<B, 1>
    : CheckColWin<B, 0>;

And finally, a GetWinner generic to get the winner, if there is one, for a board.

type GetWinner<B extends Board> =
  CheckAnyRowWin<B> extends never
    ? CheckAnyColWin<B> extends never
      ? CheckAnyDiagonalWin<B> extends never
        ? never
        : CheckAnyDiagonalWin<B>
      : CheckAnyColWin<B>
    : CheckAnyRowWin<B>;

And that’s it! You have a functioning Tic-Tac-Toe game using just the TypeScript type system and it compiles to nothing.

Testing the Game

type Winner1 = GetWinner<
  // ^? type Winner1 = "X"
  [["X", "O", " "], ["X", "X", " "], ["O", "O", "X"]]
>;

type Winner2 = GetWinner<
  // ^? type Winner1 = "X"
  [["X", "O", "O"], ["X", "O", " "], ["X", "O", "X"]]
>;

type Winner3 = GetWinner<
  // ^? type Winner1 = "X"
  [["X", "X", "X"], ["O", "O", " "], ["O", "O", "X"]]
>;

type Winner4 = GetWinner<
  // ^? type Winner1 = never
  [["X", " ", "X"], ["O", " ", " "], ["O", "O", "X"]]
>;

The Complete Implementation

Here’s the complete code, and you can can experiment with this implementation in the TypeScript Playground.

type PlayerX = "X";
type PlayerO = "O";
type Player = PlayerX | PlayerO;
type Cell = Player | " ";

type Columns = 0 | 1 | 2;

type Row = [Cell, Cell, Cell];

type Board = [Row, Row, Row];

type If<Condition extends boolean, TrueExpr, FalseExpr> = Condition extends true
  ? TrueExpr
  : FalseExpr;

type CheckRowWinForPlayer<R extends Row, P extends Player> = R[0] extends P
  ? R[1] extends P
    ? R[2] extends P
      ? true
      : false
    : false
  : false;

type CheckRowWin<R extends Row> = If<
  CheckRowWinForPlayer<R, PlayerX>,
  PlayerX,
  If<CheckRowWinForPlayer<R, PlayerO>, PlayerO, never>
>;

type CheckColWinForPlayer<
  B extends Board,
  Col extends Columns,
  P extends Player,
> = B[0][Col] extends P
  ? B[1][Col] extends P
    ? B[2][Col] extends P
      ? true
      : false
    : false
  : false;

type CheckColWin<B extends Board, Col extends Columns> = If<
  CheckColWinForPlayer<B, Col, PlayerX>,
  PlayerX,
  If<CheckColWinForPlayer<B, Col, PlayerO>, PlayerO, never>
>;

type CheckLeadingDiagonalWinForPlayer<
  B extends Board,
  P extends Player,
> = B[0][0] extends P
  ? B[1][1] extends P
    ? B[2][2] extends P
      ? true
      : false
    : false
  : false;

type CheckAntiDiagonalWinForPlayer<
  B extends Board,
  P extends Player,
> = B[0][2] extends P
  ? B[1][1] extends P
    ? B[2][0] extends P
      ? true
      : false
    : false
  : false;

type CheckDiagonalWinForPlayer<B extends Board, P extends Player> = If<
  CheckLeadingDiagonalWinForPlayer<B, P>,
  true,
  If<CheckAntiDiagonalWinForPlayer<B, P>, true, false>
>;

type CheckAnyDiagonalWin<B extends Board> = If<
  CheckDiagonalWinForPlayer<B, PlayerX>,
  PlayerX,
  If<CheckDiagonalWinForPlayer<B, PlayerO>, PlayerO, never>
>;

type CheckAnyRowWin<B extends Board> =
  CheckRowWin<B[0]> extends never
    ? CheckRowWin<B[1]> extends never
      ? CheckRowWin<B[2]> extends never
        ? never
        : CheckRowWin<B[2]>
      : CheckRowWin<B[1]>
    : CheckRowWin<B[0]>;

type CheckAnyColWin<B extends Board> =
  CheckColWin<B, 0> extends never
    ? CheckColWin<B, 1> extends never
      ? CheckColWin<B, 2> extends never
        ? never
        : CheckColWin<B, 2>
      : CheckColWin<B, 1>
    : CheckColWin<B, 0>;

type GetWinner<B extends Board> =
  CheckAnyRowWin<B> extends never
    ? CheckAnyColWin<B> extends never
      ? CheckAnyDiagonalWin<B> extends never
        ? never
        : CheckAnyDiagonalWin<B>
      : CheckAnyColWin<B>
    : CheckAnyRowWin<B>;

type Winner = GetWinner<[["X", "O", " "], ["X", "X", " "], ["O", "O", "X"]]>;

type Winner2 = GetWinner<[["X", "O", "O"], ["X", "O", " "], ["X", "O", "X"]]>;

type Winner3 = GetWinner<[["X", "X", "X"], ["O", "O", " "], ["O", "O", "X"]]>;

type Winner4 = GetWinner<[["X", " ", "X"], ["O", " ", " "], ["O", "O", "X"]]>;

What’s Next?

This is just a simple implementation. You can try adding stuff like:

  • Board validation
  • Keeping track of the current player
  • Tie detection
  • Maybe ASCII image generation of the board state

Real Talk

Should you do this in production code? No. Definitely no. Something like this is hard to read and maintain, slow, and frankly unnecessary. But the next time you think something is not possible with TypeScript, just remember that it might be.

  1. You might have a “use strict” in the compiled code depending on your tsconfig. ↩︎