3 ms·

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 th

by Iv 15y ago

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"

qntm 15y ago
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.
- T-R 15y ago
  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.
  - qntm 15y ago
    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.

by Iv 15y ago

qntm 15y ago

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.

T-R 15y ago
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.
- qntm 15y ago
  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.