Tetris AI

While the number of people interested in developing AIs for Tetris is probably around that of the average lunar population, I'll give a quick description of how this AI works on the off chance someone takes up a similar project in the future.

The number of possible moves is very small (less than around thirty at a time) making a bruit force heuristic search easily feasible. The AI operates by creating a collection of possible outcomes (the series of moves and the resulting board). The size of this collection can be reduced a considerable amount by restricting the number of rotations considered for various pieces (such as the square and stick) and using set data structures to remove duplicate outcomes from future considerations. To simplify calculations pieces are rotated, moved, then dropped in that order. This reduces the branching factor but does not take into account the possibility of resolving overhangs (when fallen blocks form an umbrella over an area).

Once the set of possible moves has been determined an exhaustive search is made for the best heuristic. This takes three factors into account:

1. Lines cleared (+50 / line)
2. Buried locations, including overhangs and bubbles (-25 / point)
3. Maximum height of pieces (-10 / line)

While the AI occasionally outperforms human players, the heuristic frequently suffers from a failure I call the "spires problem". When the board has multiple deep holes the computer player refuses to cover them (since this would result in bubbles without immediately clearing lines). This can quickly lead the AI to lose the game as it's unable to clear additional lines. Videos are available showing the AI spiring as well as doing admirably well.