I have been planning to organise a new tournament, which would include: variable match length, possibility to simulate opponents (up to a fixed depth of recursion), scripting language for the strategies and an interpreter thereof and perhaps evolution with mutating strategies. However, relative lack of time together with akrasia stood in the way.
If there is a strong interest in this, I will try to precommit to do it in, say, three weaks. I have already some usable pieces of code.
You did an awesome job hosting the last tournament, and supplying competitors with a scripting language for their strategies is an excellent idea, so I hope you can do it. How would you implement evolution and variable match length though?
Also, I think if you could quantify “strong interest”, more people might be willing to sign up for this. I definitely have a strong interest in this.
Each agent is represented by a function; for concreteness let it be a real function of some relevant subset of previous turns. If the return value on a given turn is positive, the agent cooperates, else it defects. The function is represented as a tree; each node is a function with a fixed number of parameters (zero parameters = constant). Mutations are realised as cutting random branches and replacing them by constants. Sexual reproduction would take two functions and swap some branches. Population dynamics would be basically the same as in the last tournament.
Variable match length:
I would simply make up a number N which I will not tell anyone before the game starts. Then, each match would be preceded by generating a random real number x between 0 and 1, and the match length would be set to exp(xN) rounded up to integers, or something similar.
This sounds interesting, however the longer I think about it, the less I’m in support of it.
Regarding match length, I think the main issue here is not that it is variable, but that it is unknown to the agents. This will lead to a tournament of nice strategies first exterminating all non-nice strategies, then always cooperating with each other. This won’t change even if you can simulate your opponents, because the smartest way to play against TFT is still TFT (CooperateBot). If you take away the whole concept of parasites, I don’t see much of interest left.
I don’t see random mutations coupled with sexual reproduction work either; primarily because there is no compressed blueprint that can be altered, which means that entropy will increase. I feel that purposeful evolution of an intelligent design, like shokwave’s proposal of a parameter with a gaussian distribution that can be included in any way you like, is a more viable option.
I’m also not sure whether evolution and simulation go well together at all, because ultimately you want to play optimally against every other strategy, no matter how many and which other strategies are in the pool. If you can’t simulate your opponent, evolution is there to help you adapting to the changing pool of strategies, but if you can, it seems kind of pointless to me.
We shouldn’t duplicate work; I’m currently writing up a tournament simulator myself. I’m confident on variable match length, evolution, noisy responses, cheap talk rounds, and natural selection population growth tournaments. I am less confident on simulating opponents. For submitted strategies, I was prepared to accept code, pseudocode, and English descriptions, and then translate them into coffeescript myself. Probably I will also ask for some example games to test my translations (e.g. “My bot should cooperate 1-98 and defect 99, 100 against pure tit-for-tat”).
So your scripting language sounds particularly interesting, as well as your ideas for simulating opponents. I gather the two are tied together. PM me for details!
ETA: I offer to save you the cost of overcoming akrasia and lack of time.
I was prepared to accept code, pseudocode, and English descriptions, and then translate them into coffeescript myself.
I did it last time and it was pain in the arse. It’s fun to code one PD agent, not so much when they are forty and you must follow descriptions which you are not sure that you understand correctly.
I have written an interpreter which evaluates functions written in a lisp-like prefix notation, which was originally intended to be used in a program evolving automatic traders using genetic algorithms and real stock exchange data—the traders were represented as functions. Changing it to be applicable to PD simulations would be quite easy. Mutations are already coded too.
The idea of simulating opponents was mentioned in the discussion and relates to all sorts of LW decision theory idiosyncrasies. I think it’s worth doing, even if it were as primitive as having a function “simulate(X)” which would return the result of the opponent’s decision function where all instances of “simulate” are replaced by X (which is either C or D).
even if it were as primitive as having a function “simulate(X)”
I’m toying with each Bot having a “simulated” flag, and at the beginning of each game, create a real and a simulated version of each Bot, and let both Bots look at what the simulated Bots are doing. Haven’t thought properly about it yet, but the rest of the project is coming along much faster than I’d anticipated so I’ll have time to dig into this problem soon.
EDIT: I think I can do better. If bots have a single source code in some language L, and inferior interpreters I-weak, and the game has superior interpreter I-strong, then I-weak(L) can approximate I-strong(L). Especially neat is that I-weak’s inferiority can come from inability to recurse; it could bottom out and choose arbitrary values to feed back in—or it could come from instruction limitations; no more than 10,000 or so.
I have been planning to organise a new tournament, which would include: variable match length, possibility to simulate opponents (up to a fixed depth of recursion), scripting language for the strategies and an interpreter thereof and perhaps evolution with mutating strategies. However, relative lack of time together with akrasia stood in the way.
If there is a strong interest in this, I will try to precommit to do it in, say, three weaks. I have already some usable pieces of code.
You did an awesome job hosting the last tournament, and supplying competitors with a scripting language for their strategies is an excellent idea, so I hope you can do it. How would you implement evolution and variable match length though?
Also, I think if you could quantify “strong interest”, more people might be willing to sign up for this. I definitely have a strong interest in this.
Evolution:
Each agent is represented by a function; for concreteness let it be a real function of some relevant subset of previous turns. If the return value on a given turn is positive, the agent cooperates, else it defects. The function is represented as a tree; each node is a function with a fixed number of parameters (zero parameters = constant). Mutations are realised as cutting random branches and replacing them by constants. Sexual reproduction would take two functions and swap some branches. Population dynamics would be basically the same as in the last tournament.
Variable match length:
I would simply make up a number N which I will not tell anyone before the game starts. Then, each match would be preceded by generating a random real number x between 0 and 1, and the match length would be set to exp(xN) rounded up to integers, or something similar.
This sounds interesting, however the longer I think about it, the less I’m in support of it.
Regarding match length, I think the main issue here is not that it is variable, but that it is unknown to the agents. This will lead to a tournament of nice strategies first exterminating all non-nice strategies, then always cooperating with each other. This won’t change even if you can simulate your opponents, because the smartest way to play against TFT is still TFT (CooperateBot). If you take away the whole concept of parasites, I don’t see much of interest left.
I don’t see random mutations coupled with sexual reproduction work either; primarily because there is no compressed blueprint that can be altered, which means that entropy will increase. I feel that purposeful evolution of an intelligent design, like shokwave’s proposal of a parameter with a gaussian distribution that can be included in any way you like, is a more viable option.
I’m also not sure whether evolution and simulation go well together at all, because ultimately you want to play optimally against every other strategy, no matter how many and which other strategies are in the pool. If you can’t simulate your opponent, evolution is there to help you adapting to the changing pool of strategies, but if you can, it seems kind of pointless to me.
We shouldn’t duplicate work; I’m currently writing up a tournament simulator myself. I’m confident on variable match length, evolution, noisy responses, cheap talk rounds, and natural selection population growth tournaments. I am less confident on simulating opponents. For submitted strategies, I was prepared to accept code, pseudocode, and English descriptions, and then translate them into coffeescript myself. Probably I will also ask for some example games to test my translations (e.g. “My bot should cooperate 1-98 and defect 99, 100 against pure tit-for-tat”).
So your scripting language sounds particularly interesting, as well as your ideas for simulating opponents. I gather the two are tied together. PM me for details!
ETA: I offer to save you the cost of overcoming akrasia and lack of time.
I did it last time and it was pain in the arse. It’s fun to code one PD agent, not so much when they are forty and you must follow descriptions which you are not sure that you understand correctly.
I have written an interpreter which evaluates functions written in a lisp-like prefix notation, which was originally intended to be used in a program evolving automatic traders using genetic algorithms and real stock exchange data—the traders were represented as functions. Changing it to be applicable to PD simulations would be quite easy. Mutations are already coded too.
The idea of simulating opponents was mentioned in the discussion and relates to all sorts of LW decision theory idiosyncrasies. I think it’s worth doing, even if it were as primitive as having a function “simulate(X)” which would return the result of the opponent’s decision function where all instances of “simulate” are replaced by X (which is either C or D).
I’m toying with each Bot having a “simulated” flag, and at the beginning of each game, create a real and a simulated version of each Bot, and let both Bots look at what the simulated Bots are doing. Haven’t thought properly about it yet, but the rest of the project is coming along much faster than I’d anticipated so I’ll have time to dig into this problem soon.
EDIT: I think I can do better. If bots have a single source code in some language L, and inferior interpreters I-weak, and the game has superior interpreter I-strong, then I-weak(L) can approximate I-strong(L). Especially neat is that I-weak’s inferiority can come from inability to recurse; it could bottom out and choose arbitrary values to feed back in—or it could come from instruction limitations; no more than 10,000 or so.