How are deterministic games possible in the face of floating-point non-determinism?

Question

To make a game like an RTS networked, I've seen a number of answers here suggest to make the game completely deterministic; then you only have to transfer the users' actions to each other, and lag what's displayed a little bit in order to "lock in" everyone's input before the next frame is rendered. Then things like unit's positions, health, etc. don't need to be constantly updated over the network, because every player's simulation will be exactly the same. I've also heard the same thing suggested for making replays.

However, since floating-point calculations are non-deterministic between machines, or even between different compilations of the same program on the same machine, is this really possible to do? How do we prevent that fact from causing small differences between players (or replays) that ripple throughout the game?

I've heard some people suggest avoiding floating-point numbers altogether and using int to represent the quotient of a fraction, but that doesn't sound practical to me - what if I need to, for example, take the cosine of an angle? Do I seriously need to rewrite an entire math library?

Note that I am mainly interested in C#, which as far as I can tell, has exactly the same problems as C++ in this regard.

Answer 1

Are floating-points deterministic?

I did a lot of reading on this issue a few years back when I wanted to write an RTS using the same lockstep architecture you do.

My conclusions about hardware floating-points were:

• The same native assembly code is most likely deterministic provided you're careful with floating point flags and compiler settings.
• There was one open source RTS project that claimed they got deterministic C/C++ compiles across different compilers using a wrapper library. I didn't verify that claim. (If I recall correctly it was about the STREFLOP library)
• The .net JIT is allowed quite a bit of leeway. In particular it is allowed to use higher accuracy than requires. Also it uses different instruction sets on x86 and AMD64 (I think on x86 it uses the x87, AMD64 it uses some SSE instructions whose behavior differs for denorms).
• Complex instructions (including trigonometric function, exponentials, logarithms) are especially problematic.

I concluded that it's impossible to use the built in floating point types in .net deterministically.

Possible Workarounds

Thus I needed workarounds. I considered:

1. Implement FixedPoint32 in C#. While this is not too hard(I have a half finished implementation) the very small range of values makes it annoying to use. You have to be careful at all times so you neither overflow, nor lose too much precision. In the end I found this not easier than using integers directly.
2. Implement FixedPoint64 in C#. I found this rather hard to do. For some operations intermediate integers of 128bit would be useful. But .net doesn't offer such a type.
3. Use native code for the math operations which is deterministic on one platform. Incurs the overhead of a delegate call on every math operation. Loses ability to run cross platform.
4. Use Decimal. But it's slow, takes a lot of memory and easily throws exceptions (division by 0, overflows). It's very nice for financial use, but no good fit for games.
5. Implement a custom 32 bit floating-point. Sounded rather difficult at first. The lack of a BitScanReverse intrinsic causes a few annoyances when implementing this.

My SoftFloat

Inspired by your post on StackOverflow, I've just started implementing a 32 bit floating-point type in software and the results are promising.

• The memory representation is binary compatible with IEEE floats, so I can reinterpret cast when outputting them to graphics code.
• It supports SubNorms, infinities and NaNs.
• The exact results are not identical to the IEEE results, but that usually doesn't matter for games. In this kind of code it only matters that the result is the same for all users, not that it's accurate to the last digit.
• Performance is decent. A trivial test showed that it can do about 75MFLOPS compared 220-260MFLOPS with float for addition/multiplication(Single thread on a 2.66GHz i3). If anybody has good floating point benchmarks for .net please send them to me, since my current test is very rudimentary.
• Rounding can be improved. Currently it truncates, which roughly corresponds to rounding towards zero.
• It's still very incomplete. Currently division, casts and complex math operations are missing.

If anybody want to contribute tests or improve the code, just contact me, or issue a pull request on github. https://github.com/CodesInChaos/SoftFloat

Other sources of indeterminism

There are also other sources of indeterminism in .net.

• iterating over a Dictionary<TKey,TValue> or HashSet<T> returns the elements in an undefined order.
• object.GetHashCode() differs from run to run.
• The implementation of the built in Random class is unspecified, use your own.
• Multithreading with naive locking leads to reordering and differing results. Be very careful to use threads correctly.
• When WeakReferences lose their target is indeterministic because the GC may run at any time.

Answer 2

The answer to this question is from the link you posted. Specifically you should read the quote from Gas Powered Games:

I work at Gas Powered Games and i can tell you first hand that floating point math is deterministic. You just need the same instruction set and compiler and of course the user’s processor adheres to the IEEE754 standard, which includes all of our PC and 360 customers. The engine that runs DemiGod, Supreme Commander 1 and 2 rely upon the IEEE754 standard. Not to mention probably all other RTS peer to peer games in the market.

And then below that one is this:

If you store replays as controller inputs, they cannot be played back on machines with different CPU architectures, compilers, or optimization settings. In MotoGP, this meant we could not share saved replays between Xbox and PC.

A deterministic game will only be deterministic when using the identically compiled files and run on systems that adhere to the IEEE standards. Cross platform synchronized network simulations or replays will not possible.

Answer 3

I've worked on a number of large titles.

Short answer: It's possible if you're insanely rigorous, but probably not worth it. Unless you're on a fixed architecture (read: console) it's finicky, brittle and comes with a host of secondary problems such as late join.

If you read some of the articles mentioned, you'll note that while you can set the CPU mode there are bizarre cases such as when a print driver switches the CPU mode because it was in the same address space. I had a case where an application was frame-locked to an external device, but a faulty component was causing the CPU to throttle due to heat and report differently in the morning and afternoon, making it in effect a different machine after lunch.

These platform differences are in the silicon, not the software, so to answer your question C# is affected too. Instructions such as fused multiply-add (FMA) vs ADD+MUL change the result because it rounds internally only once instead of twice. C gives you more control to force the CPU to do what you want basically by excluding operations like FMA to make things "standard"--but at the cost of speed. The intrinsics seem to be the most prone to differ. On one project I had to dig out a 150 year old book of acos tables to get values for comparison to determine which CPU was "right". Many CPUs use polynomial approximations for trig functions but not always with the same coefficients.

My recommendation:

Regardless of whether you go integer lock-step or sync, handle the core game mechanics separately from presentation. Make the game play accurate, but don't worry about accuracy in the presentation layer. Also remember you don't need to send all the networked world data at the same frame-rate. You can prioritize your messages. If your simulation is 99.999% matched you won't need to transmit as often to to stay paired. (Cheat prevention aside.)

There's a nice article about Source engine that explains one way to go about sync: Source Multiplayer Networking.

Remember, if you're interested in late join, you're going to have to bite the bullet and sync anyway.

Answer 4

Use fixed point arithmetics. Or choose an authoritative server and have it sync game state once in a while - that's what MMORTS do. (At least, Elements of War works like this. It's written in C# too.) This way, errors do not have a chance to accumulate.

Answer 5

Edit: A link to a fixed point class (Buyer beware! - I haven't used it...)

You could always fall back on fixed point arithmetic. Someone (making an rts, no less) has already done the leg work on stackoverflow.

You will pay a performance penalty, but this may or may not be a problem, as .net will not be especially performant here as it won't use simd instructions. Benchmark!

N.B. Apparently someone at intel appears to have a solution to allow you to use the intel performance primitives library from c#. This may help vectorising fixed point code to compensate for the slower performance.

Answer 6

Note that I am mainly interested in C#, which as far as I can tell, has exactly the same problems as C++ in this regard.

Yes, C# has the same problems as C++. But it also has a lot more.

For example, take this statement from Shawn Hawgraves:

If you store replays as controller inputs, they cannot be played back on machines with different CPU architectures, compilers, or optimization settings.

It's "easy enough" to ensure that this happens in C++. In C#, however, that's going to be a lot harder to deal with. This is thanks to JIT.

What do you suppose would happen if the interpreter ran your code interpreted once, but then JIT'd it the second time? Or maybe it interprets it twice on someone else's machine, but JIT's it after that?

JIT is not deterministic, because you have very little control over it. This is one of the things you give up to use the CLR.

And God help you if one person is using .NET 4.0 to run your game, while someone else is using the Mono CLR (using the .NET libraries of course). Even .NET 4.0 vs. .NET 5.0 could be different. You simply need more control over the low-level details of a platform to guarantee this kind of thing.

You ought to be able to get away with fixed-point math. But that's about it.

Answer 7

I realized after writing this answer that it doesn't actually answer the question, which was specifically about floating-point nondeterminism. But maybe this is helpful to him anyway if he's going to make a networked game in this manner.

Along with the input sharing that you're broadcasting to all players, it can be very useful to create and broadcast a checksum of important game state, such as player positions, health, etc. When processing input, assert that the game state checksums for all remote players are in sync. You are guaranteed to have out of sync (OOS) bugs to fix and this will make it easier - you will have an earlier notice that something's gone wrong (which will help you figure out reproduction steps), and you should be able to add more game state logging in suspect code to allow you to bracket whatever is causing the OOS.

Answer 8

I think the idea from the blog linked to still needs periodic synchronisation to be viable - I've seen enough bugs in networked RTS games which don't take that approach.

Networks are lossy, slow, have latency and might even pollute your data. "Floating point determinism", (which sounds buzzwordy enough to make me skeptical) is the least of your worries in reality... esp if you use a fixed time step. with variable time steps you will need to interpolate between fixed time steps to avoid determinism problems too. I think this is usually what is meant by non-deterministic "floating point" behaviour - just that variable time steps cause integrations to diverge - not anything to do with math libraries or low level functions.

Synchronisation is key though.

Answer 9

You make them deterministic. For a great example, see Dungeon Siege GDC Presentation as to how they made the locations in the world networkable.

Also remember that determinism applies to 'random' events as well!