#!/usr/bin/perl
# Calulate the odds of the wolves winning a game of werewolf.
#
# Bruno Wolff III
# July 9, 2001
#
# Assume that all information obtained by a seer is available to all
# human players without tipping off the wolves to who the seer is.
# This is unrealistic, but is concrete and allows for a lower bound
# to be calculated.
# The state subscripts for $win are:
# Number of unidentified human villagers
# Number of identified human villagers
# Number of unidentified wolves
# Number of identified wolves (0 or 1)
# Number of Seers (0 or 1)
# Next stage to occur (0 - Lynch, 1 - Seer divination, 2 - Wolf dinner)
$| = 1;
$play = 0;
while ($play < 1) {
print STDERR "Up to how many players? ";
$play = ;
chop $play;
$play =~ s/ //g;
if ($play !~ m/^\d+$/ || $play < 1) {
$play = 0;
print STDERR "Invalid number of players.\n";
}
}
$wolf = 0;
while ($wolf < 1) {
print STDERR "Up to how many wolves? ";
$wolf = ;
chop $wolf;
$wolf =~ s/ //g;
if ($wolf !~ m/^\d+$/ || $wolf < 1 || $wolf >= $play) {
$wolf = 0;
print STDERR "Invalid number of wolves.\n";
}
}
for ($h=0; $h<=$play; $h++) {
for ($w=0; $w<=$play-$h; $w++) {
for ($s=0; $s<=1 && $s<=$h; $s++) {
for ($v=0; $v<=$h-$s; $v++) {
$vid = $h - $s - $v;
for ($wun=($w>0?$w-1:0); $wun<=$w; $wun++) {
$wid = $w - $wun;
# The wolves win when all of the people are dead.
if ($h == 0) {
$win[$v][$vid][$wun][$wid][$s][0] = 1;
$win[$v][$vid][$wun][$wid][$s][1] = 1;
$win[$v][$vid][$wun][$wid][$s][2] = 1;
}
# The people win when all of the wolves are dead.
elsif ($w == 0) {
$win[$v][$vid][$wun][$wid][$s][0] = 0;
$win[$v][$vid][$wun][$wid][$s][1] = 0;
$win[$v][$vid][$wun][$wid][$s][2] = 0;
}
else {
# Lynch
# Kill wolf if known, otherwise choose randomly from unidentified villagers
# (the Seer is always identified) and unidentified wolves.
# This limits identified wolves to 1.
# If there are as many wolves as humans, only humans will get lynched.
# (There should only be an odd number of players at this step or the
# vote could deadlock.)
if ($w >= $h) {
$win[$v][$vid][$wun][$wid][$s][0] = (
($v ? $v * $win[$v-1][$vid][$wun][$wid][$s][1] : 0) +
($vid ? $vid * $win[$v][$vid-1][$wun][$wid][$s][1] : 0) +
($s ? $s * $win[$v][$vid][$wun][$wid][$s-1][1] : 0)) / $h;
}
elsif ($wid >= 1) {
$win[$v][$vid][$wun][$wid][$s][0] = $win[$v][$vid][$wun][$wid-1][$s][1];
}
else {
$win[$v][$vid][$wun][$wid][$s][0] = (
($v ? $v * $win[$v-1][$vid][$wun][$wid][$s][1] : 0) +
($wun ? $wun * $win[$v][$vid][$wun-1][$wid][$s][1] : 0)) / ($v + $wun);
}
# Hunt
# The wolves will eat a random person unless there are an odd number of
# players. (This should only happen the first night.) This means that
# the hunt calculation needs to be done after the lynch calculation.
if (($h + $w) % 2 == 1) {
$win[$v][$vid][$wun][$wid][$s][2] = $win[$v][$vid][$wun][$wid][$s][0];
}
else {
$win[$v][$vid][$wun][$wid][$s][2] = (
($v ? $v * $win[$v-1][$vid][$wun][$wid][$s][0] : 0) +
($vid ? $vid * $win[$v][$vid-1][$wun][$wid][$s][0] : 0) +
($s ? $s * $win[$v][$vid][$wun][$wid][$s-1][0] : 0)) / $h;
}
# Divination
# The Seer (if any) chooses to learn about an unidentified human or wolf.
# This must be the last thing checked since the character counts might
# not change and the hunt value needs to be already calculated.
# Once there are as many wolves as people the seer no longer matters.
# However we can't let the identified wolves keep increasing since we
# assume there can only be one for efficiancy.
if ($s == 0 || $v + $wun == 0 || $w >= $h) {
$win[$v][$vid][$wun][$wid][$s][1] = $win[$v][$vid][$wun][$wid][$s][2];
}
else {
$win[$v][$vid][$wun][$wid][$s][1] = (
($v ? $v * $win[$v-1][$vid+1][$wun][$wid][$s][2] : 0) +
($wun ? $wun * $win[$v][$vid][$wun-1][$wid+1][$s][2] : 0)) / ($v + $wun);
}
}
}
}
}
}
}
print " Wolves - Odds of wolves winning - Without seer / With seer\n";
print "Players ";
for ($i = 1; $i<=$wolf; $i++) {
printf " %-7d ", $i;
}
print "\n";
for ($j = 2; $j<=$play; $j++) {
printf "%-7d", $j;
for ($i=1; $i<=$wolf; $i++) {
if ($j <= $i) {
print " ";
}
else {
printf " %7.5f/%7.5f", $win[$j-$i][0][$i][0][0][1], $win[$j-$i-1][0][$i][0][1][1];
}
}
print "\n";
}