Determinism in VideoGames

I would not have guessed that many people would be interested in this subject o_O.
Even though many things already appear here and there in this thread, here's my take on determinism :).

The same way a tomato is a vegetable in a kitchen, and a fruit in a botany lab : the word may mean different things depending on the context :)
One could say that every single (non-quantum) computer algorithm is deterministic. Running the same program twice with the exact same "program inputs" will yield the same "program outputs". "Program inputs" must be read here as a theoretical notion : when the program asks the OS "What time is it ?" or "Have I received some bytes from the network?", that's an input. That's the "theoretical programming" meaning. (This definition is a bit twisted when considering multi-thread programs, but I guess we could consider that all the thread context switching, down to each instruction execution order, can be considered as an "input").
Even with this definition, some deterministic algorithms can feel very random. Hash functions for example, are programs specially crafted to give a completely different output for 2 very close inputs. But for the exact same same input, they will give the same result. A 100% deterministic video-game can feel very random, because very close inputs can give very different results. Some players may use the word "not deterministic" to talk about this, but I think it's best to talk about "chaotic" or "random" to be less confusing.
In the video game world, deterministic most often refers to "deterministic relative to timed user-inputs". Meaning that  if the OS gives the exact same answers regarding user-inputs (=keyboard, controller, etc) and their relative timing, then the result will be the same (for a given level/starting point). Any other info coming from the OS should not influence the result. The computer, or the OS, may not even be the same, this must not matter.
And that's this "robust to change" part that makes it somewhat difficult.

The game physics must never use any external value apart from timed user-inputs. The time the graphics card takes to display must not matter. The order of execution of the different threads, or network exchanges, should not matter. Etc, etc...
You can guess that calling the classic "Rand" function from the physics is a big No No for example xD. (you have to use "seeded" random when needed, with a deterministic seed)
A common way to achieve this is indeed to isolate physics computations from the rest of the engine. This makes "physic frames" independent from everything, including "display frames".
This comes with a bit of added complexity. For example, what if the display is faster than your physics frames (physics at 100FPS, and display can do 144) ? If you display "the latest state computed by the physics engine", it will sometimes print twice the same frame, and this will not be smooth at all. So the physics output state must be something like "At time T, there was a car at pos P, with velocity V". That way, the graphics engine can correct the position a bit, depending of the actual display timing.

But even doing all that may not be enough ! Ex : the number of bits of precision used by the floating-point co-processor on x86 machines could be changed. So different processors could give different results for the exact same multiplication, unless you forced a "standard/compatibility mode". Even worse : if you call an external function from a library in your program, it may set the mode to whatever it wants. So after some library calls, you have to reset this. Also applies to OS libraries. Tons of fun to debug xD. IIRC it's less of a pain since x64.

Also, nothing prevent a multiplayer game (with collisions/interactions) to be deterministic. Shootmania is. It means you have to be careful when transferring user-inputs, but if they are all using a common reference time, you are good to go.
The advantages have already been listed here, but it includes :
Easier to make an anti-cheat, because given the initial state and the timed user-inputs, any computer can check if the physics were altered. As many surely know, this don't prevent all ways of cheating, because "time" is still part of the input. It helps in having a rollback-based network. It also helps during development to detect if the game physics, or map blocs, change by mistake.
The cons are : it cost a bit more CPU (ex : the display extrapolation using Velocity I explained earlier), and you get into a whole world of trouble if your physics engine can not keep up the pace with the clock time. The only way out is to "slow down" the physics (= the world goes slomo). But you can't do that in multiplayer for example. That can be tough to maintain. I guess that's why it's not very common.

Note that determinism is not a requirement to have replay files. TM replay files have both the user-inputs and a "stream of positions". The user-inputs are useful because the game is deterministic, but the stream of positions could work the same without. Without a stream of positions, you would not be able to scroll quickly in the MediaTracker, because everything would have to be re-computed from start (if I'm not mistaken, it works that way for Starcraft(2) of Heroes of the Storm replay files, which is a pain).
Also note that you could have "varying conditions" (ex weather, NPCS/AI/Bots) and still be deterministic. You can add the seed you use for all your "random" physics phenomenon along with your user-inputs. Share the seed in multiplayer. Etc..
Sorry for the wall of text... T_T... When I started I was thinking "I'll just answer a few questions" xD