I didn't examine the code very carefully, but here are some sensible things that you could do and that I'm not sure you're currently doing:
- Are you doing alpha-beta pruning? http://en.wikipedia.org/wiki/Alpha-beta_pruning
- Instead of either caching everything or nothing, choose a cache size, cache things and flush the least used ones when the cache is full. (More intelligent things are possible there.)
- Explore the player moves in a clever order to avoid getting bogged down in useless branches. You could use an existing tetris AI to pick sensible moves for you and examine them first, or use simple heuristics.
- In the same spirit, since you seem to be using an exact but complicated (and costly) way to compute possible player moves, it might make sense to first explore a subset of moves which is easier to compute. For instance, examine first the moves which are just an horizontal movement, a rotation, and a straight drop. Maybe there is a winning strategy for the player which mostly uses such moves.
- I am not sure of what you cache. There is no point in caching the whole well, just caching the lines with a reachable empty space. Also, hitting any configuration from the cache is deadly (since it means we went higher and went back to an equivalent configuration).
Hopefully this is sensible and isn't stuff you already do. I'd be quite interested to know the definitive answer to this problem. :-)