A Tetris assertion

Stump your fellow simians.
Aoidoi
Posts: 863
Joined: Thu Jun 10, 2004 8:26 pm
Location: Left Noob

Post by Aoidoi »

Hardly a rigorous proof, but on some systems I played on it was impossible after a certain level to move the brick all the way to either side before it hit bottom. Didn't matter if you started as soon as it dropped, there was no way to continue indefinately as you couldn't reach the sides.

For a system wherein the top speed of the computer always allows for you to place blocks on the sides the question is harder to prove or disprove. At that point you can ignore speeds and reflexes and the question becomes are there sequences of blocks that invariably stack up regardless of placement. If the block drops are truly random, eventually you would get every possible combination, including things like 1000 of the same piece in a row. This would be no problem with the square, straight 4, or 3 and 1 pieces as I think you can always fit them in. (unless the screen is an odd number across (I forget)... in which case squares would get you eventually). The only other piece this would potentially be a problem with would be the z (or however you want to describe it) which would lose bits here and there each time if you got enough of them in a row.

Wow... I put way too much thought into that. And I played waay too much Tetris when I was younger. :D
Mulebear
Posts: 11048
Joined: Tue Aug 24, 2004 2:46 am

Post by Mulebear »

This is a link to a .wmv file. Click here to watch a Tetris master.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Post by Skeptoid »

Interesting topic.

From here: http://www.colinfahey.com/2003jan_tetri ... rategy.htm
There are whole categories of pathological sequences that CANNOT be survived.
Tetris is NP-complete: http://www.sciencenews.org/articles/200 ... thtrek.asp

The first few pages of the first paper listed under the references for the sci-news article are very interesting as well.
slimshady2357
Posts: 698
Joined: Sat Jun 05, 2004 4:53 pm

Post by slimshady2357 »

Abdul Alhazred wrote: With a sequence of identical Z tetronomos, there is no way to close it up until there is some other tetronomo. Long enough sequence of identical Z tetronomos and the game inevitably ends.
I'm not sure this is true. If the number of squares across the playing field is even, then you should be able to keep placing the Z pieces side by side and play as long as they keep coming. Here is a quick diagram I did in paint:
http://atlas.walagata.com/w/slimshady2357/tetris.jpg

You can see that the row B will be complete and be gone, dropping down row A on top of row C. This leaves a picture like:
http://atlas.walagata.com/w/slimshady2357/tetris2.jpg

Now you can add the same Z piece all along, and you will get rid of two rows this time, leaving the same as the second picture. This can be done over and over.

Adam
Bearguin
Posts: 8094
Joined: Sun Jun 06, 2004 12:26 am
Title: Thankless Bastard!
Location: Get off my fucking lawn

Post by Bearguin »

In your picture, wouldn't row A drop to row C and clear the board?
slimshady2357
Posts: 698
Joined: Sat Jun 05, 2004 4:53 pm

Post by slimshady2357 »

Bearguin wrote:In your picture, wouldn't row A drop to row C and clear the board?
Not in any tetris game I've played. A row can only drop down the same number of rows that were cleared. So if you clear 4 rows at once (usually known as a "tetris"), then the rows above that drop down 4 rows.

Adam
Bearguin
Posts: 8094
Joined: Sun Jun 06, 2004 12:26 am
Title: Thankless Bastard!
Location: Get off my fucking lawn

Post by Bearguin »

Hmmm. I must be thinking of a different game then. Sorry.
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

On a standard 10-square-width Tetris grid, alternating S and Z pieces are impossible to stack indefinitely. This has been shown mathematically. I'm sure it would be possible to cope with the alternating S and Z pieces though, on a non-standard 8 or 12 (or other multiple of 4) width grid.
Last edited by ceptimus on Wed Mar 23, 2005 5:58 am, edited 1 time in total.
Skeptoid
Posts: 1296
Joined: Fri Jun 04, 2004 5:28 am
Location: Wisconsin

Post by Skeptoid »

ceptimus wrote:On a standard 10-square-width Tetris grid, alternating S and Z pieces are impossible to stack indefinitely. This has been shown mathematically.
Yes, it has been proved that the game must end before <70,000 pieces have fallen. The game will eventually terminate on any 2n, with n=odd, width board.
I'm sure it would be possible to cope with the alternating S and Z pieces though, on a non-standard 8 or 12 (or other multiple of 4) width grid.
You may be right.


Java Applet with only S and Z pieces Can anyone beat the high score of 229?

Explanation
ceptimus
Posts: 1462
Joined: Wed Jun 02, 2004 11:04 pm
Location: UK

Post by ceptimus »

Aoidoi wrote:Hardly a rigorous proof, but on some systems I played on it was impossible after a certain level to move the brick all the way to either side before it hit bottom. Didn't matter if you started as soon as it dropped, there was no way to continue indefinately as you couldn't reach the sides.
On a PC-based game, it helps to adjust your keyboard key-repeat rate from the control panel and/or BIOS settings. There is a delay before the first repeat, which should be turned right down, and a delay between subsequent repeats that should be set as small as you can manage without overshooting too often.

That tip may allow Adam to recapture some of his Tetris crowns on FF and mu.nu :( Damn, I'm a blabbermouth. :(
Walter_Wayne
Posts: 173
Joined: Mon Jun 07, 2004 9:26 am
Location: Ottawa

Post by Walter_Wayne »

Skeptoid wrote:
ceptimus wrote:On a standard 10-square-width Tetris grid, alternating S and Z pieces are impossible to stack indefinitely. This has been shown mathematically.
Yes, it has been proved that the game must end before <70,000 pieces have fallen. The game will eventually terminate on any 2n, with n=odd, width board.
I'm sure it would be possible to cope with the alternating S and Z pieces though, on a non-standard 8 or 12 (or other multiple of 4) width grid.
You may be right.


Java Applet with only S and Z pieces Can anyone beat the high score of 229?

Explanation
But a standard tetris game it is likely that it never gets to a 70000 piece sequence of alternating S and Z pieces. The length of the pseudo-random generator sequence is short enough that it doesn't contain such a sequence.

So Abdul's assertion remains unproven.

Pedantically yours


Walt