What happens if you remove randomness from Doom?
jmtd.net
jmtd.net
Doom does things very differently to how more recent multiplayer FPS multiplayer works. Every player's host machine has identical state. That's not as superficial as things like score, who is alive/dead, etc - it's exact positions or all entities, their metadata... all the way down to the next number to be picked by the random number generator.
This is updated every tick (30Hz? can't remember) and every machine needs to synchronize with every other within that tick, or the game slows down. If you've ever played Doom over a modem, you know what it's like when someone has bad settings which result in high latency - in this case, poor frame rate. The data sent between machines consists of the inputs - e.g rotation, movement, fire, talk - and not higher level constructions such as motion vectors.
So it's entirely necessary that the "random" number generator is not so random at all. It's fairly hilarious to see the results of messing with it, though :)
It does make me think that cheats (not that I ever cheated) were missing a trick. If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider.
If you're interested in that kind of stuff, check out tasvideos.org, a community dedicated to beating old videogames as fast as possible using that type of knowledge. Since all videogame 'randomness' is really deterministic pseudo-randomness, the kind of RNG-knowing you described is ubiquitous
In fact, by coincidence, it looks like someone just recently published a DOOM (second episode) run: http://tasvideos.org/2825M.html
Also a coincidence: me and my brother used to do cooperative 2-player speeed-runs of Doom/Doom2 as part of a thing called "H2HMud". We had a setup which consisted of a fast 486, and a really slow 386. It ran really slowly - about 1/4 normal rate when you woke up a room full of entities. The 486, however, rendered every frame, which meant the person on the fast machine could happily pick every off pixel-perfect, while the slower machine player would do "support" stuff (flip switches).
I wondered what the "limit" would be if you could slow it down arbitrarily, and re-stitch, and I guess that's what it looks like in the video you posted. Thanks!
As a different example Quake was designed using a client/server model with hugely asymmetric packet sizes (~40 bytes for client->server packet and ~800 bytes for the opposite direction).
As a teenager at around 1996-1997 I once tried to re-factor Quake to use the same model as Doom - run server/client combo on both machines with servers synchronized using exact same random generator seeds / etc. Spend about two months on that, but it had proved to be very difficult - the sync between the servers was inevitably lost due to some indeterminism in the code that I couldn't uncover. Maximum that I was able to achieve was around two seconds running in sync. And I still don't know where the sync was getting lost ;)
Learned a lot from that experience, big thank you to John Carmack (and the Id Software team) for writing that code as good and clean as he/(they) did...
Something like this:
if( a == x/y )
assert( a == x/y );
if( a == x/y )
if ( getRandomBooleanFromSomewhere() )
assert( a == x/y );
Why, you might ask? It's allowed to use extra precision, but not required to. And it's not required to even be consistent about it. So: if it uses extra precision, and it decides to lose the extra precision (say, by spilling x/y to stack) between the first and second uses, the assert could potentially fire. If it doesn't do both of those, the assert cannot fire. So it's legal to remove the assert, but also legal to keep it. And also legal to randomly decide which to do at runtime.
Now, this is a stupid thing for it to do in this case. But nonetheless, it is allowed. And there are cases where analogous optimizations actually make a plausible amount of sense.
You can work around it to an extent with FPU flags. But that way lies madness. To put it mildly. ("It desyncs when I print a document.")
It's the compiler that's mainly the problem here. Or rather, the language standard.
That most certainly gives the appearance of non-determinism.
And floating point is frequently infamously tricky to deal with, I think is the obvious point without arguing terminology.
if( a == x/y )
assert( a == x/y );
That's right. The above can be legally compiled to always trigger, or never trigger, or even to sometimes trigger (although this is rare in practice).
Why? C / C++ allow floats to be stored with excess precision. And they lose that excess precision when spilled to RAM. And GCC isn't deterministic. So x/y may be pulled out as a common subexpression and spilled to a register after the first usage, and it triggers. And then the next time it isn't, and it doesn't. (Effectively, the difference between this:
temp = x/y
if( a == temp) {
spill(temp);
assert( a == temp );
}
temp = x/y
if( a == temp) {
assert( a == temp );
}
You can (most of the time) work around this by manually setting FPU precision (note that you need to change the precision of both the mantissa and exponent, as otherwise you can still end up with issues). (Except that you, in C++ at least, have to work deep magic - you have to set it before main even runs, because you can end up with problems with static initialization otherwise.) And in the process losing compatibility. And finding that random code you call occasionally resets things. Or random code you don't call (a classic example: the printer driver!). And using exactly one of float or double throughout. And hoping that none of the libraries you use ever resets FPU precision for anything, or uses the other of float or double itself. (And hope that your OS properly saves / restores the FPU everywhere, though this has largely become a non-issue).
And, worst of all, you've got to hope that the compiler performs constant folding with the same level of care as you've just taken.
Look at these:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845
http://yosefk.com/blog/consistency-how-to-defeat-the-purpose...
http://gafferongames.com/networking-for-game-programmers/flo...
http://www.yosoygames.com.ar/wp/2013/07/on-floating-point-de...
If only to have deterministic test cases...
(Relatedly, several ASIC and FPGA tools suffer from nonlinearity so badly that they will let you specify the random seed at the start and/or do multiple runs with different seeds to pick the best result)
if( a <= x/y )
assert( a <= x/y );
Main source of multi-player sync loss was a different number of rand() calls between machines e.g. a different animation sequence for own character vs enemy. If own animation calls one rand() too many, the next common rand will return diff values on own vs enemy machines. And you essentially start playing two different games together ;-)
That being said, we fixed all bugs. There were no additional checks to synchronize state other than keyboards. It was way easier than we anticipated!
Good times!
Unfortunately, many of the edge cases that cause non-deterministic behavior have gotten substantially more exploited by compilers since then.
The problems with today's systems does not lie in compilers. It lies in vastly increased complexity of the code itself.
Back in 96 we had a few sprites, with some animation sequence, sound effects. State of an object was kept in a few integers. Collisions were done using really stupid algorithm that would probe special mask in level builder with a circle consisting of 16 points, so we can get a vector pointing away from the wall. Etc.
Today, collisions, physics, presentation - all this is thousands of times more complex. More code, more bugs, more issues.
For that reason, it would be very difficult to write keyboard-state driven multiplayer today.
W.r.t. floating-point, good luck. See https://news.ycombinator.com/item?id=9430958
The only way to correct such error would be to change model to sync the actual state among machines. But that means completely different code.
All in all, I remember we added the multiplayer code at the very end. If we decided to sync state rather than exchange keyboard+mouse, we would not finish on time.
At least for anything that ever passes through C or C++, or uses code that does. (I.e. everything, close enough.)
Games I've worked on have used libraries e.g. http://nicolas.brodu.net/programmation/streflop/index.html
Now, what do you suppose happens during a context switch, when a second process wants to use floating point math?
Where you can get unpredictable (though still repeatable) behaviour is when your compiler spills into 64-bit memory slots, and does it a little differently with each little modification to the code.
""" wikipedia John Carmack ... and the Doom source code in 1997. When the source code to Quake was leaked and circulated among the Quake community underground in 1996, a programmer unaffiliated with Id Software used it to port Quake to Linux, and subsequently sent the patches to Carmack. Instead of pursuing legal action, Id Software, at Carmack's behest, used the patches as the foundation for a company-sanctioned Linux port.[citation needed] Id Software has since publicly released the source code to Quake, Quake 2....
But isn't rand() deterministic too? It's only governed by the seed.
Only /dev/random is "really" random, AFAIK. And even that is only as good as the nearby entropy.
Yes, they could have used rand() with an appropriate srand(seed), communicated between machines. They could even have used a DRBG built with an AES cipher, except it would have been too slow. However, even a bad implementation of rand() usually uses an algorithm which is essentially just "seed = seed * m + a", which is slower than a table lookup.
Anyway - the interesting thing is that a 256 entry table is sufficient for game purposes (not obvious to players), is fast, and makes the synchronous multiplayer setup work.
>Yes, they could have used rand() with an appropriate srand(seed)
rand() is shared across the whole OS, so another program calling rand() could make you skip a number; or another program could reseed rand. Then you've lost determinism.
Even if that weren't the case, you don't want you FX system to call rand() and "steal" the next number that that AI system was expecting.
With Doom's table, each system can keep a separate index into the table; now calling getRand(myIndex++) from one system doesn't interfere with other systems.
Is there actually any implementation of rand that does this? I feel like this would be a buggy implementation, or at the very least, goes against the spirit of the standard,
> If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is called before any calls to srand have been made, the same sequence shall be generated as when srand is first called with a seed value of 1.
> The implementation shall behave as if no library function calls the rand function.
You act like games today don't do this. Most games by Nintendo, notably the latest Super Smash Bros., embarrassingly still do this.
This is similar to a crit hack in TF2: https://wiki.teamfortress.com/wiki/Hacking#Critical_Hacks
>It does make me think that cheats (not that I ever cheated) were missing a trick. If they knew what the next number to be pulled from the random number generator was, they could, for example, delay firing a weapon by a frame or two, to get more damage. Probably other more interesting things I can't think of immediately. If there was ever a bot vs bot Doom competition, this is something you'd definitely want to consider.
See http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont... for an example of that sort of thing done in Nethack!
if I recall correctly, the accuracy spread for bullets is determined by a "random" seed on the client. aim hacks can counteract recoil and bullet spread by "predicting" the next values the client is going to generate.
A workaround is to have all parties pre-commit to their numbers by first sending a hash of the number. Each party will reveal their number only after receiving the hashes of everybody else. This adds another round-trip, which is bad for latency.
As a compromise, one could have clients pre-generate a whole sequence of numbers, pre-commit to that sequence by publishing its hash, and then reveal the sequence one number at a time. Then it is possible to detect tampering with the randomness at the end of a game.
However, even with this modification, another source of cheating in a peer-to-peer networked game may be that one party might want to adjust their input after having received the inputs of everybody else. This can again be mitigated with the same commit-before-publish scheme, except that now the loss of latency cannot be prevented.
(Obviously, all of these cheats can be eliminated when you have a trusted server, but in that case you can just let that server generate the randomness...)
If the random numbers being exchanged are N bits long and the length of the hash is also N (say N = 256), then a salt should be unnecessary, right? Inverting an essentially random hash value should be impossible. But it's always possible that I'm missing something.
The reason behind needing a salt normally is password reuse / poor entropy. But you don't have either problem with this situation.
Just have each peer generate a random number of sufficient length.
So, roughly. When you need more random numbers:
1) Have every client generate a random number of sufficient length and publish a cyyptographic hash of it.
2) Wait for everyone to ack that they have every hash
3) Everyone publishes the random numbers.
3) Every client verifies that everyone's random numbers match the hashes, and computes the final random value as the xor of everyone's random numbers.
As long as the random numbers generated by the clients are long enough / actually randomish, this should work.
AFAIK, this is secure. A client cannot delay until after they know other peoples random numbers, as it'll stall at step 2. A client cannot find someone else's random number from their hash, as inverting the cryptographic hash of a random number of sufficient length is infeasible.
About the only concern with this is spoofed network communication. And that's detectable.
It's part of the definition of a (secure) cryptographic hash function that this is impossible. For a secure hash function, finding two messages with the same hash cannot be done faster than by birthday collisions, which means that for a 256 bit hash function you need to compute 2^128 hashes, for a 512 bit hash function you need to compute 2^256 hashes. Even 2^128 is a pretty big number.
So you're right: adding the salt prevents the attack of precomputing a collision using an insane amount of computing power. Then again, if that's what you're worried about then you also have to consider AES-128 as broken, which (today) puts you in a rather small minority. I suppose one can never be paranoid enough ;-)
* unpredictable in practice (theoretically a player could reliably predict the hash, but only if they overpower the entire Bitcoin mining network, at a cost of billions of dollars in mining hardware)
* globally verifiable, allowing reliable synchronization
The only drawback would be that the time between proof of work shares meeting a particular difficulty target is somewhat random, in being a Poisson distribution that only averages to a particular value.
* it's provably fair, with no reliance on a trusted third party to provide a fair random number, with fair being defined as a random number that none of the participants can predict / obtain foreknowledge of.
* propagation might be faster than what can be achieved through the internet, because dedicated broadcast channels are being created for Bitcoin blockchain data, like the BitSat program, which will broadcast Bitcoin blocks to the entire planet via a cluster of 24 nanosatellites, or the Kryptoradio project, which broadcast the data over radio in Finland.
Of course this meant there were only 86,400,000 possible decks, people could generate all the possible decks ahead of time and as soon as cards would be revealed in the game they could easily match the hand being played to the limited set of possibilities. Essentially they had foresight of which cards were coming out. Furthermore, once a few decks were matched up you could vastly reduce the set of possibilities even further by working out the approximate time of day on the server.
The gist of it is their algorithm never chose the last card in the array to swap with, and the last card was never guaranteed to be the last card. They also committed the common mistake of implementing the "naive" shuffle, which is not equally distributed.
[0] http://www.cigital.com/papers/download/developer_gambling.ph...
This, BTW, is a really interesting trick that Doom pulled. There's actually only a single death sound for each type of monster.* But for some monsters, the game plays it back at a random speed--also changing the frequency, like an audiotape on fast-forward--so it becomes a brief shriek, a drawn-out groan, or something in between. This gives an impressive variety of sounds without adding extra memory-heavy samples.
Hardly anyone was aware of this as far as I can tell, which is a testament to how well it worked. I only noticed it when playing a goofy little mod that turned zombie sergeants into Energizer bunnies and played the "still going" clip when you killed them. The effect is obvious when there's actual speech involved.
*Not counting the "splatter" sound when you gib any of the gibbable critters.
There were, however, three distinct zombie death noises, independent of pitch shifting.
Or maybe I'm completely confused because I haven't played it since the '90s. Might be time to give it another try...
Friendly monsters go after enemy targets, but absent any targets, they follow you in semi-random motions, but they stay a comfortable distance away from you, except when getting onto a platform or other crowded space.
Disclaimer: I'm the author of MBF.
The impacts being discussed are mostly the effect of playing the unluckiest game of doom possible. :)
One example of this technique which I particularly like is the "100% Souls" run of Aria of Sorrow, where the normally very grindy process of getting enemy soul drops is trivialized by making sure that every enemy will drop a soul the first time it's killed: https://www.youtube.com/watch?v=DfkJpzBoJ-M
> I hex-edited the binary and replaced the random number lookup table with static values
If you have a look up table that you randomly look up, doesn't that mean you already have a random source? In this case, why need a random look up table at all?
Also, try $80 as well as $00 and $FF?
(Yeah, I'm lazy)
Just grabbing an IWAD, I'm looking forward to trying this! Thanks for the suggestion
This is interesting. I thought that both of those things were deterministic to begin with--monsters that get hit by other monsters will go after the offender until it's dead or something else hits them, and the player makes the "pained gasp" sound effect every time he's hit.
What I meant was, I hadn't thought that infighting target choice and player pain-noise referred to the "random" pool at all. I thought they were 100% predictable in the original game. I wonder where the randomness actually comes in.
But there might be a small chance involved where the entity would do another thing than the algorithmically determined action, and depending on how the values are interpreted this then triggers, the overriding of the game AI now just happens every time.
Still seem a little random, though