melty wrote:I personally would like to (and have started designing in my head) see a bot that solves diplomacy to Winter 2012, (because of the 2012 prediction, and no game will ever last that long). Then you could do different things to the AI to determine moves, (like # of Wins for Bot Country - # of Losses for Bot Country, pick the highest, or do the same thing, only weight it based on how often the move happens, ect) and get a good bot! Any ideas on what language this should be done in?

Warning: I may have taken this question a little too seriously ... and my questions may be slightly technical, depending on your background

1) I don't think diplomacy cannot be solved. Certainly the traditional meaning of solving applies to combinatorial games, and to apply that to diplomacy doesn't work. If you attempt to do so, you realise that for each player (in diplomacy), for all possible moves on move 1 there are a set of opponent's moves (including all 6 other players) such that for all your possible move 2's there are a set of opponent's moves such that ... ... for all your possible move n's (for some specific n that I don't know) there are a set of opponent's moves such that you have lost. Therefore no country has any moves with a maximin value above a forced loss. Therefore any result above losing you gain is due to your opponents helping you, in a game-theoretic sense.

The above is true for all countries, therefore no country has any moves that guarantee above a loss. However, everyone can't lose in the same game. Therefore I conclude that diplomacy cannot be a solved game, in the normal sense.

2) So I try to define a sensible substitute for solving. This gets a little tricky (so I invite anyone to jump in if I make a mistake here) but using any metric where each player is minimising the chances of their being eliminated, I cannot see how 'perfect' players would ever eliminate a player. If we believe that, at the beginning of the game, any 4 country combination can beat the remaining three countries (a plausible claim, even if I can't prove it) then clearly there is no forced way to get to a three-way draw. I actually feel you shouldn't get below a 7-player draw because at the point at which 1 player is soon to be eliminated, the countries that would "logically" be eliminated next would work to prevent that first player leaving (in some sort of vague perfect-playing universe, they could always see this threat coming early enough to fight it). I'm not sure this makes sense, however, as if all players assume perfect play then it can be comfortably assumed by all players that they can eliminate other players safely (ie without someone being able to win) up until just before that would-be-winning player is actually able to force the win against complete cooperation against the other opponents. This last point directly contradicts my previous (ie 'players can safely eliminate others whilst still getting a draw' goes against 'players who are next to lose out will help the first to lose out at an early enough period to avoid them actually losing). Can anyone help me work out which of these is right?

Btw, it's obvious neither of these actually apply to diplomacy as we play it. But melty mentioned solving diplomacy, and since I read that I'm getting quite frustrated that I can't really resolve point (2) in my head.

Also, sinnybee's point (4) above is quite interesting - presumably any attempt to 'solve' (using whatever substitute meaning you can) diplomacy would actually be finding best play for each country from any particular position, rather than just starting from the starting position and analysing potential positions from there. I guess the former will cut down on the computation required - is that true? (And yes, I'm aware that in practical terms neither will ever be possible, I'm just curious about whether my instinct for which should require less computation is correct).