portable PRNG seed/distributions

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Post Reply
Message
Author
dbenage-cx
Programmer
Posts: 389
Joined: Sun Feb 14, 2016 12:08 am

portable PRNG seed/distributions

#1 Post by dbenage-cx » Tue Dec 27, 2016 12:26 am

Recently noticed that boost::hash is not consistent across boost versions when resolving for the galaxy seed, at least on my system.
Sampling from the seed hash done in ServerApp, the result is different between 1.60 and 1.62
Though I doubt so, I am curious is if is portable (wrt OS) for the same boost version.

With the move to c++11, this could be changed to std::hash, which would at least reduce the case for boost version.
I do not see any guarantee of portable results from std::hash however, the implication is the opposite:
http://en.cppreference.com/w/cpp/utility/hash wrote:The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above.
If std::hash is not consistent across OSes, but boost::hash is (and the opposite case between boost versions), between the two I'd opt to keep boost::hash.

For the PRNG itself, std::mt19937 is "required" to produce the same results, but AFAIK none of the distributions like std::normal_distribution provide such requirement (same case for boost).
'Simply' providing a custom, portable value for seed translation might still provide different results between platforms without a custom distribution as well.

I'll open a PR for result requests from this branch, if it looks like std::hash may be desired.
(Previous results, so I don't lose them in such a case)
seed: aaaaBBBB = (std)2783040585 (boost 1_60)2892594671
seed: aaaaBBBB = (std)2783040585 (boost 1_62)1426502312

seed: aaaabbbb = (std)4214164133 (boost 1_60)3005869415
seed: aaaabbbb = (std)4214164133 (boost 1_62)2207442920

seed: 6uTwEu5q = (std)4078502888 (boost 1_60)4027358770
seed: 6uTwEu5q = (std)4078502888 (boost 1_62)707295000

Another option might be to only store the string value and push all the related PRNG calls to python, though I have not found as much discussion on portability there.
Any content posted should be considered licensed GNU GPL 2.0 and/or CC-BY-SA 3.0 as appropriate.

User avatar
Vezzra
Release Manager, Design
Posts: 4605
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: portable PRNG seed/distributions

#2 Post by Vezzra » Tue Dec 27, 2016 8:58 pm

That again... *sigh*. We had the issue of the same seed not producing the same galaxy on different platforms, but got that solved somehow - IIRC by doing all the random stuff in the Python scripts. Apparently the standard PRNG Python uses does produce the same results for the same seed across platforms.

AFAIK that relies on boost::hash to produce the same hash from the string seed on all platforms, and independent of the boost version. If there are now differences between boost versions, that's not good. As the primary concern here is to get consistent results during universe generation, all we need is a hash function that reliably produces the same hash from the seed string across platforms. If the hash functions provided by boost or the standard library fail to do so, how difficult would it be to implement our own hash function? It doesn't need to meet any sophisticated standards after all...

Morlic
AI Contributor
Posts: 238
Joined: Tue Feb 17, 2015 11:54 am

Re: portable PRNG seed/distributions

#3 Post by Morlic » Tue Dec 27, 2016 11:00 pm

If the hashing function makes trouble, why not get rid of the hashing function: Let's just use an integer seed directly.
If I provided any code, scripts or other content here, it's released under GPL 2.0 and CC-BY-SA 3.0

User avatar
MatGB
Creative Contributor
Posts: 3310
Joined: Fri Jun 28, 2013 11:45 pm

Re: portable PRNG seed/distributions

#4 Post by MatGB » Wed Dec 28, 2016 12:32 am

I too thought we'd closed it, but if it's Boost dependent that would explain some variation.

I'm in the early stages of a restarted game and while layout, species, etc are all identical placement of guard sentinels/ancient guardians/monsters aren't, there was a vacuum dragon causing havoc in the first game, that's gone, and two planets that had guardians now have maintenance ships, another has nothing, etc.

If it's going to be worked on again, getting it so it's properly identical would be an objective I'd hope.
Mat Bowles

Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

dbenage-cx
Programmer
Posts: 389
Joined: Sun Feb 14, 2016 12:08 am

Re: portable PRNG seed/distributions

#5 Post by dbenage-cx » Wed Dec 28, 2016 12:42 am

I've added a fairly simple hash function to that branch.
Not sure how I feel about reverting the string back to an integer wrt user interaction/display.

I suppose this means some python function/wrapper needs to be provided to replace RandSmallInt (and friends), at least where a portable value is desired?

I expect there is an additional issue for effects in content definitions, otherwise they would not show different behavior on the same system/setup.

User avatar
adrian_broher
Programmer
Posts: 1072
Joined: Fri Mar 01, 2013 9:52 am
Location: Germany

Re: portable PRNG seed/distributions

#6 Post by adrian_broher » Wed Dec 28, 2016 9:54 am

Recently noticed that boost::hash is not consistent across boost versions when resolving for the galaxy seed, at least on my system.
Sampling from the seed hash done in ServerApp, the result is different between 1.60 and 1.62
Though I doubt so, I am curious is if is portable (wrt OS) for the same boost version.
You're running a 64 bit OS, right?

https://github.com/boostorg/functional/ ... a00efdbeb5
Resident code gremlin
Attached patches are released under GPL 2.0 or later.
Git author: Marcel Metz

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12245
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: portable PRNG seed/distributions

#7 Post by Geoff the Medio » Wed Dec 28, 2016 10:43 am

dbenage-cx wrote:I expect there is an additional issue for effects in content definitions, otherwise they would not show different behavior on the same system/setup.
As noted elsewhere, multithreading affects the results of a/the stateful PRNG used for resolving randomness in effects evaluation. This applies directly, through explicitly multithreading of the effects code, and probably indirectly, due to AI clients requesting object ids from the server, with the results depending on the order the requests are received, and the numbering of objects affecting how they're stored in containers indexed by object id, which can in turn affect what is selected randomly from those containers or the order in which effects are evaluated.

User avatar
Vezzra
Release Manager, Design
Posts: 4605
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: portable PRNG seed/distributions

#8 Post by Vezzra » Wed Dec 28, 2016 11:33 am

dbenage-cx wrote:I suppose this means some python function/wrapper needs to be provided to replace RandSmallInt (and friends), at least where a portable value is desired?
Not really. Just checked the universe generation scripts, and they don't use the hash produced on the C++ side at all. The seed string is passed to Python as the player entered it, and there the hash value is determined by using the MD5 hash function provided by the Python standard library. So on the Python side we are already completely independent of hash functions provided by boost or the C standard lib and all the hassle that comes with them.

Which means the problem actually exists only on the C++ side of things, and for the reasons Geoff pointed out I don't see how we could achieve reproducable sequences of random values anyway.

Concerning the placement of guard monsters etc. the only solution I see is to take that out of the effectsgroups of the relevant specials and migrate it to the universe generation scripts. As well as everything else that actually is part of universe generation and therefore should produce the same results for the same seed across all platforms.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 12245
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: portable PRNG seed/distributions

#9 Post by Geoff the Medio » Wed Dec 28, 2016 11:42 am

Vezzra wrote:Which means the problem actually exists only on the C++ side of things, and for the reasons Geoff pointed out I don't see how we could achieve reproducable sequences of random values anyway.

Concerning the placement of guard monsters etc. the only solution I see is to take that out of the effectsgroups of the relevant specials and migrate it to the universe generation scripts. As well as everything else that actually is part of universe generation and therefore should produce the same results for the same seed across all platforms.
For universe generation purposes, it could probably be set up to use only a single thread while evaluating those start-of-game effects. There's no AI-client timing during that stage either.

User avatar
Vezzra
Release Manager, Design
Posts: 4605
Joined: Wed Nov 16, 2011 12:56 pm
Location: Sol III

Re: portable PRNG seed/distributions

#10 Post by Vezzra » Wed Dec 28, 2016 11:52 am

Geoff the Medio wrote:For universe generation purposes, it could probably be set up to use only a single thread while evaluating those start-of-game effects. There's no AI-client timing during that stage either.
If we manage to solve the issues with the hash function and PRNG on the C++ side as well, then yes, that could be possible, at least for effects processing on turn 1. But that feels a bit like a hack. IMO moving everything universe generation related into the universe generation scripts sounds like a reasonable approach anyway, so why not take that road?

Post Reply