Determinism in League of Legends: Implementation (2017)(technology.riotgames.com)
technology.riotgames.com
Determinism in League of Legends: Implementation (2017)
https://technology.riotgames.com/news/determinism-league-legends-implementation
51 comments
> League of Legends does not use a fixed-step server clock, but rather a measured frame delta time which we throttle to a target frame rate. This makes the server more resilient to system-wide performance spikes, but this pattern definitely complicated determinism.
This could use some elaboration. I don't even know how it's possible to have determinism without a fixed-step. I must misunderstand what this means. Every simulation tick in league of legends has gotta be the same duration, right? ie: 1.0 / 60.0?
This could use some elaboration. I don't even know how it's possible to have determinism without a fixed-step. I must misunderstand what this means. Every simulation tick in league of legends has gotta be the same duration, right? ie: 1.0 / 60.0?
The physics game sim step had to be hardcoded but you could vary the graphics rendering independently. That did mean you needed to use a different RNG for sim objects and graphics-only particle effects.
I worked on the deterministic instant-replay system for a racing sim on PS3. The most interesting thing was that on PS3 we had main processor cores (PPU) and helper cores (SPU) which had their own instruction set. Our physics sim could distribute work across both, but the thread assignment had to be deterministic because PPU and SPU got marginally different floating point results for the same instructuion and inputs. That was a fun one to figure out!
I worked on the deterministic instant-replay system for a racing sim on PS3. The most interesting thing was that on PS3 we had main processor cores (PPU) and helper cores (SPU) which had their own instruction set. Our physics sim could distribute work across both, but the thread assignment had to be deterministic because PPU and SPU got marginally different floating point results for the same instructuion and inputs. That was a fun one to figure out!
Incredible insight, thank you! Could you elaborate on any more of your experiences with PPU/SPU programming? Also, what have you gone on to do since then?
Thought I heard my ears ringing... Blast from the past here.
That's the beauty part of recording server state and playing it back -- we included a recording of whatever accurate integer-based OS time I could get on each platform. On Windows, for example, I record the raw values of QPC ticks and the tick rate into the recording. Then on playback, I play back the clocks themselves as if the hardware has that tick rate and tick count are from the recorded computer. So if frame 10 took 33.3ms and frame 11 took 66.7ms, we'd play them back that way.
Note that playbacks are almost never in real-time. The reason a typical server frame takes 33ms is that we might be processing for 5ms and then yielding the thread (sleeping) for the remaining time during real-time gameplay. On playback, we don't yield the thread, so we play back faster than real-time when doing something like a live Chronobreak (disaster recovery.)
Strictly speaking, you are right. Let's say we had a game with no player inputs (like a bots-only game.) It's possible that the outcomes might vary between two games with the same random seeds if they run different numbers of frames over the same time period. That said, we've actually tried this a few times, and our game code is surprisingly resilient to this -- only in a few instances have we found issues where subtle variations in frame time could impact player outcomes (and those are generally corrected when we find them -- this is an esports game after all.)
A lot of this comes down to tradeoffs. Yes we might have those subtle issues, but if we fixed our timestep, then we'd have the other problem of the game potentially going into slow-motion during (the admittedly rare) periods of long frame times. In practice, we decided time dilation is more negative for player performance than loss of interactive resolution; humans are great predictors of motion with limited information, but they're not so great when the rules of localized reality bend.
Edit: typo
That's the beauty part of recording server state and playing it back -- we included a recording of whatever accurate integer-based OS time I could get on each platform. On Windows, for example, I record the raw values of QPC ticks and the tick rate into the recording. Then on playback, I play back the clocks themselves as if the hardware has that tick rate and tick count are from the recorded computer. So if frame 10 took 33.3ms and frame 11 took 66.7ms, we'd play them back that way.
Note that playbacks are almost never in real-time. The reason a typical server frame takes 33ms is that we might be processing for 5ms and then yielding the thread (sleeping) for the remaining time during real-time gameplay. On playback, we don't yield the thread, so we play back faster than real-time when doing something like a live Chronobreak (disaster recovery.)
Strictly speaking, you are right. Let's say we had a game with no player inputs (like a bots-only game.) It's possible that the outcomes might vary between two games with the same random seeds if they run different numbers of frames over the same time period. That said, we've actually tried this a few times, and our game code is surprisingly resilient to this -- only in a few instances have we found issues where subtle variations in frame time could impact player outcomes (and those are generally corrected when we find them -- this is an esports game after all.)
A lot of this comes down to tradeoffs. Yes we might have those subtle issues, but if we fixed our timestep, then we'd have the other problem of the game potentially going into slow-motion during (the admittedly rare) periods of long frame times. In practice, we decided time dilation is more negative for player performance than loss of interactive resolution; humans are great predictors of motion with limited information, but they're not so great when the rules of localized reality bend.
Edit: typo
> It's possible that the outcomes might vary between two games
So just to clarify: in League, the 'dt' passed into each 'simulation step' is NOT constant? Isnt this kinda crazy? In your later articles, floating point imprecision is talked about. Couldnt this variance in dt create odd behaviour and ultimate contribute to weird things like 'character movement speed' being not _exactly_ the same between games? (like really small, but still...)
And beyond that, how does the client and the server synchronize with each other if the frame #s represent different positions in time? My mind is blown right now...
Note: I've worked on many networked games, and have written rollback/resimulate/replay code. I don't really understand _why_ League wouldnt use a fixed time step. Whats the advantage? In our games, the rendering of course uses the real dt passed in from the OS, but the simulation step is always fixed. This means in our games during a replay, your computer could render the outcome differently if your frame rate is different, but the raw simulation is always the same.
For context, to show I at least have some idea what I'm talking about, I made this replay system (and the game has rollback multiplayer):
https://gooberdash.winterpixel.io/?play=5b74f7c0-8591-40dc-b...
I havent played a lot of League, but I always assumed it would use deterministic lock step networking (like it's predecessor, Warcraft 3)
So just to clarify: in League, the 'dt' passed into each 'simulation step' is NOT constant? Isnt this kinda crazy? In your later articles, floating point imprecision is talked about. Couldnt this variance in dt create odd behaviour and ultimate contribute to weird things like 'character movement speed' being not _exactly_ the same between games? (like really small, but still...)
And beyond that, how does the client and the server synchronize with each other if the frame #s represent different positions in time? My mind is blown right now...
Note: I've worked on many networked games, and have written rollback/resimulate/replay code. I don't really understand _why_ League wouldnt use a fixed time step. Whats the advantage? In our games, the rendering of course uses the real dt passed in from the OS, but the simulation step is always fixed. This means in our games during a replay, your computer could render the outcome differently if your frame rate is different, but the raw simulation is always the same.
For context, to show I at least have some idea what I'm talking about, I made this replay system (and the game has rollback multiplayer):
https://gooberdash.winterpixel.io/?play=5b74f7c0-8591-40dc-b...
I havent played a lot of League, but I always assumed it would use deterministic lock step networking (like it's predecessor, Warcraft 3)
We're recording the integer clocks though, and those don't change between runs. While game code converts things like (QPC ticks over tick-rate) to floating point, we don't sum those numbers directly. Instead, we internally store times as the raw integers then convert them to floats on-demand (typically when an Update function is asking for "elapsedTime" or a timer is asking for a "timeSpan" (like time since the start of the game.))
LoL and TFT don't use a synchronized-simulation (lockstep, sometimes called peer-to-peer) networking model. LoL is Client-Server, meaning the replication is explicit and not based purely on playing back client inputs. This gives us more control over things like network visibility, LODs, and latency compensation at a feature-by-feature level at the cost of increased complexity. Most of the games I've built over the years use this model and the LoL team is super comfortable with it.
The GameClients are not deterministic in the way that the GameServer is, though they're naturally closer to that ideal since the GameServer itself is typically predictable.
Don't get me wrong, there's a time and place for lockstep replication, and LoL probably could have gone that way. I wasn't there when that direction was picked, but I would have likely made the same choice as my predecessors, knowing what I do about our approach to competitive integrity.
LoL and TFT don't use a synchronized-simulation (lockstep, sometimes called peer-to-peer) networking model. LoL is Client-Server, meaning the replication is explicit and not based purely on playing back client inputs. This gives us more control over things like network visibility, LODs, and latency compensation at a feature-by-feature level at the cost of increased complexity. Most of the games I've built over the years use this model and the LoL team is super comfortable with it.
The GameClients are not deterministic in the way that the GameServer is, though they're naturally closer to that ideal since the GameServer itself is typically predictable.
Don't get me wrong, there's a time and place for lockstep replication, and LoL probably could have gone that way. I wasn't there when that direction was picked, but I would have likely made the same choice as my predecessors, knowing what I do about our approach to competitive integrity.
All this stuff predates ECS and a fully specified definition of what a live service continent spanning MOBA is. All the tradeoffs make sense to me. The real question is, would it have been possible to define an engine solution that looks more like Overwatch, in the absence of a fully specified game? I feel like that is ECS's greatest weakness.
I feel like you’re skipping a step to make this comment make sense. Which is saying why using the Overwatch model would be better and why the need to introduce an ECS?
You can still achieve determinism by treating the measured delta-time as an input, and resimulating the game with recorded delta-time. This may not be feasible on public servers, but is definitely feasible for professional play where determinism is important to rewind games due to bugs which affect competitive integrity.
They have so many bugs that there's a procedure for rewinding the game during comp plays? Did I misunderstand?
They do! Its called Chronobreak. They have used it many times in professional matches successfully, but it doesn't work in 100% of scenarios.
This is not unusual. Bugs happen and when there's a lot of money on the line you need a rollback system.
Interesting. I don't think I've seen this in any other competitive game, which is why I'm surprised. But maybe I'm just lacking information
In StarCraft II you can resume from replay (and maybe in previous games as well), but I don't know if this has ever actually been used due to bugs in the game engine during competitive play.
I implemented a debug replay system for an American Football game when I worked at Sony. The AI hierarchy and all animation and physics state was recorded and game could be rewound to figure out why an NPC made a poor decision. Only needed to track state for the duration of a single play. This was on PS2 which I think had 32MB of memory but the dev systems had an extra 96MB which we could use for this sort of thing.
Hell. Replay review in American Football and other sports is a form of rewinding and fixing bugs in officiating.
So it's certainly done in real life when money's on the line.
So it's certainly done in real life when money's on the line.
Starcraft 2 lets you resume a game from a replay.
Yeah you _could_ but I fail to see why you would ever do this. It's also not feasible to synchronize the client with the server in real time with this input.
You don't need to synchronize the server and the client. The point of determinism is to be able to reproduce game states deterministically, not to have people play the video game deterministically. Again, this is to "undo" bugs in pro play (Chronobreak).
"After consulting with several other Rioters, our team settled on developing a new PRNG implementation based on XOR-SHIFT."
I wonder why?
I wonder why?
The xorshift family is one of the top two RNGs in the modern day (the other being PCG). Unfortunately, "choosing the ideal member of the family" is nontrivial if you're trying to eke out every bit of performance.
The problem with the xorshift family is that it doesn't implement the nice auto-scaling (and thus auto-testing) that PCG has. Re-parameterizing it means inventing whole new numbers from scratch and hoping you plug them in correctly. Xorshift also has a rare-but-severe "stuck near zero" problem.
The problem with the PCG family is that its trusted way of scaling (nobody likes the `_k` variants) relies on 128-bit multiplication (a modern member of the family at least reduces that to a mixed 128x64 multiply), which remains notably slow, unlike xorshift which only uses small integers.
(But I must emphasize: all RNGs from other families either have worse variants of these problems, or give up on performance entirely. These concerns should be used only to select your preferred tradeoff between the two, there is no excuse for ever using any other RNG family unless you need cryptographic security)
The problem with the xorshift family is that it doesn't implement the nice auto-scaling (and thus auto-testing) that PCG has. Re-parameterizing it means inventing whole new numbers from scratch and hoping you plug them in correctly. Xorshift also has a rare-but-severe "stuck near zero" problem.
The problem with the PCG family is that its trusted way of scaling (nobody likes the `_k` variants) relies on 128-bit multiplication (a modern member of the family at least reduces that to a mixed 128x64 multiply), which remains notably slow, unlike xorshift which only uses small integers.
(But I must emphasize: all RNGs from other families either have worse variants of these problems, or give up on performance entirely. These concerns should be used only to select your preferred tradeoff between the two, there is no excuse for ever using any other RNG family unless you need cryptographic security)
"It’s simple, fast, and has a great distribution, which means it’s more than good enough for gameplay."
Its distribution is not flawless, but I would agree that it's good enough for gameplay.
Its distribution is not flawless, but I would agree that it's good enough for gameplay.
This! We don't use it for mission-critical crypto or the like. It's there to figure out whether a bot goes left or right. Given the enormous complexity of the League game state and input surface area, it likely won't be a concern unless someone devises a way to exploit it for RNG manipulation (this seems unlikely.)
The reason we didn't use crand was just code ergonomics. C-style rand has global state (by default) and we wanted our own interface to be explicit in the code so you knew when you were using a gameplay-impacting random number.
The reason we didn't use crand was just code ergonomics. C-style rand has global state (by default) and we wanted our own interface to be explicit in the code so you knew when you were using a gameplay-impacting random number.
Likely performance. You can do xor and shift operations essentially for free on a modern pipelined CPU.
Other techniques, such as linear congruential generators, require multiplication and division.
Other techniques, such as linear congruential generators, require multiplication and division.
Besides the other answers, could also be that they wanted to make sure they had their hands on a fully deterministic implementation across different hardware/software stacks (like Windows and OS X).
As a sidenote on a project the size of LoL, the time, size and cost of implementing a PRNG based on a known one is a rounding error.
As a sidenote on a project the size of LoL, the time, size and cost of implementing a PRNG based on a known one is a rounding error.
underscores
I play dota2 because it has a well supported native elf/linux client.
And that even if I live in a country where LOL is, by far, more popular.
And that even if I live in a country where LOL is, by far, more popular.
ryanmcbride(8)
Warcraft III came out in 2002 and was fully deterministic. Save files for entire games with up to 8 players (IIRC?) and huge armies were... Tiny. For they only saved the inputs.
It comes at a surprise to me not that LoL eventually became deterministic but that it wasn't in the first place.
As a funny sidenote, around 1990 / 1991 I wrote a little 2D game and there was a bug I simply couldn't figure out. It'd happen very very rarely. And I realized, by myself, that if I rewrote the game's little physics engine to be 100% deterministic I could just record the inputs while playing and then replay it, hopefully reproducing the crash. It worked. I eventually ended up recording the bug and, sure enough, upon replaying the game would crash: at that point I knew the bug was a goner. It was a dangling pointer in a rare case where the hero had picked an extra allowing to shot two shots at once on screen instead of one and if the player would then finish the level with the first shot gone out of the screen but the second shot still on screen.
I had never heard of anyone using a deterministic engine back in 1990/1991. Fun memories.