Page 3 of 3

Re: Bot?

PostPosted: 24 Nov 2013, 05:14
by Rolan A Doobie
melty wrote:Limiting it to winter2012 gives diplomacy a finite number of positions. I picked winter 2012 because of the prediction, and that no game would ever make it that far.


First, setting any kind of time limit results in a finite number of positions. Your choice of year is not remotely unique in that.


But if your only criteria is --
A) Year must include a prediction for the end of the world
B) No game would ever make it that far (in your estimation)

---- Then I'm still curious as to why you chose 2012...instead of any of the years between 1975 and now in which similar earth-ending predictions were made, because no game would ever make it that far either, right?

For that matter, it seems best to just end your simulation in 2000. No game would ever make it that far, there was the Y2K prediction (among others), and it's an even 100 years from your starting point.

Re: Bot?

PostPosted: 24 Nov 2013, 05:19
by sinnybee
melty wrote:Limiting it to winter2012 gives diplomacy a finite number of positions. I picked winter 2012 because of the prediction, and that no game would ever make it that far. If in analasis a game reaches there, then it would be considered a loss for all sides. In the first year, there are anywhere from 0 to 21 moves possible per season, so the first year would be the easiest to solve. The Winter building has 0-21 possible builds total, with different variations in location and A or F. Year two there are anywhere from 0-42 pieces, and I think it's in the third year (or maybe 4th) that the piece limit is conceivably reached.

1)There are only 34 supply centers, therefore there can never be more than 34 units on the board, not 42+. The piece limit can be reached after just one year.
2)There are 22 starting pieces, not 21--4 for Russia.
3)Each unit has several order options. There are quadrillions of unique opening orders. I'm not even talking about a year, just the first season.
Subject: Opening Moves (or: Why Diplomacy Rocks)
4)There are an exhausting number of possibilities for the board to be in. Once the game reaches 1906 or so, the board can be in any single one of the possibilities. Therefore, if the board is "solved" to 1906 or so, it's completely solved, and there's no more work to do for 1907 on.
5)It's basically impossible to "solve" Diplomacy in the way that you seem to be talking about. You can't program in what to do in a small percentage of board possibilities, let alone every possibility, not even for Fall 1901 based on the the quadrillions of possibilities of what happened in Spring 1901. AI needs to be programmed to behave in certain ways based on the general settings of the board, not the specific position of the board.

Here's a couple more thread links you might find interesting:
Subject: First Move Tendencies on PlayDip
Subject: Quick Guide: Can I move from A to B?

Re: Bot?

PostPosted: 25 Nov 2013, 04:10
by megan
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).