#!/usr/bin/perl

# Calulate the odds of the wolves winning a game of werewolf.
#
# Bruno Wolff III
# July 9, 2001
# Updated July 21, 2001
#
# Assume no Seer information is available until he reveals it publically.
# Once this happens the wolves will kill him. If he is picked to be lynched,
# he will go public and not be lynched. He will be believed when he goes
# public. He will voluntarily go public when it makes sense to do so.

# The state subscripts for $win are:
#   Number of unidentified human villagers
#   Number of identified human villagers
#   Number of unidentified wolves
#   Number of identified wolves
#   Number of Seers. (When Seer goes public, treat him as a normal identified
#     human as the wolves will target him next. So the identify information
#     can only be used if Seer count is 0 for purposes of lynching.)
#   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 = <STDIN>;
  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 = <STDIN>;
  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=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
# and unidentified wolves if Seer revealed information, otherwise pick
# random player, but give Seer a chance to reveal stuff.
# 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 ($s == 0) {
              if ($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);
              }
            }
            else {
              $wi = 0;
              if ($wid > 0) {
                $wi = $win[$v][$vid][$wun][$wid-1][$s][1];
                $wi = $win[$v][$vid+1][$wun][$wid-1][$s-1][1]
                  if $win[$v][$vid+1][$wun][$wid-1][$s-1][1] < $wi;
              }
              $vi = 0;
              if ($vid > 0) {
                $vi = $win[$v][$vid-1][$wun][$wid][$s][1];
                $vi = $win[$v][$vid+1][$wun][$wid][$s-1][0]
                  if $win[$v][$vid+1][$wun][$wid][$s-1][0] < $vi;
              }
              $si = $win[$v][$vid+1][$wun][$wid][$s-1][0];
              if ($v + $wun > 0) {
                $u = (($v ? $v * $win[$v-1][$vid][$wun][$wid][$s][1] : 0) +
                  ($wun ? $wun * $win[$v][$vid][$wun-1][$wid][$s][1] : 0)) / ($v + $wun);
                $u = $win[$v][$vid+1][$wun][$wid][$s-1][0]
                  if $win[$v][$vid+1][$wun][$wid][$s-1][0] < $u;
                $win[$v][$vid][$wun][$wid][$s][0] = ($wid * $wi + $s * $si +
                  $vid * $vi + ($v + $wun) * $u) / ($h + $w);
              }
            }

# 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.
# Wolves will eat identified villagers first. A Seer that goes public
# can be treated as an identified villager.
# If a Seer gets eaten here, he doesn't get to spill the beans.
            if (($h + $w) % 2 == 1) {
              $win[$v][$vid][$wun][$wid][$s][2] = $win[$v][$vid][$wun][$wid][$s][0];
            }
            else {
              if ($s == 0 and $vid > 0) {
                $win[$v][$vid][$wun][$wid][$s][2] = 
                  $win[$v][$vid-1][$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][0][$wun+$wid][0][$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";
}