Deterministic programs would always output the same thing so you know beforehand whether they’ll cooperate or defect. For RNG-based programs you just bet on what’s most likely.
I welcome big guns blowing large holes in this construction :-)
Based on the fact that you retracted this, you probably already realized the problem, but I’ll say it anyway for anyone else who hasn’t noticed.
If two programs both use this strategy, they’ll go into an infinite loop where program A simulates program B simulating program A etc. Since it only checks to see how much time is left after it finishes the simulation, it won’t even manage to give up and defect. It will just run out of time.
Also, passed.time would imply that there’s a class called “passed” with a variable called “time”, which is silly. It should be passed_time or passedTime depending on how you do multi-word variables.
I didn’t look at the details too much. You can fix that problem just by having it calculate the scores for cooperate and defect, and go with the one with the higher score.
I’m not sure what you mean. Do you mean the scores given that you choose to cooperate and defect? There’s a lot of complexity hiding in ‘given that’, and we don’t understand a lot of it. This is definitely not a trivial fix to Lumifer’s program.
If two programs both use this strategy, they’ll go into an infinite loop where program A simulates program B simulating program A etc.
Not if you do it right. (Not sure if I should say any more. The contest is interesting but sharing too much in the comments risks turning it into a social engineering effort rather than a programming or mathematical effort.)
I’m not familiar with it either, but if nothing else, you can pass a counter that shows the number of iterations you’ve gone through and stop when it gets too high.
What do you plan on doing when you run out of stack space? You can’t just replace your code with a cooperate bot or a defect bot after a certain level, since they’ll defect if they think you’ll do the same thing either way, and you’ll defect if you think they’ll defect etc.
What you need is something along the lines of cooperating if their code is equivalent to yours, and defecting if it’s different. You have to do this in under ten seconds, and you have to get it to cooperate even if they have a slightly different idea of what’s equivalent.
Does that include tail-calls in mutual recursion? Even if you were going to return whatever your opponent’s code did, you probably couldn’t count on them doing the same.
Well, that was the beginning of a host of problems :-)
I don’t know about the thread (or exception handling) capabilities of Scheme in Racket, but it shouldn’t be too hard to make sure you don’t run out of time if some chunk of the code is stuck in a recursive loop. That’s not really the issue. The issue is actually the recursion itself and the consequent need to deal with opponents that eval your code and expect an answer.
As a side note, passed.time is perfectly valid variable name in some languages where it doesn’t imply a class.method structure.
Can you track total passed time, so that if your opponent simulates you with 9 seconds passed, you cooperate instead of simulating your opponent? They simulate you simulating them… until you say “I’m running out of time, it must be the case that we’re in a recursive simulation, so It’s probably true that I should cooperate!” The latest simulation of your opponent says “He cooperated, so I should!” the next to last simulation of your program says the same thing, and so forth.
Until your original program says “My simulation of my opponent says he will cooperate, but I know for sure that I started on the first cycle of the evaluation, so I’m not a simulation. I defect.”
Your code doesn’t know if it’s being evaluated by the opponent or it’s running “for real”. If it knew, the program would be remarkably easy: if (simulated) { say “I cooperate!” } else { defect }.
It’s not hard to recognize that you’re stuck in a recursive trap and need to get out of there after nine seconds, but you still don’t know what to output.
If I know early enough the ten-second time limit exactly how long into the ten seconds I am, I can be sure enough that I’m the original.
Another possibility would be to include a random chance on the order of .1% that I will set a global flag that will follow down levels of simulation, and then simulate my opponent simulating me. If I get the flag, I have high probability that my opponent is simulating me on himself; I don’t want to set that flag with high probability, because I want my opponents’ (me cooperatebot) and (me defectbot) evaluations to return correctly.
But now I’m focusing on this particular implementation of the competition, not trying to provide useful information to the question that the competition is about.
Proposed meta-rule: Programs should not make attempts to determine if they are being scored or not in order to change behavior; attempts to identify and break out of recursive loops are encouraged.
Hm. Five minutes of thought suggest to me that the following pseudocode would be optimal:
Deterministic programs would always output the same thing so you know beforehand whether they’ll cooperate or defect. For RNG-based programs you just bet on what’s most likely.
I welcome big guns blowing large holes in this construction :-)
P.S. How do I indent in preformatted code?
Based on the fact that you retracted this, you probably already realized the problem, but I’ll say it anyway for anyone else who hasn’t noticed.
If two programs both use this strategy, they’ll go into an infinite loop where program A simulates program B simulating program A etc. Since it only checks to see how much time is left after it finishes the simulation, it won’t even manage to give up and defect. It will just run out of time.
Also, passed.time would imply that there’s a class called “passed” with a variable called “time”, which is silly. It should be passed_time or passedTime depending on how you do multi-word variables.
Another problem is that you cooperate agains CooperateBot.
I didn’t look at the details too much. You can fix that problem just by having it calculate the scores for cooperate and defect, and go with the one with the higher score.
I’m not sure what you mean. Do you mean the scores given that you choose to cooperate and defect? There’s a lot of complexity hiding in ‘given that’, and we don’t understand a lot of it. This is definitely not a trivial fix to Lumifer’s program.
I messed up. I didn’t realize that until after I posted, and I didn’t feel like going back to fix it.
Not if you do it right. (Not sure if I should say any more. The contest is interesting but sharing too much in the comments risks turning it into a social engineering effort rather than a programming or mathematical effort.)
I’m not that familiar with Scheme, but is there some way to see how much stack space you have left and stop before an overflow?
I’m not familiar with it either, but if nothing else, you can pass a counter that shows the number of iterations you’ve gone through and stop when it gets too high.
What do you plan on doing when you run out of stack space? You can’t just replace your code with a cooperate bot or a defect bot after a certain level, since they’ll defect if they think you’ll do the same thing either way, and you’ll defect if you think they’ll defect etc.
What you need is something along the lines of cooperating if their code is equivalent to yours, and defecting if it’s different. You have to do this in under ten seconds, and you have to get it to cooperate even if they have a slightly different idea of what’s equivalent.
Scheme requires tail-call optimisation, so if you use tail-recursion then you’ll never overflow.
Does that include tail-calls in mutual recursion? Even if you were going to return whatever your opponent’s code did, you probably couldn’t count on them doing the same.
Yes: all tail-calls are guarantied not to exhaust resources. The precise definition of what is tail is in the spec.
Well, that was the beginning of a host of problems :-)
I don’t know about the thread (or exception handling) capabilities of Scheme in Racket, but it shouldn’t be too hard to make sure you don’t run out of time if some chunk of the code is stuck in a recursive loop. That’s not really the issue. The issue is actually the recursion itself and the consequent need to deal with opponents that eval your code and expect an answer.
As a side note, passed.time is perfectly valid variable name in some languages where it doesn’t imply a class.method structure.
Can you track total passed time, so that if your opponent simulates you with 9 seconds passed, you cooperate instead of simulating your opponent? They simulate you simulating them… until you say “I’m running out of time, it must be the case that we’re in a recursive simulation, so It’s probably true that I should cooperate!” The latest simulation of your opponent says “He cooperated, so I should!” the next to last simulation of your program says the same thing, and so forth.
Until your original program says “My simulation of my opponent says he will cooperate, but I know for sure that I started on the first cycle of the evaluation, so I’m not a simulation. I defect.”
Your code doesn’t know if it’s being evaluated by the opponent or it’s running “for real”. If it knew, the program would be remarkably easy: if (simulated) { say “I cooperate!” } else { defect }.
It’s not hard to recognize that you’re stuck in a recursive trap and need to get out of there after nine seconds, but you still don’t know what to output.
If I know early enough the ten-second time limit exactly how long into the ten seconds I am, I can be sure enough that I’m the original.
Another possibility would be to include a random chance on the order of .1% that I will set a global flag that will follow down levels of simulation, and then simulate my opponent simulating me. If I get the flag, I have high probability that my opponent is simulating me on himself; I don’t want to set that flag with high probability, because I want my opponents’ (me cooperatebot) and (me defectbot) evaluations to return correctly.
But now I’m focusing on this particular implementation of the competition, not trying to provide useful information to the question that the competition is about.
Proposed meta-rule: Programs should not make attempts to determine if they are being scored or not in order to change behavior; attempts to identify and break out of recursive loops are encouraged.
The indentation thing is a bug.