Post subject: What actually breaks determinism?
Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
This appears to be quite important for us (if not even critical). But what kind of beast is it in fact? How much do we know of it, can we teach others to fight it? I mean, we now have guides for effectively every matter related to TASing:
  • The process of TASing
  • Making Lua tools
  • Dealing with RNG
  • Debugging
  • Emulator tools required for TASing
  • Guidelines on movie file
  • Guidelines on savestates
So if one wants to TAS a game on some new platform, he can learn everything it takes to make it possible, from the lowest level, except... making it deterministic! Our experts surely have an idea of how to find causes of non-determinism and fix them, and that means they must be able to tell something about it, then we could make up a list of things to look into in general cases of simply movies not syncing, and possibly even some more interesting ones too. I'm not asking to figure out why some things still desync, if it's yet not known. For complicated platforms it may be too much heavy lifting. But I believe 15 year old hardware is predictable enough to fall into at least one of the known desync causes. So what emulator authors (or hackers) should get rid of, in hopes to make their system TASable?
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Dimon12321
He/Him
Active player (478)
Joined: 4/5/2014
Posts: 1120
Location: Ukraine
Honestly, I don't fully understand the meaning of this topic, although I have read it several times. Let's not go into such terms, because "determinism" has lots of meaning! What about desyncing: let's discuss! Desync usually happens when: 1. Emulator wrongly reads the input. Universal ROMs can be read by countries with different FPS (PAL and NTSC). If TAS was recorded on 60 FPS, it will desync on 50. Obviously! 2. Emulator wrongly writes the input. TASVideos won't accept the emulator that does this! A great example is PCSX2-rr! Obviously! 3. The game itself causes desyncs. Bullshit! But I heard that lots of games aren't well emulated with Mupen 64 in my rejected Doom 64 discussion topic. Now we have Bizhawk which is now preferred for TASing N64, right? 4. A wrong input or useless frames were made in TAS Editor. Obviously! I don't know what seems to be the problem! All emulators work well. I think we just need to finalize some emulators for a comfortable TASing.
TASing is like making a film: only the best takes are shown in the final movie.
Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
Dimon12321: I mean that kind of determinism an emulated system core must guarantee to a TASer.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Dimon12321
He/Him
Active player (478)
Joined: 4/5/2014
Posts: 1120
Location: Ukraine
feos wrote:
Dimon12321: I mean that kind of determinism an emulated system core must guarantee to a TASer.
Hah!
TASing is like making a film: only the best takes are shown in the final movie.
Joined: 7/2/2007
Posts: 3960
This is going to be pretty vague since I'm not an expert on the topic, but it seems clear to me that the following things will result in nondeterministic behavior: * Variable starting state. If the system doesn't start out the same every time then you can't guarantee that the inputs you make will result in the same results. We've had discussions about the state of uninitialized RAM in FCEUX, for example. * Nondeterministic behaviors in the emulator itself. Seems obvious, but e.g. if your emulator decides to imitate, say, disc loading times by deciding randomly how long each seek operation takes, then that emulator won't behave consistently. More realistically, emulators that take advantage of multiple cores are going to be problematic on this front, because the host system (i.e. the computer the emulator is running on) has to schedule tasks on each core in what is effectively a nondeterministic manner, which in turn means that you can't predict when each task will finish or whether certain operations will happen before other operations in a consistent fashion. * Incomplete savestates, or bugs in saving/loading states. If savestates don't capture all the state of the system, then when you load the state, you aren't perfectly restoring the system to the way it was when you made the state. This is similar to the "variable starting state" issue -- the aspects of the system that the savestate doesn't cover will be in an unpredictable state which will cause desyncs.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
ars4326
He/Him
Experienced player (763)
Joined: 12/8/2012
Posts: 706
Location: Missouri, USA
In my experiences using Gens, I encountered occasional desyncs when I would try to quickly reload savestates when using speed throttle. I'm guessing that all of the rapid calculations going on may have had something to do with it. When using Bizhawk, I had one case of repeated desyncs when working on my Dungeons and Dragons: WOTES run. In this case, when replaying the movie file from the beginning, the whole thing would desync about a minute and a half in. I was able to easily fix this by deleting all of the game's save RAM in the Genesis folder, however.
"But as it is written, Eye hath not seen, nor ear heard, neither have entered into the heart of man, the things which God hath prepared for them that love him." - 1 Corinthians 2:9
Patashu
He/Him
Joined: 10/2/2005
Posts: 3999
Self-modifying games. Besides things like saving to memory cards or saving to an internal storage, or Windows games modifying files/save data in their own directory, some arcade-games are actually self-modifying - for example, the first time you open Raiden Fighters Jet in MAME, it shows a 999 second countdown while it performs some operation - and when it finishes, every time you open the game again, even if you completely close and re-open MAME, it never happens again, because the ROM itself has been edited. This is an extreme example, but demonstrates the point.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
creaothceann
He/Him
Editor
Joined: 4/7/2005
Posts: 1874
Location: Germany
I'm pretty sure you can't modify ROM, only RAM...
Patashu
He/Him
Joined: 10/2/2005
Posts: 3999
creaothceann wrote:
I'm pretty sure you can't modify ROM, only RAM...
Try it yourself sometime. It modifies itself permanently, even if you close and re-open MAME.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Active player (303)
Joined: 8/21/2012
Posts: 429
Location: France
A very simple answer to what can cause desyncs and break determinism: a glitch in the emulator. I had FCEUX add resets in the movie file for no apparent reason and very rarely. At least it was very easy to know exactly where it happened in the movie and to fix it.
Skilled player (1703)
Joined: 9/17/2009
Posts: 4952
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
Well, not sure why, but: [1584] NES Action 52: The Cheetahmen "warps" by SwordlessLink in 03:56.06
Important: The version labeled (Rev A) has to be used in order to get the movie to sync. However, before playing back the movie, make sure that you select "Ooze".
Stuff like that can affect movie sync.
Player (96)
Joined: 12/12/2013
Posts: 376
Location: Russia
Also, easy answer to "how to make it deterministic" Just remove any sources of entropy! :D It might sounds complicated, but it easy.
Patashu
He/Him
Joined: 10/2/2005
Posts: 3999
r57shell wrote:
Also, easy answer to "how to make it deterministic" Just remove any sources of entropy! :D It might sounds complicated, but it easy.
*The entire universe grinds to a screeching halt* Finally! Now I can get some real TASing done.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Samsara
She/They
Expert player, Senior Judge, Site Admin (2120)
Joined: 11/13/2006
Posts: 2792
Location: Northern California
r57shell wrote:
Also, easy answer to "how to make it deterministic" Just remove any sources of entropy! :D It might sounds complicated, but it easy.
Oh snap, we just got schooled by an extremely condescending narcissist.
TASvideos Admin and acting Senior Judge 💙 | Cohost
warmCabin wrote:
You shouldn't need a degree in computer science to get into this hobby.
Patashu
He/Him
Joined: 10/2/2005
Posts: 3999
Samsara wrote:
r57shell wrote:
Also, easy answer to "how to make it deterministic" Just remove any sources of entropy! :D It might sounds complicated, but it easy.
Oh snap, we just got schooled by an extremely condescending narcissist.
No need to be harsh, I thought it was in good humour.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
creaothceann
He/Him
Editor
Joined: 4/7/2005
Posts: 1874
Location: Germany
Samsara wrote:
condescending narcissist
???
Site Admin, Skilled player (1234)
Joined: 4/17/2010
Posts: 11251
Location: RU
r57shell wrote:
Also, easy answer to "how to make it deterministic" Just remove any sources of entropy! :D It might sounds complicated, but it easy.
Can you be more specific? Is it possible to read the core's code and say with some certainty what is going to introduce that entropy? For a skilled coder it must be so, so please share some thoughts. Trying it by hand for each possible condition isn't efficient you know.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Player (96)
Joined: 12/12/2013
Posts: 376
Location: Russia
Language: c

const int A = <some>; // no entropy const int B = <some>; // no entropy int seed = 0; // no entropy int rand() { seed = A*seed + B; // A, B, seed - no entropy -> new seed - no entropy return seed; } // so this func deterministic void main () { seed = time(0); // time(0) - source of entropy, so seed isn't deterministic. for (int i=0; i<10; ++i) printf("rand() = %d\n", rand()); // there will be 10 random numbers but! if you know first, you can easily determine all 9 after. } // so if you set seed to some certain value in main, you'll get deterministic program. it will run always same.
List of some sources of entropy: 1) Time, timers, delays, elapsed time between some two points in program. 2) Threads execution order, it can't be same, unless if you syncronize all with appropriate methods (mutexes, events etc.) 3) Program base address (where it was loaded), current stack pointer :D, addresses of memory allocated in heap... 4) User input: keys down, keys up, mouse movements... 5) OS events: WM_MESSAGES, hmmm something else :) 6) Polling stuff: socket recieve packets, socket send packet, sound in poll mode (is there space for next sound samples?)... 7) Special random devices that produces REAL RANDOM! You can expand this list forever. But when it comes to emulators, you may restrict your emulator core from accessing to all this stuff except user input. So your emulator must have only two methods: 1) advance time (emulate frame / emulate miliseconds ...) 2) change current user input (for rerecording) and restrict from any other external input that may have entropy :), also restrict frontend from changing any data used by core. Use "encapsulation" method :). Question: how then I'll show image and play sound if it produce entropy? Answer: yes it produce entropy, but as far as you don't access it from core: (advance time method) you can use it, because while you didn't call time advance methods, state does not change.