All right procrastinators, let’s talk strategy. You want a bot that’s unexploitable. Ideally, it should be as easy as possible for the opponent to prove that you’ll do whatever they do. In a world of unexploitable bots, the bot that can achieve the most cooperation will win.
MimicBots fit all of these parameters. They make it clear that their opponent is choosing between (C, C) and (D, D). Against a MimicBot, (C, D) is not an option. MimicBots pass up some utility by cooperating with CooperateBot, but that’s fine in this competition. You aren’t playing against CooperateBot. You’re playing against humans’ bots, and I doubt that anyone is mad enough to submit a CooperateBot.
The biggest problem with a MimicBot is that it will time out when playing other MimicBots. The MimicBots will dive into an evaluation loop, where my bot evaluates yours on a quine of me, and you evaluate my quine on a quine of you, ad infinitum.
Your MimicBot has got to bottom out at some point if you don’t want to risk timing out. If you find yourself diving into an evaluation loop you’d better bottom out into Cooperation.
Note that bottoming out into cooperation is not the same thing as cooperating at the top level. If the 100th simulation of you cooperates, and the 100th simulation of them sees that as a weakness and defects, then the 99th level of you will defect and so will the 98th and so on up to the top level, where mutual defection occurs.
I’m not asking you to cooperate when the other bot looks like they’re going to time out. That’s suicide. Rather, I’m pointing out that you can’t just simulate me against you, because that loop will never end. You’ve got to simulate me against a version of you that is one step closer to cooperation. This is true no matter what strategy you choose. But let’s consider the simple case: a MimicBot that simulates you on a copy of itself that simulates you on a copy of itself that eventually bottoms out into a bot that simulates you on CooperateBot.
Such a bot is a Rank N MimicBot, where N is the simulation depth at which it puts forth a CooperateBot.
Any particular Rank N is exploitable. For example, JusticeBot is a Rank 1 MimicBot — it bottoms out immediately by simulating you against CooperateBot. You can exploit JusticeBot by cooperating with CooperateBot and nobody else.
Notice, however, the price of exploiting JusticeBot: in order to exploit JusticeBot, you’ve got to cooperate with CooperateBot (a Rank 0 MimicBot).
As another example, consider a Rank 10 MimicBot. It simulates the opponent against a Rank 9 MimicBot. You can exploit an Rank 10 MimicBot if and only if you’re willing to cooperate with a Rank 9 MimicBot.
In general, you can exploit a Rank N MimicBot by cooperating with a Rank (N-1) MimicBot.
The trick here is that the opponent doesn’t know which MimicBot they’ll be playing. They have to guess exactly right to exploit you. If they guess high, mutual cooperation is achieved (If you guess I’m a Rank 10 you’ll cooperate with a Rank 9). If they guess low, mutual defection is achieved. (If you defect against Rank 10, Rank 11 will not cooperate with you.) You can only be exploited if they guess your rank precisely.
Therefore, I advocate that we get a bunch of us together to play Rank N MimicBots. We all pick our own N, possibly randomized. Note that Rank N MimicBots will achieve mutual cooperation with any MimicBot of any rank (including CooperateBot, JusticeBot, and MimicBots who don’t bottom out). Anyone trying to exploit us will only be able to exploit a specific rank, at the price of cooperation with a lower rank and the risk of defection from higher ranks. So long as we have a wide spread of ranks, our MimicBot clique will be internally cooperative and unexploitable in aggregate.
On Tolerance
MimicBot cooperates with CooperateBot. That leaves utility lying on the table. This may irk you (if you expect anyone was dumb enough to play CooperateBot). More irksome is the fact that MimicBot cooperates with JusticeBot. There is at least one JusticeBot in play, and we should expect that many non-procrastinators have submitted bots who exploit that JusticeBot. It would be a shame for our Rank N MimicBots to miss a shot at cooperation with bots who special-case defection against JusticeBot.
Therefore I recommend submitting MimicBots of rank 3 or higher. This gives people a little leeway to exploit CooperateBot or JusticeBot as they please, and allows us a broader range of mutual cooperation with bots who have already been submitted.
On choosing N
I recommend choosing a highish N. Very low N is obviously a bad idea. Playing rank 0 (CooperateBot) is suicidal. Playing rank 1 (JusticeBot) exposes you to exploitation by everyone who’s decided to kick wubble’s JusticeBot. Beyond rank 1 all the Ranks are theoretically similar, but you’ve got to consider what other bots will do. It’s conceivable that some bots won’t believe they’re playing a MimicBot until they hit a deep enough recursion depth. It’s possible that some bots will (incorrectly) think that you’re exploitable if you return too quickly. Therefore I recommend a high N.
If you’re particularly paranoid, consider randomizing N. Humans are notoriously bad at picking random numbers, and the MimicBot clique could in theory be exploited by a bot who exploits the ranks that humans are more likely to pick. Setting your counter to (+ 3 (random 1000)) is a quick way to counter that.
You can also shake things up a bit by using non-standard counters. For example, you could write a Timed MimicBot which passes down the initial time (instead of a counter) to its quines and puts forth a CooperateBot after a certain amount of time has passed (instead of when the counter hits zero).
How do I write one of these?
You write one of these with a degrading quine. Each level should evaluate the opponent against a slightly weeker version of itself. You can do this easily by putting a counter in your bot. So long as the counter is positive, the quining function should return a quine with the counter decremented. Once the counter hits zero, the quining function should return a CooperateBot.
Sounds nice, but how do I write a ‘degrading quine’?
It’s actually pretty easy in scheme.
Define (quine (lambda (code) 'placeholder)) and (template 'placeholder). Write the rest of your logic, pretending that (quine template) generates a child quine.
Manually copy all of your code and paste it over the template placeholder. In the pasted code, find all of the “holes” (parts that can vary: the counter, the template, your cooperation predicate, etc.) and replace them with odd negative numbers.
Write the quine function to walk through the code. If it sees a negative integer, figure out which hole it is by checking (+ code 1). This allows you to replace the −3 hole without having any −3s anywhere else in the code and so on.
Copy the real quine function into the template’s quine function.
If you make any more code changes after this process, remember to mirror them in your template. It will end up having this form:
(letrec [(counter (+ 3 (random 100)))
(template '(letrec [(counter -1)
(template -3)
...
(quine (lambda (code)
(cond
; The -1 hole is for the counter.
((and (integer? code) (negative? code) (= 0 (+ 1 code)))
(- counter 1))
; The -3 hole is for the template.
((and (integer? code) (negative? code) (= -2 (+ 1 code)))
`',template)
...
In order to make your MimicBot bottom out, you’ll want to define a predicate that is similarly flexible. It should be along the lines of ((eval them) (quine template)) so long as the counter is positive and #t when the counter gets to zero. The body of the letrec can then be as simple as (if predicate 'C 'D).
You’ll want some extra code to spawn the simulation in a thread and kill it if it goes overtime and so on.
If we all write bots like this, we can form a very powerful group capable of a wide range of mutual cooperation and very difficult to exploit.
Join me. With our combined strength, we can end this destructive conflict and bring order to the galaxy.
The MimicBots will dive into an evaluation loop, where my bot evaluates yours on a quine of me, and you evaluate my quine on a quine of you, ad infinitum.
MimicBot, as I describedit, breaks out of a simulation probabilistically; it will almost surely not fall into an infinite depth of simulations. MimicBot cooperates with probability ε, and has an expected simulation depth of 1/ε when played against itself. As long as ε<.5, the best action against MimicBot is to cooperate, so the expected simulation depth can be as low as 2.
No, I did not mean this, but I left out an important word: I should have said MimicBot cooperates unconditionally with probability ε.
MimicBot will almost perfectly mirror the strategy of its opponent. Most of the time (probability 1-ε), MimicBot returns the result of a simulation of its opponent against MimicBot. If you’re fighting MimicBot, you should expect it to think and act almost exactly the way you think and act. If you decide to always cooperate with MimicBot, MimicBot will decide to cooperate with you. If you decide to always defect against MimicBot, MimicBot will (almost always) decide to defect against you. If you play a mixed strategy against MimicBot, MimicBot will play an almost identical mixed strategy against you.
The slight imperfection in the strategy mirror (cooperating unconditionally with probability ε) is necessary to avoid infinite recursion
Incorrect. His MimicBot cooperates with probability ε and mimics the opponent with probability 1-ε (which may result in cooperation or defection, depending upon the opponent.)
I’d still recommend you refrain from acting as Rank 0 or 1 (from cooperating immediately or from simulating the opponent on a MimicBot who cooperates), as it’s likely that there are bots in play that prey on CooperateBots and JusticeBots (as determined by checking if you cooperate DefectBot). Also, I imagine there will probably be a fair number of DefectBots on the field, your MimicBot is exploited by a fraction of them.
I strongly recommend writing a MimicBot that goes through two iterations before allowing itself to exit with a fixed probability. Given that tweak I agree completely that your MimicBot is quite powerful.
Depending upon the implementation of mimic_bot, this is a quiny approach. mimic_bot obviously can’t run the opponent on an exact quine of yourself, because then you won’t achieve mutual cooperation. (When one of the bots cooperates unconditionally, the other will see that it acts_like_cooperate_bot and defect.) So long as mimic_bot plays opponents against a pure MimicBot instead of a perfect quine, this should work quite well.
On an unrelated note, woah, how’d you get whitespace working?
Now that the contest is over, I will observe that contrary to your first claim...
MimicBots fit all of these parameters. They make it clear that their opponent is choosing between (C, C) and (D, D). Against a MimicBot, (C, D) is not an option.
...it’s actually rather nontrivial to prove that your “MimicBot” does the same thing as you, since it doesn’t run your program against itself, it runs your program against a different program. For example, PrudentBot defects against any of your MimicBots, since it can prove that “JusticeBot defects against me, since I defect against CooperateBot” therefore “JusticeBot+1 defects against me, since I defect against Justicebot”, etc etc. In that sense, your mimicbot is not really a mimicbot at all. You could call it “simply a higher-order justicebot”.
In contrast, with a mimicbot such as solipsist’s one can just replace an instance of opponent(me) with 'C and see that this massively increases the chances of his bot cooperating, comparing to replacing the same thing with 'D, hence you should cooperate.
Argh, this comment is irritating… even beyond the subtle mistakes (for example, “it’s essential that outsiders don’t figure out what rank of MimicBot you’re running”… if you use even a non-obfuscated simple counter, you’re pretty safe, because they’ll see it as n on their turn and n-1 on your turn, and their response to this number is the same in either case).
While I do somewhat like the fact that my MimicBot now is marginally less likely to be exploited by a predetermined-specific-n exploiter, it’s not worth how many of the key insights into the problem have now been given away for free! Now we’ll get a more homogenous, less interesting field.
If it turns out you really have some fiendishly clever way to exploit the entire MimicBot clique you just ensured, I’ll half-forgive you when you win the contest, but that does not seem likely.
There are some interesting insights left you haven’t given away, but I beg anyone else who thinks of them to keep them to their self until after the contest.
That’s a good point about obfuscation being unnecessary—I’ve updated my comment to address it. I was stuck on the fact that you can exploit any rank in advance, and had a vague feeling that you could turn this into a bot that can exploit ranks on the fly. This feeling didn’t hold up well under inspection. With regards to your other concerns:
You are encouraged to discuss strategies for achieving mutual cooperation in the comments thread.
- the judge
I considered holding back much of my own strategy, until I realized that there’s really no such thing as an optimal bot in this contest. For example, common sense says that you should exploit CooperateBot for free utility. However, if you expect to face more JusticeBots than CooperateBots then you should pass up that utility for the opportunity to exploit the JusticeBots.
This problem is a social engineering problem by construction. The game won’t go to the bot with the cleverest code, it will go to the bot that best guesses the composition of the playing field.
This problem is a social engineering problem by construction. The game won’t go to the bot with the cleverest code, it will go to the bot that best guesses the composition of the playing field.
True. I just think things are more interesting if you let that composition grow out of everyone’s isolated ideas instead of gardening it ahead of time. Bearing your judge quote in mind, I should have said something earlier.
All right procrastinators, let’s talk strategy. You want a bot that’s unexploitable. Ideally, it should be as easy as possible for the opponent to prove that you’ll do whatever they do. In a world of unexploitable bots, the bot that can achieve the most cooperation will win.
MimicBots fit all of these parameters. They make it clear that their opponent is choosing between (C, C) and (D, D). Against a MimicBot, (C, D) is not an option. MimicBots pass up some utility by cooperating with CooperateBot, but that’s fine in this competition. You aren’t playing against CooperateBot. You’re playing against humans’ bots, and I doubt that anyone is mad enough to submit a CooperateBot.
The biggest problem with a MimicBot is that it will time out when playing other MimicBots. The MimicBots will dive into an evaluation loop, where my bot evaluates yours on a quine of me, and you evaluate my quine on a quine of you, ad infinitum.
Your MimicBot has got to bottom out at some point if you don’t want to risk timing out. If you find yourself diving into an evaluation loop you’d better bottom out into Cooperation.
Note that bottoming out into cooperation is not the same thing as cooperating at the top level. If the 100th simulation of you cooperates, and the 100th simulation of them sees that as a weakness and defects, then the 99th level of you will defect and so will the 98th and so on up to the top level, where mutual defection occurs.
I’m not asking you to cooperate when the other bot looks like they’re going to time out. That’s suicide. Rather, I’m pointing out that you can’t just simulate me against you, because that loop will never end. You’ve got to simulate me against a version of you that is one step closer to cooperation. This is true no matter what strategy you choose. But let’s consider the simple case: a MimicBot that simulates you on a copy of itself that simulates you on a copy of itself that eventually bottoms out into a bot that simulates you on CooperateBot.
Such a bot is a Rank N MimicBot, where N is the simulation depth at which it puts forth a CooperateBot.
Any particular Rank N is exploitable. For example, JusticeBot is a Rank 1 MimicBot — it bottoms out immediately by simulating you against CooperateBot. You can exploit JusticeBot by cooperating with CooperateBot and nobody else.
Notice, however, the price of exploiting JusticeBot: in order to exploit JusticeBot, you’ve got to cooperate with CooperateBot (a Rank 0 MimicBot).
As another example, consider a Rank 10 MimicBot. It simulates the opponent against a Rank 9 MimicBot. You can exploit an Rank 10 MimicBot if and only if you’re willing to cooperate with a Rank 9 MimicBot.
In general, you can exploit a Rank N MimicBot by cooperating with a Rank (N-1) MimicBot.
The trick here is that the opponent doesn’t know which MimicBot they’ll be playing. They have to guess exactly right to exploit you. If they guess high, mutual cooperation is achieved (If you guess I’m a Rank 10 you’ll cooperate with a Rank 9). If they guess low, mutual defection is achieved. (If you defect against Rank 10, Rank 11 will not cooperate with you.) You can only be exploited if they guess your rank precisely.
Therefore, I advocate that we get a bunch of us together to play Rank N MimicBots. We all pick our own N, possibly randomized. Note that Rank N MimicBots will achieve mutual cooperation with any MimicBot of any rank (including CooperateBot, JusticeBot, and MimicBots who don’t bottom out). Anyone trying to exploit us will only be able to exploit a specific rank, at the price of cooperation with a lower rank and the risk of defection from higher ranks. So long as we have a wide spread of ranks, our MimicBot clique will be internally cooperative and unexploitable in aggregate.
On Tolerance
MimicBot cooperates with CooperateBot. That leaves utility lying on the table. This may irk you (if you expect anyone was dumb enough to play CooperateBot). More irksome is the fact that MimicBot cooperates with JusticeBot. There is at least one JusticeBot in play, and we should expect that many non-procrastinators have submitted bots who exploit that JusticeBot. It would be a shame for our Rank N MimicBots to miss a shot at cooperation with bots who special-case defection against JusticeBot.
Therefore I recommend submitting MimicBots of rank 3 or higher. This gives people a little leeway to exploit CooperateBot or JusticeBot as they please, and allows us a broader range of mutual cooperation with bots who have already been submitted.
On choosing N
I recommend choosing a highish N. Very low N is obviously a bad idea. Playing rank 0 (CooperateBot) is suicidal. Playing rank 1 (JusticeBot) exposes you to exploitation by everyone who’s decided to kick wubble’s JusticeBot. Beyond rank 1 all the Ranks are theoretically similar, but you’ve got to consider what other bots will do. It’s conceivable that some bots won’t believe they’re playing a MimicBot until they hit a deep enough recursion depth. It’s possible that some bots will (incorrectly) think that you’re exploitable if you return too quickly. Therefore I recommend a high N.
If you’re particularly paranoid, consider randomizing N. Humans are notoriously bad at picking random numbers, and the MimicBot clique could in theory be exploited by a bot who exploits the ranks that humans are more likely to pick. Setting your counter to
(+ 3 (random 1000))
is a quick way to counter that.You can also shake things up a bit by using non-standard counters. For example, you could write a Timed MimicBot which passes down the initial time (instead of a counter) to its quines and puts forth a CooperateBot after a certain amount of time has passed (instead of when the counter hits zero).
How do I write one of these?
You write one of these with a degrading quine. Each level should evaluate the opponent against a slightly weeker version of itself. You can do this easily by putting a counter in your bot. So long as the counter is positive, the quining function should return a quine with the counter decremented. Once the counter hits zero, the quining function should return a CooperateBot.
Sounds nice, but how do I write a ‘degrading quine’?
It’s actually pretty easy in scheme.
Define
(quine (lambda (code) 'placeholder))
and(template 'placeholder)
. Write the rest of your logic, pretending that(quine template)
generates a child quine.Manually copy all of your code and paste it over the template placeholder. In the pasted code, find all of the “holes” (parts that can vary: the counter, the template, your cooperation predicate, etc.) and replace them with odd negative numbers.
Write the quine function to walk through the code. If it sees a negative integer, figure out which hole it is by checking (+ code 1). This allows you to replace the −3 hole without having any −3s anywhere else in the code and so on.
Copy the real quine function into the template’s quine function.
If you make any more code changes after this process, remember to mirror them in your template. It will end up having this form:
In order to make your MimicBot bottom out, you’ll want to define a
predicate
that is similarly flexible. It should be along the lines of((eval them) (quine template))
so long as the counter is positive and#t
when the counter gets to zero. The body of the letrec can then be as simple as(if predicate 'C 'D)
.You’ll want some extra code to spawn the simulation in a thread and kill it if it goes overtime and so on.
If we all write bots like this, we can form a very powerful group capable of a wide range of mutual cooperation and very difficult to exploit.
Join me. With our combined strength, we can end this destructive conflict and bring order to the galaxy.
MimicBot, as I described it, breaks out of a simulation probabilistically; it will almost surely not fall into an infinite depth of simulations. MimicBot cooperates with probability ε, and has an expected simulation depth of 1/ε when played against itself. As long as ε<.5, the best action against MimicBot is to cooperate, so the expected simulation depth can be as low as 2.
You mean defects with probability ε. It cooperates with probability 1-ε.
No, I did not mean this, but I left out an important word: I should have said MimicBot cooperates unconditionally with probability ε.
MimicBot will almost perfectly mirror the strategy of its opponent. Most of the time (probability 1-ε), MimicBot returns the result of a simulation of its opponent against MimicBot. If you’re fighting MimicBot, you should expect it to think and act almost exactly the way you think and act. If you decide to always cooperate with MimicBot, MimicBot will decide to cooperate with you. If you decide to always defect against MimicBot, MimicBot will (almost always) decide to defect against you. If you play a mixed strategy against MimicBot, MimicBot will play an almost identical mixed strategy against you.
The slight imperfection in the strategy mirror (cooperating unconditionally with probability ε) is necessary to avoid infinite recursion
reads further
is enlightened
Incorrect. His MimicBot cooperates with probability ε and mimics the opponent with probability 1-ε (which may result in cooperation or defection, depending upon the opponent.)
Heh, only if random() returns a random number in [0, 1], which isn’t specified in the pseudocode.
I’d still recommend you refrain from acting as Rank 0 or 1 (from cooperating immediately or from simulating the opponent on a MimicBot who cooperates), as it’s likely that there are bots in play that prey on CooperateBots and JusticeBots (as determined by checking if you cooperate DefectBot). Also, I imagine there will probably be a fair number of DefectBots on the field, your MimicBot is exploited by a fraction of them.
I strongly recommend writing a MimicBot that goes through two iterations before allowing itself to exit with a fixed probability. Given that tweak I agree completely that your MimicBot is quite powerful.
You can deal with those special cases that way. I was going to use a flatter, less quiny approach.
Depending upon the implementation of
mimic_bot
, this is a quiny approach. mimic_bot obviously can’t run the opponent on an exact quine of yourself, because then you won’t achieve mutual cooperation. (When one of the bots cooperates unconditionally, the other will see that itacts_like_cooperate_bot
and defect.) So long asmimic_bot
plays opponents against a pure MimicBot instead of a perfect quine, this should work quite well.On an unrelated note, woah, how’d you get whitespace working?
Total kludge. Used exotic unicode whitespace characters#Spaces_in_Unicode), which are displayed unaltered in comments :-).
Now that the contest is over, I will observe that contrary to your first claim...
...it’s actually rather nontrivial to prove that your “MimicBot” does the same thing as you, since it doesn’t run your program against itself, it runs your program against a different program. For example, PrudentBot defects against any of your MimicBots, since it can prove that “JusticeBot defects against me, since I defect against CooperateBot” therefore “JusticeBot+1 defects against me, since I defect against Justicebot”, etc etc. In that sense, your mimicbot is not really a mimicbot at all. You could call it “simply a higher-order justicebot”.
In contrast, with a mimicbot such as solipsist’s one can just replace an instance of
opponent(me)
with'C
and see that this massively increases the chances of his bot cooperating, comparing to replacing the same thing with'D
, hence you should cooperate.There’s two types of mimicbots running around: fixed-rank, and random-reliant.
Which mimicbot are you analyzing?
Argh, this comment is irritating… even beyond the subtle mistakes (for example, “it’s essential that outsiders don’t figure out what rank of MimicBot you’re running”… if you use even a non-obfuscated simple counter, you’re pretty safe, because they’ll see it as n on their turn and n-1 on your turn, and their response to this number is the same in either case).
While I do somewhat like the fact that my MimicBot now is marginally less likely to be exploited by a predetermined-specific-n exploiter, it’s not worth how many of the key insights into the problem have now been given away for free! Now we’ll get a more homogenous, less interesting field.
If it turns out you really have some fiendishly clever way to exploit the entire MimicBot clique you just ensured, I’ll half-forgive you when you win the contest, but that does not seem likely.
There are some interesting insights left you haven’t given away, but I beg anyone else who thinks of them to keep them to their self until after the contest.
That’s a good point about obfuscation being unnecessary—I’ve updated my comment to address it. I was stuck on the fact that you can exploit any rank in advance, and had a vague feeling that you could turn this into a bot that can exploit ranks on the fly. This feeling didn’t hold up well under inspection. With regards to your other concerns:
- the judge
I considered holding back much of my own strategy, until I realized that there’s really no such thing as an optimal bot in this contest. For example, common sense says that you should exploit CooperateBot for free utility. However, if you expect to face more JusticeBots than CooperateBots then you should pass up that utility for the opportunity to exploit the JusticeBots.
This problem is a social engineering problem by construction. The game won’t go to the bot with the cleverest code, it will go to the bot that best guesses the composition of the playing field.
True. I just think things are more interesting if you let that composition grow out of everyone’s isolated ideas instead of gardening it ahead of time. Bearing your judge quote in mind, I should have said something earlier.