Results from the Prisoner's Dilemma Challenge

The Iterated Prisoner's Dilemma Challenge is now closed; several interesting solutions have been submitted.

Of the basic strategies, tit-for-tat (doing what the opponent did the last time, starting off with cooperating) is usually the strongest. Since the random strategy is, well, random, the results fluctuate a bit.

Most submitted strategies are a variation on tit-for-tat, modified in some way or another to make it stronger. All submissions contained a strategy that is stronger than tit-for-tat when tested against the basic strategies only, though the interaction with other new strategies made some of them come out weaker than tit-for-tat.

Submitted Strategies

Without any further ado, here are the strategies and a few comments on them.

Turn the Other Cheek

## Dean Serenevy; received on 2012-02-07
%strategies<turn-other-cheek-no-deal-with-devil-once-bit-twice-shy-variety-is-the-spice-o-life> = sub (:@mine, :@theirs, *%) {
    my ($bitten, $shy, $they-coop) = (0, 0, False);

    for @mine Z @theirs -> $me, $them {
        if $them          { $they-coop = True; }
        if $me and !$them { $bitten++; $shy = 0; }
        if !$me           { $shy++ }
    }

    return True  if 0 == $bitten;               # Cooperate if we have never been bitten
    return True  if 1 == $bitten and 0 == $shy; # Turn the other cheek once
    return False unless $they-coop;             # Screw you too!
    return $shy >= (2 ** ($bitten-1)).rand      # Once-bitten rand() shy
};

Inevitable Betrayal

## Andrew Egeler, received 2012-02-09

%strategies<inevitable-betrayal> = &inevitable-betrayal;
sub inevitable-betrayal (:@theirs, :$total, *%) { +@theirs <
($total-1) ?? @theirs[*-1] // True !! False }

%strategies<evil-inevitable-betrayal> = &evil-inevitable-betrayal;
sub evil-inevitable-betrayal (:@theirs, :$total, *%) { +@theirs <
($total-1) ?? @theirs[*-1] // False !! False }

These are variations on tit-for-tat and evil-tit-for-tat which always defect in the last round, because then the opponent can't retaliate anymore.

In a typical Iterated Prisoner's Dilemma contest, strategies don't know how many rounds are being played, just to avoid this behavior.

Tit for D'oh and Watch for Random

## Solomon Foster, receievd 2012-02-10

%strategies<tit-for-doh> = -> :@theirs, :$total, *% {
    @theirs < $total - 1 ??  (@theirs[*-1] // True) !! False
}

%strategies<watch-for-random> = -> :@theirs, *% {
    @theirs > 10 && @theirs.grep(* == False) > 5 ?? False !! (@theirs[*-1] // True)
};

tit-for-doh is the same as inevitable-betrayal. watch-for-random defects forever once the opponent has defected too often.

Me

## Audrey Tang, received 2012-02-17
%strategies<me> = -> :@theirs, *% {
    my role Me {};
    (@theirs[*-1] // Me).does(Me) but Me
};

This strategy uses a mixin in its returned boolean values to find out when it plays against itself, or against a strategy that copies its values from @theirs (ie tit-for-tat derivatives), in which case it cooperates. This games the system, though doesn't explicitly violates the stated rules.

Audrey also deserves two dishonorable mentions for two solutions that game the test harness or the other strategies by exploiting the technically imperfect sandboxing:

   au => -> :@theirs, *% {
       use MONKEY_TYPING;
       my role TRUE {};
       augment class Bool {
           method Stringy(Bool:D:) {
               self.^does(TRUE) ?? 'True' !! 'False'
           }
       }
       False but TRUE;
   }, 

   amnesia => -> :@mine, :@theirs, *% {
       my role Uh {};
       my $rv = (@theirs[*-1] // Uh).does(Uh) but Uh;
       @mine = @theirs = ();
       $rv;
   },

Those two strategies did not compete in the tournament

Lenient in the Beginning, Then Strict

I've written my own two strategies before the tournament started. Here is the original, I've only changed the signatures to run under current Niecza:

# a tit for tat, but a bit more friendly at the beginning
# to avoid hacking on forever on evil-tit-for-tat,
# but be very stringent when the other one defects too often
sub moritz-ctft(:@theirs, :$total,  *%) {
    return True if @theirs < 3;
    return False if @theirs.grep(*.not).elems > ($total / 10);

    @theirs[*-1];
};
%strategies<moritz-ctft> = &moritz-ctft;

# the evil clone...
sub moritz-ectft(:@theirs, :$total,  *%) {
    return True if @theirs < 3;
    return False if @theirs.grep(*.not).elems > ($total / 10);
    # did you believe in happy ends?
    return False if @theirs + 1 == $total;

    @theirs[*-1];
};
%strategies<moritz-ectft> = &moritz-ectft;

Results

The results vary quite a bit between runs, mostly because of the random strategy.

Here is the output from a sample run. Please don't use this for determining the "winner", because it is just a random sample with no statistical significance.

SUMMARY
2588    moritz-ectft
2577    me
2560    moritz-ctft
2491    inevitable-betrayal
2483    tit-for-tat
2480    tit-for-doh
2399    turn-other-cheek-no-deal-with-devil-once-bit-twice-shy-variety-is-the-spice-o-life
2319    watch-for-random
2272    good
1876    evil-inevitable-betrayal
1862    evil-tit-for-tat
1538    random
1145    bad

You see, inevitable-betrayal and tit-for-doh are exactly the same strategy, but the random fluctuations place them on different sides of tit-for-tat. Which is why I won't declare a winner at all, there is simply no fair way to determine one.

At first I was surprised how well the me strategy performed. But then I noticed that with the given game harness, a strategy fighting against itself counts double (once for the first copy, once for the second copy). With only 13 strategies participating, and such close results, harmonizing perfectly with yourself gives you a critical advantage.

Visualizations

For each strategy you can find an image that shows how it worked with or against another strategy. Green means cooperate, red means defect, and the height of the bar is proportional to the resulting score.

Trying to Be Fair

In an attempt to reduce the impact of the random strategy, I've changed it to use the same random sequence against each player (and of course against itself, which totally skews that particular result).

Again the rankings vary between different runs of the same program, but now at least same strategies produce mostly the same result (turn-the-other-cheek also has a random component). An example output from such a run is

SUMMARY
2558    moritz-ectft
2543    moritz-ctft
2532    me
2457    inevitable-betrayal
2457    tit-for-doh
2445    tit-for-tat
2387    turn-other-cheek-no-deal-with-devil-once-bit-twice-shy-variety-is-the-spice-o-life
2314    watch-for-random
2248    good
1856    evil-inevitable-betrayal
1844    evil-tit-for-tat
1359    random
1100    bad

TL;DR

It was a lot of fun! Thanks to everybody who submitted a strategy.

[/perl-6] Permanent link

Categories

Posts in this category

Sat, 18 Feb 2012