I would say that it's best to start with turn-based games, like Bridge or Chess or (shameless plug) Ambition (and if you take on Ambition, let me know how your AIs do). Some games, like Othello, aren't hard to beat. Or you could do one of the German board games if you want to take on a more heterogeneous environment than in, say, Checkers.
This will get you familiar with game AI as a topic. Then you want to take on RTS and FPS games, which are similar but have deadlines (frame rates) and more complexity in the environment. But it's important to get the basics down before taking on a complicated game.
Comments
I would say that it's best to start with turn-based games, like Bridge or Chess or (shameless plug) Ambition (and if you take on Ambition, let me know how your AIs do). Some games, like Othello, aren't hard to beat. Or you could do one of the German board games if you want to take on a more heterogeneous environment than in, say, Checkers.
This will get you familiar with game AI as a topic. Then you want to take on RTS and FPS games, which are similar but have deadlines (frame rates) and more complexity in the environment. But it's important to get the basics down before taking on a complicated game.