Rly like that game too, did you try it with alpha beta pruning? should considerably speed up the "look into the future" thing compared to simple min/max
Agreed. Another way to optimize it is by running the animations and the AI on separate threads. The deeper the search tree, the better the AI performs, irrespective of the heuristic used.