Calculating the perfect Tetris play: Part I

http://ains.co/blog/breaking-tetrisfriends.html

36 11 13 years ago

joosters• 13 years ago

"True randomness is hard to achieve, especially with computers."

Yes, for important cryptography. No, for pretty much everything else. Use a decent random number generator, there are many to choose from. Problem solved. Do not reinvent one.

If you are investigating the workings of Math.random() when coding a tetris bot, you are prevaricating and IMO wasting your time.

ronaldx• 13 years ago

Randomness is also useful for the integrity of online gambling - knowing what cards are coming next in a high stakes game might not be considered a waste of time.

zwily• 13 years ago

I think his point was that the game would be using a predictable RNG, which made his whole endeavor possible.

ainsej2• 13 years ago

It was sort of an interesting aside from an another aside. There are loads of different ways to write a Tetris Bot, and I've got a few different implementations varying from brute forcing the game tree to using genetic algorithms. But I figured it'd be interesting to see what could be done with perfect prediction of all the future tetrominos.

noelwelsh• 13 years ago

I thought this post was fun and interesting, and showed a great hacker mentality at work. Reverse engineering a particular Tetris implementation isn't what keeps me up at night, but I'm glad someone has tried it and shared the results!

ainsej2• 13 years ago

Thanks, glad you enjoyed it. It was a side project of mine a few months ago but they are only so much use on my hard drive, happy that people somewhat enjoyed me sharing what I've learnt

peteretep2• 13 years ago

Presumably it's got to be possible to free yourself from the constraint of a given implementation, and put together a solution for truly random pieces.

You're starting from a zero point, there's gotta be a minimum cyclic graph with each node having 7 outgoing connections for each new piece, and representing a certain configuration of blocks on the ground...

peteretep2• 13 years ago

I guess more than 7 - you have 7 * possible rotations of piece * horizontal position...

Cogito• 13 years ago

Knowing which pieces are coming next makes a significant difference in edge cases, but I'm not sure how it would affect the bot in typical play.

If you can predict the pieces perfectly you will always[1] perform at least as well as the same bot but using worse information.

[1] assuming your bot is any good.

dccoolgai• 13 years ago

Pretty sure about ten years back a team at MIT did a paper on how Tetris is NP-Complete...

croikle• 13 years ago

Note that results like this [0] tend to be for generalizations. '''It is natural to generalize the Tetris gameboard to m-by-n, since a relatively simple dynamic program solves the case of a constant-size gameboard in time polynomial in the number of pieces.'''

[0] http://arxiv.org/abs/cs/0210020

Calculating the perfect Tetris play: Part I

Related Stories