I've got Chessmaster 6000 (maybe its 7000, not quite sure about the number) and the best AI I've been able to beat is the Novice. Its also been a while since I last played a game. I don't think I'm all that good.
I've actually never played Risk...but I have played the shareware version of a Windows-based game called World Empire (1, 2, 3, 4, 5, etc.), which claims to be similar to Risk.