To what extent do optimal strategies exist?

[Telamon]

Ok, so my recent posts about optimal strategies have gotten me to thinking... to what extent can there be optimal strategies in mafia? This is a question that has come up in writing my mafia simulator.

I think I've been making the assumption that for either side, mafia or citizen, there is always an optimal strategy. That is, if the adversaries deviates from this strategy, their chances of winning is decreased. Now I recognize that this might be circular logic. If the adversaries can do something else and not decrease their chances of winning, then the proposed strategy was not optimal by definition.

Also, optimal strategies often (always?) make the assumption that the enemy is rational. In real life games, this is often not a fair assumption. When playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right? This seems like it should be the case, but it also seems like there may be some lurking assumptions here that I do not appreciate.

These are important questions though, because I've never played in a game where both sides played the optimal strategy (if there was one) the entire game. People always make mistakes. Mistakes probably tend to hurt the mafia more than the citizens, if for the only reason that the citizens can afford to lose more people. So if I calculate odds for citizens winning games, assuming perfect play, in real life the probability of them winning is probably higher?

To answer some of these questions I think I'm going to add some personality traits to the players in my mafia simulator (like talkative, suspicious, vindictive, ect...) and see what effects that has - but I remain unconvinced that result would be an adequate simulation of real play.

Open Question: What would be required for a computer to simulate mafia games in a way that the strategies used by the AI players were directly applicable to real life mafia? Would the AIs have to possess full-fledged conciousness, or do you think it can be faked? For the sake of argument, assume that it is possible to build such a simulation - many will say that there are nuances of human play that a computer cannot simulate, but if you were to make the attempt, how would you do it?

I'm tempted to argue that the problem is NP-complete, but I'll end my long-winded post here. It already seems rather out-there compared to most other posts here.

[mathcam]

Well, I think you have to be more specific. If you assume the rationality of all players (which is indeed the assumption for most of game theory), and assure that the roles in the game are made public before the game starts, then yes, I feel pretty confident that there's an optimal strategy for each player.

When playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right?

Actually, no. For example, optimal strategy (at least in the sense of game theory) for rock-paper-scissors is to choose randomly every time. Re-doing draws, you'll expect to win 1/2 of the time. And now note that even if you are playing against a complete dimwit who picks his nose and picks rock every time, you still only expect to win 1/2 of the time. Your optimal strategy

guarantees

you the most you can possibly be guaranteed. And often your optimal strategy

limits

you to this as well.

In contrast, you might argue that using psychology you could expect to do better than win 1/2 of the time. There are two fallacies in this thinking: a) You simply

can't

do better than 1/2, even using every psychological trick in the book, if your opponent has decided to play randomly his/herself, and b) If someone knows more of the psychology than you, you risk winning

less

than 1/2 of the time.

I don't know enough about AI to answer your open question, but I'm pretty sure that the problem is not NP-complete...we're just recursively generating probabilities (see my post in optimal doc strategy), which is certainly polynomial time.

Cam

[cuban smoker]

With completely rational players and an known game setup, doesn't there have to be an optimal strategy for each player? It may not be obvious, as in the prisoner's dilemna, but there are just a finite number of base cases to work from (the 3 player examples in the doc thread) and even those there are more base cases than cam originally suggested, going backwards would be "simple" recursion. I agree with mathcam, I think you can O() the problem.

Now, as to your personality question, I don't think anyone here has tried to work in any kind of logic into their simulations past listening to a cop. I haven't heard of any attemps of tracking lynch votes and attempting to use history to weight the probability of anyone voting for anyone else. We all assume that lynches are random (except for some simulations which reduce the chance of lynching mafia by setting mafia to novote other mafia), and that the people are just placeholders in our model.

Extending this to the AI question, you need to analyze games to teach your AI players to play. Just like programming a computer to play chess or poker, I think you need to stick thousands of games into your database to analyze the effect of things like premature claims, refusal to claim, bandwagons, etc. on each player and the eventual outcome of the game. Then your computer will start to understand what are good plays. Next comes trying to tag each of the players in the game with personality traits, so you cansee how that weighs in. A VERY hefty enterprise if you ask me. You'd have to go through our archived games and classify each major game event as something like "claim", etc. and we don't have a lot o plain vanilla games. But if you don't use history, you're not simulating real life mafia. It would be like creating a human robot without analyzing human behaviour. It just couldn't be lifelike.

[gslamm]

How 'bout we approach the problem from a different angle.

Start with defining the game. Have classes [Townie, cop, doc, Mafia, {SK, mason, vigilante, ...}] Let them interact at random recording results. Reward play that results in wins and punish play that results in loss. Run as many simulations as your server can in the time that you allow.

If your strategy weighting fluctuates back and forth there is no optimal play. If your strategy weighting trends in one direction that is the better play. As your number of games increases your cops will start claiming at the optimal time your docs will protect the right person and your mafia will counter claim when it is best for them, whatever is best for them as well as push lynches and night-kill the most opportune target.

Trying to guess what this final weighting will be is obviously non-obvious.

[mathcam]

Now

that

would be a very cool simulation. I'd sure like to hear the results from that.

I think you can O() the problem.

We can get a Buddhist monk to lie down on his side and medidate on the problem?

Cam

[Guest]

This sounds similar to what has been attempted in poker for years. I think that someone can get

good

but not

great

. The AI that we see today just hasn't gotten even close to that level.
That being said, I think that to program AI to get

good

at mafia would be much more difficult than poker. This is simply due to having so many more possibilities to analyze.
Maybe you should assume that there is an optimal strategy and do a cost-surface search using techniques such as neural networks or genetic algorithms. With enough test-cases or generations, respectively, you should be able to get pretty close.

[Caveman]

I'm sorry that was me in the previous post. Thought I was logged in.

[mathcam]

Yeah, but poker's a lot harder. Each unknown person has three possible classifications: cop, mafia, or townie, and not the plethora of possibilities you get for poker hands. Plus, you never get people

bluffing

at being mafia. Everyone is attempting, to some degree, to blend in.

Cam

[Caveman]

I agree that poker is harder. But, where poker has more hand options, it also has only 3 actions that can be taken. Mafia has many more actions available.

Where they become similar is in the human element. This is what is required to be

great

. We're just now getting to where a computer can read a sentence out loud with some success. (Most of them still mispronounce quite a few words). The ability to decipher the meaning of that sentence

and

the underlying subtleties is, IMO, not happening without some major breakthroughs in the field of AI.

That being said, I do think that a

good

mafia strategy is possible. Just not necessarily the

Optimal

Strategy.

[jeep]

There is an optimal strategy, but because no one plays optimally yet, you can usually pick a strategy that has a better win expectation...

I will make my mafia simulator public after I deal with the board issues. It's really quite sophisticated... but it assumes perfect play, i.e. you cannot determine from the posts what people are scum/doc/etc.

I should make JEEPBot to play in games... So many projects I'd like to do.

-JEEP

[Caveman]

A question of terms here, Mathcam: What exactly does 'rational' mean in this case? That the person plays perfectly?

[gslamm]

Jeep,
Your sim sounds like it has a very good strategy built in to it.

What I was getting at was you can start with idiots and teach them the best play by weighting moves that result in wins/losses accordingly.

The best play doesn't have to be known, only the paramaters that need to be considered need be defined: voting, night-kills, protection, investigation, claiming, counter claiming, accusing, defending, vote patterns, ...

[mathcam]

A rational player is one that follows an optimal strategy when one exists.

Cam

[shadyforce]

The choice to reveal information you have is dependant on the odds of success with and without revealing that information, which are fixed so therefore an optimal strategy exists.

The decision to protect someone is dependant on what your opponents are likely to do, which is not fixed so therefore no one optimal strategy exists.

Instead you are faced with a number of choices. Each can be weighted according to high likely they are to work, but there is a lot of speculation and human error involved in that. In the end, you usually make an educated guess based on the likelihood of being correct.

In AI, you should in no way always use the best weighted option as this would allow your opponents to always beat you. You should randomise the choice but taking account of the weighting. It also has to be acknowledged that there is no perfect way to correctly weight the options. How good the AI is, will be dependant on how accurate you can do it, but no perfect solution exists, you can only try and make it as realistic as possible.

[indentureddjinn]

the optimal strategy thing seems totally out of proportion to me. No computer now can accurately simulate the human brain, and therefore the human thought patterns and eventual mental indiscretions may not be able to be taken into account. Sure, I could say "I'm mafia" in a game, but I probably won't be believed because it would be assumed that I'm just kidding, and that ruins the whole point of an optimal strategy, because any aspect of that strategy can be ruled out or not accepted by the masses. Unless you can create a positronic brain (oh yeah Isaac Asimov) then an optimal strategy on a computer would be ery difficult, although not impossible

[mathcam]

You make exactly the point that defeats your argument, ID. The optimal strategy for a player is independent of what the people in the game actually say. It doesn't

matter

whether someone claims to be mafia or not, just as you mention, so a computer doesn't have to take into account all these psychological phenomena.

Cam

[jeep]

mathcam: what is said MUST matter.

When bandwagoned, a doc will usually reveal. Now the town has to decide:
1) do they believe him
2) is it worth the risk of lynching him anyway?

So the fact that someone revealed must be relevant. Just like cop coming out. My program assumes that anti-leptons will be followed (which may skew my results if that is not always the correct play) It does branch to find out probability of town win if:
1) lynch and find cop
2) lynch and find not cop
3) do not lynch and find results accurate
4) do not lynch and anti-lepton's
It then decides if lynching is the correct play.

-JEEP

[indentureddjinn]

Cam, I'm saying that any statement, true or false, will skew the thought pattern of the people so much that the human element must take over and decide on its own whether to believe them or not. Also, an optimal strategy may require a person to say something and either to be believed or not believed, and that can cause discrepancies based on whether or not the person's goal in acheived

[cuban smoker]

But in your situations jeep, you can quantify the risk/reward of each reaction, and thus determine the exact correct play. That makes it possible for the Mafia considering a Lepton to determine exactly when it is to his greatest benefit to initiate the ruse. Unlike in ID's argument, which like cam said, can be completely ignored. The optimal play should have nothing to do with innanities, since every players' optimal speaking strategy will be to say "I'm townie" until it becomes optimal to claim cop.

[jeep]

The goal of mafia is to play and have fun while trying to win. The optimal strategy is probably to never SAY anything. Simply vote and reveal if you are cop (or mafia posing as cop, etc). It's not a very fun way to play. I think it's important to study THAT version of the game to help determine what a balanced game is. I won't play THAT version of the game, though.

-JEEP

[cuban smoker]

Fair enough. I agree completely.

[Ythill]

Optimal strategy is a paradox in any game where people must deduce the true intentions of their opponents to win. It's why WIFOM exists.

[Xylthixlm]

It's not a paradox. It just means that the optimal strategy will be a mixed strategy rather than a pure strategy.

And, of course, you can do better than the "optimal" strategy if your opponent is imperfect. There are computer programs that can beat humans, and less-complex programs, fairly reliably in rock-paper-scissors. One of them was actually called "Iocaine Powder" and used "sicilian reasoning" (i.e. WIFOM, i.e. yomi level 6) to win...

[Xdaamno]

It's not a paradox. It just means that the optimal strategy will be a mixed strategy rather than a pure strategy.

And, of course, you can do better than the "optimal" strategy if your opponent is imperfect. There are computer programs that can beat humans, and less-complex programs, fairly reliably in rock-paper-scissors. One of them was actually called "Iocaine Powder" and used "sicilian reasoning" (i.e. WIFOM, i.e. yomi level 6) to win...

Yep, QFT.

[Yosarian2]

Well, I think you have to be more specific. If you assume the rationality of all players (which is indeed the assumption for most of game theory), and assure that the roles in the game are made public before the game starts, then yes, I feel pretty confident that there's an optimal strategy for each player.

When playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right?

Actually, no. For example, optimal strategy (at least in the sense of game theory) for rock-paper-scissors is to choose randomly every time. Re-doing draws, you'll expect to win 1/2 of the time. And now note that even if you are playing against a complete dimwit who picks his nose and picks rock every time, you still only expect to win 1/2 of the time. Your optimal strategy

guarantees

you the most you can possibly be guaranteed. And often your optimal strategy

limits

you to this as well.

Actually, no, choosing randomally is not the optimal stratagy in RPS. The optimal stratagy is to sucessfully outguess or out-read your opponent. If either you or your opponent chooses randomally, you win 1/2 the time; the only way to do better then a 50/50 win ratio is to outplay opponents who do not act randomally by not acting randomally yourself. Some people are able to do this, though; they have regular rock-paper-scissors tourniments, and some players do manage to consistantly do better then a 50% win ratio.

Back to the origional question...there is such a thing as optimal stratagy in mafia, I think, at least in a fuzzy sense (that is, it is likely there are many situations in a mafia game where there are multiple options, probably a large number of different options, that offer about equal chances of winning, and the margins of error involved are often fairly large).

However, what the optimal stratagy is depends very strongly on how well you know and can read the other players in the game, and predict how they will act in different situations.

Also, since mafia is kind of a team sport, in a way, I think that your optimal townie stratagy varies based on what the other pro-town people are doing; in basketball, for example, shooting 3 point shots can be a valid stratagy, but you don't really want a team that does nothing but shoot 3 point shots. So, in the same way, I think that there's a number of different "roles" that a townie can assume (agressive/analytical/defensive; emotional/logical/reasonable; loud/quiet; leader/follower, debator/table pounder/compromiser, ect), and that which role you should assume at any point of a game might depend on which roles the other people in the game are taking; a town where everyone is using the exact same method of finding scum isn't as likely to find all the scum, in my opinion, as a town where people are using more diverse stratagies.

Similarly, the optimal town stratagy and the optimal scum stratagy are often very close together; there are usually subtle differences, but generally it's within the margin of "fuzzyness" I mentioned earlier, ideally to the point where an outside observer can't easily tell the difference between what you are doing as scum and what you would be doing as town; a lot of mafia is a mental struggle between scum trying to slightly fudge the margins there a little and town trying to spot the very subtle difference between the two optimal playstyles. There are exceptions, though, points of a game where optimal town stratagy and optimal scum stratagy diverge widely (for example, 5 hours before deadline where there's one bandwagon on a claimed cop who really is a cop and one on your scumbuddy), and those are excellent points to go back and look at later when scumhunting.

Of course, in reality, the differences between town and scum will tend to be larger then they would be in optimal play, just because most people have only a limited understanding of exactally how they would play a situation as town, and because of different psycological tells and slips people tend to make, especally under pressure.