What happens if you remove randomness from Doom?

by pdw • 11 years ago

450 102 11 years ago

nullc• 11 years ago

It might be better to call this Low Probability Doom-- indeed, it's deterministic, but so would changing the random number generator to a counter.

The impacts being discussed are mostly the effect of playing the unluckiest game of doom possible. :)

spiritplumber• 11 years ago

This is neat... since Doom is open source, why not make the binaries available for a quick romp?

Also, try $80 as well as $00 and $FF?

(Yeah, I'm lazy)

mahouse• 11 years ago

It's very easy to compile any port. I personally recommend you to try Chocolate Doom.

GhotiFish• 11 years ago

yaay it compiled!

Just grabbing an IWAD, I'm looking forward to trying this! Thanks for the suggestion

dfkf• 11 years ago

Videos of such experiments would be greatly appreciated.

jmtd5• 11 years ago

Took me a while but here you go https://www.youtube.com/watch?v=SvfJoy1rjmo

pslam3• 11 years ago

Even the "randomness" is deterministic. The fixed, repeating table is an optimization, but it's also completely necessary for multiplayer to work.

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.

xamuel• 11 years ago

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

pslam3• 11 years ago

Wow! Yes, I am interested in that kind of thing.

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!

anon4• 11 years ago

My favourite example: http://tasvideos.org/1145M.html completing a game in under 10 seconds by manipulating the RNG to spawn the final quest completion item under the player's initial spawn point.

dchichkov2• 11 years ago

Yes. By the way this feature of Doom was allowing nice and symmetric multiplayer over slow modem or network lines. Only small client-side packets were send through the network (think keystrokes/mouse movement updates).

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...

TheLoneWolfling12• 11 years ago

Probably floating-point oddities. The bane of deterministic programming everywhere.

elwell• 11 years ago

Cool. Do you have blog that talks about old game hacks?

bananaboy• 11 years ago

The Quake and QuakeWorld source weren't released until 1999.

wyldfire• 11 years ago

Even the "randomness" is deterministic.

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.

pslam3• 11 years ago

Indeed, and I should have said "pseudorandom". What I'm trying to say is that it's fully predictable.

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.

jzelinskie• 11 years ago

the game slows down

You act like games today don't do this. Most games by Nintendo, notably the latest Super Smash Bros., embarrassingly still do this.

johntb86• 11 years ago

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.

This is similar to a crit hack in TF2: https://wiki.teamfortress.com/wiki/Hacking#Critical_Hacks

AgentME• 11 years ago

This isn't an uncommon strategy today. Many online RTS games work in a synchronized model like this still; it's much cheaper to for all players to send each other their inputs than for the server to send the positions of possibly thousands of characters constantly. The recent Halo games use a synchronized network model only in their cooperative modes. (It's obvious because lag will cause the game to slow down.)

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!

cmdrfred• 11 years ago

I've only been programming for a couple years, and I thought I was a genius for coming up with a game engine exactly as you describe here. deterministic randomness, doom beat me to it by a couple decades.

catshirt• 11 years ago

I believe modern hacks for counter strike behave exactly that way.

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.

ygra• 11 years ago

Not since December. It has been changed so that hit testing is done with a server-side seed. With the drawback that decals and tracers are wrong client-side.

im3w1l2• 11 years ago

This rng cheating can be prevented. Have everyone generate a random number in any way they want. Send that number out along with their inputs. xor all the numbers together. Then deterministically stretch the result into however much randomness is needed.

nhaehnle3• 11 years ago

This approach alone is not enough. A cheating bot could wait until they received the input+number from all other players, then choose their own number as needed to obtain the desired "random" result.

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...)

aminok3• 11 years ago

Just a thought: a FPS multiplayer game could use the proof of work generated by the Bitcoin mining network (e.g. a pool share 1/20th the difficulty of a block hash, which would be generated on average once every 30 seconds) as the seed for the RNG. This would be:

* 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.

firethief• 11 years ago

Is there a problem that solves, or is it just "because Bitcoin!"?

lmm2• 11 years ago

I very much doubt you could synchronize with the bitcoin consensus faster than synchronizing with the other players. If you're willing to communicate with each other then you can generate a random number in a consensus way easily (e.g. everyone generates their own and XOR them all).

ot• 11 years ago

Obligatory XKCD: https://xkcd.com/221/

wtbob• 11 years ago

Very interesting. One could, though, have a fair multiplayer game where each player picks a random number, commits to it (e.g. by hashing it and publishing the hash), then all players reveal their numbers, XOR them all together and use that as a seed for a CSPRNG. With a good CSPRNG, they could even mix player actions into the generator over time, resulting in a truly random game.

bentcorner• 11 years ago

It's interesting that such a simple implementation of randomness works so well, in particular enemy in-fighting and their decision to pursue or not. I'm sure when you're playing, you end up anthropomorphizing many of these decisions.

anyfoo• 11 years ago

Note that these decisions might still be "intelligent" (to a certain degree, i.e. not actually random but based on reasoning) without that hack.

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.

kkl• 11 years ago

Beautiful. This article made me smile. I also like that the author gave a simple "how-to" at the end in case I wanted to try it myself (i do!).

twblalock• 11 years ago

I'm always impressed by the simple ingenuity of the Doom source code and the immersive environment it creates.

RussellDussel• 11 years ago

This instantly reminded me of the (true) story where people were able to cheat an online poker game because the site released its source to "prove" its fairness/randomness, showing that the deck was shuffled from a fixed state using a standard RNG with the time of day (in ms) as the seed.

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.

swang• 11 years ago

This is PlanetPoker[0]

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...

im3w1l2• 11 years ago

By the birthday property, this means that it is very likely to experience the exact same deck being played out more than once.

pcvarmint3• 11 years ago

When I added friendly monsters and Wolf3D dogs to Doom, I tweaked the randomness to make the dog behavior more life-like.

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.

pcvarmint3• 11 years ago

Also, demo reproduction was a huge issue. We had to do all kinds of versioning to make sure that a demo which was recorded with one version of Doom/Boom/MBF/etc. was faithfully replayed with the current version. One tiny mistake, and the whole demo could go into a tailspin. This sometimes meant we had to preserve bugs like Lost Soul stuck-in-wall bugs.

pcvarmint3• 11 years ago

Oh, and randomness could have fixed the monster-stuck-in-doorjam bug, which is easily reproduced in E2M4 with the Baron by the blue key. The code assumed that if a monster was "in" a door sector and was blocked, then the door simply needed to be opened, and then the monster could continue in its current direction. Better would be to rotate the monster's direction randomly to help them to get out of the sticky situation. That was our fix in Boom.

PhasmaFelis5• 11 years ago

Monsters do not make different death noises at different times; only one is played for each category of monster.

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.

PhasmaFelis5• 11 years ago

On further consideration, I think it only does this with imps and the various zombies, which are the only monsters that you're likely to mow down at a rate of several per second--it might have been specifically intended to stop zombie fragfests from sounding like an echo chamber.

jmtd5• 11 years ago

Hi, article author here: it was the pitch shifting behaviour in particular that I wanted to explore when I modified the random table. Early versions of doom (<1.4) did it, but they accidentally removed that feature with a rework of sound code in 1.4 and onwards (including all versions of doom 2). It was originally applied to all but two sound effects, with special casing for chainsaw sounds (less variance afaik).

There were, however, three distinct zombie death noises, independent of pitch shifting.

frik• 11 years ago

Half Life 1 did the same audio trick too. (It's based on the Quake 1 engine)

zak_mc_kracken• 11 years ago

I'm intrigued by this:

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?

JasuM• 11 years ago

It reads the next number in the list, it's not a random lookup. See https://github.com/id-Software/DOOM/blob/master/linuxdoom-1....

justsid• 11 years ago

Doesn’t that already make it deterministic though? It’s always the same sequence of “random” numbers, even before replacing the lookup table it should’ve been deterministic.

PhasmaFelis5• 11 years ago

The chance of monster in-fighting is never, or a certainty. The player is either mute, or cries in pain whenever he's hurt.

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.

shultays3• 11 years ago

OP is wrong about Doom's determinism I guess, it is already deterministic, random values are predefined. He just set them to constant, so his random is literaly "int random() {return 4;}", still deterministic but not 'random'

PhasmaFelis5• 11 years ago

Regular Doom may not be random in the mathematical sense, but it is as far as a player is concerned. In combat, pulls from the "random number" pool are happening fast enough that I don't believe it could be exploited in any meaningful way.

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.

azinman2• 11 years ago

Wish there had been videos posted!

jmtd5• 11 years ago

Yeah a video would be a good way to demonstrate this but it would take a lot of editing to do properly and I ran out of time last night and really wanted to get this out. I might post a follow up video later.

jmtd5• 11 years ago

Took me a few days, but here's a video https://www.youtube.com/watch?v=SvfJoy1rjmo

madsravn• 11 years ago

The chance of monster in-fighting is never, or a certainty.

Still seem a little random, though

yuriks• 11 years ago

PRNG determinism is widely utilized in TAS (Tool-Assisted Speedrun, basically a game played using tools such as frame advance and save states to simulate a "omnipotent" player.) to manipulate games to achieve favourable outcomes. Usually the game code is reverse engineered and a Lua script is created that searches forward in the RNG outcomes to find the ones you want, it is then up to the runner to execute actions in the game that give you that state.

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

What happens if you remove randomness from Doom?

Related Stories