[proposition] town:scum winrate calculator

[Smithereens]

I recently broke my graphics calculator. The result was an epiphany of how difficult it actually is to do probability without the assistance of technology. For a start, I need to know how much re-balancing a 7v2 game requires to make a town win as viable as a scum win. The long way to find this is to solve this equation: 7/9x5/7x3/5+7/9x5/7x2/5x2/3+7/9x2/7x4/5x2/3+2/9x6/7x4/5x2/3 = 0.70159. So Scum are expected to win 70% of the time in a 7v2 match assuming ideal play (random lynches every day). However, I don't really have the mathematical ingenuity to solve expected win rates for much bigger games, let alone games with roles in them. The addition of a doctor for example means that instead of 2 possible outcomes (mislynch + NK or lynch + NK) there is instead double that (mislynch + NK or mislynch + no NK or lynch + NK or lynch + no NK) for as long as the doctor is alive. The cop, assuming perfect play increases the chance of lynch to (m+1)/n, and reduces the chance of mislynch to (n-m-1)/n where m is the number of scum and n is the number of living players. As you can see, the addition of a single variable exponentially increases the complexity of the calculation.

If there is a trick to running large calculations, I'd love to know it. I'm no mathematician

However, this does drive me to make a suggestion, and one where I'm actually prepared to pay money to see it happen. There are a lot of people who are really good at coding on this site, and while I know nothing about coding, I want to know if it's feasible to build a calculator that is specifically tailored towards calculating expected win rates for town:mafia:others given certain variables, including number of players, number of scum, the presence of certain roles and certain other key mechanics.

Imo it would really be a major asset to the mafia community. Mods would be able to fine tweak balancing of large themed games instead of relying on opinions. Also, we'd be able to scientifically research our games and drawn valid conclusions. Except I wouldn't have a clue as to how feasible it is. I assume currently there are a couple mathematicians running around here who know how to do large calculations in a finite amount of time, however it's clearly not possible for them to run statistical analysis of every game that pops up for a review.

Is this idea possible? Also, if you're a maths person and you have tips to share on mafia calculations, please share them!

[Ircher]

First of all, this is where computers & programming becomes useful.

[Ircher]

I have made myself a program that can calculate win rates for Mountainous games.... Except that overflow occurs pretty quick as the total number of players increase.

Prob. be better to calculate each individual prob. and multiply with the comp, but that doesn't consider how roles work together.

[Ircher]

I guess that one thing that might be useful to know is that as you add VTs to a game, the winrates will reach a limit. In 2 scum Mountainous, that limit is about 37% (for Odd numbers, Day Start; much lower if night start)

[zoraster]

http://games-net.de/hosted/tggc/trash/m ... 0&do=Go%21

[Ircher]

Just saying I didn't get those kinds of results when I made my version of the calculator....


In particular, does the calculator check for overflow?

(My implementation was written in C and went through all the possibilities 1 by 1 through recursion. To speed things up, I used a lookup table. It simply counted up town wins and total paths and then divided to give a decimal answer; I used 64-bit integers btw... I never got over 36% or so for 2 Mafia)

[Ircher]

Yeah, that calculator is wrong and here's why:

Let's assume it's 5p with 2 Mafia, 3 Town, Day Start Mountainous

On D1, there are 5 different possible lynches. Out of those,

3 of those lead to an immediate loss.

- That's 3 Outcomes
The other two lynches leads to a 3p LyLo situation (which we know is 33%, but the more important number to know is that each instance has 3 different possibilities with 1 win in each)

Do the addition and multiplication for the total number of outcomes: 3 + (2 * 3) = 9 Total Outcomes
Do the addition and multiplication for the number of outcomes where towm wins: 2 * 1 = 2 Town Win Outcomes
If you divide, you get 2/9 or 22.2%.

This is the way the calculator gets its answer of 13.3% though:

3/5 chance Town Loses Immediately.
2/5 chance Town goes to D2 3p LyLo (1/3 win chance)
---------
Town Win Chance = 2/5 * 1/3 = 2/15 = 13.3% which is NOT the correct probability if town is lynching randomly. (Cuz there are NOT 15 different outcomes for the game; there are ONLY 9)

But why the difference?

The difference is because the 3/5 chances town loses immediately DO NOT have three more possible putcomes; they only have 1 outcome each there. You are trying to count an extra 6 outcomes which simply do not exist.

[Ircher]

(EV Project ==== EPIC FAIL)

[zoraster]

Yeah, that calculator is wrong and here's why:

Let's assume it's 5p with 2 Mafia, 3 Town, Day Start Mountainous

On D1, there are 5 different possible lynches. Out of those,

3 of those lead to an immediate loss.

- That's 3 Outcomes
The other two lynches leads to a 3p LyLo situation (which we know is 33%, but the more important number to know is that each instance has 3 different possibilities with 1 win in each)

Do the addition and multiplication for the total number of outcomes: 3 + (2 * 3) = 9 Total Outcomes
Do the addition and multiplication for the number of outcomes where towm wins: 2 * 1 = 2 Town Win Outcomes
If you divide, you get 2/9 or 22.2%.

This is the way the calculator gets its answer of 13.3% though:

3/5 chance Town Loses Immediately.
2/5 chance Town goes to D2 3p LyLo (1/3 win chance)
---------
Town Win Chance = 2/5 * 1/3 = 2/15 = 13.3% which is NOT the correct probability if town is lynching randomly. (Cuz there are NOT 15 different outcomes for the game; there are ONLY 9)

But why the difference?

The difference is because the 3/5 chances town loses immediately DO NOT have three more possible putcomes; they only have 1 outcome each there. You are trying to count an extra 6 outcomes which simply do not exist.

I think you're confusing the day start for night start. Day start is 0 in the system. I get 22.86% with 2s/3t daystart

[zoraster]

oh wait. I entered a number wrong.

[Ircher]

main.c:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "classes.h"

// Lookup table
rvalues **table = NULL;

int main(void) {
  FILE *output = fopen("mountainous.txt", "w" );
  if (!output) return 1;
  unsigned int t = 0, s = 0, i = 0;
  rvalue results = {0, 0}
  // Overflow reasons; max town players
  #define T_END 20
  table = malloc( T_END * sizeof(rvalues*) );
  for (; i < T_END; ++i) {
    table[i] = malloc( (T_END - 1) * sizeof(rvalues) );
    for (s = 0; s < i; ++s) {
      table[i][s].wins = 0;
      table[i][s].totals = 0;
    }
  }
  // Town
  for (t = 2; t < T_END; ++t) {
    // Mafia
    for (s = 1; s < t; ++s) {
      print_header( output, t, s );
      run_iteration( t, s, &results );
      print_results( output, &results );
      table[t - 1][s - 1].wins = results.wins;
      table[t - 1][s - 1].totals = results.totals;
      // Reset results
      results.wins = 0;
      results.totals = 0;
    }
    fprintf( output, "---\n" );
    fflush( output );
  }
  // Free memory
  for (i = 0; i < T_END; ++i) {
    free( table[i] );
  }
  free( table );
  return 0;
}

void print_header( FILE *file, unsigned int town, unsigned int scum ) {
  fprintf( file, "%up: %uT, %uS = ", town + scum, town, scum );
}

void print_results( FILE *file, rvalues *results ) {
  fprintf( file, "%.2lf%% (%llu of %llu)\n", ((long double)results->wins * 100.00) / (long double)results->totals, results->wins, results->totals );
}

void run_iteration( unsigned int town, unsigned int scum, rvalues *results ) {
  // Check lookup
  if (table[town - 1][scum - 1].totals > 0) {
    results->wins += table[town - 1][scum - 1].wins;
    results->totals += table[town - 1][scum -1].totals;
  }
  unsigned int players = town + scum;
  // Run through each possibility
  // Record immediate wins, check if town loses next day
  // Rinse & repeat
  unsigned int *p = malloc( sizeof( unsigned int ) * players );
  if (!p) exit(1);
  unsigned int i = 0;
  for (; i < players; ++i) {
    if (i < town) p[i] = 0;
    else p[i] = 1;
  }
  for (i = 0; i < players; ++i) {
    if (p[i] == 0) {
      // Town lynch
      if (town - 2 > scum) {
        // Next day
        run_iteration( town - 2, scum, results );
      }
      else {
        // S Win
        results->totals += 1;
      }
    }
    else {
      // Mafia lynch
      if (scum - 1 > 0) {
        // Next day
        run_iteration( town - 1, scum - 1, results );
      }
      else {
        // T win
        results->wins += 1;
        results->totals += 1;
      }
    }
  }
  free(p);
}

classes.h

Code: Select all

// Function prototypes

typedef struct run_values {
  unsigned long long int wins;
  unsigned long long int totals;
} rvalues;

[Ircher]

Thats the code I'm using (there may be some minor errors in having to retype it on mobile, but it should work with a C compiler) ^

[zoraster]

I don't see how you're getting what you are. There's a 40% chance of lynching scum on Day 1. Then scum night kill bringing it to 2-1. Then there's a 33.3% chance of lynching scum on Day 2.

.3333333*.4 = .133333333

Using pure outcomes to determine things tries to act as if every outcome is equally as likely when certain outcomes are dependent on other outcomes that are more or less likely.

[Ircher]

There's only 9 possible outcomes, NOT 15

[Ircher]

Read 6 again.

[zoraster]

Day 1 there's a 2-5 chance you lynch scum for 40%. So that branch of the tree has a 40% chance of happening.

ASSUMING the above (meaning we're in the 40% world) there's now a 1-3 chance of lynching scum for 33.3%. So the 33.3% is multiplied by the 40% because that's how probabilities work. Because no other branch of the tree leads to a town win, the chance of a town win is 13.3%

[Ircher]

Alright, say we have townes X, Y, Z and mafia goons A and B.

If X is lynched, then the game ends immediately. That's one outcome. (1)
If Y is lynched, then the game ends immediately. That's one outcome. (2)
If Z is lynched, then the game ends immediately. That's one outcome. (3)

If A is lynched, then the game goes into night.

It doesn't matter who mafia nk, as they aren't nking themselves, so I'm ignoring that. (Even if I did count those, my answer would be closer (if I did, that would change it to 6 / 21 ~ 28%))

Three outcomes are left: 2 Townies, and B who is the Goon. So, that's 1 win out of 3 outcomes for this path. (6)

Same applies to the other one.

[zoraster]

I've read what you're saying, but you're wrong. It's not that there are 9 or 15 outcomes. There's actually only 3 outcomes (Day 1 Scum win, Day 2 scum win, Day 2 town win). But it doesn't matter how many outcomes there are because they're not equally possible.

[Ircher]

Put it another way, there are not 15 different ways the game can end. There are only 9 (21 if you factor in the mafia nk's target) ways for the game to end.

[zoraster]

Right. Because P(T|M) as you put it is 33.3%. But a mafia goon being lynched day 1 is only a 40% chance of happening. So given a 40% chance of something happening, you have a 33.3% chance of winning. Which is, once again, 13.3%

[Ircher]

I deleted that post for a reason.

What you don't get is that there are only 9 (21) different ways for the game to end (different combinations per se) and 2 (6) combinations that lead to a town win.

[zoraster]

so what? if I tell you that you win 100,000 if you flip heads and if you don't then you get a second chance of 100,000 dollars if you roll a 5 on a 100000000000000000000-sided die, your expected value is about $50,000 regardless of the number of technical outcomes possible.

Or I guess once again I dispute your 9, 21 or any number that isn't 3. There are 3 different outcomes for the game. Either you you lynch BOTH Day 1 and 2 or you lose, either on day 1 or day 2. And the probability of that isn't hard to calculate. And it's 13.333%

[Smithereens]

http://games-net.de/hosted/tggc/trash/m ... 0&do=Go%21

Bless your face.

[zoraster]

No problem! I forget who wrote that, but it's been a go to for a while! Though certainly keep in minds its limitations.

[Ircher]

so what? if I tell you that you win 100,000 if you flip heads and if you don't then you get a second chance of 100,000 dollars if you roll a 5 on a 100000000000000000000-sided die, your expected value is about $50,000 regardless of the number of technical outcomes possible.

Or I guess once again I dispute your 9, 21 or any number that isn't 3. There are 3 different outcomes for the game. Either you you lynch BOTH Day 1 and 2 or you lose, either on day 1 or day 2. And the probability of that isn't hard to calculate. And it's 13.333%

But there are 21 different combinations that can lead to one of those outcomes.