The tournament allows you to enter 3 bots, so we should be able to cheat if our bots can recognize each other. If so we have 1 bot, “ringer”, and 2 bots “shill0″ and “shill1” and follow this strategy:
ringer: if my opponent is shill0 or shill1, always defect. otherwise, play tit-for-tat.
shill0: if my opponent is ringer, always cooperate. otherwise play tit-for-tat.
To recognize each other, since we have access to the source code of both bots during the game, we need a hash function which is efficient in terms of characters used. One possibility would be to simply count the character codes. So we have
// one of the programs I grabbed at random as an example
let s = "r = h.length === 0 ? 1 : (h[h.length - 1].o === 1 ? h[h.length - 1].m : 1 - h[h.length - 1].m)"
// 6589
let id = [...s].reduce((a,c)=>a+c.charCodeAt(0),0)
This expression takes 41 chars, so we should be able to fit that in along with the required logic.
The obvious difficulty is that somebody could attempt to piggyback: craft a bot whose hash adds up to the same as the one our shills will auto-cooperate with. However, we should be able to solve this:
shill: if hash(c+s) = N, always cooperate. otherwise, play tit-for-tat
ringer: if hash(c+s) = M always defect. otherwise, play tit-for-tat
where c is the source code of the opponent and s is the source code of ourself.
We note that the rules of the challenge permit us to submit one of our bots by private message so that other players cannot see it. Therefore, we submit the source of ringer privately, and nobody should be able to piggyback.
I mean, yes, it’s not currently against the rules, but it obviously should be (or technical measures should be added to render it impossible, like adding random multiline comment blocks to programs).
Presumably the purpose of having 3 bots is to allow me to try 3 different strategies. But if my strategy takes less than about 160 characters to express, I have to use the ringer/shill version of the same strategy since otherwise I will always lose to a ringer/shill player using the same strategy but also shilling for his ringer. And the benefit of the ringer/shill strategy will be constant, since it shouldn’t be triggered by other players, just my bots. So it just means all the strategies are inflated by a constant amount. And it requires everyone to adopt the strategy, which is a waste of effort.
A much shorter strategy is always suboptimal in problems like these. The higher level your program can go, the better, and that requires more information.
It seems unlikely to me that this ringer/shill strategy will be particularly good compared to the other options, and you haven’t provided a compelling reason why I need to disallow it. What problems does it cause?
It seems unlikely to me that this ringer/shill strategy will be particularly good compared to the other options
It will absolutely be guaranteed to be better than equivalent strategies without ringer/shill. Remember that ringer/shill modifies an existing strategy like tit-for-tat. Ringer tit-for-tat will always beat tit-for-tat since it will score the same as tit-for-tat except when it goes up against shill tit-for-tat, where it will always get the best possible score.
This means that whatever the strongest ~160-character strategy is, the ringer/shill version will beat 2 more strategies than it. Intuitively, it seems unlikely that anyone will come up with a 240-character strategy which is that much stronger than the best ~160-character strategy. Partly this is because I suspect that the more sophisticated strategies that people will actually come up with will start running up against the execution time barrier and won’t have time to make positive use of all that complexity.
you haven’t provided a compelling reason why I need to disallow it.
You don’t need to disallow it, I’m just saying that it would be ideal if it could be disallowed. It could easily not be worth the trouble.
Ringer tit-for-tat will always beat tit-for-tat since it will score the same as tit-for-tat except when it goes up against shill tit-for-tat, where it will always get the best possible score.
It will do worse than tit-for-tat against any bot that cooperates with tit-for-tat and defects against ringer tit-for-tat.
But not much worse; against counterexamplebot, ringer tit-for-tat will defect (so almost full double-defect), and tit-for-tat will always cooperate, so for that match ringer tit-for-tat is down about 50 points (assuming 50 rounds so the score is 100-49). Ringer tit-for-tat then picks up 150 points for each match against the 2 ringers, and the score is now (300-349). And it’s only this close because the modified strategy is tit-for-tat rather than something more clever.
Also, this assumes that a bot even can defect specifically against ringer tit-for-tat. Insofar as ringer’s source is secret and the identification is a function of the source of both ringer and shill, this may not be possible. If I understood correctly we only have access to ourselves and our opponent during the match, so we can’t ask if some 3rd bot would always cooperate against our opponent, who would always defect against the 3rd.
The tournament allows you to enter 3 bots, so we should be able to cheat if our bots can recognize each other. If so we have 1 bot, “ringer”, and 2 bots “shill0″ and “shill1” and follow this strategy:
ringer: if my opponent is shill0 or shill1, always defect. otherwise, play tit-for-tat.
shill0: if my opponent is ringer, always cooperate. otherwise play tit-for-tat.
To recognize each other, since we have access to the source code of both bots during the game, we need a hash function which is efficient in terms of characters used. One possibility would be to simply count the character codes. So we have
This expression takes 41 chars, so we should be able to fit that in along with the required logic.
The obvious difficulty is that somebody could attempt to piggyback: craft a bot whose hash adds up to the same as the one our shills will auto-cooperate with. However, we should be able to solve this:
shill: if
hash(c+s) = N, always cooperate. otherwise, play tit-for-tatringer: if
hash(c+s) = Malways defect. otherwise, play tit-for-tatwhere c is the source code of the opponent and s is the source code of ourself.
We note that the rules of the challenge permit us to submit one of our bots by private message so that other players cannot see it. Therefore, we submit the source of ringer privately, and nobody should be able to piggyback.
That’s not cheating, that’s just “a strategy”. :)
I mean, yes, it’s not currently against the rules, but it obviously should be (or technical measures should be added to render it impossible, like adding random multiline comment blocks to programs).
Presumably the purpose of having 3 bots is to allow me to try 3 different strategies. But if my strategy takes less than about 160 characters to express, I have to use the ringer/shill version of the same strategy since otherwise I will always lose to a ringer/shill player using the same strategy but also shilling for his ringer. And the benefit of the ringer/shill strategy will be constant, since it shouldn’t be triggered by other players, just my bots. So it just means all the strategies are inflated by a constant amount. And it requires everyone to adopt the strategy, which is a waste of effort.
A much shorter strategy is always suboptimal in problems like these. The higher level your program can go, the better, and that requires more information.
It seems unlikely to me that this ringer/shill strategy will be particularly good compared to the other options, and you haven’t provided a compelling reason why I need to disallow it. What problems does it cause?
It will absolutely be guaranteed to be better than equivalent strategies without ringer/shill. Remember that ringer/shill modifies an existing strategy like tit-for-tat. Ringer tit-for-tat will always beat tit-for-tat since it will score the same as tit-for-tat except when it goes up against shill tit-for-tat, where it will always get the best possible score.
This means that whatever the strongest ~160-character strategy is, the ringer/shill version will beat 2 more strategies than it. Intuitively, it seems unlikely that anyone will come up with a 240-character strategy which is that much stronger than the best ~160-character strategy. Partly this is because I suspect that the more sophisticated strategies that people will actually come up with will start running up against the execution time barrier and won’t have time to make positive use of all that complexity.
You don’t need to disallow it, I’m just saying that it would be ideal if it could be disallowed. It could easily not be worth the trouble.
It will do worse than tit-for-tat against any bot that cooperates with tit-for-tat and defects against ringer tit-for-tat.
But not much worse; against counterexamplebot, ringer tit-for-tat will defect (so almost full double-defect), and tit-for-tat will always cooperate, so for that match ringer tit-for-tat is down about 50 points (assuming 50 rounds so the score is 100-49). Ringer tit-for-tat then picks up 150 points for each match against the 2 ringers, and the score is now (300-349). And it’s only this close because the modified strategy is tit-for-tat rather than something more clever.
Also, this assumes that a bot even can defect specifically against ringer tit-for-tat. Insofar as ringer’s source is secret and the identification is a function of the source of both ringer and shill, this may not be possible. If I understood correctly we only have access to ourselves and our opponent during the match, so we can’t ask if some 3rd bot would always cooperate against our opponent, who would always defect against the 3rd.
Well, I’d encourage you to submit this strategy and see how it does. :)