13 ms·

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

by pslam 11y 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 11y 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 http://tasvideos.org/2825M.html
- pslam 11y 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 11y ago
  My favourite example: http://tasvideos.org/1145M.html 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.
dchichkov 11y 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...
- TheLoneWolfling 11y ago
  Probably floating-point oddities. The bane of deterministic programming everywhere.
  - tobinfricke 11y ago
    Floating point is deterministic.
    - dilmuff 11y ago
      For distributed scenarios where the architecture, language and library are unspecified and effectively random, it is not. Not so long ago x87 80-bit precision was common while non x87 systems typically used single and double precision. Finally, IEEE-754 does not specify transcendental functions, so once you use those your results vary all over the place as approximations vary. The fact that Go does not use the the CRT for FP will demonstrate this in the real world.
    - munificent 11y ago
      On a single chip, yes. But different chips handle some corner cases differently, leading to divergence between machines.
wyldfire 11y 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.
- pslam 11y 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.
  - deleted 11y ago
    [deleted]
  - caf 11y ago
    seed = seed * m + a would certainly have been much slower than a table lookup at the time, but that's not the case with current microarchitectures.
  - xsmasher 11y ago
    Since we're bikeshedding... >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.
    - Arnavion 11y ago
jzelinskie 11y 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.
- deleted 11y ago
  [deleted]
- ossreality 11y ago
  for completely, completely, completely different reasons
johntb86 11y 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 https://wiki.teamfortress.com/wiki/Hacking#Critical_Hacks
AgentME 11y 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-controlling-nethacks.html http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont... for an example of that sort of thing done in Nethack!
cmdrfred 11y 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 11y 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 11y 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.
im3w1l 11y 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.
- nhaehnle 11y 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...)
  - geocar 11y ago
    You need to additionally add a salt to the hash taken from each peer.
    - nhaehnle 11y ago
      Good point. Yes, if the range of random numbers chosen is small. 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.
    - 11y ago
aminok 11y 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 11y ago
  Is there a problem that solves, or is it just "because Bitcoin!"?
  - aminok 11y ago
    I'm not sure if it solves any problems, but I think it might, for a couple of reasons: * 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.
- lmm 11y 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).
  - aminok 11y ago
    How do prevent one party delaying the provision of their R to the other players while calculating the final R for themselves?
ot 11y ago
Obligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/
wtbob 11y 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.

by pslam 11y ago

xamuel 11y 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 http://tasvideos.org/2825M.html

pslam 11y 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 11y ago
My favourite example: http://tasvideos.org/1145M.html 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.

dchichkov 11y 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...

TheLoneWolfling 11y ago
Probably floating-point oddities. The bane of deterministic programming everywhere.
- tobinfricke 11y ago
  Floating point is deterministic.
  - dilmuff 11y ago
    For distributed scenarios where the architecture, language and library are unspecified and effectively random, it is not. Not so long ago x87 80-bit precision was common while non x87 systems typically used single and double precision. Finally, IEEE-754 does not specify transcendental functions, so once you use those your results vary all over the place as approximations vary. The fact that Go does not use the the CRT for FP will demonstrate this in the real world.
  - munificent 11y ago
    On a single chip, yes. But different chips handle some corner cases differently, leading to divergence between machines.

wyldfire 11y 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.

pslam 11y 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.
- deleted 11y ago
  [deleted]
- caf 11y ago
  seed = seed * m + a would certainly have been much slower than a table lookup at the time, but that's not the case with current microarchitectures.
- xsmasher 11y ago
  Since we're bikeshedding... >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.
  - Arnavion 11y ago

jzelinskie 11y 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.

deleted 11y ago
[deleted]
ossreality 11y ago
for completely, completely, completely different reasons

johntb86 11y 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 https://wiki.teamfortress.com/wiki/Hacking#Critical_Hacks

AgentME 11y 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-controlling-nethacks.html http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont... for an example of that sort of thing done in Nethack!

cmdrfred 11y 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 11y 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 11y 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.

im3w1l 11y 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.

nhaehnle 11y 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...)
- geocar 11y ago
  You need to additionally add a salt to the hash taken from each peer.
  - nhaehnle 11y ago
    Good point. Yes, if the range of random numbers chosen is small. 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.
  - 11y ago

aminok 11y 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 11y ago
Is there a problem that solves, or is it just "because Bitcoin!"?
- aminok 11y ago
  I'm not sure if it solves any problems, but I think it might, for a couple of reasons: * 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.
lmm 11y 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).
- aminok 11y ago
  How do prevent one party delaying the provision of their R to the other players while calculating the final R for themselves?

ot 11y ago

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

wtbob 11y 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.