7 ms·
Is there a winning strategy in Tetris?
- mamon 9y agoI've always thought that the mechanics of Tetris are pretty straightforward and it is always possible to arrange incoming pieces without any gaps. The main difficulty for a human player is coming from the increasing speed, not the pieces not fitting together.
- __s 9y agoTetris is NP Hard. Also Hatris: https://www.youtube.com/watch?v=EIBqEUvvDi0 https://www.youtube.com/watch?v=EIBqEUvvDi0 Not sure if your comment was to say "I thought tetris was easy in a turn based environment, turns out I was wrong" or if you were contradicting the linked thread without basis
- nrook 9y agoI think your disagreement comes from a problem of definition. This paper (linked in the mathoverflow thread) appears to demonstrate playing Tetris optimally is NP-hard, even in a turn-based environment; that's because playing Tetris optimally involves getting lots of Tetrises, not just surviving indefinitely. http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-865.pdf http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-86... In contrast, it's not clear to me that playing Tetris indefinitely with the piece randomizers used in current Tetris games is NP-hard.
- Jaxan 9y agoIf you only get z shapes (with the same orientation). Is it then possible to avoid gaps? This is not clear to me at all.
- __s 9y agoYou can go infinite if only supplied Ss. You'll have intermediate holes which will be filled in after the above row is cleared
- Jaxan 9y agoAh yes, of course!
- tosh 9y agoIndependently of that in Tetris the pieces (tetrominoes) are drawn from a bag: http://tetris.wikia.com/wiki/Random_Generator http://tetris.wikia.com/wiki/Random_Generator
- pdpi 9y agoOnly in some versions. E.g. Puyo Puyo Tetris on the Nintendo Switch (to quote the most recent commercially-available Tetris I can think of) doesn't use that randomiser. I may or may not have played a few very poor games before I caught on to what was going on...
- Lewton 9y agoPuyo Puyo Tetris draws from a bag of 2 sets of tetriminos, so every 14 pieces you'll have gotten two of each, afaik Also you'll never get three of the same piece in a row* *almost 100 % sure of this Haven't happened to me in a game yet and my rating is around 4480
- mamon 9y agoBut are those pieces selected at random or not? Probability of getting even 10 z shapes in row is comparable to probability of winning a lottery (2.01599×10^-8, if I got Wolphram Alpha query right)
- amptorn 9y agoFor the purposes of finding a "winning strategy" we have to have a solution for every piece sequence, regardless of probability.
- deleted 9y ago[deleted]
- taneq 9y agoIf you only get Z-shapes (of the same orientation) forever, then no. The game's not winnable. Proving the least favourable distribution of z-shapes to other shapes which would allow a game to continue indefinitely would be really interesting. :)
- amptorn 9y agoIn fact you can just line five of the Z shapes up along the bottom, over and over again. This technique works indefinitely. Now, if there's an occasional S shape thrown into the mix, you have a problem.
- dwohnitmok 9y agoAs additional clarification if you align the piece upward to look like this then you're fine: # ## # You'll end up with # # # # # ########## # # # # # which becomes # # # # # # # # # # which you can just repeat over and over again forever (if your variant of Tetris includes gravity even this collapse to nothing).
- deleted 9y ago[deleted]
- ethan_g 9y agoCertainly the first thing that's apparent when watching pros play is their speed. However, after playing years of Tetris myself (though nowhere near pro level), I've really come to appeciate that speed is only a small fraction of what makes pros pro. * Many multiplayer games give bonuses for combos (multiple consecutive line clears), T-spins, and Tetrises. Setting these up efficiently can require reading several pieces ahead and takes a ton of practice. An example where both players do a fairly elaborate setup, one with combos and the other with T-spins: https://www.youtube.com/watch?v=mASSHXLTuU4 https://www.youtube.com/watch?v=mASSHXLTuU4 * 20G mode, made famous by games like TGM, drastically reduces the ability to manipulate the pieces. Even surviving takes new strategies (you're forced to play a lot of strange moves), much less making tetrises like the pros do. https://www.youtube.com/watch?v=aoU0DQh7zdU https://www.youtube.com/watch?v=aoU0DQh7zdU * Some multiplayer games give difficult garbage, I'm thinking of Cultris 2 specifically. Clearing garbage efficiently, known as "downstacking", requires much more careful piece placement than regular play. It's hard to appreciate from video, but if you compare pros downstacking to a normal person, you can see they use fewer pieces to clear the same amount of garbage, which is a real competitive advantage. https://www.youtube.com/watch?v=OgK4aJ_3zCw https://www.youtube.com/watch?v=OgK4aJ_3zCw
- amptorn 9y ago"Tetris" has to be well-defined mathematically before it can be confronted as a problem. Rules governing piece rotation behaviour, piece spawning, piece randomization, wall kicks, loss conditions and even well dimensions need to be laid out first.
- bubblesorting 9y agoI have great news for you! https://tetris.wiki/SRS https://tetris.wiki/SRS
- moomin 9y agoTrue story: the Cambridge Maths Society, The Archimedeans, had a journal called Eureka (of course). It happily published interesting but not important bits of mathematics. One student wrote a proof of an impossible sequence for any width board. It's even impossible if you have perfect knowledge of the sequence. All you need is to drop Ss and Zs in an irrational order. I think this got published in 1990, but I can find little evidence even if the journal's existence online.
- anvandare 9y agoI think you mean this one? Of course it's also possible that multiple people have published multiple proofs. https://www.researchgate.net/publication/2347389_How_to_Lose_at_Tetris https://www.researchgate.net/publication/2347389_How_to_Lose... The proof itself is quite self-evident: given a perfectly randomly block generator, and infinite play time, eventually you're going to produce a very long sequence of left- (or right-) facing S-blocks. Since those are impossible to eliminate (there's always one block left open on a row) eventually you lose.
- zeta0134 9y agoThis actually isn't true for modern variants of Tetris. A correct implementation of the random number generator requires that the 7 pieces be shuffled into a bag and then drawn randomly, ensuring an even distribution, and disallowing long runs without a desired piece. (Maximum of 12.) The bag is re-shuffled every 7 blocks in the sequence. https://tetris.wiki/Tetris_Guideline https://tetris.wiki/Tetris_Guideline https://tetris.wiki/Random_Generator https://tetris.wiki/Random_Generator Thus, in a game of Tetris adhering to these official guidelines, the longest sequential run of S and Z pieces would be 4, in the following sequence: [5 Random Blocks] [Z and S in any order] [Z and S in any order] [5 Random Blocks] I'd be very curious to see a proof of an impossible sequence which adheres to the official rules, as that would be quite a feat indeed!
- anvandare 9y agoIn that case it would probably still be possible, but the proof would have to be found by example. It seems like an advanced version of the Eight Queens puzzle: which sequence of bags guarantees a losing board state?
- hughperkins 9y agoA strange game. The only winning move is not to play.
- trapperkeeper74 9y agoHow about a nice game of chess?
- shellbackground 9y agoTo reference: https://youtu.be/xOCurBYI_gY?t=15m57s https://youtu.be/xOCurBYI_gY?t=15m57s It's fun how program learning to play teris pauses the game just before loosing.
- pitaj 9y agoSource of the reference is War Games (1983). https://www.youtube.com/watch?v=6DGNZnfKYnU https://www.youtube.com/watch?v=6DGNZnfKYnU
- a3_nm 9y agoThere's a related annoying question for which I've never found a conclusive answer: for the standard tetris board (width 10, height 22), is there a strategy for the player that guarantees that they will be able to fill at least one line? or conversely is there a strategy for the game (supplying the pieces) to make the player die without having filled at least one line?
- qntm 9y agoYes, a strategy does exist which can force at least one line in a well of width 10 (and different strategies for 4, 6 and 8). I did a tedious brute-force calculation which demonstrated this a few years back. The code is not particularly presentable and the calculation takes about 11 days on a modern machine (it runs in a single thread), but here: https://github.com/qntm/tetris https://github.com/qntm/tetris The limiting factor is headroom (the depth of the well). For wells of depth 0, 1 and 2, the AI clearly wins, but once the depth increases enough a strategy becomes possible. My belief is that such a strategy exists for all even well widths, although proving this is annoyingly hard.
- a3_nm 9y agoHi, thanks a lot for pointing this out to me! However https://qntm.org/tetris#sec6 https://qntm.org/tetris#sec6 does not have any cases for width 10 where the player wins. Are you implying that you have run more calculations than described in this article, and that the player can win for width 10 with a sufficient high depth?
- fghtr 9y agosee also: https://qntm.org/files/hatetris/hatetris.html https://qntm.org/files/hatetris/hatetris.html
- freshyill 9y agoI once played a game of Tetris on the Nintendo DS (about 10 years ago now) where I maxed out the lines… then the levels… and then maxed out the score. I played this same game for weeks, mostly on the train to and from work. And wouldn't you know it, but Tetris DS has a bug that won't let you save a score once you pass 100,000,000 or whatever the highest possible score is. Tetris got a lot easier when they added the ability to infinitely rotate a block for as long as you want at the top of the pile.
- reza_n 9y agoSearch for "tetris championship" on YouTube. Some great tetris gameplay and you can pick up on a lot of the strategy pros use. Ex: https://youtu.be/DdfRQjb5o9k https://youtu.be/DdfRQjb5o9k
- arikrak 9y agoIn classic Tetris you can slide the piece briefly after it lands, so you can always keep the game going.