A more rigorous analysis

[DoomYoshi]

Basically, I am going to analyze the Pokemon game quite well to ensure that it is close to balance.

Option 1 is to do everything randomly. I mean, predict that day 1s lynch is random night 1s actions are random etc.

However, mafia actions aren't random. The doctor isn't likely to protect His most likely scumster for instance. Does anyone know of an existing formula to figure out town win %?
If it came complete with SAS code, I would appreciate it. If not, I will use random ish actions.

Rule 1: mafia does not target mafia (not always true, but true often enough)
Rule 2: town does not lynch cop/doctor
Rule 3: vig doesn't kill night 1 or night 2
Rule 4: chance of mafia(scum) lynch increases every day
Rule 5: if one player targets another, then subsequent players are more likely to target that player

Then I will run a sim and see if it is roughly balanced. Any other simple rules you think I should add?

[safariguy5]

Basically, I am going to analyze the Pokemon game quite well to ensure that it is close to balance.

Option 1 is to do everything randomly. I mean, predict that day 1s lynch is random night 1s actions are random etc.

However, mafia actions aren't random. The doctor isn't likely to protect His most likely scumster for instance. Does anyone know of an existing formula to figure out town win %?
If it came complete with SAS code, I would appreciate it. If not, I will use random ish actions.

Rule 1: mafia does not target mafia (not always true, but true often enough)
Rule 2: town does not lynch cop/doctor
Rule 3: vig doesn't kill night 1 or night 2
Rule 4: chance of mafia(scum) lynch increases every day
Rule 5: if one player targets another, then subsequent players are more likely to target that player

Then I will run a sim and see if it is roughly balanced. Any other simple rules you think I should add?

This is difficult to quantify because a lot of how the actions will play out depend upon the players and game situations.

Let's imagine that Day 1, someone claims Pikachu and another person counterclaims Pikachu. Person number 1 is lynched, and turns up town. Logically, the town vig would kill Person number 2 on Night 1, which would invalidate Rule 3. And if we assume that the vigged player is mafia, then Rule 4 is also violated, because town has lost proportionally less players than mafia has (1 townie dead vs 1 mafia dead).

I believe we could quantify it, but there's not one equation that would satisfy all possible permutations of game outcome, you'd have to be constantly tweaking the variables as the game progresses to reflect changing dynamics.

[DoomYoshi]

So now would you suggest balancing a complex game? I have already done the looking at "comparative role worth" analysis. Is that the best there can be?

Also, the assumption doesn't have to be justified in all cases. As long as it usually works, it should resulting decent predictions. The way ms does most analyses is by looking at past game data. The problem there is that a lot of the games are much simpler and open setups are common.

[pmchugh]

I think it is worth a try. All models of reality are not going to be completely accurate but by making educated guesses you can make useful predictions. Also it allows you to see some potential gaps in the balance.

Also I think you could make two categories of roles, repeated and non. For instance a cop would not repeat his target where as a doctor is quite likely to repeat his targets because of claimed players.

[DoomYoshi]

I think it is worth a try. All models of reality are not going to be completely accurate but by making educated guesses you can make useful predictions. Also it allows you to see some potential gaps in the balance.

Also I think you could make two categories of roles, repeated and non. For instance a cop would not repeat his target where as a doctor is quite likely to repeat his targets because of claimed players.

Good catch there!

[DoomYoshi]

Actually, this is WAAY too hard to code.

[pmchugh]

Hey I found this:

http://wiki.mafiascum.net/index.php?title=Numbers,_Part_2
http://wiki.mafiascum.net/index.php?title=Numbers,_Part_3

Although to be honest that is not really applicable to the complexity of a NV game with 18 players.

I think I could make something in OOP that would give a less accurate but more useful outcome than this. If only I wasn't already wasting my time posting in mafia rather than doing my imminently due project code and dissertation lol.

[jorgea]

I think that by looking at past games one can make very good guesses of what possible outcomes might roll out.

[pmchugh]

I started doing this, but don't ever bet on me finishing it

[Haggis_McMutton]

I started doing this, but don't ever bet on me finishing it

Can you explain how exactly you're modelling this?

I've actually thought about doing this before, it might be an interesting project.

[pmchugh]

I started doing this, but don't ever bet on me finishing it

Can you explain how exactly you're modelling this?

I've actually thought about doing this before, it might be an interesting project.

I am doing it in OO and I have a series of "GamePath"s. One to start with and one caused by every death (the complication is in multiple kill night scenes). If a faction meets its win condition then the probability of the winning faction is increased by the probability of that game path occurring. All other actions are merely used to affect the probability of someone being killed, or to affect the probabilities of another action. For instance if the doctor has a 0.25 chance of protecting player A and the mafia has a 0.25 chance of killing player A in one night then two new game paths are created:

Game Path 1:
Outcome: No Kill
Probability: 0.25*0.25 = 0.125

Game Path 2:
Outcome: Player A dies
Probability: 0.25 * (1-0.25) = 0.1875

I haven't thought it all through yet and it gets insanely complicated when you try to think of busdrivers and some other scenarios but I think in the very least C9 games could be modeled.

[edocsil]

God i am tempted to make a c9 version in matlab

[shieldgenerator7]

I had a thought to make a computer model that could "play" all the roles of the game. It would go through all the days and randomyl select different players to target and to lynch, with exceptions (i.e. if cop found scum that scum would be lynched next day). Then the outcome would be the combination of the paths chosen (however many billions of them there are). ANd then the computer would run the test again with same setup and then after many iterations it would show the average amount of town wins and mafia wins and whatever faction you had.

[pmchugh]

matlab

I had a thought to make a computer model that could "play" all the roles of the game. It would go through all the days and randomyl select different players to target and to lynch, with exceptions (i.e. if cop found scum that scum would be lynched next day). Then the outcome would be the combination of the paths chosen (however many billions of them there are). ANd then the computer would run the test again with same setup and then after many iterations it would show the average amount of town wins and mafia wins and whatever faction you had.

So a kind of trial and error type thing then, thats easier to understand but probably not as accurate. It would be fun (in the geekiest way possible) to try use an evolutionary algorithm to perfect setups but I think that is going too far

[Rodion]

matlab

I had a thought to make a computer model that could "play" all the roles of the game. It would go through all the days and randomyl select different players to target and to lynch, with exceptions (i.e. if cop found scum that scum would be lynched next day). Then the outcome would be the combination of the paths chosen (however many billions of them there are). ANd then the computer would run the test again with same setup and then after many iterations it would show the average amount of town wins and mafia wins and whatever faction you had.

So a kind of trial and error type thing then, thats easier to understand but probably not as accurate. It would be fun (in the geekiest way possible) to try use an evolutionary algorithm to perfect setups but I think that is going too far

I have the feeling the mafiascum forum has probably discussed things like this already and you could get a nice boost to your project by checking what they have already accomplished.

[DoomYoshi]

matlab

I had a thought to make a computer model that could "play" all the roles of the game. It would go through all the days and randomyl select different players to target and to lynch, with exceptions (i.e. if cop found scum that scum would be lynched next day). Then the outcome would be the combination of the paths chosen (however many billions of them there are). ANd then the computer would run the test again with same setup and then after many iterations it would show the average amount of town wins and mafia wins and whatever faction you had.

So a kind of trial and error type thing then, thats easier to understand but probably not as accurate. It would be fun (in the geekiest way possible) to try use an evolutionary algorithm to perfect setups but I think that is going too far

Well in theory, if you know the code which plays the roles, you would have a possible outcome probability chart unless a game is not easily solveable. Simpler games could be equation-based, but more complex games would need the trial/error system. Unfortunately, the ones that you can get a nice clean equation-based output from would also be the ones that are already easiest to balance.

[Haggis_McMutton]

@ the game paths. If I didn't misunderstand you are talking about something like Minimax tree, keeping track of the probabilities on each branch. I think this is the best option for simple setups but I'm not sure it'll work on bigger/weirder ones. As I see it, there's 2 problems:

1. Deciding on the probabilities for non-trivial decisions. How is the roleblocker blocking the killer represented? How about the busdriver driving the victim? How do you probabilistically represent the info those actions give them?
2. Sheer computational limit. Let's take a 20 man NV game and let's say there's a mafia, SK, doctor, busdriver(so basically anyone can get killed or saved). There are 1(no one dies) + 20(one person dies) + 190(2 people die) = 211 paths for N1. Let's say the average throughout the game will be a quarter of this, a branching factor of 50 every night. If the game has 7 nights, that would put the total number of paths at 50^7 = 780 billion.

The trial and error approach seems more feasible to me too (at least if you want arbitrarily complex roles & big games). Technically I guess it would be MCMC.

However, the question is how much do you "correct" the randomness based on our knowledge of the game.
Can mafia randomly kill itself? How does the cop finding mafia affect the lynch next day? etc etc.
One option would be to make it completely random on the assumption that the dumbness of both mafia and town evens out. But that essentially makes investigative roles useless, so maybe not.

What would be REALLY cool is if we had a database of setups and outcome, that way we could evaluate (and maybe even train) any algorithms we come up with.

Goddamnit, now I'm really getting into this idea and I really don't have time for another project right now.

[Rodion]

I think you can only do this to balance closed setups (role distribution is laid out before game starts) as you can't estimate probability of town lynches in a game whose roles are not clear.

For instance, mafia busdriver swaps two people and cop gets a guilty result on a VT. VT is lynched.
Those things could happen the next day:
a) cop claim disbelieved, cop lynched
b) cop claim believed, existence of mafia busdriver assumed
c) cop claim believed but town treats him as insane, thus they treat his following result the opposite way
d) cop claim believed but town treats him as paranoid, thus his results are outright ignored

If you can't accurately stipulate how likely town is to treat each of the mentioned outcomes, then you can't do the minimax tree.

[Haggis_McMutton]

I think you can only do this to balance closed setups (role distribution is laid out before game starts) as you can't estimate probability of town lynches in a game whose roles are not clear.

For instance, mafia busdriver swaps two people and cop gets a guilty result on a VT. VT is lynched.
Those things could happen the next day:
a) cop claim disbelieved, cop lynched
b) cop claim believed, existence of mafia busdriver assumed
c) cop claim believed but town treats him as insane, thus they treat his following result the opposite way
d) cop claim believed but town treats him as paranoid, thus his results are outright ignored

If you can't accurately stipulate how likely town is to treat each of the mentioned outcomes, then you can't do the minimax tree.

Good point. That does seem to be another limitation.

Hmm, maybe a good starting point would be to implement the tree approach on simple closed setups, where it works well. Then implement the completely random MCMC version and compare results on those same simple set-ups.

[safariguy5]

There has to be some way to differentiate open vs. closed setups. If we're talking about a an open setup like C9, a cop claim and an guilty result would probably weight more heavily towards getting a mafia lynch. A closed setup with nobody really knowing the setup may weight the guilty investigation less.

Another possible variable to consider is assumptions with regards to time. I'm not a Comp Sci major, but in engineering, we're always making assumptions about fluid flow steady state. If we're modeling an online, forum based mafia game, then we either must assume that posts by the players (and therefore possible votes) are steady state, or they are some unsteady semi-random frequency. This might be important if we're going to consider possible time constraints imposed by deadlines. Because there's a theoretical possibility that between two equally likely possibilities, the decision will never be made and the problem would stall towards infinity in the absence of time constraints.

[pmchugh]

@ the game paths. If I didn't misunderstand you are talking about something like Minimax tree, keeping track of the probabilities on each branch. I think this is the best option for simple setups but I'm not sure it'll work on bigger/weirder ones. As I see it, there's 2 problems:

1. Deciding on the probabilities for non-trivial decisions. How is the roleblocker blocking the killer represented? How about the busdriver driving the victim? How do you probabilistically represent the info those actions give them?
2. Sheer computational limit. Let's take a 20 man NV game and let's say there's a mafia, SK, doctor, busdriver(so basically anyone can get killed or saved). There are 1(no one dies) + 20(one person dies) + 190(2 people die) = 211 paths for N1. Let's say the average throughout the game will be a quarter of this, a branching factor of 50 every night. If the game has 7 nights, that would put the total number of paths at 50^7 = 780 billion.

The trial and error approach seems more feasible to me too (at least if you want arbitrarily complex roles & big games). Technically I guess it would be MCMC.

However, the question is how much do you "correct" the randomness based on our knowledge of the game.
Can mafia randomly kill itself? How does the cop finding mafia affect the lynch next day? etc etc.
One option would be to make it completely random on the assumption that the dumbness of both mafia and town evens out. But that essentially makes investigative roles useless, so maybe not.

What would be REALLY cool is if we had a database of setups and outcome, that way we could evaluate (and maybe even train) any algorithms we come up with.

Goddamnit, now I'm really getting into this idea and I really don't have time for another project right now.

I wouldn't call it a minimax tree, it is a tree structure but it has nothing to do with finding the best course of action or minimising your loss.

The hardest thing about these probabilities is the order of operations. Roleblocker is complicated because it has multiple uses, it has kill stopping potential so must create a new path but it can also effect the odds of all other actions. Busdriver blows my mind. Personally the only way I would implement it would be to add a chance for factions to kill themselves.

Cop finding mafia is a lot easier, basically every night the cop is alive the odds of mafia being lynched increase and the odds of town being lynched decrease.

For example:

If the odds of a scum member being lynched are normally 20% and the odds of being investigated are 25% then the odds of being lynched the next day would be:

0.2 + (Weighting * 0.25)

The waiting could be set at say 70-90% as I reckon thats roughly the chance of being lynched if guiltied by cop.

You have identified the biggest issue with my approach though- time complexity.