Is bag+SRS sustainable?

Thread in 'Discussion' started by tepples, 9 Jul 2006.

  1. tepples

    tepples Lockjaw developer

    Tetris with 0 gravity and infinite next pieces has notably been proven NP-hard several years ago. The proof (available as a PDF preprint from arXiv) appears to apply to some game similar to Tetris. But some of its underlying assumptions have been rendered invalid by the Guideline.

    It assumes a model of "instantaneous rotation" which is identical to BPS bounding-box rotation (i.e. SRS rotation without wallkicks) except for the behavior of I.

    It uses different names for five of the tetrominoes, including four that I had never seen elsewhere:
    • O -> Square (Sq) (obvious)
    • J -> Left Gun (LG)
    • L -> Right Gun (RG)
    • Z -> Left Snake (LS)
    • S -> Right Snake (RS)
    The proof gives four restrictions on what it calls a "reasonable" rotation model, including the following stipulation:

    SRS can be made to kick up or down in this case. See the recent discussion of I-spins in the Lockjaw topic.

    But where the paper establishes a link between Tetris and 3-Partition, it would appear that a case with T=0 or s=0 would result in a trivial case of 3-Partition. And any case with T>0 or s>1 would result in a playfield much larger than the Guideline playfield.

    JZJJO will never occur under the Guideline's bag randomizer unless you have two bags 12345ZJ JO67890, and 5 is held and replaced with J. But then, the article considers only move left, move right, move down, rotate left, rotate right, and lock if landed, not hold piece.

    In addition, the article leaves the following important questions open:

    I have been doodling tesselations of bag-randomized tetrominoes that may allow me to prove that Tetris with bag randomization and SRS wall kicks can be played forever from an empty well, in much the same way that Lumines has been solved.
  2. tepples

    tepples Lockjaw developer

  3. Nice.

    Could we get a video of this?
  4. Sully

    Sully Unregistered

    It seems easy enough assuming slow drop speed, but whould this be sustainable in 20g?
  5. nope, this particular stack can't maintain in twenty g. has to do with the right side, since three-wide j's and l's won't make it all the way right in some cases. doesn't mean twenty g tetris doesn't solve-- just means not in this particular way.
  6. This thread never got the postcount it deserved IMO. It's one of my favourite things to come from the TC community. Thank you Tepples!

    If anyone feels like reading the wiki entry, I recently rewrote much of it. It is now extremely clear that it is sustainable forever, as the instructions have been changed to show a deterministic way of clearing the screen every 140 pieces. Overall the article has been changed from a how-to guide that allows for improvisation within "playing forever" game states, to a more formal proof that it is indefinitely sustainable.

    A bonus for people who enjoy a riddle: There's actually a known error with my revised proof, making it not possible 100% of the time. There's a relatively simple workaround I'll be adding sometime soon, but I figured I'd give you guys the chance to find a hole in my logic. You know, if you like that sort of thing. [​IMG]
  7. Cubicz

    Cubicz Unregistered

    I like this solution for it's simplicity. The proof doesn't rely on intense maths, but on a pattern. In my mind, it also further validates that a width of 10 is the 'right' width (if there was any doubt). Does this 'Playing Forever' proof easily translate to other widths?
  8. I can think of a general solution for width 12, 16, 20, 24, etc.

    Just place the I pieces flat so that you have 3 heaps of width 4. Shift the location of each heap every 4 bags and after a full circle you'll bravo.

    If you were able to follow that, then you can see that width 10 actually takes more work to loop than width 12 + 4n.
  9. tepples

    tepples Lockjaw developer

  10. jujube

    jujube Unregistered

    these players seem to have SRS + 7 bag figured out in multiplayer with kinda random garbage. but it's important to remember that they are the very best. 99.999% of us can't sustain "perfect" tetris like this for such a period of time. who knows, maybe we'll all catch up someday, but for now the better and faster player still seems to win most of the time.

    edit: yeah this off topic, i just had to jump in and defend the 7 bag a little. a little.
  11. jujube

    jujube Unregistered

    by the way, nice job with that tepples and ct. it's actually easy to screw up as i did last night, but solvable none the less.

  12. I've updated the entry... See The Final Bag for details. Unfortunately, it is not possible to get a bravo every loop, though at least it will happen most of the time.

    I've got a few ideas for consistent bravos, but they would definitely significantly complicate the proof if they work. Won't pursue it though... I've had my fill for now.
  13. tepples

    tepples Lockjaw developer

    Instead of 3 standard and 2 balance, can you do standard, balance, standard, balance, standard?
  14. Then the sides would be so short you'd very often run into the "final bag" problem.
  15. Ok looking at your pictures, I think I see what you're going for. Ending with doubled I pieces in the middle so that order doesn't matter, right? I had this same idea. I never really pursued it though, because it would really complicate the proof compared to my relatively simple solution that only bravos most of the time. If you can make it work though... [​IMG]

    I did have a less elegant but procedurally simpler solution:

    An "intro" of 4 standard bags.

    Then the same loop:

    12 standard

    4 balancing

    4 balancing (other side)

    Because of the intro, you can guarantee line clears in the final bag. But you wouldn't loop to a bravo pattern... You'd loop to the 4444004444 pattern.


    I see you removed your post/page. I guess it didn't pan out?
  16. tepples

    tepples Lockjaw developer

    I decided to just let the proof loop from bag 21 to bag 2 in the worst case.
  17. I've been putting a bit of thought into properties solutions must satisfy. I'd appreciate it if someone could prove one way or another whether this restriction applies under tetris rules. The only real difference is line clears.

    If the restriction applies, it would mean that all bravo loops would need to be an even number of bags. This would raise the theoretical minimum from a 5 bag loop to a 10 bag loop.
  18. It doesn't always. The T piece is the piece in question, with 3-1 parity (3 black, one white or the other way around), the other pieces are 2-2.

    But there are ways to make this not matter. When a line is cleared, all of the squares above "change colour". The trick is therefore to make the T be involved in a line clear where it ends up being 2-2. And the only way to do that, I believe, is to drop it vertically, with the middle row being made, leaving the other 2 pieces on different coloured squares.

    Ehh... you people want a simpler version? Try this:

    ..........  ..........  ..........  ..........
    ..........  ..........  ..........  ..........
    XXXX..XXXX  XXXX..XXXX  ..........  ..........
    However, dropping all of the pieces down a 2-wide "pit" isn't the answer either. To demonstrate this, you need to consider how many blocks each piece would put in each column if it was dropped down a 2-wide pit. S Z and O are 2-2, J L and T are 3-1, and the I is 4-0. Given those arrangements, it's not possible to put 14 in each column.

    If there is a 5 bag solution, then a good starting place might be the first 4 bags of our current soltion, with the pit showing 4444004444 (as I've been refering to it). For now, I would be willing to settle for a single solution existing for a 5 bag clear. It it isn't possible from 4444004444, then it might be possible if we start thinking from one piece earlier, namely the T piece going in on the left, leaving either 3234004444 or 4323004444, depending on how the STZ column was started.

    I often refer to the T as a good "problem-solving piece", because it can convert a bad situation into a better one (by converting a left stair to a right stair to take a different snake, or levelling out a stair to hold an O, or by T-spinning). But here, it's more of a problem-causing piece...
  19. Yeah, I've been able to see that the parity argument does not apply to Tetris. Also, I've found a 10-bag loop, though it is one that never bravos. I'd share it but I can possibly tweak it into a 5-bag loop with a bit of work.

    I'm starting to think the 20-bag loop I created is somewhat special, with its frequent bravos and its simple contingency plan to handle the worst case. I don't think it's possible to bravo-loop 10 or 5 bag loops. Tepples, if you think you could actually coax the current general design into always bravoing, it might give me some ideas to play with. I'd be genuinely impressed to see an all bravo solution though.
  20. Ok, I've thought about this. It doesn't affect us directly, but it does limit our solution space.

    For a 5 bag solution to exist, an odd number of T pieces must be played vertically, with the flat side either to the left or to the right.

    I think that column counting is the next step in finding if a solution exists or not. To clarify, exactly 14 blocks must fall into each of the 10 columns. If this can be shown to not be possible, then we will have proved that no 5 bag solution exists.

    I is 4 or 1111

    J is 13, 211, 31, or 112

    L is 31, 211, 13, or 112

    O is always 22

    S is 121 or 22

    T is 121, 13, or 31, with a restriction that there must be an even number of them (0 or 2 or 4) showing 121

    Z is 121 or 22

    CT: I'm guessing by your absence on IRC that you're posting from work, yeah?

    Edit: I might be talking complete bollocks. Feel free to demonstrate where my mistakes are...

Share This Page