4 ms·

I'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 diff

by mamon 9y ago

I'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 ago
Tetris 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 ago
  I 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 ago
If 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 ago
  You 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 ago
    Ah yes, of course!
- tosh 9y ago
  Independently 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 ago
    Only 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 ago
      Puyo 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 ago
  But 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 ago
    For 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 ago
  If 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 ago
    In 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 ago
      As 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 ago
Certainly 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

by mamon 9y ago

__s 9y ago

Tetris 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 ago
I 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 ago

If 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 ago
You 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 ago
  Ah yes, of course!
tosh 9y ago
Independently 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 ago
  Only 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 ago
    Puyo 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 ago
But 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 ago
  For 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 ago
If 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 ago
  In 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 ago
    As 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 ago

Certainly 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