On the weekend Terminator: Salvation opens, check out this article in New Scientist on "Nine Games Computers are Ruining For Humanity." We're basically looking at the usual suspects--chess, checkers, tic-tac-toe, and more recently poker. My thought on this has always been: Wake me up when the machines start kicking ass at Diplomacy.
For those who didn't waste their early years under the thumb of The Avalon Hill Game Company, Diplomacy, first published in 1959, is a social experiment in the guise of a World War I era wargame. Each player is one of the Great Powers, from Britain in the West to Turkey in the east. Each turn represents a season of the year in which the player may move his armies and navies a limited distance on the board. Warfare is a simple matter: the country with the most armies or navies in support of its move wins. The genius of the game is that the Powers' strengths are calibrated to the point that it is impossible to win or even survive without alliances. As the rules politely state, "Diplomacy is a game of promises kept, and promises broken."
The game builds in a period between each turn for players to negotiate: 30 minutes before the first turn and 15 minutes between subsequent turns. This makes Diplomacy interminable face to face, but with adjustments it has proven perfect for playing by mail (and nowadays by e-mail). Anyway, after the negotiation period, players submit their orders in a specific language developed for the game. If an order is not expressed correctly, it does not occur. A simple example would be that if Turkey wanted to move an army to Constantinople to Bulgaria, the order would have to read A Con-Bul. If the army moving from Constantinople was moving to support an attack of another army, it would add an S and then list the army it was moving to support (A Con-Bul S A Rum-Bul). Orders are open and read and carried out if possible. Needless to say, this required specificity means that one of the most effective ways to stab someone in the back and retain some plausible deniability has always been to screw up the order on purpose. Head to Boardgame Geek for examples of Diplomacy perfidity. (My favorite is probably the father who taught his son how the world really works by solemnly sealing an alliance, showing him his written orders, and then through slight of hand, replacing the order with a blank piece of paper).
Programming the computer in the Dip "language" would be easy enough. Additionally, there has to be an optimal play for each Power in each turn, and no doubt that could also be determined. I would think that the problem might be, as I said above, that you are almost never in a position to make the optimal move on your own. Establishing what should be done is the easy part; convincing another player or a group of players to assist is the difficulty. So assuming you played by e-mail, the computer would have to be programmed to propose alliances, analyze proposed alliances from other players, decide when to abandon a partnership, determine when a partner is about to deliver a well timed stab in the back (how do you express "untrustworthy son of a bitch" in binary?) and how to respond to that action.
It could also create an interesting Turing situation--should the human players even be made aware that one or more of the countries in the game would be played by software? They probably shouldn't. Honestly, one of the things you have to deal with in Diplomacy is the meta-game--the emotional effect, i.e. simmering rage, your action will have on your opponent. If you know what you do will have no such effect on one of the players, and also no impact on her later dealings with you, you would probably feel freer to backstab her versus another player. (To be fair, if you know that one of your opponents will never renege on an agreement once made, that is temporarily a point in favor of that player, but to win the game, eventually you will have to abandon an agreement, or at least be able to entertain the possibility.)
So bumbling through this, the key here isn't so much the number crunching because that part of the game is simplified enough (there are not that many pieces in the game and the situation on the game board is open) that it can be easily grasped by the human mind; the machine doesn't have its usual advantage in that area. What a computer would need to compete in Diplomacy is the ability to read human beings' intentions (which is no doubt coming) and the ability to mimic human behavior by convincingly lying its ass off, which one hopes is a little further down the road.