TLDR; An open source outline of game theory inspired constraints for tackling the AI Werewolf game. Developed in python by Ari Bornstein, Moty Michaely, Noa Yehezkel Lubin and Dor Hirst as part of their work with Bar-Ilan University
What is AI Werewolf?
Werewolf, is a party game created by Dmitry Davidoff in 1986 modelling a conflict between two groups: an informed minority, and an uninformed majority.
Our task was to implement an agent for a “werewolf” game competing against unknown agents. In this game each player can be either one of two species: werewolf or villager.
Code for the game server can be found here:
The groups are uneven, the villagers are the majority, but they have no knowledge about the other players’ species. The werewolves are the minority, but they know the other players’ species. The objective of each species community is to eliminate the other. A player wins if he was a part of the community of the species that was not eliminated. In addition, there are special roles: seer, medium, bodyguard and possessed.
The game is composed of two phases:
· The night: when werewolves can communicate (“whisper”) and vote for a certain player to be attacked.
· The day: when villagers and werewolves can communicate (“talk”) and vote for a certain player to be eliminated.
At each of the phases of the game, the server calls on the agent to return an action for its relevant moves such as talk and vote (all players), seer(divine), guard(body guard), whisper and attack (Werewolves).
For more information on the rules of the AI wolf game check out this presentation from the game designers.
https://medium.com/media/888e4835231ff57092c9da26f9913e65/href
Designing a Werewolf Agent
Since the villagers have imperfect information about werewolves, and the werewolves have imperfect information regarding which villagers are seers, mediums and bodyguards, in order to choose an ideal strategy we need a flexible and computationally efficient player estimation strategy to piece together what players roles are, from their actions and our agents certainty given his or her current role.
We first explored using the methods we learned in class such as policy, valueiteration and Q learning to help refine these estimations in addition to supervised learning methods based on games we played among ourselves.
However, we quickly discovered that the amount of computational time required to calculate these estimates and thresholds well exceeded the allotted 115ms threshold provided to us by the game server.
To build an agent that could correctly estimate, we applied the following strategies that we learned from our own analysis of the werewolf game. We treated the phases of the game as subgames and tried to estimate optimal strategies using some of the game theory concepts we learned. In the following section we will outline these estimation strategies for the different roles and their justifications.
One thing to note is that in order to win the game we needed not only to think about the game itself but also about how other competing agents and their designers would interact with our agent.
1. Estimate Strategy:
Our agent stores mappings of estimated roles as either certain or estimated.
- “Certain” are only roles we are 100% sure about, and estimate will hold roles we have only an estimation for. The map holds for each role the certain and estimated players.
- We will update the estimations according to both talking and whispering stage for werewolf players. This estimation is based loosely on signaling theory since we don’t have the thresholds but can infer certain actions and types based on player behavior.
Estimating the Seer:
If my agent is a seer than he/she is certain about their role. Otherwise the agent will estimate the seer according to which agents said “coming out” about role “werewolf” / “villager” consistently over the course of the game. The assumption being that since the seer is the villager role in the game with the most information it is in their interest to share that information consistently. The regular players do not have enough information or in the game to consistently say coming out and while the werewolves have this information it is in their incentive to lie so they are unlikely to be consistent with their calling out of other players.
Estimating the Medium:
Our agent estimates the medium according to which agents said “coming out” about the seer role the most, the rationale behind this strategy is that the medium has the ability to discover who the seer is and he/she is going to try to discover seer and let everyone know. The medium has the ability to estimate the seer better than the other players, since he has the most information about the roles of the players who died (while the other players do not have that information) and he can cross validate it with the history of who was correct the most about the players’ roles.
Estimating the Bodyguard:
Our agent estimates the bodyguard by looking at for the message “request guard” by agent X and no one died then X is guard. If no one died it means that the guard successfully protected someone and since we have no other information as to who that may have been our best guess is to assume that the bodyguard protected one of the people who asked for help.
Estimating the Possessed/Werewolf:
Our agent estimates the werewolf as follows. If the agent is a werewolf he/she marks all the other werewolves as certain. If the agent is the seer he/she marks all the werewolves he/she has divined as certain. If the agent is a medium role is medium if at the end of the day a villager died, the agent marks ones who voted for him/her as potential werewolves.
Estimating the villagers:
If the agent is a werewolf the agent marks all villagers as certain. If the agent is a body guard and protected a villager and no one died it means the player he/she protected is indeed a villager and so can mark them as a certain villager. If the agent is a seer they will mark all the divined villagers as certain. If we have a seer in the certain list, what he/she says.
2. Whisper Strategy:
In the whisper stage our agent says “coming out” / “estimate” for it’s target the target logic the same as who it plans to vote for. Since there is so much uncertainty in the game and it is in the villagers interest to communicate effectively we chose honesty as the best strategy.
3. Attack Strategy:
As a werewolf, if the agent will target the following players based on certainty it will target the following roles in the following order, seer, bodyguard, medium.
The importance of the guard grows as the game progresses therefore if number of days is greater than n/3 change priority of the guard and seer. When we don’t have any estimate for the special roles the agent will attack with the majority of other werewolves, meaning we will attach the most “attacked” (attack message) villager (and not dead) if there is no consensus with the other werewolves we target a random villager.
4. Talk Strategy:
If the agent is a werewolf it is in our interest to kill a villager with the same priority in of the attack strategy. However if we always tell the villagers to kill the most high profile targets they may get suspicious due to watching our signals therefore it’s in our incentive to lie.
Yet if we always lie about who we want killed it will be hard to target other villagers and might be suspicious.
Therefore, killed the agent will lie about it’s “coming out” / “estimate” with probability p= 20%. The 20% threshold was determined by empirical experimentation. To learn more about this kind of estimation one should check out mixed Bayesian strategies.
Else if the agent is not a werewolf we say “coming out” / “estimate” if I am certain/estimated a werewolf role — just like whisper strategy. We have 10 turns we shouldn’t say the same thing each turn we should say things in this order
- Tell everyone to vote for a werewolf
- Call out the remaining certain werewolves
- Estimate the werewolves in the estimate list.
- Shut up because we don’t want to reveal to the werewolves who is who
5. Vote Strategy:
If the agent is a werewolf then their vote strategy is the same as attack strategy. If the agent is a villager then he/she will vote for a random werewolf that they are certain about. If there is no werewolf they are certain about then they will vote a random estimated werewolf. If they have no information about potential werewolves they will vote for will vote for a random villager that is not estimated or certain to be dead, a seer, a medium, a bodyguard, or not a certain villager else they will chose a random non certain villager.
6. Guard Strategy:
The seer and the bodyguards are the two most important roles in the villager game therefore if the agent is a bodyguard and is certain who the seer is and the seer is alive protect the seer protect yourself.
7. Divine Strategy:
If the agent believes there is a werewolf/possessed in the “estimate” list divine them else select a random villager besides the current agent.
Conclusion
The above estimate and action strategy enabled us to build an adaptable agent that can take advantage of the information revealed throughout the course of the game while adapting itself to each individual role. For the reasons outlined above we believe this agent will perform competitively over the naive agent provided by the competition organizers as well an agent making uniform action decisions.
This solution helped us think more succinctly the concepts we learned about in the game theory segment of the course such as Zero Sum (only one team can win), team collaboration and inter team competition, mixed strategies and handling imperfect information.
The state constraints outlined in the above strategy align themselves for future exploration using search based simulation methods such as Monte Carlo Tree search.
For more information on AI search algorithms see.
AI Search Algorithms Every Data Scientist Should Know
If you are interested in learning more, feel free to reach out to me on twitter. Code for this work is open source and will be available shortly after the end of the competition.
Reference:
A Theoretical Study of Mafia Games, Erlin Yao, Key Lab of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, 100190 Beijing, China.
About the Author
Aaron (Ari) Bornstein is an avid AI enthusiast with a passion for history, engaging with new technologies and computational medicine. As an Open Source Engineer at Microsoft’s Cloud Developer Advocacy team, he collaborates with Israeli Hi-Tech Community, to solve real world problems with game changing technologies that are then documented, open sourced, and shared with the rest of the world.
Top comments (0)