Resistance is a popular hidden role game with 5-10 players. Each player is either part of the resistance, or a spy. The resistance wins if they can successfully complete 3 missions, and the spies win if they can sabotage 3 missions. The game consists of 5 rounds where each round some number of players are selected to go on a mission. The players then vote on whether or not to approve the mission. If the mission is approved, the players on the mission secretly vote on whether or not to sabotage the mission. If the mission is sabotaged, the mission fails and the spies get a point. Otherwise, the mission succeeds and the resistance gets a point. The game ends when either the resistance or the spies get 3 points. The full rules of the games can be found here.
The game also has expansions that add new roles and mechanics, but currently this solver only supports the base game (even plotcards are out of the scope of this solver).
Currently the solver is only available as the whole code in this repository. The code should be simple enough to be understood without further documentation (but there are descriptions of the functions in the code). The main point of this readme is to explain how the solver works.
We are going to make some assumptions about the game that some people probably wouldn't agree with. In my opinion these assumptions follow if all players play perfectly, but I'm going to list them here so that you can decide for yourself if you agree with them and they are also necessary to understand the results. I make the following assumptions:
1. The resistance agrees on their decisions: When playing the game, the decision of who goes to the mission is voted on after the leader selects a candidate mission. I'm however skipping this parts and simulating the game such that the resistance team works as unity. There might be situations where the best mission from the "objective" perspective is not actually the best mission that could be picked if there was a leader and a vote but for now this is a minor problem.
2. The spies coordinate perfectly: During the game multiple spies can be sent to the same mission. In these situations the spies have to somehow decide which of them plays the fail card. If they fail to communicate about this, they might actually both play fail cards (or both could play successes) even though the goal was to only play one fail card (after the mission, all the played cards are seen and if there are two fail cards, the resistance will know that there were two spies on the mission, giving them more information). I assume that the "spy team" makes the decision as of how many fail cards they want to play (with some player counts, some rounds need more than one fail card to fail). In my opinion, this is just what happens when the spies play optimally but this requires more thinking.
3. The resistance "knows" the strategy which spies use: This is probably the most radical assumption I make and my plan is to relax this assumption in the future. After the assumptions 1 and 2, the spies have only one kind of decion to make in the game: Do they sabotage a mission or not? This decision is not done deterministically as if the resistance knew that the spies always sabotaged in a specific situation, they could use a success in that round to deduce that no one in that round was a spy, which could be a big advantage. In this situation it could actually be good for the spies to not play fail once in a while to basically be a "certain resistance member". This is why in each round where there are enough spies to sabotage the mission, they sabotage the mission with some probability (that is dependent on the situation). These probabilities are the strategy of the spies.
An example strategy could be to always sabotage when there are the exact number of spies required to sabotage a mission but not sabotage if there were more as this would throw suspision to more spies than required.
To go back to the assumption, it means that these probabilities are known to the resistance side. This might seem like a bad assumption (and it kind of is) but it makes the calculations so much easier so I've decided to first solve the problem with this assumption and then generalize it further. The reason why this isn't such a stretch is that by monitoring millions of games from the optimally playing spies, we could have a statistic about how often the spies sabotaged in each situation and the resistance players would in this situation "know" what the probabilities were. However this doesn't work as if the spies knew that the resistance knew their probabilities, they would play with different probabilities...
The general plan is to first find a way to find the best missions for the resistance if they know how the spies play and then optimize the strategy of spies such that it minimizes the winning chance of the resistance. The first part is done using the recursive function chance_to_win which calculates the chance to win for the resistance in a given situation. The chance is calculated by considering each mission that could be picked and calculating the chance to win if that mission resulted in a success and the chance to win if that mission resulted in a fail (this is done by calling the function chance_to_win with the potential states of the game). The chance to win is then calculated by multiplying the chances to win with the chances of mission being successful / failing and summing these values. The chances of mission being successful is calculated using the known chances of spies sabotaging the mission.
The second part is to find the optimal strategy for the spies. This is not yet fully carried out as after implementing the chance_to_win I realized that my assumption 3 is not that good and I realized how to improve it. I've implemented this in function chance_to_win2 (I'm thinking of better names for this) (The function doesn't yet work. There is some bug). The difference is that chance_to_win2 calculates the chance of resistance winning the game if they think spies playing according to a strategy S while the spies actually play according to a strategy S'. This is done basically by keeping track of two probability distributions of the configurations of spies. The first distribution is
After checking that it works, the idea is to find a strategy S such that if resistance assumes that the spies play according to that and the spies choose a strategy S' to minimize the chance of resistance winning the game, the chances are as high as possible. In other words, we are just min-maxing.