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.
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?