[OLD] The Numbers Thread

[Tenchi]

Simulation is fine... the main issue is that it's difficult to know which strategy is optimal in certain situations, and in order to run a simulation you either need to decide beforehand how it will treat those situations (so you are just guessing what is optimal, and may not be finding the true EV... and in some cases, a non-obvious strategy may drastically shift the balance of the game), or you need to brute force it and try all the different possible strategies (at which point, might as well find an exact solution, IMO).

Yeah. I noticed it that in my simulation, I had to assume a no-lynch in an even number of townies in a lylo situation.

You don't need brute force - you can code an evolutionary sim, where you give each strategy a probability of occuring. Let those probabilities "mutate" over time, changing randomly in either direction, and eventually an equilibrium will be reached.

I don't know the cost of making and maintaining an evolutionary simulation (genetic algorithm). From what I understand, I run this genetic algorithm and find the optimal solution for town, and use that to calculate the probability of town winning.

I'm not a top programmer so I'm wary on taking this approach.

(If Mith or anyone can give me the derivation of the formula in the vanilla spreadsheet that would be awesome. I've reviewed my basic statistics but I'm a bit stumped. :\ Thanks.)

[Tenchi]

Simulation is fine... the main issue is that it's difficult to know which strategy is optimal in certain situations, and in order to run a simulation you either need to decide beforehand how it will treat those situations (so you are just guessing what is optimal, and may not be finding the true EV... and in some cases, a non-obvious strategy may drastically shift the balance of the game), or you need to brute force it and try all the different possible strategies (at which point, might as well find an exact solution, IMO).

Yeah. I noticed it that in my simulation, I had to assume a no-lynch in an even number of townies in a lylo situation. (Supposedly gives Town more information and a higher chance of hitting scum in final lynch)

Er... doing this lowered the EV. Did I do something wrong?

Edit: If I don't apply the strategy however, it becomes worse (er... obviously). Just increasing the number of townies to an even number makes the EV go lower.

All these were done in a simulation.

[Adel]

suppose there are three townies and one scum. Random lynch will result in 25% town win at that point. NL -> random NK -> 33% chance of town win on the next day. You might be NL whenever there is a random number of townies to ge the lower EV.
That is for vanilla. If you are doing it with the vamp role, then assuming that you have 2 townies, 1 vamp (town aligned), and 1 scum, random lynch yields 25% town win, NL should be 2/9= ~22% town win.

[mith]

No idea what the "Vamp" role is, but if it's something that can be claimed, the random lynch EV is bumped to 33% (or 50%, if scum are stupid and counter).

(An example of the difficulties of simulation - either you need to anticipate all such situations where the town might have a strategy beyond "lynch someone at random or don't lynch at all", or you need to include branches for various claims and so forth.)

Tenchi, the formula in the vanilla spreadsheet is basically:

EV[M:T] = MAX[EV[M:T-1]; M/(M+T) * EV[M-1:T-1] + T/(M+T) * EV[M:T-2]]

In plain english: The EV given M Mafia and T Townies is the maximum of two probabilities. The first is the EV given M Mafia and T-1 Townies (no lynch, followed by a nightkill). The second is EV after lynching a random player, followed by a nighkill, which is the sum of (the EV after lynching scum + nightkill times the probability of that happening) and (the EV after lynching town + nightkill times the probability of that happening).

It's recursive, so you need boundary conditions (if M is 0, EV = 1; if M >= T, EV = 0).

[mith]

Alright, bumping this to remind myself that I want to play with this stuff again.

After glancing at the Open discussion thread, I want to look at a vanilla+masonpair setup. And then get back to California again. The mason setup ought to be simpler, and hopefully figuring out how claims might work there will give some insight on the more complicated Cop-claim mess.

[mith]

Actually, perhaps I should start with a "NamedTownie" variation first - one innocent has a non-vanilla role which can be claimed (but doesn't have any other ability). The Mason setup reduces to this if a Mason is NKed before a claim happens, anyway.

Two possible starting point strategies for the Mason game (while both are still alive):

1. Town should always force a full Mason claim. This takes away the Mason claim from the scum (if they claim a player as their partner who is innocent, that innocent just denies it and the scum gets lynched without revealing any info on the Masons; if they claim their scum partner, the real Mason pair comes out and that's a win unless it's lylo, and a 50-50 even then).

2. Town shouldn't force a full claim. This improves the power of the role slightly, and it may be that scum still can't claim effectively (since one of the Masons can just counter). Would have to check for a Nash equilibrium to determine that, though.

[mith]

Ok, I've got NamedTownie done for 1 scum, and I think this is the first example of a situation where adding a townie hurts the town.

1 Mafia, 1 Townie, 1 NamedTownie = 50%
1 Mafia, 2 Townies, 1 NamedTownie = 44.4~%

1 Mafia, 3 Townies, 1 NamedTownie = 56.6~%
1 Mafia, 4 Townies, 1 NamedTownie = 56.2~%

For 1:2:1, obviously NoLynch is still correct, but you might lose your NT and go to 1:2 rather than 1:1:1. For 1:4:1, NoLynch is no longer correct, since you want to make use of the NT's presence during the day as much as possible - a bit counterintuitive, though. With more townies, the probabilities strictly increase.

I think for multiple scum we can safely assume that the first scum to be a lynch target will claim and be countered, but I don't know if we can assume scum will never counter an NT claim. Should be easy enough to check what happens if they do counter (assuming they do so with a small probability, town will always lynch the first claim, since it that player is more likely to be scum, so for M:T-1:1 we're looking at either M-1:T-3 or M:T-1 with a lost nightkill on the NT; the latter is almost certainly better for scum if there are lots of townies alive, but maybe not close to lylo).

[mith]

Looks like with 2 Mafia, NoLynch is always correct for even numbers (and thus adding a townie to go from odd to even is always bad for the town... which is unfortunate, because I rather like the idea of an even-numbered setup where the correct play is to lynch until the NT dies or it reaches lylo).

The value of the NT is pretty small - 2:9:1 vs. 2:10 gains the town about 2%.

[mith]

A further variant on this would be what I'm going to call "Census". The setup is:

X Mafia
Y Townie Type 1
Z Townie Type 2

where Y and Z are known at the start of the game. Correct strategy for Y and Z approximately equal is likely to mass claim at the beginning of the game, forcing the scum into one of the two types, and turning the game into two subgames. NamedTownie is the case where Z=1 - but note that it's not correct play to mass claim at the beginning there, since the NamedTownie becomes more valuable the longer he survives.

(I feel like this sort of setup has been discussed before somewhere, but I don't remember where or when.)

[Max]

I remember it vaguely also.

Though of course the set-ups could get more complex with more types of townies. 3 types is possible, then so is 4. Any number is feasible just mafia would have to be at least number of groups minus one for it to be fair.

Though minus two is fair also.

[jammer]

I think with a even Y and Z. If the scum is a even number, it won't matter very much. If towny gets lynched kill one of the other side. If scum gets lynched kill whatever he claimed. Ofc. town will've higher odds, because one group will often have higher odds of lynching.

If you want to have a EV, it's easier to make a simple simulator and let it run, then you know what is balanced.

I've made a (simple) simulator for cop/doc/mafias before and that seems far more complex then this.

[Fishythefish]

A further variant on this would be what I'm going to call "Census". The setup is:

X Mafia
Y Townie Type 1
Z Townie Type 2

where Y and Z are known at the start of the game. Correct strategy for Y and Z approximately equal is likely to mass claim at the beginning of the game, forcing the scum into one of the two types, and turning the game into two subgames. NamedTownie is the case where Z=1 - but note that it's not correct play to mass claim at the beginning there, since the NamedTownie becomes more valuable the longer he survives.

(I feel like this sort of setup has been discussed before somewhere, but I don't remember where or when.)

Assuming massclaim is right (and it looks right for big Y, Z), I've already got a program which works out the answers for this. I'll get the answers in some useable form tomorrow. I'll also investigate when massclaim is right.

[Fishythefish]

I've got the Census Mafia answers in an excel file (is there a sensible way to get it so others can see it?). The most striking thing is that the mafia have two strategies for claiming that they should use almost all the time; if the groups are fairly equal in size they should split up evenly, and if not they all claim in the larger group. It's very rare indeed that 4 mafia should claim 3-1.

Town shouldn't massclaim nearly as much as you would guess. Generally they should wait until near the end, when the innos they get from claiming are more valuable. Eg. with 12 players the town should only claim in 2-5-5.

Balanced setups with X=Y (in brackets balanced for vanilla):
1-1-1 (5)
2-5-5 (18)
3-10-10 (41)
4-19-19 (70)
5-27-27 (110)
6-39-39 (155)
7-52-52 (209)
8-67-67 (272)
9-84-84 (343)
It would appear you need roughly half as many townies to balance the game.

It should be noted that I assumed that claiming your group wouldn't derail a lynch if the town hasn't massclaimed. It gets ludicrously complicated if you have to start thinking about keeping track of the claims - I won't be able to fix this. I'd say this assumption should be fine except when X or Y is very small, but it will certainly screw up the numbers for Named Townie a bit. I will sort Named Townie out under the assumptions that the first scum to get wagoned claims NT, and that if a NT claim gets cc'd, the town lynchs the first claimant.

I've got some ideas for modifying my program to deal with simplish and largely non-interacting PRs. Are there any (very simple) setups that anybody would like to see numbers for?

[Fishythefish]

Thoughts on California:

1. Cop counterclaiming is almost certainly wrong. Off the top of my head, when not near lylo, the strategy of "let cop claims live one day, then lynch em if they are still alive" is going to beat the strategy of cops counterclaiming (I'm betting the mafia still kill claimed cops at night, for fear of cop hitting mafia).
2. It's very possible there are going to be crazy claiming/counterclaiming weirdnesses going on.

3. I think I should be able to get it working, though I may need some plausible looking assumptions to get rid of the worst of 2. It's going to be much harder than Census though.

3. Any setup with any kind of information role that can be fakeclaimed and counterclaimed is going to need some clever ideas I haven't thought of to get any right answers out. At some point I might code up some basic strategies for the town (no lynch, cop claims at some point / lynch, cop ccs scum / lynch, don't lynch cop claims unless they survive the night).

[mith]

It's very rare indeed that 4 mafia should claim 3-1.

Can you post some examples of this? My intuition would have been that the scum should claim so as to make the proportion of scum in each group as equal as possible.

Re: California, the potential for fake claims definitely makes any analytical treatment difficult - but I don't doubt that it's doable, it's just messy (and I would hope that solving California would shed some insight on how to go about solving the more general case). I think simulations with some reasonable strategies should give a starting point (and then you can add more strategies to try to improve the result on either side).

[Fishythefish]

I was also surprised by that result

Here is a full list of X,Y<100 when 4 scum should (or may as well) claim 3-1:

2-3-4 (2-2 just as good)
3-3-4 (2-2 just as good)
4-1-4 (4-0 just as good)
4-2-4 (4-0 just as good)
11-8-4
12-9-4

Annoyingly, these first 4 are pretty much exactly the cases I might have some hope of doing by hand. I really don't know what actually going on here.

[Herodotus]

2-3-4 (2-2 just as good)
3-3-4 (2-2 just as good)
4-1-4 (4-0 just as good)
4-2-4 (4-0 just as good)

All are LYLO or MYLO.
In 2-3-4, the 2-2 claim leads to a .5 chance lynching from the smaller group, while the 1-3 claim leads to a .5 chance lynching from the larger group. Either way, the number of townies and mafia in each group are the same at the end of a successful day 1 (2-3 town and 1-2 mafia.)
3-3-4 should probably start with a nolynch, which puts us down to 2-3-4.
4-1-4 gives a .5 chance of a correct lynch on D1, regardless of whether scum go 3-1 or 4-0, and leaves a confirmed townie in the "1" category if scum is lynched. The conf-town is killed N1, and the game continues as 4-3 mountainous.
4-2-4 should probably start with a nolynch. If the scum kill from the 4, we're in 3-2-4 = 2-3-4. If the scum kill from the 2, we're in 4-1-4.

That explains those cases. I don't know about the other cases, or more importantly, why those six are the only exceptions. But maybe the above proof will help?

[Fishythefish]

So, I fixed one town at 20 and the mafia at 4, and ran the other town from 0 to 100. I graphed the EVs arising from the 5 possible mafia claim strategies. There appears to be a point where it hardly matters at all what they claim, as long as they claim at least as many in T1 as T2, and a corresponding point where they must claim at least as many in T2 as T1. Repeating this for different values of "20" and different even values of "4", this is still very nearly true. If the split is more extreme than this, 4-0 is right, and if it's less extreme, 2-2 is right.

@Hero: thanks, that's good stuff.

[mith]

I thought I posted here last night. Guess I got distracted before I pressed submit.

Not that I didn't trust your numbers, but I got Census into my spreadsheet and our numbers agree. I'll format it nicely and reupload the spreadsheet at some point. (Or you could email me what you've got and I could use it, as it's probably more elegant than the mess I made. )

I think the 3-1 split is so rare because of the nonlinear effect of the two underlying factors controlling whether 4-0 is best. First, the strength of the Mafia group is quadratic with size (for vanilla games, but also for games with confirmed townies). Second, the strength of confirmed townies (in the case where the Mafia goes with a 4-0 split) is pretty small until we get close to X=Y (and it climbs rapidly to hit an EV of 1 wherever the confirmed group is a majority, though obviously once we're past X=Y we'd be looking at a 0-4 split, not 4-0). So, when the X/Y split is uneven, the benefit gained by having an extra member in the bigger group is more significant than that gained by having a member in the small group and keeping that group unconfirmed - the confirmed townies aren't that strong anyway, and early on the Mafia will have to take out townies in the smaller group anyway, until the ratios are more even. Because of the nonlinear trends, the breakeven point between 4-0 and 3-1 isn't when the ratio X:Y is closer to 3:1, but rather when it's closest to 2:2 (or nearly there, anyway), at which point 2-2 has already overtaken 3-1 in most cases.

[mith]

The divide between 3-1 and 2-2 looks a bit more like I might have expected (though not at the ratio I would have expected). The boundary stays around a ratio of 0.57-0.58 for most of the range I'm looking at (up to X=Y=25). That said, I wouldn't be surprised if the boundary stays essentially linear plotted as X vs. Y, rather than staying roughly constant by ratio.

The boundary between 3-1 and 4-0 on the other hand essentially remains parallel to the X=Y line, only stepping over at 11-8.

So as far as why 11-8 and 12-9 are the only setups where 3-1 is the best split for the scum, it's because step in the 3-1 vs. 4-0 boundary happens to coincide with a step in the 2-2 vs. 3-1 boundary. The boundaries are adjacent for low X-Y, and diverge for large X-Y, but the jump in the former trendline is enough to make them overlap briefly.

[Max]

Numbers I'm most interested in are those for twofold/(EDIT)multi mafia games.

[mith]

Alright, back to California...

From the NamedTownie variant, we have a lower bound - if the Cop has no actual investigation (or doesn't use it, or is known to be Naive/Paranoid, etc.), the EV is 163/630 (~25.87%).

For an upper bound, consider the case where the scum can't fake claim or counterclaim the Cop at all (even in an endgame). Now the problem is simply one of figuring out when the Cop should claim and reveal his results. For a larger game, this might actually be a tricky question (though I don't doubt we could throw together a recursive spreadsheet or a program to solve it). However, for this setup, it turns out that the Cop should almost never claim until it's down to three, unless he is the lynch target.

If the (randomly selected) lynch target is the Cop, the Cop claims. Pick a different lynch target, Cop will be nightkilled, game becomes vanilla.

If a scum is lynched Day 1, obviously the Cop should reveal if he gets a guilty after that. If he gets an innocent Night 1, however, he should stay hidden - revealing gives an EV of 2/3, but if instead we select a lynch target at random with the Cop only claiming if the chosen lynch target is the Cop or the investigation choice, the EV jumps to 7/9 (because either the scum is the lynch target, or if an innocent is lynched there is still a good chance the Cop will survive and win the game). In fact, it doesn't matter whether the Cop steps in to save the investigated innocent if that player is chosen as the lynch target (2/3 either way).

If a townie is lynched Day 1, the Cop should follow a similar plan with an innocent investigation - protect himself or the confirmed innocent, but otherwise stay hidden. The benefits of staying hidden to endgame outweigh the risk of getting killed before confirming the single investigation.

The less obvious case is that if the Cop gets a guilty, he should *still* stay hidden, at least temporarily. The instinct is "I have a guilty, it's lylo, better claim", but in fact the correct play in this case is to pick a target at random, and have the Cop come out only if the lynch target is not the player he got a guilty on. It's likely the Cop will be forced to come out, but if the lynch randomly lands on the investigated scum, the EV doubles.

Anyway, putting it all together I get an EV of 6859/15750 (~43.55%).

I suspect we can push the upper bound down some by adding the following rule: If the Day 1 lynch is on scum, the scum are told who the Cop is (this is equivalent to allowing the scum to fake claim, forcing the Cop to counter). I suppose it's possible that the Cop should stay hidden, but I think it's unlikely. Anyway, if we add in that rule just for Day 1, it pushes the EV down to ~35.78%. Adding it in across the board would push the EV lower still (may go back through and calculate this, have other things to do at the moment).

There are more complicated things going on in the actual California setup. As was pointed out earlier in the thread, the scum shouldn't claim Cop 100% of the time, or a Townie claim is confirmed innocent - rather, they should claim Cop some large fraction of the time, in order to draw out the Cop most of the time but ensure that the town must lynch Townie claims. The Cop may be better off staying hidden if scum claim Cop - if the Cop is NKed, the scum gets lynched the next day, and the real Cop gets an investigation, but on the other hand the odds of a successful D1 lynch go way down and when the Cop does come out D2 he won't necessarily be believed (since if this strategy was viable, it may also be viable for scum to leave the Cop alive N1 and counterclaim him D2). Then you've got the whole "which claim is more likely to be true" problem, in all cases (both claim D1, both claim D2, one claims D1 and the other D2). It's a mess.

I think I'll tackle 2 Mafia, 1 Doctor, 4 Townies next. Tired of dealing with Cops.

[Fishythefish]

I think the "no claiming" upper bound is likely a very good one, and I've already got a recursion for that (quite easy, should work for large setups). I've also got a "Named Townie" thing working now (turns out scum should cc the NT, but very rarely).

If you make the cop counterclaim scum, I don't think that you have an upper bound any more for high numbers. Very likely a strategy of "don't believe cop claims" is superior to the cop counterclaiming - in 100 vs 10 with an extra cop, no way is the cop's life only worth one scum.

What numbers are those EVs for?

[mith]

Oh, I certainly wasn't suggesting that particular assumption would apply for larger setups; I don't even think it could be strictly applied for California, for the reasons mentioned.

The 43.55% is for the "no fake claim" version; does your recursion agree with that? 35.78% is with the "remaining scum is told who the cop is if D1 is a scum lynch", which I don't think we can say is necessarily an upper bound (because Cop might want to stay hidden) - but it probably is higher than the actual EV (because allowing the scum to fake claim more generally should be a significant improvement for them, while allowing the cop to stay hidden will only help the town a little, if at all, and the rate at which scum should claim townie should be pretty low).

(In the 10:100+Cop setup, I'd expect the strategy would be for scum to claim Cop a large percentage of the time until the real Cop is dead, and for the real Cop to remain hidden until he's caught at least one unclaimed scum. Maybe two, but that might be pushing it. If the Cop survives long enough, he would eventually consider coming out with a lot of innocent results, of course. Probably some more tricky stuff to consider for when the Cop actually does come out. But that's pretty irrelevant if we can't even solve California.)

Actually, I think my next attempt with Cops may be a 1:2+Cop Night Start. Small enough to be managable, but it still has some interesting strategic considerations (what investigation the scum should claim, and how the town should handle claim order).

[mith]

Ok, I need to go through these again at some point because they're very much back-of-the-envelope calculations, but here's what I've got.

Obviously, if the Mafia hits the Cop (1/3 chance), it's a 1:2 endgame with an EV of 1/3.

Otherwise:

Mafia will always claim Cop. (Why? If he doesn't, the Cop is confirmed innocent; even in the Cop investigated the dead townie, it's a 50-50, and there's a 2/3 chance he investigated a living player, so the EV is 5/6.)

Assumption for simplicity: Mafia and Cop claim investigations at the same time. (I'll have to run through it later to see how things change if there's a random claim order.)

Mafia essentially has three choices: Claim a guilty on someone; Claim an innocent on someone; Claim to have investigated the dead player. Because of symmetry, it turns out that it doesn't matter wheather he claims a guilty or an innocent; so let's say he does one of the first four options (guilty on the Cop, guilty on the townie, innocent on the Cop, innocent on the townie) with probability p/4, and claims a dead player investigation the other 1-p.

The real Cop, of course, claims his actual result, and there is a 1/3 probability for each possibility.

In two of the five Mafia options, Mafia loses instantly - if he claims a guilty on the townie or an innocent on the Cop, he's dead with the Cop out. (This is where the random claim order makes things interesting - if Mafia claims second, he now knows which two cases to avoid.)

That leaves nine pairs of claims. Three are obviously symmetric - they claim guilty on each other, they both claim innocent on the townie, they both claim to have investigated the dead player. Two others are also symmetric, since there is no reason to favor a guilty or innocent from either perspective - one claims innocent on the townie, the other claims guilty on the first. In each of these five cases, it's a coin flip.

The four remaining cases:

Mafia claims Cop is Guilty, Cop investigated Dead - p/12
Mafia claims Townie is Innocent, Cop investigated Dead - p/12
Mafia claims Dead, Cop investigated Mafia - (1-p)/3
Mafia claims Dead, Cop investigated Townie - (1-p)/3

In each case, the Townie now has a choice: lynch the player who claimed a result, or lynch the player who claimed to investigate the dead. Let's call the probability of lynching the dead claim x.

Town win percentage is:

6*p/12 (the won cases)
+ 1/2*4*p/12 + 1/2*(1-p)/3 (the symmetric cases)
+ (1-x)*2*p/12 (the cases where the Cop investigated the Dead)
+ x*2*(1-p)/3 (the cases where the Cop has a result)

= 1/6 + 2p/3 + 2x/3 - 5px/6

To find the equilbrium values, we take the derivative with respect to each variable:

dEV/dx = 2/3 - 5p/6 => p = 4/5
dEV/dp = 2/3 - 5x/6 => x = 4/5

(The first says that if the Townie chooses p to be 4/5, the EV is constant with respect to x - even knowing p, the Mafia can't manipulate x to improve his odds. Likewise with the second.)

Thus: EV = 7/10.

The overall EV for the 1:2+Cop NS setup is then 1/3*1/3 + 2/3*7/10 = 26/45 = 57.7~%.