Glamestris - Tetris AI

This is a tad old, but two fellows, Glen Coppersmith, and James Dennis, have made a skilled Tetris AI that can survive for very, very long periods of time. I decided to make a little video of it, because I don't think there's one yet on YouTube.

In the first part, you'll see that the game goes on and on and on. I think I remember the computer getting over 200,000 lines once. After that, I decided to add junk rows to try and mess up the computer AI. I shoved the pieces near the top, and the computer held out for a while, but then lost the game.

Music is from OCRemix: "Slavic Roots" by djpretzel

Category:

Entertainment

Tags:

• Glamestris
• Tetris
• computer
• player
• AI

[ratsouffle]

No AI is perfect?

No! AI is perfect!

[ThomasJO89]

0:17 - 0:32 That would make a great music visualization.

[KaseyBrownFitness]

Sorry but to make it lose, you had to fill nearly 3/4th of the screen with junk blocks.

As far as I'm concerned, that AI is perfect.

[dom90ish]

Nice Music

[LNOL]

It's not imperfect. You gave it an impossible task.

[TheBlueArcher]

pretty cool, The only problem I have with this video is that you didn't really let the AI handle the garbage... you pushed up the garbage to the point where it just simply didn't have enough space to move the pieces where it needed to.

[Ikkath]

@smariot I don't get what you mean by "the end of the 7 piece sequence". You have to enumerate the tree for each piece given a specific board configuration. Thus it is no good only enumerating all the possible permuations of the 7 pieces.

Try making such an AI. Your suggestion does not give it enough information to navigate the space correctly.

I really should put some videos up on here of my Tetris AI. It has gotten (in its only ever run) 490 million lines before my PSU failed.

[smariot]

The AI is allowed to violate those restrictions, creating gaps if it so desires, the restriction only applies to the end of the seven piece sequence.

The lookup table can be generated as thus:

1: Set every state to 'not-safe'.

2: Iterate through each state. If it is not marked as safe, set it to safe if all 5040 possible sequences can be forced to the current state or any other state maked as safe.

3: Repeat step 2 until you've made a pass in which no new states were marked as safe.

[Ikkath]

@smariot Those assumptions are too strict. You can't assume that the best position for a given piece will _never_ create gaps - such a strategy can be shown sub-optimal for even a few pieces.

It isn't really a space problem. You have to compute if the move is "safe" for each possible sequence of pieces to populate this lookup table. This is what is the core problem. See Checkers was recently solved. The table is trivial once you have it.

[Ikkath]

@smariot Sorry I meant to say that too. Though in this case it matters not, the problem is still just as intractable with 5 unique pieces as with 7 (I think).

A crude upper bound on the number of states that needs checking for "safety" is astronomical: 2^199 (you can do better than this). Enumerating the entire game tree would allow you to play perfectly - though this is clearly impossible with current hardware. Perfect play however doesn't imply infinite play.

[smariot]

If you assume a maximum difference in adjacent column height of 4 blocks, that a perfect player will never create gaps, and that the last column will always remain empty, this creates a total of 387,420,489 possible game states. It could fit in a precomputed lookup table occupying 46.2MB.

[smariot]

I was just informed by my invisible friend that there are in fact 7 possible pieces, not 5. As such, there are 5040, 720 with the current piece known, and 120 with the next piece known.

In conclusion, I'm an idiot.