Archived

This topic is now archived and is closed to further replies.

AI for Mafia aka "Werewolves"...

This topic is 5010 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey there, I''ve recented started a new AI project. I thought it might be interesting to see if I could program some computer players for the game Mafia. I''m not sure if this is a game lots of people know about, or just something we play at college. The basic idea is that the game is played with 8 - 12+ people and a moderator. 2-3 people are secreted designated as mafia at the beginning of the game. Everyone else is a citizen. Play occurs in two repeating phases: Day and Night. During the day, the citizens discuss who they think is in the mafia and can vote to lynch someone. A majority results in a dead lynchee. At Night, citizens all "go to sleep" (close their eyes). The mafia players then silently choose someone to kill during the night and signal their choice to the moderator. At the beginning of the next day, the moderator makes up some gruesome death story and tells the citizens who died. The game continues until all the mafia are lynched or until there are equal numbers of citizens and mafia (at which point the citizens would no longer be able to get majority to lynch). The game is really fun and is an interesting psychological experience. To make it more interesting, you can add other roles to the mix like sheriffs, doctors, ect... For those interested, rules can be found here (as well as a good number of special roles) http://www.princeton.edu/~mafia/ I thought I would design a moderately complicated mafia game (sheriffs, doctors, maybe some other roles) and then try to write some AIs to play it and pit them against each other. I''m not sure how well this will work because when you play mafia in person, really the only way to get information about what is going on is by watching other people and noticing if anyone "looks guilty" (though you can also get information by seeing who votes to lynch who, even in the plain vanilla game. Extra roles add more ways to get information and more things to talk about). My friends and I at school have occasionally played mafia on an online BBS, and this works surprisingly well, so it''s not absolutely necessary to be able to observe the people you are playing with. I''ve only thought about it for a couple of days, but it seems like if I wanted to do a credible job of writing a Mafia AI, it would have to have some kind of fuzzy knowledge representation system coupled with a theorum prover that could determine probabilities for other people being in the mafia (or for other things). I''m sure this isn''t the only way to do it, but it seems pretty flexible. Does anyone have any suggestions of materials I should look at? It occured to me that if I spent some time on this I could write up my solution as a research paper in game theory. Writing some research papers and getting them published is something that I''ve been meaning to do before I apply to grad school. If I were going to do a professional job on such a paper, does anyone know of any prior art? I believe that plain vanilla mafia is a solveable game, in that you can determined the expected probability of any side winning before the game starts (though I have not seen a rigorous proof, I think mafiascum has some probabilities on their site). Even with extra roles, it probably remains solveable in this respect. Any ideas, comments, or pointers to interesting material? ---------------------------------------- Let be be finale of seem, seems to me. ---------------------------------------- Coding: http://www.stanford.edu/~jjshed/coding Miscellany: http://www.stanford.edu/~jjshed

Share this post


Link to post
Share on other sites
So I can''t help but to wonder if no one has responded because:

1. This problem isn''t interesting from an AI/Game Theory perspective.

2. No one has heard of this game before and has no idea what I am talking about.

or

3. No one knows of anyone else that has tried to implement an AI for this or a similar type of game.

-------------------------------------------------------------

Really, if someone who knows what they are talking about could help me distinguish between 1 and 3, that would help me out a lot, since I am tossing around the idea in my head of turning this into an independent research project next quarter at school, culminating in a paper that I''d like to try to get published. So if there is nothing interesting about this problem from a Game Theory/AI perspective, it would be nice to know about that now rather than down the road when I go to write a paper on it. Or, if this is unexplored territory, that would also be great to know.

:-)

Are there any college computer science/math professors who post on this board who would care to weight in?



----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Coding:
http://www.stanford.edu/~jjshed/coding

Miscellany:
http://www.stanford.edu/~jjshed

Share this post


Link to post
Share on other sites
The game sounds neat, though I''ve never heard of it before.

I would guess you''d want to have each AI keep a list of votes in their head, to try to match a pattern of voting.

Would such a complicated system really be better then just a simple ChooseRandomPersonToVoteFor() though? =P

Share this post


Link to post
Share on other sites
I can''t see any kind of logic to the system, as it seems to be based on guesswork and possibly trying to read into what people say and how they act. So I can''t think that any algorithm would be able to do better than chance at this game. Maybe there''s something I don''t understand though.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
It''s an interesting game. The citizens would analise the votes trying to find a pattern and the mafia guys could try to lynch the ones that are voting right. But would this make them suspects? Maybe yes if you are looking and talking to the actual persons, but not from a mathematical point of view, as far as I can see (didn''t put that much thinking to it though).

I don''t know if its good from the Game Theory point of view. The citizens don''t know if they are voting the right guy so it''s not easy to find the better way to handle this. The tradeoff between helping yourself and helping the group is not clear. Maybe the guy that is only worried about himself will allways vote the most voted guy (and the second if the first died last night). So that it can live in the end (would that be a good thing according to the game rules?). And the altruistic one would try to find the mafia guys.

You could think about some other behaviors like that, but like I said, its not very clear.

Anyway, you could try something that could be fun. Make you citizens play several times: they remember their last state when the game ended, but they don''t remember who are the mob members. And the mob members are allways the same ones(also remembering their last state, so you can let them evolve as mob members). Then after several tries, you can compare the results see if their behavior is converging to something.


Share this post


Link to post
Share on other sites
Kylotan, I think you may be right. For a simple game of Mafia vs. Citizens, randomly selecting who to kill is probably the best strategy. The problem is any better Mafia strategy has the constriant that it can''t identify the strategist as being mafia, otherwise is is obviously not optimal.

My idea was to analyze a more complicated game with a doctor and a sheriff. These are both special citizen roles. The doctor can save someone during the night, and the sheriff can determine whether a person is mafia during the night. A lot of the fun of this game when it is played in person is that people will claim to be the doctor or the sheriff, and the other citizens have to decide whether to believe them or not (the mafia has some incentive to pose as either). Sometimes two people will claim to be the same role and then everyone has to decide who is mostly likely the doctor or sheriff based on how good their story is (things like who they checked/saved every night).

In particular, I was going to craft AI''s that had different personas - talkative, suspicious, bloodthirsty, ect. and see if any of these traits help the winning chances of that player.

Anyways, I''ve started work on the program and I''ve got it running through basic games and collecting statistics. Once it becomes interesting enough to play with, I''ll probably post the source on my website.

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Coding:
http://www.stanford.edu/~jjshed/coding

Miscellany:
http://www.stanford.edu/~jjshed

Share this post


Link to post
Share on other sites