Mestroyer comments on Prisoner's Dilemma (with visible source code) Tournament - Less Wrong

47 Post author: AlexMennen 07 June 2013 08:30AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (232)

Comments (232)

You are viewing a single comment's thread. Show more comments above.

Comment author: Lumifer 05 June 2013 09:12:15PM *  0 points [-]

Hm. Five minutes of thought suggest to me that the following pseudocode would be optimal:

while(passed.time < 9.5seconds) {
outcome = eval(opponent.code(self.code))
if (outcome == "C") { c.count++ }
if (outcome == "D") { d.count++ }
}
if (c.count > d.count) {
output("C")
} else {
output("D")
}

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?

Comment author: DanielLC 05 June 2013 11:28:25PM 6 points [-]

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.

Comment author: Mestroyer 06 June 2013 12:04:12AM 1 point [-]

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?

Comment author: DanielLC 06 June 2013 12:30:48AM 2 points [-]

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.

Comment author: warbo 06 June 2013 04:02:38PM 0 points [-]

Scheme requires tail-call optimisation, so if you use tail-recursion then you'll never overflow.

Comment author: Mestroyer 06 June 2013 11:32:12PM 0 points [-]

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.

Comment author: wubbles 09 June 2013 12:45:38PM 0 points [-]

Yes: all tail-calls are guarantied not to exhaust resources. The precise definition of what is tail is in the spec.

Powered by Reddit Powered by Reddit