Evolutionary dynamics?

[gustavdelius]

Do you think that your library could be a good basis for simulating evolutionary dynamics for populations of prisoner's dilemma strategies? I have a final-year undergraduate student who is interested in this. It seems to me that an easy first step would be to build on moran.py and allow the possibility of mutation when a succesful strategy is cloned. However I am new to the package and can not yet judge whether it would be too slow to run the dynamics over evolutionary timescales. Perhaps there is a different package for evolutionary game theory that you would recommend instead?

[drvinceknight]

Hi @gustavdelius the library certainly aims to be a good basis for evolutionary dynamics so if there's something that it doesn't do that your student would find useful we'd love to have that contribution (and or work to implement it ourselves).

Have you seen these two part of the documentation that are relevant:

1. Ecological variants: http://axelrod.readthedocs.io/en/latest/tutorials/further_topics/ecological_variant.html These are similar to some of the evolutionary conclusions made by Axelrod in his original book.
2. An explanation of the moran process currently implemented (which I think is perhaps what your student requires with the addition of mutation): http://axelrod.readthedocs.io/en/latest/tutorials/getting_started/moran.html

You might also be interested to read: http://mojones.net/evolving-strategies-for-an-iterated-prisoners-dilemma-tournament.html that's a blog post by a contributor who developed/trained a new strategy by using evolutionary algorithms.

[gustavdelius]

Hi Vincent, many thanks for the fast helpful reply. The essential ingredient for evolution that so far is missing in the Axelrod library is mutation. From your answer I learn that you would be quite happy for Axelrod to be extended to make it suitable for evolutionary experiments.

The link to the blog by @mojones was very useful. He writes: "The reason we're going to the trouble of defining our own functions for scoring rather than using the built-in tournament tools in the Axelrod library is for performance. When we come to the evolutionary algorithm we're going to want to run lots of very small tournaments, and in testing I found the overhead of creating tournament manager objects for each one to be too great." This gives some ideas about what additions might be necessary to the Axelrod library.

[drvinceknight]

From your answer I learn that you would be quite happy for Axelrod to be extended to make it suitable for evolutionary experiments.

If there's something that can be added to the library that makes them easier we would indeed be delighted!

This gives some ideas about what additions might be necessary to the Axelrod library.

Fantastic. We look forward to it :)

Some thoughts:

One thing (I believe) that needs to be considered is that there are many options/variations for these mutations. Choosing the underlying structure (that the mutation would affect), for example:

• Zero determinant;
• Markov strategies;
• LookerUp (like @mojones's work);
• Finite state machines;
• etc.

To my knowledge there exists, in the literature many evolutionary approaches for each of those (different papers implementing different mutation/crossover processes). Whether or not a generic mutation framework could be designed is an interesting thought.

By the way, those 4 strategy structures are all implemented (so I hope will at least be of use to you and your student).

I am not sure if you use gitter but if you ever want some quicker communication then one of us can usually be found here: https://gitter.im/Axelrod-Python/Axelrod

[marcharper]

I think that @gustavdelius wants a Moran process with mutation, which is described in the literature. It would not be difficult to add this variant to the library, and in fact it was on my "get to it eventually list".

[drvinceknight]

Fantastic. My apologies for misunderstanding :) (Out of curiosity, is the mutation to another of the strategies in the population?) Perhaps this is something that @gustavdelius and his student could contribute to the library :)

[gustavdelius]

Hi Marc, a Moran process with mutation was indeed what I had in mind as the simplest way to introduce mutation. However, mainly due to the comment by @mojones on his blog, I suspect that the Axelrod library might need other changes in order to run evolutionary simulations fast enough, because those simulations have to now run for evolutionary timescales, not just population dynamics timescales.

Vincent is right to ask what new strategies a given strategy might mutate to. What I had in mind is that the description of how and at what rate a strategy can mutate is part of the specification of the strategy. One might even allow strategies to mutate their mutation strategy. It would be fascinating to study the evolution of evolution, wouldn't it? But I think this is going a bit too far off on a tangent for the Axelrod library.

Hi Vincent, after our interesting discussion on gitter this afternoon, I think my student will instead work on the idea of the continuous tournament I described there. But it would be nice to see others develop Axelrod to include mutation, so I am glad it is already on Marc's "get to eventually list", and maybe there will be other students of mine in the future.

[marcharper]

In the literature one often sets up a mutation matrix that determines how strategies mutate into each other. Of course it would not be difficult to add a variant of the Moran process that performs mutation in the same way to the library. However mutation could easily be done within a specific strategy by overriding the .clone() member function appropriately, and the rate of mutation itself could also change.

I don't think there is any issue with the time scaling or computational time unless you are after large populations, based on my experience running such simulations in Python and C++, with and without the Axelrod library. For example, some of the libraries I've written calculate stationary distributions for fairly large populations with mutation (over 1000 for two-types, over 500 for three-types) and the computations are not prohibitively long. Granted having non-deterministic players from the Axelrod library may increase the computation time, but it's another order of magnitude rather than and exponential increase. A small cluster of machines should suffice.

Perhaps if you could explain what the specific concern is more specifically then I can provide more appropriate guidance.

In case you haven't seen this before, the evolution of the rate of mutation has been studied in the literature by Michael Lynch and others. See also e.g. this paper and this earlier paper from 2006.

[drvinceknight]

Ah! A mutation matrix! That would be a great addition to the library.

I think the concern was due to a comment by Martin, but he was using tournaments (which do have an overhead) and not the Moran process you implemented from scratch.

On Sun, 9 Oct 2016, 20:55 Marc Harper, notifications@github.com wrote:

In the literature one often sets up a mutation matrix that determines how strategies mutate into each other. Of course it would not be difficult to add a variant of the Moran process that performs mutation in the same way to the library. However mutation could easily be done within a specific strategy by overriding the .clone() member function appropriately, and the rate of mutation itself could also change.

I don't think there is any issue with the time scaling or computational time unless you are after large populations, based on my experience running such simulations in Python and C++, with and without the Axelrod library. For example, some of the libraries https://github.com/marcharper/stationary I've written calculate stationary distributions for fairly large populations with mutation (over 1000 for two-types, over 500 for three-types) and the computations are not prohibitively long. Granted having non-deterministic players from the Axelrod library may increase the computation time, but it's another order of magnitude rather than and exponential increase. A small cluster of machines should suffice.

Perhaps if you could explain what the specific concern is more specifically then I can provide more appropriate guidance.

In case you haven't seen this before, the evolution of the rate of mutation has been studied in the literature https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2910838/ by Michael Lynch and others. See also e.g. this paper http://gbe.oxfordjournals.org/content/early/2011/08/04/gbe.evr066 and this earlier paper http://www.genetics.org/content/172/1/611 from 2006.

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/Axelrod-Python/Axelrod/issues/734#issuecomment-252508532, or mute the thread https://github.com/notifications/unsubscribe-auth/ACCGWvQpO0JJ-YRMlONuHDeZo47l6eEPks5qyUa8gaJpZM4KRsKR .

[marcharper]

Update: we now have the Moran process with the standard mutation set up in the library.

[drvinceknight]

I'm going to close this issue, as I feel it has been addressed. Please reopen if I'm incorrect.