To what extent do optimal strategies exist?
-
-
Telamon Watcher
- Watcher
- Watcher
- Posts: 0
- Joined: March 25, 2004
To what extent do optimal strategies exist?
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.Let be be finale of seem, seems to me.
[url=http://www.stanford.edu/~jjshed/blog]Blog: Shedletsky's Bits[/url]-
-
mathcam Captain Observant
- Captain Observant
- Captain Observant
- Posts: 6116
- Joined: November 22, 2002
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.
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 strategyWhen playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right?guaranteesyou the most you can possibly be guaranteed. And often your optimal strategylimitsyou 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 simplycan'tdo 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 winninglessthan 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 An Acquired Taste
- An Acquired Taste
- An Acquired Taste
- Posts: 493
- Joined: August 19, 2002
- Location: Kitchener, Ontario
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 Goon
- Goon
- Goon
- Posts: 265
- Joined: July 14, 2003
- Location: NW AR, USA
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.[size=84]"Hmm, wow.. I'll just sit back and watch the stupidity continue to unfold.. "- genku Mixed Theme [/size]-
-
mathcam Captain Observant
- Captain Observant
- Captain Observant
- Posts: 6116
- Joined: November 22, 2002
-
-
Guest This sounds similar to what has been attempted in poker for years. I think that someone can getgoodbut notgreat. 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 getgoodat 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 Goon
- Goon
- Goon
- Posts: 231
- Joined: January 5, 2004
- Location: Austin, TX
-
-
mathcam Captain Observant
- Captain Observant
- Captain Observant
- Posts: 6116
- Joined: November 22, 2002
-
-
Caveman Goon
- Goon
- Goon
- Posts: 231
- Joined: January 5, 2004
- Location: Austin, TX
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 begreat. 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 sentenceandthe underlying subtleties is, IMO, not happening without some major breakthroughs in the field of AI.
That being said, I do think that agoodmafia strategy is possible. Just not necessarily theOptimalStrategy.Time flies when you're lynching scum.-
-
jeep Cappo Bastone
- Cappo Bastone
- Cappo Bastone
- Posts: 747
- Joined: April 21, 2002
- Location: Portland, OR
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 Goon
- Goon
- Goon
- Posts: 231
- Joined: January 5, 2004
- Location: Austin, TX
-
-
gslamm Goon
- Goon
- Goon
- Posts: 265
- Joined: July 14, 2003
- Location: NW AR, USA
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, ...[size=84]"Hmm, wow.. I'll just sit back and watch the stupidity continue to unfold.. "- genku Mixed Theme [/size]-
-
mathcam Captain Observant
- Captain Observant
- Captain Observant
- Posts: 6116
- Joined: November 22, 2002
-
-
shadyforce U-S-E_T-H-E_F-O-R-C-E
- U-S-E_T-H-E_F-O-R-C-E
- U-S-E_T-H-E_F-O-R-C-E
- Posts: 951
- Joined: August 21, 2003
- Location: Dublin
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.[size=75][color=darkblue]I'm never wrong... well I was wrong once but that was when I thought I'd made a mistake but hadn't.[/color][/size]-
-
indentureddjinn Goon
- Goon
- Goon
- Posts: 478
- Joined: August 23, 2003
- Location: California, USA
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"na hanyate hanyamane sarire"
-Chapter 2, verse 20 Bhagavada Gita
http://img295.imageshack.us/img295/2469/irvington9zs.jpg-
-
mathcam Captain Observant
- Captain Observant
- Captain Observant
- Posts: 6116
- Joined: November 22, 2002
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'tmatterwhether 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 Cappo Bastone
- Cappo Bastone
- Cappo Bastone
- Posts: 747
- Joined: April 21, 2002
- Location: Portland, OR
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 Goon
- Goon
- Goon
- Posts: 478
- Joined: August 23, 2003
- Location: California, USA
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"na hanyate hanyamane sarire"
-Chapter 2, verse 20 Bhagavada Gita
http://img295.imageshack.us/img295/2469/irvington9zs.jpg-
-
cuban smoker An Acquired Taste
- An Acquired Taste
- An Acquired Taste
- Posts: 493
- Joined: August 19, 2002
- Location: Kitchener, Ontario
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 Cappo Bastone
- Cappo Bastone
- Cappo Bastone
- Posts: 747
- Joined: April 21, 2002
- Location: Portland, OR
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 An Acquired Taste
- An Acquired Taste
- An Acquired Taste
- Posts: 493
- Joined: August 19, 2002
- Location: Kitchener, Ontario
-
-
Ythill Fabio
- Fabio
- Fabio
- Posts: 4892
- Joined: November 10, 2007
-
-
Xylthixlm !xmafia win
- !xmafia win
- !xmafia win
- Posts: 5414
- Joined: July 12, 2006
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...#mafia@irc.globalgamers.net
"Xyl was completely berserk" -dramonic
"Xyl's ruthless policy lynching won the game." -Vi-
-
Xdaamno I love you
- I love you
- I love you
- Posts: 3354
- Joined: April 10, 2007
- Location: 0, 0, 0
Yep, QFT.Xylthixlm wrote: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..."This should be an absolute car crash, but let's try it." - CDB
"did you get ces to look disgusted by their offer? i thought that might work" - Patrick
Cracking Idea Mafia-
-
Yosarian2 (shrug)
- (shrug)
- (shrug)
- Posts: 16394
- Joined: March 28, 2005
- Location: New Jersey
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.mathcam wrote: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.
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 strategyWhen playing against an irrational enemy with an optimal strategy, you should expect to win more than if they were being 100% rational. Right?guaranteesyou the most you can possibly be guaranteed. And often your optimal strategylimitsyou to this as well.
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.I want us to win just for Yos' inevitable rant alone. -CrashTextDummie
Copyright © MafiaScum. All rights reserved.