Calculating the perfect Tetris play: Part I | Hacker News Reader

Calculating the perfect Tetris play: Part I

ains.co

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!

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

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

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.

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

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.

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

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

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.

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

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

Reply on news.ycombinator.com