A non-deterministic binary combination system based on player name

[sethmachine]

Hi,

I would like to develop a non-deterministic binary combination system.

A deterministic binary combination system is much like a DFA (deterministic finite state automaton).

Given inputs A, B, it will always output C.

Notation: (A,B) --> C

A non-deterministic one, on the other hand, attaches weights to the productions of every combination.

Give inputs A, B, it will output C with probability p (a real value 0-1)
(A,B) ~~> C_p

The probability of not getting C (denoted as ^C) is thus

(A,B) ~~> ^C_(1 - p).

Additional stipulations:

(i) No empty combinations: for every input pair (X, Y) there exists some output Z.

(ii) Ordering: For every input pair (X,Y) with output Z, it is not necessarily true that (Y,X) also has output Z.

(iii) Vector effect: For every pair member X, there is a real vector assigned to it which can vary between different X's. The values of the vector influence the output of a combination.

(iv) Preservation: For every pair (X,Y) where X == Y, the output will always be X, except in a few borderline cases where the real vector of either pairs might influence the product.

(v) Genetic distance: For every pair member X, there can be output Z which is impossible to produce (e.g. no matter what Y we pair with X, we can never get Z, or has a near zero probability).

(vi) Name effect: For all possible combinations (X,Y), all the probability arcs are influenced in some (non-)deterministic fashion based on an input string (which is really an integer).

Thus, the system of combinations assigned to name "JACK" will not be the same as a system of combinations assigned to name "FRED," even though the set of all pairs/outputs are the same.

The purpose of (vi) is to prevent information sharing and also create a unique experience--just because (X,Y) --> Z for "JACK" does not necessarily mean it will do the same for "FRED", or at least the probability varies.



There are some more stipulations, but I guess I would like help in getting started. In a brute force solution, I imagine if I have n objects, I would have to define n^2 combinations.

 

[frettory]

Math - Random is probably what you are looking for.

Handles might come in handy too (they can convert strings/units into numbers).

P.S. What are you using this for?

 

[Dr Super Good]

What would the purpose of this system be?

I mean non-deterministic stuff has very limited usability. Generally people just use RandomInt and such low-deterministic functions.

For a save/load system it is completely, totally and utterly useless as everything must be deterministic.

 

[sethmachine]

I mean non-deterministic stuff has very limited usability

I may be conflating non-determinism and randomness.

This should summarize it from the OP:

What would the purpose of this system be?

The purpose of (vi) is to prevent information sharing and also create a unique experience

It's about making user content unique for each user.

For a save/load system it is completely, totally and utterly useless as everything must be deterministic

This is not true. What made you think this had anything to do with a save/load system?

In my case I'd have at most 200 unique objects (thus potentially 200^2 combinations to define). That takes 8 bits to give each object a unique number? The combinations themselves are part of the map code, and do not need to be saved, only the product.

 

[Dr Super Good]

This is not true.

It is true. Data is worthless unless it is deterministic as otherwise it is not really data... When data is not fully deterministic due to external influences like errors there exists means of detecting this and either fixing it or flagging up an error. What determines the amount of data needed to store information is the determinism of the information, with truly non deterministic (random) sequence of bits being uncompressible and requiring the sequence length of bits to store.

What made you think this had anything to do with a save/load system?

Was struggling to see what on earth you would use such a system for... Still it is true that save/load systems have to be deterministic as they would not be very useful if you were given random stuff when loading.

It's about making user content unique for each user.

So you want it purely as an alternative form of randomness that has deterministic probability distribution based on user account name?

In WC3 there are only 3 non-deterministic sources you can safely use.
1. The obvious Random Integer function. The seed is defined by the session host I believe so is almost certainly different between sessions.
2. The user themselves. No one can truly predict what the users will do during a session and that by itself can be considered non deterministic. Unless you are a robot or that one guy who did input perfect play for NES punchout you can consider user input as being different from session to session (not deterministic).
3. You can use the host (host robot) to introduce external non-deterministic sources. As long as the commands the host robot synchronizes are not deterministic, they will introduce a form of non-deterministic state into the deterministic state of the session. The session must be deterministic across all clients so introducing non-deterministic behaviour has to be synchronized (host robot signals and player orders as well as initial seed) or derived from the deterministic state (what calling random does).

The biggest problem is computers by nature are deterministic. If you give a program the same inputs it will produce the same outputs (unless a hardware error occurs). A few attempts have been made at creating non deterministic random sources (useful for security) but this is very specialized hardware and certainly not used by Warcraft III.

This means that to get anything that is not deterministic (does not always produce the same results for the same input) you will have to use some form of randomness as mentioned above. This will form the starting point of your solution.

I have little idea about the requirements you have as they are too low level. I assume X and Y are meant to be characters, in which case a hashing algorithm is a good start. A hashing algorithm is deterministic (has to be) but has the property of producing an output with little relationship to the input. This has many of the properties you desire (order dependence, sharing outputs etc) so is another good place to start. Conveniently there is a built in native to do this but you may want to write your own for maybe better characteristics as the default implementation is aimed at speed.

It should be noted that players can freely change the casing of their Warcraft III user name. This means that a hidden requirement is that for every capital alphabetic character there exists a small case version which is equivalent in value. This means that someone with username "FrEd123" should produce the same results as someone with the username of "fReD123" as they represent the same account. Again the standard hash implementation is good for this as it treats upper and lower case as the same value.

The simplest approach would be a Gaussian probability distribution centred around a number derived from the hash of the user name. This would make it more likely to produce numbers within a certain range (bandwidth) that varies depending on user name. So that all values have a probability the Gaussian can be squashed to the full range of available numbers. The result will be players will have a very high chance of a result within a small range and a much lower chance of results opposite of this small range (assume the integer wraps around the maximum number of combinations required).

If you want a random series from this, you can use the results for a seed for the normal random integer function. Just remember to change the seed before use, save it after using and then restore the game seed back to avoid strange random behaviours.

 

[sethmachine]

It is true. Data is worthless unless it is deterministic as otherwise it is not really data…

I meant to refer to non-determinism in the context of the results of combinations of objects, and not non-deterministic data being stored in a load/save system.

I will attempt to give a concrete example that is high level enough.

First consider Alchemy. In Alchemy there are two types of objects: ingredients and potions. Ingredients combine to make a single potion.

We will now add the following properties / inviolable constraints to the Alchemy being considered.

(i) Binary combinations: It takes exactly two ingredients to produce a potion. A single ingredient cannot be turned into a potion, and likewise three or more ingredients cannot be combined to produce a single potion.

(ii) Recursion: The product of a combination of ingredients is also an ingredient. Thus the set of all Ingredients I describes the exact same set as the set of all Potions P.

(iii) Non-gradience: Ingredients can be represented as discrete values, i.e. integers.

(iv) Identity: The combination of two of the same ingredients results in the product which is that ingredient, i.e. (X,X) --> X

(v) Asymmetry: The order in which ingredients are combined does not always result in the same potion, i.e. (X,Y) !~= (Y, X)--which means the combination of ingredients X,Y does not necessarily create the same potion if we instead changed the order of combination to Y,X.

(vi) Completeness: All possible combinations of ingredients create some potion. That is, there are no two ingredients which cannot combine to produce some potion.

(vii) Determinism: The function F that maps combinations of ingredients to potions is one-to-one/bijective.

(viii) Universality: For all Alchemists, the function F is always the same--if one Alchemist discovered that (X,Y) --> Z, then any other Alchemist who combines X,Y will also produce the potion Z.

With these stipulations, defining the mapping between ingredients and potions is trivial--though there will still be |I|^2 combinations with |I|, thanks to (iii).

The system I described is essentially what is used in games like Elder Scrolls or Runescape for the Alchemy / Herbelore Skill, except for (vi), because not every combination of ingredients in those games can actually be made into a potion, and (v) (though I forget if (v) is true in Skyrim).

In any case, this system is exactly what I am not trying to create. The biggest problem with these kinds of Alchemy is the fact that an Alchemist need not have to discover combinations on their own (risking ingredients) and can rather simply copy the feats of other Alchemists who have documented known combinations. This ultimately kills creativity, since at some point all combinations will be documented. Barring academic concerns, I would want to deny Alchemists the discoveries of other Alchemists and force them to discover them on their own. To do this, the Alchemy needs to get a bit more complicated.

We will replace these stipulations:

(vii) Determinism, (viii) Universality with

(vii) Non-determinism: The product of (X,Y) is determined by a real weight assigned to each of their possible products, representing a probability. For simplicity, suppose these weights are simply real values ranging over [0,1] and further more the sum of all these weights for a given combination (X,Y) must be exactly 1.

(viii) Locality: The negation of Universality, in particular, if Alchemist A discovers that (X,Y) --> Z with probability of 40%, it is not necessarily the case that Alchemist B will also observe that (X,Y) --> Z with probability 40%--it could be 70%, 27.2525%, or even 0%!

Note that the Locality stipulation is itself vague. In a very general case, we might just randomize the weights based off of the name of the Alchemist. But the problem with this approach is that we basically destroy any illusion of semantics/meaning to combinations, thus Alchemists might as well combine ingredients at random, which again eliminates creativity.

Thus we will need to enforce an additional stipulation:

(ix) Locality Distance: According to some function of the weights of each combination AND/OR some function of the ingredients, all Alchemists must stay within some value of this function (e.g. the average of the weights might be one function).

To avoid complicating things, we will keep our ingredients gradient (integer valued).

I hope this explains what I am trying to do in a higher level description.

 

[Dr Super Good]

So what was the problem with the solution I described? The input type?