Solving Tetris in C

by thorn • 12 years ago

35 6 12 years ago

Someone• 12 years ago

"I'm disappointed not to have been able to solve Tetris for width 10, but I remain firmly convinced that a player victory is inevitable there too."

Note that 'victory' is defined here as 'getting one line', not as "staying alive forever"

Regular games have the player eventually lose after getting quite a few lines. With an evil adversary, that 'losing' will always happen. See http://harddrop.com/wiki/A_deadly_piece_sequence

happyhammy2• 12 years ago

why do you need to record states of a piece where the piece is not in a landing position?

what if you only recorded mountains and transformations of a mountain to another mountain?

happyhammy2• 12 years ago

also, you can simplify mountains: if the shape of 2 mountains' top surfaces are the same, then the answer to the taller mountain = answer to smaller mountain in a smaller well

rlanday• 12 years ago

There’s already an evil version of Tetris called Bastet (“bastard Tetris”).

4shadow• 12 years ago

I still thought it was fun, but it does do pretty well at deliberately choosing "bad" pieces. With enough strategy and playing through just a couple times you can exploit weaknesses against it, however. While being very good, I was still able to score 5 lines even though it was trying to to force me out of it. As to the proof, I do believe your guess that a player can always score a line given sufficient depth. My initial thought at approaching it is to consider that the pieces must all have only 4 blocks in their structure. This is a tight limiting factor which basically gives you that you need half the width in number of pieces to get across for the most part. What makes it tricky is the shortcoming* of the algorithm you used to define the worst piece available at each turn. It, with reasonable consistency, gives you a great number of the same piece until you cross a certain boundary, so with the Z shaped pieces, for example, you can construct a row, then when you get to the last one to finish a line, it switches to straight pieces, which you can similarly line up all the way across. Repeating this process leaves you with a "hole" that is two block-widths across from very nearly top to bottom, essentially guaranteeing that you can score at least one line in the process. I'm not sure how I would formalize it exactly, but that was the strategy I employed to get 4-5 lines per game.

*shortcoming may not be the best description of the algorithm, but a better choice escapes me at the moment.

wavesum• 12 years ago

on my osx/chrome setup pieces disappear when they land.

Solving Tetris in C

Related Stories