1v1 Puzzles

Use this forum to discuss Diplomacy strategy.
Forum rules
This forum is limited to topics relating to the game Diplomacy only. Other posts or topics will be relocated to the correct forum category or deleted. Please be respectful and follow our normal site rules at http://www.webdiplomacy.net/rules.php.
Message
Author
RoganJosh
Silver Donator
Silver Donator
Posts: 556
Joined: Sun Dec 31, 2017 1:02 am
Location: Stockholm
Karma: 464
Contact:

Re: 1v1 Puzzles

#41 Post by RoganJosh » Tue Jan 21, 2020 4:04 pm

Yeah, one of the intentions with the puzzle was to make people aware of that! :-)

Squigs44
Developer
Developer
Posts: 4003
Joined: Thu Jul 12, 2018 11:50 pm
Location: OKC
Karma: 2010
Contact:

Re: 1v1 Puzzles

#42 Post by Squigs44 » Tue Jan 21, 2020 6:22 pm

Are we not posting public guesses for number 3, or can I give it a shot?

jay65536
Posts: 59
Joined: Mon Dec 16, 2019 7:36 pm
Karma: 53
Contact:

Re: 1v1 Puzzles

#43 Post by jay65536 » Tue Jan 21, 2020 6:51 pm

RoganJosh wrote:
Mon Jan 20, 2020 11:26 pm
We are discussing the meaning of the sentence

France wins by probability 1.

Your interpretation is that this sentence is equivalent to "France has a strategy whose expected payoff is 1." You have not provided any arguments for why your interpretation is reasonable.

My interpretation is that this sentence is equivalent to "The supremum of the expected payoffs for all French strategies is 1". I find this to be the only reasonable interpretation.

This is literally the difference between taking maximums and taking supremums. And that just about settles the issue. No sane person would try to do real analysis using maximums.
I mean...we seem to agree on the math behind both of our assertions, so we've reduced this to a semantic debate.

Meanwhile, for anyone else who's reading the thread, maybe let's take a straw poll.

1) Do you know what a "supremum" is without looking it up?
2) Does RJ's interpretation of "win with probability 1" make sense to you? I'm guessing if you answered no to the first question, you'll also answer no to this one.
3) When you first read the puzzle, did you assume you were being asked for one single strategy that you could prove had probability 1 to win? Or did you assume you might have been being asked a different question?

While it is of course true that analysts usually deal with suprema and not maxima (for the precise reason that the former exist more often, which is the crux of the issue here), I think it is not true that a person reading this question was assuming they might need to draw on their knowledge of real analysis to arrive at the desired answer.

Squigs44
Developer
Developer
Posts: 4003
Joined: Thu Jul 12, 2018 11:50 pm
Location: OKC
Karma: 2010
Contact:

Re: 1v1 Puzzles

#44 Post by Squigs44 » Tue Jan 21, 2020 7:19 pm

jay65536 wrote:
Tue Jan 21, 2020 6:51 pm

1) Do you know what a "supremum" is without looking it up?
2) Does RJ's interpretation of "win with probability 1" make sense to you? I'm guessing if you answered no to the first question, you'll also answer no to this one.
3) When you first read the puzzle, did you assume you were being asked for one single strategy that you could prove had probability 1 to win? Or did you assume you might have been being asked a different question?
1) Yes
2) Yes
3) I dont really understand what you are asking here with this question. I suppose that yes, I assumed I was being asked to provide a strategy, which, when employed, would result in a win with probability 1. My strategy might contain a series of cases which would result in different movesests for each case though.

*Note: I am currently in my final year of studying mathematics at a university, and so my understanding of supremum and probability is likely different than other users.

Claesar
Posts: 1965
Joined: Tue Oct 03, 2017 10:34 am
Karma: 1490
Contact:

Re: 1v1 Puzzles

#45 Post by Claesar » Tue Jan 21, 2020 7:31 pm

1) No
2) No
3) Yes

I have a degree in Science, but not Math.

RoganJosh
Silver Donator
Silver Donator
Posts: 556
Joined: Sun Dec 31, 2017 1:02 am
Location: Stockholm
Karma: 464
Contact:

Re: 1v1 Puzzles

#46 Post by RoganJosh » Tue Jan 21, 2020 7:37 pm

RoganJosh wrote:
Sat Jan 18, 2020 12:40 pm
Maybe to clarify, this is exactly how "by probability 1" should be interpreted:
bartogian wrote:
Fri Jan 17, 2020 11:01 am
P.S. For those confused, a probability 1 win means that for all p<1, France can find a strategy that wins with probability at least p.
Jay, this is the post that you originally replied to.

RoganJosh
Silver Donator
Silver Donator
Posts: 556
Joined: Sun Dec 31, 2017 1:02 am
Location: Stockholm
Karma: 464
Contact:

Re: 1v1 Puzzles

#47 Post by RoganJosh » Tue Jan 21, 2020 7:39 pm

Squigs44 wrote:
Tue Jan 21, 2020 6:22 pm
Are we not posting public guesses for number 3, or can I give it a shot?
You are more than welcome to, Mr Smith and Bozo have both chipped in so far.

Notice that Puzzle 5 is a scaled down version with the same type of solution, but which requires less work.

Squigs44
Developer
Developer
Posts: 4003
Joined: Thu Jul 12, 2018 11:50 pm
Location: OKC
Karma: 2010
Contact:

Re: 1v1 Puzzles

#48 Post by Squigs44 » Wed Jan 22, 2020 4:25 am

Breaking down puzzle 3:

A couple things right off the bat:

The south is in a stalemate. While France could potentially stand to take Gulf of Lyon, France and Austria both have move sets where they are guaranteed to maintain their supply centers down south. Furthermore, Austria can do this without using Trieste.

France has the capacity to maintain all of his territories in the north safely and indefinitely. This means that France can, with surety, move his newly acquired army and fleet to obtain Edinburgh and Liverpool. From there, France can build a new army, and a new fleet. He can then use these fleets to convoy his armies to Sweden and Finland (preparing a convoy to Livonia OR Prussia). Finally, France can maneuver his fleets into Norway and Barents Sea. This allows him to continually cover St Pete, allowing the army there freedom to tap Livonia if needed. If we are going to allow France to use his unlimited time and security to move his units as described, we must also allow Austria to move his army in Trieste up into Moscow. This is where I begin my analysis.

It seems obvious from the beginning that the key weakness in Austria's defense is his deficiency in units to support ALL of Liviona, Prussia, and Munich. France can provide an attack of power 4 on Munich, an attack of power 2 on Prussia, and an attack of power 3 on Livonia. Austria, on the other hand, can only provide a defense of power 4 to Munich with the use of Silesia. A defense of power 2 to Prussia requires use of either Silesia or Warsaw, and a defense of power 3 to Livonia also requires use of Warsaw. If Austria were to play completely defensively, he would eventually lose one of the three territories.

Lets take a look at what would happen if France could penetrate one of those three territories:
France captures Munich: As long as France does not have to sacrifice Berlin to take Munich, France would win by capturing Munich.
France captures Prussia: If France can maintain his units in Berlin, Kiel, Ruhr, and Burgundy while capturing Prussia, then he can use Prussia to tap Silesia, and the other 4 units can launch a sufficiently powerful attack to capture Munich and win the game. Thus, capturing Prussia in addition to his current position is also sufficient for victory.
France captures Livonia: If France can capture Livonia and maintain his other territories, France can then use that to force either Munich or Prussia, and as shown above, will proceed to win. This proof requires a little bit of thinking, and is shown below:

Lets assume that France was able to capture Livonia by using St Pete (and then backfilled with the army that we stationed in Finland). Note that France can now safely and indefinitely hold this new position. At this point, he can observe Austria's strategy over N (a very large number) turns. At this point, Austria has either entered the same strategy over and over again, or, more likely, he has entered a mixed strategy. By observing this mixed strategy, if you follow the algorithm below, you should be able to win with probability 1:

1) Determine if Austria's mixed strategy contains either of the following movesets:
A Munich -> Kiel
A Prussia -> Berlin
A Silesia sup Prussia -> Berlin
OR
A Munich -> Berlin
A Silesia sup Munich -> Berlin
A Prussia sup Munich -> Berlin
If so, enter the moveset:
A Kiel -> Munich
A Ruhr sup Kiel -> Munich
A Bur sup Kiel -> Munich
F Baltic Sea sup Berlin
A Livonia -> Prussia
If Austria uses the above strategy, you will take Munich and win. If Austria uses any other strategy from his mixed strategy, you will hold your ground (or possibly lose Livonia, which you can take back and try again). If there is no movement, you will wait another N turns, figure out what Austria's new mixed strategy is, and go through the algorithm again.

2) Determine if Austria's mixed strategy contains any movesets where Austria does not enter:
A Silesia sup Prussia Hold
A Warsaw sup Prussia Hold

If so, enter these moves:
A Livonia -> Prussia
F Bal Sea sup Liv -> Prussia
A Berlin sup Liv -> Prussia
A Kiel sup Berlin Hold
A Ruhr -> Munich

At this point, the only way you could potentially lose the game is if Austria entered a moveset from part 1. However, if Austria was entering those movesets as part of his mixed strategy, you wouldn't use these steps. So your chances of losing are the chances that Austria decides to go N moves without using those movesets and then choosing this specific turn to use it. Thus, your chance of losing is 1/N. More likely, Austria will either support hold Prussia, and you retry this algorithm again, or you force Prussia, and can guarantee a win from there.

3) If you get to this point, that means that Austria is entering these moves every single turn:
A Silesia sup Hold Prussia
A Warsaw sup Hold Prussia
In which case you enter:
F Baltic Sea -> Berlin
A Berlin -> Munich
A Kiel sup Berlin -> Munich
A Ruhr sup Berlin -> Munich
A Bur sup Berlin -> Munich
And you take Munich while maintaining Berlin.

The algorithm I just wrote was kinda complex, and I am still trying to wrap my head around it myself. I probably could have been a bit clearer. The short story is that IF France has Livonia, he can use a wait and see strategy to figure out how Austria plays, and react accordingly. This means that he can minimize his probability of losing to 1/N, and win in all other cases. Austria would have to perfectly guess in a game of N turns when to play a certain moveset, otherwise he loses to this strategy. That means that France wins with probability (N-1)/N, which converges to 1 as N goes to infinity.

Now, I have done all this work just to show that should France win Livonia, he can win the whole game. There is still work to do. I must show that France can guarantee that he wins one of Munich, Prussia and Livonia from his current position. The argument that I *think* will solve this should be similar to the argument I used for Livonia. That is, you can construct a response to each moveset Austria could use, wait N turns, and counter the mixed strategy with probability 1 success by using the correct counter.

But for now, my brain is tired and I'm just gonna leave these thoughts out there for others to try to decipher.
1

Squigs44
Developer
Developer
Posts: 4003
Joined: Thu Jul 12, 2018 11:50 pm
Location: OKC
Karma: 2010
Contact:

Re: 1v1 Puzzles

#49 Post by Squigs44 » Wed Jan 22, 2020 4:32 am

Actually, after working through that and writing out a very confusing post, I thought of a better way of putting this problem. Lets modify the A,B / 0,1 argument used earlier:

France has options A and B
Austria has options 0 and 1

If strategies A and 0 are used, France wins.
If strategies A and 1 are used, the stalemate continues
If strategies B and 0 are used, Austria wins.
If strategies B and 1 are used, France wins.

In this situation, it seems that France cannot guarantee a win.
However, lets say that France plays strategy A for the first 100 moves. Then the only way France doesn't lose is if he plays strategy 1 for the first 100 moves. Even then the game continues. France could play strategy A again for the next 1000 moves. Again, Austria would have to play strategy 1 for the next 1000 moves. Lets say that France plays strategy A 9643 times, and then plays strategy B. The only way for Austria to win would be to play strategy 1 9643 times and then play strategy 0. In that case, Austria wins and France loses.

So while France cannot guarantee a win, if he plays the safe strategy N times and then switches to the risky strategy, he can increase his odds to (N-1)/N, which approaches 1 as N gets larger and larger.

In my long drawn out post, I tried to find situations where the above is true. Situations where France can play a safe strategy for a long time, and then play the risky strategy just once.
1

BunnyGo
Posts: 13638
Joined: Thu Jul 18, 2019 12:21 am
Karma: 4458
Contact:

Re: 1v1 Puzzles

#50 Post by BunnyGo » Wed Jan 22, 2020 11:39 am

RoganJosh wrote:
Fri Jan 17, 2020 6:49 pm
Here's a link with some nice reading and references on the difference between "impossible" and "probability 0".

https://math.stackexchange.com/question ... ossibility
I think you fundamentally misunderstand that website, or misunderstand how a clever Austria could counter an aggressive France. These are not measure 0 possibilities of being outguessed and losing Berlin or Marseille.

RoganJosh
Silver Donator
Silver Donator
Posts: 556
Joined: Sun Dec 31, 2017 1:02 am
Location: Stockholm
Karma: 464
Contact:

Re: 1v1 Puzzles

#51 Post by RoganJosh » Wed Jan 22, 2020 12:25 pm

BunnyGo wrote:
Wed Jan 22, 2020 11:39 am
I think you fundamentally misunderstand that website, or misunderstand how a clever Austria could counter an aggressive France. These are not measure 0 possibilities of being outguessed and losing Berlin or Marseille.
It sounds like you consider one specific turn, and that you assume that France will choose an attacking move that turn.

You need to consider the whole sequence of turns.

jay65536
Posts: 59
Joined: Mon Dec 16, 2019 7:36 pm
Karma: 53
Contact:

Re: 1v1 Puzzles

#52 Post by jay65536 » Wed Jan 22, 2020 12:57 pm

Squigs44 wrote:
Wed Jan 22, 2020 4:32 am
In this situation, it seems that France cannot guarantee a win.
However, lets say that France plays strategy A for the first 100 moves. Then the only way France doesn't lose is if he plays strategy 1 for the first 100 moves. Even then the game continues. France could play strategy A again for the next 1000 moves. Again, Austria would have to play strategy 1 for the next 1000 moves. Lets say that France plays strategy A 9643 times, and then plays strategy B. The only way for Austria to win would be to play strategy 1 9643 times and then play strategy 0. In that case, Austria wins and France loses.

So while France cannot guarantee a win, if he plays the safe strategy N times and then switches to the risky strategy, he can increase his odds to (N-1)/N, which approaches 1 as N gets larger and larger.
Putting aside some minor quibbles about tightening the screws with respect to how the strategies are chosen, your argument was anticipated upthread. You've come up with a sequence S_N of strategies such that as N grows, France's probability of a win by playing S_N approaches 1. The problem is you still can't show that France has a strategy that wins with probability 1.

The argument that you (and RJ) have adopted and the argument that I'm giving are basically talking past each other at this point. What you guys have shown is that France's win probability must be 1 if it is defined. What I'm saying is that in fact, it is undefined. The reason it is undefined is because we're looking at two different limits (the probabilities and the strategies) that behave poorly with respect to each other. Since you say you're a math major, I know you've seen examples similar to that before, where you have a sequence of functions, and you take the limits of the functions and the sequence, but if you switch the order of the limit-taking, you get different results if the sequence doesn't converge uniformly. That's very much analogous to what's going on in this problem.

Squigs44
Developer
Developer
Posts: 4003
Joined: Thu Jul 12, 2018 11:50 pm
Location: OKC
Karma: 2010
Contact:

Re: 1v1 Puzzles

#53 Post by Squigs44 » Wed Jan 22, 2020 9:33 pm

For the sake of clarity, can you define what you mean when you say "A sequence of French strategies". I don't really understand what you mean by that.

BunnyGo
Posts: 13638
Joined: Thu Jul 18, 2019 12:21 am
Karma: 4458
Contact:

Re: 1v1 Puzzles

#54 Post by BunnyGo » Thu Jan 23, 2020 12:02 am

RoganJosh wrote:
Wed Jan 22, 2020 12:25 pm
BunnyGo wrote:
Wed Jan 22, 2020 11:39 am
I think you fundamentally misunderstand that website, or misunderstand how a clever Austria could counter an aggressive France. These are not measure 0 possibilities of being outguessed and losing Berlin or Marseille.
It sounds like you consider one specific turn, and that you assume that France will choose an attacking move that turn.

You need to consider the whole sequence of turns.
I mean...it’s still not approaching 100% in the limit. This fundamentally doesn’t appreciate that austria isn’t thinking about the situation.

mhsmith0
Posts: 318
Joined: Wed Jan 03, 2018 12:35 am
Karma: 186
Contact:

Re: 1v1 Puzzles

#55 Post by mhsmith0 » Thu Jan 23, 2020 12:55 am

It actually approaches 100% pretty reasonably well.

In a given turn where France attacks Livonia, Austria has a chance to win if he's aggressive that turn. BUT, if he's aggressive in a turn where France does NOT attack Livonia, things get more interesting.

from earlier in thread:
Austrian move sets
1) Pru-Ber supported by Mun, Tyr/Boh/SIl support Mun H
4) Mun-Ber supported by Pru, Tyr-Mun supported by Boh/Sil
5) Mun-Kiel, Tyr-Mun supported by Boh, Pru-Ber supported by Sil

Each has a 1/3 chance of Austrian outright victory in a turn where France uses F Baltic on Livonia instead of on Berlin. HOWEVER, consider how the board looks in a turn where France is using F Baltic on Berlin.

France move sets
A] Ber-Mun supported by Bur/Ruhr/Kiel, F Baltic moves to Berlin.
B] Bur-Mun supported by Ruhr/Kiel/Ber, F Baltic support holds Berlin
C] Bur-Mun supported by Ruhr/Ber, F Baltic and A Kiel support hold Berlin
(France also has option of attacking Prussia using F Baltic to move or support A Berlin-Prussia, though that's probably generally suboptimal w/ a nonzero risk of outright loss, so I won't get into it here)

1-A: everyone bounces, no change in positions
1-B: everyone bounces, no change in positions
1-C: everyone bounces, no change in positions
4-A: France’s attack on Munich succeeds, F Baltic fills in Berlin, France wins outright
4-B: France’s attack on Munich succeeds, and whether or not he bothers filling into Burgundy, France wins outright (Ruhr/Kiel support Mun H, Baltic supports Berlin H)
4-C: everyone bounces, no change in positions
5-A: both attacks succeed. IF Austria can reinforce Prussia, he’ll lock in the draw (I haven’t calculated it)
5-B: France’s attack on Munich succeeds, and whether or not he bothers filling into Burgundy, France wins outright (Ruhr/Kiel support Mun H, Baltic supports Berlin H)
5-C: everyone bounces, no change in positions

What this means is that France has the option of endlessly choosing moveset C, once in a while sneaking in moveset B (this moveset is vulnerable to Austria choosing Mun-Ber supported by Pru/Sil, which is basically an all out gamble on Austria’s part to try and force the Mun-Ber swap and a draw), and then keeping open the option of attacking Livonia and then Prussia by way of STP.

What is Austria to do? If France’s move set is something like:
95% Bur-Mun supported by Ruhr-Ber, F Bal/A Kiel support Ber H (guaranteed to hold at worst for France, and can win outright against some alternative Austrian move sets)
4% Bur-Mun supported by Ruhr-Ber-Kiel, F Bal support Ber H (countered only by moves that leave more vulnerability if France attacks Livonia)
1% attack Livonia

Then Austria has no strategy that has more than 1-2% win equity (actively counter a potential Livonia attack, and you’re highly vulnerable to an immediate French win; don’t make moves to counter a Livonian attack, and you lose that space and eventually the game). Expand France’s strategy to be 99% / 0.9% / 0.1% and it’s harder. Go to 99.9% / 0.09% / 0.01% and Austria’s win equity shrinks further. Etc
2

jay65536
Posts: 59
Joined: Mon Dec 16, 2019 7:36 pm
Karma: 53
Contact:

Re: 1v1 Puzzles

#56 Post by jay65536 » Thu Jan 23, 2020 1:44 pm

Squigs: when I say, "a sequence of strategies," I'm referring to this:
Squigs44 wrote:
Wed Jan 22, 2020 4:32 am
So while France cannot guarantee a win, if he plays the safe strategy N times and then switches to the risky strategy, he can increase his odds to (N-1)/N, which approaches 1 as N gets larger and larger.
When you say "approaches 1 as N gets larger," you're defining a sequence of strategies, where for each N, there's a different strategy.

The sequence you've defined is that when you fix N, France plays option A (the way you defined the strategies) for N consecutive turns and then switches to option B on turn (N+1). Italy, of course, can guarantee a draw by playing option 1 for the first N turns and option 0 on turn (N+1), if he knows France is doing that. So for the sequence you've defined, France's win probability is 0.

But your general claim is correct; we can slightly alter your idea to get your point across. I'm going to leave out the alteration in case someone's still working on it, but you can PM me or else try to figure out an alteration yourself. (There are many different ways to do it.)

The point is, though, you can generate a sequence where each strategy depends on N and say, this is a sequence of strategies where as we increase N, the probability approaches 1.

The problem is, we can't just "take the limit" because there is no such thing as "the limit"--there are two different limits. There is the limit of the strategies, and the limit of the probabilities. What you, RJ, and I all agree on is that the limit of the probabilities is 1. What I am claiming--and it sounds like no one disputes--is that if you look at the limit of the strategies, and then try to figure out the winning probability of that strategy, it is 0. What RJ is claiming is that his version of the limit is the correct one, and that based on that, the winning probability is well-defined and equal to 1. What I am claiming is that the fact that those two numbers don't agree means that the winning probability is not well-defined and cannot be equal to anything.

RoganJosh
Silver Donator
Silver Donator
Posts: 556
Joined: Sun Dec 31, 2017 1:02 am
Location: Stockholm
Karma: 464
Contact:

Re: 1v1 Puzzles

#57 Post by RoganJosh » Thu Jan 23, 2020 2:54 pm

jay65536 wrote:
Thu Jan 23, 2020 1:44 pm
The problem is, we can't just "take the limit" because there is no such thing as "the limit"--there are two different limits. There is the limit of the strategies, and the limit of the probabilities.
You have not disclosed what you solution is, so I have not been able to check it for correctness. But, let me point out, if the strategy you propose is that France picks a large integer N, and then chooses an integer k uniformly at random from the interval [0,N], then this sequence of strategies does not converge in any meaningful sense.

If you have a different solution in mind, then I propose that you disclose it, at least in a PM.
jay65536 wrote:
Thu Jan 23, 2020 1:44 pm
What RJ is claiming is that his version of the limit is the correct one, and that based on that, the winning probability is well-defined and equal to 1. What I am claiming is that the fact that those two numbers don't agree means that the winning probability is not well-defined and cannot be equal to anything.
I am not claiming that my "version of the limit" is the "correct one". I am claiming that for the statement "France to win by probability 1" to make sense, the only reasonable interpretation of "probability" is as a limit. For the very reasons you mention! If this is not the interpretation, then the sentence is meaningless.

I think you did not understand that the first question I posed to you was rhetorical.

Btw, this manner of measuring sizes of subsets of the natural numbers is called "natural density." It is the standard approach, since the set of natural numbers does not admit a uniform distribution. If you have ever heard statements of the form "the probability that two natural numbers are coprime is 6/pi^2" and similar, then these "probabilities" are defined in the same manner.

jay65536
Posts: 59
Joined: Mon Dec 16, 2019 7:36 pm
Karma: 53
Contact:

Re: 1v1 Puzzles

#58 Post by jay65536 » Thu Jan 23, 2020 4:21 pm

RoganJosh wrote:
Thu Jan 23, 2020 2:54 pm
You have not disclosed what you solution is, so I have not been able to check it for correctness. But, let me point out, if the strategy you propose is that France picks a large integer N, and then chooses an integer k uniformly at random from the interval [0,N], then this sequence of strategies does not converge in any meaningful sense.
There are of course many possible solutions, as you know, but as for the one you mention:

1) It most certainly does. As N -> \inf, it converges to the strategy of always playing the safe option.

2) Even if you were right and it did not converge, then how can you claim the probability is well-defined??

Your last example is of course right, but let's dumb it down even further for non-mathematicians who are reading this. If we want to ask a question like "What is the probability that a natural number is even?" then what we do is consider an arbitrarily large N and ask the question "What is the probability that a natural number less than or equal to N is even?" In this case, if N is even, the probability is exactly 1/2, and if N is odd, the probability is (N-1)/2N. As N approaches infinity, this last expression converges to 1/2, so the limit behaves nicely and we can say without fear of contradiction that the probability is 1/2.

We can do similar things for questions like "What is the probability that a natural number is greater than 50?" (it's 1) or "What is the probability that a natural number is equal to 43?" (it's 0).

The dispute RJ and I are having is not whether we can apply such logic to this problem (we both agree we can), but HOW to apply it in the right way. In this setup, the question that we want to ask is, "What is the probability that France wins the game?" But this is not really a well-defined question. The reason it is not well-defined is because we have not assumed how the players are playing.

An example of a question that is well-defined and has an answer is: "What is the probability that France wins the game if France always plays the risky strategy and Italy plays the optimal counter-strategy?" That answer is clearly 0 because the game will end on the first turn in a draw.

Another example is "What is the probability that France wins the game if France randomizes .5/.5 and Italy also randomizes .5/.5?" Even though theoretically the game could go on forever, we can apply the above logic to conclude that the answer in this case is 2/3. Explicitly, we can compute, for any N, the probability that France wins the game in N or fewer turns. We can also compute the probability that Italy draws the game in N or fewer turns. Then we take both limits as N goes to infinity, and we find that they converge to 2/3 and 1/3, respectively.

In game theory, when you ask "What is the probability of a win for Player X [in this two-player game]?" the implicit assumption behind the question is that you're really asking "What is the probability of a win for Player X if both sides play their optimal strategy?" In other words, you'd usually answer this question by first computing the optimal strategy, then computing the probability based off of that.

The argument that RJ and Squigs are making in this thread is that it is acceptable to change the order of computation. In other words, they want to ask the question "What is the probability that France wins the game?" so they do the following, in this order:

1) They fix a value N (meant to grow arbitrarily large).
2) They ask the question "What is the probability that France wins the game on or before turn N?"
3) They compute optimal strategies for an N-turn-limited game and compute the probability that France wins that game.
4) They then take the limit as N goes to infinity of these probabilities.

There is a big difference between this method, and the 50/50 example above. In that example, we fixed a strategy first, THEN took the limit. The only variable inside the limit was the number of turns. This other method allows the strategy being played to vary inside the expression we're taking the limit of. It never actually computes the optimal strategy for France to play in the turn-unlimited game. One of the first things you learn in advanced calculus is that playing fast-and-loose with limits like this can sometimes be a huge mistake. This is one of those times.

And now that I'm actually thinking about it...is there even a French optimal strategy??? Does this game not admit a Nash equilibrium??? I am so used to studying games that clearly admit one that I forgot about this before.

mhsmith0
Posts: 318
Joined: Wed Jan 03, 2018 12:35 am
Karma: 186
Contact:

Re: 1v1 Puzzles

#59 Post by mhsmith0 » Thu Jan 23, 2020 5:06 pm

Off the cuff, I think it's fair to consider French strategy in the context of a game that has an N-turn limit (for instance, a site that say that if you haven't changed the board position [say, around the stalemate lines, to avoid trivial move sets] in N terms, it auto-draws - note that this is a LOOSER standard than webdip's "it's a draw if no supply centers have changed in like 4 turns or w/e")

So if we interpret the relevant board rule as "France needs to take Livonia or Berlin by the end of turn N", one potentially optimal (or near-optimal) move set is

p1 = (N - 2) / N, France makes the super defensive move set Bur-Mun supported by Ruhr/Berlin, Kiel/Baltic defend Berlin
p2 = 1/N, France does not attack Livonia, but instead uses the aggressive non-Livonia move set Bur-Mun supported by Ruhr/Kiel/Berlin, Baltic defends Berlin
p3 = 1/N, France attacks Livonia

p1 is the dominant default move set for MOST of France's moves, because it enforces a continual "all units hold position" at worst against any Austrian move set, while outright winning the game for France against SOME possible Austrian move sets (i.e. if Austria rolls with Munich attacking Berlin using Silesian support on Mun-Ber [Tyr-Mun supported by Boh is obvious as part of it but 2 support loses to 3 support], France takes Munich without losing Berlin and wins outright)

p2 is not a dominant move set, but it is a powerful one nonetheless. The worst case outcome of this move set is a draw (flipping Berlin and Munich control, which means a true stalemate), and the best case outcome of this move set is an outright win (if Austria rolls with Munich attacking Berlin where Silesia supports Tyr-Mun instead, France wins outright; if Austria uses Munich to cut Kiel and go Pru-Ber supported by Sil, France also wins outright)

and then p3 risks outright defeat, but if Austria plays defensively that turn, is guaranteed to win


I do not hold that the above proposal is precisely optimal, but I do hold that it's getting there (possibly p2 should be > 1/N; possibly you should also have a non-zero possibility of Ber-Mun supported by Bur/Ruhr/Kiel, and F Baltic backfilling Berlin, which also risks a true stalemate at worst against different Austrian move sets, thought it DOES risk an outright loss against Pru-Ber supported by Mun, with Tyr/Boh/Sil supporting Mun H; etc)

The Austrian counter-strategy to that is likely to be something like

q1 = (N-2)/N default set of moves that will hold positions against any non-Livonian attack move set
q2 = 1/N counters France's p2 option (but loses if you guess wrong on when to do it)
q3 = 1/N counters France's p3 Livonian option (but loses if you guess wrong on when to do it)

I'm being loose in my definitions of which move sets counter which but I think it's at least reasonable to consider it in those terms

France lines up N moves in order, placing "p2" and "p3" somewhere in the range once each
Austria lines up N moves in order, placing "q2" and "q3" somewhere in the range
(this is a simplification, but a reasonable one imo)

(p1 against p1 is "standard option, nothing happens, keep playing")
If the first non-standard option is p2 against q1, nothing happens, keep playing (and then consider the next non-standard option as the "first")
If the first non-standard option is p3 against q1, France takes Livonia and wins
If the first non-standard option is q2 against p2 or q3 against p3, Austria wins
If the first non-standard option is q2 against p1/p3, or q3 against p1/p2, or France wins (this may be overly generous to France)

This essentially boils down to odds of <= 2/N of Austria hitting p2 with q2, or p3 with p3 (it's possible that this matches on the list towards the end, and France wins with an earlier winning move, but calling it 2/N is probably ok). Also: p2 against q2 forces a draw, and p3 against q3 wins it outright for Austria, so Austria's win equity here would be more like 1.5/N.

So given a limit of N moves, and the French strategy I'd outline, you can reasonably approximate Austria's win equity as <= 1.5/N (I'm sure you can refine the strategy on France and/or Austria to shift that number around, but not so drastically as to invalidate the discussion)

As N goes towards infinity, the limit of Austrian win equity then goes to 0. I think I'm comfortable with that broad conclusion, even if the particulars are I'm sure subject to reasonable debate (i.e. maybe there's a French strategy to dip Austrian win equity below 1/N, or an Austrian strategy to bump win equity to 2/N or 3/N or w/e, but it'll still scale broadly speaking).
1

mhsmith0
Posts: 318
Joined: Wed Jan 03, 2018 12:35 am
Karma: 186
Contact:

Re: 1v1 Puzzles

#60 Post by mhsmith0 » Thu Jan 23, 2020 5:10 pm

PS to put it in more theoretical mathematical terms, I'd GUESS there's some kind of Nash Equilibrium whereby both France and Austria are optimized, but any such equilibrium can be expressed in terms of Austrian win equity = some fixed x/N, whereby N is the # of turns available for France to take Berlin or Livonia before the game is called a draw, and therefore if you're allowed to increase N indefinitely, Austria's win equity becomes functionally zero (I find it easier to think in terms of Austrian win equity and the zero limit as opposed to France's win equity and the 1 limit, even if it's just an algebraic difference)

PPS you can also think of this as being a much more complicated version of the game from the Kaiji anime a while ago, where there were five cards per side

one side had four peasant cards and one emperor card
the other side had four peasant cards and an assassin card
if you match the assassin to the emperor, the assassin side wins
if you don't, the emperor side wins

If you let the # of cards go to N (but there's still 1 assassin and 1 emperor), the assassin win equity is 1/N and goes to zero

This is more complicated (much more complicated), but the analogy very loosely holds. Austria has "assassin" move sets, and France has "emperor" move sets. Match assassin against emperor, Austria wins. Fail, and France wins.

Post Reply

Who is online

Users browsing this forum: No registered users and 42 guests