Indeterminacy, Pt. 2

[Argh]

Ok, as seen by my questions in regards to this issue, plus KDR_11k's problems re: replays, indeterminate results in Spring can "corrupt" replays, by causing events to no longer adhere to the previously-established "reality".

After thinking on this a bit, I have a fairly simple solution:

When Spring is running, and a math.random is called within a sync script, whatever number is "rolled" should be stored, and printed into the savegame format, with a break character, indicating what was "rolled".

Then, when the savegame is replayed, any time the engine hits a math.random, it should insert the next saved "roll", until it runs out've numbers, or players give any orders, or use any cheat commands other than .spectate. I.E., anything that passes back into the indeterminate realm again, due to people starting a game in the middle, invoking .godmode and ordering a unit around, etc., should then put the game back into "indeterminate" mode from that frame thereafter. Should be fairly easy to do, but has the unfortunate side-effect of bloating the replays further.

I think that should solve the indeterminacy problem. Anybody see any glaring problems with this logic?

[FLOZi]

I would imagine if something can desync a replay, it can desync a game...

[lurker]

How about the fact that math.random is already determinate, and if the problem is with it then it's a 1-5 line fix.

[Argh]

I would imagine if something can desync a replay, it can desync a game...

Nope. What happens, FLOZi, is that people "roll" different results when the replay starts. The replay only records the state / line of the LUA operating in the virtual machine... not the outcome of math.random. Therefore, each replay ends up being completely different, and insta-breaks.

How about the fact that math.random is already determinate, and if the problem is with it then it's a 1-5 line fix.

math.random is only determinate within that game state, so far as I can tell. IOW, it's not "random" once it's rolled up the results, during the game- all clients share that result. So, when everybody's in sync, it works just fine. Where it breaks stuff is when you revisit the game again. It's like you're watching a Shrodinger's Cat, basically- you don't know the state of math.random until you observe it again.

[Peet]

You're overcomplicating it ridiculously. If there is an issue, it's simply a matter of the seed not being stored.

[Argh]

If it's just a seed, and the seed value determines all sub-values of math.random, great, even easier! I assumed it was getting a new seed each time, to keep itself truly random, but if not, and that seed can then be used to generate the exact same results again, great.

If it's using the same seed all the time, though... that leads to some very uncomfortable thoughts. How can you design an AD&D simulation where the possibility that you roll a natural 20 every time you swing your sword is pre-determined, and no matter how many times you swing, it will always result in a 2?

[lurker]

Each game has a new seed. This seed is all you need to get every math.random for the entire game. You have no idea what you're talking about; spend 5 minutes looking at wikipedia before you make a huge post on a topic.

[Argh]

<sigh> Ok, I'll read this before commenting further. At any rate, my comment of "save the seed, hurrah problem solved" still seems like an accurate description of a solution to me

[lurker]

I didn't mean that part. This is a better example:

math.random is only determinate within that game state, so far as I can tell. IOW, it's not "random" once it's rolled up the results, during the game- all clients share that result. So, when everybody's in sync, it works just fine. Where it breaks stuff is when you revisit the game again. It's like you're watching a Shrodinger's Cat, basically- you don't know the state of math.random until you observe it again.

[Argh]

But, that's the truth, so far as I can tell, anyhow. The seed must be indeterminate, or this wouldn't be happening.

Look, now that I've read up on PRNGs... what they do is use a seed, probably based on the game's identity string. Great, ok. That results in whatever period, n2 - 1, yay, we have a "random number". All clients are told what the seed is, so they all pick the same result as the host.

I find this strange, btw. Why not just have the host tell the clients the result, instead of informing them that math.random just ran again? Why is the LUA doing gamestate stuff even running, on clients, and using CPU, when it's the results that matter, not the logic that created them? I mean, that's how FPS servers handle indeterminacy, as a former Counter-Strike player, I can tell ya that events in your POV have very little or nothing to do with what the server's doing...

Therefore, when math.random runs, and is given a different game identity string, or a different seed, voila, broken gamestate. Or is there something "obvious" I'm missing here, people? Heck, I don't even care, frankly- it's still broken, and if it's a quickie fix, so much the better, I just haven't the foggiest how the replay format works

[Peet]

Why not have the host calculate everything and send it all to each client? That's how the FPSes do it, so it would obviously work for spring.

[lurker]

But, that's the truth, so far as I can tell, anyhow. The seed must be indeterminate, or this wouldn't be happening.

It's not a matter of the seed being determinate, it's possibly a matter of using the wrong one. And I don't see how that is at all the same as what I quoted in the post above.


As for the rest of your post, Spring sends the orders given, and an occasional checksum to make sure people are in sync. Having to send all the random numbers would take a lot of bandwidth.

[Argh]

It's not a matter of the seed being determinate, it's possibly a matter of using the wrong one. And I don't see how that is at all the same as what I quoted in the post above.

The easiest way to see if it's truly indeterminate or is "just wrong" would be to write a script... here...

Code: Select all

function gadget:GetInfo()
   return {
      name = "Random Verifier",
      desc = "Verifies integrity of math.random within replays.",
      author = "Argh",
      date = "",
      license = "GPL, v.2 or later, 2008",
      layer = 1,
      enabled = true,
   }
end

if (gadgetHandler:IsSyncedCode()) then
--------------------------------------------------------------------------------
--  SYNCED
--------------------------------------------------------------------------------
function gadget:GameFrame(f)

if f > 0 and f < 5 then

local Random = math.random (1,20000)
Spring.Echo ("First Iteration",Random)
local Random2 = math.random (1,20000)
Spring.Echo ("Second Iteration",Random,Random2)
end

if (f == 5) then Spring.Echo("Removing Randomizer Gadget") gadgetHandler.RemoveGadget("Random Verifier")  end

end
end

Just run that once. Then bring up the replay, and see what you get. Bring up the replay again, see if it matches the first replay... Simple as that...

[Argh]

Having to send all the random numbers would take a lot of bandwidth.

You're quite right. I keep having this dim memory of somebody saying StarCraft wasn't sync'd, though, so I wonder how they got around all of this. I'm probably just horribly mistaken.

Why not have the host calculate everything and send it all to each client? That's how the FPSes do it, so it would obviously work for spring.

Why not have all players calculate everything every frame, whether or not it makes sense? Oh, wait...

[Argh]

Ok, here's my test (I'll update the script, above).

First results, "live":

First Iteration, 19781
Second Iteration, 19781, 9843
First Iteration, 14030
Second Iteration, 14030, 18346
First Iteration, 6126
Second Iteration, 6126, 8308

Second results, "Replay Running 1"

First Iteration, 19781
Second Iteration, 19781, 9843
First Iteration, 14030
Second Iteration, 14030, 18346
First Iteration, 6126
Second Iteration, 6126, 8308

Hmm. It's exactly the same. So, that ain't it, the seeds must be matching exactly... back to the drawing board.

[lurker]

Why not have all players calculate everything every frame, whether or not it makes sense? Oh, wait...

Uhhh, what does everyone calculate that isn't needed?

[Argh]

<shrugs> If I'm even going to bother discussing that side-issue, which is pretty much off the rails of this thread anyhow, I should go do some homework and see what's been done. I don't see any point in this, tbh, as I'm not qualified for the giant rewrite that would be involved, even if there was a demonstrably "better" way anyhow. For now, assume you're right.

Just like I assumed that the desync is being caused by indeterminacy, which my experiment seemed to prove is not the case, unless there's another source of indeterminacy within LUA that I'm not aware of... maybe on the unsync'd side? Surely, that's using the same seed, though?

KDR's users were reporting that it was occuring because of events surrounding the area-attack code, which is primarily based on indeterminate events... hmm...

[KDR_11k]

Spring already has synced random number generation for all kinds of things (weapon inaccuracies, CEGs, COB, ...). Instead of writing pages upon pages you could just have said "The Lua synced random generator is faulty!" and possibly posted that to Mantis instead of here.

[tombom]

Before writing up pages on a solution to a problem, make sure the problem actually exists.

[Kloot]

The synced code handler already replaces the RNG in Lua's math
table (math.random()) by its own function (SyncedRandom()) that
relies on Spring's synced RNG (gs->rand*()), there is no separate
Lua SRNG.