Rocks'n'Diamonds 4.3.0.3 released!

R'n'D is always evolving. Check here to see if a new version is out.

Moderators: Flumminator, Zomis

Post Reply
User avatar
Holger
Site Admin
Posts: 4073
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Rocks'n'Diamonds 4.3.0.3 released!

Post by Holger »

Please download and use this patch release as soon as possible, as it fixes a major problem with generating unique player IDs for the high score server.

The resulting problems with assigning scores and player names on the high score server caused by this bug have already been fixed on the server itself, but to be able to rename your player in R’n’D and still have all your scores associated with your changed player name, you have to upgrade to this new R’n’D version which fixes the problem also on the client side.

Now available from the download page!
User avatar
Holger
Site Admin
Posts: 4073
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by Holger »

Some more technical details about this problem: It was a really severe bug of the pseudo-random number generator used for generating UUIDs for new players, which resulted in UUIDs not being unique (sic!). After I found out that there were several players on the high score server with the same UUID (in fact, new players with non-unique "UUIDs" were "overwriting" those already existing "UUIDs" with their different name!), I did some more (and more extensive) tests than I already did before, and found out that even when using 1'000'000 different seeds for the PRNG (pseudo-random number generator) used for generating UUIDs, I never got more than 512 different "UUIDs". :shock:

The PRNG I was using was not written by myself, but taken from an older version of the Linux C library, which I thought should be "good enough", and I am quite sure that the bug is not in the PRNG code itself, but in my integration of it into R'n'D. As I use the same PRNG for the game engine(*), I've added another "known good" PRNG for UUID generation, and tested it thoroughly (for example, getting 1'000'000 different UUIDs for 1'000'000 different seeds now), so this problem should now be gone. (I better don't tell you about the required code in both R'n'D and the high score server to handle the resulting problems of having R'n'D clients with broken and fixed UUIDs talking to the score server, but it seems that it works fine now for both old and new R'n'D clients, with the exception that pre-4.3.0.3 versions of R'n'D cannot rename their players anymore, and will create a new player on the server when submitting new scores after renaming their player.)

Therefore, please upgrade soon. :-)
filbo
Posts: 647
Joined: Fri Jun 20, 2014 10:06 am

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by filbo »

(*) what ?

If the prng is so bad, the game engine probably shouldn't be using it either. This would invalidate old tapes so you'd need a tape header flag; or judge by engine version; to decide which prng to use in playing back a tape...
User avatar
Holger
Site Admin
Posts: 4073
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by Holger »

Yes, that's what I wanted to say. :D :-P

Seriously: Yes, it should probably be replaced by someting that works better. The engine version would be enough, as it is already the case for a number of other bugs and weirdnesses as well, for the last few decades. ;-)

Although most probably nobody will notice any difference at all anyway, as 512 different "random" states will probably be indistinguishable from 512 billion random states... but it will be unsatisfactory to know that the random number generator is *that* bad, of course... :D :shock: :o :mrgreen:
filbo
Posts: 647
Joined: Fri Jun 20, 2014 10:06 am

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by filbo »

I've actually been curious about that for years -- does RnD 'know' the prng algorithms of all the various games it emulates? Or are all of the 'tapes' it can handle self-generated by some version of RnD, so it only needs its own algorithmic history?

If there are only 512 starting points, there are only 512 possible 'versions' of each level. That is quite limiting.

It also means that random actions like amoeba growing are far less random than one might imagine. It seems like there may be cases where this really affects the possible outcomes.
User avatar
Holger
Site Admin
Posts: 4073
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by Holger »

One correction:
The PRNG I was using was not written by myself, but taken from an older version of the Linux C library, which I thought should be "good enough", and I am quite sure that the bug is not in the PRNG code itself, but in my integration of it into R'n'D.
Apparently it is not the integration into R'n'D, but indeed the poor quality of the PRNG taken from a very old version of GNU libc, dating from 1994 or earlier. In fact the random()/srandom() code is among the code of the initial commit of the GNU libc Git repository of February 1995, but probably being much older, as the PRNG code was replaced only four days later with an improved implementation. The code used in R'n'D probably dates back to the GNU libc source code of my 1992/1993 Linux installation I used when developing the first versions of R'n'D (which added the libc random functions in 1997, using that pre-1995 code).

Some more tests with that old PRNG shows the following: When using "random() % 65536" instead of "random() % 256" to create a new UUID (generating two UUID bytes at once, therefore using more bits of the random value), up to 131072 (2^17) unique UUIDs will be generated (which is still far too little). On the other side, when using "((random() % 16) << 4) | (random() % 16)" to calculate each UUID byte, the overwhelming number of 32 (2^5) different/unique UUIDs is generated for 1'000'000 different random seeds (while the same approach using the new PRNG generates 1'000'000 different UUIDs, as expected).

So, apparently the following paragraph from the RANDOM(3) man page (on the Mac, not Linux) was still true for that older version of the code:
The random() and srandom() functions have (almost) the same calling
sequence and initialization properties as the rand(3) and srand(3) func-
tions. The difference is that rand(3) produces a much less random
sequence -- in fact, the low dozen bits generated by rand go through a
cyclic pattern. All of the bits generated by random() are usable. For
example, `random()&01' will produce a random binary value.
It's interesting that these serious limitations of the PRNG used for the R'n'D game engine is not immediately visible, as the engine very often requests random numbers from a very small range (like 0..1 or 0..7). :shock:
User avatar
Holger
Site Admin
Posts: 4073
Joined: Fri Jun 18, 2004 4:13 pm
Location: Germany
Contact:

Re: Rocks'n'Diamonds 4.3.0.3 released!

Post by Holger »

After these general thoughts on the problems with the PRNG in R'n'D, some answers to filbo's questions:
I've actually been curious about that for years -- does RnD 'know' the prng algorithms of all the various games it emulates?
Yes, it does, but cannot always use the "original" algorithm. For example, the original PRNG of Emerald Mine uses the Amiga's Kickstart ROM, which would have to be included into R'n'D for a perfect emulation, which is not legally possible. Therefore, it uses a much more simple "((random = random << 31 | random >> 1) % x)" with some additional modifications during game loop (like "random = random * 129 + 1") instead, which works quite well. Supaplex uses "seed = (seed * 0x5E5 + 0x31) & 0xFFFF; return (seed >> 1);" instead, which is used to successfully play all those very old Supaplex solution tapes.
Or are all of the 'tapes' it can handle self-generated by some version of RnD, so it only needs its own algorithmic history?
That's only true for the R'n'D engine, which used srand()/rand() in it's earliest versions, later followed by the GNU libc implementation of srandom()/random().
If there are only 512 starting points, there are only 512 possible 'versions' of each level. That is quite limiting.
Indeed, although that number might in fact be even smaller (see above). :?
It also means that random actions like amoeba growing are far less random than one might imagine. It seems like there may be cases where this really affects the possible outcomes.
I'm sure it does, and I remember that I have already questioned the PRNG years ago (after whatever observations I might have made; I vaguely remember that Alan Bond pointed me to some "problems" with randomness when he created his on-the-fly randomly generated levels); unfortunately I never did such tests I now did to check UUID generation (but probably only some simple tests which apparently ended in "good enough" results or something lime that).
Post Reply