Solving Tetris in C (2011) | Hacker News Reader

Solving Tetris in C (2011)

qntm.org

48 pointsbradrn6 comments

https://github.com/qntm/tetris/blob/7c108f1f676233da9f20d831...

Just checking: are you leaving the holes intact, the fully-enclosed interior holes in the well? Because those never become relevant in the problem you've phrased -- the game ends after *one* line is filled. So interior structure never becomes visible again.

You're caching the wells that have already been visited (in that 2nd/improved codebase). But I believe the sameWell() equality test can be looser: you can identify as equal two wells which differ only by interior holes. That would make the search tree much (?) smaller.

I solved Tetris a very similar way in high school. My approach was to treat it as a zero-sum, two player game. One player assigns pieces, and the other player places pieces. Treating it this way allows using Minimax algorithm with any depth (similar to chess or other two player games!). The board evaluation function can penalize "caves" (empty orphaned spaces that have been covered by pieces above them). With a board evaluation function like this, alpha/beta pruning can be used. This gives great results!

Nice work!

I've done MiniMax w/ Alpha-Beta pruning for turn-based games and never thought to think about Tetris as a 2-player turn-based game.

FTA:

- In HATETRIS the game is over if a piece lands with any part of itself protruding into the spawning area. […] For the purposes of this piece of work, I used the HATETRIS game over rules.

- Height 2: the AI supplies a series of S blocks.

Doesn’t that mean a single S or Z block is sufficient to end the game? Those blocks always have a height of 3.

The height of the S and Z blocks is not 3 it's variable dependent on rotation. With the spawning area allowing for rotation the player may rotate the piece regardless of the well size necessitating more than 1 S or Z block to force a game over. Not to mention the spawning rotation (in Tetris and Hatetris) is the shorter one anyways.

Thanks. My brain always thinks pentominoes for “S” and “ℤ”.

Reply on news.ycombinator.com