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