Registered: Aug 2003
Posts: 712

Readers of the NKS book and of this forum are generally familiar with ordinary CAs. Some here have also encountered ICAs before - the I stands for "interactive", and denotes a "machine with input" form of a CA, in which the rule to be apply on each step is chosen out of some set of rules, according to a global "input" bit for that step. The list of all of these input bits forms an "interaction condition", another kind of "boundary condition" of the system.

A straightforward generalization of ICAs can model strategic interactions dealing with complex systems. The idea is simply to select the underlying CA rule to be used on a given step, according to choices made by several players. Where in ordinary game theory, a matrix specifies payoffs for a given pair of choices by the players, in a SICA or "strategy ICA" the choice pair specifies the CA rule to be used at that step.

One of the less satisfying aspects of traditional game theory is how simple and transparent the world is typically assumed to be, and its tendency to overlook the question of computational difficulty. While stochastic and hidden moves games are sometimes investigated as cases of "imperfect information", usually the pay off results from a particular combination of moves is treated as simple and transparent. This is not the case in realistic games of skill (chess, go e.g.) which feature perfect information in this sense, but are computationally intractable. The joke runs, chess is finite so it is solved, which of course it isn't.

It has always seemed to me that the thing to capture about both real world strategy in complicated situations (and interesting games of strategy), is the complexity of the system or world being "driven" by the interaction of player choices. (Evolutionary and ecological examples are other possible fields to apply this sort of thinking).

In simple cases the immediate consequences of choices can be seen. But to calculate all the long range consequences of arbitrary combinations of choices, in anything but a simple underlying system, rapidly gets difficult enough to be interesting, in a way min-max-ing 2x2 matrices is not. The idea here is basically just to have something more complicated than a pair of integers in the payoff boxes, and see what that does.

The attached notebook gives code to impliment SICAs in Mathematica. I cover the ECAs, 2 color 2D outer totalistic, and 3 color OT and fully general 1D cases. As for actual investigation of their behavior, I give the simplest example - exhaustive search for a best move vector against a given opponent's moves in a given game, then finding a best counter to that. There is plenty to do to investigate them. I hope some find them interesting.

Attachment: sicagamesstripped.nb
This has been downloaded 1642 time(s).

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

The following is the introduction section of the notebook above. I've also included the basic Mathematica code for the simplest example, 2 players and the elementary CAs as underlying rules.


An ordinary cellular automaton (hereafter, CA) is a deterministic system that develops along a single trajectory from any given initial condition. An interactive CA or ICA is a machine with input version of a CA, in which the rule to be applied to the underlying data array can change at each step, among some fixed set of rules, according to an interaction condition or input. This is a global "bit" for that step only. The whole sequence of interactions or interaction vector, can be thought of as another sort of boundary condition for the generalized CA.

Also notice, for certain sets of rules, changing the global bit for a given step can correspond to flipping a bit within the rule table used. All that is needed is to choose the CA rule set for the ICA such that each differs from a base rule in only one position in its rule table. (i.e. It is a "point mutation" in the rule). Thus for example, ECA rule 110 and ECA rule 46 differ only in the second position of their rule table, where 110 has a 1 and 46 has a 0. (Their rule numbers therefore differ by an exact power of 2, in this case by 64=2^6).

An obvious generalization of the ICA set up is to let the interaction bit depend on multiple choices of competing players, reproducing the game theory set up. But instead of a simple and readily analysed matrix of integer pay offs, the interacting choices specify the rule used to update the system. Which in general is difficult to score, predict, or analyse rather than being simple.

In the simplest case, each of two move vectors are combined to produce 4 possible CA rules. The underlying CA can be as simple as the ECAs, or can be something as complicated as a 9 neighbor 2D CA, or what have you. The general case would have N players each with M(i) choices, resulting in M(1) * M(2) *... M(N) possible underlying rules. The underlying rules could all be distinct and unrelated, or contain overlaps, differ only in a few cases, etc. System size and initial condition are also free parameters or "scenarios", for the same underlying game.

This set up specifies how the array will update, but not what counts as a goal for any of the players or how the game is scored. That is an independent parameter. "Drive the system state to, toward, or away from x" is the general form of a goal for any given player. The simplest sort of goals to set are density (count of cells of a certain color) either at some end step or totaled through time. Or one might score regions (3x3 entirely white areas, entirely black areas, or mixed etc). The goals can be set to ensure competition, or can allow cooperation between players, etc.

Compared to the standard game theory set up, the emphasis is on the complexity of the way the system updates, and the players' limited ability to predict the impact of their choices. Some rule combinations may however have clear tendencies. Some choices may be much less powerful than others, in their effect on the underlying evolution. There is no assumed symmetry in the set up.


ruletable[mainrule_, {play1_, play2_}] := 
    With[{original = IntegerDigits[mainrule, 2, 8]}, Map[FromDigits[#, 2] &, 
      {{original, ReplacePart[original, Mod[original[[play1]] + 
    1, 2], play1]}, {ReplacePart[original, Mod[original[[play2]] + 1,
       2], play2],
          
          ReplacePart[ReplacePart[
            original, Mod[original[[play1]] + 1, 2], play1], Mod[original[[play2]] + 1, 2], play2]}} , {2}] ]

gamemat[no_Integer] := ruletable[Floor[no/28],
   KSubsets[Range[8], 2][[(Mod[no, 28]) + 1]]]

SICAStep[gamematrix_, init_, move_] := Last[
    CellularAutomaton[gamematrix[[Sequence @@ (move + 1)]], init, 1]]

SICAEvolve[gamematrix_, init_, moves_] := FoldList[SICAStep[
    gamematrix, #1, #2] &, init, moves]


Sample initial conditions and function calls then look like -


game = gamemat[3080]
    {{110, 238}, {46, 174}}
start = Table[Random[Integer], {30}];
playerone = Table[Random[Integer], {10}]; playertwo = Table[Random[Integer], {10}];
moves = Transpose[{playerone, playertwo}];
data = SICAEvolve[game, start, moves];
ArrayPlot[data]

Report this post to a moderator | IP: Logged