I think writing a good AI is a tough job for a good game and I think there is big difference between writting a good AI for a game like chess or CIV. I was able to beat all game, CIV, MoO... in the hard level, if I had enough chance to be an avarage situation. Finally you should try online game if you are looking for a real chalenge. I remeber that I used to beat computer very easily when I was playing AoE II when I was playing 2 V 4. I used to build three layered walls to protect myself and kill 1000 units in each round. I thought I was a master so I treid it online and I found some RI which really kick hard. In the same time I used to play WC II with my freiends and I could easily beat them, but what I found in the net was different thing. It was like I was playing against a super-computer.
I have to say that among good chess engine the Frits obviously is the best. I have nver seen any preson in my real life to be able to beat a chess engine.