Tetris AI: God's Algorithm

[farter]

traditional tetris AI
this post is all about.. say (traditional (tetris AI)), or say ((traditional tetris) AI).
the goal is to clear most lines before game-over (assuming tested by infinite number of games, i.e. maximize the expected lineclear).
there's no preview piece, no hold, you get the next piece once you lock the current piece.
the next piece is generated by an ideal linear randomizer, choosing one of seven tetrominos (ITOSZJL) with equal possibility.

rules
for simplicity and some other reason for this algorithm, the detailed rules are described as follows:

• space above the visible matrix is considered empty
• a game is over when a piece locks partially/wholly outside the visible matrix
• pieces spawn where it's high enough to prevent any collision with locked minos (without softdropping)

some misc. things:

• lineclear judgement first or game-over judgement first? - to let something easier to explain, i choose game-over first in this post.
• softdrop? spins and twists? wallkick? - simply disallowing softdrop makes the result irrelevant to the offsets of pieces in their 4 directions (or say, rotation system). but yeah, allowing them means definitely higher score. for simplicity, those moves are all prohibited.

so... seems current tetris AIs are all just struggling for "fairly good" strategies, which can be run with reasonable space and time complexity.

the algorithm
these days i came up with one which might be the optimal algorithm, however for now, it needs exponential space.. say for 10*20 playfield, it needs 2^(10*20) numeric storage unit on theory.....
well for coders you might already know what i want to say..
but at least it's runnable for a 4*4 playfield!  

ok so let me start...

we assume "score" is equivalent to "lines cleared".
definations:
a matrix's expected score: starting from this matrix, how many lines more can be cleared, expectedly.
a game-over game state's expected score is 0.

the best choice for a piece entering a matrix is:
for P in "all possible landing position", find the one with maximized ("lineclear of P" + "expected score of the resulting matrix")

if the piece must cause game-over, there's no best choice, but the expected score is determined: 0.

a matrix's expected score is equal to the arithmetic mean of each of the 7 tetrominos' best choices' expected score entering this matrix.

at last, god's score on tetris is the expected score of an empty matrix.

some simple examples for understanding (4*4 matrix)
[spoiler]
below, "expected score" is shortened to ES...
examples below may be unreachable starting from an empty matrix and playing regularly (number of cells is not times of 4, etc.). they are just for explanation.

Code Select Expand


[][][]..
..[][][]
[][][]..
[][][]..

this matrix's ES is also 0, because any following piece causes death.
note that game-over is judged before line clears.

Code Select Expand


[][][]..
[][][]..
[][][]..
[][][]..

this matrix's expected score is:
(4 + "ES of a 4*4 empty matrix")/7
only I prevents death, and it clears 4 lines.

Code Select Expand


........
[][][]..
[]....[]
[]....[]

this one is a bit more complicated.
an I clears one line and keeps the matrix unchanged, a J clears one line and mirrors the matrix.
it can be easily seen that under the rule specified at first, symmetric matrices will have same ES value.
let X be the ES value of this matrix, lemme have a linear equation:
X = ((1+X) + (1+X))/7
the solution is X=2/5=0.4, this is the exact ES of this matrix.

Code Select Expand


........
..[][]..
[]....[]
[]....[]

somehow simpler but somehow deeper.
J and L don't lead to sudden death but both resulting matrices will accept no more piece.
an I still makes 1 line and nothing. so:
X = (1+X)/7, X= 1/6.
[/spoiler]

thus, for a X*Y matrix, you have to store nearly 2^(X*Y) ES values for each possible matrix...
though most of them are extremely hard to reach unless you are doing tetromino art but not survival.
and how to cut the "rarely needed" matrices is also an interesting problem. early approaches includes "disallowing holes" (2^200 -> 20^10), etc.

EDIT: run a reasonable AI, and for each piece, pick the best N(1,2,3,?) choices as "possible" choice and results a "possibly good" matrix, and span the whole searching space this way. might be still too big for 10*20, but should work fine for smaller sized ones.

if each tetromino's best choice for one matrix is determined, that matrix's ES value is determined. but i can't prove that there won't be recursive dependencies...

however, to get approximated value, iteration and simulation algorithms can also be used.

 as always, suggestions, improvements and more ideas please

[PuYoTetris]

我想听屁大爷唱歌[发呆]    By T.198
 

   


this is kidding message

[UJS3]

Cool! One point about the goal you set. When you say "the goal is to clear most lines before game-over", I guess you mean you're maximizing the expected number of lines cleared. If the goal is, for example, to beat a previously set highscore, this isn't necessarily the best approach. There may be lines of play with poorer expected line clears but a higher chance for exceptionally high outliers.

For those simple cases it's a really elegant way to compute the ES, I did the last one explicitly (calculating the expected number of I-pieces you get in a row), much more work.

[Extruderx]

http://www.ryanheise.com/tetris/tetris_art...telligence.html

95% chance that you have seen it already, but it's still there for others. Good luck with your research!

[farter]

For those simple cases it's a really elegant way to compute the ES, I did the last one explicitly (calculating the expected number of I-pieces you get in a row), much more work.

yeah because the last two only involve themselves, it can be solved with one linear equation. but then for slightly lower cases, many other matrices will be involved and their ES must be all determined to calculate the current one's. i guess it will be giant systems of linear equations to solve for the exact value...

[farter]

http://www.ryanheise.com/tetris/tetris_art...telligence.html

95% chance that you have seen it already, but it's still there for others. Good luck with your research!

thanks and yes i have seen that years ago, also played around in nullpomino RANKSAI.
it just did exactly what the last sentences said. it added several assumption to reduce the table's size.
no holes, regarding height difference >=4 same, assuming only rightmost gap, and ignored global height, to reduce the size from 2^200 to 9^8 (9: -4,-3,-2,-1,0,1,2,3,4; 8: 9 columns - 1 = 8 transitions), in order to be affordable for a normal PC (but taking ~300M? (EDIT: 168MB) harddisk, and wholly loaded into memory while running).

[UJS3]

So have you done this for a 4*4 field? On the bright side, if your field has even width then you can never have an odd number of minos occupied, so you'll "only" have to check half of the possible configurations  

[farter]

So have you done this for a 4*4 field?

not yet   it's still only an idea and i don't have much time to write programs..

On the bright side, if your field has even width then you can never have an odd number of minos occupied, so you'll "only" have to check half of the possible configurations  

yes and here it's 4-wide, the number of minos occupied will always be times of 4, only 1/4 of all are valid.
but.... 2^200 / 2 = 2^199
 hmmm... not that bright...