Programming has been a lifelong passion for me. So much that by now everything feels very familiar and I can almost predict the solutions before seeing them – except for those rare cases when something genuinely new comes up. These instances happen once in a blue moon, but there’s always that tingling feeling that reminds you why you’re doing this for a living – like when you see infinity emerge from simple arithmetic in a Mandelbrot fractal, or understand that the humble dot product can somehow simulate perspective and make a 3D cube appear on a 2D pixel canvas.

I don’t think I need to explain Tetris – I’m sure everyone who’s played this classic game knows the drill. What I would like to mention is how often I’ve built this particular thing: there must be at least half a dozen implementations of mine floating around. And it’s not even difficult anymore – it’s practically muscle memory.

This is why, on one particularly sluggish day, the question of whether I could create an AI to play Tetris popped in my head. I’m not entirely sure where this idea came from: although I had done my share of AI development in the past (for instance, I’d implemented A* pathing algorithm for a Snake AI for another 404 page), this was a whole other level of complexity. While Snake was still just another graph problem, Tetris required a significantly different approach.

I kept thinking about this idea – and that’s how I came across a paper written by Pierre Dellacherie in 2003, which introduced a radically different way of approaching this problem. All it took was this paper for me to transform this idea into a couple hours of coffee fuelled playing around.

And now, this project has become the 404 page for a website – an AI-powered Tetris clone, implemented entirely in vanilla JS (a language I really don’t get along with) and using only monospace font for rendering (who needs sprites). In what follows, I’m going to describe the technicalities behind it all.

Note: it’s probably done badly, but it was a mental exercise more than anything else.

Why Tetris, and why text?

A 404 page serves solely as an acknowledgment of the error, with a means of escaping; everything else is atmosphere (or lack thereof). Because Tetris is near universally identifiable due to shape and motion, it immediately appears to be interesting rather than broken. The AI component provides another layer: visitors can watch the computer play Tetris and wonder how long the game can last, resulting in an extended visit. Or watching it for an 45 minutes to make sure it didn’t break.

The monospaced text renderer was a purposeful design constraint. By using the block character, █, inside of a <span> tag with per-character coloured spans, there are no dependencies, no use of the canvas API, and the visual style has a retro aesthetic (purposefully) versus an accidentally plain style. The board itself is simply a loop that builds an HTML string – easy to conceptualise and easy to modify.

The board

Playing field dimensions are 10 × 20; this can be stored using a 2D array of the JavaScript language. A cell can either be null or some CSS colour, such as #00e5ff. The use of the colour and null as the single value will suffice since null will evaluate to false, while all colours will be truthy.

// 20 rows × 10 columns, all empty at start
board = Array.from({ length: H }, () => Array(W).fill(null));

Deletion of completed rows is done using a loop starting from the bottom moving upwards and deleting any row for which all cells are non-empty. In addition, an empty row is inserted on the top of the table. The index is incremented to ensure the same position is checked after splicing.

for (let r = H - 1; r >= 0; r--) {
  if (board[r].every(v => v)) {
    board.splice(r, 1);
    board.unshift(Array(W).fill(null));
    cl++;
    r++; // re-check: the row that fell into r might also be full
  }
}

Tetromino representation

Each of the seven tetrominoes is represented by a colour and a set of rotations. Each rotation is just a list of offsets [col, row], where offsets are from a particular point. Moving a tetromino to the board then involves adding its coordinates (x, y) to the offsets.

// T-piece: four rotations, each a list of four [col, row] offsets
{ c: '#d500f9', r: [
  [[1,0],[0,1],[1,1],[2,1]],  // stem up    ·#·  →  ###
  [[0,0],[0,1],[1,1],[0,2]],  // stem right
  [[0,0],[1,0],[2,0],[1,1]],  // stem down
  [[1,0],[0,1],[1,1],[1,2]]   // stem left
]}

The seven pieces and their colours are:

The 7-bag randomiser

The Tetris game itself doesn’t just randomly select each piece. Random selection results in sequences where one shape doesn’t show up for ages or keeps showing up again and again in rapid succession. Rather, it employs a system called the 7-bag algorithm, which means that all seven shapes are mixed up in a bag and then dealt out one by one until the bag is used up. This ensures that there’s a set of 14 shapes containing all seven types of pieces in any stretch.

function refillBag() {
  const a = [0, 1, 2, 3, 4, 5, 6];
  // Fisher-Yates shuffle
  for (let i = 6; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  bag.push(...a);
}

The AI

This is when the algorithm lives up to its name. The decision process follows the method that was introduced by Pierre Dellacherie in 2003, one of the most analyzed single-perspective lookahead techniques for Tetris.

The idea is quite simple: take all the possible orientations and placements of the current piece, and estimate how well the piece will fit into the grid when falling from that placement using some evaluation function. No training is needed; there are no artificial neural networks here, only four particular field properties and their coefficients.

The scoring function

This evaluation includes four characteristics associated with the new state of the board:

Aggregated height : the summation of the tallest cell occupied in each column. A smooth and low board is easier to deal with compared to a high and ragged one. This characteristic is penalised.

Rows cleaned : the number of entire rows cleared out by the new piece. The more lines are cleared, the better the result. This is the only non-penalised characteristic.

Holes : empty cells that have at least one occupied cell above them in the same column. Holes are hidden killers in Tetris; they can be revealed only by clearing all rows above them. This characteristic is penalised the most.

Roughness : the summation of the difference of height between any two adjacent columns. A ragged skyline makes filling it hard; therefore, this characteristic is also penalised, but not as heavily as holes.

These weights were derived by Dellacherie and were later reproduced and validated. The AI, though not perfect, does not plan further than the next move and thus cannot plan two moves ahead, but its play style is good enough to last long enough without filling the board. This is precisely the behaviour needed for a background filler.

The search

For each type of piece, the number of different possible valid placements is low: no more than 4 rotations x 10 columns = 40 possible placements, less those that cannot be placed due to the present state of the board. The complete search takes microseconds.

function decide(type) {
  let best = -Infinity, bRot = 0, bX = 3;

  for (let rot = 0; rot < TETROS[type].r.length; rot++) {
    const cs   = TETROS[type].r[rot];
    const minC = Math.min(...cs.map(([c]) => c));
    const maxC = Math.max(...cs.map(([c]) => c));

    for (let x = -minC; x <= W - 1 - maxC; x++) {
      if (!valid(board, type, rot, x, 0)) continue;
      const res = simulate(type, rot, x);
      if (!res) continue;
      const s = evalBoard(res.b, res.cl);
      if (s > best) { best = s; bRot = rot; bX = x; }
    }
  }
  return { rot: bRot, x: bX };
}

The range of values for x is computed based on the bounding box of the piece itself to ensure that no test position is ever beyond the walls of the playfield. The value of minC is required to handle pieces with an offset from column 0 in their leftmost cells.

Simulation

The limits for the values of x are derived using the dimensions of the bounding box of the current piece so that the simulated drop does not go outside the boundaries of the playing field. The calculation of the minimum value for C becomes necessary due to cases where the pieces do not start at column 0.

The simulate function uses gravity to move the piece from row 0 to its final resting place, removing any lines formed and returning the resultant board and the number of lines removed. However, changes to the live game board are made only during calls to lock() once the piece has landed.

function simulate(type, rot, x) {
  let y = -1;
  while (valid(board, type, rot, x, y + 1)) y++;
  if (y < 0) return null; // blocked at spawn row — discard

  const b = board.map(row => [...row]); // shallow clone is enough
  cells(type, rot, x, y).forEach(([c, r]) => { if (r >= 0) b[r][c] = col; });
  // ... clear lines, count cleared ...
  return { b, cl };
}

While cloning the board for each candidate seems like it would be very costly, a 10 × 20 grid of small strings is really small. Even on an older computer processor, computing all 40 clone candidates, drops, and evaluations only takes less than a millisecond, freeing the web page for a full frame period. Look, I was brought up on 8 and 16 bit machines where the vertical blank interrupt was a real challenge, so speed matters ok?

The game loop

There are only two stages within this loop: fall and lock. When a new piece comes into play, the AI chooses the rotation and column immediately, with no animation of sliding. It then begins falling downwards by one row with a setTimeout callback interval until it can’t fall any more, at which point it locks onto the board.

function spawn() {
  cur = { t: nextType, rot: 0, x: 3, y: 0 };

  // AI decides — piece jumps to target position immediately
  const { rot, x } = decide(cur.t);
  cur.rot = rot;
  cur.x   = x;

  tid = setTimeout(doFall, fallSpeed());
}

function doFall() {
  if (valid(board, cur.t, cur.rot, cur.x, cur.y + 1)) {
    cur.y++;
    render();
    tid = setTimeout(doFall, fallSpeed());
  } else {
    lock();
    setTimeout(spawn, 120);
  }
}

Fall times begin from 180 ms, reducing in 12ms increments down to 28 ms (approximately 35 lines per second). The 120 ms delay between pieces provides sufficient time for locking recognition before the appearance of the next piece.

A game-over condition is achieved when a new piece cannot be placed on the board from the start of its fall time. A 2.2 seconds freezing period followed by resetting the board will reset the AI process.

Rendering

A new HTML string has been generated for every tick, containing one per cell with the cell colour rendered in an inline style attribute and separated by new lines in a element.Batch of cells that are filled will have a “█”, whereas empty cells will have a “·” represented in a darker shade than white.The last character in each cell gives the cell its width by creating a blank space between characters which provides an even amount of space between characters across all columns relative to their heights.

for (let r = 0; r < H; r++) {
  for (let c = 0; c < W; c++) {
    const cl = display[r][c];
    h += cl
      ? `<span style="color:${cl}">█ </span>`
      : `<span style="color:${EC}">· </span>`;
  }
  if (r < H - 1) h += '\n';
}
document.getElementById('bp').innerHTML = h;

Active is copied into a shallow copy of the board prior to the render, hence the live board array will always contain only locked pieces. This provides a nice abstraction layer where decide is not dependent on if the currently active piece is part of the board.

Updating the innerHTML property for each tick entails recreating around 200 DOM elements; however, doing that is not as inefficient as only updating the relevant cells. Since a 404 page only has to update once every 28 to 180 ms, this is absolutely fine.

What the AI gets wrong – and why that is fine

One known problem with single-piece lookahead is its inability to recognise “setup” moves, where taking a minor hit now results in a major advantage two or three pieces down the line. The traditional example is the “I-piece well”: purposefully leaving a single-column gap on the right-hand side to enable a vertical I-piece to clear four rows at once. Single-piece lookahead AI will usually fill such a gap since it prefers a flat surface as more optimal in the immediate future.

The use of two-piece lookahead with 7-bag distribution resolves this issue. Even the less complex algorithm presented in this paper will usually last for several hundred pieces until losing, far enough for an unmonitored background application. Suboptimal AI behaviour is actually desired here: idealistic AI that never loses will inevitably result in a board filled with cleared lines and nothing left to see, while occasional mistakes that get corrected later make for a more dynamic spectacle.

The complete source is a single self-contained HTML file with no dependencies. The playing field, the AI, and the 404 message are all in one place, which makes it easy to drop into any web server as a static file or easily added to a content management system.

See it running →