23
$\begingroup$

I saw this problem many years ago. I am sure many puzzlers will know its original name. I was reminded of it when reading about Conquering of Regions problem. A Strategy Game Involving Conquering of Regions

  • Wellington and Napoleon each have an army of 100 soldiers.
  • Each army is divided into 10 platoons.
  • A platoon can have any number of soldiers (including zero).

When the action begins, Platoon 1 from Wellington's army engages with Platoon 1 from Napoleon's army, Platoon 2 engages with its opposite number and so on.

  • The platoon having more soldiers than the opposition wins their individual engagement.
  • The winner of an engagement incurs no casualties whereas the loser suffers the loss of all soldiers.
  • If the number of soldiers on each side is equal, the engagement is a draw and neither side suffers any casualties.

Each engagement takes place on a separate territory and is fought independently of the others. Neither side knows in advance the size of the enemy platoon faced in any of the territories.

The two generals are noted for their powerful logic and deep insight into psychology. In this scenario, both are pursuing aggressive strategies. If you were one of the generals, how would you distribute your soldiers so as to have the maximum chance of (a) winning the most platoon engagements and (b) defeating the greatest number of opposition soldiers?

Edit: The name of the game is Colonel Blotto: https://en.wikipedia.org/wiki/Blotto_game There is a lot of research on it, including computational approaches and polls: https://arxiv.org/search/?query=blotto&searchtype=all&source=header

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Related: fivethirtyeight.com/features/can-you-rule-riddler-nation (The riddler classic) $\endgroup$ – im_so_meta_even_this_acronym Sep 18 '19 at 1:12
  • 3
    $\begingroup$ Hire 1 extra mercenary. Attack with full force. Guaranteed win. (Not posting as an answer since it's obviously cheating.) $\endgroup$ – Darrel Hoffman Sep 18 '19 at 13:34
  • 2
    $\begingroup$ Question: both sides are motivated by winning battles and inflicting casualties, and have no incentive to avoid incurring casualties or losing battles? $\endgroup$ – Ben Aveling Sep 19 '19 at 5:30
  • 1
    $\begingroup$ For the purposes of this problem, we assume that both sides have maximum aggressive intentions. $\endgroup$ – John Foley Sep 19 '19 at 8:04
  • 3
    $\begingroup$ Allowing 0 solidiers makes it a lot less interesting likewise putting no value on land lost. $\endgroup$ – Ian Ringrose Sep 19 '19 at 13:37

11 Answers 11

Active Oldest Votes
20
$\begingroup$

I'll kick off with some observations.

I think there is no easily determinable winning strategy. The game as envisaged is mind-blowing because there are 4,263,421,511,271 possible ways of arranging your army. However, suppose that there were a deterministic configuration that maximized either a or b. Then both sides would use it and all 10 platoons would be a draw.

But, if you knew what your opposition were going to do, then you'd just mirror their army, take the smallest platoon with size $\geq 9$, and give 1 to each other army winning 9 battles.

Then again, it would depend on what your opponent's objectives were. If he simply wanted to save as many men as possible, he'd do something like $(100,0,0,\ldots)$. Easy to beat with objective (a) and impossible with objective (b). So it is important to know whether the opposing general knows about your objective and/or has an objective of their own.

But normally this reduces to something like rock, paper, scissors where the Nash Equilibrium solution is to have an equal probability of choosing rock, paper, or scissors.

Determining a Nash Equilibrium for such a large solution space is not trivial. So here are some numerical attempts for much simpler problems:

For both problems, I assume that defeat means you need your platoon to be strictly bigger than the opposing platoon. I then assume 9 soldiers and 3 platoons, and evolve the strategy until I'm roughly indifferent to what my opponent is choosing. I also assume that my probabilities are going to be equal for all permutations. So whatever my probability is for [0,3,6] it will be the same for [0,6,3], [3,0,6], and so on.

For problem a, it shows the following (with a lot of spurious accuracy!):

[0 0 9] 0.08969140375863138
[0 2 7] 0.033696054860265535
[0 4 5] 0.029747584762232965
[0 3 6] 0.027726778078327265
[0 1 8] 0.025936954631579415
[1 1 7] 0.006435624011966441
[1 4 4] 0.002057572668762006
[3 3 3] 0.0018396498692940773
[2 2 5] 0.0003207716042842319
[1 2 6] 4.886082454138541e-13
[2 3 4] 4.0188092068566764e-13
[1 3 5] 1.124292366185872e-19

I assume I've made an error, since the high probability of the [0,0,9] solutions seems wrong (It might be correct since it gives a high probability of a score of 1 when the max score in this case is 2). But I'll post this for now to show the approach. The score you would get in this case (against any choice from player 2) is $1.18\pm 0.01$. Of course, your max score is 2 and your min is 1.

Here's the case for 6 soldiers and 4 platoons showing similar trends:

[0 0 0 6] 0.03507904334840038
[0 0 2 4] 0.029695480610278505
[0 0 3 3] 0.02956549030935802
[0 0 1 5] 0.02715661099230036
[1 1 1 3] 1.3911109098506814e-05
[0 2 2 2] 1.362817469650331e-06
[1 1 2 2] 7.786961895140738e-07
[0 1 1 4] 1.469657831039888e-09
[0 1 2 3] 1.1765812916837055e-18

I'm still having troubles convincing myself that I haven't made an error. I mean, you basically always get 1 unless you have the exact same strategy, so why the preference for the [0,0,0,6] type solutions? Here the average score is $1.35\pm0.03$

For problem b, I don't think there is one because you will always get 0 if your opponent plays [0,0,9] as discussed earlier.

Another observation: Doing the 9 soldiers with 3 platoons but setting the [0,0,9] solutions to 0 probability yields:

[0 2 7] 0.051643285123016455
[0 4 5] 0.04878474186500994
[0 3 6] 0.03799226690918427
[1 1 7] 0.022924736330020803
[0 1 8] 0.011810956237999548
[1 4 4] 0.007329407508318203
[3 3 3] 0.006553131156166946
[2 2 5] 0.00043231217051718226
[2 3 4] 9.779932406154017e-13
[1 2 6] 2.2520149653133117e-14
[1 3 5] 4.0049117381710107e-19
[0 0 9] 0.0

It's far further from an equilibrium. But interestingly, the results are generally higher scores. The score ranges from $1.24$ to $1.4$ with an average of $1.28$. Something weird is going on...

I'll be interested to see what other people come up with.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Well, to maximize B you should simply have the same setup, ensuring complete destruction of your and his army. Also, I would assume platoon has to have at least 1 unit in it. $\endgroup$ – Zizy Archer Sep 18 '19 at 6:43
  • 4
    $\begingroup$ IIRC, from a game-theoretic approach, an optimal strategy is guaranteed, ie. a Nash equilibrium. The guarantee holds for mixed strategies (stochastic choice from a set of sepecific strategies) only. As the game setup is symmetric (in particular no 'first mover'), the equilibrium will indeed involve mixed strategies, so the optimality translates into a winning probability. The actual strategy will depend on whether the complete platoon allotment must be fixed in advance or can be adjusted after each engagement. $\endgroup$ – collapsar Sep 18 '19 at 11:53
  • $\begingroup$ Have one BIG platoon of 90, have one of 10 and the rest 0. Squash his platoons with BIG platoon. Solved :D! $\endgroup$ – Him_Jalpert Sep 18 '19 at 20:51
  • $\begingroup$ There must be a solution that gives you at least a 50% chance of winning or drawing at option a. $\endgroup$ – Ben Aveling Sep 18 '19 at 23:36
  • 1
    $\begingroup$ @DrXorile How do you win 2 engagements when you're fielding [0 0 9]? The 9 will either win or draw its engagement. But the 0's must either lose or draw - unless we say that if there aren't troops from both sides, then there is no engagement, not that I think that changes anything. $\endgroup$ – Ben Aveling Sep 19 '19 at 5:23
10
$\begingroup$

Nash equilibrium

This task, including the uncertainty about what the opponent would pick, would be a classic fit for game theory, and it must have a solution that's locally optimal i.e. where anyone deviating would make their chances worse (the Nash equlibrium). It's not a question whether such a solution exists, it's well known and proven that it does.

Of course finding the solution is a bit harder, and I won't propose a particular solution, however, I'd still like to post this answer so as to counter multiple other answers asserting that a solution "doesn't" or "can't" exists, which is strictly false.

However I'll outline the characteristics that the solution must have, as it turns out that these characteristics are not obvious to many answerers.

  1. The solution must be non-deterministic i.e. a 'mixed strategy' in game theory terms; as due to the structure of this particular game any particular choice of layout would have a 'counter' that beats it. The same reasoning can be applied to e.g. rock-paper-scissors toy example, where any deterministic strategy fails, but a random strategy of 1/3 chance of each is optimal against an theoretically-perfect opponent, as it can't be beaten.
  2. The game is symmetric - so in the equilibrium we'd assume that both opponents are using the same strategy and obtain the same results i.e. a draw.
  3. The winning strategy (whatever it is - Nash equlibrium proof proves that it must exist but doesn't provide a construction on how to find it) doesn't facilitate deviation - if the opponent chooses any particular strategy e.g. always using 10x10 layout, or a mixed strategy such as 50% of the time doing 91 (at a random location) + 9x1 and 50% of the time doing 9x11 + 1 (at a random location) then the correct solution either beats that strategy or does the same as in the equlibrium (e.g. the rock-paper-scissors case). So we can immediately disqualify some potential candidates for which specific counters exist - as a starter, every strategy in the form of "I'll use this particular split of soldiers" is clearly not a valid candidate, so it must be a mixed strategy that's a probabilistic combination of multiple platoon split choices.
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Consider the set of all specific allotments of n=100 soldiers to k=10 bins the universe of pure strategies in this game. A mixed strategy then is a discrete probability distribution over this set. An optimal mixed strategy whose existence is guaranteed by Nash's theorem corresponds to some unknown distribution F over the universe. Due to game symmetry, this strategy/distribution will be chosen by both players. Thus the sample distribution of both players' concrete deployments would be iid ... $\endgroup$ – collapsar Sep 18 '19 at 17:31
  • $\begingroup$ ... Define some random variables: Let X_1, X_2 denote the concrete deployments under F, let DS be sign(X_1 - X_2) and CountDS the number of positive components in DS. The key to the solution may be the stochastic analysis of CountDS, namely maximizing its expected value. Unfortunately that seems well beyond my math capabilities. It gets more complicated if F is not unique. Any ideas or comments? $\endgroup$ – collapsar Sep 18 '19 at 17:31
  • $\begingroup$ The game is not necessarily symmetric. We know what our payoff is, but not necessarily what the opponent's payoff is. $\endgroup$ – Dr Xorile Sep 18 '19 at 17:39
  • 1
    $\begingroup$ @DrXorile The game is symmetric since the players are indistinguishable. And both players know the their opponent's payoff structure as it is the same as their own. The concrete payoff of the opponent for a game instance is not known beforehand; however, it never is when mixed strategies (randomized choices) are applied, so no game classifucation should depend on this criterion. $\endgroup$ – collapsar Sep 18 '19 at 17:56
  • 2
    $\begingroup$ "the equilibrium we'd assume that both opponents are using the same strategy and obtain the same results i.e. a draw." <-- where draw = equal probability of winning and losing each game, with some chance of draws. There won't be a a strategy where every game is a draw. $\endgroup$ – Ben Aveling Sep 18 '19 at 23:51
5
$\begingroup$

This is an extension of Dr Xorile's observations, which fully answers the question that "there is no optimal strategy as long as knowdledge(and/or guessing) of your opponent distrubution is missing".

But if we knew the opponents strategy, then

a) Maximisation of wins

If we use a N soldier platoon to beat an N-1 soldier enemy platoon, then the "win efficiency" of our soldiers is 1/N (wins gained/soldiers used). This number gets higher and closer to 1 the lower N is. So the logic would be to :

First create a platoon with soldiers equal to 1+ the enemy's smallest platoon. Then, do the same for the enemy's second smallest platoon and so on.

b) Maximisation of enemy causalties

Exactly the opposite. If we use a N+1 soldier platoon to beat an N soldier enemy platoon, then the "kill efficiency" of our soldiers is N/N+1 (enemies killed/soldiers used). This numbers gets higher and closer to 1 the higher N is. So the logic would be to : First create a platoon with soldiers equal to 1+ the enemy's largest platoon. Then, do the same for the enemy's second largest platoon and so on.

It is interesting to see that even if we knew the opponent's distribution, getting wins or causalties lead to ...

...opposite tactics!

| improve this answer | |
$\endgroup$
4
$\begingroup$

For (b), defeating the greatest number of opposition soldiers?

1x100.

I either win or draw. No other combination delivers that result.

For (a), winning the most platoon engagements:

I send one soldier to go spy on the other general, and then I'm sure I could arrange a winning combination using the remaining 99 men. ;-)

Seriously, it's a toss-up. It's rock-scissors-paper. For any combination, there is going to be a combination that defeats it. 10x10 is beaten by 9x11, which is beaten by 8X12, and so on. But 10x10 defeats 4x25, and so on.

Edit: rock-scissors-paper, not rock-scissors-stone. Doh.

Edit 2: New rules! Disaster!

Given the new (clarified) rules, the above strategy for (b) is now useless. If it is optimal, then both generals will follow it, then every engagement is a draw and neither side gets to inflict any casualties. Disaster!

Remember, we don't care how many casualties we take, only how many casualties we inflict.

My 'best' solution is now the worst possible solution.

New revised strategy for (b):

Assuming one side is Red and one side is Blue, then:

If I am Red, then deploy troops 49-51-0. Else deploy 51-49-0.

My 'opponent', being as exactly rational as I am, will also have hit on this same strategy, and we both inflict 49 casualties, the maximum achievable amount.

A less rational opponent might try to deploy 48-52-0 or 52-48-0, but my opponent is rational enough to know that there is no optimal strategy than can achieve better than 49.

Any strategy that tries to achieve a result of 49, while deviating, even occasionally, from 51-49, must result in some drawn engagements - meaning no casualties. Therefore, no such such strategy can be optimal.

To be sure:

I send one soldier to the other general with a message outlining the above, timed to arrive an hour before the battle. Further, I expect to receive a messenger from the other general, an hour before the battle. After all, the strategy works just as well with 50-49.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wrt b): All opponent strategies that would allot less than 99 soldiers to the first platoon, distributing the remainder to at least 2 platoons, would win against your strategy, thus it cannot be optimal. That being said, any deterministic 'optimal' strategy would produce the same result for both players adopting it. Therefore, whatever that strategy is, it will - if it exists - result in a series of draws. $\endgroup$ – collapsar Sep 18 '19 at 13:32
  • $\begingroup$ "rock-scissors-stone"? $\endgroup$ – trentcl Sep 18 '19 at 17:47
  • 4
    $\begingroup$ in a "rock-scissors-stone" game....I feel like scissors are... disadvantaged ;) $\endgroup$ – Patrice Sep 18 '19 at 18:32
  • $\begingroup$ Fair cop. Edited. It is probably true here that there are some strategies that are totally hopeless. $\endgroup$ – Ben Aveling Sep 18 '19 at 23:31
  • 1
    $\begingroup$ @BenAveling if cooperation is an option and there is more than one battle, an optimal strategy could also always be 100-0 on one side an 99-1 on the other, which would kill 49.5 enemy troops on average each round $\endgroup$ – Falco Sep 19 '19 at 12:38
3
$\begingroup$

There is no solution. Proof by contradiction:

Suppose there was a deterministic solution for the 'best deployment', as required by the question since you need to divide up your army before engagement.

Since the solution is deterministic and is objectively the 'best' solution for either Problem (a) or Problem (b) or both, all armies would use this pattern.

For each battle, the platoons on both sides now have exactly the same number of soldiers, resulting in no clear winner.

In contrast, a totally random deployment would have at least some wins under some conditions. So the 'best deployment' isn't really the best. This is a contradiction.

This violates the assumption that there was a deterministic 'best deployment'.

QED by reductio ad absurdum

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ In which way does the existence of a deterministic best deployment follow from the problem description ? $\endgroup$ – collapsar Sep 18 '19 at 13:47
  • 1
    $\begingroup$ @collapsar You have to divide up your army before engagement, so you have to choose the deployment without reference to the other army. If there's a 'best' deployment, it needs to be a deterministic. $\endgroup$ – Lawrence Sep 18 '19 at 14:12
  • 1
    $\begingroup$ I am sorry, my statement was ambiguous: In which way does the problem description say that the 'best deployment' must be a deterministic choice ? The choice of deployment might be randomized and optimal in expectation (actually, iirc, game theory's Nash equilibrium in mixed strategies and its existence theorem guarantees that such a choice exists). $\endgroup$ – collapsar Sep 18 '19 at 14:24
  • 1
    $\begingroup$ All that says is that the best deployment would have to be non-deterministic, which is kind of a reasonable assumption, as it applies for very many tasks in game theory. However, it does not mean that the best deployment strategy doesn't exist - I mean, it's proven that such conditions (Nash equlibrium) must exist for every game like this. $\endgroup$ – Peteris Sep 18 '19 at 16:29
  • 3
    $\begingroup$ But since the problem is symmetric, any optimal strategy, even a non-deterministic one, will be identical for both sides. There's no way to get an edge over your opponent. $\endgroup$ – Nuclear Hoagie Sep 18 '19 at 20:09
2
$\begingroup$

My take on it:

Given that each option is equally likely,

the "expected number" of soldiers in any enemy platoon is 10. So, in order to win the most battles, you would want to have at least 11 soldiers as many platoons as possible, which may be done by having 9 11 man platoons and 1 1 man platoon.

I think it is possible to get a proof (partitions?) to this also, which I will try.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Since your opponent is expected to apply this strategy, the optimum strategy is to 12 soldiers in each platoon. But if then, we would expect your opponent to have 12 soldier platoons and we should have 13... and so until we end with one 100 soldier platoon. $\endgroup$ – Pere Sep 18 '19 at 12:47
  • $\begingroup$ Well, obviously that makes this question frivolous. We are assuming here that every combination is equally likely. $\endgroup$ – Certainly not a dog Sep 18 '19 at 12:53
  • $\begingroup$ Well, the problem is not very well defined and a random opponent is a possible interpretation. However, I suggest adding that to the answer. In addition, each option being equally likely depends on the way the soldiers are distributed at random. $\endgroup$ – Pere Sep 18 '19 at 13:01
  • $\begingroup$ Yes, it is a bit of a bugger, and that is why I indeed did start my solution with that. I guess I should move it out of the spoiler. And, since the order of platoons and indeed the soldiers themselves is irrelevant, I don't see how there is any ambiguity in the randomness. $\endgroup$ – Certainly not a dog Sep 18 '19 at 13:11
  • $\begingroup$ @Pere The setup of the game wrt won engagements is symmetric, so any non-randomized strategy will be pursued by both opponents. Obviously this means 10 draws. $\endgroup$ – collapsar Sep 18 '19 at 13:15
2
$\begingroup$

Whatever distribution you end up making, you'll be facing the same quantity of elements in a mathematical set, that would be your undoing.

A distribution by 10 soldiers is superseded by 1x1 + 9x11 + N other such possibilities.

A distribution by 1x1 + 9x11 soldiers is superseded by 1x4 + 8x12 + N other such possibilities.

...

A distribution by X soldiers is superseded by N other such possibilities.

The "best" distribution's odds of success is as good as the "worst" distribution.

Any additional computing would lead to psychoanalysis of the human mind, in search of what the common human mind would decide to do, if they were indeed given such a choice. This though, does not lead to mathematics. It leads to something else.

There is no mathematical strategy in rock paper scissor, because it boils down to psychoanalysis - ways to influence your opponent into giving you a choice you can use to your advantage.

| improve this answer | |
$\endgroup$
2
$\begingroup$

RAND Corporation published an article about playing Colonel Blotto optimally here. The caveat is that their version is continuous while here we have to stick with non-negative integer numbers, but it's probably a good way to approximate a fairly optimal solution.

In the paper, they go over several cases. Fortunately this problem is covered under Case III (where the number of hills is more than 3, but there is a special condition that holds whenever each of the hills has the same weight. It claims that the optimal strategy is to draw a regular decagon, inscribe a circle over it, erect a hemisphere with the incircle as a great circle, and then pick a point at random on the hemisphere.

Then, project this point back to the plane containing the decagon, and then take the ratios of the projections to each side, which gives the ratios of the values you should assign to the hills.

| improve this answer | |
$\endgroup$
-1
$\begingroup$

Here is my attempt at a solution:

Part a of the question reads: "maximum chance of winning the most platoon engagements". The most platoon Engagements you can win is 9, that should be obvious. In the optimal case, you win each fight by having one more soldier in the respective platoon. Since the Maximum number of soldiers you can assign to 9 platoons is 99, you defeat 90 soldiers. This is the Maximum number of soldiers you can defeat while adhering to rules a and b. Since you Need perfect cooperation for this to happen (Enemy must always assign one less soldier to 9 of your platoons, every assignment where you have one platoon with exactly one soldier and every other platoon with at least 2 has equal chances to fulfill the requirements of the question.

Sorry for the bad formatting.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Enemy armies are not known for cooperating in their own destruction. $\endgroup$ – Sneftel Sep 20 '19 at 8:36
  • $\begingroup$ @Sneftel : But cooperation is needed to maximize amount of battles won while also maximizing amount of soldiers defeated. The Maximum amount of battles to win is 9, while the Maximum amount of soldiers to defeat is 90. For that to happen, you Need cooperation. Thus, it does not matter which described legal alignment you choose, your Chance remains the same. $\endgroup$ – Supersamu Sep 20 '19 at 14:23
-1
$\begingroup$

Well, so it's "mathematically" impossible to solve it, BUT there is my "casual" aproximation having 2 references:

  1. b)defeating the greatest number of opposition soldiers

  2. A platoon can have any number of soldiers

It means that if we knew that a platoon can have any number of soldiers, that includes that platoons can have 0 soldiers in each one except in one.

In this way you have a 100-platoon, which can win every case, or in the worst case possible, draw.

And if my chances are wining or draw, seems the best approximation for me, as loosing is not a part of my possible result.

| improve this answer | |
$\endgroup$
-1
$\begingroup$

Here is what I think: the best chance you have of winning without having more information about your opponent is to distribute the soldiers equally, 10 in each platoon. I didnt do the math and I might be wrong, but I think that in this case you can never lose, the worst outcome being a draw.

EDIT:

  • @collapsar yes, so obvious, ofc you would lose if the opponent distributes 11 in each platoon;
  • what about putting the max number, equally distributed in each platoon: this would be 5 platoons with 19 soldiers and 5 platoons with 1. How can the opponent beat you now?
| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You are mistaken. Assume an opponent who distributes 11 soldiers to each of the platoons #1-9, and 1 to #10 -> you lose 9/10 engagements, and by casualties 90:1. $\endgroup$ – collapsar Sep 18 '19 at 11:42
  • $\begingroup$ If you field only 10-men platoons your opponent sets 9 platoon of 11 men and a last platoon of a single soldier. Results: 9-1 for him. $\endgroup$ – Kotrin Sep 18 '19 at 11:43
  • $\begingroup$ UNLESS you set YOUR army as 8 platoons of 12 and two platoons of 2. You win eight, possibly 9. $\endgroup$ – Bob Jarvis - Reinstate Monica Sep 18 '19 at 11:44
  • $\begingroup$ The point, however, is that you don't know prior to revealing your army's setup just how your opponent's army will be configured. Fog of war and all that. Hmmm...I wonder what's for lunch..? Make reservations in Paris for us, will you, Darling? $\endgroup$ – Bob Jarvis - Reinstate Monica Sep 18 '19 at 11:51
  • 1
    $\begingroup$ @collapsar While I would like some more proof to his theory, finding possible scenarios where he loses is not really the point. The question asks which strategy has the best chance, not which strategy is unbeatable. $\endgroup$ – Mark Sep 18 '19 at 12:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.