It is hard to find a game that has a truly good AI ( when I say "good" I mean the AI that functions well as a challenging opponent and/or a useful ally, it plays the game well, it is not easy to exploit, and provides a fun gaming experience) .

Which game do you think have the best AI for their genre (I figure it was better to break it down by genre because it is hard to compare a shooter AI to a turn based strategy AI).

(Edit: you do not have to name one for each genre, but feel free to list as many as you like)

What is the best AI for a:

First Person Shooter

Action Game

Adventure Game

Role Playing Game

Real Time Strategy

Turn Based Strategy

Vehicle Simulation

Sports Game

(Feel free to add a genre if I missed one)

It mostly depends on the type of game and the gameplay, but for a RTS, SC2 has a very good AI when played on Very Hard (Insane is just the same but with some cheating). The AI doesn't know where you are, or anything about you, and it constantly tries to scout to learn more about you. Although it starts to get a bit flawed when resources run out, in 30+ minutes games.

For a FPS, FEAR had a good AI, but I think this was true mostly because the game took place in buildings where there's not much open space.

Hmm. That's a good question. I have had some occasions where I was actually surprised by the AI doing something quite clever. I have to say the best shooter AI I've seen was in Crysis 2. Those enemies will actually attempt to outwit you, scout for you, cover each other, try to drive you out of cover...it's nothing that other games don't do too, but they seem to be less scripted and more emergent, and they can be quite impressive.

For teammates, the best AI I've seen was in Republic Commando. Funny and personable allies, of course - but more importantly, whether you micromanage them or not, your teammates are helpful and follow your lead nicely.

I guess flight sims would go under vehicle simulation? The AI in IL-2 Sturmovik is pretty decent and I understand the latest patch made it a lot better. I have not patched the game myself since apparently the patch introduced a couple of bugs as well, but one player was quite effusive in his praise of the new AI and the old one was good.

For sports, here is my opinion:

Pro Evolution Soccer 2012. Seriously, they advertised Active AI on the product. And it actually really active. Usually in football games, your team-mate (AI) always kinda dumb and relied too much on you to decide what the next step. But in PES 2012, they actually move by their own; find space, make themselves available for pass, decoy run, stay tight to the opponent (in front of them) who's has been assigned marking duty. No need to press run trigger all the time like FIFA. They're not perfect but currently it's the best out the in market (sports game AI).

Stalker has excellent AI for a open worldish RPG/shooter hybrid. Watching the game world do it's thing with the inhabitants in day to day life is breathtaking. Enemies think and do just like you in a firefight, or when hunting. My word, watching the animals hunt one another is creepy because it mimics RL wildife so believably.

For pure FPS, killzone 2 and resistance 1-3 should get a mention. Enemies in both games display intelligence when under threat.

Yeah, FEAR's AI was good, but it could rely a lot on scripting and "cheating," since the game was very action based (so once they were alerted they could get away with omnipotently knowing where you were) and took place in mostly enclosed environments. Now Far Cry 1...THAT game had some impressive AI. They would actually work together to hunt you down. As an overall package, I think FEAR is an absolutely marvelous FPS/Horror hybrid. Great action, a pretty good story, an awesome atmosphere... the only problem with the game was that it could get a little repetitive.

For the strategy genre Galactic Civilizations II is remarkable. I seem to recall that the A.I. doesn't cheat at all it just considers absolutely everything each turn which I am much to lazy to consider. Almost any review of the game is sure to bring it up.

For TBS games, the question can't really be answered without specifying the criteria for "best" and "TBS" beforehand.

If by "best" you mean "likelihood to prevent a player victory", then the best TBS AIs are obviously Tic-Tac-Toe and "Connect Four", since these AIs can prevent a player victory with 100% certainty.

If by "best" you mean "likelihood to win the game without cheating", then the answer is probably Chess (because in the two games mentioned before, players are usually skilled enough to prevent an AI victory as well). Chess is probably the TBS game where the the AI has evolved the farthest beyond the average player's skill.

Now, all the games mentioned so far are board game conversions, and are much simpler than any 4X / empire building games. So if you exclude those "simple" games from the list, the answers will obviously different.

"Galactic Civilizations" has a very good AI, however, this comes at the cost of the game's atmosphere. The game was designed from the ground up to be manageable for the AI, this is the reason why the technology tree consist mostly of iterations like "Diplomacy I", "Diplomacy II", "Diplomacy III" etc., which just increase the same bonus(es) successively. While this made it easier to program a challenging AI, some players complained that the gameplay felt bland.

Personally, my pick would be "Civilization IV + Better BtS AI mod". This AI is _less_ challenging than the one in GalCiv, but its task is also much harder, since Civ4 hasn't been designed specifically for the AI. Given how complex this game is, the AI does a tremendous job. It also handles mods very well, i.e. you can confront it with totally different techs, units, buildings, etc., and it will still be able to make meaningful decisions.

The AI does get the benefit of knowing what settings are best for any given situation and then using them, though. In theory you can be overshot, in level flight, in a 500kph plane by one that can only do 400kph if you're making a bit of a mess of things and the AI is optimizing the living shit out of acceleration. On the other hand I tend to fly German planes (especially the Fw 190-A8 and Me 262) which tend to be vastly superior to anything they will come across, so I can't really complain.

FEAR 1 AI was designed to take advantage of level layout, multiple paths to player's hiding spot, multiple possible cover positions and other funny stuff, like the ability to shoot mines poorly hidden by the player. Many firefights display different AI behaviour when replayed.
Then some brain-dead idiots turned the levels of FEAR 2 and 3 into cover-based tunnels, which eliminated most of the AI tactics. Who, the guys who spotted you half a mile away? I didn't get fat into the game, gave up on the arrival of mutants. Ugh... The catch about IL-2 AI is that it doesn't know the word "random". That's how the replays there work (and get broken with every patch) - the game records starting conditions and the players' actions while the rest is predetermined and calculated based on that. There won't be surprises - a pilot who starts the mission by diving will do it every time.
That and I hate the AI's kamikaze attitude and the lack of self-preservation.

Half-Life 2 and its episodes.

The AI of the Elites in Halo: CE.

As far as racing games go, Total Immersion Racing from back-a-day deserves an honourable mention. The AI itself was fairly methodical, but it had a feature where you could piss off the AI drivers so much that they'll start ramming you and making irrational mistakes.

It's a shame that the feature was shoved down your throat - it had bright icons above the cars to tell you in what sort of the mood the driver was in - but it did lend the AI a lifelike quality.