Hatetris: Tetris That Hates You | Hacker News Reader

Hatetris: Tetris That Hates You

qntm.org

75 pointsPieSquared19 comments

A guest on Speed Demos Archive had an impressive 20-point game:

"56AA AAAA AAA6 AAAA AAAA 8AAA AAAA AB55 AAAA AAAB 00AA AAAA AA9A AAAA AAA6 0AAA AAAA A96A AAA8 AAA9 A808 AAAA AA9A AAAA AAAB 55AA AAAA A82A AAAA AA97 5AAA AA9A AAAA A6AB 5AA6 AAAA 6AAA AAAA C02A AAAA AABF BEAA AAA9 E9AA AAA9 AAAA AAFE AAAA AD5A AAAA F0AA AAA9 BF00 AAAA AA9B AD56 AAAA FC02 AAAA AABA C02A AAAA AB5A AAAA BAAA AAB6 AAAA AB55 6AAA A02A AAAA A82A AAAA ACAA AAAC 02AA AAAA FE9A AAAF EAAA 9D5A AAA9 6AAA AD57 AAAB C2AA A9BF 00AA AAA6 BBF0 0AAA AABA D56A AAC0 2AAA AAD6 AAAB AAAA DAAA A80A AAAA 82AA AAB5 5AAA B2AA A0C0 AAAA AFDA AABF AA9D 5AAA 5AAA 57DA A6AB C2AA 6FC0 2AAA 6BBF 00AA AAEB 00AA AA03 5556 AA02 AAA8 282A AB0A AAB2 AAB6 AA9D AAB5 02AB 55AA 80C2 AAB0 22AB AAD6 AB55 AA00 AA40 AA79 A"

http://speeddemosarchive.com/forum/index.php?topic=11523.msg...

  	--- hatetris.html	2010-04-10 03:37:17.491337444 +0100
	+++ Downloads/hatetris.html	2010-04-10 03:32:08.264902582 +0100
	@@ -65,6 +65,8 @@
				var replayOut;
				var replayIn;
				var replayTimeoutId;
	+			var gravityTimeoutId;
	+			var gravityInterval = 500;
	 
				// draw the current scenery
				function drawWell(thisWell) {
	@@ -415,6 +417,8 @@
	 
					// take user input
					document.onkeydown = keyhandler;
	+
	+				gravityTimeoutId = setTimeout("gravityHandler();", gravityInterval);
				}
	 
				function showReplay() {
	@@ -554,6 +558,14 @@
					}
				}
	 
	+			function gravityHandler() {
	+				var down = 2;
	+				var gameContinues = transformHandler(down);
	+				if(gameContinues) {
	+					gravityTimeoutId = setTimeout("gravityHandler();", gravityInterval);
	+				}
	+			}
	+
				function keyhandler(event) {
	 
					// only handle one key at a time.
	@@ -626,4 +638,4 @@
				/></p>
			</noscript>
		</body>
	-</html> 
	\ No newline at end of file
	+</html>

Interesting!

I particularly like the fact that the author's top score was five lines and he has absolutely no idea whether it's possible to come up with a strategy to beat the machine (it's completely deterministic).

edit: I've been thinking about it some more, and what's interesting is that you ought to be able to analyze it using regular game theory and prove interesting things about it. There must be an optimal strategy for both players, and there ought to be some highest possible score on the assumption that both players play with optimal strategy. Even if this game is too complicated to fully analyze, perhaps thinner games can be analyzed completely? For instance, is it possible for the computer to prevent the player from getting any lines in a 4x4 game? I _think_ two S shapes, a square and an L would do the trick, but I could be wrong. What if it were four wide by eight high?

If his algorithm is correct, it is known that it is possible to guarantee a loss in truly random Tetris with the right sequence of Ss and then Zs; you can force a hole, and this means that the player must eventually use.

Now, he may not be implementing his "worst possible piece" algorithm correctly, and it is certainly the case that the requisite sequence of Ss and Zs will take its sweet time about killing you.

It looks like he's choosing the worst piece by looking one step ahead. In general, choosing strategies this way can back you into corners. I'd be interested to know whether in this case, looking ahead 1 move is enough to get a global win as well (for the AI).

The paper "How to Lose at Tetris" (http://www.geom.uiuc.edu/java/tetris/tetris.ps) says that you don't even need to know what the player is doing. And that even almost all [1] random tetris games are bound to be lost, even with perfect play.

[1] "Almost all" is a technical term in probability theory and means "with probability 1" (which is not the same as "all games".)

I wonder whether that is equivalent the same technical term from set theory which mean "all except for a finite number of exceptions", and thus with a finite underlying set, it's correct to say that "almost all" elements have a property when in fact none of them have it...

It's similar, but with a finite set it wouldn't show up unless you had some outcomes have probability 0 (in which case, why not just delete them from the outcome space?).

Where you need the idea is in continuous spaces - like a uniform [0,1] random variable. With probability 1 it's not a rational number, etc.

It'd be funny to port this to the Android Market, label it as just another tetris clone, and wait for the reviews to start coming in...

I played for a couple of minutes, and I already want to punch someone.

Really cool though!

I got the five points he did without too much difficulty, but going beyond that seems difficult. This is fun!

replay:

  D516 AAAA AAAA B55A AAAA AAA5 D6AA AAA5 D6AA AAAA 95D6 AAA9 5DAA A5D6 AA9D AAAA AAAA 9DAA AAAA A9DA AAAA A9DA AAAB 5AAA AA9D AAA9 7A87 00AA AAAA 956A 0055 BAAA AAAA AEAA AAAA EAAA AAEA AAAE AABA AA0E AAAA AAAB CC2A AA2A AAA9 8CAA AAAA A82E AAAA AAC2 AAAA A0EA AA83 AAA8 3AA8 0CAA AAAA A80D 5540 2A7A A5DA A00E AAAA A80C AAAA A80C AAAA 00DD AAA5 EAAD 55AA BAA8 3FC0 AAA0 4D55 6A9D AA4E A83A A803 DFCE A82A

6! This is a cool game.

"55AA AAB6 AAAA F6AA AA9A AAA2 AAAA AAAA 009A AAAA AAAA A977 0AAA AAAA A755 AAAA AA40 02AA AAAA AAC0 6AAF AAAA AAC2 6D54 30AA AAAA A805 400A AAAA AAB2 9AAA AA9D AAAA AAAB 0000 2AAA AAA5 AAAA AAA0 AAAA AAA3 0FD5 575A AAAA A94A AAAA AB55 6AAA AAAA AAAA 0756 AAAA 9D56 AAAA 752A AA9D 5AAA 9DAA A756 AB5A A0C3 5EA6 AAAA 0D6A AAAB 2AAA A000 03DC AAAA AA0D 555A 80EA BF4A AAA0 02AA AA83 AAAA 81AB DAA0 05D5 6A80 A9AA 36AA 002A AAD5 5AAB 1A80 AAA0 02AA B5A8 0DAA A8"

Mandatory xkcd reference: http://xkcd.com/724/

You can play it here: http://www.geekosystem.com/xkcd-tetris-hell-game/

This game would be much more punishing if it did not keep repeating the same piece over and over again. The way that a piece would repeat itself until just before a line is cleared makes the game's AI way too obvious.

And now, we can up the problem even further:

Build a tetris clone which forces the player to "win" with 13 lines scored.

l-tris has a hardmode which is a similar idea... although it plays like tetris rather than a logic puzzle.

It gives me nothing but S-pieces. I've had one 4-line bar. Hardly fun. Hardly interesting.

I can create a tetris clone that only gives one piece as well.

He warns that the preferred piece is an S in the docs. But I was able to force the game to generate squares and lines with "good" play. (I could predict by the end which piece it would pick with reasonable accuracy.) To do better (at least based on my watching the high score replays), you have to intentionally "play badly" and make gaps that open up if you clear a middle row of the gap. The 17-replay I saw generated tons of lines, which I honestly wouldn't expect this app to generate.

Reply on news.ycombinator.com