Quinn Brander
Canada
flag msg tools
Imagine you and I are playing Bruno Faidutti’s Citadels.

I am the assassin and can murder a character of my choice. You, knowing I have the assassin and will try to murder you, must choose between 2 characters: one that will award a symbolic value of ‘1’ if not murdered (say, the thief and I have no money), and one that will award the much stronger symbolic value of ‘3’ (say, the warlord and you have several red districts). I will not know which one you chose when I announce my target, and your symbolic value will be ‘0’ if I murder you. Which character should you choose?

According to game theory, an equilibrium strategy would involve randomly choose one using a probability model of 75% for 3 and 25% for 1, assuming no prior data about a specific opponent. Equilibrium for the assassin would involve randomly choose murder using a probability model of 75% for 3 and 25% for 1, assuming no prior data about a specific opponent.

I believe it is fair to say that if two computers, using these strategies, played a game out like this, the end result would essentially be decided by chance (after compensating for first player advantage).

There are those that have argued the counter-intuitive point that when people make these sorts of choices it is also decided by chance. The argument goes something like this: while both players make their choice for particular reasons, they have no substantive grounds for believing that their opponent will choose one character over the other. This is justified since actual gamers don’t generally decide their moves based on probability rolls or equilibrium strategies. Rather, both players are making decisions based on phantom data (the presumed move of their opponent), and because of this, their own decisions are effectively random.


I am going to attempt to build a case against this argument.

My first piece of evidence is that some players are measurably better and worse at these sorts of challenges. The worse assassin and non assassin players tend to choose each of the options roughly half of the time, while the better assassin and non assassin players will favour choosing the ‘3’ much more often than the ‘1' (closer to the equilibrium model). This is because players are primed to consider all options equally, even when results are wildly unequal, merely by the availability of the choices. Bomber is a simple game that quickly reveals the folly of this sort of thinking.

In Bomber, each turn players alternate being ‘bomber’ or ‘diffuser’ and reveal their moves simultaneously. The bomber can choose to immediately bomb by revealing 10 fingers, or reduce their timer bomb by 1 finger (timer starts at 9 fingers). If the bomber sets off a bomb, they win. The diffuser can either diffuse an immediate bomb by revealing 10 fingers, or stall their opponent’s timer by revealing 0 fingers.

An immediate bomb pretty much always wins the game because of errors on behalf of the diffuser, who should diffuse 8 times out of 9 but usually doesn’t. Experienced players learn to nearly always diffuse, while new players tend to try and stall their opponent’s timers far too often and lose because of it.

Once two players have established a reputation for equilibrium proportions in their choice frequencies, metagaming becomes a crucial and meaningful factor. A player well known for assassinating the stronger character, for instance, may occasionally deviate from the optimal strategy and murder the weaker character more often than would be ideal from a computing standpoint if the other player has become accustomed to selecting the weaker character. Meta-gaming works well against humans when it doesn't against computers precisely because humans are unable to make random choices, and instead use patterns of behaviour to determine their best course of action. Establishing a pattern in order to break it is a meaningful and effective human vs human strategy.

There are only two instances in which I do not doubt that luck plays a deciding role. One is with two new players that continually choose both characters with equal frequency. The other is with two experienced players that fail to deviate from the equilibrium strategy described in game theory in order to gain small advantages. However, the number of games that fall into either of these camps is relatively small.


Do I have something wrong, or do you have something to add? Shoot! If you want to read more- I've started a Game Design Analysis blog here- zamagame.com
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Ron Parker
United States
Fort Wayne
Indiana
flag msg tools
Avatar
mbmbmbmbmb
Quote:
You, knowing I have the assassin and will try to murder you, must choose between 2 characters


Does this situation ever actually occur in the game? I might strongly suspect that you have the assassin, but I don't believe it's ever possible to know that with 100% certainty prior to choosing my own role.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Brander
Canada
flag msg tools
Well, you can be confident within certain contexts. For example, in a two player game if the magician and assassin are both gone and neither player has cards in hand, the other player can feel fairly certain the assassin was chosen and the magician randomly placed facedown. But yes, technically you are correct.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Pieter
Netherlands
Tilburg
flag msg tools
Good intentions are no substitute for a good education.
badge
I take my fun very seriously.
Avatar
mbmbmbmbmb
A game-theoretical optimum simply means that if you play that strategy (in a zero-sum game), you are statistically guaranteed not to do worse than your opponent (and neither will you do better). As soon as you diverge from a game-theoretical optimum, you create the opportunity to do better than your opponent, but you also run the risk to do worse. A strong player simply has a better grasp on his opponent's motives so that he can exploit his opponent's strategy. Simply the fact that some players achieve, on average, better results than others means that some players do not play according to the game-theoretical optimum. That's all.

For your example Citadels, however, the Nash Equilibrium is very hard to calculate as there is imperfect information: you cannot KNOW what your opponent chose, and you do not KNOW your opponent's pay-offs. So the calculation of the optimum incorporates (amongst other things) an estimate of your opponent's strategic preferences. Which you do not have unless you are a mind reader. Trying to say something about Citadels strategies based on game theory is something you better not attempt.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Quinn Brander
Canada
flag msg tools
Well said. Using Citadels as a example is a bit questionable for sure, since the game is far more complex than a simple game theory scenario. Nonetheless, game theory does apply in a limited sense to Citadels as well as in a number of other games, and I was merely using the example to draw people into a larger discussion.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Herb
United States
Georgia
flag msg tools
mbmbmbmbmb
Flyboy Connor wrote:
A game-theoretical optimum simply means that if you play that strategy (in a zero-sum game), you are statistically guaranteed not to do worse than your opponent (and neither will you do better). As soon as you diverge from a game-theoretical optimum, you create the opportunity to do better than your opponent, but you also run the risk to do worse. A strong player simply has a better grasp on his opponent's motives so that he can exploit his opponent's strategy. Simply the fact that some players achieve, on average, better results than others means that some players do not play according to the game-theoretical optimum. That's all.

For your example Citadels, however, the Nash Equilibrium is very hard to calculate as there is imperfect information: you cannot KNOW what your opponent chose, and you do not KNOW your opponent's pay-offs. So the calculation of the optimum incorporates (amongst other things) an estimate of your opponent's strategic preferences. Which you do not have unless you are a mind reader. Trying to say something about Citadels strategies based on game theory is something you better not attempt.


That just isn't true. Assuming optimal play in a two player game (no player makes a mistake) some games are a first-player win, some a second player win, and the rest would be a ties.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
Flyboy Connor wrote:
A game-theoretical optimum simply means that if you play that strategy (in a zero-sum game), you are statistically guaranteed not to do worse than your opponent (and neither will you do better). As soon as you diverge from a game-theoretical optimum, you create the opportunity to do better than your opponent, but you also run the risk to do worse.

Every part of that is untrue.

I suspect you are imagining a symmetrical game where both players are playing optimally, in which case, yes, both players have the same expected (not "statistically guaranteed") result. But that has nothing to do with optimality, it's simply because both players are in identical situations and using identical strategies.

But if you play optimally and your opponent does not, then in a symmetrical game, your expected result is is better than his (not equal), by definition.

If the game is asymmetrical, then the optimal strategy might be different for each side, and neither both sides playing optimally nor both sides playing identically will guarantee that they have equal expected results. For all we know, it could be a lop-sided game where your opponent's worst strategy still gives a better result than your best strategy.

Nash equilibrium is defined as being a point where, if one player stays at the equilibrium, then the other player's best move is also to stay at the equilibrium. That doesn't imply that both players are doing equally well, but it DOES imply that you CANNOT "create the opportunity to do better" by switching strategies (unless your opponent also switches).
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Yaron Davidson
Israel
flag msg tools
mbmbmbmbmb
QuinnBrander wrote:

According to game theory, an equilibrium strategy would involve randomly choose one using a probability model of 75% for 3 and 25% for 1, assuming no prior data about a specific opponent.

Even ignoring the fact that assuming no prior data about a specific opponent is usually unrealistic in this (and similar) game, you're also assuming known "values" for the options, which both players agree on. This is not quite true.

If these values are known (such as expected amount of VP of the move), then these are not the correct value when weighing options. The game state matters a lot too (3 VP early in the game are very different than 3 VP for the win), and other changes to game state are hard to quantify (what's the exact effect on value of the color of a building?).
And if you agree that this value is not exactly known but an estimate considering the current state of the game, then the value will not necessarily be estimated the same by both players.

QuinnBrander wrote:
I believe it is fair to say that if two computers, using these strategies, played a game out like this, the end result would essentially be decided by chance (after compensating for first player advantage).

Depends on how the computer programs are set to work, and how to consider the other one. For example it's also legitimate to set such a computer, against an unknown opponent, to always pick the larger probability. This could give much better than random results if working against a program using the weighted chances you suggest, and terrible results if working against a program intended to defeat this strategy (so always choosing low chance as non-assassin and high-chance as assassin).

You are right that if you take two computer programs that model the weights (values) of each situation exactly the same (which is of course not a necessity or even likely if it's not a copy of the same program), and which are set to always make choices by a random selection based directly on those weights (which is again not a necessity and likely won't be the same, you can give a computer program some levels of risk aversion or risk taking or modified weights based on observed behavior from the other player/program), then indeed the results will be random.

But that isn't different than saying that if players will always toss a coin in these situations then essentially player's choices will always be random. Absolutely true, but meaningless since it's only relevant to a very specific scenario that was defined exactly to get those ransom results.


QuinnBrander wrote:
while both players make their choice for particular reasons, they have no substantive grounds for believing that their opponent will choose one character over the other.

You must have been playing Citadels with very different people than I have been playing with.
Most people do have different levels of risk aversion, different preferences for spite/aggression, and different levels of taking things personally in a game.

QuinnBrander wrote:
This is justified since actual gamers don’t generally decide their moves based on probability rolls or equilibrium strategies.

Many players actually do take probabilities into account when making decisions, and do try to weigh options according to the value they think they have and the chance they think they will happen.

QuinnBrander wrote:
Rather, both players are making decisions based on phantom data (the presumed move of their opponent), and because of this, their own decisions effectively random.

Presumed move of the opponent is not "phantom data".
But sure, if what you're trying to say is "when we assume that the moves of the opponent are not knowable or estimable, then a decision based on the estimated move of the opponent is effectively ransom" then it's true, I agree. It's just that the assumption is wrong, so the conclusion isn't valid.


QuinnBrander wrote:
The worse assassin and non assassin players tend to choose each of the options roughly half of the time,

Why? Won't someone who always pick one option be a much worse assassin once this is noticed by opponents? Unless of course playing against a similar non-assassin always making the alternate choice, in which case they'll be a super great assassin?

QuinnBrander wrote:
while the better assassin and non assassin players will favour choosing the ‘3’ much more often than the ‘1' (closer to the equilibrium model).

They'll be better against players using the exact same model, they won't be better in real games, where different players give different values to options that these "better" players ignore.

QuinnBrander wrote:
This is because players are primed to consider all options equally, even when results are wildly unequal, merely by the availability of the choices.

No they're not. Sure, if given a completely worthless option some players will assign to it a more than 0 worth simply because it's there, but it's really unjustified to go as far as "equally".

QuinnBrander wrote:
A player well known for assassinating the stronger character, for instance, may occasionally deviate from the optimal strategy and murder the weaker character more often than would be ideal from a computing standpoint if the other player has become accustomed to selecting the weaker character.

So you agree knowing the opponent does have an effect on choices, great.
Then why do you still refer to the "ignore opponents behavior, and assume they give the same value as you do to everything" strategy as "optimal"? It is very sub-optimal except in a very limited set of circumstances.

QuinnBrander wrote:
Meta-gaming works well against humans when it doesn't against computers precisely because humans are unable to make random choices, and instead use patterns of behaviour to determine their best course of action.

Computer programs make choices as they were programmed to do. When playing against a computer program, if the program is unsophisticated enough to always give the same weight to the same options and to never modify its behavior based on opponent's actions, then when playing against it you have full knowledge of what it will do while it doesn't have it on you, and presto, meta-gaming (for example if you know there's always 75% chance it will use assassin on what it considers the 3 option then you always pick the 1 option and come out way ahead, since this is an easy-mode program that won't learn and will always succeed in assassinating you only 25% of the time. This exact scenario won't happen 4 times in the game, so the "expected" value isn't as important as the better chance you get on this one game).

Everything uses patterns of behavior. Especially computer programs which are very explicit set of programmed patterns. "estimate value of options and then use weighted ransom selection directly based on relative values" is a pattern.

QuinnBrander wrote:
One is with two new players that continually choose both characters with equal frequency.

My last game of Citadels was a 5-players game with 2 new players and 2 that only played a couple of times. I don't think anyone there chose options in a way that was your "with equal frequency". Though of course it's not always easy to tell, since the supposed weights aren't the same in real life, and there are more than 2 options almost always, and the exact same game situation (so exact same estimated value) doesn't repeat often.

QuinnBrander wrote:
The other is with two experienced players that fail to deviate from the equilibrium strategy described in game theory in order to gain small advantages.

Again, this is not a realistic strategy when playing, because even when players assign their own exact values to options these values are different from the ones that opponents have, and opponents do have patterns of behavior, and the players themselves have patterns of behavior.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
herace wrote:
Assuming optimal play in a two player game (no player makes a mistake) some games are a first-player win, some a second player win, and the rest would be a ties.

Most of the other posters here seem to be in the mindset of game theory, which typically assumes a game where players make blind simultaneous decisions (e.g. rock-paper-scissors) and where many different outcomes of different desirability may be possible (e.g. they care about whether you win with a score of 50 or a score of 60, not just whether you won or lost).

You seem to be assuming a sequential game of perfect information with no chance and binary outcomes. (The field of mathematics that studies games of this sort is combinatorial game theory.)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Pieter
Netherlands
Tilburg
flag msg tools
Good intentions are no substitute for a good education.
badge
I take my fun very seriously.
Avatar
mbmbmbmbmb
Antistone wrote:
Flyboy Connor wrote:
A game-theoretical optimum simply means that if you play that strategy (in a zero-sum game), you are statistically guaranteed not to do worse than your opponent (and neither will you do better). As soon as you diverge from a game-theoretical optimum, you create the opportunity to do better than your opponent, but you also run the risk to do worse.

Every part of that is untrue.

I suspect you are imagining a symmetrical game where both players are playing optimally, in which case, yes, both players have the same expected (not "statistically guaranteed") result. But that has nothing to do with optimality, it's simply because both players are in identical situations and using identical strategies.

But if you play optimally and your opponent does not, then in a symmetrical game, your expected result is is better than his (not equal), by definition.

If the game is asymmetrical, then the optimal strategy might be different for each side, and neither both sides playing optimally nor both sides playing identically will guarantee that they have equal expected results. For all we know, it could be a lop-sided game where your opponent's worst strategy still gives a better result than your best strategy.

Nash equilibrium is defined as being a point where, if one player stays at the equilibrium, then the other player's best move is also to stay at the equilibrium. That doesn't imply that both players are doing equally well, but it DOES imply that you CANNOT "create the opportunity to do better" by switching strategies (unless your opponent also switches).

Yeah, you are right. I had been working for 14 hours straight and wasn't clear in my thoughts. I wanted to express that the OP was not using game theory in the correct way, but I wasn't either.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.