Swords and Armor: A Game Theory Thought Experiment

post by nick012000 · 2010-10-12T08:51:28.673Z · score: 14 (41 votes) · LW · GW · Legacy · 78 comments

Note: this image does not belong to me; I found it on 4chan. It presents an interesting exercise, though, so I'm posting it here for the enjoyment of the Less Wrong community.

For the sake of this thought experiment, assume that all characters have the same amount of HP, which is sufficiently large that random effects can be treated as being equal to their expected values. There are no NPC monsters, critical hits, or other mechanics; gameplay consists of two PCs getting into a duel, and fighting until one or the other loses. The winner is fully healed afterwards.

Which sword and armor combination do you choose, and why?

78 comments

Comments sorted by top scores.

comment by Steve_Rayhawk · 2010-10-12T12:10:18.636Z · score: 20 (22 votes) · LW(p) · GW(p)

Gambit said the only equilibrium was mixed, with 1/5 each of (blue sword, blue armor), (blue sword, green armor), (yellow sword, yellow armor), (green sword, yellow armor), and (green sword, green armor).

With a stylin' bonus of ε points per duel (if a win is 1 point and a loss is −1 points), Gambit says for ε≤1/4 the equilibrium is:
(blue sword, blue armor): 1/5−(4/5)ε
(blue sword, green armor): 1/5−(3/5)ε
(yellow sword, yellow armor): 1/5+(4/5)ε
(green sword, yellow armor): 1/5+(3/5)ε
(green sword, green armor): 1/5

comment by Will_Newsome · 2010-10-12T12:27:59.012Z · score: 6 (8 votes) · LW(p) · GW(p)

>>2vc//
​>Note: this image does not belong to me; I found it on 4chan.
>>2vc//2sbt
​>Yellow yellow, because it looks the most awesome and seems like a generally decent combo,
>>2vc//2scc
​>Gambit says
​>(yellow sword, yellow armor): 1/5+(4/5)ε

File : Gambit_sez_small.jpg

comment by [deleted] · 2010-10-12T16:48:47.902Z · score: 6 (6 votes) · LW(p) · GW(p)

Uh-oh, LessWrong is turning into 4chan! :)

comment by AllegedWisdom · 2010-10-18T17:11:43.041Z · score: 0 (0 votes) · LW(p) · GW(p)

I do not see the logic behind this. Why would you ever choose to wear blue armor? No matter what weapon the opponent has, the best armor is either green or yellow. The blue weapon is only optimal against blue armor, but nobody should be wearing blue armor.

comment by JGWeissman · 2010-10-18T17:25:17.644Z · score: 1 (1 votes) · LW(p) · GW(p)

EDIT: The deleted comment this responds to claimed that you should never use the blue armor, because against any weapon, either the green or the yellow armor is better.

It can make sense to choose the armor that is not optimal in any case if it is good enough in more cases. There are no bonus points for winning by a larger margin.

comment by drc500free · 2010-10-18T13:56:44.073Z · score: 0 (0 votes) · LW(p) · GW(p)

This post is incorrect. You do need to consider the individual matchups, not the average damage taken and given. My suggestion loses 2-3.

I understand the same-color bonus, but it seems to break the results when you set the stylin bonus to 0. For each (blue, yellow, green) sword, I get the damage against (blue,red,yellow,green) armor to be:

  • Blue Sword: (6240, 6160, 6400, 6080)
  • Yellow Sword: (6150, 5975, 6500, 5700)
  • Green Sword: (5940, 6210, 5400, 6840)

For a sword distribution of (.4,.2,.4) and an armor distribution of (.4, 0, .4, .2) , I get expected values for swords of (6272, 6200, 5904) and for armors of (6102,6143,6020,6308).

That's not an equilibrium, is it? Against that population, why would I not pick the Blue Sword with the Yellow Armor, for an expected payoff of (6272,6020)?

comment by Meni_Rosenfeld · 2010-10-14T22:57:06.221Z · score: 0 (0 votes) · LW(p) · GW(p)

Gambit said the only equilibrium was mixed, with 1/5 each of (blue sword, blue armor), (blue sword, green armor), (yellow sword, yellow armor), (green sword, yellow armor), and (green sword, green armor).

FWIW, my calculations confirm this - you beat me to posting. One nitpick - this is not the only equilibrium, you can transfer weight from (blue, green) to (red, green) up to 10%.

comment by Will_Newsome · 2010-10-12T12:20:47.429Z · score: 0 (0 votes) · LW(p) · GW(p)

comment by Nominull · 2010-10-13T06:48:39.768Z · score: 8 (8 votes) · LW(p) · GW(p)

My general heuristic for these sorts of games is to play the option that beats the option that beats the option that looks best to me at first blush. In this case that means I play green sword, yellow armor. It's a reasonably fast heuristic that does reasonably well.

comment by machrider · 2010-10-13T00:03:53.429Z · score: 8 (8 votes) · LW(p) · GW(p)

Deleted earlier comment due to a bug in the code.

Here's the result of a naive brute force program that assumes a random distribution of opponents (i.e. any combo is equally likely), sorted by number of wins:

185: red/blue
269: red/red
397: yellow/blue
407: yellow/red
438: red/yellow
464: red/green
471: yellow/green
483: yellow/yellow
512: blue/yellow
528: green/green
539: green/red
561: green/blue
567: green/yellow
578: blue/red
635: blue/green
646: blue/blue

The program is here: http://pastie.org/1217024 (pipe through sort -n)

It performs 30 iterations of all 16 vs 16 matchups. Note that the player that attacks first has an advantage, so doing all 16 vs 16 balances that out (everyone is player 1 as often as he is player 2).

I signed up today to comment in this thread, so don't mock me too heavily. :)

Edit: Bumped iterations to 30 and hit points to 80,000 to try to smooth out randomness in the results.

comment by [deleted] · 2010-10-13T02:09:06.466Z · score: 6 (6 votes) · LW(p) · GW(p)

This, and your much clearer second test, are useful, but only insofar that the weapons are chosen equally. Though, as some have found out, they clearly won't be. This would be more useful if you tested with the combinations that seem best [e.g. blue/blue, blue/green, green/green] and dropped the ones that no one who can run even some of the math would play [e.g. red/any]. Could you try that and see if it changes any of the results drastically?

comment by machrider · 2010-10-13T02:27:35.158Z · score: 4 (4 votes) · LW(p) · GW(p)

Agreed, re: the limitations of my method. As you suggested, I ran another pass using only the top 7 candidates (wins >= 19 in my previous comment). Here are the results:

3: blue/red
5: blue/green
7: blue/blue
7: green/green
7: green/red
9: green/blue
11: green/yellow

Choosing the top 10 (wins >= 17 from before):

7: blue/red
7: red/green
9: green/green
9: green/red
11: blue/blue
11: blue/green
11: blue/yellow
11: green/blue
11: yellow/yellow
13: green/yellow

Yellow/yellow pops up as a surprise member of the 5-way tie for second place. The green sword is less effective once you introduce these new members. There are probably a lot of surprises if you keep varying the members you allow. And all of this still assumes a normal distribution, which is unlikely.

comment by machrider · 2010-10-13T02:58:16.632Z · score: 6 (6 votes) · LW(p) · GW(p)

Pursuing this stupidity to its logical conclusion, I just did an elimination match with 16 rounds. Start with all combinations and cull the weakest member every round. Here's the result: http://pastie.org/1217255

Note the culling is sometimes arbitrary if there's a tie for last place. By pass 14, we have a 3-way tie between blue/blue, blue/green, and green/yellow. Those may very well be the best three combinations, or close to it.

Final version of program here: http://pastie.org/1217284

(Removed randomness and just factored in the probability of evasion into damage directly. This lets me use smaller numbers and runs much faster. Verified that the results didn't change as a result of this.)

comment by [deleted] · 2010-10-13T02:47:14.354Z · score: 2 (2 votes) · LW(p) · GW(p)

Interesting. Three main observations:

1] blue/green has been a popular good choice, but in this bracket, not so much. I wonder how much sway this should have on all of our guesses.

2] the blue/blue combination that I figured works well tied for third, ironically with green/green and even more ironically, below green/blue.

3] green/yellow comes out on top, probably because no one else in this simulation is running yellow armor. I wonder if this changes when we add in blue/yellow, likely in place of blue/red.

Biggest question: Say we could make a simulation where we start with say, 10 characters, of each of these combinations, set them to wander about, and then when they beat someone, the person beaten adopts the winner's combination. I wonder if that would help our understanding of this game, or if it wouldn't work due to a quick, short-term dominance by one combination.

comment by shokwave · 2010-10-13T08:46:31.223Z · score: 5 (5 votes) · LW(p) · GW(p)

If they were beaten, they adopt a combination that would have beaten the opponent. The psychology of game-players in PVP games suggests that they would much prefer to use a different set of equipment rather than copy a set of equipment someone used against them.

To give the simulation an equilibrium, perhaps they have a small chance to adopt the winner's combination and otherwise adopt a combination that would have won.

comment by [deleted] · 2010-10-13T17:08:07.194Z · score: 3 (3 votes) · LW(p) · GW(p)

If they were beaten, they adopt a combination that would have beaten the opponent. The psychology of game-players in PVP games suggests that they would much prefer to use a different set of equipment rather than copy a set of equipment someone used against them.

Goodness, thank you! I had that correct in my first comment on this whole post, as I played an MMO called Guild Wars avidly for a while. I apparently forgot that here. It does make the simulation somewhat more challenging to model.

comment by machrider · 2010-10-13T01:36:32.827Z · score: 4 (4 votes) · LW(p) · GW(p)

I'm thinking iterations just confuses things. With a high enough HP value we should be able to eliminate "luck". So here's a pass with 1 iteration and 20 million initial HP:

2: red/blue
8: red/red
13: yellow/blue
13: yellow/red
15: red/yellow
15: yellow/green
17: blue/yellow
17: red/green
17: yellow/yellow
19: blue/red
19: green/blue
19: green/green
19: green/red
19: green/yellow
21: blue/blue
23: blue/green
comment by machrider · 2010-10-13T01:02:19.506Z · score: 0 (0 votes) · LW(p) · GW(p)

Just did another trial with initial HP set to 1 million (still 30 iterations). Took a while. Results:

63: red/blue
247: red/red
391: yellow/blue
397: yellow/red
450: red/yellow
463: yellow/green
507: yellow/yellow
510: blue/yellow
518: red/green
566: green/red
567: blue/red
568: green/yellow
569: green/blue
570: green/green
633: blue/blue
661: blue/green

I think the higher HP value does a great job of reducing the effect of randomness. You can see red/blue has dropped significantly while blue/green has emerged as probably the best combination against a random opponent. The biggest surprise to me in all of this is how well the blue sword does; it seems so "average".

comment by RichardKennaway · 2010-10-12T11:09:14.381Z · score: 4 (8 votes) · LW(p) · GW(p)

This is a zero-sum game with the same 16 strategies for each player. If player 1 does damage A1 (for attack), S1 times per (say) hour, and player 2 has armour that cancels D2 points from a successful attack and gives E2 (evade) percent change of dodging, the rate of damage by player 1 on player 2 is S1*(1-E2/100)*(A1-D2). Subtract from this the same expression with 1 and 2 swapped and that is the differential rate. Given the conditions of the problem, the only thing that matters about this rate is its sign. So there's a 16*16 payoff matrix with entries 1, 0, and -1.

I've computed it, and it turns out that no strategy dominates any other: every row contains at least one -1 in a column containing at least one 1. However, I forget how to compute a minimax mixed strategy for such games. I think it's a linear programming problem, and for 16 variables it can't be done manually unless the data have some regularity to be exploited. Eyeballing the matrix, I don't see any.

comment by SeventhNadir · 2010-10-13T00:05:22.112Z · score: 3 (3 votes) · LW(p) · GW(p)

16 possible combination's of Weapon/Armor available, 256 possible combination's of Weapons/Armor between two players.

Only factor in deciding a winner between players is the player with the higher DPS, the margin between the two players is irrelevant.

So you work out the winner in each of the 256 match-ups (16 mirror matches will be stalemates). Armed with the knowledge of what-beats-what, it's just a matter of knowing the distribution what combo's other players went and selecting the best armor/sword combo for that population.

Do these steps seem right?

I'd actually kind of like to work this out, but there has to be a better way to work out the 256 combo's than doing it all by hand. Any suggestions?

comment by wnoise · 2010-10-13T16:49:25.466Z · score: 5 (5 votes) · LW(p) · GW(p)

I'd actually kind of like to work this out, but there has to be a better way to work out the 256 combo's than doing it all by hand. Any suggestions?

This is one reason why knowing a little bit of programming is worthwhile, even if you don't intend to use it as a career. (Several full tables have been posted, BTW).

comment by [deleted] · 2010-10-12T17:26:07.499Z · score: 3 (3 votes) · LW(p) · GW(p)

After running through a 4x4 matrix, I figured that blue/blue was the best overall. Nothing can outdamage you unless it's by x/green armor, which then gets owned by everyone with a green/x so everyone else starts playing green/green and ties, until eventually some smart guy swaps to green/blue. Thus, you laugh for a while as everyone else follows and lose to your original blue/blue, starting the cycle again.

Matrix + human psychology for laughs [and wins?]

Personally, I'm caught between how awesome the green sword looks and the style of going blue/blue [plus blue/blue deals with everyone else's odd choice of yellow/yellow]. And I'm sure others probably know how to work the dominance form better e.g. Gambit or rosyatrandom.

comment by HughRistik · 2010-10-12T22:03:57.033Z · score: 10 (10 votes) · LW(p) · GW(p)

I haven't checked your math, but you have the psychology right for MMOs. Basically, figure out what the Flavor of the Month is, and then play what counters it.

See Dave Sirlin's discussions of yomi layer 3 and rock, paper, scissors.

Yomi is the Japanese word reading, as in reading the mind of the opponent. If you can condition your enemy to act in a certain way, you can then use his own instincts against him (a concept from the martial art of Judo). Paramount in the design of competitive games is the guarantee to the player that if he knows what his enemy will do, there is some way to counter it.

What happens, though, when your enemy knows that you know what he will do? He needs a way to counter you. He's said to be on another level than you, or another "Yomi Layer." You knew what he would do (yomi), but he knew that you knew (Yomi Layer 2). What happens when you know that he knows that you know what he will do (Yomi Layer 3)? You'll need a way to counter his counter. And what happens when he knows that you know....

[...]

Before we get into how ordinary human minds can become entangled in complicated guessing games, let's look at what needs to be there to create these guessing games at all. The designer's tendency might be to create moves and counters. Then create counters to counters, then counters to counters to counters, then counters to those, and so on. Actually, a game need only support counters up to Yomi Layer 3, since Yomi Layer 4 can loop around back to Yomi Layer 0.

Let's say I have a move (we'll call it "m") that's really, really good. I want to do it all the time. (Here's where the inequality of risk/reward comes in. If all my moves are equally good, this whole thing falls apart.) The "level 0" case here is discovering how good that move is and doing it all the time. Then, you will catch on and know that I'm likely to do that move a lot (Yomi Layer 1), so you'll need a counter move (we'll call it "c1"). You've stopped me from doing m. You've shut me down. I need a way to stop you from doing c1. I need a counter to your counter, or "c2."

Now you don't know what to expect from me anymore. I might do m, or I might do c2. Interestingly, I probably want to do m, but I just do c2 to scare you into not doing c1 anymore. Then I can sneak in more m.

You don't have adequate choices yet. I can alternate between m and c2, but all you have is c1. You need a counter to c2, which we'll call c3. Now we each have two moves.

Me: m, c2 You: c1, c3.

Now I need a counter to c3. The tendency might be to create a c4 move, but it's not necessary. The move m can serve as my c4. Basically, if you expect me to do my counter to your counter (rather than my original good move m), then I don't need a counter that; I can just do go ahead and do the original move...if the game is designed that way. Basically, supporting moves up Yomi Layer 3 is the minimum set of counters needed have a complete set of options, assuming Yomi Layer 4 wraps around back to Layer 0.

comment by khafra · 2010-10-13T17:35:00.875Z · score: 2 (2 votes) · LW(p) · GW(p)

Couldn't the second player use m in place of c3 in most game mechanics which would allow the first to use m instead of c4?

comment by ShardPhoenix · 2010-10-14T06:48:59.876Z · score: 2 (2 votes) · LW(p) · GW(p)

I think it's assuming that the player's abilities are generally asymmetrical, like in a fighting game.

comment by rosyatrandom · 2010-10-12T09:58:42.580Z · score: 3 (3 votes) · LW(p) · GW(p)
    D    S    D*S        a1        a2        a3        a4    
s1    100    80    8000    6336    6256    6400    6080    6268
s2    80    100    8000    6120    6120    6000    6080    6080
s3    150    50    7500    6210    6035    6500    5700    6111.25
s4    50    180    9000    6156    6426    5400    6840    6205.5
                    6205.5    6209.25    6075    6175    


                Da    -12        -8        -20        0    
                Do    0.1        0.15    0        0.24    

My first instinct was to make the table above, which may or may not be readable here (EDIT: mostly readable, some tab glitches). I first calculated each sword's damage per minute (obviously, in general you want the highest value here), and then worked it out as applied to each armour type.

Here's where it gets... tricky, as you want the sword that maximises damage to all armour types, and the armour that minimises damage from all sword types. Do we look at average values? That could leave you open to being gamed by someone whose choices are poor except against your specific choices.

The best average choice here, by the way, is clearly Sword 1 (Blue) and Armour 3 (Yellow). But Sword 1 is not the best choice against Armours 2 and 4, and Armour 3 is not the best choice against Swords 1 and 3.

Nevertheless, the difference is small enough that I would still go with them; in the end, I think, being optimal like that is still the best strategy, as players with worse choices will be outcompeted. I am niggled by the thought that the optimal armour is not actually optimal against the optimal sword, but I don't think you can really do anything about that

comment by AllegedWisdom · 2010-10-18T17:02:12.734Z · score: 0 (0 votes) · LW(p) · GW(p)

I got the same numbers.

With that payoff matrix, you can quickly see that both the red and blue armors are dominated. You should never use either. If the opponent has a blue weapon (s1) you want green armor (a4) so you take the least damage. If they have a red weapon (s2), you want yellow armor (a3). If they have a yellow weapon (s3), you want green armor (a4). If they have a green weapon (s4), you want yellow armor (a4).

This shrinks the strategy space considerably. In equilibrium, everyone will have yellow or green armor. If they have yellow armor (a3), then you want the yellow weapon (s3) to damage them the most. If they have the green armor (a4) then you want the green weapon (s4).

So everyone should be randomizing between yellow and green armor, and yellow and green weapons.

comment by magfrump · 2010-10-14T03:33:14.571Z · score: 2 (2 votes) · LW(p) · GW(p)

I'd play green/yellow; it seems like it would do well among the top choices, plus I like weapons that attack fast.

I began working out the 16x16 matrix but then I realized I could just read the thread and somebody would have already worked it out. Machrider's simulations seem like the most convincing since they're the only ones that account for multiple rounds of selection.

comment by shokwave · 2010-10-12T19:15:33.388Z · score: 2 (2 votes) · LW(p) · GW(p)

Since you're fully healed at the end of the fight, the actual amount of damage you do or take is less relevant; whether you did more than the opponent is more relevant. To that end, I worked out the survival time in each armor against each sword and ranked them from worst case scenario to best case scenario. Now each armor has four different lifespans (worst to best) - and, for each sword, I worked out how many of the four armors could be killed in each lifespan. (4 armors x 4 enemy swords = 16 lifespans, 16 lifespans x 4 your swords = 64 different amounts of damage). So in the end, for each of the 16 combinations of equipment, the table gave me 4 numbers of wins (worst case, second worst, second best, best case). Note that the mirror match comes somewhere in between worst case and best case since it's a draw.

By these calculations, blue sword / green armor is the best (0, 3.5, 3.5, 4), closely followed by blue sword / blue armor (1.5, 3, 3, 3). There's a four-way tie for third, with blue sword / red armor (0, 2.5, 3, 4), green sword / blue armor (2, 2, 2.5, 3), green sword yellow armor (1, 2, 3, 3.5) and green sword / green armor (0.5, 3, 3, 3). Depending on how strong trends are, any of these could be the temporary best.

Incidentally, the worst option is red sword / blue armor - it has the dubious distinction of being unable to win any matchup, and tie only two.

comment by jhl · 2010-10-12T17:30:18.629Z · score: 2 (2 votes) · LW(p) · GW(p)

Strategy:

  1. Minimize worst-case damage taken.
  2. Maximize worst-case damage inflicted.

Implementation:

http://codepad.org/KEqxSa4j

Results:

  • Selected Armor: blue with max damage 6336.0
  • Selected Sword: blue with min damage 6080.0
comment by [deleted] · 2010-10-12T12:41:50.609Z · score: 2 (4 votes) · LW(p) · GW(p)

What I find interesting is that even though this post is being downvoted, there are an awful lot of people still taking the time to think about it :)

comment by RichardKennaway · 2010-10-12T19:37:32.482Z · score: 7 (7 votes) · LW(p) · GW(p)

Well-known memetic hazard.

comment by PlaidX · 2010-10-12T09:41:32.109Z · score: 2 (2 votes) · LW(p) · GW(p)

The red sword is strictly worse than the blue sword. Beyond that I'm too lazy to figure it out.

comment by rosyatrandom · 2010-10-12T10:29:56.493Z · score: 4 (4 votes) · LW(p) · GW(p)

That's true; despite having the same damage per minute, the red swords stats are harmed more by armour damage reduction (since if x<y, (x-a)y < x(y-a)).

It should be noted that the Armour Damage stat only affects a Sword's Damage stat, while Dodge is global: Mitigated Damage per minute = (Sword Damage + Armour Damage) Speed (1-Dodge)

comment by Relsqui · 2010-10-12T18:07:58.763Z · score: 1 (1 votes) · LW(p) · GW(p)

That's true; despite having the same damage per minute, the red swords stats are harmed more by armour damage reduction

But the blue sword is harmed more by dodging, because it has fewer chances in a minute to do any damage at all. If we were looking at just dodge, and not damage absorption, the red one would do more damage in (100-dodge)% of a minute's worth of attacks.

Does the absorption factor outweigh that, then? :)

comment by Jonathan_Graehl · 2010-10-12T21:48:24.145Z · score: 2 (2 votes) · LW(p) · GW(p)

But the blue sword is harmed more by dodging, because it has fewer chances in a minute to do any damage at all

No sword is harmed more or less by dodging than any other sword, under the stated assumption that hit points are large enough that the results are effectively always equal to their expectations.

comment by Relsqui · 2010-10-12T22:49:29.439Z · score: 2 (2 votes) · LW(p) · GW(p)

That reasoning didn't get the point across to me at all, but I sat down to do the math and see how it worked out for myself and you're right. Never mind. :)

comment by Jonathan_Graehl · 2010-10-12T23:46:38.275Z · score: 1 (1 votes) · LW(p) · GW(p)

I omitted my reasoning. I'm glad you found it for yourself :)

comment by Relsqui · 2010-10-12T17:51:22.841Z · score: 0 (0 votes) · LW(p) · GW(p)

That's true; despite having the same damage per minute, the red swords stats are harmed more by armour damage reduction

But the blue sword is harmed more by dodging, because it has fewer chances in a minute to do any damage at all. If we were looking at just dodge, and not damage absorption, the red one would do more damage in (100-dodge)% of a minute's worth of attacks.

Does the absorption factor outweigh that, then? :)

comment by AdShea · 2010-10-12T10:41:02.452Z · score: 0 (0 votes) · LW(p) · GW(p)

This is the correct equation for any attack pair. Now just need to do a 16-16 table to see what wins over what. I'll do it during lecture tomorrow.

comment by rosyatrandom · 2010-10-12T11:03:37.921Z · score: 14 (16 votes) · LW(p) · GW(p)

You mean this table? :)

(This and the one I made below can be seen properly at http://tinyurl.com/lwgttable , along with the ATT vs DEF tables I worked out the outcomes from)

Hmm. Unless this has gone wrong, the best combo is Sword 1 and Armour 4, with Sword 1/Armour 1 being close). But if you bank on people choosing 1/4, then 1/1 will beat them.

NB: Yes, I made a lot of mistakes and edits to get here, and probably have still made some...

VS        a1         a1    a1    a1    a2    a2    a2    a2    a3    a3    a3    a3    a4    a4    a4    a4
        s1        s2    s3    s4    s1    s2    s3    s4    s1    s2    s3    s4    s1    s2    s3    s4
a1    s1    0.5        0    0    0    1    0    0    0    0    0    0    0    1    1    1    1
a1    s2    1        0.5    1    1    1    0.5    1    1    1    1    1    1    1    1    1    1
a1    s3    1        0    0.5    0    1    1    1    1    0    0    0    0    1    1    1    1
a1    s4    1        0    1    0.5    0    0    0    0    1    1    1    1    0    0    0    0
a2    s1    0        0    0    1    0.5    0    0    1    0    0    0    1    1    1    0    1
a2    s2    1        0.5    0    1    1    0.5    0    1    1    1    1    1    1    1    0    1
a2    s3    1        0    0    1    1    1    0.5    1    0    0    0    0    1    1    1    1
a2    s4    1        0    0    1    0    0    0    0.5    1    1    1    1    0    0    0    0
a3    s1    1        0    1    0    1    0    1    0    0.5    0    1    0    1    0    1    0
a3    s2    1        0    1    0    1    0    1    0    1    0.5    1    0    1    0    1    0
a3    s3    1        0    1    0    1    0    1    0    0    0    0.5    0    1    1    1    0
a3    s4    1        0    1    0    0    0    1    0    1    1    1    0.5    0    0    0    0
a4    s1    0        0    0    1    0    0    0    1    0    0    0    1    0.5    0.5    0    1
a4    s2    0        0    0    1    0    0    0    1    1    1    0    1    0.5    0.5    0    1
a4    s3    0        0    0    1    1    1    0    1    0    0    0    1    1    1    0.5    1
a4    s4    0        0    0    1    0    0    0    1    1    1    1    1    0    0    0    0.5
_    _    10.5    1    6.5    9.5    9.5    4    6.5    9.5    8.5    7.5    8.5    9.5    11    9    7.5    9.5
comment by Snowyowl · 2010-10-12T14:01:30.714Z · score: 3 (3 votes) · LW(p) · GW(p)

You worked that out that yourself? (upvoted) Working out the best strategy is unfortunately a bit more complicated than just summing up each column, since by that logic everyone would go Green/Blue, and you'd then beat them with Red/Green or something else that beats Green/Blue. But I'm still impressed with your matricial mastery.

comment by rosyatrandom · 2010-10-12T18:00:21.389Z · score: 1 (1 votes) · LW(p) · GW(p)

Yeah, it wasn't that difficult once I worked out how to set it up. I used the table below of Sword vs Armour damages with an index function based on the numbers in the row/column headings. Here's an example:

=INDEX($E$2:$H$5,RIGHT(O$14),RIGHT($A22))

E2:H5 is the Swords vs Armour table.

O14 is the s1 part of the a4|s1 column label.

A22 is the a2 part of the a2|s4 row label.

Thus, this works out the mitigated attack value of Sword 1 vs Armour 2. This table as a whole worked out the mitigated attacks for columns versus rows. A second table worked out rows vs columns, and the table shown above merely compared the two values.

I agree though, the strategy is complex and I think perhaps in these situations always comes down to how risky/analytical you think the other players going to be, and how you think they think they're going to judge everyone else. And... well, how do you even start doing that? Especially since, most of the time, people will just... stop behaving rationally when faced with this kind of situation.

comment by AdShea · 2010-10-12T15:08:01.278Z · score: 2 (2 votes) · LW(p) · GW(p)

That looks like what I got. It'd be interesting to do a cycle analysis like you do with Non-transitive Dice.

comment by Jordan · 2010-10-13T00:50:46.944Z · score: 2 (2 votes) · LW(p) · GW(p)

Thanks for the mini mind blow with the non-transitive dice link.

Can you elaborate on what cycle analysis is?

comment by AdShea · 2010-10-13T15:04:10.388Z · score: 3 (3 votes) · LW(p) · GW(p)

Cycle analysis is basically drawing out a graph (nodes and edges) of what beats what. For standard Rock-paper-scissors you get a graph that looks like this:

ROCK -------> SCISSORS -------> PAPER

^-----------------------------------------------|

In systems that aren't balanced like the sword and armor problem here you can use it to decide what choice to make by giving each node a probability value based on how many people in game use that and then the best choice would be the node with the greatest (sum of probabilities on outgoing nodes) - (sum of probabilities on incoming nodes).

comment by nick012000 · 2010-10-13T06:18:23.126Z · score: -1 (1 votes) · LW(p) · GW(p)

Nice chart. This one's better, though; it clearly lists which sword and armor win, as well as listing number of losses and ties. I got it from the same thread as the one in the OP; I was just waiting until someone suggested doing something like this before I posted it.

Didn't want to take away your fun, after all. ;)

comment by JJ10DMAN · 2010-11-14T07:27:41.268Z · score: 1 (1 votes) · LW(p) · GW(p)

This has more to do with human psychology than strict mathematical game theory:

As an obsessive gamer and game designer: when fighting a random opponent, unless there is a ladder system and you end up in the top 2% or so of the population, the optimal strategy is to counter whatever is the optimal strategy vs. a null, average, or un-equipped person. That is to say, the vast majority of players who do not make a nearly-random selection will calculate the ideal strategy against a percieved "average" or "typical" set of values for damage/speed/armor/dodge, and then stop exactly there. So to win, you need to go exactly one step beyond that and then stop exactly there.

comment by MrEff · 2010-10-18T21:33:53.644Z · score: 1 (1 votes) · LW(p) · GW(p)

I think using a 16x16 strategy matrix just obscures the issue. Your choice of sword is never affected by the opponent's choice of sword; it seems that way because switching swords could turn a loss into a win, but that is a simple optimization, not a game theoric calculation. Your opponent changing his sword will never alter your best choice of sword (taking armor as fixed). What we really have is two 4x4 games that happen to be identical, requiring a single solution.

So I drew the 4x4 sword vs armor type matrix and solved for dominated strategies. Going through the table and marking best responses, I reduced it like this:

  1. Red is never the best sword for any armor. Although it isn't dominated by any other single strategy, the mixed strategy "blue or yellow or green sword" does dominate it. While it seems that a strategy could be "good enough" in any situation while never being the best, in fact such a strategy is never optimal. You can Google this reasoning method as "never a best response".

  2. Similarly, neither the red armor nor the blue armor is ever a best response to any type of sword. Eliminate both choices.

  3. Redraw the matrix with the remaining choices, discarding the red sword and the red and blue armors.

  4. With the blue armor nor longer a viable choice, the blue sword is never a best response to the remaining choices (yellow or green armor). Eliminate.

  5. We now have a 2x2 matrix of (green, yellow) and (green, yellow). If you assume that the margin of victory is unimportant, the equilibrium strategy is to mix green sword and yellow sword 50/50 and to mix green armor and yellow armor 50/50.

However, in any actual MMO, the margin of victory is important. You require less healing, or you can do more damage to a second opponent before you die, or you are less likely to suffer an unexpected defeat due to randomness. Using the actual damage/second numbers, you will choose the green sword only 35.7 percent of the time, and the green armor 49 percent of the time. The final answer will be between these two situations and requires more information to calculate.

Choosing blue/green because it has the most wins vs. the field is not a great solution method, because "the field" will simultaneously be choosing optimal strategies as well. You will certainly not face an equal distribution of opposing strategies. It is possible to calculate what you will face if you assume the opponents are all close to rational.

Because each weapon and each armor must be the best response to something to ever be worth choosing, the number of viable armors and the number of viable swords must be equal.

I didn't add in a stylin' bonus, but you have a 50% chance to be stylin' already so it shouldn't make a big difference.

I am not quite certain how Steve Rayhawk got a different answer out of Gambit. I assume it's because he used wins/losses instead of dps numbers, which turned some strongly dominated strategies into weakly dominated strategies and kept them alive.

comment by JGWeissman · 2010-10-19T00:56:53.376Z · score: 2 (2 votes) · LW(p) · GW(p)

I am not quite certain how Steve Rayhawk got a different answer out of Gambit. I assume it's because he used wins/losses instead of dps numbers,

Yes. In this problem we are concerned with winning a duel, and not with the margin of victory. The problem statement includes "The winner is fully healed afterwards."

comment by wedrifid · 2010-10-19T02:19:19.229Z · score: 1 (1 votes) · LW(p) · GW(p)

However, in any actual MMO, the margin of victory is important. You require less healing, or you can do more damage to a second opponent before you die, or you are less likely to suffer an unexpected defeat due to randomness. Using the actual damage/second numbers, you will choose the green sword only 35.7 percent of the time, and the green armor 49 percent of the time. The final answer will be between these two situations and requires more information to calculate.

Add in "you are more likely to win despite the opponent being more skilled or having a better connection".

comment by ata · 2010-10-15T20:43:57.963Z · score: 1 (1 votes) · LW(p) · GW(p)

I'm not familiar with PvP MMOs or how this kind of gameplay works. What do damage/speed/dodge signify? Is it turn-based or continuous?

comment by James_K · 2010-10-14T04:17:41.785Z · score: 1 (1 votes) · LW(p) · GW(p)

I've given the problem a quick pass and I can conclude this much:

1) Using the red weapon is weakly dominated, so definitely don't do that.

2) There's no Nash equilibrium in pure strategies, so if there's an equilibrium, it's in mixed strategies. If I have time over the weekend, I might re-learn how to do Lagrange Multiplier calculus and then I'll have a go at calculating a mixed strategy equilibrium.

comment by John_Maxwell (John_Maxwell_IV) · 2010-10-14T04:05:50.339Z · score: 1 (1 votes) · LW(p) · GW(p)

Some pagelong computer program I wrote says that these are the dominant strategies:

(sword damage, sword speed) (armor damage, armor dodge)
(100,  80) (-12,  10)
(100,  80) (-20,   0)
(100,  80) (  0,  24)
( 80, 100) (  0,  24)
(150,  50) (-20,   0)
( 50, 180) (-20,   0)
( 50, 180) (  0,  24)

I suppose I'd pick one at random because I'm too lazy to figure out what the right mixed equilibrium is.

comment by RolfAndreassen · 2010-10-12T19:22:49.242Z · score: 1 (1 votes) · LW(p) · GW(p)

So, along with a lot of other people I did a win/loss matrix, and I find a different answer from anyone else's. By my calculation, Yellow Sword / Green Armour strictly dominates.

Under the given hypothesis of very large HP, the winner of a duel is simply the one that does most expected damage per minute; the formula is (damage-reduction)(speed(1-dodge)).

I think rosyatrandom's table must be wrong. He says that B/B beats B/G, which is false; consequently there must be a mistake in his calculation. Consider: The blue sword does 100x80x0.76=6080 damage to the green armour, and 88x80x0.9=6336 damage to the blue armour; consequently blue sword and green armour beats blue sword and blue armour.

Edit: Never mind, I made a mistake in my script. Back to the drawing board until I find the bug.

Edit2: I'd put in the wrong speed values for the yellow and green swords. Now I don't find a dominant strategy.

comment by RichardKennaway · 2010-10-12T11:44:13.935Z · score: 1 (1 votes) · LW(p) · GW(p)

A lot of different answers have been posted. Are we being marked on this?

comment by Will_Newsome · 2010-10-12T10:09:17.419Z · score: 1 (3 votes) · LW(p) · GW(p)

Yellow yellow, because it looks the most awesome and seems like a generally decent combo, and also because it might be a slightly suboptimal but odd combo that people wouldn't prepare for, and also because I'm too lazy to do math.

comment by vvineeth4u · 2010-10-18T13:21:24.109Z · score: 0 (0 votes) · LW(p) · GW(p)

It always depends on the choice of the opponent. If the damage caused by the opponents weapon is less than or equal to 80 ({50,80}) choose the yellow armour, for the other available choices ({100,150}) choose the green armour to minimize damage per attack.

Regarding the choice of weapon, always choose green to inflict maximum damage in a given amount of time.

So the best strategy is to go with a yellow armour and green weapon if one has no prior knowledge.

comment by shokwave · 2010-10-16T17:35:48.541Z · score: 0 (0 votes) · LW(p) · GW(p)

So, uh, after this post, knowing that some people are going to see the mixed strategy equilibrium, some are going to calculate the best combo given all combos are represented equally, some are going to pick based on style, etc etc... the best strategy would then be assign a prior probability to the chances of each analysis being made by your opponent, weight each analysis's "best picks" according to the prior, and build a representation of the field you are likely to face - then pick the best combo against that specific field?

If that's correct then the critical question is how accurate your priors are. So my answer looks something like "Pick the member of the equilibrium that performs best against other members that might be chosen for other reasons, cause they will be over-represented compared to other equilibrium members." That looks like Rayhawk's ε points for style calculation in gambit, except you consider ε to be a constant for "irrationally disposed towards x".

Of course, over time you'd gather statistical data and you could use it to refine your priors on analysis/irrational dispositions, but with that data you don't need any of this, you can just do simple statistics.

comment by aausch · 2010-10-15T21:49:32.024Z · score: 0 (0 votes) · LW(p) · GW(p)

I once played a game where a similar kind of setup was arranged with armour - however, the armour selection was not necessarily fixed over each battle. Players could effectively change armour at specific points throughout the combat.

If you want to try an even more interesting arrangement, imagine players get to switch one item of their setup every, say, 10 or 15 rounds.

comment by Eliezer Yudkowsky (Eliezer_Yudkowsky) · 2010-10-15T05:37:21.473Z · score: 0 (4 votes) · LW(p) · GW(p)

Out of those four colors? Blue/blue, of course, because I'm RAVENCLAW!

comment by machrider · 2010-10-12T23:41:06.612Z · score: 0 (0 votes) · LW(p) · GW(p)

This problem seems to get a bit more complicated in the game theoretical sense of trying to guess what the average opponent will be equipping. A naive assessment of the expected damage inflicted and expected damage taken led me to think green/green is the best combo.

Then I wrote this stupid brute force program that fights every combo against each other 10 times and tallies up wins: http://pastie.org/1216986

Running it through | sort -n, I get:

10: yellow/yellow
30: blue/yellow
50: red/yellow
72: yellow/blue
105: blue/blue
105: yellow/red
133: red/blue
136: green/yellow
177: blue/red
183: red/red
210: green/blue
242: yellow/green
247: green/red
271: blue/green
279: red/green
310: green/green

So against a truly randomized field of players, green/green is indeed the combo that will most likely win. However, if the opponents typically favor only a few of the above combos, the result might be different.

Edit: Funny observation about yellow/yellow having 10 wins (after 10 trials of every matchup): yellow/yellow only wins when it is against yellow/yellow. Someone has to win that fight, so 10 is the minimum wins any combo can have. Against all other combos, yellow/yellow always loses.

comment by steven0461 · 2010-10-12T20:43:52.100Z · score: 0 (0 votes) · LW(p) · GW(p)

The letter of the question doesn't say you and your opponent have common knowledge of each other's rationality, and it's not clear that that's the spirit of the question either. I'd probably just play whatever does best against a random choice.

comment by steven0461 · 2010-10-12T20:31:10.139Z · score: 0 (0 votes) · LW(p) · GW(p)

Why do all these answers assume the opponent is rational?

comment by Matt_Simpson · 2010-10-12T15:58:56.682Z · score: 0 (0 votes) · LW(p) · GW(p)

If you assume the payoffs are damage and not just victory, you can treat this as a 4x4 zero sum game since weapon choice has no effect on armor effectiveness and vice versa. Then you can calculate the damage per minute for every weapon vs. every armor, and dominance reasoning yields: blue sword, green armor.

But that assumption is probably not accurate and I'm too lazy to compute the 16x16 win/loss payoff matrix, so what Steve Rayhawk said.

comment by RobinZ · 2010-10-12T16:37:41.899Z · score: 1 (1 votes) · LW(p) · GW(p)

Blue sword, green armor loses to green sword, blue armor: it deals (100-12)*0.9*80 = 6336 damage/minute and takes (50-0)*0.76*180 = 6840 damage/minute. rosyatrandom has the 16x16 table.

comment by Matt_Simpson · 2010-10-12T17:16:05.010Z · score: 0 (0 votes) · LW(p) · GW(p)

But green sword/blue armor loses to something else. Dominance reasoning isn't supposed to guarantee that your strategy beats everyone.

OTOH, my 4x4 table doesn't look like the one rosyatrandom linked to, so I may have made a computational error.

comment by RobinZ · 2010-10-12T17:31:18.133Z · score: 2 (2 votes) · LW(p) · GW(p)

But green sword/blue armor loses to something else. Dominance reasoning isn't supposed to guarantee that your strategy beats everyone.

Oh! I thought you were using the game-theoretic definition of "dominance", where one strategy always beats (or always beats or matches) another strategy. For example, in this game, any red-sword strategy is dominated by the corresponding blue-sword strategy.

comment by Matt_Simpson · 2010-10-12T18:58:10.864Z · score: 0 (0 votes) · LW(p) · GW(p)

Well I was, but I didn't mean to say that blue/green dominates everything else (imprecise language on my part). If you iteratively remove dominated strategies on both sizes you're left with blue/green - which is thus a Nash Equilibrium. At least on my table, but I don't trust my numbers anymore.

comment by Morendil · 2010-10-12T11:22:34.588Z · score: 0 (0 votes) · LW(p) · GW(p)

Everyone will choose the armor which minimizes the maximum damage you can take from an opponent, and choose the weapon which maximizes the minimum damage you can inflict on an opponent. Green/green.

I'm assuming the equation is (speed(1-dodge))(damage-dmg_reduction) expected HP loss per minute.

comment by wnoise · 2010-10-12T11:17:51.395Z · score: 0 (0 votes) · LW(p) · GW(p)

Green sword and yellow armor.

There is one mixed Nash equilibrium with lopsided majority blue armor, minority green, and nearly even majority green sword, minority yellow. I expect people to be biased more towards handling the majority of the cases.

EDIT: this is using the damage per time as the utility. This decouples the choice of armor and sword so that it's really one 4x4 game where you play both sides. Time for survival would be another reasonable utility, which can be had just by inverting the damage numbers.

comment by Bongo · 2010-10-12T10:19:53.435Z · score: 0 (0 votes) · LW(p) · GW(p)

Green & Green/Yellow

Green sword has the best damage*speed. For armor, assume the average hit does 100 damage. Then p% dodge is as good as -p damage, and green wins there, too.

But! If everyone else reasons that the green sword is best, too, then the average hit would do 50 damage, and the best armor would be yellow.

comment by Morendil · 2010-10-12T11:30:14.030Z · score: -1 (1 votes) · LW(p) · GW(p)

Everyone will choose the armor which minimizes the maximum damage you can take from an opponent, and choose the weapon which maximizes the minimum damage you can inflict on an opponent. Green/green.

I'm assuming the equation is (speed x (1-dodge)) x (damage-dmg_reduction) expected HP loss per minute.

comment by Arcy · 2010-10-20T04:33:40.763Z · score: 1 (1 votes) · LW(p) · GW(p)

Pardon me if I am incorrect, but it seems to me that there is a basic assumption going on that everyone, given those clear choices, will think rationally and crunch the numbers themselves in order to find the optimal choice, given a scenario I'd either equal representation or strictly against the "best" choices. I can understand the reasoning behind this, especially given the high percentage Iof people on this particular thread who are willing to do the math, but is it not also a safe assumption that neither of these scenarios will be the case, given that there will be a large percentage of copy cats and almost an equally large percentage Iof people choosing irrationally based on initial inclinations? I can appreciate the work everyone has done in calculating statistics, but honestly, so much of the true results of actual games played by a random population will inevitably prove to be... shall we say, random? While accurate to a large extent, computer calculations can never truly factor in the whimsical nature of freedom of choice. People will pick red/red, like it, and might even do well with it. Sure, we can quibble about optimization for hours, and it has been quite delightful to see so many put this much thought into a basic choice, but the fact of the matter is that while statistically one combination might seen most imposing, it still has a weakness to another "worse" combo for a reason, and chances are that a lot more people will be out there with just the "fluke combo" needed to take you out than will crunch the numbers and agree with your reasoning. ...sorry to interrupt, just thought I'd mention the human factor of inevitable irony for a different perspective.

comment by Perplexed · 2010-10-20T04:55:39.105Z · score: 2 (2 votes) · LW(p) · GW(p)

computer calculations can never truly factor in the whimsical nature of freedom of choice.

I think you will discover that many people here believe that if anyone or anything can "factor in the whimsical nature of freedom of choice", then computer calculations can do it too.

The dispute is mostly about whether or not to assume that the other players are rational. In the absence of good empirical evidence about the other players, I think you have to assume they are rational. My rationale? Well, if you don't assume they are rational, exactly what do you assume?

Perhaps the best way to justify the assumption of rationality, though, is to imagine that you are the acknowledged guru on this particular game. And you are offering advice on your blog (which everybody who plays the game reads) regarding choice of sword and armor. So what advice do you give? You had better advise your fans to choose their swords and armor using the mixed strategy Nash equilibrium. Because if you advise anything else, all your fans are going to be pwned.

"Ok", you say. "If I imagine that, then I see what is good about Nash equilibria. But, why are you asking me to imagine stuff?"

Unfortunately, I don't have a good answer to that question.

comment by jimrandomh · 2010-10-12T11:57:54.299Z · score: -3 (7 votes) · LW(p) · GW(p)

Oddly enough, the armor doesn't specify whose damage is reduced, and by the usual notational convention, wearing red blue or yellow armor would reduce your own damage dealt, not damage taken. This is counterintuitive, but it makes green/green completely dominant.

comment by DSimon · 2010-10-12T13:22:39.770Z · score: 6 (8 votes) · LW(p) · GW(p)

I think you're picking a meaning for the armor values that's clearly not intended; this is a math question, not a trick question.