arr28
commented
9 years ago This is very similar to the thinking I was doing about IntNets or RegNets or whatever they were going to be called - essentially allowing integer state variables alongside boolean state variables.
They would also capture things like the number of stones in a pit for Kalaha, whether a cell was red/black/empty in C4, etc. and no doubt many other things.
In your notes above, you cover the "easy" part of how to deal with the output of the integer state variable (although in practise, it would be a considerably upheaval). However, there's also the problem of how to set the variable. What do you feed in? For step counters, an edge-triggered increment would be ideal - but that severely limits applicability. What other operations should be provided? Set to a particular value presumably - but how is that encoded?
If we've got more than 1 integer variable, that also opens up the possibility of other operations (addition, etc.). I did have this all thought out at one point, but I can't find any note of it, so I'll make a few more notes here.
Considering the propnet as a circuit diagram with basic logical operators, the intnet has all the same, but...
- The lines connecting the components come in two types, defining the type of data they carry (either boolean as currently or integer).
- There are components for converting between the two data types
- Something like your Multiplex, but maybe tweaked a little
- Greater than, Less than, etc.
- New components which act on integers (with addition being the obvious one here, but easy to add more if we spotted games that would benefit from them).
- Integer constants
Then there's the problem of analysing the rules to determine which of the new components can usefully be inserted in place of a large block of pure propnet.
Many games contains base props, some subset of which themselves represent elements of a set such that only 1 member of that set (one proposition) can be true at once. The commonest case is the subset of 'step' propositions in most games. That is it is an invariant of the game state (for reachable states) that exactly one of the set: (true (step 1)) (true (step 2)) ... (true (step N)) will be true.
This generalizes to arbitrary sets, but is readily detected for sequences by (fairly easy) rule analysis.
Given such a set of propositions (which I'll refer to using the name of the base prop sentence, upper cased just for terminology, so 'STEP' here) we can then look for relations in the GDL that include expressions of the form:
(and (true (step ?x)) expr)
(the 'and' will be implicit in actual GDL, but included above for clarity.
During propnet production this would expand to a set of instances of And component with inputs from (step n) and expr (one And for each member of STEP).
Suppose we replaced the grounded base props of STEP in our state representation with an int (which is simply an index over the set values ?x which (step ?x) grounds out over). We could then replace all the instances of And generated by the grounding of STEP with a single new component, which I'll call Multiplex, which takes a boolean input (from the output component representing expr) and an integer input (representing the value of step in the current state, and therefore encoding the family of (step ?x) propositions). This component has N outputs (one for each grounding of step) ordered by the index of ground values of ?x (i.e. - the integer input). All outputs propagate false apart from the one indexed by the current value of the integer input, which propagates the value of the boolean input.,
A trivial mechanical use of this component, wherein the boolean input is tied to TRUE, acts as a converter of the new state representation to recover the base props we would have had before and feed them into the propnet, That is sufficient to act as an adapter with the potential to represent the state more efficiently.
However, it's much more interesting to think about what happens when we generate propnets for rules that include a conjunction of (step ?x) with something else. Consider the GDL for Hex. This includes the following:
(<= (next (connected ?k ?m ?n)) (transfer ?e) (true (connected ?e ?m ?n)) (true (step ?k)))
which has the form:
(<= (A ?k) (expr) (true (step ?k)))
This means it can be realized in the propnet as a Multiplex component instead of 81 And components (or logic involving 81 And components at least until transformations are applied). Doing this would mean that the fan-out of the output component of (expr) would be reduced 81-fold, which translates as replacing a loop over 81 outputs during propagation with selecting a single output by direct indexing. The resulting network would also be much smaller.
Sequences of this type are very common (step counters, capture counters, resource counters of various sorts), so such a technique might have quite wide applicability.