Monsters are not replicable with same seed

[Oberlus]

Environment

• FreeOrion Version: v.0.4.8, v0.4.9, and probably all others.
• Operating System: Any

Description

The location of monsters and monster nests at game start are not replicable using the same seed and galaxy settings (including Experimentors enabled/disabled).

Expected Result

The starting location of monsters and nests should depend on galaxy seed and settings, so that games can be replicated without a save file.

Steps to reproduce

• Click on single player, set a fixed seed, start game.
• Build super-testers takeover and advance two turns.
• Check out locations of monsters and nests.
• Resign and repeat the process, to check out that this time monsters are not the same nor in the same places.

[geoffthemedio]

Do you have random reseeding enabled? Are there AI empires?

[Oberlus]

Do you have random reseeding enabled? Are there AI empires?

Random reseeding enabled, AI empires present.

Edit: for some reason, I thought random reseeding had to be enabled (checked) to get consistent results. After reading the tooltip, I see it should be disabled to get the same sequence of random numbers and more repeatable games.

However, I have started 3 games with random reseeding enabled and another 3 games with it disabled, and I got not once the monsters on the same positions (they are similar sometimes, but there is always some differences, not only names but type of monster).

[Vezzra]

AFAIK that has always been a problem. While we managed to get the same map on all platforms when using the same seed, monster placement can't be reproduced.

The problem is that, when it comes to monster and monster nest placement, not everything is done by the universe generation scripts, but also by FOCS effects on turn 1. As effect execution is multi-threaded, the order in which effects are executed isn't strictly determined, making it impossible to get the same results from the RNG on each run.

We've yet to find a solution to this problem.

[geoffthemedio]

You can set the server options to use just one thread for effect evaluation.

[Oberlus]

You can set the server options to use just one thread for effect evaluation.

Would that affect performance?

We've yet to find a solution to this problem.

Could the effects be executed by a fixed and know number of threads (independent of multithreaded capabilities of the local system) and be instantiated sequentially in a fixed and known order with each of them getting a (different) seed determined by the galaxy seed so that RNG used in each thread produces a known sequence of random numbers that does not depend on the order in which the threads are executed/mixed?

Sorry for the long sentence. It makes me think of David F. Wallace and Thomas Bernhard.

[geoffthemedio]

... each thread produces a known sequence of random numbers ...

Possibly, but the threads aren't operating on independent gamestates, so inconsistent and unpredictable timing issues could occur even if each thread generates random numbers independently from all the other threads' random number generation.

[peteroupc]

I am aware that the problem of thread schedulers and reproducible "randomness" has been tackled by using a different design from traditional PRNGs. Notably, so-called "splittable" PRNGs have been developed for use in "isolated parallel computations that may generate subtasks", such as event processing that could be done by individual threads:

• The JAX PRNG Design Notes explains how splittable PRNGs can be useful and describes one design of such a PRNG.
• Java's SplittableRandom class implements a splittable PRNG.
• Claessen and Pałka, "Splittable Pseudorandom Number Generators using Cryptographic Hashing", 2013, describes a splittable PRNG design that hashes a seed with a splitting path to produce pseudorandom numbers.

Essentially, splittable PRNGs give each task its own PRNG, rather than using global or thread-local PRNGs. In this case, a unique PRNG could be passed to Python's execute_turn_events method and that method could generate random numbers using that PRNG, rather than rely on a global or thread-local PRNG to do so. In the case of splittable PRNGs, a task does the following:

• Splits its PRNG into two states, and replaces its own PRNG with the left-hand state.
• Creates a new subtask (e.g., execute_turn_events), and passes the right-hand state to the subtask.

[Vezzra]

@Oberlus:

You can set the server options to use just one thread for effect evaluation.

Would that affect performance?

It should. If it didn't, having multithreaded effect evaluation would be pointless.