Academic Tetris Papers

[PetitPrince]

Being at EPFL (http://www.epfl.ch/), I suddenly realized that I had a wide access to scientific publication. So naturally, I searched for Tetris http://www.tetrisconcept.net/forum/images/smilies/icon_smile.gif (using PubMed, Sciencedirect and Google Scholar). Here is the result of an initial search. I ignored most of article speaking about game violence and those using Tetris as a handy psychoneuroexercice thing. I tried to focus specifically on Tetris itself.

Psychology
Maglio et Kirsh 1996) Epistemic Action Increases With Skill (http://wexler.free.fr/library/files/maglio%20(0)%20epistemic%20action%20increases%20wi th%20skill.pdf) (: apparently, we make more error as our skill increases. WTF ?
Maglio, Wenger et Copeland (2007) Evidence for the role of self-priming in epistemic action: Expertise and the effective use of memory (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V5T-4NH6NBN-1&_user=10&_coverDate=01_252F31_252F2008&_alid=893285513&_rdoc=1&_fmt=h05CF17932E) : a continuation of the previous article. I must say I didn't understood those two articles.

Math
Breuklaar, Demaine, Hohenberger et al. (2004) Tetris is hard, even to approximate (http://www.liacs.nl/~rbreukel/publications/tetris_is_hard.pdf) : the famous article proving that Tetris is NP-complete (i.e. fracckin' hard)
Baccherini et Merlini (2007) Combinatorial analysis of Tetris-like games (http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-4R11Y2W-1&_user=7199228&_coverDate=09_252F28_252F2008&_alid=893285513&_rdoc=31&007D7B279D) : every "Tetris-like" game is a finite automaton.
Brzustowski (1988) Can you win at Tetris ? (http://https?dspace.library.ubc.ca/dspace/bitstream/2429/3263/1/ubc_1992_spring_brzustowski_john.pdf) : A Master thesis: Tetris strategy and analysis from a mathematician point of view. C_t, it was made at University of Waterloo http://www.tetrisconcept.net/forum/images/smilies/icon_smile.gif .
Carr (2005) Applying reinforcement learning to Tetris (http://www.cs.ru.ac.za/research/g02c0108/files/litreviewfinalhandin.pdf) : an overview of how people tried to "solve" Tetris.
Hoogeboom et Kosters (2008) The Theory of Tetris (http://www.liacs.nl/home/kosters/tetris/tot.pdf) : a review article discussing more of the NP-completeness issue of Tetris.

Computer Science
B�hm, Kokai et Mandl (2005) An Evolutionary Approach to Tetris (http://www2.informatik.uni-erlangen.de/Forschung/Publikationen/download/mic.pdf) : Tetris + Genetic programming = awesome ?
Siegel et Chaffee (1996) Genetically Optimizing the Speed of Programs Evolved to Play Tetris (http://www.cs.bham.ac.uk/~wbl/biblio/cache/http___www1.cs.columbia.edu__evs_papers_tetris.ps) : another one.
Fahey (200x) Tetris AI (http://www.colinfahey.com/tetris/tetris_en.html): Fahey's famous Tetris AI (and other goodies). Okay, it's not a "real" (i.e. published) article, but it more than good enough.

And I haven't read all the article... yet. I haven't explored the bibliography section either.

[Shibby]

This is awesome. Tetris broken down to a science!

[caffeine]

Two recent ones I liked:

What baboons, babies and Tetris players tell us about interaction: a biosocial view of norm-based social learning (http://www.macdorman.com/kfm/writings/pubs/CowleyMacD2006BaboonsBabiesTetris.pdf)

Can Playing the Computer Game �Tetris� Reduce the Build-Up of Flashbacks for Trauma? A Proposal from Cognitive Science (http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=2607539) (The study behind what we read in the news not to long ago.)

Epistemic Action Increases With Skill (: apparently, we make more error as our skill increases. WTF ?
When I read this article four years ago I thought, "that's total bullshit. Their 'expert' players most definitely suck." If you look at the data on Ai's LJ 40 lines thread (http://www.tetrisconcept.net/forum/viewtopic.php?f=2&t=549) (3/30/09) as well as the data I recorded during the month I played constantly and achieved 3TPS (http://spreadsheets.google.com/pub?key=plvXjzGAyfVnQQdnyc8E9Jw), you'll see there's a negative correlation between speed and KPT (which means the less buttons you press, the faster you go).

In Ai's record thread, out of 53 players, there is a -.28 correlation
In my data record from October and November (all games finished, none canceled, no games were ever played on a different application), out of 1887 games there is a -.35 correlation.

This clearly shows that KPT is important, and that we should be mindful of finesse. The above study showed otherwise probably because the players weren't really that good, and/or there weren't enough players/games played.

[iphys]

To be honest, I never believe the results of any scientific studies, because most of them are just BS made up by overconfident academics who will spout any nonsense just to get papers published.

[Pineapple]

To be honest, I never believe the results of any scientific studies, because most of them are just BS made up by overconfident academics who will spout any nonsense just to get papers published.
Tetris is hard, even to approximate is a good example of this theory in action... http://www.tetrisconcept.net/forum/images/smilies/icon_rolleyes.gif

[tepples]

I never believe the results of any scientific studies, because most of them are just BS made up by overconfident academics who will spout any nonsense just to get papers published.
Tetris is hard, even to approximate is a good example of this theory in action... http://www.tetrisconcept.net/forum/images/smilies/icon_rolleyes.gif
Especially when there's no interest in publishing a follow-up paper that disproves the thesis once The Tetris Company amends the Guideline to make the original paper's assumptions (no hold, several piece sequences that never occur in bag, and a rotation system where "after" always overlaps "before") obsolete. Wikipedia, for one, thinks Tetris still uses a memoryless randomizer because the newest "reliable" (i.e. mainstream or scholarly media) source says so, even though the newest reliable source is years old. (The "Tetris is hard" preprint (http://arxiv.org/abs/cs.CC/0210020) is from October 2002, after Tetris Worlds was published but before the permanence of its changes to the formula became apparent.) Unfortunately, I still don't know of any reliable outlet that would touch "Playing forever".

[mikehaggar]

"Tetris is hard, even to approximate." is a mathematical proof. If you are claiming it's bogus, then please show the flaw in the proof. This is not a psychological study where the author's opinion matters. Furthermore, the assumptions in this paper are that one knows in advance ALL of the pieces that are going to be generated and in the exact order, as well as assuming you have an infinite number of moves and rotations before the piece lands. Basically, they are giving you as much freedom as possible (much more than the game gives you), and they still prove the result. Please explain how ANY of TTC's guidelines negate the findings here.

[caffeine]

Mike, tepples has shown that under TTC's guidelines, you can (in fact) play forever (http://www.tetrisconcept.net/forum/../wiki/index.php/Playing_forever).

Also for the record, I like scientific experiments. You find out cool little things you didn't know before.

[colour_thief]

It was tepple's original idea that it could be possible, but I'm the one who proved it. http://www.tetrisconcept.net/forum/images/smilies/icon_sad.gif

[caffeine]

Oops, me sorries.
http://www.band-aid.com/images/products/activeLifeStyle/img6.jpg

[m:)]

To be honest, I never believe the results of any scientific studies, because most of them are just BS made up by overconfident academics who will spout any nonsense just to get papers published.

it depends on the person making the report. a lot of those people who attend the university for years and years really do care about learning.

you logic also applies to the media. you do need to take it with a grain of salt and the best bet it to look at multiple studies before drawing any conclusions.

i tend to be very skeptical myself but there is a lot of knowledge out there these days. it's really interesting how technology has changed the speed of communication.

[Billmaan]

Please explain how ANY of TTC's guidelines negate the findings here.Their result hinges on the assumption that you can be given any sequence of pieces during the game. Since the TTC guidelines mandate the use of a 7-piece bag randomizer, this is a faulty assumption; for example, you cannot receive three S blocks in a row. It's not so much that their findings are bogus, it's that they're not applicable to "real-world" tetris.

[Zaphod77]

in fact, their proof assumes a bastet randomizer instead. one that tries to give you the worst possible piece at any given time.

Then this is generalized to the fact that a true memoryless randomizer is capable of giving that exact same piece order.

Under the Guideline, the counter presumption is true instead, and no killer sequences are available for the randomizer to give.

[PetitPrince]

More papers:

Breukelaar, Hoogeboom, and Kosters (2003) Tetris is hard, made easy (http://www.informatik.uni-leipzig.de/alg/lehre/ws07_08/KT/tetris1.pdf): an alternate way to prove that Tetris is NP-complete.

Farias and Van Roy (2006) Tetris: A Study of Randomized Constraint Sampling (http://www.stanford.edu/~bvr/psfiles/tetrischapter.pdf)

Heidi Burgiel (1997) How to lose at Tetris (http://www.geom.uiuc.edu/java/tetris/tetris.ps) more way to lose at Tetris

also

Kosters' How to construct Tetris configurations (http://www.liacs.nl/~kosters/tetris/default.htm): aka automatic Tetris art. Very cool.

[PetitPrince]

Barnes, Siderius, and Gelb (2009) Structure, Thermodynamics, and Solubility in Tetromino Fluids (http://pubs.acs.org/doi/abs/10.1021/la900196b) (more visualisation/animation (http://www.chemistry.wustl.edu/~gelb/tetrominoes.html)) [via Ars Technica (http://arstechnica.com/science/news/2009/05/the-thermodynamics-of-tetris.ars)]: this team models a fluid using tetramino shapes. This must have been a lot of fun to study. Also, the animations are kinda hypnotic.

[tepples]

Breukelaar, Hoogeboom, and Kosters' paper uses a piece sequence that can be represented as a regular expression L(OJO)+OI. That'll never happen in bag (Guideline) or strict history (LJ65) and pretty much never in TGM style history. (Consider the chance of making another O when your history is ...OOJO.)

Have any reliable sources for Tetris's switch to a bag randomizer appeared in the past month?

[PetitPrince]

You've surely seen it in the news (http://news.bbc.co.uk/today/hi/today/newsid_8587000/8587211.stm):

Holmes EA, James EL, Coode-Bate T, Dee*prose C (2009) Can Playing the Com*pu*ter Game “Tetris” Reduce the Build-Up of Fla*sh*backs for Trauma? A Pro*po*sal from Cog*ni*tive Science (http://www.plosone.org/article/info:doi%2F10.1371%2Fjournal.pone.0004153#cor1). PLoS ONE 4(1): e4153. doi:10.1371/journal.pone.0004153

So after Goaste, tubgirl, 2 girl 1 cup or other intertube delicacies, play some Tetris, it helps.

[cyberguile]

very interesting.
I'm wondering if it does increase memory capacities in a very similar way

[PetitPrince]

I was listening to an old Radiolab episode about dreams (http://www.radiolab.org/2007/may/24/dreams/) when they mentioned that work of Prof. Robert Stickgold:

Robert Stickgold et al. (2000), Replaying the Game: Hypnagogic Images in Normals and Amnesics (http://www.sciencemag.org/content/290/5490/350.abstract)

They tasked several people to play Tetris 7 hours for 3 days, and asked what they saw during their transition state from wakefulness and sleep (the fancy term is Hypnagogia (http://en.wikipedia.org/wiki/Hypnagogia)). Some of these people had anterograde amnesia (inability to form new memories, in short).

They found that most people thought of or saw a game of Tetris during that pre-sleep period, even the amnesiac !
(and also the amnesiac didn't get better score over the time, suggesting that Tetris skills aren't procedurally learned)

[Zaphod77]

The bag randomizer was developed for The New Tetris, to ensure that in the somewhat near future, the pieces needed for your gold squares would show up. It is a 63 piece bag, as determined through statistical analysis.

This is 100% confirmed, even though the info is not on the net anywhere.

Authentic Tetris Games made since then have featured the standard 7 bag mostly.

[wksrdg]

Looking at some of the discussion on this and previous page, I think there are a few interesting questions related to randomizers. I have not thought through this very well so there could be mistakes in what I have written. I also don't have any knowledge of specific randomizers as such. I am assuming in this discussion that there is no interaction between the randomization and any other part of the game.

The more specific or stringent one randomizer is compared to another (in a strict sense), the more specific conclusions one can draw. But there is some value in doing an analysis for a completely memoryless randomizer, since it encapsulates every other randomizer.

But, on the other hand, there is also something that is not natural about this kind of randomizer. One can intuitively say that such a randomizer is not "balanced". Any reasonable randomizer should first be balanced, one could say. I think this a fairly open question in itself. Two decent definitions of "balanced randomizers" that come to my mind are:
1- The number of pieces handed over must all be equal within some bounded time interval repeatedly. One could also bring in number of variations into this type of definition.
2- Consider the difference between the piece that is the handed over the most and the least. This difference should not be able to increase without bound under any possibility (let the maximum of this difference be D for example).

It is worth noting that any randomizer that satisfies the second condition would also satisfy the first automatically.

I feel that the second definition is more natural and I will take it as a reference point from here on. Now, in my opinion, any randomizer that is balanced in this way satisfies a certain criteria of being fair.

Now any specific randomizer will always generate a sequence that is regular. This means that one can also test the criteria of being unbalanced or balanced (and value of D if it is so) on any particular randomizer without too much difficulty (and some trial and error). It would be nice to figure out a simple and general method for doing so for once and for all though.

Consider the most general possible sequence with value of maximum difference as 7, say D7. It isn't too difficult to see that this would be regular too. Now suppose we take any randomizer R from a more modern tetris game and find the value of D for it (lets say it turns out to be 7). Then D7 would encapsulate R, by its definition.

Also, we can note that D8 would encapsulate D7 and D9 would encapsulate D8 and so on. Now normally we would set the maximum value of difference by keeping it in some relation with field area. For example, for a field of 200, we could have something like D=10.

So what I am saying very roughly is that in some sense the idea of a reasonable/balanced randomizer provides a demarcation between general and the specific.

[wksrdg]

I was looking at some randomizers in wiki, so a few more points to add about specific randomizers (as I understood how they work).

--TGM Randomizer
Purely from the point of view of possibility
TGM Randomizer = Memoryless

But if one were intent on looking at this randomizer from probabilistic point of view, it could be viewed as assigning different 'probability distribution' for all the pieces depending on configuration it is in. Specifics would depend on initial history and number of tries.

--TGM Randomizer (with infinite tries)
This would belong to class of unbalanced randomizers too (as I used the word in the previous post), since, for example, it is entirely possible to repeat a repeated sequence of six pieces forever without ever repeating the seventh. Actually it is possible to continue indefinitely with just five pieces.

--Bag Randomizers
As I understood it, a 7-Bag is simply taking the unique set of pieces (L,J,S,Z,I,T,O) and then drawing them out one by one. Similarly, 14-Bag would be taking two such unique sets, putting them in a bag, and then drawing out one by one until the bag is empty? And then this process is repeated again?

With this definition, it would be
For 7-bag, D=1 (actually D1=7-bag)

For 14-bag, D=2
That means D2 would encapsulate 14-bag.

So actually, number of modern randomizers don't fit into the description I was giving.

As for what I said in the second paragraph of the original post, an example of it would be that if one could show (for the sake of discussion) that it is possible to play forever with D2 randomizer, then this would automatically follow for 14-bag. Actually this can be taken further than this and isn't just limited to playing forever. A relatively simple point, but still worth re-iterating.

[muf]

What bothers me is that all this research (including what you're doing right now) fails to account for the specific algorithm used as the baseline PRNG. Since (for instance) all TGM games use the standard ANSI C PRNG, you can eliminate a lot of statistical what-ifs because the PRNG follows a fixed model with certain guaranteed uniformity. Assuming any PRNG to be "truly random" is a big mistake that can seriously skew your results.

[wksrdg]

I don't know about the terms you are using. From what I can gather roughly, here is what I think.

Results can be skewed if they make statistical predictions. And if someone were trying to make statistical predictions, then yes, specific implementation of randomness would need to be taken carefully. Obviously the randomizer, on the basis of its principle alone, doesn't and can't make any such predictions.

But you can't discount categorically the value in doing analysis without assuming a specific implementation. I will try to explain my reasoning.

If one is concerned with specific questions then, on the very least, you can be sure (based on the nature of the question alone) that either it will still hold under any specific implementation or the answer 'may' change. After all any specific implementation of randomness, no matter what its statistical basis or justification may be, would still remain within the basic rules of the randomizer (I hope I am making sense).

In particular, it would be nice to see someone taking up a randomizer that is reasonably interesting and then trying to show some properties.

Also, it seems that any analysis based on TGM Randomizer would be more useful under a specific implementation since otherwise it becomes too basic. It would just be better to assume a memoryless randomizer in that case.

[muf]

I don't know about the terms you are using. From what I can gather roughly, here is what I think.

PRNG = Pseudo-Random Number Generator. Basically, the baseline "memoryless" randomiser that all the specific randomisers are based on. Bag randomiser uses it to fill the bag, and the TGM randomiser uses it to roll and re-roll piece choices, etc. If your rand() function can be guaranteed to (or guaranteed not to) exhibit certain behaviour, then it's pointless to carry the possibility over into your analysis. What mainly triggered me was your statement of "Actually it is possible to continue indefinitely with just five pieces". I'm fairly sure that most programmatical pseudorandom generators can guarantee that for any given seed, all 7 numbers will show up at least x times in every n generated numbers. That wipes out a lot of stupid assumptions about the remote possibility of edge cases like only 5 out of 7 tetrominoes appearing in an entire random sequence.

EDIT: You might also be interested in checking out these threads:
Randomizer theory (http://tetrisconcept.net/forum/showthread.html?t=512)
Questions about Randomizers (http://tetrisconcept.net/forum/showthread.html?t=1735)