Trouble is, when your bot plays itself it gets stuck in a loop, runs out of time and gets 0. This will make it very unlikely to ever rise to dominance in an evolutionary tournament.
Depending on how much time is allowed the following might be a viable solution: with a 1% chance cooperate, otherwise run the other bot’s source code. If the bot plays itself, or for that matter any other bot that tries to run its source code, after 100 (on average) iterations it will return cooperate, and then working backwards will (usually) converge to the right thing.
Obviously, the value of 1% should be as small as possible; the average time used is proportional to the reciprocal of the probability.
This could be fixed with a trivial modification: first check if the opponent source code is identical to your own, and if it is then cooperate. Otherwise run the other bot’s source.
However, there’s another problem: If DuncanS’s strategy plays against a CooperateBot or a random bot, it will throw away a lot of points.
Quite so. I actually never intended to post this—I edited the post several times, and in the end thought I’d abandoned it. But never mind.
I thought of various trivial modifications to fix the problem that you iterate infinitely deep if you meet yourself. You could check for yourself—that works as long as nobody else enters an equivalent strategy—in which case you will do each other in.
I’m not so worried about the cooperateBot or random bot as these will in any case do so badly that they won’t tend to turn up in the population pool. But I could obviously do better against these by defecting all the way. In fact, any algorithm that neither runs me, or checks what I played previously ignores my behaviour, and should be defected against.
The most reliable fix to the recursion problem that I can think of is to implement a hard resource limit, whereby if you spend (say) 9500 of 10000 processing units on analysis, then you drop the analysis and implement a dumb strategy with whatever juice you have left. Probably wouldn’t take much more than a simple counter being incremented in a bottom-level loop somewhere, as long as you’re looking at your opponent’s source through a level of indirection rather than just jumping straight into it. Some analysis strategies might also converge on a solution rather than finding an exact one, although this would be easier and more reliable with behavioral than with source analysis.
However, trapdoors like this are exploitable: they give agents an incentive to nearly but not quite run out the clock before making a decision, in hopes that their opponents will give up and fall back on the simple and stupid. The game theory surrounding this seems to have PD-like characteristics in its own right, so it may just have pushed the relevant game-theoretical decisions up to the metagame.
There is actually a human algorithm in the cooperate/defect space—which is to distrust anyone who seems to spend a long time making a cooperate decision. Anyone who has a really quick, simple way of deciding to cooperate is OK—anyone who takes a long time is thinking about whether you will defect, or whether they should defect—and you should probably find someone else to trust. This is one of the good things about Tit for tat—it passes this test.
However, there’s another problem: If DuncanS’s strategy plays against a CooperateBot or a random bot, it will throw away a lot of points.
That is a problem, but fortunately we know that those competitors will be eliminated before the chameleon, whereupon it will begin to improve its performance.
If the DuncanBot detects a source code different from its own, it runs that source code. So a DuncanBot looks to any CliqueBot like a member of it’s clique.
That may well be right—a cliquebot may well decide I’m not in its clique, and defect. And I, running its source code, will decide that my counterparty IS in the clique, and cooperate. Not a good outcome.
Clearly I need to modify my algorithm so that I run the other bot’s code without bothering to analyse it—and have it play against not its actual opponent, but me, running it.
To add to this (probably silly) post—I was drawn to this problem for the reasons that Eliezer considers it the interesting case. In this form, it’s a variant on the halting problem / completeness problem. Each of these can’t be solved because some cases turn into an infinitely deep recursive nesting. Any purported algorithm to predict whether another algorithm will halt can’t solve the case where it’s analysing itself analysing itself analysing itself etc. Hence my rather tongue-in-cheek response.
And my response hits the same problem in a different form. When it meets itself, it gets into an infinite loop as each side tries to run the other. To solve it, at some level you need a ‘cooperate’ to be introduced in order to terminate the loop. And doing that breaks the symmetry of the situation.
A Turing machine simulated with finite resources is decidable by a Turing machine, so the halting problem isn’t a problem, though in this case the simulator also has finite resources, so infinite loops aren’t a problem.
Predicting what the opponent would do if you always return “cooperate” means predicting how the opponent would play against a CooperateBot, and acting this way means adopting opponent’s strategy against CooperateBots as your own when playing against the opponent, which is not a CooperateBot and knows you are not a CooperateBot. Sounds like a recipe for failure (or for becoming an almost-DefectBot, actually, if the opponent is smart enough and expects genuine CooperateBots).
3) sounds fun. I already have a strategy for this variant—just run the other bot’s source code without bothering to analyse it.
Trouble is, when your bot plays itself it gets stuck in a loop, runs out of time and gets 0. This will make it very unlikely to ever rise to dominance in an evolutionary tournament.
Depending on how much time is allowed the following might be a viable solution: with a 1% chance cooperate, otherwise run the other bot’s source code. If the bot plays itself, or for that matter any other bot that tries to run its source code, after 100 (on average) iterations it will return cooperate, and then working backwards will (usually) converge to the right thing.
Obviously, the value of 1% should be as small as possible; the average time used is proportional to the reciprocal of the probability.
This could be fixed with a trivial modification: first check if the opponent source code is identical to your own, and if it is then cooperate. Otherwise run the other bot’s source.
However, there’s another problem: If DuncanS’s strategy plays against a CooperateBot or a random bot, it will throw away a lot of points.
Quite so. I actually never intended to post this—I edited the post several times, and in the end thought I’d abandoned it. But never mind.
I thought of various trivial modifications to fix the problem that you iterate infinitely deep if you meet yourself. You could check for yourself—that works as long as nobody else enters an equivalent strategy—in which case you will do each other in.
I’m not so worried about the cooperateBot or random bot as these will in any case do so badly that they won’t tend to turn up in the population pool. But I could obviously do better against these by defecting all the way. In fact, any algorithm that neither runs me, or checks what I played previously ignores my behaviour, and should be defected against.
The most reliable fix to the recursion problem that I can think of is to implement a hard resource limit, whereby if you spend (say) 9500 of 10000 processing units on analysis, then you drop the analysis and implement a dumb strategy with whatever juice you have left. Probably wouldn’t take much more than a simple counter being incremented in a bottom-level loop somewhere, as long as you’re looking at your opponent’s source through a level of indirection rather than just jumping straight into it. Some analysis strategies might also converge on a solution rather than finding an exact one, although this would be easier and more reliable with behavioral than with source analysis.
However, trapdoors like this are exploitable: they give agents an incentive to nearly but not quite run out the clock before making a decision, in hopes that their opponents will give up and fall back on the simple and stupid. The game theory surrounding this seems to have PD-like characteristics in its own right, so it may just have pushed the relevant game-theoretical decisions up to the metagame.
There is actually a human algorithm in the cooperate/defect space—which is to distrust anyone who seems to spend a long time making a cooperate decision. Anyone who has a really quick, simple way of deciding to cooperate is OK—anyone who takes a long time is thinking about whether you will defect, or whether they should defect—and you should probably find someone else to trust. This is one of the good things about Tit for tat—it passes this test.
That is a problem, but fortunately we know that those competitors will be eliminated before the chameleon, whereupon it will begin to improve its performance.
This doesn’t solve the slightly different CliqueBots won’t cooperate with each other problem.
If the DuncanBot detects a source code different from its own, it runs that source code. So a DuncanBot looks to any CliqueBot like a member of it’s clique.
A piece of code that runs a piece of source code does not thereby become that piece of source code.
That may well be right—a cliquebot may well decide I’m not in its clique, and defect. And I, running its source code, will decide that my counterparty IS in the clique, and cooperate. Not a good outcome.
Clearly I need to modify my algorithm so that I run the other bot’s code without bothering to analyse it—and have it play against not its actual opponent, but me, running it.
I meant what happens when a DucanBot meats a DicanBot that does the same thing but has trivial cosmetic differences in its source code?
To add to this (probably silly) post—I was drawn to this problem for the reasons that Eliezer considers it the interesting case. In this form, it’s a variant on the halting problem / completeness problem. Each of these can’t be solved because some cases turn into an infinitely deep recursive nesting. Any purported algorithm to predict whether another algorithm will halt can’t solve the case where it’s analysing itself analysing itself analysing itself etc. Hence my rather tongue-in-cheek response.
And my response hits the same problem in a different form. When it meets itself, it gets into an infinite loop as each side tries to run the other. To solve it, at some level you need a ‘cooperate’ to be introduced in order to terminate the loop. And doing that breaks the symmetry of the situation.
A Turing machine simulated with finite resources is decidable by a Turing machine, so the halting problem isn’t a problem, though in this case the simulator also has finite resources, so infinite loops aren’t a problem.
Predicting what the opponent would do if you always return “cooperate” means predicting how the opponent would play against a CooperateBot, and acting this way means adopting opponent’s strategy against CooperateBots as your own when playing against the opponent, which is not a CooperateBot and knows you are not a CooperateBot. Sounds like a recipe for failure (or for becoming an almost-DefectBot, actually, if the opponent is smart enough and expects genuine CooperateBots).
I changed my comment to remove this vulnerability—didn’t realise it had already been seen.