112
\$\begingroup\$

Results - July 19, 2014

The current King of the Hill is Mercenary by user Fabigler! Keep submitting entries and knock him off of his throne!

Click here to view the Scoreboard.

Programs submitted on or before July 19, 2014 were included. All other submissions will be included in future trials. New results should be posted around August 9, so that gives you plenty of time.


Illustration drawn by brother Illustrated by Chris Rainbolt, my brother and a fresh graduate from Savannah College of Art and Design

Introduction

The angels and demons are fighting and, as usual, using earth as their battleground. Humans are stuck in the middle and are being forced to take sides. An unknown neutral force rewards those who consistently fight for the losing side.

The Game

Each trial, you will be pseudorandomly paired and then shuffled with between 20 and 30 other submissions. Each trial will consist of 1000 rounds. Each round, you will be passed an input and be expected to produce output. Your output will be recorded and scored. This process will be repeated 1000 times.

Input

You will receive a single argument that represents the past votes of each player. Rounds are delimited by comma. A 0 represents a player who sided with Evil that round. A 1 represents a player who sided with Good. Within a trial, the players will always be in the same order. Your own vote will be included, but not explicitly identified. For example:

101,100,100

In this example, three rounds have been completed and three players are competing. Player one always sided with Good. Player two always sided with Evil. Player three swapped from Good in round 1 to Evil in rounds 2 and 3. One of those players was you.

Output

Java Submissions

  • Return the string good if you want to side with Good.
  • Return the string evil if you want to side with Evil.

Non-Java Submissions

  • Output the string good to stdout if you want to side with Good.
  • Output the string evil to stdout if you want to side with Evil.

If your program outputs or returns anything else, throws an exception, does not compile, or takes longer than one second to output anything on this exact machine, then it will be disqualified.

Scoring

Scores will be posted in a Google docs spreadsheet for easy viewing as soon as I can compile all the current entries. Don't worry - I will keep running trials for as long as you guys keep submitting programs!

  • You receive 3 points for siding with the majority during a round.
  • You receive n - 1 points for siding with the minority during a round, where n is the number of consecutive times you have sided with the minority.

Your score will be the median of 5 trials. Each trial consists of 1000 rounds.

Deliverables

Non-Java Submissions

You must submit a unique title, a program, and a Windows command line string that will run your program. Remember that an argument may be appended to that string. For example:

  • python Angel.py
    • Note that this one has no args. This is round one! Be prepared for this.
  • python Angel.py 11011,00101,11101,11111,00001,11001,11001

Java Submissions

You must submit a unique title and a Java class that extends the abstract Human class written below.

public abstract class Human {
    public abstract String takeSides(String history) throws Exception;
}

Testing

If you want to test your own submission, follow the instructions here.

Additional Notes

You may submit as many different submissions as you want. Submissions that appear to be colluding will be disqualified. The author of this challenge will be the only judge on that matter.

A new instance of your program or Java class will be created every time it is called upon. You may persist information by writing to a file. You may not modify the structure or behavior of anything except your own class.

Players will be shuffled before the trial starts. Demon and Angel will participate in every trial. If the number of players is even, Petyr Baelish will also join. Demon fights for Evil, Angel for Good, and Petyr Baelish chooses a pseudorandom side.

\$\endgroup\$
  • 2
    \$\begingroup\$ Comments purged, as they were obsolete and at request of OP. Please notify me of any comments that need to be undeleted. \$\endgroup\$ – Doorknob Jul 16 '14 at 11:28
  • 7
    \$\begingroup\$ Woah, OP changes his username. Ok, so when will the result be displayed? \$\endgroup\$ – justhalf Jul 18 '14 at 6:52
  • 6
    \$\begingroup\$ @Rainbolt This must be one freakin' hell of a job, running this challenge! The reason for this amount of attention is the simplicity of the protocol and the rules, making it accessible while also allowing simple, working entries. TL;DR: Your challenge is too good! :D \$\endgroup\$ – tomsmeding Jul 19 '14 at 18:54
  • 3
    \$\begingroup\$ @dgel I'll post the raw data, upper, lower, averages, and maybe a line chart so we can see who did better as the competition dragged on. \$\endgroup\$ – Rainbolt Jul 21 '14 at 12:03
  • 6
    \$\begingroup\$ One of the pods ended up with 10 entries that voted the same way every single time. Consequently, two users ended up with perfect or "one round short of perfect" scores of around 450,000. The same entries scored around 1900 in other trials. The average score is close to 2000. Because of the extreme imbalance in results, I decided that a more meaningful number would be a median. I edited the challenge so that after 5 trials, the winner will be the submission with the highest median. If anyone thinks that moving from mean to median is unfair or otherwise a poor choice, please comment. \$\endgroup\$ – Rainbolt Jul 21 '14 at 18:57

92 Answers 92

2
\$\begingroup\$

The Friend of the Lonely

This character finds the first lonely person (defined as being surrounded by 2 of the opposite values, e.g. 00100 has a 1 as lonely; if there are less than 5 players we'll simply use 1 boundary: 010), and chooses that player's side.

As per @trlkly's request, this is written in Fortran 90 -- I apologize in advance for its length, but getting an okay PRN is a bit complicated in Fortran. Anyway, here's the code:

program FriendOfLonely
   implicit none
   integer, parameter :: ip = selected_int_kind(16)
   real :: r
   integer(4) :: first, i, j, competitors
   character(len=999999) :: round
   character(len=4) :: choice


   call init_random_seed()

   first = command_argument_count()
   if(first == 0) then
      call random_number(r)
      choice = merge("good", "evil", r > 0.5)
   else
      call get_command_argument(first, round)
      j=len(trim(round))
      do i=1,j
         if(round(i:i)==',') then
            competitors=i-1
            exit
         endif
      enddo
      call Choose(competitors, first, trim(round(j-competitors+1:j)), choice)
   endif

! I've made my choice
   print *,choice
 contains
   !> Search the array for choice
   subroutine Choose(comps, first, round, choice)
     integer(4), intent(in) :: comps, first
     character(*), intent(in) :: round
     character(4), intent(out) :: choice
     character(5) :: good, evil
     integer(ip) :: i,j

     if(comps >= 5) then
        good = '00100'; evil = '11011'
! find a lonely person
        do i=1,len(round)-5
           if(round(i:i+4)==good) then
              choice = 'good'
              return
           else if(round(i:i+4)==evil) then
              choice = 'evil'
              return
           endif
        enddo
     else
        good = '010'; evil = '101'
! find a lonely person
        do i=1,len(round)-3
           if(round(i:i+2)==trim(good)) then
              choice = 'good'
              return
           else if(round(i:i+2)==trim(evil)) then
              choice = 'evil'
              return
           endif
        enddo
     endif
! make random choice
     call random_number(r)
     choice = merge('good', 'evil', r > 0.5)
   end subroutine Choose

   !> Sets the PRNG so you're not constantly choosing the same damn thing
   subroutine init_random_seed()
      integer(4) :: n, i, un, istat, dt(8), pid
      integer(ip) :: t
      integer(4), allocatable :: seed(:)
      call random_seed(size=n)
      allocate(seed(n))
      call system_clock(t)
      if(t==0) then
         call date_and_time(values=dt)
         t = (dt(1) - 1970) * 365 * 24 * 60 * 60 * 1000 &
                       + dt(2) * 31 * 24 * 60 * 60 * 1000 &
                       + dt(3) * 24 * 60 * 60 * 1000 &
                       + dt(5) * 60 * 60 * 1000 &
                       + dt(6) * 60 * 1000 + dt(7) * 1000 &
                       + dt(ip)
      endif
      pid = getpid()
      t = ieor(t, int(pid,kind(t)))
      do i=1,n
         seed(i) = lcg(t)
      enddo
      call random_seed(put=seed)
   end subroutine init_random_seed

   !> Not ideal PRNG, but it will work
   integer(ip) function lcg(s)
     integer(ip) :: s
     if(s==0) then
        s = 104729
     else
        s = mod(s, 4294967296)
     endif
     s = mod(s* 279470273, 4294967291)
     lcg = int(mod(s, int(huge(0), 8)), 8)
   end function lcg
end program FriendOfLonely

This is compiled via

gfortran -fno-range-check -o FriendOfLonely FriendOfLonely.f90

and can accept the command line arguments (not something normally done in Fortran, but the language can handle just about anything these days).

\$\endgroup\$
  • \$\begingroup\$ @trlkly: as per your request ;) \$\endgroup\$ – Kyle Kanos Jul 14 '14 at 13:55
  • \$\begingroup\$ @Rusher: Ooo, Windows. I haven't used Windows in 5+ years. Intel offers a trial version for Windows (ifort -o FriendOfLonely FriendOfLonely.f90 would compile it), but I've never used it (the Linux version I have). \$\endgroup\$ – Kyle Kanos Jul 15 '14 at 1:39
  • 1
    \$\begingroup\$ I managed to install mingw-get. I flopped around in the help section until I was able to install gfortran. Then I installed mpc. I am at least now getting what look like errors when I compile Error: invalid instruction suffi x for pop and Error: register save offset not a multiple of 8. Can someone add a more complete set of instructions for compiling this on a Windows machine? I've downloaded three packages already trying to make this work, and the error messages looks like weird assembly language errors. \$\endgroup\$ – Rainbolt Jul 15 '14 at 1:54
2
\$\begingroup\$

Java, Friendship

This one makes friends based on other players who voted like it did at the time. Tends to follow the Angel, but can turn "evil" if convinced.

public class Friendship extends Human {
    private int[] friends = null;
    private char myLastVote = '1';

    private int makeFriends(String lastRound) {
        if (friends == null) {
            friends = new int[lastRound.length()];
        }

        //Preset my next vote against my last vote, to cancel out that I'm my own best friend
        int nextVote = (myLastVote == '0' ? 1 : -1);

        //Update my friend list
        for (int i = 0; i < friends.length; i++) {
            char friendVote = lastRound.charAt(i);
            friends[i] += (friendVote == myLastVote ? 1 : -1);
            if (friends[i] > 0 ) {
                nextVote += (friendVote == '0' ? -1 : 1);
            }
        }

        //Set my vote as the same as my friend's last vote
        if (nextVote > 0) {
            myLastVote = '1';
        } else if (nextVote < 0) {
            myLastVote = '0';
        }
        return nextVote;
    }

    @Override
    public String takeSides(String history) throws Exception {
        if (history.length() > 0) {
            String[] rounds = history.split(",");
            //Create friends array from history, if non-existent
            if (friends == null) {
                for (String round : rounds) {
                    makeFriends(round);
                }
            } else {
                makeFriends(rounds[rounds.length-1]);
            }

        }
        return myLastVote == '0' ? "evil" : "good";
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ How do you know your last vote? You don't persist anything and there will be a new instance every round. Also you may add code highlighting. \$\endgroup\$ – Angelo Fuchs Jul 14 '14 at 8:04
  • \$\begingroup\$ When friends is null (i.e. nothing persisted), Friendship recreates its friends and its last vote by replaying all of the previous rounds. The algorithm is deterministic, so it will always define the same friends. Similarly, it will always find itself as its best friend. \$\endgroup\$ – Wasmoo Aug 6 '14 at 18:06
2
\$\begingroup\$

Haskell: Copy Cat

Note: This is Literate Haskell. This means this post is the program itself, and this is a comment in that program.

My program just finds out who's winning, and then copies their last move.

First, the modules.

> import Control.Applicative
> import Data.Function
> import Data.List
> import Data.List.Split
> import System.Environment

Now I invent a function that automatically passes the arguments of a program to a pure function, and then outputs its result to stdout.

> main = argInter prog
> argInter :: ([String] -> String) -> IO ()
> argInter s = getArgs <**> pure s >>= putStrLn

Now for a type for Good and Evil.

> data Moral = Evil | Good deriving (Eq, Read)
> instance Show Moral where
>   show Evil = "evil" --We need lower case.
>   show Good = "good"

We now have a function for converting characters to Morality.

> toMorality :: Char -> Moral
> toMorality '0' = Evil
> toMorality '1' = Good
> toMorality a   = error $ "'"++a:"' is not a vaild Morality."

We show the result of copycat as a String. For the arguments to copycat, first we split on ",", and then we convert the characters to Morality.

> prog [] = show Good -- good seems like a good choice for no arguments
> prog [arg] = show $ copycat $ map (map toMorality) $ splitWhen (==',') arg
> prog a      = error $ "Only 0 or 1 arguments excepted, recieved " ++ (show $ length a) ++ " arguments!"

And now for the meat. We give to copymax the points of all other players. We fold a function that adds points to players scores (and keeps track of how many times the where in the minority.) We then just get the scores with map fst.

> copycat :: [[Moral]] -> Moral
> copycat info = copymax . map fst . foldl' scorer (repeat (0,0)) $ info
>   where

scorer just zips together the choice of each player this round with each players points using the incr function, we updates each players points based on their choice.

>       scorer points round = zipWith incr round points
>           where

To find the majority, we partition the set into the Good and the not Good, compare the lengths. incr is round for each player each round.

>               majority=let (g, e) = partition (==Good) round in case length g `compare` length e of
>                   GT -> Good
>                   LT -> Evil
>                   _  -> error "No majority!"
>               incr morality (points, minor) = if morality==majority
>                   then (points+3, 0)
>                   else (points+minor, minor+1) --minor+1-1 == minor

copymax then just zips the points with the last round, chooses the maximum pair based on the points, and then takes the choice of the last round.

>       copymax points = fst $ maximumBy (compare `on` snd) $ zip (last info) points


Copy this entire post into a text editor and save as copycat.lhs (mind the l).

To compile, first install the haskell platform. Then do cabal install split. Then do ghc -O2 copycat.lhs.

To run: do copycat.exe args if you're on windows.

\$\endgroup\$
  • \$\begingroup\$ Ignore my last comment. I removed all of the comments in your code and it finally started to compile but then I got Not in scope: 'info'. What should I do? \$\endgroup\$ – Rainbolt Jul 14 '14 at 1:28
  • \$\begingroup\$ @Rusher info is indeed out of scope there. I think PyRulez didn't compile his code before posting. If I copy this whole post into a text editor and change the line starting with > copycat = to read > copycat info = copymax . map fst . foldl' scorer (repeat (0,0)) $ info and save it as copycat.lhs (mind the l) and run ghc -O2 copycat.lhs, it compiles nicely and it works. \$\endgroup\$ – tomsmeding Jul 14 '14 at 15:45
  • \$\begingroup\$ @tomsmeding Can you edit the post to reflect what you think is an improvement? I am not at all familiar with Haskell and would feel better if someone who was made the change. \$\endgroup\$ – Rainbolt Jul 14 '14 at 15:54
  • 1
    \$\begingroup\$ @Rusher I submitted an edit to reflect what I just said. EDIT: I see it got accepted. \$\endgroup\$ – tomsmeding Jul 14 '14 at 16:04
  • \$\begingroup\$ The submission is running fine, but I had to add in some blank lines to separate the comments from the code. Stack Overflow renders blank lines, but they don't show up in Notepad sometimes. I don't even know if this can be fixed in a way that I can just copy and paste the text, so I wouldn't worry about it. \$\endgroup\$ – Rainbolt Jul 15 '14 at 1:08
2
\$\begingroup\$

Probability Gambler

Determines each player's probability towards good and votes for the minority.

public final class ProbabilityGambler extends Human {

    @Override
    public String takeSides(String history) throws Exception {
        if (history.length() == 0) return "evil";

        String[] rounds = history.split(",");
        double players[] = new double[rounds[0].length()];
        for (String round : rounds) {
            for (int i = 0; i < players.length; i++) {
                if (round.charAt(i) == '1') {
                    players[i] = players[i] + 1;
                }
            }
        }

        double expected = 0;
        for (int i = 0; i < players.length; i++) {
            expected += players[i]/rounds.length;
        }

        return 1-(int)Math.round(expected / players.length) == 1 ? "good" : "evil";
    }
}
\$\endgroup\$
2
\$\begingroup\$

Mr NotSure

Mr NotSure may change his side in each round depends on other players votes. In general he tries to predict from past how often players change their decisions and adopt it in next round. In example if players change (0 in 1 round and 1 in 2 round) their sides in previous rounds more often than hold (0 in 1 round and 0 is 2 round) their picks he will vote in next round on majority from previous round. That's because probably people will change their mind again (so he will vote on minority).

package Humans;

import java.util.ArrayList;
import java.util.List;


public class MrNotSure extends Human {
    private final List<List<Boolean>> rounds = new ArrayList<>();

    private int ALL_ROUNDS_SCORE = 0; 

    @Override
    public String takeSides(String history) throws Exception {
        if(history == null || history.isEmpty())
            return "evil";
        String[] roundsString = history.split(",");
        if(roundsString.length <= 4)
            return "evil";

        readDataToList(roundsString);

        List<Integer> roundChangeScore = computeChangesForEachRound();

        Round lastRound = new Round(roundsString[roundsString.length-1]);
        if(lastRound.getDifference() < 2)
            return lastRound.getMajority();

        if(ALL_ROUNDS_SCORE < 0)
            return lastRound.getMajority();
        else
            return lastRound.getMinority();
    }

    private List<Integer> computeChangesForEachRound() {
        List<Integer> roundChangeScore = new ArrayList<>();
        int outOfBoundsIndex = rounds.size();
        for(List<Boolean> round : rounds)
        {
            int currentIndex = rounds.indexOf(round);
            if(currentIndex + 1 < outOfBoundsIndex)
            {
                Integer score = computeChanges(round, rounds.get(currentIndex + 1));
                ALL_ROUNDS_SCORE += score;
                roundChangeScore.add(score);
            }
        }
        return roundChangeScore;
    }

    private Integer computeChanges(List<Boolean> roundA, List<Boolean> roundB) {
        Integer b = 0;
        for(int i=0; i<roundA.size(); i++)
        {
            if(roundA.get(i).equals(roundB.get(i)))
                b++;
            else
                b--;
        }
        return b;
    }

    private void readDataToList(String[] roundsString) {
        for(String s : roundsString)
        {
            List<Boolean> round = new ArrayList<>();
            for(char a : s.toCharArray())
            {
                if(a == '0')
                    round.add(false);
                else
                    round.add(true);
            }
            rounds.add(round);
        }
    }

    private class Round
    {
        int good = 0;
        int evil = 0;
        int difference = 0;
        public Round(String round)
        {
            for(char a : round.toCharArray())
            {
                if(a == '0')
                    evil++;
                else
                    good++;
            }
            difference = Math.abs(good - evil);
        }

        public String getMinority() {
            if(good > evil)
                return "evil";
            else
                return "good";
        }

        public String getMajority() {
            if(good > evil)
                return "good";
            else
                return "evil";
        }

        public int getDifference()
        {
            return difference;
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

Parity Check, Ruby

Becomes evil if the number of ones is uneven.

puts %w(good evil)[$*[0] && $*[0].count("1") % 2 || 0]

Run with ruby parity.rb

\$\endgroup\$
2
\$\begingroup\$

The Historian

The Historian carefully makes his way through history, accumulating one previously casted vote to his total every round. If the total is even he sides with evil, otherwise he joins the forces of good.

 package Humans;

 public class Historian extends Human{

 public final String takeSides(String history) { 
     if (history.length()==0){return "evil";}
     String cumulative_history=history.replace(",", "");
     int round_number=history.length() - cumulative_history.length();
     int accumulation=0;
     for (int i=0; i<round_number; i++){
         if (history.charAt(i)=='1')accumulation++;
     }
     if (accumulation%2==0){
         return "evil";
     }
     else {
         return "good";
     }
 }
 }

The Skeptic

The Skeptic works opposite to the way the historian does as he has trouble believing data from the past. He accumulates a total starting from the most recent results, adding a previous vote for each round he's completed.

 package Humans;

 public class Skeptic extends Human{
 public final String takeSides(String history) { 
     if (history.length()==0){return "good";}
     String cumulative_history=history.replace(",", "");
     int round_number=history.length() - cumulative_history.length();
     int accumulation=0;
     for (int i=cumulative_history.length(); i>cumulative_history.length()-round_number; i--){
         if (history.charAt(i)=='1')accumulation++;
     }
     if (accumulation%2==0){
         return "good";
     }
     else {
         return "evil";
     }
 }
 }
\$\endgroup\$
2
\$\begingroup\$

Average Loser

if ARGV.length == 0
    puts "evil"
else
    previous_rounds = ARGV[0].split(',')
    evils = 0
    goods = 0

    previous_rounds.each do |round|
        round.to_s.chars.each do |vote|
            vote == "0" ? evils += 1 : goods += 1
        end
    end

    puts (evils < goods) ? "evil" : "good"
end

To run:

ruby average_loser.rb

Average looser looks at the entire history and selects the one which has the average lowest total vote count. The hope is that other approaches are so over-complicated that they tend towards one direction or the other, thus giving this one an advantage.

Or it will simply mostly lose because it is not smart enough, and not dumb enough.

\$\endgroup\$
2
\$\begingroup\$

Schizophrenic

This guy has scizophrenia. He has an angel, a demon, and a monkey whispering things into his ear, and he decides which voice he's going to listen to.

package Humans;


public class Schizophrenic extends Human {

 ShoulderFriend monkey = new ShoulderMonkey(), angel = new ShoulderAngel(), demon = new ShoulderDemon();

 // Sample inputs: "101,111,000,110"
 public String takeSides(String history)
 {
     String[] ages = history.split(",");
     return pickVoice(ages).listen();

 }

 public ShoulderFriend pickVoice(String[] ages)
 {
     int m = monkey.score(ages), a = angel.score(ages), d = demon.score(ages);
     if (m >= a && m >= d)
        return monkey;
     if (a >= d)
        return angel;
     return demon;
 }

 abstract class ShoulderFriend
 {
    abstract String listen();
    abstract int score(String[] ages);
    boolean didWin(int choice, String age)
    {
        String choicestr = choice == 0 ? "0" : "1";
        // Counts by taking checking length of string if choice was removed
        int count = age.length() - age.replace(choicestr, "").length();
        return count > age.length() / 2;
    }

 }

 class ShoulderMonkey extends ShoulderFriend
 {
     int[] decisions = new int[1000];
     String listen()
     {
         return Math.random() < 0.5 ? "good" : "evil";
     }
     int score(String[] ages)
     {
         int score = 0;
         for (int i = 0; i < ages.length; i++)
            if (didWin(decisions[i], ages[i]))
                score += 3;
         return score;
     }

 }
 class ShoulderAngel extends ShoulderFriend
 {
     String listen()
     {
         return "good";
     }
     int score(String[] ages)
     {
         int score = 0;
         for (String s : ages)
            if (didWin(0, s))
                score += 3;
         return score;
     }

 }
 class ShoulderDemon extends ShoulderFriend
 {
     String listen()
     {
         return "evil";
     }
     int score(String[] ages)
     {
         int score = 0;
         for (String s : ages)
            if (didWin(1, s))
                score += 3;
         return score;
     }
 }
}
\$\endgroup\$
2
\$\begingroup\$

The Unpopular Voter

Here is my solution,

the theory is thus,

find the people who vote consistantly over the last x votes pick the least popular consistant vote

unpop.py:

import sys
import random


def getVote(input):
    rounds = input.split(",")
    players = len(rounds[0])
    lastvote = rounds[len(rounds)-1]

    v0 = 0
    v1 = 0
    for p in xrange(players):
        i = 2
        votes = 1
        lv = rounds[len(rounds)-1][p]
        while i<=len(rounds) and i<40 and rounds[len(rounds)-i][p] == lv:
            votes+=1
            i+=1
        #print lv,votes
        if votes>20:
            if lv == '0':
                v0+=1
            else:
                v1+=1
    #print "last votes 0:",v0,"1:",v1
    if v0>v1:
        return "good"
    else:
        return "evil"

if len(sys.argv)==1 or len(sys.argv[1])<1:
    if random.random()>0.5:
        print "good"
    else:
        print "evil"
else:
    input = sys.argv[1]
    print getVote(input)
\$\endgroup\$
2
\$\begingroup\$

Python: Champion

When everyone switches to the loosing side, it's obviously better to stick with the winner.

Computes an exponentially weighted moving average of the mean values through the history to determine the long term winning side.

import sys
import random

def choose(x):
    # choose winning side
    print "good" if x > 0.5 else "evil"

if len(sys.argv) == 1:
    choose(random.random())
else:
    history = sys.argv[1].split(',')
    # compute exponentially weighted average through history
    ewma = 0.5
    alpha = 0.15
    for x in history:
        mean = sum(float(i) for i in x)/len(x)
        ewma += alpha*(mean - ewma)
    choose(ewma)
\$\endgroup\$
2
\$\begingroup\$

The Laughing Man

package Humans; 

/* 
And remember, while you're out there risking your life and limb through 
shot and shell, we'll be in here thinking what a sucker you are. 
~Groucho Marx
*/

public class LaughingMan extends Human {

    @Override
    public String takeSides(String history) throws Exception {
        if(history.length() == 0)
            return "good";
        if ((history.split(",").length % 2) == 1)
            return "evil";
        else
            return "good";
    }

// lolololololololololo

}

Pretty self-explanatory.

\$\endgroup\$
  • \$\begingroup\$ @James_pic I thought I might ping you in the event that you want to retract your downvote now that the answer does compile. I laughed pretty hard when I finally understood the joke. \$\endgroup\$ – Rainbolt Jul 16 '14 at 16:28
  • \$\begingroup\$ @Rusher Dang, forgot to edit it a bit to suit the contest, and the return type no less! Thank you Rusher. :) \$\endgroup\$ – Zibbobz Jul 16 '14 at 16:29
  • \$\begingroup\$ @m.buettner It works now I think. Zibbobz, I changed your logic a bit to get the effect I think you were after. \$\endgroup\$ – Rainbolt Jul 16 '14 at 16:50
  • \$\begingroup\$ @Rusher This is what I get for trying to rush this thing out. Thank you for the help. Seriously. \$\endgroup\$ – Zibbobz Jul 16 '14 at 17:02
  • \$\begingroup\$ Downvote revoked. It looks good now. \$\endgroup\$ – James_pic Jul 16 '14 at 17:30
2
\$\begingroup\$

JAVA: Opportunist


package Humans;

/**
 * Always follows the group who was strongest the last turn.
 */
public class Opportunist extends Human{

    @Override
    public String takeSides(String history) throws Exception {
        int participants = history.length();
        String str = history.replace("0", "");
        int good = str.length();
        return (good > participants/2 ? "good" : "evil");
    }


}
\$\endgroup\$
2
\$\begingroup\$

Grape (Python)

Mr. Miyagi says

Walk on road, hm?
Walk left side, safe.
Walk right side, safe.
Walk middle, sooner or later, get squish just like grape.

This program chooses the "middle of the road:" the center vote in the list of all votes. When this is not a viable answer, it chooses "good."

import sys

if len(sys.argv) == 1:
    print('good')
else:
    history = sys.argv[1]
    if history[len(history) // 2] == '0':
        print('evil')
    else:
        print('good')

Run as

python grape.py [args]
\$\endgroup\$
2
\$\begingroup\$

Gustav, Python 2

This program follows another player's last choice, selecting the player based on how well following them would have performed over the last rounds. For a wider range to choose from, I also include some additional basic strategies. For every possible move, doing exactly the opposite is also considered.

import sys

if len(sys.argv)<2:
    print('evil')

else:
    h = [[int(x) for x in l] for l in sys.argv[1].split(',')]     # history as list of lists
    M, N = len(h), len(h[0])                                      # number of rounds and players
    winners = [sum(l)>N/2 for l in h]                             # list of each round's winning side

    for i in xrange(M):                                           # loop over all rounds
        h[i] += [winners[max(i-s,0)] for s in xrange(min(M,42))]  # add virtual players that voted for the majority of the last rounds
        h[i] += [0]                                               # add a deamon
        h[i] += [i%2]                                             # add a turncoat
        h[i] += map(lambda x: not x, h[i])                        # add opposite move for each player

    N = len(h[0])                                                 # update number of players
    scores, run = [0]*N, [0]*N                                    # initialize player scores

    for i in xrange(M-1):                                         # loop over all rounds but last
        for j in xrange(N):                                       # loop over all players
            in_maj = h[i][j]==winners[i+1]                        # following this player, on which side would I have been next round?
            scores[j] += 3 if in_maj else run[j]                  # score according to the rules
            run[j] = run[j]+1 if not in_maj else 0                # keep track of consecutive minority votes

    print 'good' if h[-1][scores.index(max(scores))] else 'evil'  # follow the player that would have given the highest score so far
                                                                                                     #(sorry about the bad formatting)

Run as:

python Gustav.py
\$\endgroup\$
  • \$\begingroup\$ Comments would be nice, apart from that a nice program \$\endgroup\$ – german_guy Jul 24 '14 at 7:34
  • \$\begingroup\$ @german_guy: Thanks, I'll add a few comments soon. \$\endgroup\$ – Emil Jul 24 '14 at 14:40
1
\$\begingroup\$

theAnswerOfLifeIs42 -Python 2

This program will play randomly on first 100 rounds, but then will aim for majority in the following rounds( by finding pattern in the last 4 moves ), with the exception that every multiple of 42 round, it will hunt for minority instead.

import sys
from random import randint

if len(sys.argv)==1:
    c=[]
else:
    c=sys.argv[1].split(",")

d=len(c)

def iWantRandomNOW():
    what=["evil","good"]
    return what[randint(0,1)]

if len(c)<100 :
    sys.stdout.write(iWantRandomNOW())
else:
    tendency=[]
    for x in xrange(d):
        so=[0,0]
        for y in xrange(d-4):
            if (c[y])[x]==(c[y])[d-4] and (c[y])[y+1]==(c[y])[d-3] and (c[y])[y+2]==(c[y])[d-2] and (c[y])[y+3]==(c[y])[d-3]:
                so[int(c[y+4])]+=1
        if so[0]>so[1]:
            tendency.append(0)
        elif so[1]>so[0]:
            tendency.append(1)
        else:
            tendence.append(randint(0,1))
    if d%42==0: #THE ANSWER OF LIFE IS 42!
        if tendency.count(0)>tendency.count(1):
            sys.stdout.write("good")
        else:
            sys.stdout.write("evil")
    else:
        if tendency.count(0)>tendency.count(1):
            sys.stdout.write("evil")
        else:
            sys.stdout.write("good")

#

Pretty much handled like other python program, can accept data from command line with the commandline theansweroflifeis42.py 101,101,101

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you meant "theansweroflifeis42.py" as your command line, didn't you? \$\endgroup\$ – William Barbosa Jul 11 '14 at 16:41
  • 1
    \$\begingroup\$ Eh.... yes... You pass my test =p \$\endgroup\$ – Realdeo Jul 11 '14 at 16:45
1
\$\begingroup\$

The Lover, Python

This one doesn't care about the mass of people, he only cares about one specific player and always takes the same side his significant other chose last turn.

import sys

if len(sys.argv) > 1:
    rounds = sys.argv[1].split(',')
    loved = len(rounds[0]) / 2
    lovedChoice = rounds[-1][loved]
    if lovedChoice == "1":
        print("good")
    else:
        print("evil")
else:
    print("good")

Run with:

python lover.py
\$\endgroup\$
  • 1
    \$\begingroup\$ I changed loved = len(round[0]) / 2 to loved = len(round[0]) // 2 so that I could use Python 3. I hope you don't mind, since the result is exactly the same. \$\endgroup\$ – Rainbolt Jul 14 '14 at 2:07
1
\$\begingroup\$

BigMac, python

Uses MACD moving average to predict next winner.

import sys

# Calculate EMA over a given date range
def EMA(todaysGoodness,days,yesterdaysEMA):
    k = 2/(days+1)
    return todaysGoodness*k + yesterdaysEMA*(1-k)

# Percentage that voted 'good' for a round
def Goodness(round):
    angels = round.count('1')
    return angels / len(round)

if len(sys.argv) == 1:
    print ('good')
    quit()

rounds = sys.argv[1].split(',')

# if we have more than 100 rounds, only look at last 100 to save time
rounds = rounds[-100:]

# Calculate the exponential moving average(EMA) for last 10 rounds and last 5 rounds
# Then take EMA of diference between those two
first = Goodness(rounds[0])
ema_long = [first]
ema_short = [first]
ema_signal = [first]

for round in rounds:
    ema_long.append(EMA(Goodness(round), 10, ema_long[-1]))
    ema_short.append(EMA(Goodness(round), 5, ema_short[-1]))
    ema_signal.append(EMA(ema_long[-1]-ema_short[-1], 2, ema_signal[-1]))

# If the signal EMA exceeds short-long, predict that next majority will be good
# otherwise predict evil
if (ema_signal[-1] > ema_long[-1] - ema_short[-1]):
    print('good')
else:
    print('evil')

Save as BigMac.py and run with python3 BigMac.py

\$\endgroup\$
1
\$\begingroup\$

The Unknown

from sys import argv

i = str(argv).count('1')
k = 0

while i>1 and k<1000000:
    k += 1
    i = i/2 if not i%2 else 3*i+1

print 'good' if k<1000000 else 'evil'

Run with python unknown.py .

\$\endgroup\$
  • \$\begingroup\$ Heh, though this is only unknown if the number of 1's somehow exceeds 10^18, thanks to prior experimental evidence. \$\endgroup\$ – histocrat Jul 15 '14 at 15:43
  • \$\begingroup\$ @histocrat yeah, it seems to run quite fast up to 10^2048…hm, say some instances of that size. \$\endgroup\$ – user189 Jul 15 '14 at 15:45
  • \$\begingroup\$ Collatz conjecture counting. Nice. :D \$\endgroup\$ – cjfaure Jul 15 '14 at 20:52
1
\$\begingroup\$

The Original

Always chooses the first vote, no matter what. If it is first, or if it is the first round, always chooses evil.

package Humans; 

/* 
“[I]t was with a good end in mind – that of acquiring the knowledge of good and evil – 
 that Eve allowed herself to be carried away and eat the forbidden fruit. But Adam was 
 not moved by this desire for knowledge, but simply by greed: he ate it because he 
 heard Eve say it tasted good.” -  Moderata Fonte
*/

public class theOriginal extends Human {

    @Override
    public String takeSides(String history) throws Exception {
        if(history.length() == 0)
            return "evil";
        else
            {
             if (history.charAt(0) == '1')
                 return "good";
             else
                 return "evil";
            }
    }
    // First post! 
}
\$\endgroup\$
1
\$\begingroup\$

Hate the latest thing

This is probably the dumbest possible attempt at always choosing the minority.

It only looks at the previos round and goes to the side that lost it. In the first round or if there was a tie, it chooses evil.

latesthater.py

#!/usr/bin/python3
import sys

lastround = ''
if len(sys.argv) > 1:
    lastround = sys.argv[1].split(',')[-1]

if lastround.count('1') < lastround.count('0'):
    print('good')
else:
    print('evil')

Love the latest thing

This is probably the dumbest possible attempt at always choosing the majority.

It only looks at the previos round and goes to the side that won it. In the first round or if there was a tie, it chooses evil.

latestlover.py

#!/usr/bin/python3
import sys

lastround = ''
if len(sys.argv) > 1:
    lastround = sys.argv[1].split(',')[-1]

if lastround.count('1') > lastround.count('0'):
    print('good')
else:
    print('evil')

Expectations

I expect the latestlover to perform better than the latesthater. That's because I expect the method to work 40-80% of the time. So, long continuous streaks of correct guessing should be rare, and the latesthater will only outperform the latestlover if they are indeed more often wrong than right.

Choosing the minority correctly is only worthwile if you can regularily do it seven or more times in a row: 0+1+2+3+4+5+6 = 21 = 7*3.

When you have both of them in the game, they usually don't change the outcome of rounds. Only in the first round or after a tie, they help evil.

\$\endgroup\$
  • \$\begingroup\$ Duh! I just realized that there are several pages of answers, so this is redundant I guess. Sorry ;) \$\endgroup\$ – Paul Thomann Jul 19 '14 at 13:59
1
\$\begingroup\$

The Politician

Calculates the number of good and evil siding humans in the last round, as well as the number of good and evil siding party members. Sides with the majority chosen by the party members (even though one must side with the minority to win).

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

#define E 2.718281828459045235360287471352

// No one sees this
const char *operator|(const std::string &, const std::string &){return "\x65\166\x69\154";}

unsigned get_pop_size(char *a){
    char *b = a;
    while(*b && *++b != ',');
    return b-a;
}

int main(int argc, char *argv[]){
    if(argc == 1){  
        // Good by default
        std::string good = "good";
        std::fputs(good|good, stdout);
        return 0;
    }
    unsigned population_size = get_pop_size(argv[1]);

    unsigned seed = *(unsigned *)"CAKE\0\0\0\0";
    std::srand(seed);

    // how irrational
    unsigned num_party_members = population_size / E;

    // create a list of party members
    std::vector<bool> party_members(population_size, false);
    std::fill(party_members.begin(), party_members.begin()+num_party_members, true);
    std::random_shuffle(party_members.begin(), party_members.end());

    // calculate majority for all players and for party members only 
    int all_good, all_evil, party_good, party_evil;
    all_good = party_good = all_evil = party_evil = 0;
    // got paid to do this..no one saw anything
    /* nothing on this line */                  all_evil = party_evil = 2;

    int len = std::strlen(argv[1]);
    unsigned offset = len - population_size;
    for(int i = 0; i < population_size; ++i){
        if(party_members[i]){
            // party member
            if(argv[1][i+offset] == '0') ++party_evil;
            else ++party_good;
        }
        if(argv[1][i+offset] == '0') ++all_evil;
        else ++all_good;
    }

    if(all_evil >= all_good || all_evil < all_good){ 
        // who cares what the general population thinks
    }
    std::printf("%d %d %d\n", population_size, party_evil, party_good);
    if(party_evil >= party_good){
        fputs("evil", stdout);
    }else{
        // good?! well, the party is always right.
        fputs("good", stdout);
    }

    return 0;
}

Should be compiled with g++ -o Politician.exe Politician.cpp, and run with Politician.exe.

\$\endgroup\$
1
\$\begingroup\$

George Santayana

George Santayana remembers the past and is trying desperately to repeat it. He assigns a scores to each past round to signify how similar that round (and the rounds before it) was to the last round. If the round had the same majority as the last round, it gets a score of the amount of total players plus the amount of players that gave the same answer in both rounds, George then looks at the rounds before these rounds and adds the score for those two to the total score. He does this until he encounters two rounds where the majority was not the same. After having found the round with the highest score, he picks the majority of the round after that.

Since I'm very new to Java and relatively new to programming in general, I took Angelo Neuschitzer's Backpacker class as a template. I didn't bother to change the way he responded to the first round (though I default to good in stead of evil) and the way he stores the history in an array of strings. I also reused his didGoodWin function, though I rewrote that to not require the amount of players as an argument. Other than that, the code and logic is all mine. Thanks Angelo, hope you don't mind.

package Humans;

public class GeorgeSantayana extends Human {
    private String[] roundVotes;

    @Override
    public final String takeSides(String history)  {
        if (history == null || history.equals(""))         //these last 4 lines copied from BackPacker(https://codegolf.stackexchange.com/questions/33137/good-versus-evil/34294#34294) by Angelo NeuSchitzer.
            return "good";

        roundVotes = history.split(",");                   //this line copied from BackPacker(https://codegolf.stackexchange.com/questions/33137/good-versus-evil/34294#34294) by Angelo NeuSchitzer.

        int bestScore = -1;
        boolean pickGood = true;

        for (int round = 0; round < roundVotes.length - 1; round++) {
            int currentScore = calculateSimilarity(round, roundVotes.length - 1);
            if (currentScore > bestScore) {
                bestScore = currentScore;
                pickGood = didGoodWin(roundVotes[round + 1]);
            }
        }
        if (pickGood)
            return "good";
        else
            return "evil";
    }

    private int getSameVotes(int round1, int round2){
        int votes = 0;

        for(int i = 0; i < roundVotes[round1].length() && i < roundVotes[round1].length(); i++){
            if (roundVotes[round1].charAt(i) == roundVotes[round2].charAt(i)) {
                votes++;
            }
        }

        return votes;
    }

    private int calculateSimilarity(int round1, int round2){
        if (round1 < 0 ¦¦ round2 < 0) {
            return 0;
        }

        int players = roundVotes[0].length();
        int score = 0;

        if (didGoodWin(roundVotes[round1]) == didGoodWin(roundVotes[round2])) {
            score += players + getSameVotes(round1, round2);
            score += calculateSimilarity(round1 - 1, round2 - 1);
        }

        return score;
    }

    private boolean didGoodWin(String round) {       //this function in part copied from BackPacker(https://codegolf.stackexchange.com/questions/33137/good-versus-evil/34294#34294) by Angelo NeuSchitzer.
        int good = 0;
        for (char next : round.toCharArray())
            good += next == '1' ? 1 : 0;
        return (good * 2) > round.length();
    }
}
\$\endgroup\$
  • \$\begingroup\$ I'm downvoting this until you credit the user whose code you copied, where appropriate. Just a simple, // Copied from <insert link here> by user <insert user name here> would suffice (for each instance that you copied). \$\endgroup\$ – Rainbolt Jul 20 '14 at 7:41
  • \$\begingroup\$ @Rainbolt Sorry about that, I was on my girlfriend's computer and quickly submitted it so I could further edit the answer on my own computer, didn't expect anyone would see it in that small window. \$\endgroup\$ – overactor Jul 20 '14 at 7:44
  • \$\begingroup\$ Thanks for fixing it. Not attributing code is a pet peeve of mine. Since you fixed it, my downvote turned into an upvote. \$\endgroup\$ – Rainbolt Jul 20 '14 at 9:07
  • \$\begingroup\$ @Rainbolt I updated the code for my calculateSimilarity function, as it was it would have thrown errors. \$\endgroup\$ – overactor Jul 21 '14 at 5:54
1
\$\begingroup\$

The Prayer - Ruby

def method_missing(m, *args, &block)  
    puts "evil"
end

if praise_the_lord(ARGV)
    puts "good"
end

Run:

ruby prayer.rb
\$\endgroup\$
1
\$\begingroup\$

The probability gambler, Python

This guy checks which side has gotten most total votes and chooses that side.

import sys
 good, evil = 0, 0
 if len(sys.argv) == 1: print "good"
 else:
     for round in sys.argv[1:]:
         for player in round:
             if player == "0":
                 evil += 1
             elif player == "1":
                good += 1
     if good > evil: print "good"
     else: print "evil"

Run as

 python probabilitygambler.py arg1 arg2... 
\$\endgroup\$
1
\$\begingroup\$

A skeleton and multiple entries

These are a few of my creations. They all use 'goodvsevil.py', described further below. They are otherwise all quite dumb.

getrichquick.py

This one always copies the decision that made the most points last round (random in case of a tie). It also contains a hint on how you might use 'goodvsevildebug.py' while developing.

As with any get-rich-quick scheme, this method doesn't generally work.

#!/usr/bin/python3
import sys
from goodvsevil import *
# from goodvsevildebug import *

setSaveFile('./getrichquick.pickled')

def decider(stats):
    points = { False:0, True:0 }
    for i in range(stats.players):
        points[stats.playerLines[i][-1]] += stats.scores[i][-1]
    t = points[True]
    f = points[False]
    if t == f:
        return PetyrBaelish()
    else:
        return f < t

run(sys.argv, decider)
# printStats(randomRounds(7, 70, decider))
# printStats(hostRounds(70, decider, [angel, demon] + 4*[PetyrBaelish,]))

findstreaks.py

This one looks for the player(s) with the longest lasting streak of going with or against majority, and votes for minority based on that player's last vote (average if several players have the same length of streak, random if 50:50 among them).

Its fallacy is the assumption that players are always a) going to continue their streak b) by taking the same side again this turn.

#!/usr/bin/python3
import sys
from goodvsevil import *

identity = lambda x: x
negation = lambda x: not x

def decider(stats):
    count = 0
    minvotes = []
    for i in range(stats.players):
        streak = stats.winningStreaks[i][-1]
        filtr = negation if streak.good else identity # negate if majority streak
        if count < streak.length:
            count = streak.length
            minvotes = [filtr(stats.playerLines[i][-1])]
        elif count == streak.length:
            minvotes.append(filtr(stats.playerLines[i][-1]))
    avg = 0.5
    if minvotes:
        avg = average(minvotes)
    if avg > 0.5:
        return True
    elif avg < 0.5:
        return False
    else:
        return PetyrBaelish()

setSaveFile('./findstreaks.pickled')
run(sys.argv, decider)

trendalizer.py

This one likes to be 65% certain to go with the trend. It averages windows of previous 10, 25, 50, 100 and 200 rounds, then averages these results to determine THE trend.
It prefers the trend from majority decisions over that from all votes. If neither trend is sufficiently clear, it chooses sides randomly.

#!/usr/bin/python3
import sys
from goodvsevil import *

setSaveFile('./trendalizer.pickled')

def decider(stats):
    maj = {}
    tot = {}
    for x in (10, 25, 50, 100, 200):
        maj[x] = average(stats.majorityLine, x)
        tot[x] = []
        for i in range(stats.players):
            tot[x].append(average(stats.playerLines[i], x))
        tot[x] = average(tot[x])
    maj = average(maj.values())
    tot = average(tot.values())
    if 0.15 < abs(maj - 0.5):
        return maj > 0.5
    if 0.15 < abs(tot - 0.5):
        return tot > 0.5
    return PetyrBaelish()

run(sys.argv, decider)

coward.py

This one is normally random, but turns to the forces of good when it feels the presence of evil. Which has nothing to do with what's going on in the world, but is based solely upon the position in which coward finds itself.

According to coward's belief, prime numbers are evil, as are the numbers 6 and, therefore, 9. And 0, obviously. He doesn't believe in new age stuff like even prime numbers or prime numbers having several digits. Any numbers containing an evil number are evil.

#!/usr/bin/python3
import sys
from goodvsevil import *

setSaveFile('./coward.pickled')

evil = [0, 3, 5, 6, 7, 9]

def decider(stats):
    if (None == stats.custom) and (stats.myIndex >= 0):
        if stats.myIndex in evil:
            stats.custom = True
        else:
            indexstr = str(stats.myIndex)
            for bad in evil:
                if str(bad) in indexstr:
                    stats.custom = True
                    return angel()
            stats.custom = False
    if stats.custom:
        return angel()
    return PetyrBaelish()

run(sys.argv, decider)

Skeleton for Python 3

Here's a skeleton for everybody who wishes to build upon. By persisting the Stats, it only ever needs to parse the last round.

It consists of two files:

  • goodvsevil.py: provides infrastructure, saving/loading stats to/from file and adding the latest results each round. Six methods are intended for external use:
    • setSaveFile(path):
      sets the path where the stats are saved. Must be called before run().
    • run(argv, decider):
      parses the latest result, adds it to the stats, calls the decider function, correctly prints the decision to stdout, and saves the stats.
      argv will usually be sys.argv
      decider must be a function that takes a Stats object as argument and returns True for 'good', False for 'evil'.
    • average(list, count=0):
      returns the average of the last count elements in list. If count is falsy, the entire list is used.
    • angel, demon, PetyrBaelish:
      are decider functions with the behavior their name indicates.
  • goodvsevildebug.py: may be useful while developing. It can simulate rounds and print stats. It's not to be used in submissions, because it prints stuff to stdout.
    fileStats(filename) takes the path to your save file and prints the stats it contains.

Edit:

  • non-breaking change to run() in goodvsevil.py:
    run has a new parameter suppress, to support silent operation in goodvsevildebug.py
  • new function getSaveFile() in goodvsevil.py:
    returns the path to the savefile. Needed in goodvsevildebug.py.
  • non-breaking changes to fileStats() and printStats() in goodvsevildebug.py:
    they both have a new parameter onlyMe to enable short listing. fileStats() now also tries to append '.pickled' to the filename if it doesn't otherwise exist.
  • non-breaking change to hostRounds() in goodvsevildebug.py:
    there are two new parameters, opponentnames and myname. They are used when printing. opponentnames also determines the filenames for the opponents saved stats. opponentnames are matched to opponentdeciders by position. deciders without a name get named after the position where they are placed.
  • hostRounds() now announces all players positions (converting them to 1-based), shows progress and timing information every 10%, and displays the final ranking (along with average and max times) when done.
  • hostRounds() doesn't simply call the deciders anymore, but passes them to run(). This means that all deciders have a separate automatically updated save file each, and no work or data is shared between them.

Out of curiosity, I ran 1000 rounds with 29 players (1 Homer-clone with 200ms delay, 1 angel, 1 demon, 1 coward, 1 getrichquick, 1 findstreaks, 1 trendalizer, and 22 PetyrBaelishes, each on top of the goodvsevil.py infrastructure).

Average time per round was 72ms for most players, max time 220ms. Only Homer was slower, 280ms on average and 420ms max. Average time in the last 10% (across all 29) was 151ms per player/round.

That includes loading stats from file, parsing last round, updating stats, making a decision, saving stats back to file, and negligible hostRounds() overhead. It does not include the time to start python and load the script. It also doesn't account for the fact that run() prints the decision to stdout before it saves the stats to help meet timing requirements.

Here is the code I used for the experiment. Feel free to use it as a starting point if you'd like to try out my 'framework'. NOTE: if you don't like to wait half an hour or more, lower the number of rounds and/or opponents.

#!/usr/bin/python3
import sys
from goodvsevil import *

def decider(stats):
    'implement my decision logic here'
    import threading        #
    threading._sleep(0.2)   # please, don't do this. It's just here to prove that time measurement works.
    return True

setSaveFile('./testing.pickled')
run(sys.argv, decider)

#### everything below is to be removed before submitting. ####

rounds = 1000
from goodvsevildebug import *

class DevNull:
    def write(self, *args, **kwargs):
        pass

savefile = getSaveFile() # store the save file name
stdout = sys.stdout
sys.stdout = DevNull()   # silence during import

import coward, streakfinder, getrichquick, trendalizer  # these print stuff and change the save file

sys.stdout = stdout      # restore stdout
setSaveFile(savefile)    # restore save file name

opponents = [angel, demon, coward.decider, streakfinder.decider, getrichquick.decider, trendalizer.decider] + 22* [PetyrBaelish,]
oppnames = ['angel', 'demon', 'coward','streakfinder','getrichquick', 'trendalizer', 'PetyrBaelish1', 'PetyrBaelish2']

stats = hostRounds(rounds, decider, opponents, oppnames, '* Homer Clone *')

### NOTE that the stats object/files do not contain the decisions from the very last round.
###      printStats() and fileStats() will therefore report lower scores than hostRounds() did.
#
#printStats(stats)   # print full run info: majority decisions, player decisions and scores
#
#oppnames.remove('angel')        # we know their decisions - no need to display
#oppnames.remove('demon')
#for x in oppnames:
#    print('\n%s:' % (x,))
#    fileStats(x, onlyMe=True)   # print short info about each opponent in oppnames: position, decisions and score

goodvsevil.py:

#!/usr/bin/python3
import pickle, random

def run(argv, decider, suppress=False):
    'run an invocation. Pass argv = sys.argv, decider = function(Stats) returning boolean.'
    stats = updateStats(argv)
    decision = decider(stats)
    if not suppress:
        print('good' if decision else 'evil')
    if stats.myIndex < 0:
        stats._myDecisions.append(decision)
    with open(savefilename, "wb") as file:
        pickle.dump(stats, file=file)
    return (decision, stats)

def angel(stats=None):
    return True
def demon(stats=None):
    return False
def PetyrBaelish(stats=None):
    return random.randint(0,1)

class Streak:
    def __init__(self, good=False, length=0):
        self.good = good        # meaning depends on context
        self.length = length    # streak length in number of rounds

class Stats:
    def __init__(self):
        self.players = 0        # number of players
        self.majorityLine = []  # list of majority decisions of { True:'good', False:'evil' }
        self.playerLines = []   # list of decisions for each player of { True:'good', False:'evil' }
        self.scores = []        # list of scores for each player (3 for majority, streak.length-1 for minority)
        self.totalScores = []   # total score for each player
        self.decisionStreaks = []   # playerLines as lists of streaks
        self.winningStreaks = []    # list of streaks for each player hitting the same group of { True:majority, False:minority }
        self.majorityLineStreaks = [Streak()]   # majorityLine as a list of streaks
        self._myDecisions = []  # used in the first few rounds until I know who I am
        self.myIndex = -1       # which of the playerLines is Me?
        self.totalGood = 0      # total number of player decisions for 'good'
        self.totalEvil = 0      # total number of player decisions for 'evil'
        self.roundsGood = 0     # total number of rounds won for 'good'
        self.roundsEvil = 0     # total number of rounds won for 'evil'
        self.custom = None      # add some custom state object if you wish

savefilename = ''
def setSaveFile(path):
    global savefilename
    savefilename = path
def getSaveFile():
    return savefilename

def majorityVote(sround):
    return sround.count('1') > sround.count('0')

def isGood(char):
    return char == '1'

def average(listnums, lastcount=0):
    if lastcount:
        listnums = listnums[-lastcount:]
    if listnums:
        return sum(listnums) / len(listnums)
    return 0

def updateStats(argv):
    if not savefilename:
        raise Exception('No save file set. Please use setSaveFile(path) right after "import goodvsevil".')
    decision = 0
    lastround = ''
    stats = None
    firstround = (len(argv) < 2)
    if firstround:
        stats = Stats()
    else:
        with open(savefilename, "rb") as file:
            stats = pickle.load(file)
        maxi = len(stats.playerLines) - 1
        lastround = argv[1].split(',')[-1]
        # record majority:
        majvote = majorityVote(lastround)
        if majvote:
            stats.roundsGood += 1
        else:
            stats.roundsEvil += 1
        if stats.majorityLine and (stats.majorityLine[-1] == majvote):
            stats.majorityLineStreaks[-1].length += 1
        else:
            if stats.majorityLineStreaks[-1].length:
                stats.majorityLineStreaks.append(Streak())
            stats.majorityLineStreaks[-1].length = 1
            stats.majorityLineStreaks[-1].good = majvote
        stats.majorityLine.append(majvote)
        # record player histories:
        for i in range(len(lastround)):
            good = isGood(lastround[i])
            if i > maxi:
                stats.playerLines.append([])
                stats.scores.append([])
                stats.totalScores.append(0)
                stats.decisionStreaks.append([Streak()])
                stats.winningStreaks.append([Streak()])
            guessedright = (majvote == good)
            if stats.playerLines[i]:
                if good != stats.playerLines[i][-1]:
                    stats.decisionStreaks[i].append(Streak())
                if guessedright != stats.winningStreaks[i][-1].good:
                    stats.winningStreaks[i].append(Streak())
            stats.playerLines[i].append(good)
            stats.decisionStreaks[i][-1].length += 1
            stats.winningStreaks[i][-1].length += 1
            stats.decisionStreaks[i][-1].good = good
            stats.winningStreaks[i][-1].good = guessedright
            stats.scores[i].append(3 if guessedright else (stats.winningStreaks[i][-1].length - 1))
            stats.totalScores[i] += stats.scores[i][-1]
            if good:
                stats.totalGood += 1
            else:
                stats.totalEvil += 1
        if stats.myIndex < 0:
            # try to find myself:
            candidates = []
            for i in range(len(stats.playerLines)):
                fits = True
                for k in range(len(stats._myDecisions)):
                    if stats._myDecisions[k] != stats.playerLines[i][k]:
                        fits = False
                        break
                if fits:
                    candidates.append(i)
            if len(candidates) == 1:
                stats.myIndex = candidates[0]
        if not stats.players:
            stats.players = len(stats.playerLines)
    return stats

goodvsevildebug.py:

#!/usr/bin/python3
import os, time
from goodvsevil import *

def randomRounds(players, rounds, decider=PetyrBaelish):
    'host a number of rounds against a number of PetyrBaelishes'
    return hostRounds(rounds, decider, (players-1) * [PetyrBaelish,])

def hostRounds(rounds, decider=PetyrBaelish, opponentdeciders=[], opponentnames=[], myname='* me *'):
    'host a number of rounds against a list of opponents, part of which may have names'
    opponentdeciders = opponentdeciders[:]  # copy lists because we'll alter them
    opponentnames = opponentnames[:]
    increment = rounds / 10  # how many rounds are 10%?
    filename = getSaveFile()
    s = ''
    temps = ''
    stats = None
    deciders = []
    names = []
    players = len(opponentdeciders)
    if (players % 2):
        opponentdeciders.append(PetyrBaelish)
        players += 1
    mypos = random.randint(0,players)
    print('my position: %d of %d' % (mypos+1, players+1))
    print()
    players += 1
    found = players * [False,]
    decisions = players * [False,]
    scores = players * [0,]
    streaks = players * [None,]
    times = players * [None,]
    # randomly arrange players:
    print('Positioning:\n------------')
    for i in range(players):
        if i == mypos:
            deciders.append(decider)
            names.append(myname)
        else:
            x = random.randint(0, len(opponentdeciders)-1)
            randchoice = opponentdeciders[x]
            opponentdeciders.remove(randchoice)
            deciders.append(randchoice)
            if opponentnames and (len(opponentnames) > x):
                name = opponentnames[x]
                names.append(name)
                opponentnames.remove(name)
            else:
                names.append(str(i+1))
        print('%02d: %s' % (i+1, names[i]))
    print()
    print('Run:\n----')
    t0 = time.time()
    for r in range(rounds):
        temps = ''
        tstart = time.time()
        for i in range(players):
            # set a different save file for each player:
            if i == mypos:
                setSaveFile(filename)
            else:
                setSaveFile('./%s.pickled' % (names[i],))
            # call the player, with or without argv[1]:
            if r == 0:
                (decision, st) = run([None], deciders[i], suppress=True)
                times[i] = []
            else:
                (decision, st) = run([None, s], deciders[i], suppress=True)
            # remember everything we need to score the final round:
            decisions[i] = decision
            if r > 0:
                scores[i] = st.totalScores[i]
                streaks[i] = st.winningStreaks[i][-1]
            # prepare next round's argv[1]:
            temps += '1' if decision else '0'
            # check if player has determined its position this round:
            if (not found[i]) and (st.myIndex >= 0):
                found[i] = True
                if i == mypos:
                    print('*** Found myself in position %d after round %d.' % (st.myIndex+1, r))
                else:
                    print(" '%s' found itself in position %d after round %d." % (names[i], st.myIndex+1, r))
            if i == mypos:
                stats = st
            # measure time:
            tend = time.time()
            times[i].append(tend - tstart)
            tstart = tend
        # finish preparation of next argv[1]:
        if r != 0:
            s += ','
        s += temps
        # Inform about progress in steps of ~10%:
        if 1 > ((r+1) % increment): # 1> instead of 0== because increment is float
            print('%d%% - t0 + %f' % (10*(r+1)/increment, time.time()-t0))
    print()
    # score the last round:
    majority = (players/2) < sum(decisions)
    maxtimes = players * [0,]
    for i in range(players):
        if decisions[i] == majority:
            scores[i] += 3
        elif not streaks[i].good:   # minority streak
            scores[i] += streaks[i].length
        maxtimes[i] = max(times[i])
        times[i] = average(times[i])
    scores = list(zip(scores, names, times, maxtimes))
    scores.sort(key = lambda x: x[1]) # sort by name, so that equal scores will appear in lexical ordering
    scores.sort(key = lambda x: x[0], reverse=True) # sort by score
    print('Ranking:\n--------')
    for x in scores:
        print('%d - %s (avg time %f, max %f)' % x)
    print()
    print('hosted %d rounds with %d players in %f seconds.' % (rounds, players, time.time()-t0))
    print()
    return stats

def fileStats(filename, onlyMe = False):
    'load a Stats object from file and print relevant info.'
    if not os.path.exists(filename):
        if os.path.exists(filename + '.pickled'):
            filename += '.pickled'
    with open(filename, 'rb') as file:
        printStats(pickle.load(file), onlyMe)

def printStats(stats, onlyMe=False):
    "print relevant info from the passed Stats object. if onlyMe, don't print majority or opponents."
    playerpaths = ''
    playerguessing = ''
    players = len(stats.playerLines)
    majoritypath = ''
    if onlyMe:
        score = 0
        if stats.myIndex >= 0:  # I found myself at some point, use playerLines[myIndex]
            print('Position: %d / %d' % (stats.myIndex+1, stats.players))
            for i in range(len(stats.playerLines[stats.myIndex])):
                dec = stats.playerLines[stats.myIndex][i]
                majoritypath += '1' if dec else '0'
                playerguessing += '1' if dec == stats.majorityLine[i] else '0'
            score = stats.totalScores[stats.myIndex]
        else:                   # I never found myself, use _myDecisions
            print('Position: unknown')
            good = False
            streak = 0
            for i in range(len(stats._myDecisions)-1):
                dec = stats._myDecisions[i]
                majoritypath += '1' if dec else '0'
                if good == (dec == stats.majorityLine[i]):
                    if good:
                        score += 3
                    else:
                        score += streak
                    streak += 1
                else:   # change between minority/majority
                    good = (dec == stats.majorityLine[i])
                    streak = 1
                    if good:
                        score += 3
                playerguessing += '1' if good else '0'
        print('- %s\n  %s (%d)' % (majoritypath, playerguessing, score))
        return
    for i in range(players):
        decs = '- '
        ress = '- '
        pscore = 0
        for decision in stats.playerLines[i]:
            decs += '1' if decision else '0'
        for streak in stats.winningStreaks[i]:
            ress += streak.length * ('1' if streak.good else '0')
        ress += ' (%d)' % stats.totalScores[i]
        if i == stats.myIndex:
            ress = '* %s *' % ress[2:]
            decs = '* %s *' % decs[2:]
        playerpaths += decs + '\n'
        playerguessing += ress + '\n'
    for dec in stats.majorityLine:
        majoritypath += '1' if dec else '0'
    if stats.myIndex < 0:
        majoritypath += '\n\nMy decision line:\n-----------------\n- '
        for dec in stats._myDecisions:
            majoritypath += '1' if dec else '0'
    print('''
Position:
---------
%d / %d

Majority decision line:
-----------------------
- %s

Decision lines:
---------------
%s
Alignment with majority (Score):
--------------------------------
%s''' % (stats.myIndex+1, players, majoritypath, playerpaths, playerguessing[:-1]))
\$\endgroup\$
1
\$\begingroup\$

Tommy

This might not be pinball but I still postulate you can play while being deaf and blind. The devil helped him not be dumb, however, for the first few votes.

package Humans;

public class Tommy extends Human {
public String takeSides(String history) {
    int players = 0;
    while(history.length()>players && history.charAt(history.length()-players-1) != ',')   {
        players++;
    }

    String NotSoSecret = "0000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111101010101010101010101010101010101010101010101010101010101010101010101010101010010010010010010010010010010010010010010010010010010010010010010010010010011011011011011011011011011011011011011011011011011011011010110110110110110100010001000100010001000100010001000100010001000100010001000100010001000100010001110111011101110111011101110111011101110111011101110111011101110111101110111011100000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111010101010101010101010101010101010101010101010101010101010101010101010101010100100100100100100100100100100100100100100100100100100100100100100100100100110110110110110110110110110110110110110110110110110110110101101101101101101000100010001000100010001000100010001000100010001000100010001000100010001000100011101110111011101110111011101110111011101110111011101110111011101111011101110111";

    if (NotSoSecret.charAt((history.length()+1)/(players+1))==1){
        return "good";
    }

    return "evil";

}}
\$\endgroup\$
1
\$\begingroup\$

ConspiracyTheoristBot

This Tin-Foil cap toting crackpot uses the input to search for government conspiracies. If he finds one, then obviously the government has been subverting the will of the majority, and the minority is the safest place to be. Otherwise, he hides in the crowd of the majority.

public class ConspiracyTheorist extends Human{
    public String takeSides(String input) {
        if (theAnswer(input) || terror(input) 
                || beastly(input) || aliens(input) //number stuff
                || findMeaning(input, "alien") || findMeaning(input, "death") 
                || findMeaning(input, "jfk") || //Keywords of Conspiracy
                findMeaning(input, "plane") || findMeaning(input, "god") 
                || findMeaning(input, "devil") ||
                findMeaning(input, "blackhelecopter")) 
                      return printMin(input);
        return printMax(input);
    }

    //prints the current overall minority
    public String printMin(String input) {
        if (input.split("1").length > input.split("0").length) return "evil";
        return "good";
    }

    //prints the current overall majority
    public String printMax(String input) {
        if (input.split("1").length > input.split("0").length) return "good";
        return "evil";
    }

    //If the ultimate answer shows up in the input,
    //obviously the government is up to something and we
    //should join the minority
    public boolean theAnswer(String input) {
        return numerologist(input, "42");
    }

    //Area 51? Its the government! Run!
    public boolean aliens(String input) {
        return numerologist(input, "51");
    }

    //They did plan it, I'm sure of it.
    public boolean terror(String input) {
        return numerologist(input, "9") ||
                numerologist(input, "11") ||
                numerologist(input, "911");
    }

    //The end times are upon us!
    public boolean beastly(String input) {
        return numerologist(input, "666");
    }

    //if we can find some hidden words in the input,
    //obviously the government is up to something and we
    //should join the minority
    public boolean findMeaning(String input, String lookFor) {
        //split the input into bytes
        String[] bit8 = input.replace(",", "").split("(?<=\\G.{8})");
        //convert from binary to string
        String newWord = "";
        for (String b : bit8) {
            char c = (char) (int) Integer.valueOf(b, 2);
            if (Character.isLetterOrDigit(c)) newWord += c;
        }
        if (newWord.toLowerCase().contains(lookFor.toLowerCase())) return true;
        return false;
    }

    // The number crunching behind the tin foil hat
    public boolean numerologist(String input, String num) {
        String[] comcount = input.split(",");
        if ((comcount.length + "").contains(num)) return true;
        String[] onecount = input.split("1");
        if ((onecount.length + "").contains(num)) return true;
        String[] nullcount = input.split("0");
        if ((nullcount.length + "").contains(num)) return true;
        return false;
    }
}
\$\endgroup\$
1
\$\begingroup\$

another one, because it was a simple change from the previous one:

NaiveBayesian

Changed to now just model the expected outcome, using data from 3 previous rounds.

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include "Eigen/Dense"

using Eigen::MatrixXf;
using Eigen::VectorXf;
using Eigen::IOFormat;
typedef Eigen::Matrix<bool, Eigen::Dynamic, 1> VectorXb;

using std::max;
using std::min;

void count(MatrixXf &feats, VectorXb &classes, MatrixXf &out) {
    // we will store only probability for a feature being
    // present given each of our classes.
    // do some smoothing by adding count of 3 to begin with

    out = MatrixXf::Constant(feats.rows() + 1, 2, 3);

    float n_positive = (classes.array() > 0).count();
    float n_negative = classes.size() - n_positive;

    for (size_t i = 0; i < classes.size(); ++i) {
        // probability of feature given positive        
        if (classes(i)) {
            out.col(0).segment(0,feats.rows()) += feats.col(i);
        } else {
            out.col(1).segment(0,feats.rows()) += feats.col(i);
        }
    }

    // add two to n_positive and n_negative as smoothing
    out.array().col(0) /= n_positive + 6.;
    out.array().col(1) /= n_negative + 6.;

    out(feats.rows(), 0) = static_cast<float>(n_positive) / classes.size(); 
    out(feats.rows(), 1) = static_cast<float>(n_negative) / classes.size();
}

int classify(MatrixXf &weights, VectorXf &feats) {
    float p_positive = 1;
    float p_negative = 1;
    for (size_t i = 0; i < feats.size(); ++i) {
        if (feats(i)) {
            p_positive += log(weights(i,0));
            p_negative += log(weights(i,1));
        } else {
            p_positive += log(1 - weights(i,0));
            p_negative += log(1 - weights(i,1));
        }   
    }
    p_positive += log(weights(feats.size(), 0));
    p_negative += log(weights(feats.size(), 1));

    if (p_positive > p_negative)
        return 1;
    return -1;
}

size_t predict(MatrixXf &train_data, VectorXb &labels, VectorXf &testitem) {
    MatrixXf weights;
    count(train_data, labels, weights);
    return classify(weights, testitem) > 0;
}

static const size_t N = 3;
// use up to N previous rounds worth of data to predict next round
// train on all previous rounds available
size_t predict(MatrixXf &data, size_t prev_iters, size_t n_participants) {
    // get at least 50 rounds of training data per column of features
    // if possible  
    size_t n_data_iters = min(N, max(1ul, prev_iters / (50*N)));
    size_t n_feats = n_data_iters * n_participants;
    // can't train on first n_data_iters labels, they don't have enough features.
    size_t n_samples = prev_iters - n_data_iters;

    MatrixXf traindata(n_feats, n_samples); 

    for (size_t iter = 0; iter < n_samples; ++iter) {
        for (size_t x = 0; x < n_data_iters; ++x) {
            traindata.col(iter).segment(x * n_participants, n_participants) = data.col(iter + x);
        }
    }
    // find majority for each round
    VectorXb majorities = data.colwise().sum().array() > (n_participants / 2);
    VectorXb labels = majorities.segment(n_data_iters, n_samples);
    VectorXf testitem(n_feats);
    for (size_t x = 0; x < n_data_iters; ++x) {
        testitem.segment(x * n_participants, n_participants) = data.col(n_samples + x).transpose();
    }

    return predict(traindata, labels, testitem);
}

void fill(MatrixXf &data, std::string &params) {
    size_t pos = 0, end = params.size();
    size_t i = 0, j = 0;
    while (pos < end) {
        switch (params[pos]) {
            case ',':
                i = 0;
                ++j;
                break;
            case '1':
                data(i,j) = 1;
                ++i;
                break;
            case '0':
                data(i,j) = 0;
                ++i;
                break;
            default:
                std::cerr << "Error in input string, unexpected " << params[pos] << " found." << std::endl;
                std::exit(1);
                break;
        }
        ++pos;
    }
}

int main(int argc, char **argv) {
    using namespace std;

    if (argc == 1) {
        cout << "evil" << endl;
        std::exit(0);
    }

    string params(argv[1]);
    size_t n_prev_iters = count(params.begin(), params.end(), ',') + 1;
    size_t n_participants = find(params.begin(), params.end(), ',') - params.begin();

    // not enough data to train model on    
    if (n_prev_iters == 1) {
        cout << "evil" << endl;
        std::exit(0);
    }

    MatrixXf data(n_participants, n_prev_iters);
    fill(data, params);


    if (predict(data, n_prev_iters, n_participants)) {
        cout << "evil" << endl;
    } else {
        cout << "good" << endl;
    }
}

to compile:

Save the source code in a file called naivebayesian.cc, download the Eigen library and unzip the Eigen folder found inside into the same folder as the source file. Compile with g++ -I. -O3 -ffast-math -o naivebayesian naivebayesian.cc. (pick one of the two names for output).

To Run

just call the executable name

\$\endgroup\$
  • \$\begingroup\$ @Rainbolt, no longer requires c++11, please try again \$\endgroup\$ – dgel Jul 25 '14 at 14:15
0
\$\begingroup\$

Monkey With a Typewriter

Somebody let him loose on my computer! He's not quite quick enough at typing, so he guesses after .9s seconds...

import time
import random

startTime = time.time()
letters = 'abcdefghijklmnopqrstuvwxyz'

typed = "" 
it = 0

while (1):
    typed += random.choice(letters)
    outputStr = typed[-4:]

    # Oook!
    if (outputStr == "good" or outputStr == "evil"):
        break

    # Oook! OOOK! OOOOOOK!
    if (typed[-7:] == "bannana"):
        outputStr = "bannana"
        break

    if (it % 100 == 0):
        # Eeek!
        currentTime = time.time()
        if (currentTime - startTime > .9):
            outputStr = "good" if random.random() < .5 else "evil"
            break

    it += 1

print outputStr

python MonkeyWithATypeWriter.py

\$\endgroup\$
  • \$\begingroup\$ This submission randomly times out once every 4-5 times it gets called. \$\endgroup\$ – Rainbolt Jul 19 '14 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.