The Darwin Game

Collusion seems possible here, with a player sacrificing itself for another's benefit.

When bot A (master) and bot B (slave) play each other, start with a few handshake turns that will let them recognize each other. Then have bot A play all 5's and bot B play all 0's.

Sample handshake: B starts 1,0. A plays 5 on its second turn if its opponent played 1 on its first turn.

Set each of them up to cooperate against itself.

When playing someone else, they should mainly be aiming for a generic "do good", but bot B should put more emphasis on its absolute score (e.g., it's okay to capitulate to "always 3" because it capitulates to bot A even harder). Bot A should put more emphasis on its relative score since it needs to win.

If you can find multiple students who are willing to throw the game for your benefit, get them all to submit the same bot B (or variations which do slightly different things against other bots).

Starting with a simpler problem, let's say that I want to build a bot that cooperates with itself as well as possible and also tries to distribute points as evenly as possible between copies of itself. This is the best that I've come up with:

Always play either 2 (low) or 3 (high).

On the first turn, play 2 with probability p and 3 with probability 1-p.

If we got 5 points last turn, then play what my opponent played last turn. (This makes mutual cooperation continue forever, while alternating high-low.)

If we got less than 5 points last turn, then play 2 with probability q and 3 with probability 1-q.

If we got went over 5 last turn, then play 2 with probability r and 3 with probability 1-r.

Let's call this fairbot(p,q,r).

If my calculations are correct, expected score in self-play is maximized with p=q=r=0.69 (to the nearest .01). On average this brings in a combined 2.24 total points less than the fair maximum (5 per turn) for the two bots, because it might take a few turns to coordinate on which copy plays 3 vs. 2. (The quickest coordination happens with p=q=r=0.5, but that would miss out on 3 points because half the coordination failures cost the whole pot; with more weight on 2 the coordination failure happens more often but usually only shrinks the pot by 1 point.)

Starting to think about how fairbot plays against other bots:

Fairbot never settles into a stable pattern against "always 3" or "always 2"; it continues to switch between 2 and 3 (and plays the same thing as its opponent more often than not). Presumably it would be better it stick with 3s against "always 2" and to either stick with 2s or stick with 3s against "always 3" (depending on whether I prioritize relative or absolute score).

If I knew that fairbot(0.69,0.69,0.69) was my opponent, I think I'd want start by playing 3s, and then settle into mutual alternating coordination once we got a pot of 5. I would do slightly better than this bot does against me or against itself. I could get a much larger relative score by playing always 3, but it would hurt my absolute score by a lot. Or possibly I could do something in between.

An obvious way to make fairbot(p,q,r) more aggressive / less exploitable is to reduce p, q, or especially r.

We can add other rules which cover situations that never arise in self-play, such as when the opponent plays something other than 2 or 3, or when 5-point mutual cooperation gets broken (a non-5 pot after the previous turn had a pot of 5).

This is one of the first series I read on Less Wrong and I enjoyed it very much. I found it a great introduction to this forum.

The mockingbird: Find whatever method the current leader(s) is/are using to enable self-cooperation, and find the way to mimic them with a small advantage. (e.g. if they use a string of 0,1,4,5s to self-identify, spam 4 until they identify as you, then identify how to get into the side of mutual cooperation that is sometimes up a point.

Tit-for-tat with correction: Start with a even distribution, then play what they played last round, except if the total last round was above five and they played higher, reduce the value you played by the amout that exceeded five last round; if the total last round was below five and they played lower, increase the value you play this round by the shortfall. (If the values played were the same, adjust by half the difference, randomly selecting between two values if a .5 change is indicated. (Loses at most 5 points to fivebot, loses about half a point per round to threebot, leaves some on the table with twobot, but self-cooperates on round two with 80% probability.

Featured this post for being the first in a exciting and finished sequence (I should figure out a better way of causing concluded sequences to be Featured, when I only realise how awesome they are by the end). The second post was super fun to read, and the splitting into three posts meant that I notice how much my models were surprised by the third and final post - the outcome.

For these reasons, and also in the hope that people will build on the darwin game's setup, I've Featured it.

Promoted to the frontpage: I have some guesses on where this is going, but I am not confident abd definitely curious, and it seems like a great start to a good explanation.

Oh my gosh this sounds really fun.

Are programs allowed to have either a way to differentiate themselves from each other (like one program gets a 1 and the other gets a 0 for each game) or a source of randomness? Because otherwise it doesn't seem possible to cooperate with yourself.

It would be so cool if someone organized a game of this here or something...

I've read about about experiment like this while learning game theory. Simple Tit-for-Tat stratetgy (play what your opponent played last turn) won 3 tournaments straight. It auto-enables cooperation, (almost) whatever is your opp's strategy and if they want to exploit you - well, they can't.

You may need to think how to initialize to cooperate with yourself.

Copying over my thought process from your main blog:

Start with a short identifying sequence of 0s,1s,4s, and 5s. Seeing any 2 or 3 drops into oppositional mode immediately. Have the last two characters of this sequence only convey one bit of identification each; {0,5} vs. {1,4}. Determine which of them to use randomly, to establish who will be the low side and who the high side. This gives you a 75% handshake chance and 75% polarity-match chance, vs. 75/50 for finding them separately, at a cost of about 1 point in expectation.

In adversarial cases, start out with literal tit-for-tat; play the last number the opponent played. Come up with a short list of possible default strategies; always-2, always-3, always-N, 0/5-alternating, 2/3-alternating, 1/4-alternating. Probably a couple others. If the output doesn’t look quite like tit-for-tat, and the discrepancy with one of these other simple strategies is smaller, play the FDT-best-response strategy. For alternating strategies it’s the same alternation but in reverse, for always-N for N2 it’s to play always-3. This will involve several special cases, but they only need to handle common strategies so it’s limited.

Actually, skip the handshake code. This will get optimality against itself without that by starting out with random 2/3 for ~4 rounds and then proceeding from there.

Updates from reading other thoughts; use a 2-probability of 0.69 rather than 0.5 for the initial random run, for better performance as per Unnamed. This would also help against dumb no-forgiveness or minimal-forgiveness bots.

Really, really interesting. I'm going to do some formal analysis later. Some brainstorming first:

1. I want my bot to have memory. My bot needs to track the opponent bot's previous moves in a given round.
2. My bot would have hypotheses on the kind of bot it is playing. It would particularly need to have the following types of hypothesis {fixed probability distribution over all numbers, a reactionary program (the current move of the program depends on my bots previous moves).
3. I want my bot to cooperate against reactionary bots that adopt tit for tat with forgiveness. Of the reactionary bot does not forgive, my bot may be unable to cooperate. Especially if the reactionary bot tries to exploit or punish my bot based on my bot's initial moves.
4. I want my bot to quickly identify itself as soon as possible. This may involve my bot playing suboptimally in the first few moves, but should also make it easier to identify reactionary bots.
5. I want my bot to cooperate against itself.
6. I want my bot to exploit submissive $(P(x \in [0,2] > 0.5)$ (where $x$ is the number the opponent bot writes) bots. The degree of exploitation (how often it exploits) depends on my bot's hypothesis of how submissive it's opponent is.
7. I want my bot to punish offensive $(P(x \in [3,5] > 0.5)$ (where $x$ is the number the opponent bot writes) bots. The degree of punishment (how often it punishes) depends on my bot's hypothesis of how offensive it's opponent is.
8. I want my bot to be Bayesian. My bot would use Bayesian inference to update it's hypotheses on its opponent.
9. I would specify a utility function that specifies the appropriate trade off my bot should make between gaining points, and figuring out the kind of opponent it is facing. (I already have a rough idea of how my bot would go about gaining information due to my project on optimising scientific research).
10. I expect that my bot becomes more optimal as n tends to infinity, where n is the number of turns in a given round. This is because my bot may waste the first few turns may be in order to gain information.
11. I expect that given the source code of any bot, it is possible to script a predator bot, such that the predator bot always performs at least as good as the prey bot. As such, I expect to not disclose certain parts of my bot's algorithm once I complete the design.

I'm thinking of having my bot randomly playing 5 or 0 in the first round, so it can quickly identify itself. If the opponent played something else, it adopts accordingly. If the opponent played 5 or 0, it adopts another sequence of rituals (I don't want to say it here so that a predator bot wouldn't be scripted for my bot) which should help confirm that it is playing against itself.