Comment by T-R | Hacker News Reader

Comment by T-R | Hacker News Reader

Parent Full thread

It might be a good idea to look at it as an induction problem - one state leads to another, and since a lot of states are effectively the same, it means the tree can be pruned.

Let's say the player has a row that's almost full - say, one spot left to fill all the way on the right. That means the AI needs to not give the player any block that would let him fill it (I,J,L,S,T) - so the player can force the AI to just give him O and Z blocks. If the hole isn't against the wall, the AI can only give O blocks. There are only a few, if any board states where the player cannot create a line using only O and Z blocks - the player just needs to make sure he doesn't loosen the restriction on the AI (such as by covering the hole).

If the hole is 2-wide, depending on the hole's depth, the AI may only be able to give T blocks, if even that, and for most board states, you'll probably find that T blocks can be used to make a line without loosening the restrictions on the AI.

You have 10 columns and you need to consider at least 4 rows, to account for the possibility to make a line. That means 2^40 different possible states, and I think that most of them are reachable with the rules of Tetris. It could still be implemented with a hash_table and yield interesting results, but it is still possible to fill up the memory with such an algorithm.

Before using such an approach, I think it would make sense to find a compressed way of representing a state. I think it would be workable to have ten "heights" describing the enveloppe of the structure and to add 3 bits to describe the presence of "holes" in the 3 bottom lines (the presence of holes in the top line can be inferred in the enveloppe information).

That would give us 2 bits of height per column, plus 3 bits for hole presences. 2^23 : a more manageable state space of 8 millions.

Such a representation is not enough to have a good AI or to even make a completely evil AI but it fills the bill when it comes to solve the problem at hand : "prevent the player from making even a single line"

You're suggesting using 2 bits to store the height of the column, plus 3 bits to store the presence of holes, for a total of 5 bits per column. Exactly how you got from that to a figure of "2^23" I don't know. That's actually (2^5)^10 = 2^50 possible column combinations.

Why not just use 4 bits to represent the whole column? That's (2^4)^10 = 2^40, exactly where we started.

In fact, look at rows instead. With 10 columns and 4 rows there are, to be more precise, (2^10 - 1)^4 possible states.

And the majority of which have "floating" (disconnected) sections which, while reachable with the rules of Tetris, cannot be reached without making at least one line.

In case you didn't read the article, Tetris has been solved for width 10 height 4: the AI wins. The same is true for width 10 height 5. We need to go further.

I don't think he meant for the 3 bits to be per-column, I think he meant 3 bits total - one for each row below the top, meaning "does this row have a hole that is covered? (and as such, cannot be cleared unless a line above it is cleared)". This effectively turns all board states with the same exact topology and potential for clearing lines below the surface into the same state.

I think his overall strategy is similar to a point that I intended to make - that there are large sets of states that are effectively equivalent, and treating them as such reduces the complexity of the problem. Not that dissimilar from alpha-beta pruning or branch-and-bound.

Ooh. That's actually cleverer. It reduces the space of possible wells quite substantially. It does make detecting a horizontal line more difficult, though. I will think about this.

Reply on news.ycombinator.com