4 ms·

Calculating the perfect Tetris play: Part I

joosters 13y 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 13y 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 13y ago
  I think his point was that the game would be using a predictable RNG, which made his whole endeavor possible.
- ainsej 13y 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 13y 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!
- ainsej 13y 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
peteretep 13y 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...
- peteretep 13y ago
  I guess more than 7 - you have 7 * possible rotations of piece * horizontal position...
- Cogito 13y 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 13y ago
Pretty sure about ten years back a team at MIT did a paper on how Tetris is NP-Complete...
- croikle 13y 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 http://arxiv.org/abs/cs/0210020

"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 13y 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 13y ago
I think his point was that the game would be using a predictable RNG, which made his whole endeavor possible.
ainsej 13y 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 13y 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!

ainsej 13y 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

peteretep 13y 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...

peteretep 13y ago
I guess more than 7 - you have 7 * possible rotations of piece * horizontal position...
Cogito 13y 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 13y ago

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

croikle 13y 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 http://arxiv.org/abs/cs/0210020