The Darwin Game

lsusr

LESSWRONG
LW

2020 Less Wrong Darwin Game

91 The Darwin Game

by lsusr

9th Oct 2020

3 min read

131

91

~~Click here to participate. Entries must be submitted on October 18th, 2020 or earlier.~~

Entry is now closed.

In 2017, Zvi posted an exciting story about The Darwin Game, a variation of iterated prisoner's dilemma.

I will run my own version of the game in the week following October 18th, 2020. You do not have to know how to program in order to participate. I will code simple bots for non-programmers. If you do know how to program then you may create your own complicated bot.

Here are the rules. Changes from Zvi's original game are in brackets [like this].

For the first round, each player gets 100 copies of their program in the pool, and the pool pairs those programs at random. You can and often will play against yourself.

Each pair now plays an iterated prisoner’s dilemma variation, as follows. Each turn, each player simultaneously submits [an integer] from 0 to 5. If the two numbers add up to 5 or less, both players earn points equal to their number. If the two numbers add up to 6 or more, neither player gets points. This game then lasts for a large but unknown number of turns, so no one knows when the game is about to end; [I guarantee it will be at least 100 turns per iterated prisoner's dilemma].

Each pairing is independent of every other pairing. [You do know what round of the game it is and that you are facing an opponent. If you face a copy of yourself you are automatically awarded the maximum 5 points per round (2.5 points per bot). You otherwise do not know any history of the game to this point.] Your decision algorithm does the same thing each pairing.

At the end of the round, all of the points scored by all of your copies are combined. Your percentage of all the points scored by all programs becomes the percentage of the pool your program gets in the next round. So if you score 10% more points, you get 10% more copies next round, and over time successful programs will displace less successful programs. Hence the name, The Darwin Game.

Your goal is to have as many copies in the pool at the end of the last round as possible, or failing that, to survive as many rounds as possible with at least one copy.

[I will attempt to iterate until there is a stable equilibrium.]

I will add some silly bots of my own to make the early game more interesting.

Instructions for non-programmers

Please give a simple explanation of what you want your bot to do. Write it with mathematical precision. If your specification is even slightly ambiguous then you will be disqualified.

Instructions for programmers

Write a program of the following format.

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) intializer and a move(self, previous=None) method. You may write your class in Python 3 or Hy.

Unlike Zvi's original game, you do get to know what round it is. Rounds are indexed starting at 0. The previous parameter of the move method is an integer indicating what your opponent did last iteration. If it is the first iteration then previous equals None.

A new instance of your class will be initialized in each round. You may save whatever information you want into the class instance's fields but you may not save information between rounds or between class instantiations. The move method must always return an integer from 0 to 5 inclusive.

You may import standard libraries like random, scikit and numpy.

Coordinating with other players

Anyone can play, but only players with a Less Wrong account that existed before I declared this tournament will be allowed to coordinate out-of-game. This rule exists to prevent players from submitting multiple entries to this contest and self-coordinating. Coordinating with other people is encouraged. Coordinating with yourself between multiple separate entries is cheating.

~~Click here to participate. Entries must be submitted on October 18th, 2020 or earlier.~~

Entry is now closed.

Exercises / Problem-SetsGame TheoryProgrammingEvolutionPrisoner's DilemmaRationality

Frontpage

91

The Darwin Game - Rounds 0 to 10

34 comments107 karma

Mentioned in

107The Darwin Game - Rounds 0 to 10

48The Darwin Game - Rounds 1 to 2

45Final Babble Challenge (for now): 100 ways to light a candle

10Reward large contributions?

5The Mutant Game - Rounds 11 to 30

New Comment

131 comments, sorted by

top scoring

Click to highlight new comments since: Today at 2:15 AM

Some comments are truncated due to high volume. (⌘F to expand all)Change truncation settings

[-]Multicore4y430

tl;dr I betrayed the CloneBot clique and submitted MimicBot. My submission is in this Github repository.

My Process in chronological order:

There were three important things I noted in the original post

Self cooperation is free, so an early lead is a big advantage.
There are guaranteed to be “silly” bots in the early pool.
You can vary your strategy depending on the round.

It seemed to me that the best strategy was to get as many points as possible early by exploiting silly bots, cooperating with anyone willing to cooperate, and folding somewhat to attackers. Then later on just play a non-exploitable cooperative strategy and hope for your early advantage to snowball.

Simulation

After seeing AbstractSpyTreeBot and some of the comments around it, it seemed to me that simulation was perhaps the best way to take advantage of simple bots. There are various approaches you could take, but mine was to simulate every possible sequence of moves I could make for the next N turns, and use the one with the best outcome. Since this has exponential time complexity, I only considered the moves 2 and 3 and kept N fairly small, with the option for the game runner to reduce it further to improve performance.... (read more)

3Lukas Finnveden4y

Damn, good job. We should've gone with my suggestion that the whole payload needed to fit on one line, separated by ; (though maybe this would've caused us to lose so many clique-members out of annoyance that it wouldn't have been worth it).

1Vanilla_cabs4y

That's an idea worthy of consideration, but in addition to the risk you raised, I also feared some members would have submitted invalid bots.

2Lukas Finnveden4y

Yeah, if we'd seen the issue, I think we could've gotten around it just by not using splitlines, which would've been smoother. Though of course, this exploit updates me towards thinking that there are other vulnerabilities as well.

2philh4y

If we don't use splitlines we instead need to use something similar, right? Like, even if we don't need to worry about LF versus CRLF (which was a genuine suggestion I made), we still need to figure out if someone's got any de-indents after the start of the payload. And I don't expect us to do better without splitlines than with it.

1Lukas Finnveden4y

Using newlines to figure out what happens after "payload" is fine, as far as I can tell. Multicore's exploit relies on newlines being used when comparing stuff before the payload. Stuff like CRLF vs LF is a bit awkward, but can maybe be handled explicitly?

2philh4y

Oh yeah, that's true as far as I know. I guess it depends how much we trust ourselves to find all instances of this hole. A priori I would have thought "python sees a newline where splitlines doesn't" was just as likely as the reverse. (I'm actually not sure why we don't see it, I looked up what I thought was the source code for the function 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 implementation of it and a python implementation?)

3philh4y

Clever! I looked for holes in mostly the same directions as you and didn't find anything. I think I either didn't think of "things splitlines will split on but python won't", or if I did I dismissed it as being not useful because I didn't consider comments.

3Taleuntum4y

Your betrayal of the clique is very nice, hats off to you. I also liked your idea of getting others not that interested in the game to submit bots helping you, It's a pity it did not occur to me. However, I think you are, too, overconfident in you winning. I've run a simulation of the whole tournament till the 160th round with 8 bots (MatrixCrashingBot, TitforTatBot, PasswordBot1, PasswordBot2, EmptyCloneBot, earlybird, incomprehensiblebot, CliqueZviBot) and in the final equilibrium state there are three bots: earlybird, incomprehensiblebot and CliqueZviBot with roughly equal populations. While PasswordBots do help you at the start your lead seems to disappear later when the dumb bots and non-clique members die (which is nice, because your bot's output when simulating is pretty annoying). Sure, it's just one run of the tournament with a low number of participants (it's slow to do the tournament on my laptop), but it's something.

1Multicore4y

That does revise down my expectations of winning, but my bot having run thousands of times on someone else's computer and not crashing (or failing the clone check?) is good to hear. Maybe I'm overestimating the snowball effects of an early pool. If the late game has everyone cooperating with everyone else, your matches with others are only giving a tiny bit fewer points than matches against your copies.

2Vanilla_cabs4y

I gave an equal chance to an early newcomer and a late newcomer of trying to betray. Maybe I was wrong, and I should be mindful of that in the future. Also, I felt like our numbers were dangerously close to the minimum (6), and I expected a couple members to retract before I revealed the names (which di not happen). So in my mind I had no choice but to accept you. Good job! My plan for security was to leave an obvious vulnerability, and entrust members who would report with the task to look for more subtle ones. Only Lanrian reported, late in the week, and I didn't trust them enough because I was suspicious of their motive when they'd asked me for making our code easier to simulate (which turns out they were honest about).

[-]Zvi4y310

Free self recognition seems like it makes game less interesting, And that anyone who gets a big lead early just wins?

[-]Vanessa Kosoy4y110

Given that you can read the opponent's source code, self-recognition is trivial to implement anyway (trivial but annoying, since you need to do quining).

4lsusr4y

Since quining is "trivial but annoying", I am willing to provide a quining function in the extra package if anyone requests it.

8lsusr4y

I am aware of the potential strategic implication you bring up. However, as the organizer of this game, I believe it is my place neither to confirm nor deny beforehand any strategic implications of these rules. Explaining my rationale necessarily involves discussing the strategic implications. I will explain my rationale for this choice after the game.

7SarahSrinivasan4y

Eh, okay, but (prediction) this choice nudges me from "probably participate" to "probably ignore".

3Harmless4y

If I had to guess, the reasoning behind it is to nudge the game closer to a 'true' prisoner's dillemma (trying to work out if your opponent is willing to cooperate, rather taking focus away from it towards the shallower problem of trying to work out if your opponent is a copy of you)

8SarahSrinivasan4y

I agree, and this design avoids that problem, but seems to introduce a much larger one, assuming the intent also includes measuring bots on their ability to survive in progressively more "difficult" bot mixes, which "Darwin" seems to imply. This choice also nudges me from "has noodled around the idea of hosting a similar competition many times and probably won't" to "same, but slightly more likely to actually do it". :D

2Multicore4y

My suggestion for a future Darwin Game tournament is to get rid of the 0, 1, 4, and 5 moves, and leave 2 and 3 as the only legal moves. Serious bots generally don't need or use the other moves, so they mostly just make you add annoying special case logic to get a few more points out of GoofBots in the early game.

3John_Maxwell4y

It's a good point but in the original Darwin Game story, the opening sequence 2, 0, 2 was key to the plot.

5lsusr4y

Update: There are two primary reasons for free auto-recognition. Firstly, I promised to write bots for non-programmers and I didn't want to promise to implement an arbitrary number of bad crypto systems written by non-specialists. Secondly, I believe is is good game design to reward early aggression.

7Ericf4y

Reading the other's source code is a bigger change (actually, a superset of auto-recognizing self) It actually makes coordinating trivial and enforceable, since you can just check for the correct behavior & password before cooperating. And if you can run your opponent's source code...

1Oskar Mathiasen4y

If i had to guess on the motives, the last time a similar game was played (non publically) the meta developed to be about self recognizing, this is likely a rule to avoid this. Winning strategy was some key string to identify yourself, cooperate with yourselt, play 3 otherwise. (Granted number of iterations was low, so people might not have moved to be non cooperating strategies enough (something like grim trigger))

[-]johnswentworth4y230

Is reading the opponent's source code legal?

8lsusr4y

Yes. You may read the opponent's source code via the get_opponent_source(self) function. 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 Beware the halting problem. Infinite recursion constitutes overuse of compute resources and may be grounds for disqualification.

2Vanessa Kosoy4y

Is this disqualification in advance, or in run-time? That is, do you just look at the code and decide whether it's good, or do you give each program some bounded time and memory to run and disqualify it if any copy overflows it? (Btw another option would be, punish only that copy.)

4lsusr4y

Run-time. I disqualify the entire program—not just the one copy—and then restart the game with one (or fewer) competitors.

3kuudes4y

Does this open a security hole of future prediction like Spectre etc? Some bots could have a thing where they remember if they have met certain another bot (SignalBot) in the game. If they haven't, they decide that the game setup carries certain preset information. If the bots find out later in the game that the preset condition would be true, then they coordinate so that SignalBot causes infinite loop and gets disqualified and the game restarted. Now the game will miss SignalBot, causing the others to use this information to deduce the signalled information. Tl;dr: Givens: In some cases Left is best strategy. Otherwise Right is best strategy. 1. ForetellerBot observes SignalBot in the game, decides to play Right. 2. Bots observe Left is better strategy. 3. SignalBot nonhalts and gets thrown out, game is reset. 4. ForetellerBot observes no SignalBot in the game, decides to play Left.

3Multicore4y

OP said elsewhere in the comments (emphasis mine): And in the original post:

1kuudes4y

You are not peeking at the game engine, you can just message this the same as you can message cooperation (2, 0, 2 code etc). You also do not need to save any information over instances - all of your bots on a round are running on the same instance. If any of your ForetellerBots observes SignalBot, then SignalBot has not dropped. SignalBot's existence is in itself the flag.

4Multicore4y

A separate instance of each bot is created for each pairing in each round. All that ForetellerBot knows in any pairing is whether it is itself facing a SignalBot, not whether any of its copies are.

1kuudes4y

Thanks for the info. This conflicts with the specification of which I interpreted to mean that there exists exactly 1 instance of the class per round. The model you propose makes sense though, I guess my mental model of the thing was mistaken.

2John_Maxwell4y

Why does get_opponent_source take self as an argument?

3lsusr4y

There are two active bots. The self argument tells the game client which bot's code not to return.

3John_Maxwell4y

Thanks.

[-]Vanilla_cabs4y190

If you're participating in the contest and you want to win, I have a proposition for you:

Howdy! You've probably looked up Zvi's past Darwin game that directly inspired this one. A group of players formed a clique who recognized each other, cooperated among themselves and defected on everyone else. They nearly wiped the board, but they were preyed upon by a member who played both sides.

What they missed was a way to guarantee that all members apply the decided strategy. They had no way to enforce it.

But we have a way.

I call it CloneBot: a bot who checks that its opponent has the exact same code as itself. No way to cheat that! It guarantees that every member of the clique does the same thing. Moreover, there'll be a way to cooperate optimally, avoiding losing the first rounds to coordinate. The clique are gonna be the most efficient ccoperators.

But in the end we're all gonna tie, it's boring. I want to take a chance at winning!

So do I. This is why the clique are only going to collaborate until a predefined round. After we've eliminated the competition, we can have a dramatic showdown among ourselves. Cool, no? In the code, there's gonna be a separate function that's called only after... (read more)

5Measure4y

I don't approve of this. Assuming that everyone who pledges to join the clique actually submits a CloneBot and nobody finds a way to beat the recognition code and defect from the clique, and assuming there isn't a subtle bug in the code that disqualifies some or all of the clones, then the clone cohort can indeed eliminate 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 everyone goes through with this, then of course I'd be better off submitting a clone myself (again assuming no cheating/errors/etc. - I would certainly need to see the code myself before deciding to join), but this is a bit different from typical public-goods-type pledges. Typically, everyone wants the thing done but given that it is done would individually rather not contribute. Here everyone would rather the thing not be done, but given that it is done would individually rather contribute. This is a straightforward example of a bad equilibrium. If you have pledged, or are thinking of pledging, consider: * How surprised would you be if a bug in the CloneBot code disqualified all the clones? * How surprised would you be if someone managed to bypass the code checking and defect from the group? * How surprised would you be if one or more people who pledged didn't actually submit a CloneBot? * Is this the kind of equilibrium you want to encourage?

1Vanilla_cabs4y

I get it that you don't like that players join forces. I am not sure I'd allow coordination if I had a say on the rules. But per the rules coordination is part of the game. That's it. For all we know, others are making cliques in secret. I believe my scheme substantially increases our chances of winning, so I'll go with that. Admissions are closing soon. Good luck, whatever you decide :)

2Measure4y

I can't say it's not fair, and I do realize you've put a lot of work into this. Have you decided to make the clone code public?

3Vanilla_cabs4y

At least one member asked for a basic obfuscation measure. Publishing the code would defeat their purpose. Also, from an insider's perspective, publishing the code now would only slightly increase our chances to get another member before the end of admissions, while it would entail a significant risk of opponents adjusting their strategy against it. I should have decided on the publication earlier, but honestly it was never a priority.

4Vanilla_cabs4y

We were five hundred, but with swift support Grew to three thousand as we reached the port (Le Cid) It's been an exciting week, I've had lots of fun, thanks everyone who shared ideas, and thanks lsusr for swiftly and kindly answering all my questions. Now is time for the final act. * arxhy * DaemonicSigil * Emiya * frontier64 * Lanrian * Multicore * philh * simon * Taleuntum * Vanilla_cabs You will receive a personal message shortly. That is all.

2frontier644y

I pledge to join if there is at least 5 people total joined.

2arxhy4y

Pledging now to join if at least 8 do.

2DaemonicSigil4y

How do you determine who gets the first 3? Maybe lsusr will be kind enough to provide a symmetry-breaking bit in the "extra" package. (It would only be fair, given that bots playing themselves are automatically given max score.) If not, and you have to do things the hard way, do you compare source code alphabetically, 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 defection against outsiders depend on the round number. i.e. cooperate at first to maximize points, then after some number of rounds, when you're likely to be a larger proportion of the pool, switch to defecting to drive the remaining bots extinct more quickly.

5lsusr4y

I am neither kind nor fair-minded enough to provide a symmetry-breaking bit in the extra package.

3Vanilla_cabs4y

Great idea! I've updated the following heuristic using that. There is one thing that is different between the programs: the code that you will add to be executed in the later rounds (the payload). As I said, CloneBot will ignore it when judging whether its opponent is a clone. But if the opponent is a clone, it will use this heuristic to decide who goes first: * compare both payloads lexicographically * if the difference in length is the same parity as the round, the shortest plays 3 * otherwise, the longest plays 3 This is fair, deterministic, and needs 0 turn to communicate. There's no point in tweaking your payload in the hope of starting with 3 more often. The only problem are ties, which are unllikely, and adding your name as a comment solves it. Why also compare length? Because otherwise, the payloads of extreme length (very short or very long) would have very stable alternating priority, while the ones in the middle would be more subject to randomness. This way, it's the same randomness for everybody. That seems reasonable. I'm just worried that we might let greedy or even cooperating bots take too much lead. Ideally, as soon as the clique reaches criticals mass, it should starve its opponents. The 'as soon' depends on what proportion of the pool we'll initially be.

[-]Taleuntum4y180

Explanation of my strategy and thought process in chronological order

After seeing Vanilla_Cabs's comment I lied to them about wanting to join the clique. I was undecided, but I figured seeing the code of the clique can be a great advantage if I can exploit some coding mistake and I can still decide to join later anyway if I want.

The first versions of CloneBot (the name of the program for our clique) did actually contain a mistake I could exploit (by defining the __new__() method of the class after the payload) and so this was my plan until Vanilla_Cabs fixed this mistake. After they fixed it, I didn't notice any way I can take advantage, so I joined the clique in spirit.

Initially my plan for my bot was a simulator which simulates between 100 and 1000 turns of the opponent against a few candidate bots (ZviBot, TiTforTat, return 3, return 2, etc..) and then depending on the round number either chooses the one with the maximum point for me or the one which gets more points than the opponent. There were unfortunately two problems with this plan:

Bots who can detect if they are in a simulation can get me into an infinite loop which would disqualify my program, so I had to research the

... (read more)

[-]Vanilla_cabs4y140

The first versions of CloneBot (the name of the program for our clique) did actually contain a mistake I could exploit (by defining the __new__() method of the class after the payload) and so this was my plan until Vanilla_Cabs fixed this mistake. After they fixed it, I didn't notice any way I can take advantage, so I joined the clique in spirit.

Little did you know that I was aware of this weakness from the beginning, and left it as a test to find whom I could trust to search for the weaknesses I didn't know. Of the 3 (I think) to whom I showed the code early, only Lanrian reported it.

I'm curious how believable my lies were, I felt them to be pretty weak, hopefully it's only because of my inside view.

I didn't play a simulator so I didn't care about the first.

About the second, I can tell you that another member alerted me that you seemed to have a hidden ally. They feared you had made an ally outside the clique, or just given the code to join the clique to a player know only to you. Which I thought was a possibility. Actually, I hoped for a few stowaways to boost our numbers.

2Taleuntum4y

Maybe it's a little cheap to say this after you've revealed it, but it did actually occur to me that you might have deliberately made this weakness. Had I known that in Python you can redefine methods, I might have reported it, but the exploit with __new__() seemed pretty obscure (even though I didn't know the other way and I did know this). The possibility of this being a test was also the reason I went with the "Oh I'm so busy, I didn't have time to review the code.." excuse. I'm also curious whether Larion calculated with you deliberately planting the mistake or they had in-game ethics. Also, before you posted the list of the members publicly, you were the center of the clique and could control the information the clique members got. I was really paranoid about this and I feel you could have used this somehow. Have you thought along these lines? About your second point, It's nice I could make someone believe that I had an ally outside the clique.

5Emiya4y

Oh, that was me I think. I had simply thought your comment meant you were preparing code with someone else. Whether he was inside the clique, outside it, or a non player helping you out I wasn't sure, but I still recommended caution. I did think it was weird that you'd let slip such information, but couldn't see any reason for making people think you had allies, so I just thought that the most likely explanation was that a non player was helping you. Still, being cautious wouldn't hurt. I have to say I didn't made the connection about simulation crashing software being outside the clique, likely because I wasn't playing a simulator so I didn't thought much about it. All in all... I think it's a lie that would work best on the people it wouldn't need to work on. If I had thought to change a plan I had going based on the information you provided, I would have wondered a bit more about why you did that, perhaps getting suspicious. But I still think it wouldn't really be obvious as a lie to anyone. On a side note, I really love this site. I can't really recall any other game I've been in getting this tangled.

3Vanilla_cabs4y

I didn't know about __new__(), I only knew about redifining methods, so based on what you knew, your reasoning was correct. I knew no one before starting the clique. Lanrian joined the same way as the others. If anything, Lanrian was suspicious because they insisted we put the random.seed() inside move() and make it pseudorandom so that simulators can accurately emulate our behaviour. The reason they gave was to better collaborate, and have the simulators play 2 against 3 instead of 3 against 3. I was mildly convinced and I still am suspicious of that move. They only late in the week reported the weakness, after you and philh passed on the chance to do so. But they did so soon after I showed them the code. The secrecy on the members was used to: * prevent members and potential members from worrying if there were too few current members. That was the purpose I had in mind when I made that choice. A few days before the end I still was not sure we'd be enough. I was also worried some members would drop if we were too little. So the 2 members who joined in the last 2 days really helped. * avoid any collusion between members that would not include me. And more generally receive any valuable information that members would like to share. So I used that advantage only in a defensive way. But I did receive an offer that did inform me on more offensive uses, and impacted my payload, which I will elaborate on if the sender allows it.

3Lukas Finnveden4y

I stand by my reasoning! As long as we don't yield to bullying, simulators are our friends, ensuring that the maximum payout is always payed out.

2Lukas Finnveden4y

I didn't think about reporting the bug as making a sub-optimal but ethical choice – I just wanted to be part of a clique that worked instead of a clique where people defected. My aversion to lying might have affected my intuitions about what the correct choice was, though, idk ¯\_(ツ)_/¯

4philh4y

Incidentally, you could also just redefine existing methods, 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

4Taleuntum4y

Good to know. I'm a C++ guy which has a "one definition rule" not only for the translation unit, but for the whole program, so I incorrectly assumed that python is the same even though the languages are obviously very different.

4philh4y

I believed both of these lies, though if I'd come to rely on them at all I might have questioned them. But I assumed your friend was in the clique.

1Taleuntum4y

Yes, I feared that some might think my friend is in the clique. However I couldn't just say that they are not in the clique, because that would have been too obvious. (like my other lie: "Yeah, I totally have another method for detecting being in a simulation even if the simulation runs in a separate process, but unfortunately I can't reveal it.") So I tried to imply it by speaking about him as if he is not in the conversation and him not commenting after I mentioned him. I hoped in case someone was planning to submit a simulator outside the clique they would try to sneakily inquire about whether my friend is in the clique or not and then I would have asked a random, not competing lesswronger to play the part of my friend.

3Lukas Finnveden4y

I believed all lies! And I might've submitted a simulator if you hadn't told the first, and would definitely have tried harder to simulator-proof my bot, so you did change my behaviour. Leaving the clique wouldn't have been worth it, though. Even knowing that you lied about the 2nd thing, I assign decent probability to someone crashing all the simulators outside the clique. (I think this is incorrect, though – if you can figure out that you're in a simulation, it's way better to claim that you'll be submitting 3 to scare the simulator into playing 2.)

[-]Zvi4y160

So, in case anyone's wondering what I did...

I cared enough to think and enter, but not to program.

I designed a simulator, but was told it wouldn't be coded for me, so that was out.

So instead, I wrote this:

Until symmetry breaks, if the round # is 1, is 3 or is even, play sequence 23322232323322233 and then repeat 22222223 until symmetry breaks. If round # is odd and 5 or more, the reverse, except repeating 22222223 at the end.

Once it breaks, alternate 2 and 3 for 4 turns.

Then, if the last turn added to 5, keep doing that until 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.

Otherwise, depending on round number:

Rounds 1-50: Keep alternating until turn t+10. After that, if last turn added to 5, alternate 2 and 3. Otherwise, check their average score per round after symmetry. If it's 2.5 or lower, play 2, otherwise play 3.

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

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

(We could improve by add... (read more)

5lsusr4y

Your entry is in. I implemented the If (their score > my score and round > 5) play 3. Else Play 2. algorithm. 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))

5Zack_M_Davis4y

Seeing people actually use Hy is making me nostalgic!

5lsusr4y

I love Hy and use it all the time for data science and other applications. Thank you for all your work on the project!

4gilch4y

Zack_M_Davis isn't the only one. I've also written Hissp now. I'm curious how they compare for data science work (and other applications). I've also seen evhub, the author of Coconut, here on LessWrong.

3Multicore4y

We'll see how many people submitted simulators braver than mine, but simulators being timid seems like a natural consequence of the rules allowing you to nuke your opponent if you find out that you're in a simulation, and a common enough perception that simulators might have enough of an advantage that they should be eliminated. Static analysis is not very useful if the opponent's code is at all obfuscated, which is likely is if your opponent is looking to nuke simulators. Does your static analysis catch the code getattr(__builtins__, ‘e’ + ‘x’ + ‘e’ + ‘c’)(base64.decode(God knows what)) ? Or however many dozens of other ways there are to do something like that? The tournament might look significantly different if the rules were slanted in the simulator's favor, maybe if you just had to avoid infinite simulation loops and keep runtime reasonable, and the worst the opponent was allowed to do if they found they were in a simulation was to play BullyBot in order to extort you or play randomly to make the simulation useless. The iterated prisoner's dilemma with shared source code tournament a few years ago had a lot of simulators, so I assume their rules were more friendly to simulators.

2philh4y

I do think it would be hard to obfuscate in a way that wasn't fairly easy to detect as obfuscation. Throw out anything that uses import, any variables with __ or a handful of builtin functions and you should be good. (There's only a smallish list of builtins, I couldn't confidently say which ones to blacklist right now but I do think someone could figure out a safe list without too much trouble.) In fact, I can't offhand think of any reason a simple bot would use strings except docstrings, maybe throw out anything with those, too. (Of course my "5% a CloneBot manages to act out" was wrong, so take that for what it's worth.) I know of two such - one (results - DMRB was mine) in Haskell where you could simulate but not see source, and an earlier one (results) in Scheme where you could see source. I think in the Haskell one it would have been hard to figure out you were being simulated. I'm not sure about the scheme one.

[-]gjm4y110

The first line says "Entries must be submitted on October 18, 2020, or earlier."

Then a bit later you say "I will run my own version of the game on October 16, 2020."

Will you be making your time-travel technology available to contestants' bots, and if so what is the API they should use?

[-]lsusr4y160

Good question! My time travel technology will not be available to contestants' bots. This is in accordance with Less Wrong's established norm of containing dangerous technology.

I have edited the original post in a futile attempt to cover-up this leak and have removed the relevant API call from the extra module.

[-]Ben Pace4y150

Thanks for obeying the norms. That we definitely have. Around time travel technology.

[-]jan betley4y80

Your TitForTatBot
* never sets self.previous
* even if it was set, it would stop cooperating when opponent played 0

Also I agree with Zvi's comment, why 2.5 for free? This way one should really concentrate on maxing out in the early stage, is it intended?

2lsusr4y

I fixed the self.previous mistake. I think I'll leave the other bug as it is. See this comment concerning 2.5.

[-]philh4y70

Will post a link to a github repo with my code later today (when I'm not meant to be working), but for now, here's my thought processes.

(Edit: my code is here. My entry is in incomprehensibot.)

General strategy:

I was undecided on joining the clique, but curious. I didn't want to be a sucker if someone (possibly the clique organizer) found a way to betray it. I sent out feelers, 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 decided to do so, though I may have had the idea in my head befo

... (read more)

2philh4y

I now think these were overconfident. I think it would be fairly easy to simulate incomprehensibot safely; but hard to simulate incomprehensibot in a way that would be both safe and generically useful. The difficulty with simulating is that you need to track your opponent's internal state. If you just call MyOpponentBot(round).move(myLastMove) you'll be simulating "what does my opponent do on the first turn of the game, if it gets told that my last move was...". If you do this against incomprehensibot, and myLastMove is not None, incomprehensibot will figure out what's up and try to crash you. So at the beginning, you initialize self.opponent = MyOpponentBot(round). And then every turn, you call self.opponent.move(myLastMove) to see what it's going to do next. I don't expect incomprehensibot to figure this out. But if your opponent has any random component to it, you want to do that a couple of times at least to see what's going to happen. But if you call that function multiple times, you're instead simulating "what does my opponent do if it sees me play myLastMove several times in a row". And so you need to reset state using deepcopy or multiprocessing or something, and incomprehensibot has ways to figure out if you've done that. (Or I suppose you can just initialize a fresh copy and loop over the game history running .move(), which would be safe.) But actually, the simple "initialize once and call .move() once per turn" isn't obviously terrible? Especially if you keep track of your predictions and stop paying attention to them once they deviate more than a certain amount (possibly zero) from reality. And Taleuntum's bot might catch that, I'm not sure, but I think Incomprehensibot wouldn't. I think at some point I decided basically no one would do that, and then at some other point I forgot that it was even a possibility? But I now think that was silly of me, and someone might well do that and last until the showdown round. Trying to put a number on that would

1Taleuntum4y

The links you posted do not work for me. (Nevermind) Wow, you are really confident in you winning. There are 10 players in the clique, so even if there are no players outside the clique (a dubious assumption) a priori 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 possible member is a good number imo. i would say 80%. I would say 70% for the (possibly accidental) betrayal. Without seeing your jailbreak.py I can't say how likely that others are able to simulate you. What does "act out" mean in this context?

3philh4y

Conditioned on "any CloneBot wins" I've given myself about 25%. 10% in that conditional would definitely be too low - I think I have above-baseline chances on all of "successfully submit a bot", "bot is a CloneBot" and "don't get disqualified". I think I expect at least three to fall to those hurdles, and five wouldn't surprise me. And of the rest, I still don't necessarily expect most of them to be very serious attempts. By "act out" I mean it's a bot that's recognized as a CloneBot by the others but doesn't act like one - most likely cooperating with non-clones, but not-cooperating with clones would also count, it would just be silly as far as I can tell. I also include such a bot as a CloneBot for the 75%.

2philh4y

Updated 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 experimentation, looks like we both get close to 2.5 points/turn, but I exploit you for approximately one point every few hundred turns, leaving me the eventual victor. :D I haven't looked closely to see where that comes from. Of course too much depends on what other bots are around.

1Vanilla_cabs4y

3philh4y

Well played!

2simon4y

I fell for I thought it would be harmless and that there was some chance (even though it would make more sense to read some codeword directly from the payload) that someone would be using it as a recognition signal to boost a chosen clique member's bot using a non clique member's bot. Is it really disqualifiable? I am not using foo for anything else other than setting it.

4philh4y

Putting data in global state is forbidden, yeah, even if you don't do anything with it. I was a bit surprised. Just to be clear, this would only be forbidden if you put it at the top level. If you put it in your class it would be fine. So class CloneBot(): ... def payload(self) : ... foo = 'bar' # allowed foo = 'bar' # forbidden

2lsusr4y

The parent comment comes from a private conversation between me and philh in which I conveyed erroneous information. The mistake is my fault—not philh's. A line such as foo = 'bar' is legal in some contexts. A line which uses the global namespace to preserve information between class instances is illegal.

2simon4y

Yeah, I put it in at top level.

4Taleuntum4y

Disqualifying players for things they obviously wouldn't do if they knew the rules of the game seems pretty cruel. I hope isusr just deletes that line for you.

7lsusr4y

simon will not be disqualified.

1simon4y

Thanks!

2lsusr4y

Setting constants into the global state of your own file is fine. What I care about is whether you're setting variables into the global state for the purpose of preserving information between bot instantiations or otherwise messing with the game engine. simon's bot clearly does neither.

2philh4y

I confess I'm a bit confused, I thought in our PM conversation I was fairly explicit that that's what I was asking about, and you were fairly explicit that it was forbidden? It's not a big deal - even if this was forbidden I'd think it would be totally fine not to disqualify simon, and I still don't actually expect it to have been useful for me.

6lsusr4y

In my private conversation with you (philh) I stated "Writing variables to the global namespace is forbidden." I then doubled down on the error by stating "Yes. All data must be saved in a class instance." I apologize for the error. What I should have written was that using the global namespace to get around information restrictions is illegal but that writing constants to your module's global namespace in a way that does not evade information restrictions is fine.

[-]Lukas Finnveden4y70

What timezome is the deadline in? Or to be maximally precise – can you give a final submission-hour in UTC?

3lsusr4y

See here.

[-]jacobjacob4y70

Great initiative, thanks for organizing!

[-]Dagon4y70

Fun! Note that the "automatic recognition of self" and "group, not individual fitness" rules are different from many such contests. I think it's likely that this allows super-simple bots to win, if the initial mix allows them to get past the first few iterations.

I'd predict three-bot is the most likely simple winner - it gets full value against itself (as does everyone), and gets some points for all opponents' probes and complex signaling (that includes bidding 0, 1, or 2). It NEVER gives an opponent more points than it gets. ... (read more)

1simon4y

I hope not too many other clique members submitted 3-bot (we will destroy each other then, assuming multicore hasn't already taken over by the showdown time).

1Rochambeau4y

Wouldn't three-bot only get a few points against tit-for-tat bots? I agree it can't do worse than its opponent (meaning it would at worst tie if it is one of the last two bots), but bots that can cooperate or even two-bot could be raking in a lot more points as long as the population of bots isn't dominated by three-bot. For example, in a given round if three-bot is versing 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 getting a comparatively large amount of points meaning they will dominate later rounds so I think two-bot is a better simple strategy than three-bot (granted it will not win).

1frontier644y

Auto-self-recognition is trivial when you have the ability to read opponent's source code. You can detect you're playing against a copy of yourself and your 'opponent' will do the same. Although in this case you will lose a small amount of points randomly deciding which bot will choose 3 and the other 2 assuming there is no deterministic way to differentiate the clones. ETA: I see that you posted your comment before Isusr said you could view opponent's source.

[-]Zvi4y60

A thought for next time, if you want to build a simulator, it could make sense to wait one round before simulating anything even slightly unsafe, and do something simpler in round 1. That way, if something weird might potentially disqualify you but will itself get disqualified, it dies before it can remove you from the pool.

[-]Zack_M_Davis4y50

I don't know whether it's a competitive entry (it would be a FoldBot in Zvi's taxonomy), but as a quick piece of software, I'm pretty proud of AbstractSpyTreeBot!

4Taleuntum4y

You should also check whether 'exec' is in the program code string, because someone could call getopponentsource with exec and caesar-encryption, otherwise you will be DQ'd if someone submits a program like that. (However, rebinding getopponentsource is probably more elegant than this type of static analysis.)

3Multicore4y

This seems to only simulate the opponent's first move, and then act as if the opponent will make that move every round. For the most part this is a good reference implementation though, and I expect I'll be borrowing from it in my submission.

[-]Multicore4y110

An interesting bot for simulators to grapple with is this:

class BullyBot:

def __init__(self, round=0):

self.opponentThreesPlayed = 0

def move(self, previous=None):

if self.opponentThreesPlayed > 3:

return previous

elif previous == 3:

self.opponentThreesPlayed+=1

if self.opponentThreesPlayed > 3:

return 2

return 3

Something that holds out just long enough to get a naive simulator to fold to it forever, but will probably end up cooperating with most others.

3lsusr4y

Competitive or not it is technically competing. Welcome to the game!

[-]philh4y40

To check, what timezone is the deadline in?

4lsusr4y

Pacific Time Zone.

[-]Zack_M_Davis4y40

This is the Nash bargaining game. Is there some specific reason to call it a "Prisoner's Dilemma variation", or is it just "everyone has heard of the Prisoner's Dilemma, and don't have a generic term for this kind of game-theory tournament"?

8lsusr4y

It's the latter.

[-]Emiya4y30

I'm a non programmer, if I submitted a bot that's too complicated or that is supposed to do something that isn't a possible move, would I be contacted and get a chance to change it, provided I submit it early enough?

Could you provide one or more examples of too complicated descriptions, just so I know for which level of complexity I should aim? I'm not clear on how you would consider a bot that has a decision three with different options and processes but no part that's hard to program, for example. (To avoid giving hints or good ideas, they can be filled with completely stupid instructions or be for bots that try to do some other stuff)

2lsusr4y

If you're worried whether something is too complicated then the best solution is to PM me with your most complicated dream bot and I'll tell you how much of it I'm willing to code. An example of something that is too complicated is Zach_M_Davis's AbstractSpyTreeBot which runs a simulation of its opponent. Another example of something too complicated is is a neural network trained on your opponent's past history. Such bots are perfectly legal if you code them yourself to reasonable speed constraints but I will not write one for you. A hard-coded decision tree with several unambiguously-specified simple options is well within reason if that is all there is to it and you write a good specification. For example, using regular expressions to analyze your opponent's source code if fine.

1Emiya4y

That sounds perfect, thank you. I'm sorry to ask for another detail, but I'm not 100% sure if simulator-bots such as AbstractSpyTreeBot are legal if you can program them yourself. Your reply seems to state so, but I didn't wanted to assume.

2lsusr4y

Simulator bots are legal for programmers to write provided they never crash, slow the game to a crawl, etc. Any bot (even a non-simulator) that does will be disqualified. I have not yet read the AbstractSpyTreeBot source code in detail nor run it myself. A cursory glance suggests it's within the rules.

[-]Andrew Jacob Sauer4y30

What are the rules about program runtime?

0lsusr4y

Vague. The only limitations are obvious stuff like hacking the game client to get around information restrictions, using so much compute you slow the game itself to a crawl, installing anything that takes me significant effort to set up and anything I consider a security risk. You may PM me for clarification on your specific situation. I can easily perform speed tests as I have already written the game client. If you are a programmer then you may request reasonable features such as reading your opponent's source code. Edit #1: In order to maximize resource use, you may provide an adjustable constant such as TREE_DEPTH. Edit #2: Any code that can always complete 10,000 move calls within 5 seconds is guaranteed to be "fast enough".

5Drako3654y

What do you mean by information restrictions? What exactly is restricted? If I were to use some side-channel to determine that I was being simulated by an opponent and forkbomb if so, would I be eliminated for hacking? Would they be eliminated for overusing compute? (after all, it wasn't my code per say that forkbombed, but their code simulating my code) Would I be eliminated for being a dick? (Which would be self-evident, at any rate) You say in another comment, "Simulator bots are legal for programmers to write provided they never crash, slow the game to a crawl, etc. Any bot (even a non-simulator) that does will be disqualified." I'm just concerned about the edge case where someone writes the troll code described above, and suddenly every person who submitted a simulator bot (i.e. Zak M. Davis) gets DQ'd. The rules as written suggest that such a bot (presuming it does not preserve information across rounds) would be perfectly legal and it's Zak's own fault for executing untrusted code, but that seems to effectively prohibit simulators as there's an infinite plurality of side-channels through which to do this. A few possible resolutions would be: 1. Whoever wrote the code that contains the instructions to forkbomb is at fault. Essentially, don't be a dick. 2. Any information not explicitly given is forbidden. Essentially, you don't know if you're being simulated, and you're not allowed to find out. 3. Untrusted code is untrusted code; simulate at your own risk. Essentially, if Zak executes my forkbomb, that's his problem. (Well, your problem as well to fix it, but his fault.) Resolution 2 seems the most reasonable to me, but if you choose it I humbly request a way to locally overwrite get_opponent_source so you simulate your opponent's response without risking infinite recursion. (Such an overwrite is probably standard python, but being ignorant of your implementation I'd be concerned about screwing something up and not being able to detect the mistake in t

2lsusr4y

Hacking the game engine is against the rules. If your opponent decides to simulate your code then hacking them from inside your opponents' simulation is allowed. Your code is allowed to peek at the game engine for the purposes of figuring out if it is being simulated by someone else's code. Peeking at the game engine for other reasons, like figuring out how many of each opponents remain or attempting to modify the game engine itself or attempting to modify your opponents' code from anywhere outside their own simulation of you is against the rules. Anything that could damage the game's execution environment is a security risk and grounds for disqualification. Forkbombing your opponent is really pushing things…but technically legal. I would prefer something more mundane like calling exit() or an infinite loop. Anything more damaging than a forkbomb constitutes a security risk and is not allowed under any circumstances. If you are going to write any malware-like then code (including forkbombs) then please draw my attention to it in some way what the intended behavior is so I can mitigate any unintended consequences to my own systems. Even better would be to PM me for explicit permission. Any code which gets disabled by malware will get disqualified from the tournament. I will then restart the tournament with the broken competitor(s) removed. The resolution is #3 "Untrusted code is untrusted code; simulate at your own risk." The function get_opponent_source returns source code as a string. You can trivially overwrite it in your local environment with the command get_opponent_source = my_custom_get_opponent_source. (This is standard Python.) If you execute your opponent's code in a simulation where get_opponent_source has been rebound[1] to a new function (and have not otherwise left alternate attack vectors open) I see no reason why this would would trigger infinite recursion. If you rebind the get_opponent_source function in your local environment in a reasonable

3Taleuntum4y

In what order do programs get disqualified? For example, if I submit a program with an infinite loop, every other program using simulation will also go into infinite loop when meeting with my program as detecting infinite loops generally isn't theoretically feasible. Is my program disqualified before the others? What is the general principle? EDIT: An unrelated question: Do round numbers start from 0 or 1? In the post you write "Unlike Zvi's original game, you do get to know what round it is. Rounds are indexed starting at 0.", but also: "Your class must have an __init__(self, round=1) [..]". Why not have the default initializer also use 0 if the round numbers start from zero?

3lsusr4y

First a run your program against one or more simple programs without any simulations. If your program hits an infinite loop there then you will be disqualified before you get to infect any other programs. In this way you can be disqualified before the others. If your program passes the simple tests then it will join the pool and against all other programs which have passed the initial test. All programs which fail to terminate at this stage will be removed simultaneously. Thank you for the bug report. I have corrected __init__(self, round=1) [..] to __init__(self, round=0) [..]

3philh4y

Hm. Can we get a "you can use at least this amount of time per move and not be disqualified"? Without wanting to say too much, I have a strategy in mind that would rely on knowing a certain runtime is safe. (Allowing for some amount of jankiness, so that if the limit was 5s I'd consider 4s safe.)

4lsusr4y

I will not disqualify anyone who can complete 100 move calls in 5 seconds (0.05 seconds per call on average) on my T450s. I will not disqualify anyone who can complete 100 move calls in 0.05 seconds on my T450s. Edit: Corrected time limit downward by 100×.

4philh4y

Thanks. I confess I'd been hoping for more like 100x that, but not really expecting it :p

5lsusr4y

My previous answer was a mistake. It is actually 100 move calls in 0.05 seconds. Sorry. The numbers are brutal. If a game goes for 50 rounds and 10 different bots each use 5[1] seconds per move and there are 550 moves per bot per pairing then it would take 4.36 years to run this tournament. 5secondsmove×550movesspawning×100spawningsbot×round×50roundstournament×10bots×1tournament31,536,000secondsyear=4.36years However, do note that the guarantee is "0.05 seconds per 100 moves" as opposed to "0.0005 seconds per move". If you only have to run expensive computations once then, depending on your algorithm, the right caching system might get you close to 100× performance. I can add caching functions to the extra package if that would help. The computer in question has 4 processors and runs Linux so multiprocessing can get you up to a 4× speedup. ---------------------------------------- 1. 500 seconds per move is 100× my original limit which equals 10,000× the corrected limit. ↩︎

4philh4y

Oh, geez. I figured it would be too long, but I didn't think about just how much too long. Yeah, with these constraints, even 5s per hundred moves I agree is unreasonable. Caching seems easy enough to implement independently, I think. No need for you to add it.

2Andrew Jacob Sauer4y

Is everybody's code going to be in Python?

3lsusr4y

The rules are that, from the game engine's perspective, everyone's code is going to be written in Python 3 or Hy. It is theoretically possible that someone's code might, say, include some code in a different language that is then executed from the Python runtime.

2philh4y

I don't know how likely it is to make a difference, but what version of python 3?

2lsusr4y

Python 3.6.9 or Hy 0.18.0.

[-]SarahSrinivasan4y20

If you face a copy of yourself you are automatically awarded the maximum 5 points per round

What's your rationale behind this? Isn't part of the point that you need to be able to survive even in an ecosystem consisting mainly of you?

2lsusr4y

See this answer.

[-]arxhy4y10

Are comments allowed?

[This comment is no longer endorsed by its author]Reply

3lsusr4y

Like in the code? # Comments are allowed in the code.

[-]Harmless4y10

~~Is the number of rounds per matchup going to be in the tens, or the thousands?~~

Edit: I just realised you specified in the post

2lsusr4y

The number of turns per round is at least 100 and no more than 1000. I have not yet determined the number of rounds. If practical, I will iterate until there is a stable equilibrium. Edit: I have edited the original post to reflect the latter statement about rounds.

[-][anonymous]4y00

[This comment is no longer endorsed by its author]Reply

4lsusr4y

As soon as I can. Hopefully by the end of this week.

Moderation Log

131Comments