See the following for riddle explanation & context: https://fivethirtyeight.com/features/how-much-is-a-spy-worth-in-a-warring-riddler-nation/
-
There will be at most one tie. (Grumble grumble tie rule adding extra complexity.) If there are two or more ties, move 1 soldier from the least important castle to the most important castle, yielding a strictly better score and 2 fewer ties. Additionally, if there is a tie, it will be for the least important castle - move 1 soldier from the weaker winning castle to the higher tying castle to get a strictly better score.
-
There's no point in "over" winning given these rules. So there's no need to examine winning combinations that defeat an "extra" castle for honor. Winning castle combinations can thus be reduced to "minimal" ones where the loss of ANY castle causes loss of the game. 28 points is the goal (out of 55). Some winning positions score more than 28, but never when taking / tying low-score castles.
-
Given 1 & 2, I wrote a Python script to produce all the possible "minimal" winning sets, of which there were 77. (
calculateWinOptions()) -
Given the number of possible winning sets, this can be applied to a defender formation to score it. Go through all the possible castle conquests from #3, calculate the soldiers required to beat the defender formation using that strategy, then take the minimum value, which is the most efficient strategy that uses the fewest # of soldiers. (
scoreDefense()) -
From a defender's perspective, I highly doubt it ever makes sense to not use a monotonically increasing number of soldiers. Why would you ever want to guard castle 10 less than castle 9? Barring some discrete math weirdness, it seems strictly optimal to guard higher-value castles more.
-
In the "continuous" case, where the defender had billions of soldiers and there were 55 castles of value 1, it's pretty clear to see that there's no point in getting fancy: each castle should be guarded the same amount, and failing to do this is just free points for your opponent. For example, abandoning 40% of your castles and spreading the rest of your forces among the remaining 60% allows an attacker to use defeat just 1/6 (17%) of your forces to win. Spreading equally means the attacker needs 50.1% of your strength.
-
As such, the "baseline" defense for the discrete case should also be similar (if not identical). Scoring each "point" as worthy of 1.8 soldiers of protection (100/55), you end up with [0, 2, 4, 6, 7, 9, 11, 13, 14, 16, 18] (this includes an irrelevant 0-strength castle to make list index logic nicer).
-
Defeating the baseline defense gives a naive, kneejerk result of 54 soldiers required, so the spy is worth 46 soldiers. Here are the 5 winning attacks on the baseline: [[0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1], [0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1]]
-
I added a function to try variants of the above defense that would modify the scores by -2 to +2 for each castle, so long as it still allocated 100 soldiers total and didn't violate the "non-decreasing number of soldiers by castle" rule #5. Going further away than 2 from the baseline seemed unlikely to be a good play. There ended up 395,300 different defender strategies generated by
createAlternates(). I then threw these modified defenses against our scorer. Result: [0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19] ended up being the best defense, requiring 56 soldiers to break it. It's very even, as there are 40 different attacks that all require 56 soldiers against it. (Amusingly enough, none of them involve ties, so the tie rule may have been a big distraction after all.) The fact that it's a simple progression of odd numbers makes me wonder if I missed some faster, non-computational way to solve the problem. Notably, the "price" ends up being 2 soldiers per "point", with it requiring 20 soldiers to take castle 10, 18 soldiers to take castle 9, etc. I'm not sure if there's a sneaky way to 'prove' that this is the best defense, although experimentally it clearly is.