[a3_nm]

Ah, right, so the real problem is still open. :-)

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

[qntm]

Alpha-beta pruning sounds like a reasonable route forward. In this case, each "well" is a state in the game and placing a new piece in the well constitutes a move to a new state. Since the "heuristic value" of a move is absolute (player wins or AI wins), I already have stuff in place to exit early from an exhaustive evaluation of all possible landing points if a definitive answer is found. But I don't have anything in place to put those landing points into an optimal order for evaluation purposes. A Tetris-playing AI which can quantify the "goodness" of a move would be useful here, and that's entirely possible.

Intelligent caching is possible but I think it would be difficult for me to implement and I'm not certain that it would yield much benefit.

Actually, the procedure for identifying all the possible player moves is very fast already and I think making it prioritise "easier" moves would slow it down. In particular, ruling out or de-prioritising simple things like "tucking" a piece under another is very counterproductive.