Classic Survival Tetris AI

中文版

Overview

This is an AI implemented by Misakamm. Under the classic Tetris survival rules described below, with no next-piece lookahead, it reaches about 270 million lines cleared on average, making it the first public AI to exceed 100 million lines under this ruleset.

Ruleset

1. The playfield is 10 columns wide and 20 rows high. Other board heights can be used for experiments, but the height must be stated with the results. The maximum playfield height is the top-out line.
2. Each piece is generated by a memoryless linear random generator over the 7 standard tetrominoes. Memoryless means the generated piece is independent of both the piece history and the current board state.
3. Pieces spawn above the playfield, above the top-out line. Existing blocks in the board never block the choice of a horizontal position or rotation state.
4. Only hard drop is allowed. Soft drop and slide-under moves are not allowed.
5. After a piece is locked, if any cell is above the top-out line, the game ends immediately. This top-out check is performed before line clears.
6. There is no next-piece preview. The AI can only use the current piece.

Rotation-System-Free Rules

Under this ruleset, the initial spawn position no longer matters, because horizontal movement cannot be blocked. The initial orientation also does not matter. Since soft drop is not allowed, there is no need to model kicks, spins, or rotation-before-drop behavior to tuck a piece into a position. The AI only needs to evaluate placing a given orientation at a given x coordinate.

For that reason, this document calls it a rotation-system-free ruleset. Under this ruleset, the AI has the smallest set of game mechanics to handle, making it well suited for comparing Tetris AIs. It is also used by many Tetris AI papers.

Scoring

A single game is scored by the total number of cleared lines. For multi-seed statistics, the following values are reported:

• Mean.
• Median.
• Median divided by ln2. For an exponential distribution, this is the theoretical mean. If this value is close to the sample mean, the sample size is likely sufficient. When the sample size is insufficient, this value can be used as a mean estimate.

Random Number Generator

This project uses pcg32_k2_fast from the PCG random number library. It has a 2^128 state space and passes all known randomness tests, which is sufficient for these experiments.

When generating pieces, the 32-bit integers produced by the RNG are treated as a bit stream. Each piece draw consumes 3 bits. If the value is 7, that value is rejected and the next 3 bits are used, until the value falls in [0, 6].

Published Records

Year	Author	Lines cleared
2003	Pierre Dellacherie	5,000,000
2009	Boumaza	35,000,000
2009	Thiery & Scherrer	35,000,000
2013	Victor Gabillon et al.	51,000,000
2026	Misakamm	270,000,000

Notes:

• The values in this table are estimates and omit trailing digits.
• The commonly cited 600,000-line result for Pierre Dellacherie is under the rule where pieces appear inside the top of the playfield. See Colin Fahey's implementation. Under the rules used in this document, Dellacherie's AI reaches around 5 million lines, consistent with the rules used by Thiery & Scherrer. The approximately 5-million-line figure is from the paper by Victor Gabillon et al.
• The Thiery & Scherrer paper includes concrete weights and feature definitions. Under the rotation-system-free ruleset, the original result can be reproduced experimentally; at height 16, the mean is 1,000,000 lines.
• According to the paper by Victor Gabillon et al., their result is 51,000,000 lines, but no verifiable source code is available.
• For a broader overview, see The Game of Tetris in Machine Learning.

Version History

• V1.0: record was 120,000,000.
• V2.0: fixed cross-platform RNG inconsistency, adjusted weights, and improved the record to 270,000,000.

AI Evaluation

Weights

• row_transitions = 100
• column_transitions = 95
• hole = 401
• landing_height = 67
• rows_cleared = 86
• well_depth_2 = 176
• well_depth_3 = 99
• x1_hole = 88
• x2_hole = 88
• hole_depth = 75
• shape_adaptability = 117

Note: in the source code, row_transitions is hard-coded as a constant. column_transitions is named vertical. The other weight names match the source code.

Feature Definitions

The following features match Pierre Dellacherie's algorithm:

• row_transitions: a penalty feature. Counts transitions in each row. The row starts and ends with a non-zero sentinel, so both horizontal boundaries are treated as filled cells.
• column_transitions: a penalty feature. Counts transitions in each column from top to bottom. The column starts with a zero sentinel and ends with a non-zero sentinel, so the top boundary is treated as empty and the bottom boundary is treated as filled.
• hole: a penalty feature. Counts the number of holes.

Other features:

• landing_height: a reward feature. After the piece is placed, compute the average distance from the top of the playfield for the 4 cells of the placed piece.
• rows_cleared: a reward feature. Counts the number of line clears.
• well_depth_2: a penalty feature. If a column is lower than both adjacent columns, let h be the smaller of the two side height differences. If h is 1, the value is well_depth_2 / 5; if h is 2, the value is well_depth_2; if h >= 3, the value is well_depth_3 + (h - 2) * hole, where hole depends on the x coordinate and is the hole penalty for that column. For example, at the leftmost or rightmost wall, the value is hole + x0_hole. Then compute the sum of all well values as sum and the largest single-well value as max; the final value is sum * 2 - max.
• x1_hole: a penalty feature. Adds an extra penalty if a hole is in a column one cell away from the left or right wall. Similarly, there are x0_hole and x2_hole: x0_hole is fixed to 1.5 * x1_hole and applies to the leftmost or rightmost wall column; x2_hole applies to columns two cells away from the wall.
• hole_depth: a penalty feature. Find the highest hole and return the height of its column. If multiple highest holes tie, return the maximum column height among those holes.
• shape_adaptability: a reward feature. This is the most complex feature. It scans every consecutive pair and triple of columns. For example, heights 3, 2, 3 match a T placement and add 1 to the match count for T. Heights 3, 3, 3 match the upside-down T orientation, as well as flat L and J placements, so this 3-column pattern adds 1 to each of those three tetrominoes. For each tetromino, the match count is clamped from 0 to 2; values greater than 2 are treated as 2. The score table is 0, 4, 6, so no match gives 0 points and one match gives 4 points. The I piece is excluded. The remaining 6 tetrominoes are scored and averaged. For rotation-symmetric tetrominoes such as SZO, duplicate orientations are not counted twice.

AI Results

Distribution

Based on tens of thousands of simulated games, the line-clear count at a fixed board height follows an exponential distribution. Therefore, at least 300 samples are needed to reach 95% confidence with the mean error below 10%.

Detailed Height-20 Results, Width 10

At height 20, 200 seeds were run, using seeds 20000-20199:

Seed	Lines	Lines	Lines	Lines
20000-20003	317,118,282	434,718,708	66,832,583	281,978,049
20004-20007	256,912,801	310,407,339	929,234,180	1,016,849
20008-20011	265,098,050	85,388,679	552,604,612	6,220,383
20012-20015	116,674,246	181,451,102	416,899,008	278,197,716
20016-20019	102,479,853	301,566,407	218,785,700	127,780,063
20020-20023	53,232,791	24,334,594	5,605,536	25,301,778
20024-20027	77,831,990	79,938,070	34,859,749	338,647,362
20028-20031	72,528,592	143,484,995	18,716,634	224,524,548
20032-20035	200,660,472	383,959,875	382,844,843	174,203,522
20036-20039	643,741,636	349,059,612	472,341,629	498,005,976
20040-20043	375,212,414	144,914,225	1,225,848,655	194,238,156
20044-20047	40,638,230	115,450,578	238,005,856	465,819,585
20048-20051	27,316,587	346,341,144	363,938,540	56,409,992
20052-20055	253,814,079	1,098,449,932	9,161,635	222,500,717
20056-20059	130,407,358	19,127,541	111,005,164	11,321,606
20060-20063	765,893	172,521,137	163,580,314	161,244,801
20064-20067	82,554,014	172,679,424	84,592,129	92,410,994
20068-20071	329,787,416	65,798,012	87,664,091	652,936,929
20072-20075	474,702,224	241,827,190	2,471,215,820	47,537,514
20076-20079	194,805,779	3,495,668	11,172,184	206,284,849
20080-20083	115,686,918	602,392,552	186,664,808	94,006,114
20084-20087	409,275,490	227,905,966	462,929,096	13,960,901
20088-20091	190,151,822	460,817,598	101,526,494	235,359,646
20092-20095	79,044,098	342,815,685	327,747,150	162,628,533
20096-20099	632,568,723	342,170,724	33,582,673	89,084,682
20100-20103	108,402,472	4,768,764	152,555,974	60,181,326
20104-20107	413,028,131	451,153,453	555,084,954	56,412,783
20108-20111	488,612,165	284,810,382	145,994,967	1,045,202,271
20112-20115	1,250,510,113	120,565,729	51,381,899	54,927,219
20116-20119	152,984,775	248,308,795	730,311,137	108,392,573
20120-20123	345,614,040	240,765,208	230,972,796	10,434,127
20124-20127	350,176,937	20,956,150	278,298,996	64,594,533
20128-20131	92,072,740	313,083,141	77,710,870	56,530,912
20132-20135	58,378,528	798,368,306	305,649,769	160,975,053
20136-20139	28,388,405	96,390,499	142,144,451	274,342,849
20140-20143	1,093,183,095	264,200,796	446,978,586	95,385,274
20144-20147	234,469,087	145,930,086	1,136,632	41,229,193
20148-20151	18,825,496	539,612,747	212,875,674	500,919,059
20152-20155	1,135,078,012	97,289,611	293,322,110	319,695,682
20156-20159	581,661,719	304,036,050	441,441,112	526,764,876
20160-20163	33,062,955	139,578,781	59,326,174	65,906,950
20164-20167	553,529	582,370,193	205,829,867	223,264,930
20168-20171	78,959,533	507,960,693	19,274,665	349,349,924
20172-20175	161,883,174	8,596,833	150,640,354	111,703,345
20176-20179	487,051,799	167,816,721	504,801,536	546,192,899
20180-20183	847,994,219	64,498,692	526,510,376	460,098,515
20184-20187	250,941,878	119,532,119	3,618,046	163,143,075
20188-20191	17,970,964	23,393,133	472,868,439	296,631,381
20192-20195	66,985,595	305,189,420	222,943,509	695,587,761
20196-20199	1,019,243,979	33,404,479	292,332,670	173,253,169

Statistics over the 200 seeds above:

• Mean: 269,583,731.13
• Median: 188,408,315.0
• Median / ln2: 271,815,741.71

Statistics by Board Height

Height	Avg	Median	Median/ln2
5	26.85	18.0	25.97
6	90.07	65.5	94.50
7	272.31	182.0	262.57
8	825.20	573.5	827.39
9	2,670.43	1,791.0	2,583.87
10	7,519.81	4,942.5	7,130.52
11	21,551.13	15,461.5	22,306.23
12	68,485.57	46,994.5	67,798.73
13	196,402.45	137,416.0	198,249.38
14	577,329.26	408,859.0	589,858.85
15	1,713,508.46	1,196,521.5	1,726,215.63
16	4,814,532.13	3,327,912.5	4,801,162.86
17	12,649,009.52	9,280,883.0	13,389,483.88

Notes:

Height 5 uses seeds 5000 to 5999, height 6 uses seeds 6000 to 6999, and so on.

Since the logarithm is not linearly increasing, I use a log-quadratic model: ln(f(h)) = a + b*h + c*h^2. The fitted parameters are a, b, and c.

Fit predictions, using height 5 through height 17. Each of those heights uses 1000 seeds, so all are included:

Height	Avg	Median	Median / ln2
18	36515278.30	26620120.38	38404715.66
19	100457853.25	74277460.35	107159723.70
20	273537447.00	205418770.34	296356641.28

The Median / ln2 column is derived directly from the fitted median, not fitted independently. The fit differs from the measured results, but is broadly consistent.

Therefore, at height 20, the mean line-clear count is about 270 million. This record should be stable.

Reproducing the Results

This project includes the complete C++ implementation needed to reproduce the results. The metric is also simple enough that the implementation can be rewritten independently to verify the result.

An AI demo page is also available.

Build and Run

make
./run_simple_ai --rows 10 --seed 6

Example output:

pieces=30204 lines=12073

This means that on a 10-row by 10-column board, using random seed 6, the AI placed 30204 pieces and cleared 12073 lines. To collect multi-seed statistics, implement a small Python script that invokes this command in multiple processes.

Training Method and Compute Cost

The AI weights were optimized with the Cross Entropy (CE) Method. The optimization used 20 samples, each sample ran 100 games, each game was a complete height-13 game, and optimization ran for 100 iterations. The upper bound on total compute is:

20 * 200000 * 100 * 100 = 40,000,000,000 lines

The 200000 term is the average number of cleared lines. On my machine (MacBook M1), one core can simulate about 360 million lines per hour. Therefore the total single-core compute time is about 110 hours, or just under 5 days.

Single-Game Evaluation During Training

The final line-clear count lines is used as the single-game score.

Multi-Game Scoring

For multiple single-game scores, sort the scores, remove the top and bottom 1/3, and average the remaining scores as the final candidate score.

Reference

Archived old blog post