Setting a seed is ineffective when parallelising

[drvinceknight]

So I just stumbled upon the following. If you run this code snippet twice:

import axelrod as axl
import numpy as np
axl.seed(1)
players = [s() for s in axl.demo_strategies]
tournament = axl.Tournament(
     players=players,
     turns=200,
     repetitions=5
)
results = tournament.play(processes=0)
list(map(np.mean, results.normalised_scores))

You will not get the same results.

axl.demo_strategies include axl.Random so this is due to the seed not being effective.

If you run the same code but in series multiple times:

import axelrod as axl
import numpy as np
axl.seed(1)
players = [s() for s in axl.demo_strategies]
tournament = axl.Tournament(
     players=players,
     turns=200,
     repetitions=5
)
results = tournament.play()
list(map(np.mean, results.normalised_scores))

then you do get the same results.

This is because the axl.seed(1) becomes redundant as jobs don't all necessarily finish in the same order and so are not necessarily run in the same order thus offsetting the random sequence.

Possible fix? (Not sure)

I can think of one idea towards a fix which involves sampling random integers in the "parent" tournament process and passing those to matches which would each set their own seed.

Modifying the match generator to do something like:

    def build_match_chunks(self):
        """
        A generator that returns player index pairs and match parameters for a
        round robin tournament.

        Yields
        -------
        tuples
            ((player1 index, player2 index), match object)
        """
        if self.edges is None:
            edges = complete_graph(self.players)
        else:
            edges = self.edges

        for index_pair in edges:
            match_params = self.build_single_match_params()
            yield (index_pair, match_params, self.repetitions, random.integer()). # Adding the random integer here

and modifying the Match to take a seed (and set the seed):

class Match(object):
    """The Match class conducts matches between two players."""

    def __init__(
        self,
        players,
        turns=None,
        prob_end=None,
        game=None,
        deterministic_cache=None,
        noise=0,
        match_attributes=None,
        reset=True,
        seed=seed,
    ):

Good points:

• [If this works] This would ensure that there are no differences in results from using multi processes or series.
• If a seed is set (like in the code above) then the random integers generated by the "parent" process would be the same;
• If a seed is not set then the "parent" process would pass "random" seeds to the matches so not reproducible.

Problem/question:

I think that the only way to do this efficiently is to sample the "parent" random numbers in the generator but if I'm not mistaken that will still be affected by the offset seedings (when a match sets a seed that will offset for the parent):

• Can we "copy" the random module so we can have two random sequences on the go? (One for the parent process and the other for the matches?). (We could potentially implement our our Mersenne twister but that sound idiotic)
• Perhaps using numpy.random.randint() could be used to sample all random seeds needed "efficiently". This has the downside to needing to know how many matches we want. In practice this isn't a problem, in theory we've tried to keep things so that the generators did not need this information...

Any other/better ideas?

Whatever the fix we should include something like the original code snippet as a test. If we can't fix it we should at least document this as a downside to parallelisation...

[marcharper]

Building on your last bullet -- we can exhaust the match generator so we know how many matches there will be, generate that many random seeds in the Tournament class (in bulk with numpy), zip those sequences together and pass the seeds into the Match class as you suggest. We can also save the seeds for each Match since the results for each match should be reproducible (and then the entire tournament so as well).

I think we have to do it this way to get per tournament repeatability. Since various processes may get pre-empted, we can't guaranteed that matches will get the same seeds otherwise, e.g. if we were to cache a random.Random in the Tournament class and issue seeds as needed.

[drvinceknight]

Yeah that sounds like a good idea @marcharper. I really like the idea of saving the seeds for each match. Do you think we might have some slight issues about memory from exhausting the match generators (for very large tournaments) ?

One final idea I had, and this is more a question, I don't know enough about pseudo random numbers know: do the seeds need to be random? Would the pseudo randomness take care of things if we just passed an incrementing sequence as seeds through the generator?

Would the following work:

def build_match_chunks(self):
        """
        A generator that returns player index pairs and match parameters for a
        round robin tournament.

        Yields
        -------
        tuples
            ((player1 index, player2 index), match object)
        """
        seed = 0
       
        for index_pair in edges:
            match_params = self.build_single_match_params()
            yield (index_pair, match_params, self.repetitions, seed). 
            seed += 1

[marcharper]

We couldn't start with zero every time, but otherwise from a randomness perspective I doubt incrementing the seeds like so would cause significant issues. Nevertheless it's probably better not to introduce structure into the random values themselves -- it's hard to say for sure that the structure of random generator won't have some hard to detect effect on the results.

We could run into memory issues for a very large tournament, but there are ways around that -- cache the match generators and seeds to disk for example and load them in batches as needed.

Looks like the generator has an upper bound formula (size). If that's always correct then we don't need to exhaust the generator -- rather we'll generate more random seeds than needed. It's quadratic however, which isn't great from a scaling perspective.

[drvinceknight]

We could run into memory issues for a very large tournament, but there are ways around that -- cache the match generators and seeds to disk for example and load them in batches as needed.

Looks like the generator has an upper bound formula (size). If that's always correct then we don't need to exhaust the generator -- rather we'll generate more random seeds than needed. It's quadratic however, which isn't great from a scaling perspective.

Right, so the idea EDIT:would could be to exhaust the generator if it doesn't have a known size?

[marcharper]

Yeah, I guess we could still run into memory issues just from the number of seeds as well, but anything less than 1000 players should be alright.

[drvinceknight]

Cool. I can have a go at this unless you'd like to?

[marcharper]

Sure. I thought about it a bit more and I think that caching to disk is probably the way to go since it avoids any issues with memory. But I'll try to remain open-minded to other solutions.

[drvinceknight]

Sounds like a sensible approach if memory becomes an issue 👍

Let me know if you'd like to chat anything over 👍