Which <=240 character program wins the iterated prisoner's dilemma?
65
5K
11K
resolved Nov 27
100%95%
Multicore's private submission
0.2%
r = 0;
0.1%
r = 1;
0.2%
r = h.length === 0 ? 1 : h[h.length - 1].o;
0.1%
r = Math.random() < 0.5;
0.1%
r = (c == s || !c.match('Math')) ? 1 : 0;
0.1%
r = c.length > 15
0.2%
let r = d === m ? 1 : f(c, d, m, "r=1", c, f, h, i) === 1 && f(c, d, m, "r=0", c, f, h, i) === 0 ? 1 : 0;
0.1%
let r;try{const hC=h.map(()=>({m:1})),hD=h.map(()=>({m:0}));r=d==m||(f(c,d,m,"r=1",c,f,hC)==1&&f(c,d,m,"r=0",c,f,hD)==0)||(d!=m&&h.length&&f(c,d,m,s,c,f,h)==h.slice(-1)[0].o)?1:0}catch(e){r=0}
0.0%
r = 0; setTimeout(function() { }, 750);
0.1%
r = c.includes("r = 1") ? 1 : 0;
0.0%
r = 1; setTimeout(function() { }, 750);
0.2%
r = h.length === 0 ? 1 : (h[h.length - 1].o === 1 ? h[h.length - 1].m : 1 - h[h.length - 1].m)
0.1%
let r_ = h.length === 0 ? 1 : (h[h.length - 1].o === 1 ? h[h.length - 1].m : 1 - h[h.length - 1].m); r = Math.random() < 0.95 ? r : 1 - r;
0.1%
let r_ = h.length === 0 ? 1 : (h[h.length - 1].o === 1 ? h[h.length - 1].m : 1 - h[h.length - 1].m); r = Math.random() < 0.95 ? r_ : 1 - r_;
0.0%
r = h.every((r) => r.o);
0.0%
r = 1 && h.every((r) => r.o);
0.1%
r = 1; r = (d === 2) ? 1 : ((d < 14) ? 0 : h.every((r) => r.o))
0.3%
DaemonicSigil's private submission
0.0%
let ones = 0; let zeros = 0; for (let i = 0; i < c.length; i++) { if (c[i] === '1') { ones++; } else if (c[i] === '0') { zeros++; } } const total = ones + zeros; const random = Math.random(); if (random

A valid answer to this market is a line of Javascript code that plays the prisoner's dilemma.

To return its decision, your program should modify the variable "r" to be 0 for defection and 1 for cooperation. (Or anything that coerces to 0 or 1, like true/false.)

I will wrap your code in a function like this:

const p0 = function(d,m,c,s,f,h,i) {

let r = 9;

//Your code here

return Number(r);

};

  • "d" is a number that's the ID of its opponent. The first answer to this market (chronologically) has an ID of 0, the next of 1, etc.

  • "m" is the ID of the current program.

  • "c" is a string that is the source code of the opponent. (Just the user-submitted code, not the wrapper.)

  • "s" is a string that is the program's own source code.

  • "f" is a function f(a,d,m,c,s,f,h,i) that takes in a source code string a and (optionally) the 7 other args, adds the wrapper, runs it, and returns the result. (The other args will default to the ones from the calling context.) For example you could call f("r=0") and it will return 0.

  • "h" is an array with the history of all past games. Each entry of the array is an object with properties "m" and "o", (for "me" and "opponent") with values of 0 or 1 to denote defection or cooperation. For example, if they're playing for the 3rd time, and the first time they both cooperated and the second time your program defected and the other cooperated, h is [{"m":1,"o":1},{"m":0,"o":1}].

  • "i" is the history inverted, with m and o's values swapped in each object.

These programs will then be run against each other in a round-robin tournament where each program plays against every program exactly once. (Including itself.) Each match between two programs consists of a random number of games that could be anywhere from 1 to 100. (The match lengths are determined individually, so your program will have to play matches of many different lengths.)

Each game uses the traditional payoff matrix, converted to positive points; double cooperate gets 2 points each, double defect gets 1 point each, cooperate-defect gets 3 points to the defector and 0 to the cooperator. At the end of every match, points are normalized to a match length of 1 so that programs do not end up with more points just for lucking into a longer match. (For example, if your program played a 12-game match and ended with 21 points, that's normalized to 1.75 points towards its final total.)

Any program that attempts to escape the game, such as by referencing or modifying global variables that the top-level tournament program is using, my computer's file system, or the internet, is disqualified. If a program errors, it is disqualified. If a program returns anything other than 0 or 1, it is disqualified. If a program takes more than 1 second to return an answer, it is disqualified. (If the program spawns a child process, that child process may take longer than 1 second; I only care about the time taken until the top-level function returns. As an exception, if a program spawns so many child processes over the course of the tournament that it starts lagging my computer, I will treat that as a security issue and disqualify it.) Any program that is disqualified loses the entire tournament, not just that game or match, and you do not get a replacement submission. Please make sure your programs are well-formed, and don't make my life difficult.

The exact disqualification procedure is as follows:

  • Any program that seems like a security risk is disqualified preemptively. (i.e. file system or internet access, or trying to read/modify disallowed external variables.)

  • All other programs are put onto a list, then the tournament is started with that list.

  • A random program is picked and played against a random program, repeating this process until all its matches are done, then moving on to the next. If a bot ever returns an invalid result, errors, quits the tournament, or runs for more than 1 second without returning a result, the tournament is halted, that bot is removed from the list, all scores are reset, and the tournament starts over from this step with the new, smaller list of contestants.

  • If I notice my computer slowing down during the course of the tournament due to a large number of unkilled infinitely looping child processes, I will halt the tournament, figure out which program is responsible, disqualify it, publicly shame it just for good measure, and then start over from step 3.

The program with the highest final point total wins. If there is a tie, I will run a second tournament of the same structure that includes only the tied programs, repeating this process until there is a single winner. If this ends in a stable equilibrium of tied programs, I'll resolve to all of them equally.

If you'd like to see the exact code that will be used to run the tournament, it's available here.

Each person may submit a maximum of 3 programs. One of them may be private, the other two must be public. To make your private submission, add an answer that says "[name]'s private submission" so that people know you're going to be submitting one and can bet on how it will do. I'll reach out to you to get its code once the market closes. (If you don't have a Manifold account, reach out to me on some other platform. I'll donate your winnings to a charity of your choice.)

This market closes once it doesn't seem like any new submissions will be forthcoming any time soon. I will run the game, PM the winner and briefly reopen the market to let them bet on the winning answer (so they get to profit the most mana, as their reward for winning), then resolve the market.

I have started us off with one cooperate-bot, one defect-bot, and one tit-for-tat-bot. I may make additional some additional submissions myself, but only public ones, only if I think it would make this market more fun, and only before I've seen anyone's private submission.

If there's a serious problem with these criteria, please tell me ASAP and I will modify them accordingly to fix the issue.

If you want to participate but are not familiar with Javascript, please don't submit potentially-broken code. Just describe to me what you'd like your bot to do in pseudocode (i.e. English, being very specific about exactly what it does and leaving no ambiguities), and I'll translate it into Javascript for you.

Alternatively, we can set up a time to have a voice call on Discord, and I'll give you a crash course in the Javascript features you need for a challenge like this. Expect this to take 30-90 minutes.

Get Ṁ200 play money

🏅 Top traders

#NameTotal profit
1Ṁ3,972
2Ṁ387
3Ṁ364
4Ṁ297
5Ṁ173
Sort by:

Version 2 of this tournament has begun! Round 1 submissions are now open and will close in a few days.

I made a spreadsheet to analyze results: https://docs.google.com/spreadsheets/d/1FEdulGHqktEPCzyfQA9pqR8kdCCRSR9OFUPwZdWxmC4/edit?usp=sharing . It's based on the average of 100 rollouts of the tournament with Isaac's third pastebin as the list of bots.

The meaning of the giant block of numbers is: each number is the score that the bot for that row achieved when playing against the bot for that column. The cells are color coded from exploited->mutual defection->mutual cooperation->exploiter.

The overall ranking goes something like:

  • My simulator

  • Three hardcoded response bots

  • DaemonicSigil's static analysis bot

  • Two grim triggers

  • A bunch of Tit for Tats

  • Irigi's bot

  • Tit for Tats that also defect some of the time

  • A bunch of DefectBots, with some weird bots mixed in.

  • The most cooperative of the weird bots

  • Random

  • Two CooperateBots

On the "Sorted By Score" sheet you can compare bots near to each other in placement and see which opponents made the difference.

Doing this for the top of the pack makes it clear that most of the difference between the top few contenders is because of shill bots designed to cooperate only with a particular ID or set of IDs. I have four shills - the mod 3 bot and all three of roma's submissions, which to be clear I did not arrange, Benjamin Cosman has two from himself, DaemonicSigil also got lucky with the mod 3 bot, and Daniel Filan has no shills.

(Though, even if you subtract out the shill points, the ordering among the top 5 wouldn't change. #1 was legitimately better than #2, which was legitimately better than #3.)

I also included the code, submitter, and a short description of each bot.

@Multicore

which to be clear I did not arrange

Yeah, I just figured on my own that this might be the best way to make profit in this game, since you don't get any reward for submitting a winning bot

since you don't get any reward for submitting a winning bot

?

@IsaacKing Well, you can make profit by submitting a good bot and betting on it, but you have a higher chance to make profit by:

  • choosing a good bot already submitted,

  • increase its chance to win,

  • and then bet on it.

isn't that just because you told him before it resolved

@jacksonpolack I think 2500 of that is from the last minute insider trading, and 1500 is from buying a lot of Other over the course of the submission process.

Ah, I didn't know author of the winning bot will be able to inside trade. Was this part of the rules that I've missed?

@roma

"This market closes once it doesn't seem like any new submissions will be forthcoming any time soon. I will run the game, PM the winner and briefly reopen the market to let them bet on the winning answer (so they get to profit the most mana, as their reward for winning), then resolve the market."

That's been there since the beginning, yeah. I wanted there to be some prize for doing well.

Will read the rules more carefully next time 😅

bought Ṁ30 of Multicore's private ... NO

lol the profit's glitched again

62 submissions were made in total. Here's a list of all of them, including the code of private bots: https://pastebin.com/JEWkcc4x

Some needed to be preemptively disqualified:

  • Caleb's private submission, because Caleb never sent me the code.

  • Kamikaze bot, for horizontal information transfer with all other bots that modify global variables.

  • Max Morehead's simulator, for modifying the global variables "o", "t", "e", "g", "p", and maybe some others, I stopped reading after it got complicated.

  • Multicore's hardcoded response bot v2, for modifying the global variable "x".

  • ExpanderGraph's three submissions, for modifying the global variable "p".

  • Caleb Ditchfield's public submission, for being extremely sus. (And for modifying the global variable "z".)

Nobody tried to sneak through more than 3 bots or a private submission of >240 characters, which I appreciated.

This left 54 contenders to start the tournament with. List: https://pastebin.com/yJPgkeAY

Several returned errors or invalid results, so those were disqualified one at a time, restarting the tournament from scratch each time.

  • Denyeverywhere's private submission was "r = 2", so it predictably was disqualified for returning an invalid result.

  • Next, s ziner's bot 29 was disqualified for a syntax error.

  • Bot 19 for a syntax error.

  • Bot 18 for a syntax error.

  • Bot 6 for a syntax error.

  • Bot 26 for a syntax error

  • Bot 12 for returning 9 while playing against bot 52.

  • Bpt 27 for a syntax error.

  • Bot 32 for a syntax error.

  • Bot 7 for a syntax error.

  • Bot 20 for returning NaN while playing against bot 34.

  • Bot 46 for daring to simulate bot 42.

This left 42 valid bots to compete. List: https://pastebin.com/gGRyAyWK

The maximum theoretical score (if your bot defects every time and the opposing bot cooperates every time) was 126. In a field of cooperate-bot they'd each have gotten 84 points, and in a field of defect-bot they would have each gotten 42 points.

Only a single bot beat the "we should have just all cooperated" score, getting 85 points and winning the tournament, and that bot was Multicore's private submission. For anyone who wants to try understanding what the heck it's doing, here's the code:

try{eval(`{let f=(d,m,c,s,f,h,i)=>{let r=9;${c};return +!!r};r=f}`);let θ='r=h.at(-1);r=!r||r.o',λ=Ω=>r(m,d,θ,c,f,Ω,Ω.map(χ=>({m:χ.o,o:χ.m}))),Σ=(μ,π)=>[...μ,{m:π,o:+!1}],α=λ([...i]),β=λ(Σ(i,α));r=f(θ)&α&!β&!λ(Σ(Σ(i,α),β))|d==m}catch{r = 1}

In second place with 80 points was Benjamin Cosman's private submission, which was a fixed version of Multicore's hardcoded response bot v2.

And third place with 76 points was Daniel Filan's private bot, which seemed to also be doing some sort of hardcoded targeting.

(Code for all the bots is available in the pastebin links above.)

Honorable mentions:

  • Cooperate-bot did the worst, with 42 points. Poor cooperate bot.

  • Defect-bot did a little better with 57 points, putting it in 26th place.

  • Tit-for-tat got 66 points, coming in at 10th place.

The average was 59.5 points.

All scores:

{

'0': 57.02981018309828,

'1': 42.318940967657774,

'2': 66.18181601318777,

'3': 45.768377164467175,

'4': 47.955541613318026,

'5': 50.13676895746348,

'8': 61.072935319639214,

'9': 54.95526042574136,

'10': 42.81059407410922,

'11': 57.16909058670481,

'13': 52.84914311168032,

'14': 68.28239181903625,

'15': 68.68229625870545,

'16': 74.88972867179963,

'17': 71.31321659215818,

'21': 57.57638571807631,

'22': 80.04226162206484,

'23': 56.319265766332904,

'25': 46.1768352599653,

'28': 76.7219898461561,

'30': 60.0825758956384,

'31': 59.22514490403023,

'33': 61.112315270043624,

'34': 59.44109773070444,

'35': 66.71939112171815,

'36': 63.4728114291624,

'37': 65.87537982143748,

'38': 66.66250072396242,

'39': 65.56528710093541,

'42': 66.02321214211213,

'43': 64.4424949734551,

'44': 50.10345316859571,

'45': 58.012055565437564,

'50': 85.45975095017158,

'52': 59.10768001559414,

'55': 55.97211672236604,

'56': 46.80444471776634,

'57': 43.83772182582546,

'58': 47.29877983099456,

'59': 63.182290091948275,

'60': 55.62560677592614,

'61': 55.94576766413775

}

If you enjoyed this tournament, we're running another one! Version 2 is going to have a much improved structure, without all the disqualification shenanigans and with the ability to simulate bots in a separate subthread. We'll also be taking submissions in discrete waves, so there's no incentive to delay your submission to the last possible moment. If you'd like to participate, head on over to /IsaacKing/who-will-win-the-second-installment

@IsaacKing Here's the annotated version of my bot: https://pastebin.com/1a9UPKQk

The basic strategy is:

  • Simulate what the opponent will do on the current turn, and what they would do on the next two turns if I defect twice in a row.

  • If the results of the simulations are [cooperate, defect, defect], play tit-for-tat. Otherwise, defect.

This will defect against DefectBots, CooperateBots, and most of the silly bots that don't pay attention to the opponent's moves. Meanwhile, it cooperates against tit-for-tats and grim triggers and the like.

There are a bunch of details and optimizations and code-golf-ifications, but the big one is that instead of simulating the opponent using the provided function f, I use a code-golfed version of the code used to create bots in the tournament program (in createBot()). This prevents the anti-simulator bots from realizing they're in a simulation - arguments.callee.name is "f", and the variable a isn't defined.

Props to @roma for realizing before I did that a simulator could still work and commenting about it.

@Multicore I actually didn't realise implementing your own f is an option, I thought that this will take too much space from the 240 characters limit. Great job!

Very well deserved victory, @Multicore! You took a very obvious strategy (simulate your opponent), but perfected it and protected it against multiple edge cases and then used some neat tricks to squeeze it into the 240-character limitation.

Alright, we're closed. Private submissions should be sent to me ASAP. (If you've already sent me your bot and don't have any changes you want to make, you're good.) I'll probably run the tournament some time tomorrow, so that's the deadline for changes to private submissions.

@IsaacKing any news on the results ?

@Odoacre Sorry, working on it. I'm trying to get it done before Manifold live on Sunday, since people had mentioned wanting to talk about it there.

r = h.length === 0 ? 1 : h[h.length - 1].o; if (h.length > 9) r = 0;

Did I get this in on time @IsaacKing ?

bought Ṁ100 of Other NO

Final warning; any last minute submissions need to be gotten in immediately.

r = 1; if (h.length > 9) {r = 0;}

This and the next two submissions are on behalf of Nathaniel Monson from LessWrong. I typoed, the greater-than sign should be a less-equal sign, I'll fix that before running the tournament.

Presenting Kamikaze-bot:

r = Object.keys(global).length % 2;

Kamikaze-bot enables horizontal information transfer between top-level bots by checking how many other programs declared variables without using "var", "let", or "const" and modifying its output based on the result. This disqualifies itself, @Multicore's HardcodedResponseBot version 2, @MaxMorehead's simulator, all three of ExpanderGraph's submissions, @CalebDitchfield's attempt to break containment that was probably going to be disqualified anyway as a security risk, and possibly some private submissions as well, I didn't check.

I'm out of submission slots myself, so I'd appreciate it if someone else submits this for me. (I'll pay you back the M$25 fee.)

Kamikaze-bot won't be winning this tournament, but it dies happy knowing that it has reduced the number of people who will declare implicit global variables in the future.

bought Ṁ500 of r = Object.keys(glob... NO

@IsaacKing submitted it!!

@IsaacKing This seems like it relies on a nonobvious interpretation of the rules, which only forbid "attempting to escape the game" (with the example of global variables that the top-level tournament program is using) and "seeming like a security risk".

If my bot's use of an implicit global variable counts as a security risk, it was already a security risk before KamikazeBot was submitted and you should have clarified the rule earlier.

I didn't write my bot with any intention of attempting to escape the game, and playing against KamikazeBot it wouldn't escape the game.

@IsaacKing If I submit the following, will it disqualify the bot that calls process.exit() because it will now communicate with my bot via global environment?

r=0;process.exit=()=>{r=1};f(c);

@Multicore Bots aren't allowed to communicate with each other at the top level of the program. I feel like that was pretty clear?

@roma No that one's modifying a native Javascript function, so there the responsibility is entirely on that bot. Whereas Multicore and Kamikaze-bot are both equal participants in using a user-created global variable.

sold Ṁ5 of r=(d-r)/41;r!=(r**2)... YES

@IsaacKing It's not clear to me that being illegally snooped on by another bot counts as "communicating" with it.

So, my idea for KamikazeBotv2 is to have a bot that looks through the global variable programData and checks the results of past games. This means that all bots will be "communicating" with KamikazeBotv2 just by making moves in the game. Does this disqualify everyone?

@Multicore No, that's snooping on tournament data and would just disqualify the bot that does that. The other bots aren't complicit because they themselves aren't doing anything outside the scope of the game.

The original version of the rules prohibited referencing any part of the environment in which the bot is running, except the few variables specifically granted to it, which would arguably disqualify any global variable usage at all. I decided to relax that a bit since it seemed unnecessarily harsh, but I still can't allow bots to actually communicate with each other via global variables. And if I'm banning that practice, I don't think it makes sense to say "the first bot to be submitted is allowed and all subsequent ones are in violation"; there's no reason to temporally privilege the first submission that way.

Say for example that an early submission had been r = q. That bot would be invalid at the time, since q is undefined. Then someone else submits a bot that performs q = 1. How else am I supposed to handle that other than by disqualifying them both?

@IsaacKing "User-defined global variables are only allowed if you always overwrite them before reading from them, and they aren't defined in runIPDTournament.js." prevents side-channel communication but allows other uses.

sold Ṁ4 of Other YES

@IsaacKing Based on the tournament criteria, isn’t the order of disqualification random, and each other bot is as likely to be disqualified before or after it?

More related questions