From: kubo@jacobi.math.brown.edu (Tal Kubo) Newsgroups: sci.math Subject: Re: Infinite probabilities Date: 13 Feb 1998 02:08:56 GMT KRamsay wrote: >Yes, I saw a talk by someone who proved it for his master's thesis.There >is a finite sequence of tetrominos which, if the machine selects them, >you lose. In a random sequence of tetrominos such a sequence will >eventually appear with probability 1. There's an article on this in a recent Mathematical Gazette. 70000 consecutive skew tetrominos force a loss starting from an empty board, and an alternating sequence of left- and right-handed skew tetrominos will eventually force a loss on any size board and any starting position. By skew tetromino I mean the piece you drew, or its mirror image: > ** > ** ============================================================================== From: "Maxim V. Razin" Newsgroups: rec.puzzles Subject: The Evil Tetris Date: Wed, 11 Mar 98 11:46:58 +0200 The Evil Tetris: Consider the standard Tetris game: tetramino figures XXXX XXX XXX XXX XX XX and XX X X X XX XX XX are falling into the pit with width 10 and height 20. The Player can rotate and shift the current figure. If a horisontal row becomes completely full, it vanishes. (a) Suppose the evil Daemon who puts figures in play, wants the Player to lose. Can he/she/it/... do it independently of Player's actions? (b) The same question if the Daemon is blind and can't see the pit. ============================================================================== From: tilford@ralph.caltech.edu (Mark J. Tilford) Newsgroups: rec.puzzles Subject: Re: The Evil Tetris Date: 14 Mar 1998 05:06:46 GMT Does the evil being have to choose the entire line of pieces in advance, or can it adjust its plans depending on the player's actions? -- ----------------------- Mark Jeffrey Tilford tilford@cco.caltech.edu ============================================================================== From: George Weinberg Newsgroups: rec.puzzles Subject: Re: The Evil Tetris Date: Sun, 15 Mar 1998 08:02:09 -0800 Maxim V. Razin wrote: > > The Evil Tetris: > > Consider the standard Tetris game: tetramino figures > XXXX XXX XXX XXX XX XX and XX > X X X XX XX XX > are falling into the pit with width 10 and height 20. > The Player can rotate and shift the current figure. > If a horisontal row becomes completely full, it vanishes. > > (a) Suppose the evil Daemon who puts figures in play, wants > the Player to lose. Can he/she/it/... do it independently > of Player's actions? > > (b) The same question if the Daemon is blind and can't see > the pit. Here's my attmpt at a demon strategy (works blind). Alternate dropping these guys X and these guys YY XX YY X I don't see how they player can help but lose, feel free to prove me wrong. George ============================================================================== From: Mark R Plesko Newsgroups: rec.puzzles Subject: Re: The Evil Tetris Date: Tue, 17 Mar 1998 10:17:14 -0500 Excerpts from netnews.rec.puzzles: 11-Mar-98 Re: The Evil Tetris by Glenn Rhoads@sonora.rutg > In fact, the player can't win if you drop any combination of the two pieces > XX and XX > XX XX How about if the demon drops XX until a line is cleared, then XX until a XX XX line is cleared, and repeats? It seems that this will bump the player up two rows for each line obtained. (Obviously the player doesn't have to use the first five pieces to obtain a line, but I don't think that matters) | | | | | X X X X X| |XXXXXXXXXX| (1) |X X X X X | +----------+ Remove the second row | | | | | | | X X X X X| (2) |X X X X X | +----------+ Switch pieces |X X X X X | |XXXXXXXXXX| | X X X X X| | X X X X X| (3) |X X X X X | +----------+ Remove the fourth row | | |X X X X X | | X X X X X| | X X X X X| (4) |X X X X X | +----------+ etc. Note that | | | X X X X | | XXXXXXXX | | XXXXXXXXX| (3) |X X X X X | +----------+ also seems to fail. To make this a blind demon strategy, perhaps the demon could drop a large enough number of each piece (I believe 37 in the first case) to guarantee that the player has obtained a line or lost the game due to sheer number of pieces in the playing field. I think this works but would definitely like to see confirmation or a counterexample. -Mark ============================================================================== From: zare@cco.caltech.edu (Douglas J. Zare) Newsgroups: rec.puzzles Subject: Re: The Evil Tetris [Spoiler] Date: 19 Mar 1998 08:02:01 GMT Maxim V. Razin wrote: >The Evil Tetris: > >Consider the standard Tetris game: tetramino figures >XXXX XXX XXX XXX XX XX and XX > X X X XX XX XX >are falling into the pit with width 10 and height 20. >[...] call those Z S Most of the following ideas are not mine. Theorem: For any finite width and any finite height, the sequence S Z S SZ SZS SZSSZ ... invariant under the substitution S|->SZ Z|->S cannot be placed from any initial configuration. Hence, for any board some finite prefix of this sequence cannot be placed, and so you will lose at Tetris with probability 1 if the pieces are chosen "at random". The specific sequence isn't important (that some such sequence exists given that one will lose with probability 1 on each board is an easy exercise); its useful property is that the S's and Z's do not have a rational limiting ratio. Why S's and Z's? Let the number of squares above the first column be A and the number of squares above the second column be B. B-A must be between -20 and 20, and will only kept constant or increased by the placement of an S or a Z. So, if you are given the killer sequence all but at most 40 of the placements with at least one square in the first two columns must be # # ## or ## . # # 12 12 One can continue this argument with columns 3 and 4, then with 5 and 6, etc. to show that all but finitely many of the placements must be vertical, in columns 2k-1 and 2k. Note that S's and Z's leave gaps when stacked on each other, and such gaps are not removed by placing S's and Z's "vertically". Now, you need to show that you have to put S's on top of Z's or vice versa infinitely often. For this you use the sequence or the board and the sequence; if you do not misstack infinitely often then you have to settle down to some stacks of S's and some stacks of Z's. You can't do this unless the limiting ratio of the sequence is 2a/width, for some integer a. The above combined with bookkeeping (and figuring out that the limiting ratio of the above sequence is irrational) allows a rigorous proof. IIRC a few million alternating S's and Z's kills on the standard board, but it can be done much faster if one watches the player. Douglas Zare ============================================================================== From: you.know.him@you.love.him (Mike Naylor) Newsgroups: rec.puzzles Subject: Re: The Evil Tetris [Spoiler] Date: Fri, 20 Mar 1998 00:55:33 GMT For some reason I feel more at peace now, just knowing that there are people out there who have completely unraveled the mysteries of Tetris. -- Mike Naylor - myfirstname.mylastname@mail.serve.com Visit Strawberry Macaw's Puzzle page at http://www.serve.com/games/puzzles.htm ============================================================================== From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math Subject: Re: Tetris, probability of losing 1 Date: 15 May 2002 23:27:08 GMT In article , MacGyver wrote: >http://www.math.niu.edu/~rusin/uses-math/games/tetris/losing >Is is actually supposed to be from this group, that's why I ask here. The person whose Master's thesis Keith Ramsay refers to there was John Brzustowski. At last report he was at University of Alberta (try jbrzusto@ualberta.ca). Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: dpanagop@yahoo.com (Dimitris Panagopoulos) Newsgroups: sci.math Subject: Re: Tetris, probability of losing 1 Date: 17 May 2002 06:07:53 -0700 >From a quick view of the text at: www.math.niu.edu/~rusin/uses-math/games/tetris/losing I 've got the impression that the argument there is the same with that of an article in "The mathematical Gazette" vol.81, num.491, July 1977. I don't know if it is online but you can always try your local library.