The best “A-players” and “B-players” now choose moves against their copies by flipping coins, so that half the time they get at least one cookie.
Waidaminute—those aren’t “A-players” or “B-players” any more, but variants. And if two “A-player variants” vary in a slightly different way, will they recognize each other as such? Doing so is not a trivial problem!
Anyway, my algorithm would be something like:
“Calculate a hash of my code, hashMe, and a hash of my opponent, hashYou. If (hashMe + hashYou) is odd, the player with the highest hash shall be the Chosen One, otherwise it’s the player with the lowest hash (if the hashes are identical, find some other unambiguous higher/lower criteria both players share, player IDs or something or lexicographic ordering of source code, if none exists, flip a coin). If I’m the Chosen One, play A, otherwise play B. Also, random string of comments (to ensure different instances of this algorithm have different hash functions).”
This should have an expected value 1.5 against predictors (it can be simulated safely without recursion problems), 0.5 against A-players, 1 against B-players and 0.75 against coin-flippers. And more importantly, it’s resistant to exploitation/blackmail, and gets the max utility of 1.5 against itself.
The only problem with this algorithm is that it’s not good at coordinating with similar algorithms that have a different “Chosen One” criteria (e.g. “look at the parity of the (hashMe+HashYou)th digit of pi”). That could be fixed, but is considerably more complicated.
Calculate a hash of my code, hashMe, and a hash of my opponent, hashYou. If (hashMe + hashYou) is odd, the player with the highest hash shall be the Chosen One, otherwise it’s the player with the lowest hash (if the hashes are identical, find some other unambiguous higher/lower criteria both players share, player IDs or something or lexicographic ordering of source code, if none exists, flip a coin).
This is way too complicated. Instead of ending with “flip a coin” why not just start with it?
If you don’t recognize your opponent as a copy of yourself because he’s written in C++ and not Java, or because he uses iteration and not recursion, then you’re acting sub-optimally (unless those things matter of course!).
In any cliquing strategy, you (the player) want to submit a bot that always defects against a bot that is not functionally equivalent to itself: this is crucial to guarantee the stability of the Nash equilibrium that you hope to reach.
You also want your bot to cooperate with any bot it can prove to be functionally equivalent to itself, and to always compute an answer in a finite time.
Due to Rice’s theorem , functional equivalence is a semidecidable property, therefore you need to use a stronger, decidable, equivalence relation that underestimates, but never overestimates, functional equivalence. Textual equality is the most obvious of such relations. You can invent many more weaker equivalence relations that still guarantee functional equivalence, but they would add complexity to your bot and presumbly make coordination with the other player more difficult, therefore it is not an obvious choice to use any of them.
Once you have chosen to use a cliquing strategy, you still have to choose between (infinitely) many cliques, therefore you face a “choosing sides” coordination game with the other player. This a non-trivial problem, but fortunately it is easier than the original game.
Waidaminute—those aren’t “A-players” or “B-players” any more, but variants. And if two “A-player variants” vary in a slightly different way, will they recognize each other as such? Doing so is not a trivial problem!
Anyway, my algorithm would be something like:
“Calculate a hash of my code, hashMe, and a hash of my opponent, hashYou. If (hashMe + hashYou) is odd, the player with the highest hash shall be the Chosen One, otherwise it’s the player with the lowest hash (if the hashes are identical, find some other unambiguous higher/lower criteria both players share, player IDs or something or lexicographic ordering of source code, if none exists, flip a coin). If I’m the Chosen One, play A, otherwise play B. Also, random string of comments (to ensure different instances of this algorithm have different hash functions).”
This should have an expected value 1.5 against predictors (it can be simulated safely without recursion problems), 0.5 against A-players, 1 against B-players and 0.75 against coin-flippers. And more importantly, it’s resistant to exploitation/blackmail, and gets the max utility of 1.5 against itself.
The only problem with this algorithm is that it’s not good at coordinating with similar algorithms that have a different “Chosen One” criteria (e.g. “look at the parity of the (hashMe+HashYou)th digit of pi”). That could be fixed, but is considerably more complicated.
This is way too complicated. Instead of ending with “flip a coin” why not just start with it?
Right, so the TDT way to do this would be to diagram the causal structure and only accept as “copies” programs with the same structure.
hashMe does seem to be a good way to access the Pareto optimum that V_V mentions.
Being strict in recognizing the other is a feature, not a bug. You want to obtain a stable Nash equilibrium.
If you don’t recognize your opponent as a copy of yourself because he’s written in C++ and not Java, or because he uses iteration and not recursion, then you’re acting sub-optimally (unless those things matter of course!).
Don’t conflate the player with the bot.
In any cliquing strategy, you (the player) want to submit a bot that always defects against a bot that is not functionally equivalent to itself: this is crucial to guarantee the stability of the Nash equilibrium that you hope to reach.
You also want your bot to cooperate with any bot it can prove to be functionally equivalent to itself, and to always compute an answer in a finite time. Due to Rice’s theorem , functional equivalence is a semidecidable property, therefore you need to use a stronger, decidable, equivalence relation that underestimates, but never overestimates, functional equivalence.
Textual equality is the most obvious of such relations. You can invent many more weaker equivalence relations that still guarantee functional equivalence, but they would add complexity to your bot and presumbly make coordination with the other player more difficult, therefore it is not an obvious choice to use any of them.
Once you have chosen to use a cliquing strategy, you still have to choose between (infinitely) many cliques, therefore you face a “choosing sides” coordination game with the other player. This a non-trivial problem, but fortunately it is easier than the original game.