[proposition] town:scum winrate calculator

[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)

[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)

[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) ^

[Ircher]

There's only 9 possible outcomes, NOT 15

[Ircher]

Read 6 again.

[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.

[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.

[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.

[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.

[Ircher]

The amount of information one has ACTUALLY CHANGES the probabilities.

[Ircher]

X,Y,Z are town; A,B are scum.

Code: Select all

X lynched --> 0 / 1
Y lynched --> 0 / 1 (0 / 2)
Z lynched --> 0 / 1 (0 / 3)

A lynched: 3 / 9 (3 / 12)
  X Nk'd: 1 / 3 (1 / 6)
    Y lynched --> 0 / 1 (0 / 4)
    Z lynched --> 0 / 1 (0 / 5)
    B lynched --> 1 / 1 (1 / 6)

  Y NK'd: 1 / 3 (2 / 9)
    X lynched --> 0 / 1 (1 / 7)
    Z lynched --> 0 / 1 (1 / 8)
    B lynched --> 1 / 1 (2 / 9)

  Z NK'd: 1 / 3 (3 / 12)
    X lynched --> 0 / 1 (2 / 10)
    Y lynched --> 0 / 1 (2 / 11)
    B lynched --> 1 / 1 (3 / 12)

B lynched: 3 / 9 (6 / 21)
  X Nk'd: 1 / 3 (4 / 15)
    Y lynched --> 0 / 1 (3 / 13)
    Z lynched --> 0 / 1 (3 / 14)
    A lynched --> 1 / 1 (4 / 15)

  Y NK'd: 1 / 3 (5 / 18)
    X lynched --> 0 / 1 (4 / 16)
    Z lynched --> 0 / 1 (4 / 17)
    A lynched --> 1 / 1 (5 / 18)

  Z NK'd: 1 / 3 (6 / 21)
    X lynched --> 0 / 1 (5 / 19)
    Y lynched --> 0 / 1 (5 / 20)
    A lynched --> 1 / 1 (5 / 21)

The above represents ALL the different ways the game can end. The first number reprsent the town wins in that tree and the second is the total number of combinations in that tree. In parenthesis is the running total.

[Ircher]

It took a while, I get it now.

[Ircher]

It's that not all outcomes are equally likely because of the context

Not related.

I thought about that, and that's where the nk thing and info thing came in that I mentioned.

[Ircher]

And that, my friend, is why mafia is interesting.

A program cannot account for every possibility, but if you make some assumptions, you can calculate some things in a reasonable manner. I actually think the more important Q to be asking here is how to calculate the way two roles work together (like Cop+Doc which is a breaking strategy). Also, the EV is an expected win rate; it is by no means perfect.

[Ircher]

Feel like this thread ought to be moved to open setup discussion simply cuz it contains a very useful link.