05-22-2016 at 02:14 PM
Part 2 - Ghost Behaviour - Meaning of Deterministic vs Non-DeterministicDeterministic:
"A deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.Given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.
A deterministic algorithm, for example, if given the same input information will always produce the same output information."
"Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this
means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined."
A nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.
A nondeterministic algorithm is an algorithm that:
if it uses external state other than the input: a) such as user input b) a global variable c) a software or hardware timer value d) a random value generator e) uses values randomly stored in memory.
If it operates in a way that is timing-sensitive, for example if it has multiple processors or processes writing to the same data at the same time. In this case, the precise order in which each processor or process writes its data will affect the result. If a software or hardware overflow error causes its state to change in an
The Ultimate History of Video Games: from Pong to Pokemon and beyond..
by David Marofske
"Pac-man preset paths [which means it is Deterministic], by running certain patterns, players were able to confuse them and play near indefinitely. There are no set patterns to fool ghosts in Ms. Pac-Man [which means it is Non-deterministic]"