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

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.