In the reading I did last night, xoroshiro128** and CMWC seemed like possibly suitable candidates.
Yes, it seems xoshiro/xoroshiro are the successors to xorshift (and were invented after I wrote the Xorshift extension.) The creators recommend xoshiro128++ or xoshiro128** for 32 bit generators. Interestingly the ** variant only uses scrambling multipliers of 5 and 9! When I implemented xorshift32* I had to use a scrambler of 1597334677.
xorshift128+ is used by most JS engines, and Java includes xoroshiro128++ and xoshiro256++. So we’d be in good company if we used any of these variants (or even xoroshiro64**) (except the single + variants, which are only for generating floating point numbers). And they’d be faster and use less memory than MT.
Sadly, it’s not that simple. The first result is not necessarily fully predictable. It might be if calling for a random number between 1 and 4 on a particular platform (with the Windows IDE version of Glulxe it is always 3, but with Git it could be any of 1-4, and the fully predictable results come later in the sequence).
It would be necessary to hold a bank of sequences representing the particular possible starting random number streams determined empirically for each platform/terp combination and check for one of those.
But then what, if Inform finds it’s running on an affected platform? There’s currently not a simple way of implementing an in-house alternative RNG across all versions.
Kludgey though it is, the ‘prime the RNG by running it gazillions of times’ workaround I have posted remains at present the most practical sticking-plaster.
I don’t like it, and do hope someone can come up with a better one, because as @Dannii has pointed out, we ideally would have a good solution for legacy terps.
Yes, that’s the plan.
The I6 system function random is quite overloaded. Call it with a negative number to seed the VM’s RNG. Call it with one positive number to request a random number up to that, or with multiple values to return one of them. I hadn’t realised it was overloaded like that! I didn’t account for any of that in my Xorshift extension, but if we were to implement a RNG in I7’s kit code then it really should account for all of them.
@zarf Would it be at all feasible to split up it up into three veneer/system functions, so that you could replace only the seed and get a number parts (leaving the one-of-several as the default implementation, which would in turn use the random number function), and you could replace them separately? Because I don’t how we could reimplement random(1, 2, 3) - is there even a way for a Glulx function to know how many arguments were given to it? It would be great if random was treated like a macro that determined what it was doing then called the appropriate replaced function or native code.
Or alternatively, for I7 can we just depreciate the multi arg form? That would be much simpler.
Here is an evil method to replace the system random() function in Ver 10.
It relies on the fact that one of the few remaining ways to directly inject I6 code into the final I6 source (auto.inf) is with the Include (- ... -) when defining <a kind> | <an object> syntax.
The insertion parasitises the compiler’s random-kind class declaration header to inject a Replace random; statement, then declares a dummy-kind class declaration header to absorb the orphaned remainder of the compiler’s random-kind class declaration:
A random-kind is a kind of object.
Include (-;
Replace random;
Class dummy_kind
class K0_kind
-) when defining a random-kind.
which leads to this in the final I6:
Class K16_random_kind
class K0_kind
;
Replace random;
Class dummy_kind
class K0_kind
with plural bc_U167
with short_name bc_U168
with article bc_U169
with list_together bc_U170
;
This works because class declarations come early enough in the final I6 source that no code calling random() (which would otherwise compile the system random() function) has yet been compiled. The I6 compiler is therefore happy to accept the directive to replace the system random() function with our own.
EDIT Evil scientists among you will immediately notice that this provides a method to directly inject ANY undigested code into the final I6 source (auto.inf), bypassing the I6->Inter->I6 compilation process that spits out some otherwise valid I6 code, either because
i) it isn’t supported by the I6->Inter compiler, but is supported by the final I6->story compiler
ii) it has dependencies on things only created late in the I6->Inter->I6 compilation chain
4 Likes
That kind of inclusion doesn’t work when compiling to C, and will probably be removed in the future.
1 Like
I know, but for the present it enables those using Ver10 to compile stories that will work properly on legacy interpreters (with the dodgy PRNG) by implementing an in-house random() function, presenting an alternative to the kludgey ‘run the RNG a gazillion times on startup’ workaround.
Hopefully by the next release of Inform the issue will have a more formal resolution.
2 Likes
Ibid.
One woe doth tread upon another’s heels, so fast they follow:
Hamlet, Act 4, Scene 7
1 Like
If I remember right from the Technical Manual, when this happens it actually compiles a static array containing [1, 2, 3], then replaces the call with anonymous_array-->random(3). The random function never actually sees those arguments.
2 Likes
Nice one!
I have a lot of sympathy for that, so I want to be clear that the rest of this post is intended to be informational, without any implication that you “should” or “shouldn’t” do something.
Apologies for inviting the “contentious subject”, I really should have seen that coming when I brought up PCG. I don’t have a strong opinion between the variants of PCG, xoroshiro, and xoshiro that are currently recommended by the respective authors. I believe it’s fairly uncontroversial that all of them are at least pretty decent, and much better than most earlier RNGs, all academic feuds about what’s best (or fastest) aside. You might as well roll dice to pick one if you don’t want to bother comparing them. None of these algorithms are so flawless that an expert can’t teach them a party trick that highlights some weakness of some weird variant or usage pattern, but those don’t seem to affect the “take a recommended algorithm, seed it in the recommended way, and then just use it as a single stream of random numbers” use case.
All of Mac, Windows and Linux have some ways of getting high quality random numbers, but they also have heaps of legacy interfaces that one has to dodge because they’re not, in fact, any good by modern standards. Learning about all that baggage and how to avoid it isn’t fun, I’m hardly an expert about it myself, but it’s necessary if you actually want better randomness than what you can get out of the box from the algorithms discussed in this thread.
In particular, POSIX random() as currently used in Glulxe (seeded with time(NULL) and getting full 32 bits instead of just 31 via (random() << 16) ^ random()) fails the statistical test suite PractRand very consistently and very quickly, much more quickly than MT19937 for what it’s worth. At least that’s what I’m seeing on my machine with whatever implementation glibc uses (POSIX doesn’t specify much about it, and while I can find the implementation, there doesn’t seem to be any discussion of how good or bad it is) and a program I slapped together to feed PractRand:
hanna@eirin:~/testingRNG/PractRand-pre0.95$ cat glulxe_random.c
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdint.h>
void main() {
uint32_t seed = time(NULL);
fprintf(stderr, "time(NULL) seed = %u\n", seed);
srandom(seed);
while (1) {
uint32_t w = (random() << 16) ^ random();
fwrite(&w, sizeof(uint32_t), 1, stdout);
}
}
hanna@eirin:~/testingRNG/PractRand-pre0.95$ gcc -O2 glulxe_random.c -o glulxe_random && ./glulxe_random | ./RNG_test stdin
time(NULL) seed = 1695919320
RNG_test using PractRand version 0.95
RNG = RNG_stdin, seed = unknown
test set = core, folding = standard(unknown format)
rng=RNG_stdin, seed=unknown
length= 128 megabytes (2^27 bytes), time= 3.3 seconds
Test Name Raw Processed Evaluation
[Low1/32]BRank(12):512(1) R=+238.9 p~= 6.1e-73 FAIL !!!!
...and 198 test result(s) without anomalies
Actually, now that I think about it, I don’t actually know of any seedable RNG provided by Linux (either the OS proper or glibc) that’s considered to be high quality by today’s standards. There’s various sources of cryptographically secure randomness (/dev/urandom, arc4random, getrandom syscall, etc.) but those don’t accept seeds. They are very good for getting an an unpredictable seed for another RNG, avoiding the usual issues of seeding with time(NULL) or process IDs or the like, but on their own can’t be used for the Glulx RNG. And all options I’m aware of for seedable RNGs are C library functions with serious defects due to being stuck with algorithms chosen decades ago.
1 Like
Ok, good to know. I’ll take a look.
Yeah, I’m seeing that. Not thrilled about it.
That’s actually ok! The way I’ve got the code right now, the native RNG (which we want to be high-quality) will be used non-seeded. (That’s the call which is srandom(time(NULL)) right now, but that’s not optimal for several obvious reasons.)
The built-in RNG – xoshiro128 or whichever – is used with a seed. It’s a 32-bit seed to begin with, so there’s only so much we can do with it anyway.
I am really trying to limit the current task to “Update the Glulxe source code, and then maybe clone the changes to Git.” I know that leaves some interpreters behind.
(For what it’s worth, yes, a Glulx function can know how many arguments it has. See the PrintAnyToArray() library function, etc.)
1 Like
Any RNG used for Glulx @random has to support seeding, even if it starts out in an unpredictable state by default, because @setrandom with non-zero L1 has make the RNG behave deterministic (as function of the seed and of course only for that particular interpreter version). I7 exposes RNG seeding as a phrase for authors to use, and I believe the “Make random outcomes predictable when testing” setting in the apps relies on it.
Unless you’re talking about switching from one RNG implementation to the other dynamically during play, any time the game re-seeds the RNG? Yeah, I see now that’s what you’re doing in the branch you linked earlier.
Continuing the not-fun news, if you want to go this way then I don’t think any of the options mentioned are headache-free for this purpose:
/dev/urandomis apparently more widely supported than I thought (including on macOS), but it’s still a file and doing file I/O any time the game wants to flip a coin seems a bit silly. And since it’s a file accessed by a certain path, it may be unavailable or inaccessible (I believe that’s why Linux introducedgetrandomlater) or subject to other perplexing failure modes.getrandomis a Linux-ism and new enough that it’s apparently still good practice to check for its availability and fall back to something else if it’s missing.- On the other hand,
arc4randomis not available on Linux (allegedly this will change, but it doesn’t seem to have reached my machine yet).
And that’s just Linux, maybe Mac too. What about other platforms such as “git/glulxe compiled via emscripten running in the browser/Lectrote”? Now I’m tired enough of all those headaches that I want to take a step back to point out: we’re now talking about using cryptographically secure pseudorandom number generators (CSPRNG) for an IF interpreter. Why? I fully understand wanting high quality randomness, but CSPRNGs don’t offer better randomness than their non-cryptographic peers in any sense that’s meaningful for us here.
The objective of CSPRNGs is to resist attempts to influence or recover the internal state and thereby predict past or future outputs. Non-crypto RNGs are insecure under such threat models, but good ones are no worse than CSPRNGs under any other measure of “quality of randomness” or “unpredictability”. And of course, adversarial threat models are comically out of place here: a player trying to break the RNG can just poke the RAM of the interpreter running on their computer to set up an RNG seed of their choice! That’s probably easier than painstakingly figuring out the state of an insecure RNG from in-game observations, but in my opinion the latter is more fun to watch in a speedrun.
CSPRNGs being hopefully indistinguishable from “true randomness” is just a corollary of the security objective, and in fact the randomness can be somewhat compromised without lowering the security to the point where it’s considered broken. Another example is the observation that CSPRNGs based on a block cipher in counter mode (encrypt s, then s+1, then s+2, etc. for some starting point s) will never repeat any output block across its whole period because a block cipher never maps two different inputs to the same output. Intuitively, that’s not a property we’d like an unpredictable random number generator to have! It’s not a very practical issue because the block size is at least 128 bits, so you’d need to see at least 2^64 blocks (much more for larger block sizes) for the lack of repetition to start becoming suspicious and even then it wouldn’t help an attacker predict the next outputs. But it’s the exact sort of thing which, for any non-crypto RNG, would be taken as evidence that the algorithm is busted.
All of that is to say: there isn’t really a choice between dealing with these annoying platform differences vs. having worse randomness if you don’t. You can have your cake and eat it too with a simple, portable implementation of high quality randomness for both reproducible and unpredictable modes. That reduces the problem to getting a good “unpredictable” seed, which is much easier: fancy platform APIs can be used if desired and available, but not bothering and just throwing time(NULL) in there still picks a different high-quality stream of random numbers every second. (It just sucks for the “launched many times by a script” use case.)
1 Like
Oh, I agree. “High quality” is the goal here. David only brought in a crypto-secure Windows API because Windows has it right there.
1 Like
Ah, that’s what _vararg_count is for. Never used it for my own functions before.
It’s great to see such quick progress on updating Glulxe and Git!
However I think I think this is important enough that I7 should do at least something small to account for the older terps, but you can tune that discussion out if you want.
Someone asked before if it is only Windows terps that are affected? I’m pretty sure every Git terp is affected. I just looked at Git’s code for the first time, and saw that it doesn’t have any conditional code, it never tries to use a RNG from the OS/libc. It just has the same weak RNG that Glulxe used to have. I expect David is intending to fix this to use the same solution as Glulxe once that’s been decided.
2 Likes
For further testing: a new Windows build of Glulxe. This uses Windows’ RNG if no seed is set (or it is set to 0), and Zarf’s implementation of MT19937 otherwise.
glulxe_new_rng.zip (976.2 KB)
It seems to me there are 4 scenarios here:
Old story file with old terp → may not work properly, but there’s not much we can do but advise using new terps wherever possible
Old story file with new terp → this will require a better PRNG to be implemented within the new terp
New story file with old terp → this will require a new in-house PRNG to be implemented
New story file with new terp → unless the story has means of knowing whether it is running on a terp with a good PRNG, it will have to assume the worst and still default to an in-house PRNG
Conclusion, we need a new implementation within as many terps as possible for the sake of the existing back-catalogue of Glulx stories, but it may nevertheless be advantageous for all new Glulx stories to use an in-house PRNG to guard against being run on an old terp.
3 Likes
I can see four options for what Inform 7 could do:
- Implement some kind of xorshift-like and use it unconditionally. Good enough for lots of other languages!
- Determine (through a gestalt?) whether the VM’s built in
@randomopcode is good enough, and if it isn’t then implement an xorshift-like. - Do a minimal (perhaps <93) priming of the VM’s RNG, hoping it’s good enough for most casual random uses in Inform. Anyone with serious needs (for random combat perhaps) can implement an xorshift-like themselves.
- Do a maximal (<33K) priming of the VM’s RNG.
In this topic we’ve mostly been considering priming the VM’s RNG in order to increase the number of distinct sequences. But ignoring the question of how many distinct sequences there are, is Git’s current RNG actually good enough for the sequences it produces? Does it have a low-bit bias? If it’s not good enough then we really need to choose option 1 or 2.
If Inform 7 implements its own RNG, then how do we seed it? If Git’s current RNG returns a value closely derived from the timestamp if it’s not adequately primed, then maybe we just directly seed it with glk_current_time.
Anyone know the name of the algorithm implemented in Git/Glulxe? Zarf is about to replace the Glulxe RNG, but here’s a permalink. If we had the name I’m sure it wouldn’t be hard to find an analysis of it to see if it has a low-bit bias etc. It only does one actual subtraction each round… which seems very weak.