Except that the analogy to rock-paper-scissors would be that I get to move logically first by deciding my conditional strategy “rock if you play scissors” etc., and simulating you simulating me without running into an apparently non-halting computation (that would otherwise have to be stopped by my performing counterfactual surgery on the part of you that simulates my own decision), then playing rock if I simulate you playing scissors.
At least I think that’s how the analogy would work.
I suspect that this kind of problems will run into computational complexity issues, not clever decision theory issues. Like with a certain variation on St. Petersburg paradox (see the last two paragraphs), where you need to count to the greatest finite number to which you can count, and then stop.
Suppose I know that’s your strategy, and decide to play the move equal to (the first googleplex digits of pi mod 3), and I can actually compute that but you can’t. What are you going to do?
If you can predict what I do, then your conditional strategy works, which just shows that move order is related to simulation ability.
In this zero-sum game, yes, it’s possible that whoever has the most computing power wins, if neither can access unpredictable random or private variables. But what if both sides have exactly equal computing power? We could define a Timeless Paper-Scissors-Rock Tournament this way—standard language, no random function, each program gets access to the other’s source code and exactly 100 million ticks, if you halt without outputting a move then you lose 2 points.
This game is pretty easy to solve, I think. A simple equilibrium is for each side to do something like iterate x = SHA-512(x), with a random starting value, using an optimal implementation of SHA-512, until time is just about to run out, then output x mod 3. SHA-512 is easy to optimize (in the sense of writing the absolutely fastest implementation), and It seems very unlikely that there could be shortcuts to computing (SHA-512)^n until n gets so big (around 2^256 unless SHA-512 is badly designed) that the function starts to cycle.
I think I’ve answered your specific question, but the answer doesn’t seem that interesting, and I’m not sure why you asked it.
Well, it’s probably not all that interesting from a purely theoretical perspective, but if the prize money was divided up among only the top fifth of players, you’d actually have to try to win, and that would be an interesting challenge for computer programmers.
Except that the analogy to rock-paper-scissors would be that I get to move logically first by deciding my conditional strategy “rock if you play scissors” etc., and simulating you simulating me without running into an apparently non-halting computation (that would otherwise have to be stopped by my performing counterfactual surgery on the part of you that simulates my own decision), then playing rock if I simulate you playing scissors.
At least I think that’s how the analogy would work.
I suspect that this kind of problems will run into computational complexity issues, not clever decision theory issues. Like with a certain variation on St. Petersburg paradox (see the last two paragraphs), where you need to count to the greatest finite number to which you can count, and then stop.
Suppose I know that’s your strategy, and decide to play the move equal to (the first googleplex digits of pi mod 3), and I can actually compute that but you can’t. What are you going to do?
If you can predict what I do, then your conditional strategy works, which just shows that move order is related to simulation ability.
In this zero-sum game, yes, it’s possible that whoever has the most computing power wins, if neither can access unpredictable random or private variables. But what if both sides have exactly equal computing power? We could define a Timeless Paper-Scissors-Rock Tournament this way—standard language, no random function, each program gets access to the other’s source code and exactly 100 million ticks, if you halt without outputting a move then you lose 2 points.
This game is pretty easy to solve, I think. A simple equilibrium is for each side to do something like iterate x = SHA-512(x), with a random starting value, using an optimal implementation of SHA-512, until time is just about to run out, then output x mod 3. SHA-512 is easy to optimize (in the sense of writing the absolutely fastest implementation), and It seems very unlikely that there could be shortcuts to computing (SHA-512)^n until n gets so big (around 2^256 unless SHA-512 is badly designed) that the function starts to cycle.
I think I’ve answered your specific question, but the answer doesn’t seem that interesting, and I’m not sure why you asked it.
Schneier et al here prove that being able to calculate H^n(x) quickly leads to a faster way of finding collisions in H. http://www.schneier.com/paper-low-entropy.html
Well, it’s probably not all that interesting from a purely theoretical perspective, but if the prize money was divided up among only the top fifth of players, you’d actually have to try to win, and that would be an interesting challenge for computer programmers.