Viva La Resistance! A Resistance Game Solver

Update (Feb142016): see bottom for an improved strategy.

The Game

At a December workshop, I played The Resistance, a game in which there are two teams, the resistance and the spies. The spies know everyone’s identity; each resistance player knows only one’s own. Overall, the goal of the spies is to remain undetected; the goal of the resistance is to discover who the spies are.

Play proceeds in rounds in which a player nominates a subgroup to go on a “mission”. The nomination is then voted on. If the vote succeeds, every member of a mission plays either a “success” or “failure” card for the mission. One or two failure cards (depending on the mission size) causes the mission to fail. The cards played in a mission are public, but it is secret who played which card. (If the vote fails, the next player nominates a subgroup.)

The spies’ goal is to fail missions without being detected, and the resistance goal is to have missions succeed. So the spies generally wish to play failure cards while in a mission. Furthermore, spies always want some spy in the mission to spoil it. The resistance wants no spies to go on missions. The problem for the resistance is that when a mission fails, they know one or more of the subgroup is a spy, they just don’t know which one.

The spies win the game if they can cause three missions to fail before the resistance can cause three missions to succeed.

The game is simple but engaging, and similar in spirit to the game Mafia (Werewolf).y

The Problem

I played the game with computer scientists from the top universities and research labs. We debated strategy and were generally pretty bad at the game, despite having a lot of fun. In particular, the spies seemed to win a lot.

The problem is: what is the optimal approach to game play?

The Approach

The problem is a great fit for Bayesian Analysis. In each round, we learn partial information about the players from the group outcome. Only spies play failure cards. We can use that information to update our believe in the probability that a player is a spy.

Suppose there are four players, [ a, b, c, d] and two spies. Initially each player has the same probability of being a spy, 2/4 = 0.5. Now suppose that [ a, b, c ] go on a mission, and return the set of cards \{Success, Fail, Fail\}. How do we update the spy probabilities of the group?

Bayes Theorem states that

P(A|B) = \dfrac{P(A)P(B|A)}{P(B)}

In our case, “A” is the event that a particular player is a spy, and “B” is the event that we we observed a particular set of mission cards. We wish to compute P(A|B), the updated probability that a player is a spy given the cards played in the mission.

So for each mission, we apply Bayes’ Theorem to each player, including the players not in the mission—if the spy probabilities increase (or decrease) for the mission players, then they decrease (or increase) for the non-mission players.

From the cards \{Success, Fail, Fail\}, we know that two of [ a, b, c ] are spies (and so d is definitely not a spy, since there are two spies, total). Let’s compute the updated spy probability for player a.

P(A) = 0.5, the original spy probability for player a (or any other player). To calculate P(B), we first determine every possible assignment of players in the mission to spies and non-spies (there are \binom{2}{3} such assignments). In the mission, there are three possibilities:

  1. spies = [a, b]
  2. spies = [a, c]
  3. spies = [b, c]

For each combination, we multiply the probabilities for the assignments. So in case (1), we have

0.5(0.5)(1-0.5) = 1/8

for assigning players a and b to being spies and c to being a non-spy. Then we sum the probabilities for all three combinations. In our example, we get

\frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}

So P(B) = 0.375.

To compute P(B|A), we assume that player a is a spy, and now recompute the probability that [b, c] contains the remaining one spy. Using the same approach as for computing P(B), we get P(B|A) = 0.5. Now we can apply Bayes’ Theorem:

\dfrac{0.5(0.5)}{0.375} = 2/3

So player’s a probability of being a spy shot up to 0.66, and so did player b’s and c’s.

Player d‘s spy probability drops to 0. The updated spy probabilities for any player not in the mission can be computed just as we did for the mission players, except we take the total number of spies and subject the number of failure cards observed. In this case, however, since we know all the spies were in the group, d‘s spy probability must be 0. (Another way of thinking about it is that there is an invariant that the sum of the player’s spy probabilities must always be the total number of spies in the group.)

The Strategies

How should the game be played by the resistance and spies, respectively, to increase the odds of winning?

For the resistance, picking the players the least likely to be spies is optimal. Let’s call this the pick-lowest strategy.

One possible optimization is to always pick yourself in a mission. The rational is that you know if you are part of the resistance, and you pick yourself for a mission, then you have at least one guaranteed non-spy. So even if your probability of being a spy as known to the group is higher than others, you have perfect knowledge of yourself. Let’s call this the pick-myself strategy,

For the spies, there are a few options. By default, the spies could always play a failure card (fail-always). But a spy might also play a success card to avoid detection; doing so is especially advantageous in the early rounds; one strategy is to never fail the first round (succeed-first). If the spies can collude to ensure only one plays a failure card during a mission, that provides the least amount of information to the resistance (fail-one).

There are other strategies and other combinations of strategies, but this is a good representative sample.

Which are the best strategies?

Findings

To discover the best strategies, we use Monte-Carlo simulations on the strategies over each number of players (with different number of players, there are different number of spies and missions). I found a few interesting results:

  • The best chance of wining for the resistance, and the closest odds between the resistance and spies, is with six players. At six players, the resistance has a 30-40% chance of winning under different strategies. The worst configuration is eight players, with not more than a 14% chance of winning for the resistance. During actual game play, it seemed that the odds favored the spies.
  • The best strategy for the resistance is the pick-lowest strategy. The strategy may be counter-intuitive, but consider this: the pick-myself strategy provides the spies an opportunity to always include themselves in a mission when picking a mission. The pick-myself strategy is an instance of a local maxima (i.e., local knowledge of knowing yourself to be part of the resistance) that is non-optimal.
  • Moreover, voting becomes a no-op. The game includes a voting round in which players vote on the proposed players for a mission. But If the resistance agrees on an optimal strategy, any deviation from the strategy by a player is because the player is a spy. If the person does deviation, the resistance votes against it (and resistance outnumber spies, so will win the vote), and we now have complete assurance the proposer is a spy. The spies have no choice but to follow the optimal strategy of the resistance.
  • Of the spy strategies listed above, the best is the fail-one strategy, which is intuitive. The succeed-first strategy is another example of a local maxima that is non-optimal; while it protects that particular spy from detection, it is more valuable for the spies in general to fail the mission.

The related Mafia game has some analytical results, giving bounds on (their version of) the resistance to spies. I have not done that, nor have I done Monte-Carlo analysis to determine what proportion of resistance and spies and mission sizes gives a more even chance of winning. In Mafia, it is noted that in actual game play, the resistance wins more often than simulations/analytical analysis would suggest, with different attributions (e.g., people are bad at lying over iterative rounds).

Play Along at Home

I have implemented the Bayesian solver in a webserver hosted on Amazon Web Services. You can use the solver when playing with others.

http://ec2-54-173-249-238.compute-1.amazonaws.com/

An easier-to-remember link is http://tiny.cc/theresistance1.

If you want to run Monte Carlo simulations, you will have to download the code and run it locally, however.

Implementation

https://github.com/leepike/theresistance

Update (Feb142016)

It has been pointed out by Eike Schulte in the comments and Iavor Diatchki that by including some additional information, the strategy might be improved. This is indeed the case. The intuition is that if a group has previously included a spy, that group should not be selected again, even if it is the lowest probability group. For example, with five players, consider the following rounds:

  • Round 0: players [0,1] are selected and there is one fail card.
  • Round 1: players [2,3,4] are selected and there is one fail card.
  • Round 2: players [2,3] are selected and there are no fail cards.

At this point, players [0,1] have a 0.5 probability of being a spy and players [2,3,4] have a 1/3 probability. So in round 3, we do not want to select players [2,3,4] even if they have the lowest probabilities. So we select a group with the lowest spy probability that has not already included a spy. The server has been updated to include this strategy. The strategy does better; for example, at 6 players, we have just over a 50% chance of winning!

Advertisements

2 Responses to “Viva La Resistance! A Resistance Game Solver”

  1. Eike Schulte Says:

    I don’t think this is true: “But If the resistance agrees on an optimal strategy, any deviation from the strategy by a player is because the player is a spy.” Consider this: In a five-player game, it is my turn to propose the final three-player team. I’m a member of the resistance but unfortunately, three other players have lower spy probabilities than me. Even if we agreed (however that would work) on pick-lowest before, it is not optimal for me to follow that strategy because it will result in a certain loss. So resistance members can have reasons to deviate from the strategy (and depending on the outcomes from previouss missions even earlier than the last round).

    Also, your how do you break ties? You cannot agree on a rule before assigning roles (it’s against the spirit of the game, also why would you agree to that when you have a ggood chance of becoming a spy?) but once the players know their roles, their input in that discussion becomes tainted. If you leave it up to the leader to break ties, I’m almost certain that the spies could use that to game the system.

    Really, the resistance has no way of agreeing on a strategy because the players do not know with whom they have to agree. The interesting thing about The Resistance is that you cannot treat it as a two-player game because the resistance has no reliable way of playing as a team. A good solution would probably be based on some mathematical break-through explaining how to think abiut multiplayer games (which we don’t really know how to do right now, I think).

    • Lee Pike Says:

      I added an update to the post that considers some of the additional information that might be used. Indeed, the strategy is improved; thanks!

      I’m not sure what are ties. Do you mean there are multiple groups that could be selected for a mission? If so, an arbitrary decision would be to select those players with the lowest indexes (where indexes are assigned based on the order of the play).

      I disagree that you can’t treat the resistance as a two-player game. They don’t know who they have to agree with, just that if they each follow some particular strategy, then overall their probability of winning increases.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: