The Resistance

TheResistance

Some time ago I was introduced to this board game called The Resistance.

I very rarely play board games, so I am anything but an expert.
My impression however of non-mainstream fantasy-themed board games is that they are usually very time consuming and quite difficult to grasp (and played only by people in long leather coats).

On the contrary the designer behind this game might be on to something.
The Resistance has many of the common features of a great mainstream board game.
The rules are easy to understand, games are short, very social, there is no player elimination, involves deduction, deceit and it can probably be converted into a drinking game…. you name it.

So how does the game work?

Rules:

The game can be played by any number of people between 5 and 10 (at least this is the recommendation).
There are two opposing sides: The Resistance(the good guys), and the Spies(the bad guys).
The sides are determined by cards that are shuffled and dealt among the players.
The number of members on each side is determined according to a table you can find here.
The game is set up so that spies know who each other are, but the resistance members don’t.
It is in the interest of the resistance to try and identify who is a spy and who is not (of course there can be disagreement which is the basis of the whole game).
The game consists of up to 5 rounds, called missions.
Before each mission the leader(a rotating role) chooses a team, after which there is a round of voting to determine whether the team should be accepted for the mission or not.
The majority vote wins (in case of a tie the team is rejected).
The size of the team in each mission is decided by a table you can find here.
If the team is rejected then the next leader chooses a new team and another round of voting takes place.
There can be no more than 5 rejections over the course of the game, otherwise the spies win.
If the team is accepted then each team member can decide whether to succeed or fail the mission.
These decisions are recorded on cards that are shuffled and then shown (so that it is impossible to directly link a decision back to any player – deducing who is a spy is in essence what the game is about).
If any of the cards have recorded a Fail, then the mission as a whole has failed (i.e Fail has veto).
The Resistance need 3 successful missions to win the game, otherwise the spies win (best of 5 missions).
Of course members of the Resistance have no reason to fail any mission, so only spies can fail missions.

If you are still unclear about the rules you can watch a video here.
The video also shows what the game pieces physically look like if you are interested.

 
Besides the rules I wanted to mention some tactical remarks so you can get a feel for how the game is played:

  • Talking a lot is part of the game. If you are a spy you need to convince the resistance that you are not a spy and do everything you can to cause confusion in the game. This could take the form of false accusations, coming up with deceiving arguments and other sorts of manipulation to pretend you are an ally of the opposite camp.
  •  

  • Being in the resistance can be quite difficult. It is often easier for the individual members of the resistance to gather information for themselves as to who is a spy, since they can eliminate themselves from the equation. However any such information is not easily communicated to the rest of the resistance members, why should they trust you?
  •  

  • As part of being in the resistance you may want to carefully observe why some players tend to reject teams with certain members (or the absence of certain members). This is a source of information which I rarely used myself while playing as resistance. Of course the spies want to ensure that they are part of as many missions as possible so that they are in control. Therefore certain teams should look less attractive to them.
  •  

  • Being a spy you do not necessarily want to fail every mission you are a part of. Particularly if there are more than one spy in a mission it can be devastating to reveal this fact by for example double failing. If you fail a mission with a small team you tend to give away more information as a spy since the resistance can narrow down the search to fewer people. As a spy you can also choose not to fail a mission to gain trust in further missions and then sit back and watch the confusion as you fail subsequent missions for unapparent reasons. On the flip side by not failing you may give away some game equity in case the mission succeeds. Therefore any such move needs to be weighed carefully as a tradeoff.
  •  

    While playing it became obvious that the game seems heavily biased in favour of the spies (or we may have been playing it wrong). Out of the 5 or 6 times that the game was played I believe the resistance won only once, and that was because of a glaring mistake on part of the spies. I remember afterwards thinking whether there exists a better strategy the resistance could employ to increase their chances of winning?
    Is there even a strategy the spies can implement to win with certainty?

    I don’t know if any game theorist have ever taken a serious look at this game before, but I’ve at least managed to find a strategy that gives the resistance a guaranteed chance of winning with probability \frac{4}{15} \approx 27\% in a game of 6 people and a winning rate of \frac{3}{10} = 30\% in a game of 5 people.
    I do not recommend playing this strategy unless you want to kill all the fun in the game.
    I merely want to establish the existence of a strategy that attempts to answer the questions posed above in a neutral setting where no information other than what is on the board is used. There is also no claim of optimality for this strategy (in fact there is a chance you may be better off using social tells to aid you).

    A Strategy For The Resistance:

    The main idea behind the strategy is that the resistance can pre-adopt a decision tree deciding what teams should be sent on each mission depending on the outcome of previous missions.

    By fixing a decision tree no team can ever get rejected since the resistance are in majority.
    Moreover if a spy down-votes a team he has immediately revealed himself to be a spy since members of the resistance have no reason to down-vote.
    Therefore all votes must be positive.
    This makes team voting redundant.

    Since the resistance members are initially unaware of who is on their side the decision tree must be made public information i.e the spies know exactly how the teams are selected for each mission.

    We may therefore assume the spies choose the path that maximizes their gain in the decision tree.

    So we have translated the game into a situation where the resistance come up with the best possible decision tree and spies pick the worst possible path for the resistance.

    Of course the question is how often the spies can find a path that leads to at least 3 failed missions considering all possible spy locations around the table?

    The following decision tree can be used by the resistance to achieve certain win in 4 out of \left( \begin{array}{c} 6 \\ 2 \end{array} \right) = 15 possible spy configurations in a 6 player game.
    The tree is by no means unique.
    Here a filled black circle represents a player being selected to go on a mission.
    According to the game table the number of people required on each of the 5 missions is 2,3,4,3,4 for 6 players.
    It should also be noted that a “Fail” branch may only be taken if there is a spy in the team.
    Hence the spies may not always be able to reach 3 failed missions.

    DecisionTree2

     

    Strategy Analysis:

    Let us analyze the game in which there are 6 players.
    The number of distinct decision trees for this problem is given by:

    \left( \begin{array}{c} 6 \\ 2 \end{array} \right)^{1}\left( \begin{array}{c} 6 \\ 3 \end{array} \right)^{2}\left( \begin{array}{c} 6 \\ 4 \end{array} \right)^{4}\left( \begin{array}{c} 6 \\ 3 \end{array} \right)^{8}\left( \begin{array}{c} 6 \\ 4 \end{array} \right)^{16} \approx 5.10^{37}

    Like in so many combinatorial games this is impossible to brute force.
    That is, finding an optimal tree by evaluating the win/loss distribution across every possible decision tree.

    In lack of better ideas, lets try to grow a tree on best effort and stop when things become impossible.
    We want to accommodate for as many spy locations as possible, so let’s start by considering two spies at 1,2 and make it very hard for them by not giving them any choice opportunities.
    We can do this by excluding them from the team three missions in a row.
    This way the resistance win all three missions, and hence the game.

    TreeGrow1

    Now consider spies at location 1,3. We want to block all possible bad paths for the resistance by choosing new nodes appropriately. Given the current tree, the two first missions will automatically succeed since they do not include any spy. Once we reach (3) there will be a spy in the team but he cannot afford to succeed the mission without losing the game so he is forced to fail the mission. We can now add a node appropriately on the Fail-branch of (3) to make the next mission go in favour of the resistance – and hence the game.

    TreeGrow2

    Next lets consider spies at location 1,4.
    Now things are getting slightly more constrained for us, but it is still possible to make the spies lose.
    We have two paths to consider given the current tree.
    If spies choose to fail the mission in (2) then we can make sure the resistance win the next two missions by choosing nodes appropriately.
    If spies choose to succeed (2) then they cannot afford to succeed (3) without losing the game.
    If they fail (3) then they will lose (4) and hence the game, so there is nothing more to do for this case.

    TreeGrow3

    We can still do more.
    Consider spies in locations 2,3
    The first two missions will automatically succeed given current tree.
    In (3) we have our first spy in the team, but he cannot afford to lose the mission without losing the game.
    Moving on to (4) we have another spy in the team, and likewise he cannot afford to lose the mission so he needs to fail it. We can now add in another node to the fail branch of (4) to win the next mission for the resistance.

    TreeGrow4

    It is now impossible to continue.
    Any other spy configuration can follow the path (1) \rightarrow (2) \rightarrow (3) \rightarrow (4) \rightarrow (7) to fail 3 missions.
    Thus remaining nodes are redundant and can be chosen arbitrarily.

    This does not constitute a proof of optimality (within the strategy) but I suppose it might be possible to formalize an argument along these lines.
    That 4 out of 15 could be optimal for any decision tree is also supported by the heuristic search algorithm I implemented to evolve a best possible solution tree (see Genetic Algorithms for more details).
    The tree generated by the algorithm can be seen in the full decision tree depicted above.
    Can you spot which spy configurations are the winning ones for the resistance?

     
    The argument for 5 players work in a similar fashion, I will leave this as an exercise.

    Out of accident I noticed that if we change the rules so that the spies must win 4 out of 5 missions to win the game then the strategy described in this post yields a completely fair game in the case of 5 players, and a near fair game (46.66667 \% for resistance) in a 6 player game.

    The game we have considered in this post is the absolute vanilla version of The Resistance.
    There are many other interesting variations of this game.
    Particularly the version with a “Merlin”, who is part of the resistance and know who the spies are.
    Spies are unaware of who the Merlin is and are given a chance at the end of the game to guess who it is.
    If they guess correctly then the spies win the game, regardless of whether the resistance have won more missions.
    So the Merlin character is under very high pressure during the game because on one hand he needs to communicate who the spies are to the other resistance members, but on the other hand this communication cannot be too obvious because then he gives the game away.
    It might be interesting to analyze how much this changes the winning probabilities for either team.
    Regardless of what happened during the game the spies have a 25 \% chance at taking home the game by pure luck (in a 6 player game) which intuitively seems unfair.

    Advertisements
    This entry was posted in Game Theory, Uncategorized and tagged , , , , , . Bookmark the permalink.

    3 Responses to The Resistance

    1. adam says:

      with a slight modification, you should be able to achieve 1/3 or approximately 33%.

      First pick two people, let’s assume they’re good, that’s a 40% chance both are good… and so they pass

      then pick a third person. Either they’re good, and the good guys win, because they choose the same group in the 4th mission and accumulated win 3… this happens 50% of the time.
      If they pick a bad person and he fails, then you eliminate that person, that happens 50% of the time.

      Then for mission 3, choose the original two and choose two new people. If they pass, it’s game over as well, this happens 1/3 of the time,

      2/3 of the time you get a single fail, then by default mission 4 has to succeed since you’ve identified two spies, and mission 5 is a 50/50 win or lose by choosing one of the people from mission 3.

      Therefore your win percentage is 2/5* (1/2 + 1/2*(1/3 + 2/3*(1/2))) = 1/3

      This of course lends itself to spies always choosing false, but even working through the logic, if a spy did lie, it doesn’t change too much unless it’s the first two, then you just lose without interpretation.

      • Amini says:

        Hi Adam,

        I like your idea to incorporate randomness into the strategy i.e instead of choosing the teams deterministically according to a decision tree, one chooses the teams randomly under some agreed and publicly revealed restrictions that are respected by the resistance (and hence by everybody). This way the spies have less opportunity to “plan ahead” and must instead choose between probablity trees (see below). The probability proposed in your comment comes from a probability tree where the spies always choose to fail every mission they are a part of. I believe this may unfortunately not lead to the best possible strategy for the spies.

        For instance if we assume that a success in the first round implies both team members are part of the resistance we will be right with probability 2/5. Assume now that the spies adopt a strategy where they will succeed the second mission.
        Thus the second mission will succeed regardless of which members are chosen and therefore no information can be extracted from this mission. At this point we can assume that the spies will fail every future mission they are part of since they cannot afford to be deceptive again without losing the game. In the third mission 4 people are to be chosen, 2 of which we know are the resistence and so there is only 1 pair out of 6 which includes both remaining resistence members. Thus the mission will fail with probability 5/6. In the fourth mission 3 people are to be chosen and we have 1/2 chance of winning or losing the mission for the resistance depending on which third member is chosen out of the remaining four (2 of which are resistance and 2 of which are spies). If the mission fails then we know for sure that player we picked was a spy (under our assumption from the first mission). For the final mission we have to choose 4 people. Out of the 6 players we know two that are resistance and one that is a spy. Out of the remaining 3 there are 2 resistance and 1 spy. Thus mission succeeds with probability 1/3 and fails with probability 2/3.

        This leads to the probability 2/5*(1/6 + 5/6*(1/2 + 1/2*(1/3))) = 13/45 ~ 0.288888 for the resistance.

        This is still better than the proposed strategy, but one would have to evaluate all the probability trees that arises from the choices made by the spies. The moral of the story being that the probability tree is parametrized by strategies chosen by both the resistance and the spies.

    2. I like the strategies mentioned here, and had been considering putting some “random factor” into my playthroughs of the king arthur version. One note i will mention, is that not only is merlin a game changer in the Avalon version, due to information gain/alternate win condition due to him, but there is also an optional character “oberon” who while being on the bad guys side, is UNKNOWN to every other player. having a true “wild card” who is unknown to both sides is a tad disruptive to these kinds of calculations. And the lady of the lake chit, who can give information, to players, or if entirely controlled by the allies of mordred, can be dangerous. The strategies mentioned here can help in resistance, but it’s a much, much harder analysis, if these additional elements are used, as they are additional means of verifying/concealing information, in addition to the votes. I would love to see some thought put into how the affect the game.

    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