Sections

 Home
 Dev Log
 Resume
 Free Media
 Riddles
 Bob's Gallery
 Links & Resources
 Contact


Projects

 Stem
 Arm
 Kana Quizzer
 Keybinding Util
 Model Gallery
 Applets
 Nexus


Applets

 Contents
 Mr. Jelly 2D
 Mr. Jelly 3D
 Toroidal Spirals
 3D Tetris
     Tetris AI
 Bullies
     Bullies AI


Tetris AI

AI Evaluation

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.

back