Exactly one of the following statements is true.
Which one?
Prove it.
I created HATETRIS in 2010 because I wanted Tetris players to suffer. It was something I created for my own amusement and as a programming challenge and to investigate the use of JavaScript as a gaming platform. HATETRIS is a version of Tetris which always supplies the worst possible piece.
HATETRIS explores only to a depth of 1. It looks at the immediate future and chooses the single worst piece for the present situation, ignoring the possibility of the player using the current piece to set up a situation where the second piece forces a line. After the first iteration of the game, I started using a bit mask to express each row of the playing field ("well"), which made testing the insertion and removal of possible pieces faster, to the extent that a new piece appeared more or less instantly instead of appearing after a second or two. This improvement allowed the algorithm to be improved to look a second piece into the future, while taking more time. This made the game sluggish, though, so I never left this modification in place.
The other reason I didn't leave HATETRIS to look at depth 2 was because the game was still too easy. Even looking two pieces into the future it was startlingly easy to contrive situations whereby no matter which pair of pieces was supplied, the player could always force a line. Consistent scores of 2 or 3 lines did not satisfy me. HATETRIS+2 wasn't difficult enough. I noted that I intended to return to the project just as soon as I could create a game which never permitted the player to get lines. Ever. I determined to create the evil AI from case 2.
About a year passed and I finally got around to thinking about the problem again. After some additional thought I decided that the chances were that case 1 was actually true. The player can always get a line. But how to prove it?
"Tetris", the mathematical structure, has to be well-defined before it can be solved. In fact there are numerous implementations of Tetris with subtle distinctions. This is fine, as long as we are clear which implementation we are working with.
The "standard" Tetris well has a width of 10 and a height of 20. The piece enters the well from above.
In "standard" Tetris the piece spawns in rows 21 and 22 which are hidden off the top of the screen. Since it's possible to rotate a piece at this height, causing many of them to protrude higher, we can infer the existence of a row 23 as well.
In HATETRIS, 4 full rows of spawning area are provided, and pieces spawn in the middle, across rows 22 and 23.
For the purposes of this piece of work, I used the HATETRIS spawning rules.
In "standard" Tetris the game is over if
This means that pieces can land with partial protrusions into the top three rows, but the game can continue. Even if a piece lands overlapping the original spawn zone, the game can STILL continue if you are lucky enough that the next piece does not spawn overlapping it.
In HATETRIS the game is over if a piece lands with any part of itself protruding into the spawning area. (This means the spawning area is always free of obstructions, with space to move and rotate each piece before allowing it into the main well.)
For the purposes of this piece of work, I used the HATETRIS game over rules.
Tetris always has 7 pieces, I, J, L, O, S, T and Z, but the various orientations of each piece are also subject to variation. Exactly what happens when a piece is rotated? In the naive case, the piece could rotate around its centre of gravity, but that would result in pieces positioned off-centre in many cases, and require floating point numbers.
HATETRIS uses an arcane homegrown procedurally generated rotation system which I do not recommend because of its quirks.
"Standard" Tetris has several systems, but the one used for this piece of work is the Original Rotation System. This cannot be procedurally generated, but generating the orientations by hand as bitmasks was trivial.
More recent versions of Tetris implement advanced functionality such as wall and floor kicks, which I omitted for the sake of optimisation. If there is obstruction or the piece would end up partially outside the well, a move or rotation is simply forbidden.
It is assumed for the sake of argument that there is no gravity (or, to put it another way, the player is at liberty to move the piece as far horizontally and rotate it as many times as they desire before it falls another row). To move down, the player presses "down".
A piece locks when the player moves down, but meets an obstruction. Thus, there is effectively infinite "lock delay".
Since 1 line is all that is needed, we can thankfully omit any procedures for restructuring the playing field after a line is made.
The question is still meaningful for Tetris wells as narrow as 4 units wide. Any narrower and the I piece can no longer spawn or rotate. A standard Tetris well has a width of 10 and wider wells are of less interest to me.
If the spawning area at the top is kept, and we only count the lines below this point, the question is also meaningful for wells as shallow as 0 units, although in the cases of height 0, 1 and 2 the solutions are trivial: the AI always wins. (Height 0: the player cannot land a single piece without losing. Height 1: the AI supplies an O block. Height 2: the AI supplies a series of S blocks.)
One quick observation will save us all a great deal of time. By supplying an endless stream of O blocks, the AI can always win any Tetris well with an odd-numbered width: 5, 7 and 9. So, the widths of interest are 4, 6, 8 and 10 only.
If the player can force a line without losing in a well of depth H, the player can do the same in any deeper well by following exactly the same procedure. So, the real question is this: given a well of width W, what is the minimum required depth for the player to win? Alternatively, prove that the AI can always win no matter the depth - or at least to depth 20, if possible.
I took this as an opportunity to become familiar with a programming language which I knew very little about, even when I used it in university for my computing projects.
There is nothing that I can say about the C programming language that hasn't already been said thirty years ago. But it's all new to me, so just let me have this.
C is a monumental culture shock to anybody familiar with modern programming languages. C is so old that the canonical reference (Kernighan & Ritchie's The C Programming Language) describes it in terms of languages with which I have literally no familiarity, such as FORTRAN and Pascal. For example, the book carefully explains that the notation a[i, j] for accessing elements of multidimensional arrays - notation which I have never seen anywhere - is illegal. At the same time, K&R singularly fail to make clear that in C it is impossible to choose the size of an array at run time. Once this fact dawned on me it made life a lot easier and, in retrospect, it is obvious that dynamic arrays would be a feature only of dynamic programming languages, which C isn't. But dynamic array sizing just wasn't there at the time, in the same way that nowadays you would never stop to explain that no, this car cannot fly.
It is enlightening and relaxing to finally find out where things like printf() and fopen() are actually invariably cribbed from; to find out what malloc actually is and why (see above) it is even necessary. It's valuable to learn the true power and practical use of memory pointers. It's cool to be finally exposed - if briefly, like radioactivity - to the layer where things like binary trees and linked lists are actually important to the process and need to be built manually.
It's also aggravating and frustrating. C's strict type safety is wonderful, except when it isn't. Its type declarations are confusing and strange. (why are the square brackets on the label, not on the data type? int[10] foo makes more sense than int foo[10], doesn't it? I'm not crazy?) Handing pointers to functions around, yes! Null-terminated strings, erm, okay. Not checking array bounds? When would that ever not lead to a catastrophic error of some description? Here's another one: "Hey, what happens if you forget to free some of the memory you malloced?"
K&R deserve all the praise they have ever received for creating a language book which is so small that it is actually useful. Ever tried to use Programming Perl as a reference? "Dear Zarquon, Larry," I think to myself every time I try, "stop punning and get to the point!" But K&R also seem to have an unbecoming fetish for extreme terseness in their programs. Their persistent omission of braces is alarming. And I hope C isn't the first programming language you learn and K&R isn't the first programming language book you read, because unscrambling
while((s[i++] = t[j++]) != '\0')
into something legible will take you a solid week, and it'll be a lifetime before anybody forces you to unlearn nonsense like
isdigit(s[++i] = c = getch())
. Never in my life have I thought that I would have to write this down, but don't do more than three things simultaneously in one line of code! I never imagined that there was anybody in the world who needed to be told that, but here we are. It's not even faster code! It's just the idiotic idiomatic style!
The basic pseudocode for the brute force algorithm is this:
who_wins(well W) { for each piece P { for each landing state of piece P in well W { well W2 = result if(that_makes_a_line(W2)) { next piece } if(who_wins(W2) == PLAYERWINS) { next piece } } // AI wins every landing state return AIWINS } // Player wins every piece return PLAYERWINS } print who_wins(empty_well)
Since it would be preferable to know who wins, and how, what I actually implemented is a little more complicated, and a full solution is returned in each case.
The major optimisation breakthrough I made when planning this program was to observe that when you consider all 7 possible pieces in all 19 possible orientations, from left to right and top to bottom in the well, there are only approximately 4000 possible states which pieces can occupy during the course of any given game. These states form a network or directed graph, joined by edges representing player input. Starting from the original spawning state, pressing Left leads to one state, Right leads to another, as do Down and Rotate. If the wall is in the way, it is possible that pressing any given key will not move the piece, resulting in an edge leading from a state back to itself. There are in fact 7 disconnected graphs of states, one for each possible piece.
Having seen this, I wrote my program to generate every single possible state in a single procedure right at the start of execution, before beginning the brute force search. During this initial stage, all the tedious calculation of bit masks, piece rotation and piece dimensions and positions and offsets is handled and then cached in a single big array for future reference. Also cached are the edges connecting states together.
Pre-calculating all of this makes several things easier, such as detecting a collision between a piece and the contents of the well, inserting a piece into the well and removing the piece from the well afterwards. But fastest of all is locating new landing sites. By simply "painting" every state as "unreachable" and then starting from a single guaranteed "reachable" spawn point, I wrote what basically amounts to a "flood fill" routine which explores the whole state space looking for accessible states (and indirectly ruling out inaccessible states) and incidentally collecting a list of those states which happen to be landing points.
In the first few versions of this program, I ignored duplicate wells and solved every single possibility naively. This allowed me to calculate a solution for a large selection of wells. The longest solution (width 8, height 7, player wins) took some 9 hours to solve. However, I suspected that some wells were being solved over and over again using this method. At length, I rewrote the program to store the results for each well in turn. This resulted in a program which ran much faster. Unfortunately, it now rapidly rans out of memory when solving the larger wells. Even more unfortunately, the new program could not generate any new results.
I used Fabrice Bellard's Tiny C Compiler to compile and run my program on Windows. I'm not in a position to compare this with other C compilers, but TCC is extremely small and fast and did the job, at a time when most of the people I asked were seriously suggesting that I switch to Linux just so that I could run "Hello world".
(Update, 2019-12-26: the latest version of TCC seems to have some kind of show-stopping compiler bug. I use MinGW's version of gcc now.)
The program:
The only two options you should really worry about are the WIDTH and the HEIGHT of the well. These are set using #define statements at the top of the code. Possibly this doesn't provide a substantial performance improvement over taking those numbers from the command line, but it was just how I implemented the configuration to begin with and I never got around to changing it.
I'm not a C expert. I'm pretty sure, though, that this program strikes a good balance between being readable and being high-performance. The most scope for improvement would be in a re-written, more efficient algorithm, with a focus on intelligence and saving memory, and less emphasis on brute force.
As mentioned, for odd-numbered widths, the AI wins by supplying an endless stream of O blocks.
Who wins? | WIDTH | |||||
---|---|---|---|---|---|---|
4 | 6 | 8 | 10 | 12+ | ||
HEIGHT | 0 | AI | AI | AI | AI | AI |
1 | AI | AI | AI | AI | AI | |
2 | AI | AI | AI | AI | AI | |
3 | AI | AI | AI | AI | AI | |
4 | AI | AI | AI | AI | AI | |
5 | PLAYER | AI | AI | AI | ? | |
6 | PLAYER | PLAYER | AI | AI | ? | |
7 | PLAYER | PLAYER | PLAYER | ? | ? | |
8+ | PLAYER | PLAYER | PLAYER | ? | ? |
Results for (width, height) = (8, 6), (8, 7) and (10, 5) were computed using tetris4.c. tetris6.c requires 13GB of memory to compute (8, 6), and runs out of memory in the other two cases.
All other results can be generated using either program - tetris6.c is recommended as it provides more informative output.
I am pleased to have completely solved Tetris for wells of width 4, 6, and 8 (and, trivially, 5, 7 and 9). I'm disappointed not to have been able to solve Tetris for width 10, but I remain firmly convinced that a player victory is inevitable there too.
I considered a method for avoiding having to "flood fill" the whole state space every time a new piece was added. Instead of painting every state as unreachable every time, we would keep the "reachability" attribute as a persistent attribute. First, we would also create and cache a list of "predecessor" states for each state. (In other words, the same digraph but with all the edge directions reversed.) For each state, we would also collect a list of other states overlapping that state.
Then, whenever a new piece is locked into the well, we would mark that lock state and any states listed overlapping it as unreachable. Then, we could do a sort of smaller "reverse flood fill", looking for all states which have now become unreachable because all their predecessors are unreachable too. When the new piece is removed from the well, we mark its lock state and all the states listed as overlapping it as reachable again and perform a conventional flood fill to revert everything to the way it was.
It's not clear whether this "flood fill / flood unfill" procedure would be any quicker than doing a conventional flood fill from the top every time. The "reverse flood fill" is much slower than a flood fill because every state needs checking multiple times. And just implementing the pre-caching of overlapping states and nothing else occupied much more memory and made my program take substantially longer to run.
I realised that if the player can force a line at row 2 (for example) in a well of width 4, then the player can simply do this twice side by side in a well of width 8. This would result in a complete line at row 2 spanning the whole well, and this would in turn result in a general solution for wells of all widths divisible by 4: 4, 8, 12, 16 and so on. If the same could be done for a well of width 6, then 4+6=10, 4+4+6=14, and so on, so we would have a general solution for the whole game!
Unfortunately I ran some tests and proved that the AI, if so inclined, can deliberately prevent a line from forming at any specific row it so pleases, even while the player creates lines at other rows. This is achieved by supplying O and I blocks in particularly mean combinations. There might be some more meat in this approach but I can't get to it.
There's limitless scope for smarter investigation of all the possibilities, and for being choosy about what to cache, freeing up solutions to solved wells when they're no longer needed in memory, and so on. But this isn't easily accomplished in C and it needs a better mathematician than me to implement. Frankly, I've lost the will to continue. If you discover any simple modification to the code which results in more results, particularly if you can prove that you can force a player victory for width 10 at any depth, please let me know. To say that Tetris has been "solved" would be awesomely cool.
Although I remain convinced that the player can always force a win in a standard Tetris well, I'm strongly considering taking the optimised C code that was developed here and rolling it into a newer, more hate-filled version of HATETRIS at some point in the future. I need a break right now though, so that won't happen immediately.
Constraining the AI to only O blocks solved the odd-numbered widths very quickly. Could constraining the choice to 6, 5, 4, 3, or 2 pieces make the process faster in the other cases?
It might be possible to sort the list of possible landing states so that states advantageous to the user appear earlier. This would allow us to exit earlier from branches where the user wins and shorten processing time.
Follow-up work by a3nm has demonstrated that yes, as suspected, the player does in fact win if they play rationally on a board with width 10.
The key optimisation they made in their exhaustive search, which I didn't think of, was to ignore piece sliding behaviour and instead simply require the player to rotate their chosen piece and drop it straight down. This simplified the problem and reduced the size of the possibility space enough to make it computationally tractable, while not decreasing the player's playing ability so much that the player could no longer succeed in making a line.
Most excitingly, a3nm also provides a playable JavaScript version of the game, where you are the AI and try (and fail) to prevent the player from making lines by providing bad pieces. The worst sequence of pieces I've managed to create, playing casually, is I, O, O, O, O, O, O, O, O, O, O (11 pieces), before piece 12 invariably allows a line to be made.
Since the player's hands are slightly tied in this scenario, the minimal amount of "headroom" required demonstrated here might not be the minimal headroom required in my proposed scenario. Having said that, defining minimal headroom, which is equivalent to defining topping-out conditions, has always been fairly thorny and arbitrary, much like defining rotation behaviour. Structuring the problem so as to avoid these questions seems like a strong general approach.
Excellent work!
Discussion (45)
2011-07-21 01:33:03 by Jack:
2011-07-21 01:36:04 by Matt:
2011-07-21 02:39:43 by MWchase:
2011-07-21 03:38:25 by AndrewJenner:
2011-07-21 04:04:49 by RyanVoots:
2011-07-21 04:07:54 by RyanVoots:
2011-07-21 04:08:24 by Marc:
2011-07-21 04:33:58 by A:
2011-07-21 04:53:18 by AndrewJenner:
2011-07-21 05:41:03 by EgyptUrnash:
2011-07-21 07:19:20 by Pete:
2011-07-21 08:39:21 by YarKramer:
2011-07-21 08:46:17 by riku:
2011-07-21 10:11:11 by ErikB:
2011-07-21 12:37:51 by Toby:
2011-07-21 12:38:58 by mech:
2011-07-21 13:35:37 by qntm:
2011-07-21 17:20:07 by Val:
2011-07-21 22:15:45 by Ross:
2011-07-21 22:36:25 by Val:
2011-07-23 04:20:14 by David:
2011-07-23 13:00:46 by qntm:
2011-07-24 19:47:52 by Repomancer:
2011-07-27 08:19:54 by LeVentNoir:
2011-07-28 00:08:00 by OvermindDL:
2011-07-28 13:23:36 by qntm:
2011-07-28 23:02:49 by OvermindDL:
2011-07-28 23:54:14 by OvernmindDL:
2011-07-29 00:10:37 by OvermindDL:
2012-06-14 22:54:32 by DSimon:
2012-06-14 22:56:22 by DSimon:
2013-01-19 00:13:26 by Helena:
2014-10-15 03:00:53 by Ionatan:
2015-07-14 01:51:06 by Ray:
2019-12-19 04:57:33 by Aquarial:
2019-12-19 21:35:28 by qntm:
2019-12-26 20:16:44 by qntm:
2022-04-20 14:49:18 by a3nm:
2022-04-25 19:10:21 by qntm:
2022-04-25 20:56:16 by Tim:
2022-04-26 13:36:13 by John F:
2022-04-27 11:05:28 by Baughn:
2022-05-09 10:06:44 by ingvar:
2022-08-26 23:27:12 by ion:
2022-10-24 21:01:37 by Rick : ):