News for hackers. Stuff that matters.
Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Monday January 09, 2023 @10:12AM (#34311174)
the claim is that this is theoretically possible in stock tetris with only one modification: an infinite board (with a floor).

the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from clearing because they have infinite width (so the game won't interfere with your construction).

their concept for gates is that if you nudge a block at a certain row as it's falling, it will either shift one column over or be blocked. this page is a good visualization:

https://meatfighter.com/tetromino-computer/inverter-not.html

except... once you hard-drop a block in tetris, you can't nudge it. and if you don't hard-drop it, it will never reach your canvas.

they kind-of hand-wave this in the section "infinite playfield". after describing the mechanics of a hard drop, they say:

> A more generalized version, the semihard drop, attempts to vertically translate the piece from “row infinity” to a specified, finite row.

if the fall timer can't get the block into a finite row, how would a player (without hard-dropping)?

loved reading through this, though. the animations were perfect for describing the mechanism! very high-quality documentation for a fun project.

Re:Tetris Is Capable of Universal Computation by UncleMeat on Monday January 09, 2023 @10:31AM (#34311402)
NES tetris has a RNG that can be manipulated so you always get the piece you want as long as you never need duplicates. You don't even need a junkyard.
Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Monday January 09, 2023 @10:33AM (#34311436)
interesting! unfortunately the board would be too small to build more than one or two gates before you start to run into row clearing and the ceiling.

edit: is this your article? thank you for the wonderful post!

Re:Tetris Is Capable of Universal Computation by UncleMeat on Monday January 09, 2023 @10:48AM (#34311637)
No it is not my article. I just know weird things from other articles I also didn't write involving doing weird stuff with NES tetris.
Re:Tetris Is Capable of Universal Computation by zero__one on Monday January 09, 2023 @11:12AM (#34311955)
From https://meatfighter.com/tetromino-computer/input-language.ht...

> In practice, IL programs direct the agent to construct a pile near the origin that progressively grows taller and wider. That being the case, it can work with a Tetris implementation that defines “row infinity” as a finite row whose index increases as a function of the number of spawns. In such an implementation, the agent emulates a semihard drop with a finite number of soft drops.

Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Monday January 09, 2023 @12:23PM (#34312869)
that's not really infinite, though, and other pages do describe it as truly infinite, e.g.:

> When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity.

i'm nitpicking, of course. everything described is possible with a sufficiently large board. you'll just have a time constraint to place each block.

Re:Tetris Is Capable of Universal Computation by zero__one on Monday January 09, 2023 @04:07PM (#34316080)
For the method described in the paper to work, the infinite version of the game requires a semihard drop operation or something analogous as a legal move. In modern versions of Tetris, the rotation systems permit very unusual operations such as wall climbing or infinite lock delays, not to mention rotating in physically impossible ways. A semihard drop is not a big ask on an infinite playfield. It's within the spirit of the game.
Re:Tetris Is Capable of Universal Computation by undersuit on Monday January 09, 2023 @12:45PM (#34313226)
You want to know how the Tetromino does memory allocation and garbage collection?

I don't think the infinite board is that big of a deal. Turing Machines and Lambda Calculus have no limits on their memory space and we implement analogues of them in our limited memory space.

Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Monday January 09, 2023 @02:24PM (#34314749)
i'm talking about the theoretical model, not the implementation details. i'm focusing on the definition of "infinity" here:

> On an infinite playfield, tetrominoes spawn at “row infinity” and column zero. When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity. This means, in finite—though potentially vast—time, the agent can shift the piece into any finite column. And once in position, the agent can hard drop the piece.

gate construction relies on "nudging" a block at a specific row as it is falling. but if blocks start at row infinity, the only way to get them down should be to hard-drop them -- which precludes nudging.

they've defined a new "semi-hard-drop" operation, and introduced it as a "generalization" of legal moves, but it isn't.

Re:Tetris Is Capable of Universal Computation by undersuit on Tuesday January 10, 2023 @02:54AM (#34321799)
Why isn't it? It just hides time passage. Oh no the computer gets a higher score... but it's not playing Tetris, the high score doesn't matter.

For instance: "For instance, if the agent emulates a semihard drop with a finite number of soft drops, then it will let a gravity drop serve as the final soft drop. "

Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Tuesday January 10, 2023 @08:58AM (#34324874)
it's math: no amount of soft-drops (or gravity drops) can bring a block from row infinity to row x. subtracting one from infinity is fruitless.
Re:Tetris Is Capable of Universal Computation by undersuit on Tuesday January 10, 2023 @02:57PM (#34330592)
And you can't have an infinite tape, but no one is out there saying the Turing Machine is fake.

Consider this. Our physical implementations of turing machines work even though we don't have an infinite memory. We do encounter some limitations because of such.

The Tetrino also works. You can create it and run it on a finite board. It would be limited just at our physical machines are limited without access to infinite memory.

Re:Tetris Is Capable of Universal Computation by woodrowbarlow on Wednesday January 11, 2023 @12:10PM (#34340989)
i'm not saying it's impossible to model an infinite board using software (that's quite possible). i'm saying that if it's possible to soft-drop a block to an arbitrary row, then the model of infinity is faulty and inconsistent. and, unfortunately, both the infinite board and the soft-drop are required fundamental underpinnings of the proposed mechanism for computation.
Re:Tetris Is Capable of Universal Computation by undersuit on Wednesday January 11, 2023 @01:32PM (#34342403)
And I'm saying you don't need a board to be infinite to do work, you just need a board to be infinite to compute all work. Just like you need infinite tape for a Turing Machine to be able to compute all work.
Re:Tetris Is Capable of Universal Computation by tshaddox on Monday January 09, 2023 @01:22PM (#34313898)
> the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from clearing because they have infinite width (so the game won't interfere with your construction).

Not to mention that you need unbounded memory anyway.