Find the Spy
January 7th, 2014 at 11:46:14 AM
permalink
There's a game called 'Resistance' that I quite enjoy. It's a social deduction game, not unlike Mafia, where some players are spies/traitors to the 'cause' and the good guys are trying to complete missions while the spies are trying to stop them.
Distilling it down for the question there's 5 missions. The good guys win if they pass 3 of them. The spies win if they fail 3 of them. In this example, there are 6 players, 2 are spies, 4 are good guys. On each mission, the team puts in a 'pass' or 'fail' card secretly. Assume spies will always play the fail card.
If the mission has 1 or more fails played, the mission fails (there's a special rule for some missions, but lets make it simple).
So we have 6 players, a,b,c,d,e,f. Two of that group are Spies.
The missions are sized;
Mission 1 : 2 members
Mission 2-4 : 3 members
Mission 5 : 4 members
(so mission 5 only passes if only good guys go).
Let mission 1 be: {a,b} and the result of 1 Fail played be written as:
{a,b} = 1
What group should you send on Mission 2 to get the highest chance of a pass?
Given that mission Failing, what group should go on Mission 3?
{a,b} = 2 is uninteresting, as the good guys now can send passing teams.
{a,b} = 0 is useful, as you can use Missions 2 and 3 to find the spies by sending {a,c,d} then {b,e,f}.
(in the real game, the team is voted on, spies don't always have to fail a mission. The game scales from 6-10 players, and has variants were additional info can be added for some players. Note that the spies know who each other is, but the good guys don't).
The bonus question that prompted this, given the simplified game, is it solvable? Depending on who sets up the teams?
Distilling it down for the question there's 5 missions. The good guys win if they pass 3 of them. The spies win if they fail 3 of them. In this example, there are 6 players, 2 are spies, 4 are good guys. On each mission, the team puts in a 'pass' or 'fail' card secretly. Assume spies will always play the fail card.
If the mission has 1 or more fails played, the mission fails (there's a special rule for some missions, but lets make it simple).
So we have 6 players, a,b,c,d,e,f. Two of that group are Spies.
The missions are sized;
Mission 1 : 2 members
Mission 2-4 : 3 members
Mission 5 : 4 members
(so mission 5 only passes if only good guys go).
Let mission 1 be: {a,b} and the result of 1 Fail played be written as:
{a,b} = 1
What group should you send on Mission 2 to get the highest chance of a pass?
Given that mission Failing, what group should go on Mission 3?
{a,b} = 2 is uninteresting, as the good guys now can send passing teams.
{a,b} = 0 is useful, as you can use Missions 2 and 3 to find the spies by sending {a,c,d} then {b,e,f}.
(in the real game, the team is voted on, spies don't always have to fail a mission. The game scales from 6-10 players, and has variants were additional info can be added for some players. Note that the spies know who each other is, but the good guys don't).
The bonus question that prompted this, given the simplified game, is it solvable? Depending on who sets up the teams?
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
January 7th, 2014 at 12:12:42 PM
permalink
I watched the game played on 'table top' on youtube (love that show. got me interested in several games).
they played a 5 player version that I thought relied more on luck than skill. each player acted as team captain for each round. obviously, each time the traitor was captain, the mission would fail. so, getting the other missions to pass relied on no traitor in the team, and with only 5 rounds, there is not enough time to deduce who the traitor is.
so, imo, the game is not "beatable". the game is short and with small groups, you have too high a chance to have the mole in the group. and with large groups, the chance is low enough that you didn't have to do anything... the missions would never fail. maybe the question should be, what is the optimal amount of people to play per traitor to make it challenging yet winnable.
they played a 5 player version that I thought relied more on luck than skill. each player acted as team captain for each round. obviously, each time the traitor was captain, the mission would fail. so, getting the other missions to pass relied on no traitor in the team, and with only 5 rounds, there is not enough time to deduce who the traitor is.
so, imo, the game is not "beatable". the game is short and with small groups, you have too high a chance to have the mole in the group. and with large groups, the chance is low enough that you didn't have to do anything... the missions would never fail. maybe the question should be, what is the optimal amount of people to play per traitor to make it challenging yet winnable.
January 7th, 2014 at 12:17:06 PM
permalink
I am going to interpret solvable as guaranteeing a resistance win. In that case, I submit the following for your consideration:
No! The proof relies on the following claim:
If after failing two missions, the spies cannot be identified unequivocally, a win cannot be guaranteed.
Why is this? If you can't identify the spies, you will need at least one more failed mission to identify them, which will lose the game. You need to do this because you must send all 4 resistance members without guessing to win the 5th mission. If you can't identify the spies after 2 failures, you may still win, but it will involve at least some degree of luck, hence not solvable.
Now consider the first mission {a,b} = 1. You have three choices on how to proceed. Send two from the first mission: {a,b,c}, one from the first mission: {a,c,d}, or none from the first mission: {c,d,e}. ALL three strategies are plagued by the same problem: if the 2nd mission also has exactly one fail, you cannot identify the 2 spies. Also, you've failed 2 missions. The win cannot be guaranteed.
Basic game unsolvable.
If after failing two missions, the spies cannot be identified unequivocally, a win cannot be guaranteed.
Why is this? If you can't identify the spies, you will need at least one more failed mission to identify them, which will lose the game. You need to do this because you must send all 4 resistance members without guessing to win the 5th mission. If you can't identify the spies after 2 failures, you may still win, but it will involve at least some degree of luck, hence not solvable.
Now consider the first mission {a,b} = 1. You have three choices on how to proceed. Send two from the first mission: {a,b,c}, one from the first mission: {a,c,d}, or none from the first mission: {c,d,e}. ALL three strategies are plagued by the same problem: if the 2nd mission also has exactly one fail, you cannot identify the 2 spies. Also, you've failed 2 missions. The win cannot be guaranteed.
Basic game unsolvable.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
January 7th, 2014 at 1:22:00 PM
permalink
Quote: StoneyI watched the game played on 'table top' on youtube (love that show. got me interested in several games).
they played a 5 player version that I thought relied more on luck than skill. each player acted as team captain for each round. obviously, each time the traitor was captain, the mission would fail. so, getting the other missions to pass relied on no traitor in the team, and with only 5 rounds, there is not enough time to deduce who the traitor is.
so, imo, the game is not "beatable". the game is short and with small groups, you have too high a chance to have the mole in the group. and with large groups, the chance is low enough that you didn't have to do anything... the missions would never fail. maybe the question should be, what is the optimal amount of people to play per traitor to make it challenging yet winnable.
With more players, you have more spies, and more folks on each mission. 6/7 seems like a good number. The voting for each mission team is interesting as well (it's useful to vote against some teams, just so you don't rush in too fast).
There are extra cards to add in more secret info (such as look at another players card or force a player to vote for a mission team). These add to the general chaos. Normally, the Resistance seems to lose in my groups.
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
January 7th, 2014 at 1:26:00 PM
permalink
Quote: dwheatleyI am going to interpret solvable as guaranteeing a resistance win. In that case, I submit the following for your consideration:
Neat, thanks, that's a quick incisive way of proving it as unsolvable. That's a good thing, by the way, as it makes it a lot more about the discussion on the teams, and trying to work out whose pushing for a certain player more than is reasonable.
"Then you can admire the real gambler, who has neither eaten, slept, thought nor lived, he has so smarted under the scourge of his martingale, so suffered on the rack of his desire for a coup at trente-et-quarante" - Honore de Balzac, 1829
January 8th, 2014 at 9:30:53 AM
permalink
A question that will take more work but is still interesting is: after a {a,b} = 1 start, find the resistance strategy that maximizes their chance of winning.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
