I'm looking for some new games to get for the summer. What I'm mainly looking for is a game with clever AI, no matter which genre. RTS, TBS, action, tactical, sports (mainly ice hockey), and maybe also RPG. I would like to find a game with AI that is varied, difficult to predict, where the AI skill isn't achieved through AI cheating or something simplistic like giving the AI godlike aim in a shooter. Alternatively, if the AI isn't that complex, it should at least take long before I discover exactly how it works and how to exploit it systematically.

Some games I've been thinking about: Histwar, ArmA, full spectrum warrior, one of the many ww2 strategy game released in the latest 5 years (which one is the best?), STALKER, some combat flight simulator. I'm also considering getting some very old games, if they're strategy/tactical and feature very good AI, even if the graphics are bad.

What are your experiences with these suggested games? And where I have mentioned a broad genre, which particular games would you recommend?