# The Darwin Game

Click here to par­ti­ci­pate. En­tries must be sub­mit­ted on Oc­to­ber 18th, 2020 or ear­lier.

En­try is now closed.

In 2017, Zvi posted an ex­cit­ing story about The Dar­win Game, a vari­a­tion of iter­ated pris­oner’s dilemma.

I will run my own ver­sion of the game in the week fol­low­ing Oc­to­ber 18th, 2020. You do not have to know how to pro­gram in or­der to par­ti­ci­pate. I will code sim­ple bots for non-pro­gram­mers. If you do know how to pro­gram then you may cre­ate your own com­pli­cated bot.

Here are the rules. Changes from Zvi’s origi­nal game are in brack­ets [like this].

For the first round, each player gets 100 copies of their pro­gram in the pool, and the pool pairs those pro­grams at ran­dom. You can and of­ten will play against your­self.

Each pair now plays an iter­ated pris­oner’s dilemma vari­a­tion, as fol­lows. Each turn, each player si­mul­ta­neously sub­mits [an in­te­ger] from 0 to 5. If the two num­bers add up to 5 or less, both play­ers earn points equal to their num­ber. If the two num­bers add up to 6 or more, nei­ther player gets points. This game then lasts for a large but un­known num­ber of turns, so no one knows when the game is about to end; [I guaran­tee it will be at least 100 turns per iter­ated pris­oner’s dilemma].

Each pairing is in­de­pen­dent of ev­ery other pairing. [You do know what round of the game it is and that you are fac­ing an op­po­nent. If you face a copy of your­self you are au­to­mat­i­cally awarded the max­i­mum 5 points per round (2.5 points per bot). You oth­er­wise do not know any his­tory of the game to this point.] Your de­ci­sion al­gorithm does the same thing each pairing.

At the end of the round, all of the points scored by all of your copies are com­bined. Your per­centage of all the points scored by all pro­grams be­comes the per­centage of the pool your pro­gram gets in the next round. So if you score 10% more points, you get 10% more copies next round, and over time suc­cess­ful pro­grams will dis­place less suc­cess­ful pro­grams. Hence the name, The Dar­win Game.

Your goal is to have as many copies in the pool at the end of the last round as pos­si­ble, or failing that, to sur­vive as many rounds as pos­si­ble with at least one copy.

[I will at­tempt to iter­ate un­til there is a sta­ble equil­ibrium.]

I will add some silly bots of my own to make the early game more in­ter­est­ing.

# In­struc­tions for non-programmers

Please give a sim­ple ex­pla­na­tion of what you want your bot to do. Write it with math­e­mat­i­cal pre­ci­sion. If your speci­fi­ca­tion is even slightly am­bigu­ous then you will be dis­qual­ified.

# In­struc­tions for programmers

Write a pro­gram of the fol­low­ing for­mat.

class TitForTatBot():
def __init__(self, round=0): # Edit: Changed "1" to "0"
self.turn = 0
self.round = round
self.previous = None
def move(self, previous=None):
self.turn += 1
if self.previous:
output = self.previous
self.previous = previous
return output
else:
return 2

# Edit 2020-10-11: The above code is wrong. The properly-implemented TFT move method looks like this.
#    def move(self, previous=None):
#        self.turn += 1
#        if previous == None:
#            return 2
#        else:
#            return previous



Your class must have an __init__(self, round=1) in­tial­izer and a move(self, previous=None) method. You may write your class in Python 3 or Hy.

Un­like Zvi’s origi­nal game, you do get to know what round it is. Rounds are in­dexed start­ing at 0. The previous pa­ram­e­ter of the move method is an in­te­ger in­di­cat­ing what your op­po­nent did last iter­a­tion. If it is the first iter­a­tion then previous equals None.

A new in­stance of your class will be ini­tial­ized in each round. You may save what­ever in­for­ma­tion you want into the class in­stance’s fields but you may not save in­for­ma­tion be­tween rounds or be­tween class in­stan­ti­a­tions. The move method must always re­turn an in­te­ger from 0 to 5 in­clu­sive.

You may im­port stan­dard libraries like random, scikit and numpy.

# Co­or­di­nat­ing with other players

Any­one can play, but only play­ers with a Less Wrong ac­count that ex­isted be­fore I de­clared this tour­na­ment will be al­lowed to co­or­di­nate out-of-game. This rule ex­ists to pre­vent play­ers from sub­mit­ting mul­ti­ple en­tries to this con­test and self-co­or­di­nat­ing. Co­or­di­nat­ing with other peo­ple is en­couraged. Co­or­di­nat­ing with your­self be­tween mul­ti­ple sep­a­rate en­tries is cheat­ing.

Click here to par­ti­ci­pate. En­tries must be sub­mit­ted on Oc­to­ber 18th, 2020 or ear­lier.

En­try is now closed.

• tl;dr I be­trayed the CloneBot clique and sub­mit­ted MimicBot. My sub­mis­sion is in this Github repos­i­tory.

# My Pro­cess in chronolog­i­cal or­der:

There were three im­por­tant things I noted in the origi­nal post

• Self co­op­er­a­tion is free, so an early lead is a big ad­van­tage.

• There are guaran­teed to be “silly” bots in the early pool.

• You can vary your strat­egy de­pend­ing on the round.

It seemed to me that the best strat­egy was to get as many points as pos­si­ble early by ex­ploit­ing silly bots, co­op­er­at­ing with any­one will­ing to co­op­er­ate, and fold­ing some­what to at­tack­ers. Then later on just play a non-ex­ploitable co­op­er­a­tive strat­egy and hope for your early ad­van­tage to snow­ball.

## Simulation

After see­ing Ab­strac­tSpyTreeBot and some of the com­ments around it, it seemed to me that simu­la­tion was per­haps the best way to take ad­van­tage of sim­ple bots. There are var­i­ous ap­proaches you could take, but mine was to simu­late ev­ery pos­si­ble se­quence of moves I could make for the next N turns, and use the one with the best out­come. Since this has ex­po­nen­tial time com­plex­ity, I only con­sid­ered the moves 2 and 3 and kept N fairly small, with the op­tion for the game run­ner to re­duce it fur­ther to im­prove perfor­mance.

There are sev­eral pos­si­ble pit­falls with simu­la­tors:

• The op­po­nent might have ran­dom­ized be­hav­ior, mak­ing your simu­lated pre­dic­tions use­less. In fact, not us­ing ran­dom­iza­tion seems wrong to me, since you might get stuck in a rut against an­other de­ter­minis­tic bot, al­ter­nat­ing 2 and 3 on the same sched­ule. Only bad bots would be de­ter­minis­tic and there­fore simu­lat­able.

• The op­po­nent might have planted a land­mine in their code to dis­qual­ify any po­ten­tial simu­la­tor.

• The op­po­nent might be slow, and make my dozens of simu­la­tions per turn take too long.

• The op­po­nent might be a Bul­lyBot, who at­tacks un­til the op­po­nent re­tal­i­ates. My short time hori­zon would make fold­ing look cor­rect, when ac­tu­ally re­tal­i­at­ing would give more points in the long run. At the same time, I did want to fold against At­tack­Bot.

My solu­tion to the first three prob­lems was to only run simu­la­tions against bots with two or fewer open paren­the­ses “(” in their source. That’s how many you need to define __init__ and move, so it wouldn’t leave any for calls to exec or ran­dom or in­spect. I sus­pect it might be pos­si­ble to sneak a land­mine past this re­quire­ment, but since I didn’t tell any­one what I was do­ing it seemed safe enough. Hope­fully enough of the de­ter­minis­tic bots fulfill this re­quire­ment for simu­la­tion to be worth­while.

For the Bul­lyBot prob­lem, I had the simu­la­tion also see what the best strat­egy was that didn’t let the op­po­nent outscore by more than X but also got at least Y points. If this strat­egy didn’t ex­ist, such as against At­tack­Bot, I would fold, but oth­er­wise I would play that strat­egy. I also made the simu­la­tion be more will­ing to be un­com­pro­mis­ing against at­tack­ers as the rounds went on, in case one of the dumb bots was ac­tu­ally putting up a fight in the over­all tour­na­ment.

For my backup strat­egy against non-simu­lat­able bots I kept it sim­ple and pul­led from Zvi’s play­book. In the early rounds, I play an EquityBot which folds if the op­po­nent plays 3 ten times in a row. In the later rounds, I play DefenseBot.

I con­sid­ered a plan of obfus­cat­ing my code so that it would look safe to other simu­la­tors, and then dis­qual­ify­ing them if they tried to simu­late me. I gave up on that be­cause it seemed like other simu­la­tors would ei­ther be care­ful like I was or some­one else would dis­qual­ify them for me. Plus, simu­la­tors are fun. I’d rather have a fair fight against other simu­la­tors. My code uses ran­dom­iza­tion and has lots of scary key­words in it, so other simu­la­tors aren’t go­ing to be ex­ploit­ing me.

To feed my simu­la­tion plan, I found two peo­ple who didn’t have time to make a proper sub­mis­sion, and got them to sub­mit Pass­wordBot, which plays 3 on the first two turns, then if the op­po­nent played 2 on the first two turns it plays 2 for the rest of the game, and oth­er­wise plays 3 for the rest of the game. I figured that only a branch­ing simu­la­tor could take ad­van­tage of this.

## CloneBot

Through­out the week, a cou­ple peo­ple pub­li­cly an­nounced in­tent to join the CloneBot clique. I de­cided that the CloneBots would be a huge threat that I might not be able to com­pete with if I didn’t do some­thing to ad­dress them. Origi­nally I was plan­ning to not con­tact the clique and use the pub­lic source, but when Vanilla_cabs an­nounced the source would not be pub­lic, I mes­saged them in­di­cat­ing will­ing­ness to join the clique. I’m not sure how sus­pi­cious the timing seemed to them, but I was in­cluded any­way. I gave Vanilla_cabs some notes about other parts of the code, but in­ten­tion­ally did not com­ment on any­thing re­lated to se­cu­rity.

My plan was to by­pass what­ever they were us­ing to check that the op­po­nent is a clone, so that I could get perfect co­op­er­a­tion with clones, but also use my simu­la­tion strat­egy to ex­ploit dumb bots and con­tinue to co­op­er­ate with out­siders as the clones got more ag­gres­sive.

On Fri­day, the CloneBot se­cu­rity up­date was re­leased, with the fi­nal ver­sion of the clone check.

(I can’t figure out how to paste code into here), the source is here.

There are two con­straints:

• After the string san­i­ti­za­tion, my code be­fore the pay­load must com­pare iden­ti­cal with the san­i­tized ver­sion of my op­po­nent’s pre-pay­load code.

• After the string san­i­ti­za­tion, my code af­ter the pay­load must have at least eight spaces at the be­gin­ning of ev­ery line.

I got crack­ing.

I no­ticed that the checker was split­ting the code by “\n”, so I won­dered if there was any other char­ac­ter that python would treat as se­man­ti­cally equiv­a­lent to a newl­ine. There is—the ASCII Form Feed char­ac­ter \f (0x0C). How­ever, this didn’t work. I hadn’t no­ticed the ear­lier san­i­ti­za­tion step of us­ing splitlines() and then join­ing by \n. All my \f’s were just get­ting turned into \n’s and get­ting busted.

I then won­dered if there was any other way of con­vinc­ing python that there was a newl­ine, or con­vinc­ing it to de­dent to a lower in­den­ta­tion level, with­out us­ing a char­ac­ter that would be caught by splitlines or us­ing less than eight spaces of in­den­ta­tion. A string of google searches led me to read­ing through the C code for the python lexer, which was very ed­u­ca­tional but con­vinced me that this route was a dead end.

I no­ticed in read­ing about the lexer that it has a some­what com­pli­cated sys­tem for han­dling tabs and spaces in in­dents. I no­ticed that the code san­i­ti­za­tion was au­to­mat­i­cally con­vert­ing tabs to four spaces and won­dered if I could use a mix­ture of tabs and spaces in in­den­ta­tion to ma­nipu­late the if /​ else state­ments in the clonebot move func­tion to make it run the pay­load early. Un­for­tu­nately python 3 does not al­low any mix­ture of tabs and spaces which makes the mean­ing of the code de­pend on how many spaces a tab is worth. I think this at­tack vec­tor might be valid if we were us­ing python 2.

At this point it was 3 AM and I slept on it. On Satur­day morn­ing I thought back to the very thing that had foiled my first at­tempt, the splitlines() san­i­ti­za­tion. In­stead of find­ing a char­ac­ter that would be treated as a newl­ine but not caught by splitlines, what about a char­ac­ter that would be caught by splitlines but not treated as a newl­ine? I found a thread on­line where peo­ple were com­plain­ing about splitlines split­ting on cer­tain char­ac­ters, and a dev said the be­hav­ior was in­ten­tional. One of those char­ac­ters was 0x1D, the ASCII Group Separa­tor char­ac­ter. I tried it in a test pro­gram, and it worked. I tried it in CloneBot, and… it worked!

That’s the tech­nique my fi­nal pro­gram uses. Start­ing with the first com­ment in the move func­tion, I re­placed ev­ery newl­ine with 0x1D, which is a valid char­ac­ter in a com­ment. The bot­tom half of the CloneBot source is a com­ment and gets skipped over, so the move func­tion ac­tu­ally runs my cus­tom code, which is all in­dented at least eight spaces and fulfills the sec­ond con­straint of the clone check. I use the same co­op­er­ateWithClone func­tion as the clones to co­op­er­ate with them un­til the show­down round, at which point I just treat them like any other bot.

I’m not too sur­prised that other peo­ple tried and failed to cheat the re­stric­tions, since it took me 8+ hours and some real think­ing out­side the box. It does make me feel bet­ter that I’m not the only would-be be­trayer.

## Predictions

How do I think I’m go­ing to do? My bot passes the clone check both in Vanilla_cabs’s offi­cial check­ing tool and in my test har­ness, but I can see some pos­si­bil­ity of some­thing in­tro­duc­ing enough differ­ences to screw up the check. Vanilla_cabs en­couraged peo­ple to sub­mit through the form, while I sub­mit­ted a git repo. Lsusr promised to pre­serve my spe­cial char­ac­ters, but the real game en­vi­ron­ment might be differ­ent enough to make the check go wrong, though if that was the case maybe all clones would fail the check.

Separately, my bot is pretty com­pli­cated. I wouldn’t be sur­prised if it was the longest sub­mit­ted, at over 250 lines of code. I’ve done a fair amount of test­ing, but I am not con­fi­dent in my abil­ity to make my soft­ware ro­bust to any­thing that might hap­pen. There’s a de­cent chance some­thing un­ex­pected will hap­pen and I’ll crash and get dis­qual­ified.

How­ever, if my bot doesn’t have a crip­pling bug and no one else figured out how to sub­mit a MimicBot, I don’t re­ally see how I lose. I get lots of points from clones, dumb bots, and co­op­er­a­tors, while ev­ery­one else is los­ing out against at least one of those.

I’ll say 30% my bot crashes or fails the clone test, 10% some­one else sub­mit­ted MimicBot and theirs is bet­ter, 10% those things don’t hap­pen but I still lose, 50% I win.

• Damn, good job. We should’ve gone with my sug­ges­tion that the whole pay­load needed to fit on one line, sep­a­rated by ; (though maybe this would’ve caused us to lose so many clique-mem­bers out of an­noy­ance that it wouldn’t have been worth it).

• That’s an idea wor­thy of con­sid­er­a­tion, but in ad­di­tion to the risk you raised, I also feared some mem­bers would have sub­mit­ted in­valid bots.

• Yeah, if we’d seen the is­sue, I think we could’ve got­ten around it just by not us­ing splitlines, which would’ve been smoother.

Though of course, this ex­ploit up­dates me to­wards think­ing that there are other vuln­er­a­bil­ities as well.

• If we don’t use splitlines we in­stead need to use some­thing similar, right? Like, even if we don’t need to worry about LF ver­sus CRLF (which was a gen­uine sug­ges­tion I made), we still need to figure out if some­one’s got any de-in­dents af­ter the start of the pay­load. And I don’t ex­pect us to do bet­ter with­out splitlines than with it.

• Us­ing newl­ines to figure out what hap­pens af­ter “pay­load” is fine, as far as I can tell. Mul­ti­core’s ex­ploit re­lies on newl­ines be­ing used when com­par­ing stuff be­fore the pay­load.

Stuff like CRLF vs LF is a bit awk­ward, but can maybe be han­dled ex­plic­itly?

• Oh yeah, that’s true as far as I know. I guess it de­pends how much we trust our­selves to find all in­stances of this hole. A pri­ori I would have thought “python sees a newl­ine where splitlines doesn’t” was just as likely as the re­verse. (I’m ac­tu­ally not sure why we don’t see it, I looked up what I thought was the source code for the func­tion and it looked like it should only split on \n, \r and \r\n. But that’s not what it does. Maybe there’s a C im­ple­men­ta­tion of it and a python im­ple­men­ta­tion?)

• Clever! I looked for holes in mostly the same di­rec­tions as you and didn’t find any­thing. I think I ei­ther didn’t think of “things splitlines will split on but python won’t”, or if I did I dis­missed it as be­ing not use­ful be­cause I didn’t con­sider com­ments.

• Your be­trayal of the clique is very nice, hats off to you. I also liked your idea of get­ting oth­ers not that in­ter­ested in the game to sub­mit bots helping you, It’s a pity it did not oc­cur to me.

How­ever, I think you are, too, over­con­fi­dent in you win­ning. I’ve run a simu­la­tion of the whole tour­na­ment till the 160th round with 8 bots (Ma­trixCrash­ingBot, Tit­forTatBot, Pass­wordBot1, Pass­wordBot2, Emp­tyCloneBot, ear­ly­bird, in­com­pre­hen­si­ble­bot, CliqueZviBot) and in the fi­nal equil­ibrium state there are three bots: ear­ly­bird, in­com­pre­hen­si­ble­bot and CliqueZviBot with roughly equal pop­u­la­tions. While Pass­wordBots do help you at the start your lead seems to dis­ap­pear later when the dumb bots and non-clique mem­bers die (which is nice, be­cause your bot’s out­put when simu­lat­ing is pretty an­noy­ing). Sure, it’s just one run of the tour­na­ment with a low num­ber of par­ti­ci­pants (it’s slow to do the tour­na­ment on my lap­top), but it’s some­thing.

• That does re­vise down my ex­pec­ta­tions of win­ning, but my bot hav­ing run thou­sands of times on some­one else’s com­puter and not crash­ing (or failing the clone check?) is good to hear.

Maybe I’m over­es­ti­mat­ing the snow­ball effects of an early pool. If the late game has ev­ery­one co­op­er­at­ing with ev­ery­one else, your matches with oth­ers are only giv­ing a tiny bit fewer points than matches against your copies.

• Origi­nally I was plan­ning to not con­tact the clique and use the pub­lic source, but when Vanilla_cabs an­nounced the source would not be pub­lic, I mes­saged them in­di­cat­ing will­ing­ness to join the clique. I’m not sure how sus­pi­cious the timing seemed to them, but I was in­cluded any­way.

I gave an equal chance to an early new­comer and a late new­comer of try­ing to be­tray. Maybe I was wrong, and I should be mind­ful of that in the fu­ture.

Also, I felt like our num­bers were dan­ger­ously close to the min­i­mum (6), and I ex­pected a cou­ple mem­bers to re­tract be­fore I re­vealed the names (which di not hap­pen). So in my mind I had no choice but to ac­cept you.

I tried it in CloneBot, and… it worked!

Good job! My plan for se­cu­rity was to leave an ob­vi­ous vuln­er­a­bil­ity, and en­trust mem­bers who would re­port with the task to look for more sub­tle ones. Only Lan­rian re­ported, late in the week, and I didn’t trust them enough be­cause I was sus­pi­cious of their mo­tive when they’d asked me for mak­ing our code eas­ier to simu­late (which turns out they were hon­est about).

• Free self recog­ni­tion seems like it makes game less in­ter­est­ing, And that any­one who gets a big lead early just wins?

• Given that you can read the op­po­nent’s source code, self-recog­ni­tion is triv­ial to im­ple­ment any­way (triv­ial but an­noy­ing, since you need to do quin­ing).

• Since quin­ing is “triv­ial but an­noy­ing”, I am will­ing to provide a quin­ing func­tion in the extra pack­age if any­one re­quests it.

• I am aware of the po­ten­tial strate­gic im­pli­ca­tion you bring up. How­ever, as the or­ga­nizer of this game, I be­lieve it is my place nei­ther to con­firm nor deny be­fore­hand any strate­gic im­pli­ca­tions of these rules.

Ex­plain­ing my ra­tio­nale nec­es­sar­ily in­volves dis­cussing the strate­gic im­pli­ca­tions. I will ex­plain my ra­tio­nale for this choice af­ter the game.

• Eh, okay, but (pre­dic­tion) this choice nudges me from “prob­a­bly par­ti­ci­pate” to “prob­a­bly ig­nore”.

• If I had to guess, the rea­son­ing be­hind it is to nudge the game closer to a ‘true’ pris­oner’s dillemma (try­ing to work out if your op­po­nent is will­ing to co­op­er­ate, rather tak­ing fo­cus away from it to­wards the shal­lower prob­lem of try­ing to work out if your op­po­nent is a copy of you)

• I agree, and this de­sign avoids that prob­lem, but seems to in­tro­duce a much larger one, as­sum­ing the in­tent also in­cludes mea­sur­ing bots on their abil­ity to sur­vive in pro­gres­sively more “difficult” bot mixes, which “Dar­win” seems to im­ply.

This choice also nudges me from “has noo­dled around the idea of host­ing a similar com­pe­ti­tion many times and prob­a­bly won’t” to “same, but slightly more likely to ac­tu­ally do it”. :D

• My sug­ges­tion for a fu­ture Dar­win Game tour­na­ment is to get rid of the 0, 1, 4, and 5 moves, and leave 2 and 3 as the only le­gal moves. Se­ri­ous bots gen­er­ally don’t need or use the other moves, so they mostly just make you add an­noy­ing spe­cial case logic to get a few more points out of GoofBots in the early game.

• It’s a good point but in the origi­nal Dar­win Game story, the open­ing se­quence 2, 0, 2 was key to the plot.

• Read­ing the other’s source code is a big­ger change (ac­tu­ally, a su­per­set of auto-rec­og­niz­ing self) It ac­tu­ally makes co­or­di­nat­ing triv­ial and en­force­able, since you can just check for the cor­rect be­hav­ior & pass­word be­fore co­op­er­at­ing. And if you can run your op­po­nent’s source code...

• If i had to guess on the mo­tives, the last time a similar game was played (non pub­li­cally) the meta de­vel­oped to be about self rec­og­niz­ing, this is likely a rule to avoid this.
Win­ning strat­egy was some key string to iden­tify your­self, co­op­er­ate with yourselt, play 3 oth­er­wise. (Granted num­ber of iter­a­tions was low, so peo­ple might not have moved to be non co­op­er­at­ing strate­gies enough (some­thing like grim trig­ger))

• Is read­ing the op­po­nent’s source code le­gal?

• Yes. You may read the op­po­nent’s source code via the get_opponent_source(self) func­tion.

from extra import get_opponent_source

class SpyBot():
def __init__(self, round=1):
self.round = round
def move(self, previous=None):
opponent_source = get_opponent_source(self) # return value is of class str
if '3' in opponent_source:
return 2
return 3


Be­ware the halt­ing prob­lem. In­finite re­cur­sion con­sti­tutes overuse of com­pute re­sources and may be grounds for dis­qual­ifi­ca­tion.

• In­finite re­cur­sion con­sti­tutes overuse of com­pute re­sources and may be grounds for dis­qual­ifi­ca­tion.

Is this dis­qual­ifi­ca­tion in ad­vance, or in run-time? That is, do you just look at the code and de­cide whether it’s good, or do you give each pro­gram some bounded time and mem­ory to run and dis­qual­ify it if any copy overflows it? (Btw an­other op­tion would be, pun­ish only that copy.)

• Run-time. I dis­qual­ify the en­tire pro­gram—not just the one copy—and then restart the game with one (or fewer) com­peti­tors.

• Does this open a se­cu­rity hole of fu­ture pre­dic­tion like Spec­tre etc?

Some bots could have a thing where they re­mem­ber if they have met cer­tain an­other bot (Sig­nalBot) in the game. If they haven’t, they de­cide that the game setup car­ries cer­tain pre­set in­for­ma­tion.

If the bots find out later in the game that the pre­set con­di­tion would be true, then they co­or­di­nate so that Sig­nalBot causes in­finite loop and gets dis­qual­ified and the game restarted. Now the game will miss Sig­nalBot, caus­ing the oth­ers to use this in­for­ma­tion to de­duce the sig­nalled in­for­ma­tion.

Tl;dr:

Givens: In some cases Left is best strat­egy. Other­wise Right is best strat­egy.

1. Foretel­lerBot ob­serves Sig­nalBot in the game, de­cides to play Right.

2. Bots ob­serve Left is bet­ter strat­egy.

3. Sig­nalBot non­halts and gets thrown out, game is re­set.

4. Foretel­lerBot ob­serves no Sig­nalBot in the game, de­cides to play Left.

• OP said el­se­where in the com­ments (em­pha­sis mine):

Your code is al­lowed to peek at the game en­g­ine for the pur­poses of figur­ing out if it is be­ing simu­lated by some­one else’s code. Peek­ing at the game en­g­ine for other rea­sons, like figur­ing out how many of each op­po­nents re­main or at­tempt­ing to mod­ify the game en­g­ine it­self or at­tempt­ing to mod­ify your op­po­nents’ code from any­where out­side their own simu­la­tion of you is against the rules.

And in the origi­nal post:

You may save what­ever in­for­ma­tion you want into the class in­stance’s fields but you may not save in­for­ma­tion be­tween rounds or be­tween class in­stan­ti­a­tions.

• You are not peek­ing at the game en­g­ine, you can just mes­sage this the same as you can mes­sage co­op­er­a­tion (2, 0, 2 code etc).

You also do not need to save any in­for­ma­tion over in­stances—all of your bots on a round are run­ning on the same in­stance. If any of your Foretel­lerBots ob­serves Sig­nalBot, then Sig­nalBot has not dropped. Sig­nalBot’s ex­is­tence is in it­self the flag.

• Each pairing is in­de­pen­dent of ev­ery other pairing. [You do know what round of the game it is and that you are fac­ing an op­po­nent. If you face a copy of your­self you are au­to­mat­i­cally awarded the max­i­mum 5 points per round (2.5 points per bot). You oth­er­wise do not know any his­tory of the game to this point.

A sep­a­rate in­stance of each bot is cre­ated for each pairing in each round. All that Foretel­lerBot knows in any pairing is whether it is it­self fac­ing a Sig­nalBot, not whether any of its copies are.

• Thanks for the info. This con­flicts with the speci­fi­ca­tion of

A new in­stance of your class will be ini­tial­ized in each round.

which I in­ter­preted to mean that there ex­ists ex­actly 1 in­stance of the class per round.

The model you pro­pose makes sense though, I guess my men­tal model of the thing was mis­taken.

• Why does get_op­po­nent_source take self as an ar­gu­ment?

• There are two ac­tive bots. The self ar­gu­ment tells the game client which bot’s code not to re­turn.

• Thanks.

• # If you’re par­ti­ci­pat­ing in the con­test and you want to win, I have a propo­si­tion for you:

Howdy! You’ve prob­a­bly looked up Zvi’s past Dar­win game that di­rectly in­spired this one. A group of play­ers formed a clique who rec­og­nized each other, co­op­er­ated among them­selves and defected on ev­ery­one else. They nearly wiped the board, but they were preyed upon by a mem­ber who played both sides.

What they missed was a way to guaran­tee that all mem­bers ap­ply the de­cided strat­egy. They had no way to en­force it.

## But we have a way.

I call it CloneBot: a bot who checks that its op­po­nent has the ex­act same code as it­self. No way to cheat that! It guaran­tees that ev­ery mem­ber of the clique does the same thing. More­over, there’ll be a way to co­op­er­ate op­ti­mally, avoid­ing los­ing the first rounds to co­or­di­nate. The clique are gonna be the most effi­cient cc­op­er­a­tors.

But in the end we’re all gonna tie, it’s bor­ing. I want to take a chance at win­ning!

So do I. This is why the clique are only go­ing to col­lab­o­rate un­til a pre­defined round. After we’ve elimi­nated the com­pe­ti­tion, we can have a dra­matic show­down among our­selves. Cool, no? In the code, there’s gonna be a sep­a­rate func­tion that’s called only af­ter a given round. The code checker will ver­ify that the func­tion is only called at the right time, but will ig­nore what is in­side.

What will CloneBot do?

Depends on the pro­por­tion of clones. If we’re a big group, CloneBot will straight up defect against out­siders by play­ing 3. Other­wise, CloneBot will co­op­er­ate, but make sure op­po­nent does not gain more than it­self.

With its clones, CloneBot will co­op­er­ate by al­ter­nat­ing 2-3. Who gets the first 3 will be de­ter­mined fairly be­fore the first turn starts.

Ok, but I don’t want to find my­self in a small clique that’s go­ing to lose.

You don’t have to com­mit to sub­mit­ting CloneBot right away. All you need to do is con­tact me to say you’re in, con­di­tional on the clique be­ing large enough. By de­fault, con­tact me pri­vately. If you want, you can roll a D6, and if you roll 6, join me pub­li­cly right here.

A few days be­fore the dead­line, if we’re 5 or less, I’ll just an­nounce that the crit­i­cal mass was not reached. But if we’re more than 5, I will make pub­lic the names of all who con­tacted me to join the group and crush the com­pe­ti­tion. If I post your name at that mo­ment, you must sub­mit CloneBot.

I like the idea, but I wish X in­stead of Y.

Every de­tail is open to dis­cus­sion for about 3 days. After that, this post will be up­dated, and ev­ery per­son who ex­pressed their de­sire to join will be in­formed of the changes and asked to con­firm their par­ti­ci­pa­tion.

Where do I find CloneBot?

I’m con­sid­er­ing mak­ing the code pub­lic.

## Let the best clique mem­ber win :)

• I don’t ap­prove of this. As­sum­ing that ev­ery­one who pledges to join the clique ac­tu­ally sub­mits a CloneBot and no­body finds a way to beat the recog­ni­tion code and defect from the clique, and as­sum­ing there isn’t a sub­tle bug in the code that dis­qual­ifies some or all of the clones, then the clone co­hort can in­deed elimi­nate the non-clone bots. At that point though, we’re right back where we started, and then what? Why not just let the best bot win in the first place?

If ev­ery­one goes through with this, then of course I’d be bet­ter off sub­mit­ting a clone my­self (again as­sum­ing no cheat­ing/​er­rors/​etc. - I would cer­tainly need to see the code my­self be­fore de­cid­ing to join), but this is a bit differ­ent from typ­i­cal pub­lic-goods-type pledges. Typ­i­cally, ev­ery­one wants the thing done but given that it is done would in­di­vi­d­u­ally rather not con­tribute. Here ev­ery­one would rather the thing not be done, but given that it is done would in­di­vi­d­u­ally rather con­tribute. This is a straight­for­ward ex­am­ple of a bad equil­ibrium.

If you have pledged, or are think­ing of pledg­ing, con­sider:

• How sur­prised would you be if a bug in the CloneBot code dis­qual­ified all the clones?

• How sur­prised would you be if some­one man­aged to by­pass the code check­ing and defect from the group?

• How sur­prised would you be if one or more peo­ple who pledged didn’t ac­tu­ally sub­mit a CloneBot?

• Is this the kind of equil­ibrium you want to en­courage?

• I get it that you don’t like that play­ers join forces. I am not sure I’d al­low co­or­di­na­tion if I had a say on the rules. But per the rules co­or­di­na­tion is part of the game. That’s it. For all we know, oth­ers are mak­ing cliques in se­cret.

I be­lieve my scheme sub­stan­tially in­creases our chances of win­ning, so I’ll go with that.

Ad­mis­sions are clos­ing soon. Good luck, what­ever you de­cide :)

• I can’t say it’s not fair, and I do re­al­ize you’ve put a lot of work into this. Have you de­cided to make the clone code pub­lic?

• At least one mem­ber asked for a ba­sic obfus­ca­tion mea­sure. Pub­lish­ing the code would defeat their pur­pose.

Also, from an in­sider’s per­spec­tive, pub­lish­ing the code now would only slightly in­crease our chances to get an­other mem­ber be­fore the end of ad­mis­sions, while it would en­tail a sig­nifi­cant risk of op­po­nents ad­just­ing their strat­egy against it. I should have de­cided on the pub­li­ca­tion ear­lier, but hon­estly it was never a pri­or­ity.

• We were five hun­dred, but with swift support

Grew to three thou­sand as we reached the port

(Le Cid)

It’s been an ex­cit­ing week, I’ve had lots of fun, thanks ev­ery­one who shared ideas, and thanks lsusr for swiftly and kindly an­swer­ing all my ques­tions. Now is time for the fi­nal act.

• arxhy

• DaemonicSigil

• Emiya

• fron­tier64

• Lanrian

• Multicore

• philh

• simon

• Taleuntum

• Vanilla_cabs

You will re­ceive a per­sonal mes­sage shortly.

That is all.

• I pledge to join if there is at least 5 peo­ple to­tal joined.

• Pledg­ing now to join if at least 8 do.

• How do you de­ter­mine who gets the first 3? Maybe lsusr will be kind enough to provide a sym­me­try-break­ing bit in the “ex­tra” pack­age. (It would only be fair, given that bots play­ing them­selves are au­to­mat­i­cally given max score.) If not, and you have to do things the hard way, do you com­pare source code alpha­bet­i­cally, and favour X over Y on even rounds and Y over X on odd rounds?

Also, it may be a good idea to make the level of defec­tion against out­siders de­pend on the round num­ber. i.e. co­op­er­ate at first to max­i­mize points, then af­ter some num­ber of rounds, when you’re likely to be a larger pro­por­tion of the pool, switch to defect­ing to drive the re­main­ing bots ex­tinct more quickly.

• I am nei­ther kind nor fair-minded enough to provide a sym­me­try-break­ing bit in the extra pack­age.

• do you com­pare source code alpha­bet­i­cally, and favour X over Y on even rounds and Y over X on odd rounds?

Great idea! I’ve up­dated the fol­low­ing heuris­tic us­ing that.

There is one thing that is differ­ent be­tween the pro­grams: the code that you will add to be ex­e­cuted in the later rounds (the pay­load). As I said, CloneBot will ig­nore it when judg­ing whether its op­po­nent is a clone. But if the op­po­nent is a clone, it will use this heuris­tic to de­cide who goes first:

• com­pare both pay­loads lexicographically

• if the differ­ence in length is the same par­ity as the round, the short­est plays 3

• oth­er­wise, the longest plays 3

This is fair, de­ter­minis­tic, and needs 0 turn to com­mu­ni­cate. There’s no point in tweak­ing your pay­load in the hope of start­ing with 3 more of­ten. The only prob­lem are ties, which are un­llikely, and adding your name as a com­ment solves it.

Why also com­pare length? Be­cause oth­er­wise, the pay­loads of ex­treme length (very short or very long) would have very sta­ble al­ter­nat­ing pri­or­ity, while the ones in the mid­dle would be more sub­ject to ran­dom­ness. This way, it’s the same ran­dom­ness for ev­ery­body.

Also, it may be a good idea to make the level of defec­tion against out­siders de­pend on the round num­ber. i.e. co­op­er­ate at first to max­i­mize points, then af­ter some num­ber of rounds, when you’re likely to be a larger pro­por­tion of the pool, switch to defect­ing to drive the re­main­ing bots ex­tinct more quickly.

That seems rea­son­able. I’m just wor­ried that we might let greedy or even co­op­er­at­ing bots take too much lead. Ideally, as soon as the clique reaches crit­i­cals mass, it should starve its op­po­nents. The ‘as soon’ de­pends on what pro­por­tion of the pool we’ll ini­tially be.

• # Ex­pla­na­tion of my strat­egy and thought pro­cess in chronolog­i­cal order

After see­ing Vanilla_Cabs’s com­ment I lied to them about want­ing to join the clique. I was un­de­cided, but I figured see­ing the code of the clique can be a great ad­van­tage if I can ex­ploit some cod­ing mis­take and I can still de­cide to join later any­way if I want.

The first ver­sions of CloneBot (the name of the pro­gram for our clique) did ac­tu­ally con­tain a mis­take I could ex­ploit (by defin­ing the __new__() method of the class af­ter the pay­load) and so this was my plan un­til Vanilla_Cabs fixed this mis­take. After they fixed it, I didn’t no­tice any way I can take ad­van­tage, so I joined the clique in spirit.

Ini­tially my plan for my bot was a simu­la­tor which simu­lates be­tween 100 and 1000 turns of the op­po­nent against a few can­di­date bots (ZviBot, TiTforTat, re­turn 3, re­turn 2, etc..) and then de­pend­ing on the round num­ber ei­ther chooses the one with the max­i­mum point for me or the one which gets more points than the op­po­nent. There were un­for­tu­nately two prob­lems with this plan:

1. Bots who can de­tect if they are in a simu­la­tion can get me into an in­finite loop which would dis­qual­ify my pro­gram, so I had to re­search the ways this might hap­pen to know how to pre­vent it. I started by in­spect­ing the code for Ab­strac­tTreeSpyBot and I did no­tice some ways to do this:

• The code always in­stan­ti­ates a new ob­ject, so by stor­ing past moves, I can de­tect if I’m in a simu­la­tion if my move() method’s ar­gu­ment is not None and I have not stored pre­vi­ous moves. This defect how­ever is re­ally spe­cific to this pro­gram and other simu­la­tors can eas­ily avoid it by stor­ing the in­stan­ti­ated class ob­ject be­tween rounds.

• The code sim­ply calls the simu­lated bot’s move() method which can be de­tected by in­spect­ing the call stack and find­ing a lo­cal vari­able named ‘self’ with a method named ‘move’ of a class type not named the simu­lated bot’s class­name. This method of de­tec­tion can still be tricked by run­ning the simu­la­tion in a differ­ent pro­cess (eg by call­ing the python in­ter­preter from the shell, this has the ad­van­tage of hav­ing an easy and ro­bust way to re­define get_op­po­nent_source()), but still I ex­pect this would DQ many sub­mit­ted simu­la­tors. (I at­tached the code of a bot us­ing this type of de­tec­tion.)

2. Isusr posted a very un­for­giv­ing time limit. Un­for­tu­nately, I could not make simu­la­tor bot work in this time­limit. In fact, on my lap­top even Ab­strac­tSpyTreeBot does not run in 0.05s (1 init + 100 moves) and to avoid de­tec­tion I would have to call the python in­ter­preter from the os which would again cost a lot of time. It does not even mat­ter what the time limit is just that it is not a vague ‘don’t be too slow’ like it was ini­tially, be­cause I planned to simu­late (100-1000 moves+init)*(num­ber of pro­grams I want to try), so if the num­ber of pro­grams I want to try is greater than 1 I would go over the limit if my op­po­nent uses even just half the limit.

After this, see­ing that I can’t make my simu­la­tor work, I aban­doned the idea of me sub­mit­ting a simu­la­tor. How­ever see­ing that some other types of simu­la­tor can still be pretty strong, I de­cided to dis­in­cen­tivize them, so when Lar­ian cau­tioned in the clique-chat that simu­la­tor crash­ing bots weaken our clique (as isusr restarts the whole tour­na­ment in the event of DQ), so we should not use them, I lied that I’ve already sub­mit­ted one pro­gram de­tect­ing and crash­ing simu­la­tors. Of course Lar­ian’s point was valid, so ob­vi­ously I did not even plan to do so. Some time later It oc­cured to me that my claim that there is a simu­la­tor crash­ing bot in the clique might in­cen­tivize those who wanted to sub­mit a simu­la­tor to leave the clique, so I added an­other lie that the method of de­tect­ing simu­la­tors was my friend’s idea (hope­fully sug­gest­ing that there is an­other con­tes­tant with the same method out­side the clique). I’m cu­ri­ous how be­liev­able my lies were, I felt them to be pretty weak, hope­fully it’s only be­cause of my in­side view.

After this I had to come up with an ac­tual pro­gram. My in­trigue and life didn’t leave me with much time, so I fi­nally sub­mit­ted a ZviBot (a bot similar to the one de­scribed in the Dar­win Game se­ries) as a pay­load (for those not in our clique: pay­load is the part of the CloneBot which ac­ti­vates in the endgame against other clique mem­bers). While I did not have time to run simu­la­tions, I had three rea­sons for this sub­mis­sion:

1. ZviBot has a good track record in a similar com­pe­ti­tion.

2. Given that bots in this com­pe­ti­tion know the round num­ber, I ex­pect that many will get meaner (less co­op­er­at­ing) in the later rounds on the grounds that if they sur­vived for this many rounds they are prob­a­bly a sig­nifi­cant por­tion of the pool, so they can try to kill oth­ers. How­ever be­cause the pro­grams will use differ­ent rates of be­com­ing un­co­op­er­at­ing, they will get elimi­nated from the pool one by one as the oth­ers are still co­op­er­atat­ing. By not get­ting meaner my plan was to stay in the fi­nal equil­ibrium state with oth­ers.

3. I was cu­ri­ous how such a sim­ple bot would perform.

Bot de­tect­ing simu­la­tors:

class MatrixCrashingBot():
def __init__(self, round=1):
import inspect
from time import sleep
sf = inspect.stack()
simulated = False
enemy = ""
for f in sf:
if ('self' not in f.frame.f_locals):
continue
fo = f.frame.f_locals['self']
fod = dict(inspect.getmembers(fo))
if 'MatrixCrashingBot' != fo.__class__.__name__ and 'move' in fod:
simulated = True
enemy = fo.__class__.__name__
break
if simulated:
while 1:
print("{} tried to simulate me :O >:\[ So I sent him to an infinite cycle!\nNote to the tournament organizer: The infinite cycle is run by {} not by the MatrixCrashingBot! ".format(enemy, enemy))
sleep(3)
def move(self, previous=None):
return 3


Bot I fi­nally sub­mit­ted: (ev­ery­thing ex­ept the pay­load is writ­ten by Vanilla_cabs. The core idea (al­ter­nat­ing 3s and 2s) of the pay­load is from Zvi)

class CloneBot():
def __init__(self, round=0):
import math
import random
import extra
self.math = math
self.random = random
self.extra = extra

self.showdownRound = 90     # after this round, your personal program takes over
self.round = round          # the current round
self.myMoves = []           # all the moves you've made, first to last
self.opponentMoves = []     # all the moves your opponent has made, first to last

my_source_raw = extra.__getattribute__(''.join(['ge','t_','my','_s','ou','rce']))(self)
opponent_source_raw = extra.__getattribute__(''.join(['ge','t_','op','po','ne','nt','_s','ou','rce']))(self)
my_source = "\n".join(["    ".join(line.split('\t')).rstrip() for line in my_source_raw.splitlines()])
opponent_source = "\n".join(["    ".join(line.split('\t')).rstrip() for line in opponent_source_raw.splitlines()])

if not 'def payload(self) :' in opponent_source :
self.is_opponent_clone = False
else :
my_common_code, my_payload = my_source.rsplit('def payload(self) :', 1)
opponent_common_code, opponent_payload = opponent_source.rsplit('def payload(self) :', 1)
if my_common_code != opponent_common_code :
self.is_opponent_clone = False
else :
self.is_opponent_clone = True
for line in opponent_payload.split("\n") :
# checks that no common method or property is overwritten after the payload
# allows the innocuous command "foo = 'bar'" by member's demand
if line.lstrip() != "" and line != "foo = 'bar'" and line[0:8] != "        " :
self.is_opponent_clone = False
break

if self.is_opponent_clone :
# fair way to decide who starts with 3 between two clones
# for 100% protection against ties, personalize your payload with a comment
self.high_first = (my_payload < opponent_payload) == ((payload_length_difference+round) % 2 == 1)

def move(self, previous=None) :
self.turn = len(self.myMoves)               # the current turn
# pseudorandom to allow simulators to collaborate
self.random.seed((self.round+1) * (self.turn+1) * (7 if previous==None else (previous+1)))

if previous != None :
self.opponentMoves.append(previous)
if self.is_opponent_clone :
if self.round < self.showdownRound :
output = self.cooperateWithClone()
else :
else :
output = self.default()
self.myMoves.append(output)
return output

def defaultCooperation(self) :              # factor influencing behaviour with non-clones, 1 at round 0, 0 at round 60
return max(0.0, float(self.showdownRound - (self.round*1.5)) / self.showdownRound)

def cooperateWithClone(self) :
if self.turn == 0 :
if self.high_first :
return 3
else :
return 2
else :
return self.opponentMoves[-1]

def default(self) :
if self.turn == 0 :
if self.random.random() < 0.5 * self.defaultCooperation() :
return 2
else :
return 3
elif self.myMoves[-1] + self.opponentMoves[-1] == 5 :
if self.myMoves[-1] == 2 :
return 3                        # tit for tat
elif self.myMoves[-1] == 3 :
if self.turn >= 2 :
if self.myMoves[-2] == 3 and self.opponentMoves[-2] == 2 :
return 3                # stable 3 against 2
if self.random.random() < self.defaultCooperation() * 1.2 :
return 2                    # cooperation
else :
return 3                    # maintain 3 against 2
else :
return self.myMoves[-1]         # free candy
elif self.myMoves[-1] + self.opponentMoves[-1] < 5 :
return 5 - self.opponentMoves[-1]
else :                                  # sum > 5
if self.random.random() < self.defaultCooperation() * max(0, 50-self.turn) / 100.0 :
return 2                        # back down
else :
return 3                        # maintain

# put a personal word here to guarantee no tie during cooperation: in a pretty body no one can see your rotten soul
# put what you want to play for the showdown
# no line after 'def payload(self)' should have less than 8 whitespaces at the beginning,
# unless it's an empty or only whitespace line
#
# Idea of solution: most program will gradually get meaner as rounds
# progress, but because they do so at different rates
# they will get eliminated as other, still cooperating bots outcompete their
# meanness. By not getting meaner I plan to stay in the final equilibrium state.
# Otherwise it's a ZviBot.
if self.turn == 0:
self.switched = False
return 3
else:
# against very submissive bots
if self.turn >= 3 and self.opponentMoves[-1] < 3 and self.opponentMoves[-2] < 3 and self.opponentMoves[-3] < 3:
return 5-self.opponentMoves[-1]
# against bots who are very bad at detecting patterns
if self.turn >= 5 and self.opponentMoves[-1] == 3 and self.opponentMoves[-2] == 2 and self.opponentMoves[-3] == 3 and \
self.myMoves[-1] == 3 and self.myMoves[-2] == 2 and self.myMoves[-3] == 3 and not self.switched:
self.switched = True
return 3;
if self.myMoves[-1] == 2:
return 3
elif self.myMoves[-1] == 3:
return 2

• The first ver­sions of CloneBot (the name of the pro­gram for our clique) did ac­tu­ally con­tain a mis­take I could ex­ploit (by defin­ing the __new__() method of the class af­ter the pay­load) and so this was my plan un­til Vanilla_Cabs fixed this mis­take. After they fixed it, I didn’t no­tice any way I can take ad­van­tage, so I joined the clique in spirit.

Lit­tle did you know that I was aware of this weak­ness from the be­gin­ning, and left it as a test to find whom I could trust to search for the weak­nesses I didn’t know. Of the 3 (I think) to whom I showed the code early, only Lan­rian re­ported it.

I’m cu­ri­ous how be­liev­able my lies were, I felt them to be pretty weak, hope­fully it’s only be­cause of my in­side view.

I didn’t play a simu­la­tor so I didn’t care about the first.

About the sec­ond, I can tell you that an­other mem­ber alerted me that you seemed to have a hid­den ally. They feared you had made an ally out­side the clique, or just given the code to join the clique to a player know only to you. Which I thought was a pos­si­bil­ity. Ac­tu­ally, I hoped for a few stow­aways to boost our num­bers.

• Maybe it’s a lit­tle cheap to say this af­ter you’ve re­vealed it, but it did ac­tu­ally oc­cur to me that you might have de­liber­ately made this weak­ness. Had I known that in Python you can re­define meth­ods, I might have re­ported it, but the ex­ploit with __new__() seemed pretty ob­scure (even though I didn’t know the other way and I did know this). The pos­si­bil­ity of this be­ing a test was also the rea­son I went with the “Oh I’m so busy, I didn’t have time to re­view the code..” ex­cuse. I’m also cu­ri­ous whether Lar­ion calcu­lated with you de­liber­ately plant­ing the mis­take or they had in-game ethics. Also, be­fore you posted the list of the mem­bers pub­li­cly, you were the cen­ter of the clique and could con­trol the in­for­ma­tion the clique mem­bers got. I was re­ally para­noid about this and I feel you could have used this some­how. Have you thought along these lines?

About your sec­ond point, It’s nice I could make some­one be­lieve that I had an ally out­side the clique.

• Oh, that was me I think. I had sim­ply thought your com­ment meant you were prepar­ing code with some­one else. Whether he was in­side the clique, out­side it, or a non player helping you out I wasn’t sure, but I still recom­mended cau­tion.

I did think it was weird that you’d let slip such in­for­ma­tion, but couldn’t see any rea­son for mak­ing peo­ple think you had al­lies, so I just thought that the most likely ex­pla­na­tion was that a non player was helping you. Still, be­ing cau­tious wouldn’t hurt.

I have to say I didn’t made the con­nec­tion about simu­la­tion crash­ing soft­ware be­ing out­side the clique, likely be­cause I wasn’t play­ing a simu­la­tor so I didn’t thought much about it.

All in all… I think it’s a lie that would work best on the peo­ple it wouldn’t need to work on. If I had thought to change a plan I had go­ing based on the in­for­ma­tion you pro­vided, I would have won­dered a bit more about why you did that, per­haps get­ting sus­pi­cious.

But I still think it wouldn’t re­ally be ob­vi­ous as a lie to any­one.

On a side note, I re­ally love this site. I can’t re­ally re­call any other game I’ve been in get­ting this tan­gled.

• I didn’t know about __new__(), I only knew about red­ifin­ing meth­ods, so based on what you knew, your rea­son­ing was cor­rect.

I knew no one be­fore start­ing the clique. Lan­rian joined the same way as the oth­ers. If any­thing, Lan­rian was sus­pi­cious be­cause they in­sisted we put the ran­dom.seed() in­side move() and make it pseu­do­ran­dom so that simu­la­tors can ac­cu­rately em­u­late our be­havi­our. The rea­son they gave was to bet­ter col­lab­o­rate, and have the simu­la­tors play 2 against 3 in­stead of 3 against 3. I was mildly con­vinced and I still am sus­pi­cious of that move. They only late in the week re­ported the weak­ness, af­ter you and philh passed on the chance to do so. But they did so soon af­ter I showed them the code.

I was re­ally para­noid about this and I feel you could have used this some­how.

The se­crecy on the mem­bers was used to:

• pre­vent mem­bers and po­ten­tial mem­bers from wor­ry­ing if there were too few cur­rent mem­bers. That was the pur­pose I had in mind when I made that choice. A few days be­fore the end I still was not sure we’d be enough. I was also wor­ried some mem­bers would drop if we were too lit­tle. So the 2 mem­bers who joined in the last 2 days re­ally helped.

• avoid any col­lu­sion be­tween mem­bers that would not in­clude me. And more gen­er­ally re­ceive any valuable in­for­ma­tion that mem­bers would like to share.

So I used that ad­van­tage only in a defen­sive way. But I did re­ceive an offer that did in­form me on more offen­sive uses, and im­pacted my pay­load, which I will elab­o­rate on if the sender al­lows it.

• I stand by my rea­son­ing! As long as we don’t yield to bul­ly­ing, simu­la­tors are our friends, en­sur­ing that the max­i­mum pay­out is always payed out.

• I didn’t think about re­port­ing the bug as mak­ing a sub-op­ti­mal but eth­i­cal choice – I just wanted to be part of a clique that worked in­stead of a clique where peo­ple defected. My aver­sion to ly­ing might have af­fected my in­tu­itions about what the cor­rect choice was, though, idk ¯\_(ツ)_/​¯

• by defin­ing the __new__() method of the class af­ter the payload

In­ci­den­tally, you could also just re­define ex­ist­ing meth­ods, which was how I planned to do it. Like,

class Foo():
def __init__(self):
self.x = 1

def __init__(self):
self.x = 2

Foo().x # 2

• Good to know. I’m a C++ guy which has a “one defi­ni­tion rule” not only for the trans­la­tion unit, but for the whole pro­gram, so I in­cor­rectly as­sumed that python is the same even though the lan­guages are ob­vi­ously very differ­ent.

• I lied that I’ve already sub­mit­ted one pro­gram de­tect­ing and crash­ing simu­la­tors. … I added an­other lie that the method of de­tect­ing simu­la­tors was my friend’s idea (hope­fully sug­gest­ing that there is an­other con­tes­tant with the same method out­side the clique). I’m cu­ri­ous how be­liev­able my lies were, I felt them to be pretty weak, hope­fully it’s only be­cause of my in­side view.

I be­lieved both of these lies, though if I’d come to rely on them at all I might have ques­tioned them. But I as­sumed your friend was in the clique.

• Yes, I feared that some might think my friend is in the clique. How­ever I couldn’t just say that they are not in the clique, be­cause that would have been too ob­vi­ous. (like my other lie: “Yeah, I to­tally have an­other method for de­tect­ing be­ing in a simu­la­tion even if the simu­la­tion runs in a sep­a­rate pro­cess, but un­for­tu­nately I can’t re­veal it.”) So I tried to im­ply it by speak­ing about him as if he is not in the con­ver­sa­tion and him not com­ment­ing af­ter I men­tioned him. I hoped in case some­one was plan­ning to sub­mit a simu­la­tor out­side the clique they would try to sneak­ily in­quire about whether my friend is in the clique or not and then I would have asked a ran­dom, not com­pet­ing less­wronger to play the part of my friend.

• I be­lieved all lies! And I might’ve sub­mit­ted a simu­la­tor if you hadn’t told the first, and would definitely have tried harder to simu­la­tor-proof my bot, so you did change my be­havi­our. Leav­ing the clique wouldn’t have been worth it, though. Even know­ing that you lied about the 2nd thing, I as­sign de­cent prob­a­bil­ity to some­one crash­ing all the simu­la­tors out­side the clique. (I think this is in­cor­rect, though – if you can figure out that you’re in a simu­la­tion, it’s way bet­ter to claim that you’ll be sub­mit­ting 3 to scare the simu­la­tor into play­ing 2.)

• So, in case any­one’s won­der­ing what I did...

I cared enough to think and en­ter, but not to pro­gram.

I de­signed a simu­la­tor, but was told it wouldn’t be coded for me, so that was out.

So in­stead, I wrote this:

Un­til sym­me­try breaks, if the round # is 1, is 3 or is even, play se­quence 23322232323322233 and then re­peat 22222223 un­til sym­me­try breaks. If round # is odd and 5 or more, the re­verse, ex­cept re­peat­ing 22222223 at the end.

Once it breaks, al­ter­nate 2 and 3 for 4 turns.

Then, if the last turn added to 5, keep do­ing that un­til they don’t.

Once they don’t...

If they’ve always played 0 or less, play 5.

If they’ve always played 1 or less, play 4.

If they’ve always played 2 or less, play 3.

Other­wise, de­pend­ing on round num­ber:

Rounds 1-50: Keep al­ter­nat­ing un­til turn t+10. After that, if last turn added to 5, al­ter­nate 2 and 3. Other­wise, check their av­er­age score per round af­ter sym­me­try. If it’s 2.5 or lower, play 2, oth­er­wise play 3.

Rounds 51-100: Same as above, ex­cept you also always play 3 if their score is 5 or more higher than yours.

Rounds 101+: Same as above, ex­cept you also always play 3 if their score is higher than yours.

(We could im­prove by adding more logic to prop­erly ex­ploit in strange situ­a­tions, but we don’t care enough so we won’t.)

That’s it. Keep it sim­ple. Still call it BendBot I guess.

The in­ten­tion here was pretty ba­sic. Endgame be­hav­ior varies by round to get stingier if any­one tries some­thing, to grab early pool share with­out be­ing ex­ploited later.

The big thing is that this bot is de­ter­minis­tic. I in­ten­tion­ally avoid call­ing the ran­dom func­tion by choos­ing a semi-ran­dom set of 2s and 3s, on the the­ory that it’s un­likely any­one else would choose an iden­ti­cal se­quence, and if I meet my­self I get the 2.5 any­way.

If they are not simu­lat­ing or check­ing code, it won’t mat­ter.

If they are look­ing at all, then my not load­ing their code and not be­ing ran­dom tells them the wa­ter’s fine, take a look, see what’s go­ing on, and we can co­op­er­ate fully—you can see what I’m start­ing with, and we can get 2.5 each with­out in­ci­dent. I’m sad that some peo­ple thought that more than two paren­the­sis was high risk to simu­late/​ex­am­ine—I thought that the ob­vi­ous thing to do was check to see if some­one ever loads code or uses a ran­dom func­tion, and if you don’t do ei­ther, you should be safe.

So the thought was, many of the best bots would be simu­la­tor bots and I’d get full co­op­er­a­tion from them, whereas when they faced each other, they’d have to do some ran­dom match­ing to co­op­er­ate, so I’d have an edge there, and I’d do rea­son­ably well against any­thing else that went late un­less some al­li­ance was afoot.

Turns out an al­li­ance is afoot af­ter all, but I cer­tainly didn’t care enough to worry about that. Let them come, and let the back­stab­bers profit, I say.

I was told that I had by far the most com­pli­cated non-coded en­try even then, and that my endgame logic was be­ing re­placed with ran­domly 50% 2, 50% 3. I was asked, sub­mit as-is, fix it, or with­draw?

That mod­ifi­ca­tion definitely didn’t work, and the code that was writ­ten was not some­thing I felt OK touch­ing. So I ex­plained why, and sug­gested it be re­placed with this:

If (last round added to 5 or less) play what­ever they played last.

Else If (their score > my score and round > 5) play 3.

Else Play 2.

I figured that was one ex­tra line of code and should take like 2 min­utes tops, and if that was ‘too com­plex’ then that was fine, I’d sit out.

So ba­si­cally, let my­self get ex­ploited very early since there would likely be at least one all-3s in the mix but all such things would swiftly lose, then shift to hard­core mode a lit­tle faster to keep it sim­ple.

I didn’t get a re­ply to that, so I don’t know if my en­try is in or not. I hope it is, but ei­ther way, good luck ev­ery­one.

• Your en­try is in. I im­ple­mented the If (their score > my score and round > 5) play 3. Else Play 2. al­gorithm. I hope I got the rest of it right.

(import random)
(setv +sequence-1+ [2 3 3 2 2 2 3 2 3 2 3 3 2 2 2 3 3])
(setv +sequence-2+ [2 2 2 2 2 2 2 3])

(defclass BendBot []
(defn --init-- [self &optional [round 0]]
(setv self.round round)
(setv self.opponent-record [])
(setv self.record [])
(setv self.turn -1)
(setv self.count-to-four 0)
(setv self.terminal-behavior False))

(defn move [self &optional [previous None]]
(+= self.turn 1)
(if previous
(.append self.opponent-record previous))
(setv output
(if (= self.opponent-record self.record)
(if (or (% self.round 2)
(< self.round 4))
(if (< self.turn (len +sequence-1+))
(. +sequence-1+ [self.turn])
(. +sequence-2+ [(% (- (len +sequence-1+)
self.turn)
(len +sequence-2+))]))
(if (< self.turn (len +sequence-1+))
(. (list (reversed +sequence-1+)) [self.turn])
(. +sequence-2+ [(% (- (len +sequence-1+)
self.turn)
(len +sequence-2+))])))
(if (< count-to-four 4)
(do
(+= count-to-four 1)
(if (= (last self.record) 3)
2
3))
(if (or self.terminal-behavior
(= 5 (+ (last self.record) previous)))
(if (= (last self.record) 3)
2
3)
(do
(setv self.terminal-behavior True)
(if (all (map (fn [x] (<= x 0)) self.opponent-record))
5
(all (map (fn [x] (<= x 1)) self.opponent-record))
4
(all (map (fn [x] (<= x 2)) self.opponent-record))
3
(if (> (+ (last self.record)
previous)
5)
3
2)
))))))
(.append self.record output)
output))

• See­ing peo­ple ac­tu­ally use Hy is mak­ing me nos­talgic!

• I love Hy and use it all the time for data sci­ence and other ap­pli­ca­tions. Thank you for all your work on the pro­ject!

• I’m sad that some peo­ple thought that more than two paren­the­sis was high risk to simu­late/​ex­am­ine—I thought that the ob­vi­ous thing to do was check to see if some­one ever loads code or uses a ran­dom func­tion, and if you don’t do ei­ther, you should be safe.

We’ll see how many peo­ple sub­mit­ted simu­la­tors braver than mine, but simu­la­tors be­ing timid seems like a nat­u­ral con­se­quence of the rules al­low­ing you to nuke your op­po­nent if you find out that you’re in a simu­la­tion, and a com­mon enough per­cep­tion that simu­la­tors might have enough of an ad­van­tage that they should be elimi­nated.

Static anal­y­sis is not very use­ful if the op­po­nent’s code is at all obfus­cated, which is likely is if your op­po­nent is look­ing to nuke simu­la­tors. Does your static anal­y­sis catch the code getattr(__built­ins__, ‘e’ + ‘x’ + ‘e’ + ‘c’)(base64.de­code(God knows what)) ? Or how­ever many dozens of other ways there are to do some­thing like that?

The tour­na­ment might look sig­nifi­cantly differ­ent if the rules were slanted in the simu­la­tor’s fa­vor, maybe if you just had to avoid in­finite simu­la­tion loops and keep run­time rea­son­able, and the worst the op­po­nent was al­lowed to do if they found they were in a simu­la­tion was to play Bul­lyBot in or­der to ex­tort you or play ran­domly to make the simu­la­tion use­less. The iter­ated pris­oner’s dilemma with shared source code tour­na­ment a few years ago had a lot of simu­la­tors, so I as­sume their rules were more friendly to simu­la­tors.

• I do think it would be hard to obfus­cate in a way that wasn’t fairly easy to de­tect as obfus­ca­tion. Throw out any­thing that uses import, any vari­ables with __ or a hand­ful of builtin func­tions and you should be good. (There’s only a small­ish list of built­ins, I couldn’t con­fi­dently say which ones to black­list right now but I do think some­one could figure out a safe list with­out too much trou­ble.) In fact, I can’t off­hand think of any rea­son a sim­ple bot would use strings ex­cept doc­strings, maybe throw out any­thing with those, too.

(Of course my “5% a CloneBot man­ages to act out” was wrong, so take that for what it’s worth.)

The iter­ated pris­oner’s dilemma with shared source code tour­na­ment a few years ago had a lot of simu­la­tors, so I as­sume their rules were more friendly to simu­la­tors.

I know of two such—one (re­sults—DMRB was mine) in Haskell where you could simu­late but not see source, and an ear­lier one (re­sults) in Scheme where you could see source.

I think in the Haskell one it would have been hard to figure out you were be­ing simu­lated. I’m not sure about the scheme one.

• The first line says “En­tries must be sub­mit­ted on Oc­to­ber 18, 2020, or ear­lier.”

Then a bit later you say “I will run my own ver­sion of the game on Oc­to­ber 16, 2020.”

Will you be mak­ing your time-travel tech­nol­ogy available to con­tes­tants’ bots, and if so what is the API they should use?

• Good ques­tion! My time travel tech­nol­ogy will not be available to con­tes­tants’ bots. This is in ac­cor­dance with Less Wrong’s es­tab­lished norm of con­tain­ing dan­ger­ous tech­nol­ogy.

I have ed­ited the origi­nal post in a fu­tile at­tempt to cover-up this leak and have re­moved the rele­vant API call from the extra mod­ule.

• Thanks for obey­ing the norms. That we definitely have. Around time travel tech­nol­ogy.

* never sets self.pre­vi­ous
* even if it was set, it would stop co­op­er­at­ing when op­po­nent played 0

Also I agree with Zvi’s com­ment, why 2.5 for free? This way one should re­ally con­cen­trate on max­ing out in the early stage, is it in­tended?

• I fixed the self.previous mis­take. I think I’ll leave the other bug as it is.

See this com­ment con­cern­ing 2.5.

• Will post a link to a github repo with my code later to­day (when I’m not meant to be work­ing), but for now, here’s my thought pro­cesses.

(Edit: my code is here. My en­try is in in­com­pre­hen­si­bot.)

Gen­eral strat­egy:

I was un­de­cided on join­ing the clique, but cu­ri­ous. I didn’t want to be a sucker if some­one (pos­si­bly the clique or­ga­nizer) found a way to be­tray it. I sent out feel­ers, and Vanilla_Cabs shared the clique bot code with me.

I saw a way to defect against the clique. I think that’s when I de­cided to do so, though I may have had the idea in my head be­fore­hand. I would call my en­try “bas­tardBot” and it would be glo­ri­ous. I told Vanilla_Cabs I was in. They asked if the code was air­tight. “I don’t see any­thing I want to flag.”

Some­one else found that same bug, and was more hon­est than I. I spent some time try­ing to work around the fix, but couldn’t see any­thing. I tried to get Vanilla_cabs to put a new hole in, un­der the pre­text that I wanted some code at the top level—this was true, but it was only marginally use­ful. I couldn’t think of any new holes that wouldn’t be re­ally freak­ing ob­vi­ous, so in­stead I tried be­ing vague about my re­quire­ments to see if they’d sug­gest some­thing I could use, but they didn’t. Even­tu­ally we just set­tled on “the ex­act line foo = 'bar' is per­mit­ted as an ex­cep­tion”, and I didn’t see what I could do with that.

Later, lsusr told me that that line would get me dis­qual­ified. I didn’t say any­thing, in the hopes some clique mem­ber would won­der what it was for, in­clude it in their bot just in case, and get dis­qual­ified.

I feel a lit­tle bad about all this, and hope Vanilla_cabs has no hard feel­ings.

My backup plan was: don’t let any­one simu­late me, and get them dis­qual­ified if they try. (New name: “in­com­pre­hen­si­bot”.) “jailbreaker.py” shows my tricks here. Defense seemed more effec­tive than offense, and I didn’t think I could safely simu­late my op­po­nent, and es­pe­cially not do so safely and use­fully within the time limits, so I gave up on the idea. As for my ac­tual moves, I didn’t have much in mind. After reread­ing (or at least reskim­ming) “the Dar­win pregame” I set­tled on this:

After the show­down round, start off with some­thing like Zvi’s “I’ll let you do bet­ter than me, but you could do even bet­ter by co­op­er­at­ing with me”. Grad­u­ally move to­wards “I won’t let you do bet­ter than me” as time pro­gresses; if my op­po­nent had more than a cer­tain num­ber of points than me, I’d re­fuse to play less than 3. (I chose the num­ber of points based on ex­pect­ing 550 turns on av­er­age, and gave it a min­i­mum of 5 to al­low some co­or­di­na­tion dance early on.) Early on, skew to­wards play­ing 2 ini­tially; if op­po­nents ran­dom­ize be­tween 2 and 3, and pick 3 with prob­a­bil­ity >= 13, then 2 max­i­mizes my score. Later, skew to­wards play­ing 3 ini­tially, which in­creases my prob­a­bil­ity of beat­ing my op­po­nent.

pay­load.py” shows my ap­proach here. I mod­el­led it off the early-round CloneBot moves against non-clones. If last round had been a to­tal of 5, I’d play their last move. If it had been 4, I’d do the same, but maybe add a lit­tle. If it had been more, I’d re­peat my own move, but maybe sub­tract one. In the 5 and >5 cases, I had some “push­ing” be­havi­our to see if I could ex­ploit them: if I haven’t had a chance to push yet, or if push­ing had worked well (or seemed like it would have worked well) in the past, or if I just hadn’t tried it re­cently, I’d try to take one more point than I re­ally had any right to. I didn’t do that in the <5 case be­cause that situ­a­tion was my only source of ran­dom­ness, which seemed im­por­tant some­how.

(I’m a bit con­fused about, if the last-round to­tal isn’t five, should I base off my own pre­vi­ous move or theirs? My de­ci­sions here weren’t prin­ci­pled.)

If this made me play 0 (I dunno if it ever would), I’d make it a 1. If it made me play less than 3, and I was too far be­hind (de­pend­ing on round), I’d make it a 3.

Just be­fore I went to bed Satur­day night, some­one sent a mes­sage to the clique group say­ing not to try to break simu­la­tors. Be­cause if a clique mem­ber simu­lates us and gets dis­qual­ified, the tour­na­ment is restarted and the clique is smaller. That was com­pletely right, and I felt stupid for not think­ing of it sooner.

I still de­cided to ig­nore it, be­cause I thought the game would be small enough that “fewer op­po­nents” was bet­ter than “big­ger clique”. Overnight some­one else said they’d already sub­mit­ted a simu­la­tion-breaker, so I dunno if any­one ended up play­ing a simu­la­tor.

Right to­wards the end I started do­ing nu­mer­i­cal anal­y­sis, be­cause early on I was too en­am­oured with my own clev­er­ness to no­tice what a good idea it was. I didn’t have time to do any­thing thor­oughly, but based on run­ning my paload against Three­Bot (which gets 148-222 early, 10-15 late) I re­duced my ex­ploita­bil­ity ramp-down from 100 rounds (cho­sen fairly ar­bi­trar­ily) to 20 (still fairly ar­bi­trary). Come to think of it, I don’t think I com­pared “what pro­por­tion of the pool do I need to even­tu­ally win” be­tween my early and late game be­hav­iors.

It would have been in­ter­est­ing to have some kind of log­ging such that my bot could re­port “I think I’m be­ing simu­lated right now, and this is how I know” and af­ter­wards lsusr could me how of­ten that hap­pened. I as­sume that would be sig­nifi­cant work for lsusr to set up though, and it adds at­tack sur­face.

Pre­dic­tions:

• I win: 20%.

• A CloneBot wins: 75%.

• At least one clique mem­ber sub­mits a non-CloneBot (by ac­ci­dent or de­sign): 60%.

• At least one clique mem­ber fails to sub­mit any­thing: 60%.

• At least one bot tries to simu­late me af­ter the show­down and doesn’t get dis­qual­ified: 10%.

• At least one bot tries to simu­late me af­ter the show­down and suc­ceeds: 5%.

• At least one CloneBot man­ages to act out: 5%.

• I get dis­qual­ified: 5%.

• *At least one bot tries to simu­late me af­ter the show­down and doesn’t get dis­qual­ified: 10%.

• At least one bot tries to simu­late me af­ter the show­down and suc­ceeds: 5%.

I now think these were over­con­fi­dent. I think it would be fairly easy to simu­late in­com­pre­hen­si­bot safely; but hard to simu­late in­com­pre­hen­si­bot in a way that would be both safe and gener­i­cally use­ful.

The difficulty with simu­lat­ing is that you need to track your op­po­nent’s in­ter­nal state. If you just call MyOpponentBot(round).move(myLastMove) you’ll be simu­lat­ing “what does my op­po­nent do on the first turn of the game, if it gets told that my last move was...”. If you do this against in­com­pre­hen­si­bot, and myLastMove is not None, in­com­pre­hen­si­bot will figure out what’s up and try to crash you.

So at the be­gin­ning, you ini­tial­ize self.opponent = MyOpponentBot(round). And then ev­ery turn, you call self.opponent.move(myLastMove) to see what it’s go­ing to do next. I don’t ex­pect in­com­pre­hen­si­bot to figure this out.

But if your op­po­nent has any ran­dom com­po­nent to it, you want to do that a cou­ple of times at least to see what’s go­ing to hap­pen. But if you call that func­tion mul­ti­ple times, you’re in­stead simu­lat­ing “what does my op­po­nent do if it sees me play myLastMove sev­eral times in a row”. And so you need to re­set state us­ing deepcopy or mul­ti­pro­cess­ing or some­thing, and in­com­pre­hen­si­bot has ways to figure out if you’ve done that. (Or I sup­pose you can just ini­tial­ize a fresh copy and loop over the game his­tory run­ning .move(), which would be safe.)

But ac­tu­ally, the sim­ple “ini­tial­ize once and call .move() once per turn” isn’t ob­vi­ously ter­rible? Espe­cially if you keep track of your pre­dic­tions and stop pay­ing at­ten­tion to them once they de­vi­ate more than a cer­tain amount (pos­si­bly zero) from re­al­ity. And Tale­un­tum’s bot might catch that, I’m not sure, but I think In­com­pre­hen­si­bot wouldn’t.

I think at some point I de­cided ba­si­cally no one would do that, and then at some other point I for­got that it was even a pos­si­bil­ity? But I now think that was silly of me, and some­one might well do that and last un­til the show­down round. Try­ing to put a num­ber on that would in­volve think­ing in more depth than I did for any of my other pre­dic­tions, so I’m not go­ing to try, just leave this note.

• The links you posted do not work for me. (Nev­er­mind)

Wow, you are re­ally con­fi­dent in you win­ning. There are 10 play­ers in the clique, so even if there are no play­ers out­side the clique (a du­bi­ous as­sump­tion) a pri­ori there is 10% chance. If I had money I would bet with you.

I also think there is a good chance that a CloneBot wins. 10 pos­si­ble mem­ber is a good num­ber imo. i would say 80%.

I would say 70% for the (pos­si­bly ac­ci­den­tal) be­trayal.

Without see­ing your jailbreak.py I can’t say how likely that oth­ers are able to simu­late you.

What does “act out” mean in this con­text?

• Con­di­tioned on “any CloneBot wins” I’ve given my­self about 25%.

10% in that con­di­tional would definitely be too low—I think I have above-baseline chances on all of “suc­cess­fully sub­mit a bot”, “bot is a CloneBot” and “don’t get dis­qual­ified”. I think I ex­pect at least three to fall to those hur­dles, and five wouldn’t sur­prise me. And of the rest, I still don’t nec­es­sar­ily ex­pect most of them to be very se­ri­ous at­tempts.

By “act out” I mean it’s a bot that’s rec­og­nized as a CloneBot by the oth­ers but doesn’t act like one—most likely co­op­er­at­ing with non-clones, but not-co­op­er­at­ing with clones would also count, it would just be silly as far as I can tell. I also in­clude such a bot as a CloneBot for the 75%.

• Up­dated with a link to my code. I also put yours in to see how we’d fare against each other one-on-one—from quick ex­per­i­men­ta­tion, looks like we both get close to 2.5 points/​turn, but I ex­ploit you for ap­prox­i­mately one point ev­ery few hun­dred turns, leav­ing me the even­tual vic­tor. :D I haven’t looked closely to see where that comes from.

Of course too much de­pends on what other bots are around.

• They asked if the code was air­tight. “I don’t see any­thing I want to flag.”

And I saw right through that my friend :D

As I said in my re­ply to Tale­un­tum, I left the weak­ness as a test to find some­one I could trust to find sneak­ier weak­nesses. Of you three who saw the code, only Lan­rian re­ported. “I don’t see any­thing I want to flag.” That’s cute. To be more ac­cu­rate, I wasn’t sure you were hid­ing a se­cu­rity flaw, but I didn’t have to be sure since ei­ther way meant I couldn’t en­trust you with the task. And the word­ing left me think­ing you were hid­ing a se­cu­rity flaw with 80% cre­dence. I thought about ask­ing “Did you see any­thing worth flag­ging?”, but de­cided against it.

Later, lsusr told me that that line would get me dis­qual­ified. I didn’t say any­thing, in the hopes some clique mem­ber would won­der what it was for, in­clude it in their bot just in case, and get dis­qual­ified.

I feel a lit­tle bad about all this, and hope Vanilla_cabs has no hard feel­ings.

Not at all, I just feel like I’ve dodged a big bul­let. How come that line would get some­one dis­qual­ified? Has lsusr been more spe­cific?

• Well played!

• I fell for

Even­tu­ally we just set­tled on “the ex­act line foo = ‘bar’ is per­mit­ted as an ex­cep­tion”, and I didn’t see what I could do with that.

Later, lsusr told me that that line would get me dis­qual­ified. I didn’t say any­thing, in the hopes some clique mem­ber would won­der what it was for, in­clude it in their bot just in case, and get dis­qual­ified.

I thought it would be harm­less and that there was some chance (even though it would make more sense to read some code­word di­rectly from the pay­load) that some­one would be us­ing it as a recog­ni­tion sig­nal to boost a cho­sen clique mem­ber’s bot us­ing a non clique mem­ber’s bot.

Is it re­ally dis­qual­ifi­able? I am not us­ing foo for any­thing else other than set­ting it.

• Put­ting data in global state is for­bid­den, yeah, even if you don’t do any­thing with it. I was a bit sur­prised.

Just to be clear, this would only be for­bid­den if you put it at the top level. If you put it in your class it would be fine. So

class CloneBot():
...
...

foo = 'bar' # allowed

foo = 'bar' # forbidden

• The par­ent com­ment comes from a pri­vate con­ver­sa­tion be­tween me and philh in which I con­veyed er­ro­neous in­for­ma­tion. The mis­take is my fault—not philh’s. A line such as foo = 'bar' is le­gal in some con­texts. A line which uses the global names­pace to pre­serve in­for­ma­tion be­tween class in­stances is ille­gal.

• Yeah, I put it in at top level.

• Disqual­ify­ing play­ers for things they ob­vi­ously wouldn’t do if they knew the rules of the game seems pretty cruel. I hope isusr just deletes that line for you.

• simon will not be dis­qual­ified.

• Thanks!

• Set­ting con­stants into the global state of your own file is fine. What I care about is whether you’re set­ting vari­ables into the global state for the pur­pose of pre­serv­ing in­for­ma­tion be­tween bot in­stan­ti­a­tions or oth­er­wise mess­ing with the game en­g­ine. simon’s bot clearly does nei­ther.

• I con­fess I’m a bit con­fused, I thought in our PM con­ver­sa­tion I was fairly ex­plicit that that’s what I was ask­ing about, and you were fairly ex­plicit that it was for­bid­den?

It’s not a big deal—even if this was for­bid­den I’d think it would be to­tally fine not to dis­qual­ify simon, and I still don’t ac­tu­ally ex­pect it to have been use­ful for me.

• In my pri­vate con­ver­sa­tion with you (philh) I stated “Writ­ing vari­ables to the global names­pace is for­bid­den.” I then dou­bled down on the er­ror by stat­ing “Yes. All data must be saved in a class in­stance.”

I apol­o­gize for the er­ror. What I should have writ­ten was that us­ing the global names­pace to get around in­for­ma­tion re­stric­tions is ille­gal but that writ­ing con­stants to your mod­ule’s global names­pace in a way that does not evade in­for­ma­tion re­stric­tions is fine.

• What time­zome is the dead­line in? Or to be max­i­mally pre­cise – can you give a fi­nal sub­mis­sion-hour in UTC?

• Great ini­ti­a­tive, thanks for or­ga­niz­ing!

• Fun! Note that the “au­to­matic recog­ni­tion of self” and “group, not in­di­vi­d­ual fit­ness” rules are differ­ent from many such con­tests. I think it’s likely that this al­lows su­per-sim­ple bots to win, if the ini­tial mix al­lows them to get past the first few iter­a­tions.

I’d pre­dict three-bot is the most likely sim­ple win­ner—it gets full value against it­self (as does ev­ery­one), and gets some points for all op­po­nents’ probes and com­plex sig­nal­ing (that in­cludes bid­ding 0, 1, or 2). It NEVER gives an op­po­nent more points than it gets.

When you add in truly so­phis­ti­cated bots, who ex­ploit each other based on knowl­edge of the mix of op­po­nents, they can do enough bet­ter in early rounds for three-bot to never get crit­i­cal mass. Like­wise for co­or­di­nated bots who can ac­cu­rately de­tect each other, get­ting full value for more cases than non-co­or­di­nated ones.

edit: af­ter read­ing Zvi’s old posts, I re­al­ize two things:

1. auto-self-recog­ni­tion (but not auto-part­ner recog­ni­tion) is weird, and prob­a­bly changes the cor­rect ex­plore-ex­ploit strat­egy sig­nifi­cantly. Per­haps not as far to­ward the sim­ple as I pro­pose, above—part­ner recog­ni­tion is go­ing to be im­por­tant.

2. start­ing mix mat­ters a whole lot. it’ll be a very differ­ent game with 100,000 ini­tial pro­grams than with 50. And there will be a group­think com­po­nent—there’s no way to avoid the meta-game of un-en­forced part­ner­ships.

• I’d pre­dict three-bot is the most likely sim­ple winner

I hope not too many other clique mem­bers sub­mit­ted 3-bot (we will de­stroy each other then, as­sum­ing mul­ti­core hasn’t already taken over by the show­down time).

• Wouldn’t three-bot only get a few points against tit-for-tat bots? I agree it can’t do worse than its op­po­nent (mean­ing it would at worst tie if it is one of the last two bots), but bots that can co­op­er­ate or even two-bot could be rak­ing in a lot more points as long as the pop­u­la­tion of bots isn’t dom­i­nated by three-bot.

For ex­am­ple, in a given round if three-bot is vers­ing tit for tat, it might get a few points right away and then no more, but in that same round, two tit for tat bots or a tit for tat and a two-bot are get­ting a com­par­a­tively large amount of points mean­ing they will dom­i­nate later rounds so I think two-bot is a bet­ter sim­ple strat­egy than three-bot (granted it will not win).

• Auto-self-recog­ni­tion is triv­ial when you have the abil­ity to read op­po­nent’s source code. You can de­tect you’re play­ing against a copy of your­self and your ‘op­po­nent’ will do the same. Although in this case you will lose a small amount of points ran­domly de­cid­ing which bot will choose 3 and the other 2 as­sum­ing there is no de­ter­minis­tic way to differ­en­ti­ate the clones.

ETA: I see that you posted your com­ment be­fore Isusr said you could view op­po­nent’s source.

• A thought for next time, if you want to build a simu­la­tor, it could make sense to wait one round be­fore simu­lat­ing any­thing even slightly un­safe, and do some­thing sim­pler in round 1. That way, if some­thing weird might po­ten­tially dis­qual­ify you but will it­self get dis­qual­ified, it dies be­fore it can re­move you from the pool.

• I don’t know whether it’s a com­pet­i­tive en­try (it would be a FoldBot in Zvi’s tax­on­omy), but as a quick piece of soft­ware, I’m pretty proud of AbstractSpyTreeBot!

• You should also check whether ‘exec’ is in the pro­gram code string, be­cause some­one could call getop­po­nentsource with exec and cae­sar-en­cryp­tion, oth­er­wise you will be DQ’d if some­one sub­mits a pro­gram like that. (How­ever, re­bind­ing getop­po­nentsource is prob­a­bly more el­e­gant than this type of static anal­y­sis.)

• This seems to only simu­late the op­po­nent’s first move, and then act as if the op­po­nent will make that move ev­ery round.

For the most part this is a good refer­ence im­ple­men­ta­tion though, and I ex­pect I’ll be bor­row­ing from it in my sub­mis­sion.

• An in­ter­est­ing bot for simu­la­tors to grap­ple with is this:

class Bul­lyBot:

def __init__(self, round=0):

self.op­po­nen­tThree­sPlayed = 0

def move(self, pre­vi­ous=None):

if self.op­po­nen­tThree­sPlayed > 3:

re­turn previous

elif pre­vi­ous == 3:

self.op­po­nen­tThree­sPlayed+=1

if self.op­po­nen­tThree­sPlayed > 3:

re­turn 2

re­turn 3

Some­thing that holds out just long enough to get a naive simu­la­tor to fold to it for­ever, but will prob­a­bly end up co­op­er­at­ing with most oth­ers.

• Com­pet­i­tive or not it is tech­ni­cally com­pet­ing. Wel­come to the game!

• To check, what time­zone is the dead­line in?

• Pa­cific Time Zone.

• This is the Nash bar­gain­ing game. Is there some spe­cific rea­son to call it a “Pri­soner’s Dilemma vari­a­tion”, or is it just “ev­ery­one has heard of the Pri­soner’s Dilemma, and don’t have a generic term for this kind of game-the­ory tour­na­ment”?

• It’s the lat­ter.

• I’m a non pro­gram­mer, if I sub­mit­ted a bot that’s too com­pli­cated or that is sup­posed to do some­thing that isn’t a pos­si­ble move, would I be con­tacted and get a chance to change it, pro­vided I sub­mit it early enough?

Could you provide one or more ex­am­ples of too com­pli­cated de­scrip­tions, just so I know for which level of com­plex­ity I should aim? I’m not clear on how you would con­sider a bot that has a de­ci­sion three with differ­ent op­tions and pro­cesses but no part that’s hard to pro­gram, for ex­am­ple. (To avoid giv­ing hints or good ideas, they can be filled with com­pletely stupid in­struc­tions or be for bots that try to do some other stuff)

• If you’re wor­ried whether some­thing is too com­pli­cated then the best solu­tion is to PM me with your most com­pli­cated dream bot and I’ll tell you how much of it I’m will­ing to code.

An ex­am­ple of some­thing that is too com­pli­cated is Zach_M_Davis’s Ab­strac­tSpyTreeBot which runs a simu­la­tion of its op­po­nent. Another ex­am­ple of some­thing too com­pli­cated is is a neu­ral net­work trained on your op­po­nent’s past his­tory. Such bots are perfectly le­gal if you code them your­self to rea­son­able speed con­straints but I will not write one for you.

A hard-coded de­ci­sion tree with sev­eral un­am­bigu­ously-speci­fied sim­ple op­tions is well within rea­son if that is all there is to it and you write a good speci­fi­ca­tion. For ex­am­ple, us­ing reg­u­lar ex­pres­sions to an­a­lyze your op­po­nent’s source code if fine.

• That sounds perfect, thank you.

I’m sorry to ask for an­other de­tail, but I’m not 100% sure if simu­la­tor-bots such as Ab­strac­tSpyTreeBot are le­gal if you can pro­gram them your­self. Your re­ply seems to state so, but I didn’t wanted to as­sume.

• Si­mu­la­tor bots are le­gal for pro­gram­mers to write pro­vided they never crash, slow the game to a crawl, etc. Any bot (even a non-simu­la­tor) that does will be dis­qual­ified.

I have not yet read the AbstractSpyTreeBot source code in de­tail nor run it my­self. A cur­sory glance sug­gests it’s within the rules.

• What are the rules about pro­gram run­time?

• Vague. The only limi­ta­tions are ob­vi­ous stuff like hack­ing the game client to get around in­for­ma­tion re­stric­tions, us­ing so much com­pute you slow the game it­self to a crawl, in­stal­ling any­thing that takes me sig­nifi­cant effort to set up and any­thing I con­sider a se­cu­rity risk. You may PM me for clar­ifi­ca­tion on your spe­cific situ­a­tion. I can eas­ily perform speed tests as I have already writ­ten the game client.

If you are a pro­gram­mer then you may re­quest rea­son­able fea­tures such as read­ing your op­po­nent’s source code.

Edit #1: In or­der to max­i­mize re­source use, you may provide an ad­justable con­stant such as TREE_DEPTH.

Edit #2: Any code that can always com­plete 10,000 move calls within 5 sec­onds is guaran­teed to be “fast enough”.

• What do you mean by in­for­ma­tion re­stric­tions? What ex­actly is re­stricted? If I were to use some side-chan­nel to de­ter­mine that I was be­ing simu­lated by an op­po­nent and fork­bomb if so, would I be elimi­nated for hack­ing? Would they be elimi­nated for overus­ing com­pute? (af­ter all, it wasn’t my code per say that fork­bombed, but their code simu­lat­ing my code) Would I be elimi­nated for be­ing a dick? (Which would be self-ev­i­dent, at any rate)

You say in an­other com­ment, “Si­mu­la­tor bots are le­gal for pro­gram­mers to write pro­vided they never crash, slow the game to a crawl, etc. Any bot (even a non-simu­la­tor) that does will be dis­qual­ified.” I’m just con­cerned about the edge case where some­one writes the troll code de­scribed above, and sud­denly ev­ery per­son who sub­mit­ted a simu­la­tor bot (i.e. Zak M. Davis) gets DQ’d. The rules as writ­ten sug­gest that such a bot (pre­sum­ing it does not pre­serve in­for­ma­tion across rounds) would be perfectly le­gal and it’s Zak’s own fault for ex­e­cut­ing un­trusted code, but that seems to effec­tively pro­hibit simu­la­tors as there’s an in­finite plu­ral­ity of side-chan­nels through which to do this.

A few pos­si­ble re­s­olu­tions would be:

1. Who­ever wrote the code that con­tains the in­struc­tions to fork­bomb is at fault. Essen­tially, don’t be a dick.

2. Any in­for­ma­tion not ex­plic­itly given is for­bid­den. Essen­tially, you don’t know if you’re be­ing simu­lated, and you’re not al­lowed to find out.

3. Un­trusted code is un­trusted code; simu­late at your own risk. Essen­tially, if Zak ex­e­cutes my fork­bomb, that’s his prob­lem. (Well, your prob­lem as well to fix it, but his fault.)

Re­s­olu­tion 2 seems the most rea­son­able to me, but if you choose it I humbly re­quest a way to lo­cally over­write get_op­po­nent_source so you simu­late your op­po­nent’s re­sponse with­out risk­ing in­finite re­cur­sion. (Such an over­write is prob­a­bly stan­dard python, but be­ing ig­no­rant of your im­ple­men­ta­tion I’d be con­cerned about screw­ing some­thing up and not be­ing able to de­tect the mis­take in test­ing)

EDIT: Upon fur­ther con­sid­er­a­tion it seems in­evitable that Zak will get DQ’d for in­finite re­cur­sion. So I must be miss­ing some­thing.

• Hack­ing the game en­g­ine is against the rules. If your op­po­nent de­cides to simu­late your code then hack­ing them from in­side your op­po­nents’ simu­la­tion is al­lowed. Your code is al­lowed to peek at the game en­g­ine for the pur­poses of figur­ing out if it is be­ing simu­lated by some­one else’s code. Peek­ing at the game en­g­ine for other rea­sons, like figur­ing out how many of each op­po­nents re­main or at­tempt­ing to mod­ify the game en­g­ine it­self or at­tempt­ing to mod­ify your op­po­nents’ code from any­where out­side their own simu­la­tion of you is against the rules.

Any­thing that could dam­age the game’s ex­e­cu­tion en­vi­ron­ment is a se­cu­rity risk and grounds for dis­qual­ifi­ca­tion. Fork­bomb­ing your op­po­nent is re­ally push­ing things…but tech­ni­cally le­gal. I would pre­fer some­thing more mun­dane like call­ing exit() or an in­finite loop. Any­thing more dam­ag­ing than a fork­bomb con­sti­tutes a se­cu­rity risk and is not al­lowed un­der any cir­cum­stances. If you are go­ing to write any malware-like then code (in­clud­ing fork­bombs) then please draw my at­ten­tion to it in some way what the in­tended be­hav­ior is so I can miti­gate any un­in­tended con­se­quences to my own sys­tems. Even bet­ter would be to PM me for ex­plicit per­mis­sion.

Any code which gets dis­abled by malware will get dis­qual­ified from the tour­na­ment. I will then restart the tour­na­ment with the bro­ken com­peti­tor(s) re­moved.

The re­s­olu­tion is #3 “Un­trusted code is un­trusted code; simu­late at your own risk.”

The func­tion get_opponent_source re­turns source code as a string. You can triv­ially over­write it in your lo­cal en­vi­ron­ment with the com­mand get_opponent_source = my_custom_get_opponent_source. (This is stan­dard Python.) If you ex­e­cute your op­po­nent’s code in a simu­la­tion where get_opponent_source has been re­bound[1] to a new func­tion (and have not oth­er­wise left al­ter­nate at­tack vec­tors open) I see no rea­son why this would would trig­ger in­finite re­cur­sion.

If you re­bind the get_opponent_source func­tion in your lo­cal en­vi­ron­ment in a rea­son­able way that is it­self ob­vi­ously not an at­tempt to breach any­thing then I will con­sider that a bug in the game en­g­ine and at­tempt to en­g­ineer a fix.

I have not yet read over Zak’s code in de­tail nor have I at­tempted to ex­e­cute it. If it in­finitely re­curses then it will be dis­qual­ified.

1. Edit: Do note that an un­obfus­cated simu­la­tor bot is likely to have a state­ment some­thing along the lines of from extra import get_opponent_source. If you over­write the get_opponent_source func­tion and then ex­e­cute your op­po­nent’s code, it is pos­si­ble your op­po­nent’s from extra import get_opponent_source may un-over­write your re­bind­ing. ↩︎

• In what or­der do pro­grams get dis­qual­ified? For ex­am­ple, if I sub­mit a pro­gram with an in­finite loop, ev­ery other pro­gram us­ing simu­la­tion will also go into in­finite loop when meet­ing with my pro­gram as de­tect­ing in­finite loops gen­er­ally isn’t the­o­ret­i­cally fea­si­ble. Is my pro­gram dis­qual­ified be­fore the oth­ers? What is the gen­eral prin­ci­ple?

EDIT: An un­re­lated ques­tion: Do round num­bers start from 0 or 1? In the post you write “Un­like Zvi’s origi­nal game, you do get to know what round it is. Rounds are in­dexed start­ing at 0.”, but also: “Your class must have an __init__(self, round=1) [..]”. Why not have the de­fault ini­tial­izer also use 0 if the round num­bers start from zero?

• First a run your pro­gram against one or more sim­ple pro­grams with­out any simu­la­tions. If your pro­gram hits an in­finite loop there then you will be dis­qual­ified be­fore you get to in­fect any other pro­grams. In this way you can be dis­qual­ified be­fore the oth­ers.

If your pro­gram passes the sim­ple tests then it will join the pool and against all other pro­grams which have passed the ini­tial test. All pro­grams which fail to ter­mi­nate at this stage will be re­moved si­mul­ta­neously.

Thank you for the bug re­port. I have cor­rected __init__(self, round=1) [..] to __init__(self, round=0) [..]

• Hm. Can we get a “you can use at least this amount of time per move and not be dis­qual­ified”? Without want­ing to say too much, I have a strat­egy in mind that would rely on know­ing a cer­tain run­time is safe. (Allow­ing for some amount of jank­i­ness, so that if the limit was 5s I’d con­sider 4s safe.)

• I will not dis­qual­ify any­one who can com­plete 100 move calls in 5 sec­onds (0.05 sec­onds per call on av­er­age) on my T450s.

I will not dis­qual­ify any­one who can com­plete 100 move calls in 0.05 sec­onds on my T450s.

Edit: Cor­rected time limit down­ward by 100×.

• Thanks. I con­fess I’d been hop­ing for more like 100x that, but not re­ally ex­pect­ing it :p

• My pre­vi­ous an­swer was a mis­take. It is ac­tu­ally 100 move calls in 0.05 sec­onds. Sorry.

The num­bers are bru­tal.

If a game goes for 50 rounds and 10 differ­ent bots each use 5[1] sec­onds per move and there are 550 moves per bot per pairing then it would take 4.36 years to run this tour­na­ment.

How­ever, do note that the guaran­tee is “0.05 sec­onds per 100 moves” as op­posed to “0.0005 sec­onds per move”. If you only have to run ex­pen­sive com­pu­ta­tions once then, de­pend­ing on your al­gorithm, the right caching sys­tem might get you close to 100× perfor­mance.

I can add caching func­tions to the extra pack­age if that would help. The com­puter in ques­tion has 4 pro­ces­sors and runs Linux so mul­ti­pro­cess­ing can get you up to a 4× speedup.

1. 500 sec­onds per move is 100× my origi­nal limit which equals 10,000× the cor­rected limit. ↩︎

• Oh, geez. I figured it would be too long, but I didn’t think about just how much too long. Yeah, with these con­straints, even 5s per hun­dred moves I agree is un­rea­son­able.

Cach­ing seems easy enough to im­ple­ment in­de­pen­dently, I think. No need for you to add it.

• Is ev­ery­body’s code go­ing to be in Python?

• The rules are that, from the game en­g­ine’s per­spec­tive, ev­ery­one’s code is go­ing to be writ­ten in Python 3 or Hy. It is the­o­ret­i­cally pos­si­ble that some­one’s code might, say, in­clude some code in a differ­ent lan­guage that is then ex­e­cuted from the Python run­time.

• I don’t know how likely it is to make a differ­ence, but what ver­sion of python 3?

• Python 3.6.9 or Hy 0.18.0.

• When does this start?

• As soon as I can. Hope­fully by the end of this week.

• If you face a copy of your­self you are au­to­mat­i­cally awarded the max­i­mum 5 points per round

What’s your ra­tio­nale be­hind this? Isn’t part of the point that you need to be able to sur­vive even in an ecosys­tem con­sist­ing mainly of you?

• Are com­ments al­lowed?

• Like in the code?

# Comments are allowed in the code.

• Is the num­ber of rounds per matchup go­ing to be in the tens, or the thou­sands?

Edit: I just re­al­ised you speci­fied in the post

• The num­ber of turns per round is at least 100 and no more than 1000. I have not yet de­ter­mined the num­ber of rounds. If prac­ti­cal, I will iter­ate un­til there is a sta­ble equil­ibrium.

Edit: I have ed­ited the origi­nal post to re­flect the lat­ter state­ment about rounds.