How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Game 2 is a bit tricky. An answer to your described strategy would be to write a large number generator f(1),which produces some R, which does not depend on your opponents’ programs, create a virtual machine that runs your opponents’ programs for r steps, and, if they haven’t halted, swaps the final recursive entry on the call stack with some number (say, R, for simplicity), and iterates upwards to produce real numbers for their function values. Then you just return the max of all three values. This strategy wins against any naive strategy, wins if your opponents are stuck in infinite loops, and, if taken by all players symmetrically, reduces the game to who has a larger R—i.e. the game simplifies to GAME1, and there is still (probably) one survivor.
How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Well the brute force strategy is going to do a lot better, because it’s pretty easy to come up with a number bigger than the length of the longest program anyone has ever thought to write, and then plugging that into your brute force strategy automatically beats any specific program that anyone has ever thought to write. On the other hand, the meta-strategy isn’t actually computable (you need to be able to decide whether program produces large outputs, which requires a halting oracle or at least a way of coming up with large stopping times to test against). So it doesn’t really make sense to compare them.
How does your proposed solution for Game 1 stack up against the brute-force metastrategy?
Game 2 is a bit tricky. An answer to your described strategy would be to write a large number generator f(1),which produces some R, which does not depend on your opponents’ programs, create a virtual machine that runs your opponents’ programs for r steps, and, if they haven’t halted, swaps the final recursive entry on the call stack with some number (say, R, for simplicity), and iterates upwards to produce real numbers for their function values. Then you just return the max of all three values. This strategy wins against any naive strategy, wins if your opponents are stuck in infinite loops, and, if taken by all players symmetrically, reduces the game to who has a larger R—i.e. the game simplifies to GAME1, and there is still (probably) one survivor.
Well the brute force strategy is going to do a lot better, because it’s pretty easy to come up with a number bigger than the length of the longest program anyone has ever thought to write, and then plugging that into your brute force strategy automatically beats any specific program that anyone has ever thought to write. On the other hand, the meta-strategy isn’t actually computable (you need to be able to decide whether program produces large outputs, which requires a halting oracle or at least a way of coming up with large stopping times to test against). So it doesn’t really make sense to compare them.