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
%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;
return True if 1 == $bitten and 0 == $shy;
return False unless $they-coop;
return $shy >= (2 ** ($bitten-1)).rand
};
Inevitable Betrayal
%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
%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
%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:
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;
sub moritz-ectft(:@theirs, :$total, *%) {
return True if @theirs < 3;
return False if @theirs.grep(*.not).elems > ($total / 10);
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.
