PDA

View Full Version : The Art of Mafia Detection



Kommodus
01-27-2007, 18:38
The Art of Mafia Detection
An Analytical Approach

By Kommodus


Anyone who has played a game of Mafia online, on this forum or any other, knows something of the usual methods used by townspeople to identify the mafia in their midst. Some players will vote to execute a fellow player based on virtually any arbitrary reasoning – even something as silly as the name of the player they are voting for. More advanced players frequently perform intense exercises in psychoanalysis, attempting to identify suspicious behavior in the content of their peers’ posts. A few players have achieved high degrees of success with this approach. However, while this kind of analysis is useful (and, in fact, essential) in identifying the guilty, experience has shown that the results it produces are far more frequently incorrect than correct. Clearly, there must be a more reliable way.

Human beings are many things, and among others they are predictable. Anyone able to discover the rules based on which a particular individual acts will be able to predict that individual’s behavior with a reasonable degree of accuracy. We do this unconsciously in our everyday interaction with our various acquaintances. In addition to predicting effects from causes, therefore, it is possible to derive causes from observed effects.

When human behavior can be measured, quantified, and analyzed, the causes and effects of said behavior become much easier to identify. Online Mafia games provide an exceptional environment in which to measure human behavior, and to propose and test theories concerning it. The following is a summary of the approaches I have taken to this puzzle.


Chapter 1: Watson

When most of the players in a game of Mafia are substantially inexperienced, it can be assumed that the tactics used by both sides will be simplistic in nature. A brief examination of the rules of the game implies that, in general, the following principles will hold:


When voting, the townspeople will vote to execute players they think may be mafia.
Members of the mafia, on the other hand, will vote to execute players they know to be innocent.
The second rule is, of course, not always true. Experienced Mafiosi will sometimes vote for their partners, in an effort to distance themselves from them and prevent the townspeople from recognizing their partnership. This is so common a practice that it is now expected – mafia members may appear to accuse and argue with each other in an attempt to confuse the townspeople.

Nevertheless, a simple numerical strategy for identifying the mafia involves tracking each vote that is cast, and tracking who has voted for the most verifiably innocent players. (Keep in mind that once a player has been killed by the mafia, they are known to be innocent, since in most variations of the game the Mafiosi are not allowed to kill each other. This rule does not hold true in complex games with multiple mafia families, in which this method is rendered useless.)

Suppose, for example, you are a townsperson trying to decide between three possible suspects, each of whom has cast six votes. Suspect 1 has voted for three players who have been killed by the mafia, Suspect 2 has voted for five assassinated players, and Suspect 3 has voted for four. According to this method, Suspect 2 would be the best choice to lynch, having voted for 83% verifiably innocent players (compared to 50% and 67% for Suspects 1 and 3 respectively).

https://img104.imageshack.us/img104/7233/watsonwb4.th.jpg (https://img104.imageshack.us/my.php?image=watsonwb4.jpg)
Figure 1: Watson in action

This method takes into account a relatively small amount of data, and takes quite a few rounds to amass enough information to be useful. It frequently helps to augment the method by using other pieces of useful information – for example, players do not have to be assassinated to be verified as probable innocents. Various other game events or conversation can serve this purpose as well.

This method is simplistic and understandably easy for the mafia to foil. Because it relies on observing the relatively obvious, I have given it the codename Watson.

METHOD QUICK FACTS

Codename: Watson

First Used: Mafia II

Results and History:

In Mafia II, this method successfully identified Lemur in round 6. By round 7, it pointed correctly to Cowhead418 to a lesser degree.

Following that game, vote indexing fell out of favor quickly. I was selected as a Mafioso in Mafia III, and therefore used it only in pretense. By the time that game had ended, more advanced techniques were in development.

Strengths:


Works well in games with a simple setup and relatively inexperienced players.
Doesn’t require much effort to execute.
Weaknesses:


Nearly useless in games with multiple mafia families.
Only the most inexperienced Mafiosi will be caught by it.
Players who abstain, vote “no lynch,” or simply lurk deprive the method of the data it needs to function.
Closing Comments:

Keeping track of votes is still a good practice, and can be used to supplement more advanced detection techniques. Seamus Fermanagh is notable for continuing to track voting patterns – a practice he has used with some success.


Chapter 2: Lestrade

From its inception, the analytical method code-named Lestrade was shrouded in secrecy. When I informed the public in Mafia IV that Masy was certainly a Mafioso, I refused to divulge my reasoning. Though puzzled and skeptical, the townspeople went along with my recommendation, bringing a remarkably quick end to the game.

Ironically, Lestrade is not, in fact, a numerical method at all. After Mafia II I spent some time reflecting on other possible ways with which to analyze voting data. It quickly became apparent that no other methods would be forthcoming. Mafiosi are entirely capable of voting as if they were normal townspeople, and if familiar with vote-indexing techniques, they would be sure to do so. What was needed was not a new way to analyze the data, but entirely new data.

The inspiration for Lestrade came from something I had noticed during previous games. Players were sometimes accused of being mafia on the basis that they had been observed sending private messages. However, this approach suffered from several crucial flaws, which were frequently pointed out:


Private messages can be sent for any reason. The reason could be completely unrelated to the game. PMs are also often sent by players holding special pro-town roles, as well as by those holding pro-mafia roles.
Attempting to catch a fellow player sending a PM can be a time-consuming task. It is impossible to watch everyone at once, and it can only be done for a relatively short period of time. Unless you spend an enormous amount of time watching the forum each day, the players you hope to watch will frequently be online when you are not.
It occurred to me that if it were possible to monitor the profile of every player in a game at all times, the problems listed above could be mitigated. It would still be impossible to identify the target(s) of the private messages or their content, but it would certainly narrow the suspect list down to a very few individuals.

As soon as this thought occurred to me, another logically followed: it was possible. In fact, for a computer programmer with basic knowledge of string parsing, it was positively easy. Over the next couple of days, Lestrade took shape. It was a computer program that downloaded the profiles of a list of players at specified intervals (about every 30 seconds). The most recent activity of each player was extracted from the profile and stored in a database, where it could be queried at my leisure.

https://img104.imageshack.us/img104/2637/lestradely3.th.jpg (https://img104.imageshack.us/my.php?image=lestradely3.jpg)
Figure 2: Lestrade in action

The tool worked flawlessly in Mafia IV. A casual glance at the data on round three revealed the identities of the remaining Mafioso (Masy) and the detective (Reenk Roink). The second Mafioso, discovery1, had already been lynched before the program was complete.

However, immediately following this game, the ethics of the practice of “profile-watching” began to be called into question. It was seen by some as a poor way to play the game. In addition, a number of strategies were proposed to counter it, such as using invisible mode or communicating through a means other that private messaging.

Regardless of these ethical questions, I had already made a decision to use Lestrade one time only. The point was not to win game after game for the townspeople, but to see if my newly-devised method would work. Once my curiosity was satisfied, I promised never to use the same tactics again.

Because this method requires the right conditions and a certain amount of luck to work, I decided to give it the code-name Lestrade.

METHOD QUICK FACTS

Codename: Lestrade

First Used: Mafia IV

Results and History:

At the start of the game, this method had not been developed yet, and was created and tested only as the game progressed. By round 3, the bugs were worked out and Masy was immediately identified. Simultaneously, Reenk Roink was discovered to be the detective. Discovery1 was never identified, as he had been lynched in round 2 before the tool was complete.

Strengths:


Extremely powerful in the right circumstances; theoretically has the ability to catch the mafia in a single round.
Weaknesses:


The ethics of using a method such as this are questionable at best.
Easily defeated through the use of invisible mode.
Rendered weaker in games with a large number of special roles, since many players will have a reason to send private messages.
Closing Comments:

Following Mafia IV, I promised never to use this tool again, due to its apparent game-killing power. However, adjustments in the way the game is played have rendered it largely useless anyway.

Profile-watching continues to be an occasionally-used tactic. GeneralHankerchief used this method to identify Destroyer of Hope in Cosa Nuova. I have not seen it used since, as it appears to have fallen out of favor with most players. In addition, invisible mode is much more common now – some games require it.


Chapter 3: Holmes

The weaknesses inherent in my first two approaches made me aware of the need for a new method – one that would be powerful enough to deal with counter-tactics from the mafia and flexible enough to be useful in complex games.

In devising my next tool, I thought back to the normal ways in which players try to identify the mafia. They generally have some notion of how the behavior of a Mafioso differs from that of an innocent villager, and they look for this “guilty” behavior. If they are familiar with the players participating in a game, they may also look for changes in a particular player’s behavior, which commonly (though not always) indicates guilt. These indicators are valuable, but the subjective ways in which they are normally applied are prone to error. I wondered if, and how, they could be quantified.

Clearly, there is no simple way to quantify the content of a post. It is beyond my ability to write a program capable of interpreting a piece of text and determining whether or not it should be deemed “suspicious.” However, many characteristics of a player’s posts in a game can be quantified, including the following:


How frequently does the player post?
How regularly does the player post?
How long are the player’s posts, and how does the length vary?
How long does the player wait after the beginning of a turn to post?
These are just a few of the many metrics that can be used to measure and quantify a player’s behavior. By the time this approach was devised, many games had already been completed in this forum. Therefore, I had a wealth of data readily available to draw from.

Of course, manually gathering the necessary statistics would be prohibitively time consuming. Fortunately, in Lestrade I already had a program capable of downloading and parsing web pages. I simply applied it to a slightly different problem, and soon the data was rolling in.

One of my first questions was: do Mafiosi tend to follow certain behavioral patterns? If they do, it is only subconsciously. Mafiosi will attempt to act as naturally as possible, so as to avoid suspicion. However, in the very act of trying to act normally, their behavior changes subtly. For example, they may put more thought into their words, taking more time to decide what to say. They may inadvertently appear to be diverting more or less time to finding the mafia. I hoped that a statistical analysis would identify these patterns and more.

When I analyzed the data from past games, there were certain behavioral patterns followed by many Mafiosi – an encouraging sign. However, not all Mafiosi matched these patterns, and many townspeople did match them despite being innocent. I decided that this approach would be helpful, but would not yield quick or easy answers.

The second question was this: how can a significant behavior change be identified? Because I had data from all past games, it was easy to compare each player’s behavior in a current game with their behavior in past games – provided they had played before. However, no one plays exactly the same from one game to the next. Therefore, it became a matter of deciding which changes were significant. This determination was ultimately more art than science, and is not worth discussing in detail here.

The first time I used Holmes, I combined the observations discussed above to produce a short list of likely suspects. However, that was as far as I could get with purely objective means. The numbers didn’t tell quite as clear a tale as I hoped they would.

Therefore, I built an additional feature into the new program, which would become one of its most important features. I gave it the ability to quickly extract all posts made by a specified player. While simple, this feature was very powerful. If you are a somewhat serious player, think about how much time you have spent paging through a long thread to examine a particular player’s behavior! With my new tool, this task became effortless, giving me an advantage in terms of simple organization.

https://img201.imageshack.us/img201/4773/holmesxi7.th.jpg (https://img201.imageshack.us/my.php?image=holmesxi7.jpg)
Figure 3: Holmes in action

By combining the statistical profiles of each player with a bit of subjective analysis, it ultimately proved possible to significantly narrow down the list of suspects. In Mafia V, the method code-named Holmes passed its first test, though not without some difficulty.

Because this method is at its core a profiling system, I decided to code-name it Holmes, after the great profiler himself.

METHOD QUICK FACTS

Codename: Holmes

First Used: Mafia V

Results and History:

This method was programmed during the opening rounds of Mafia V. It was mostly operational by the third or fourth round.

Reenk Roink was successfully identified in round 5. At the time, Ignoramus and Seamus Fermanagh (the other Mafioso) were the other suspects. By round 7, Ignoramus had dropped off the list and Seamus had been identified.

Strengths:


Flexible enough to function in a wide variety of situations.
Difficult for the mafia to defeat, even if they know it’s being used against them.
Weaknesses:



Not very useful when profiling a new player’s behavior, as there are no benchmarks to compare with.
Frequently produces a list of suspects that contains innocents as well as mafia.
Closing Comments:

This method has much room for improvement. It can be defeated by careful Mafiosi, and is not foolproof. It is likely to undergo evolutionary changes over time, as new metrics are devised to analyze behavior. Let the mafia beware!


Conclusion

Many players may not like the idea of an analytical approach to the game of Mafia. This is understandable, and in all honesty there are many different approaches that can yield success. For example, I have frequently discovered that players are doing excellent detective work outside the thread, through various private communications. Approaches such as these can yield astonishing success.

However, one of my motivations is time. It may be thought that I’ve put a great deal of time into the methods I’ve discussed. The reality is, however, quite different: by creating programs that analyze the game for me, I ultimately spend less time playing the game. I rarely have much time to spare on the private discussions in which many engage.

Of course, the main motivation throughout has been intellectual curiosity. Mathematics and technology have been leveraged in many popular games, such as chess, checkers, etc. Can they be leveraged in psychological games, such as Mafia? As I consider everything I’ve done, I realize my efforts have ultimately been quite simplistic. However, they have been enough to make it clear that analysis of such games is both possible and potentially fruitful.

I hope this document has been helpful and informative.

doc_bean
01-27-2007, 18:48
I now fear Sasaki might try to create his own Lestrade. Though with all the PMing going on it probably won't be as good anymore.

Sasaki Kojiro
01-27-2007, 19:02
Very interesting. I do spend a lot of time rereading threads or using the search feature to find someones posts from a thread.

Haha, I thought you were just insanely compulsive when I saw you checking peoples profiles over and over and over in Mafia IV.

Caius
01-27-2007, 19:03
Is following someone legal?

I want the tracker program.

Good guide.Now i suspect someone.

Kagemusha
01-27-2007, 19:05
Exellent post Kommodus and Exellent information.:bow:

doc_bean
01-27-2007, 19:10
Is following someone legal?

I want the tracker program.

Good guide.Now i suspect someone.

He can't follow you when you're in invisible mode, which is why most of us have it turned on.

Sasaki, however, can.

Thanks for the info Kommodus !

Alexander the Pretty Good
01-27-2007, 19:16
Whoa. I'm taking notes. :book:

Kommodus
01-27-2007, 19:30
Haha, I thought you were just insanely compulsive when I saw you checking peoples profiles over and over and over in Mafia IV.

:laugh4: :laugh4: :laugh4:

I figured you thought that. The truth is I almost never manually clicked on anyone's profile.

And Sasaki, you better not go create your own version of Lestrade... :help:


Is following someone legal?

I want the tracker program.

If it's legal, it's only barely so; either way, it's hardly ethical. That's why I only did it once and promised not to do it again. :yes:

And no one gets my programs. Go write your own! :smash:

Caius
01-27-2007, 19:32
What did you use.

Kommodus
01-27-2007, 19:37
What did you use.

I used C# to write Lestrade and Holmes. Watson was just a spreadsheet with some VBA macros.

Csargo
01-27-2007, 20:21
Very nice Kommodus though something you missed with the profile watching is you can also just open another Org and you wouldn't be able to see the person PMing unless you were watching their profile every 10 seconds or so.

At first I thought this was your new mafia game. :bigcry:

Dutch_guy
01-27-2007, 21:47
I enjoyed reading that Kommodus, you obviously know what you're doing and it did work for us townies in many games thus far.

Needless to say, the main objections against such a programm you raised yourself; the chance you're mafia is a real one (especially if you get to chose your mafioso yourself) and then the programm, and you with it, can't be trusted. Plus, again you said this yourself, the game is more of psycological game, reading into other player's words and all that, although admittedly numbers do help a lot when we have things as post count and posts per day, like here.

Let us know if that super programm ever comes along though ~;) I daresay we'd be interested...

:balloon2:

CountArach
01-27-2007, 23:38
Great read Kommodus! :2thumbsup:

Moros
01-28-2007, 17:06
I'm glad that the time I was mafia, I was with you. I still manages to ***** it up tough.

arrividercri ~;)

Kommodus
01-28-2007, 17:22
I'm glad that the time I was mafia, I was with you. I still manages to ***** it up tough.

arrividercri ~;)

Ah, no worries GG! You were actually a decent mafioso; you made it pretty far. It didn't work out in the end, but then again, I'm a pretty bad mafioso myself! :laugh4:

Moros
01-28-2007, 17:27
Sure you are. If it weren't for you I'd be glad if I made a round or 5.

So did the program say if I behave mafioso like back then? Are you also following, capo de tuti capi with your program? I know I'd love to see the statistics. dirty white glove mafiosi!

Crazed Rabbit
01-28-2007, 18:33
Ha, t'was not the screw-ups of the mafia, t'was the unlucky detective who nailed them in mafia III!

~;p

Anyways - on to the subject. This is pretty fascinating. But could not a player purposely using wildly varying posting schemes in different games make it more difficult for the holmes detector?

Crazed Rabbit

Moros
01-28-2007, 22:43
would be difficult to always think about that. And when you are'nt mafiosi, I don't think you'd think about it. The main problem is to keep at it and not change it when being mafioso.

Kommodus
01-28-2007, 22:53
Anyways - on to the subject. This is pretty fascinating. But could not a player purposely using wildly varying posting schemes in different games make it more difficult for the holmes detector?

Of course. But then they'd look guilty, and players who do that tend to get lynched rather quickly.

*indicates Reenk Roink*

Husar
01-29-2007, 00:20
I just read parts of the above, but Lestrade explains why the org is so slow at times.~;)

Kommodus
01-29-2007, 15:39
I just read parts of the above, but Lestrade explains why the org is so slow at times.~;)

Ah, don't be silly. ~;) Lestrade was used for a day or two tops, and that was months ago. Never used it since - and never will! :2thumbsup:

Reenk Roink
01-29-2007, 17:47
Of course. But then they'd look guilty, and players who do that tend to get lynched rather quickly.

*indicates Reenk Roink*

Kommodus, if you have the spare time and are curious like I am, can you go ahead and test your Holmes in every game I've played?

I really want to see how guilty I was, and if I was somehow more guilty in the games that I was really Mafia than in the ones I was not.

This is really interesting... :2thumbsup: