# Solution to Avalon board game

Question: If players are able to discuss strategy before playing Avalon, does the game have an optimal solution?

The strategy can be as convoluted as you want. I just want to know if in principle this is a "solved" game.

The game rules are fairly simple and for reference the details of number of good vs evil players, and rounds can be read here: https://en.wikipedia.org/wiki/The_Resistance_(game)

If there are G good and E evil players, at the end of the game team evil can always just randomly guess Merlin to win. So an optimal solution will be defined as:

• for team good, a strategy in which (regardless of what team evil chooses to do) they can guarantee succeeding at least 3 missions and team evil can't do any better than 1/G chance of choosing Merlin
• for team evil, a strategy which (regardless of what team good chooses to do) maximizes their chance of winning the game, with a chance greater than the trivial solution of guessing with chance 1/G

As far as I know, the rules are not entirely clear on what communication the players may do (besides forbidding just directly showing their character cards), for the purposes of this question, consider the following rule on communication (if playing by email, it would be equivalent to every message must be sent to all):

• Cannot rely on 'under the table' note passing, texting, etc. All statements made by a player must be public, in the sense that the every player has the raw message (even if not all players have enough context to derive the same meaning - ie. an Evil person stating he is Merlin is never confusing to an evil character since the evil characters all know each other, but can be misleading to a good character. Only the raw message itself must be public, asymmetric knowledge of intentions gained from a message is fine.)

I have a suspicion that despite not being able to trust any particular character is telling the truth, there might be a solution in favor of the good characters which takes advantage of the inherent asymmetry caused by the character Merlin and there always being more good characters than evil.

Can anyone think of a solution?

• "All communication is public", surely an encrypted message is not public? Oct 26, 2014 at 10:52
• Its there for everyone to see. There is no hiding the message. If people didn't share the messages publicly, this wouldn't work. Oct 26, 2014 at 11:00
• Encryption/Encoding is hiding the message. :) Oct 26, 2014 at 15:23
• I'm not suggesting anyone actually play this way (it would be dreadfully boring and pointless). I am just analyzing this as a puzzle. All messages are public. The whole point of encryption is that you don't need to hide the message. Even the key exchange messages are public. If it is not allowed for a public message to mean different things to different players, then anything an Evil person says in normal games are "hiding the message", since the Evil players have additional context the good do not. Again, I am not suggesting anyone play it this way, I am just trying to analyze it as a puzzle Oct 26, 2014 at 23:24
• FWIW, I like the question, it is interesting and novel. I've played enough to know some of the twists and have some ideas, but proving it is likely beyond me. Oct 29, 2014 at 3:20

Despite not being able to trust any particular character is telling the truth, in some circumstances there appears to be a solution in favor of the good characters which takes advantage of the inherent asymmetry caused by the character Merlin and there always being more good characters than evil.

Here is an attempted mathematical solution for team good.

This relies on Merlin knowing all the evil characters. So will not work if the character Mordred is included (an evil character Merlin does not know about). If other special characters are used, it should not affect anything. It is also a work in progress in that this strategy gives quite a bit of extra information to "team good", but there may still be some details that need working out. (For example, I've already had someone point out to me that one must be careful to pad out messages appropriately or just knowledge of the length is enough context to figure out who Merlin is with this strategy.)

After dealing character cards, a good person suggests:

1. the following strategy will allow good to win, so provably deviating from these rules will indicate you are evil
2. whoever is the first mission leader will be now referred to as player #0
3. players clockwise from #0 get numbered accordingly
4. each player (i) comes up with a secret phrase: phrase_i
5. from this, each player (i) generates a secret number for other player (j) as secret_ij = HASH( phrase_i + string(j) )
6. use these secret_ij numbers along with public key exchange to generate a crypto key between each player: Key_ij = Key_ji = result of public key exchange between player (i) and (j)

Now with that setup, the good player goes on to suggest the following:

1. Special round of discussion: all players openly/publicly give encrypted messages to the other players stating one of the following:

7a) declaring themself as not-merlin

7b) declaring themself as merlin, stating who all is good, and providing his phrase_i so all keys and therefore messages from him can then be read by that person

2. Merlin should declare "merlin" to all good guys, and "not-merlin" to all evil. Normal loyal servants should just declare "not-merlin" to everyone.

3. if a good player gets a message deviating from this rule, they can immediately release the related key used for that communication to out the evil person. So evil effectively must pretend to be normal good or merlin.

4. More generally, a good person should immediately expose any fake merlin (release his secret phrase) if they can prove they are fake without giving information about merlin.

For example, if a fake merlin ever claims another person claiming to be merlin is good, this outs themselves as fake, as the real merlin would never do this. Unfortunately, a good person might need to keep this to themself, as revealing this could reveal information about Merlin. However if multiple merlins choose groups such that there is no consistent way for one to be real (for example two merlins claiming each other as good, or three merlins claim such that it makes a cycle), then the entire group is fake and should be exposed.

5. Now a round of plaintext discussion (no encryption). Each player states which groups of good guys were declared to them by people declaring to be merlin. (Note: only the groups are released, not who claimed the group.)

6. If there is a group declared such that not everyone in the group states they were told they are in the group, then that group is clearly false (as good has no reason to deviate from the plan).

Since the number of good > the number of evil, any group with the correct number of people will necessarily include at least one good. This means evil cannot usefully mislead here.

7. If there is a player who appears in all proposed sets of good players, he must be good. All good players should release all secret phrases they know to this player. Now even more restrictive than before, this player then can expose fake merlins whose group selections include each other in a revealing manner.

8. If there is enough information that every one should be able to deduce a guaranteed good team without revealing merlin, someone can just explain it. Good, having superiority in numbers, can now ensure the correct group is sent each time.

9. If there is not enough information for everyone to determine good/evil, the mission leader picks a team which will eliminate as many proposed "good groups" from consideration as possible. If Merlin was the mission leader, he could purposely pick a correct or incorrect group here, so no information about Merlin is lost here. If the mission wouldn't actually eliminate a possible "good group", and the person still insists on this mission team anyway or calls a vote before discussion, it outs themselves as evil and good can vote the mission team down. (Note this of course does not indicate good/evil for the team they suggested though.) So evil has to play along here to try to help narrow down a team.

10. If the mission fails, it should by design eliminate at least one, if not more, proposed "good groups". If the mission succeeds, it provides no information. Proceed to pick the next one.

I may be missing something, but I do not believe team evil gains any information about merlin from this strategy. I also am not sure how to prove it, but it appears to me there is enough information to always have good win.

First note that if every time a mission fails, at least one possible "good group" is eliminated, there have to be at least 3 fake merlins for team evil to have a chance. So the only potential issue is in the 7-10 player version.

Second, note that the intersection of all proposed good sets must actually be good.

Third, if the intersection between two proposed sets has only one person, that person must be good.

This along with previous information and other simple deductions is quite restrictive.

For a concrete example, consider the seven person game: 3 evil, 4 good.

All three evil characters need to successfully claim to be merlin to have a chance. So if we can eliminate one by deduction, good wins.

If no fake merlins include an additional evil member in the proposed group, then there are E+1 people that have only been included in one group. The complement of this must be good.

If all fake merlins include an additional evil member in the proposed group, then there will be a cycle of fake merlins claiming other fake merlins are good, and thus out each other.

So at least one fake merlin must include G-1 good members in the proposed group. Thus if there is a proposed group that doesn't have an intersection of size G-1 with at least one other group, it can be discarded. (Taking the number of groups down to 2, thus allowing the good to win.)

For a seven player game, there are three missions requiring <= G-1 people. So if no proposed group can be eliminated only with deduction, then always choose for the mission the intersection of at least two groups. If evil fails the mission, they eliminate more than one group, and thus good again wins.

• This "solution" give the good side perfect knowledge which goes against the rules and the spirit of the game. Oct 29, 2014 at 4:03
• @JoeW I think the point of this is that the good side don't have perfect knowledge at the start, but after a couple of failed missions they can derive it. Consequently this answer suggests that if all players play in this (pain-staking) way then the good team can force a win. It's definitely against the spirit of the game - MWilliams mentions in a comment on the question "I'm not suggesting anyone actually play this way (it would be dreadfully boring and pointless).". Oct 29, 2014 at 9:24
• In particular I don't think many people would like to be part of a game where they have to manually perform an asymmetric key exchange protocol before they can start playing! Oct 29, 2014 at 9:28
• @tttppp This is an attempt to get perfect knowledge without having to play the game and by using a method that violates the rules. Oct 29, 2014 at 12:46
• @PaulMarshall It may not be spelled out in the rules, but I am pretty sure that a game with hidden roles prohibits methods to deliver perfect knowledge to a side that is not supposed to have it before you even begin playing. Nov 30, 2014 at 20:12

It seems all evil has to do is: all the evil players conspire who they think Merlin is (it can be a random guess), and they each pretend to be Merlin and out the other spies and declare the real Merlin as also a spy.

If they are right in their random Merlin guess, the other players gain no new information, and Merlin appears indistinguishable from other players. Play continues as normal, with the spies knowing they were right about their Merlin guess, so the assassin will win the game for them.

If, as is more likely, they are wrong, the spies are easily outed, the missions are brief and obvious, and the assassin has already eliminated one possible target for Merlin, and has a slightly better chance in picking.

Point is, still far from a guaranteed "good" win.

• This makes some pretty big assumptions about what the other players would do. Particularly whether the non-merlin good guys would listen at all to someone claiming to be merlin and outing the spies, as the real Merlin is unlikely to do so. Sep 18, 2015 at 22:39