Tony's Home

CellularAutomata

are like

WeiQi

and similar to

FeynmanCheckerboards

which, in 1+1 dimensions, are isomorphicto 1-dimensional

IsingModels

 

CellularAutomata

 and QuantumComputation

A single CELLULAR AUTOMATON STATE configuration is one of all possible initial states.Choice of a particular single configuration is a RANDOM choice.  

In his book A New Kind ofScience, StephenWolfram says (at page 771):

"... In present-day physics the standard mathematical formalism of quantum mechanics is often interpreted as suggesting that quantum systems work like multiway systems, potentially following many paths in parallel. And indeed within the usual formalism one can construct quantum computers that may be able to solve at least a few specific problems exponentially faster than ordinary Turing machines.

But ... I strongly suspect that even if this is formally the case, it will not turn out to be a true representation of ultimate physical reality ...".

I strongly disagree with Wolfram - in my opinion,  

quantum information and quantumgame theory, as expressed in VoDouPhysics, does in fact truly represent ultimate physicalreality.

Since VoDou Physics does in factgive realistic calculatedvalues of particle masses and force strength constants, including theelectromagnetic fine structure constant, I also strongly disagreewith Wolfram when he says, at page 1025:

"... In the past century, the emphasis has been on physical constants such as the fine structure constant ... over the past 20 years or so I [Wolfram] have received a steady stream of mail presenting such notions with varying degrees of obscurity and mysticism. But while I believe that every feature of our universe does indeed come from an ultimate discrete model, I would be very surprised if the values of constants which happen to be easy for us to measure in the end turn out to be given by simple traditional mathematical formulas. ...".

 

About an Ultimate Model for the Universe, Wolfram says, atpages 8, 465, 466, 471:

"... In the future of physics the greatest triumph would undoubtedly be to find a truly fundamental theory for our whole universe. Yet despite occasional optimism, traditional approaches do not make this seem close at hand. But with the methods and intuition that I develop in this book there is I believe finally a serious possibility that such a theory can actually be found. ...

... Ultimate Models for the Universe. ... one of the crucial points discovered in this book is that more complex phenomena do not always require more complex models. And indeed I have shown that even models based on remarkably simple programs can produce behavior that is in a sense arbitrarily complex.

So could this be what happens in the universe? And could it even be that underneath all the complex phenomena we see in physics there lies some simple program which, if run long enough, would reproduce our universe in every detail?

The discovery of such a program would certainly be an exciting event ...

In a sense, the existence of such a program would be the ultimate validation of the idea that human thought can comprehend the construction of the universe. ...

... Given a particular underlying program, it is always in principle possible to work out what it will do just by running it. But for the whole universe, doing this kind of explicit simulation is almost by definition out of the question. ... Small-scale simulation will certainly be possible ... it will be possible to get at least as far as reproducing the known laws of physics ...

... to find the ultimate rule will be a major triumph for science, and a clear demonstration that at least in some direction, human thought has reached the edge of what is possible. ...".

On aQuestion and Answer web page, StephenWolfram says:

"... Cellular automata were what got me started on the science I've developed in A New Kind of Science. And even after all of the things I've studied for A New Kind of Science, cellular automata are still the best examples I know of all sorts of phenomena. ... cellular automata ... probably represent about 20 percent of the examples in the book ...".

On anotherQuestion and Answer web page, StephenWolfram answers questions:

"... Q: What is the picture on the cover of A New Kind of Science?

A: The yellow image is an example of one of the main discoveries of the book. It's an extremely simple computer program&emdash;something called the rule 110 cellular automaton&emdash;that turns out to produce behavior that seems as complicated as anything in our universe. ...

Q: Does A New Kind of Science propose a new fundamental theory of physics?

A: ... I don't yet have a final theory, but I think I've managed to figure out a pretty promising direction to try to find it. What I've done is extremely different from what's been being done in particle physics and field theory and string theory. ... And I'm pretty sure that the framework I describe in A New Kind of Science will actually let one build a truly fundamental theory of physics. ...".

In an interview published in the New Scientist (25August 2001, pages 44-47), Stephen Wolfram was asked by Marcus Chown:

"... Have you discovered the simple program that is generating the Universe? ...",

and Stephen Wolfram replied:

"... Not yet. But I have found increasing evidence that it exists ...".

 

In my opinion,

VoDou Physics is such asimple programthat generates the Universe,

but it is based on quantuminformation and quantum game theoryrather than Wolfram's classical approach.

 


Alexander Schatten (e-mail address:  aschatt@fbch.tuwien.ac.at) has written a Tutorial on Cellular Automata. Schatten says: 

"... if only the left, the right neighbour and the cell itself isconsidered in the rules (r=1), there are 256 possible rulestotally:

 Cellular Automata have been classified by Wolfram into 4 classes: Class 1 - After a finite number of time-steps, going to a unique state           from (nearly) all possible starting conditions.  Class 2 - Usually creating patterns that repeat periodically           or are stable.  They can be seen as a kind of filter.   Class 3 - From nearly all starting conditions,           creating aperiodic chaotic patterns.  Class 4 - more complex behaviour, capable of universal computation.            They show a high level of irreversibility,           and usually die after a finite number of time steps.    Langton has also classified Cellular Automata, using his Lambda parameter, which is the probability that a cell will live to the next generation in time.  As described in The Global Dynamics of Cellular Automata, Santa Fe Institute Reference Volume I, by Andrew Wuensche and Mike Lesser (Addison-Wesley 1992), another parameter, the Z-parameter, is defined as the probability that the next cell of a partial pre-image has a unique value.   For Binary rules, as Z varies from 0 to 1, Lambda varies from 0 to 1/2 and conversely from 1 to 1/2.  To get a simpler comparison between Z and Lambda, you can use another parameter, the Lambda Ratio, which for a binary rule is:   Lambda Ratio  =  2 Lambda  if Lambda is not greater than 1/2, and Lambda Ratio  =  2 (1 - Lambda)  if Lambda is greater than 1/2.  The Lambda Ratio is never smaller than the Z parameter.   Some important characteristics of Cellular Automata are:  array length                                  L maximum pre-maging                            mp maximum period of attractor cycles            mc maximum length of transient trees             ml number of separate basins in the field        nb   Consider mc, ml, and nb:  Since a preponderance of any one will tend to diminish the other two, these three parameters vary together.    Wuensche and Lesser give examples of varying characteristics of 1-dimensional binary nearest neighbor (n=3) Cellular Automata:   Class 1 typically has Z = 0.25,         a lot of ambiguous permutations in the rule table,         mp diverges exponentially with L,         mc, ml, nb are either fixed or vary arithmetically with L.         cycles and transients are short.  Class 2 typically has Z = 0.5,         many basins separated from the uniform attractor,         mp diverges exponentially with L, but less than for Class 1,         mc, ml, nb are either fixed or vary arithmetically with L,         cycles and transients are short.  Class 4 typically has Z = 0.75,         complex behavior,          mp and some combination of mc, ml, nb are finely balanced,         mp diverges by intermediate function of L,         mc, ml, nb diverge by intermediate function of L,         cycles and transients are moderately long.        Class 4 has been called the Edge of Chaos,        the area of universal computation and possible life,        because at lower Z values things are too simple        and at higher Z values things are too chaotic.  Class 3 typically has Z = 1.0,         chaotic behavior,         mp is fixed,         some combination of mc, ml, nb diverges exponentially with L.  As Wuensche and Lesser note, there are some exceptions to the general characterizations.    Stephen Wolfram lists all 256 types of 2-state 1-dimensional Cellular Automata thathave nearest neighbor (3-cell neighborhood) rules. 

TimothyH. Keitt illustrated those256rules, saying:

"... Here's the results for all 1-Dcellular automata (CA) rules. Each block represents 50 time steps(vertically) using an 50 cell array (horizontally). The top line ineach block is a random initial array of 1's (white) and 0's (black).There are 256 possible rules for a 1-D CA with a 3 cell neighborhood.Each rule can be encoded as a binary string and given a numberrepresenting that string. The first rule (upper right [? left?] corner) is 00000000 or rule 0, the second 00000001 or rule 1,the third 00000010 or rule 2, and so on.

This set [shown below] was generated using the same rulesas in the one above.

The only difference is that each array was started with a single"on" cell in the middle. ...".

 

As to which of the 256 rules have Class 4behavior, HaroldMcIntosh said (on a 1996 web page athttp://alife.santafe.edu/alife/topics/cas/ca-faq/classify/classify.html,which web page seems to me to not now (September 2001) be on theweb):

"... It's generally accepted that the following "elementary" (2state, radius 1) rules have typical class IV (or "complex")behaviours, because they feature emergent coherent propagatingstructures (analagous to gliders in Life, but 1-D). These glidersmove and interact on periodic backgrounds; collisions between glidersproduce new gliders.

HaroldMcIntosh went on (on that 1996 web page)to say, further:

"... Wolfram's most important contribution to cellular automataseems to have been his way of looking at automata - first by settingrandom fields loose to see how they evolve, and second,systematically contrasting all the different rules with one another.He may just have been lucky, to have tried this at a time whensuitable computer facilities had just become available. ...

.... Conway's work with Life represented a different approach, inthat "marginal stability" seems to have been his goal, with referenceto the possibility of proving theorems about the evolution, but oncea rule meeting that requirement was found, further development hasmostly been oriented toward exploiting that one single automaton....

... we need to notice that the spatial sequence (1000)*, accordingto Rule 54, has a temporal period of 4 also, and that it is anextremely common feature of well aged configurations.

Besides the regular regions, there are slip lines, where twomicrocells are joined out of phase. Sometimes the interstices arelarger; rarely are they extremely large save as the consequence of aninitial configuration. Holes tend to fill by regular crystallizationat the boundaries, but there is always the chance for aninconsistency as the gap nears completion.

The boundary regions are so conspicuous there is a temptation tothink of them as "particles" moving hither and yon against adisregardable background. Sometimes the movement is considerable andconsistent, suggesting "gliders" although for Rule 54 they tend tostay in place. If Rule 54 particles move, it is more by diffusionthan by having a momentum. There also exists the possibility that theparticles collide, opening several avenues of further evolution. Theymay disappear (pair annihilation), cross over (solitons), or createsome new kind of interstice (particle creation or transmutation).

The scale of the field that is examined tends to influence itsinterpretation, so it should be chosen as large as possible to getthe full effect of the dynamics of imperfections. ...

Some Rules map zero fields into one fields and conversely; theyare necessarily odd numbered rules less than 128. Should there beextended runs or gaps, they will tend to alternate, but withboundaries which can move around. ...".

 

  Some interesting examples of Cellular Automata are forms of the Binomial Triangle sometimes known as the Yang Hui Triangle or the Pascal Triangle, as discussed in the web pages of Andrew Granville, which cover such things as Binomial Triangle patterns modulo prime numbers.  HISTORICAL NOTE:  The Binomial Triangle known to Europeans as Pascal's Triangle was known to the Southern Song Chinese mathematician mathematician Yang Hui (1261 AD).  Here are some references to even earlier discovery of the Binomial Triangle:  1100-1109 AD: Jia Xien states the method of forming the Pascal triangle; the triangle was probably known before his time. (from The Timetables of Science, A. Hellemans and B. Bunch, Simon and Schuster (1988))ca. 1100-1180 AD: As-Samaw'al ibn-Yahya al-Maghribi wrote The Luminous Book on Arithmetic, which contained an illustration of the Binomial Triangle up to order 11. He was he son of a Moroccan Rabbi. He moved to Baghdad and coverted to Islam. He did not claim to have discovered the Binomial Triangle, but to have gotten it from Al-Karaji, who in turn may have gotten it from another source. (from From One to Zero, G. Ifrah, Penguin (1985) English translation of 1981 French book)ca. 300-200 BC: The Jaina mathematician Halayudha has been given credit for discovering the Binomial Triangle by John McLeish (The Story of Numbers, Fawcett Columbine (1991)). McLeish says that it should be called the Meru-Prastera rule.   The Binomial Triangle is a basic structure in Clifford Algebras, such as are used in the D4-D5-E6-E7-E8 VoDou Physics model.   Cellular Automata are related to Ising Models and to Spin Networks.    There are interesting connections between Wei Qi and Cellular Automata. (Wei Qi is sometimes known by its Japanese name, Go.) For instance: "... John Conway first played Life by hand\on a board for the game of Go, using the Go pieces for live cells. ...". Iwo Bialynicki-Birula has formulated Dirac and Weyl equations on a cubic lattice as Quantum Cellular Automata.  Generalized Cellular Automata based on E8 lattices and octonions, using Quantum Computation, might accurately represent the HyperDiamond Feynman Checkerboard picture of the D4-D5-E6-E7-E8 VoDou Physics model.   

QuantumComputation and Cellular Automata

How are the interesting ChaosStructures related to Cellular Automata (such as fractalself-similarity, irreversible chaotic complexity, strange attractors,etc.) affected by using Quantum Computers instead of ClassicalComputers?

Quantum Computation is fundamental in theD4-D5-E6-E7-E8VoDou Physics model, so it is important(in my opinion) to see how Quantum Computation is related to ChaosStructures, which I do not regard as fundamental and do regard asemergent.

It is my view that, if you use QuantumComputation,

I feel that my view is supported by the paperquant-ph/0203062by Terraneo, Georgeot, and Shepelyansky, in which they discusssimulating Strange Attractors on Quantum Computers. They say:

"... the dynamics of many various dissipative systems converges to so-called strange attractors. These objects are characterized by fractal dimensions and chaotic unstable dynamics of individual trajectories. They appear in nature in very different contexts, including applications to turbulence and weather forecast, molecular dynamics, chaotic chemical reactions, multimode solid state lasers and complex dynamics in ecological systems and physiology. The efficient numerical simulation of such dissipative systems can therefore lead to many important practical applications.

Here we study a simple deterministic model where dynamics converges to a strange attractor, and show that it can be efficiently simulated on a quantum computer.

Even if the dynamics on the attractor is unstable, dissipative and irreversible, a realistic quantum computer can simulate it in a reversible way, and, already with 70 qubits, will provide access to new informations unaccessible for modern supercomputers. ...".

 

 


WeiQi

 A single WEI QI STATE configuration is one of all possible states of placement of stones on the board lattice.Choice of a particular single configuration is a CONSCIOUS choice.
What about Wei Qi inHigher Dimensions?
 Some threads from Santa Fe A-Life discuss connections between Wei Qi and Cellular Automata. (Wei Qi is sometimes known by its Japanese name, Go, or by its Korean name, Baduk.)  Wei Qi moves are not made by predetermined rule or at random, but by Conscious Intelligence that:  observes an incomplete state of the board; perceives which more complete states are likely; and makes a move that tends to produce favorable states.   Progress in the Wei Qi game is defined as going from less complete states to more complete states, and NOT by going from earlier in time states to later states.  The objective is defined as producing a more complete state that is more favorable. Here favorable means maximizing the area controlled, or, in Cellular Automata terminology, maximizing the desired basins of attraction by using the move to alter the Cellular Automaton.    The Wei Qi board is not 19x19 lines in a square pattern, but 19x19 lines in a rectangular pattern, suggesting a distinction between the vertical lines and the horizontal lines.   If the vertical lines represent time, and the horizontal lines represent one space dimension, then the entire board might represent (1+1)-dimensional spacetime.   Therefore, the Conscious Intelligence of the Wei Qi player perceives the relevant 19x19 region of spacetime all at once, in its entirety, as a lightcone being lifeform might perceive a region of the spacetime in our universe.  From that perspective, the Wei Qi moves of the Conscious Intelligence would be like a lightcone being making moves at various points of our spacetime to alter its structure so as to maximize the favorable basins of attraction in the ensemble of possible Many-Worlds.    In order to make its move, such a lightcone being might have to interact with a massive spacelike being in order to actually execute the move.  By making its move, and so affecting the Many-Worlds, such a type of lightcone being might be acting as an abstract Many-Worlds being.   This perspective seems to indicate a relationship between Randomness of Cellular Automata, Ising Models, and Sum-Over-Histories Feynman Checkerboards and Consciousness of the Wei Qi player.    The pattern-principles (Li) by which the next Wei Qi move is determined might be represented by the I Ching and the Tai Hsuan Ching as though the I Ching and Tai Hsuan Ching show how to move in Wei Qi. The interactions among the basins of attraction would be in accord with the principles of Zhen-Shan-Ren.      Generalized Wei Qi based on E8 lattices and octonions, using Quantum Computation, might accurately represent the HyperDiamond Feynman Checkerboard picture of the D4-D5-E6-E7-E8 VoDou Physics model.   The Zhou dynasty established its capitol at Xi'an, on the Wei River, and ordered its empire systematically.  For instance, 
land was divided into square frameworks with 9 belts of land surrounding the central capitol.  The resulting pattern is a 19x19 grid of boundary lines, with the capital at the center, and 4 quadrants (SW, SE, NE, NW).  Placement of Qi markers on the intersection points of the grid shows how to establish a good and stable government, and may be an early application of the ancient game Wei-Qi, which has similarities to Cellular Automata, Ising Models,and Feynman Checkerboard physics models, and whose moves might be determinable by the I Ching.  The land in the Wei River valley (or anywhere else) is not flat and square, so that the actual boundaries would not be exactly square.  The Wei-Qi game reflects that by never using an exactly square board.  If the center lines through the capitol are omitted, and the outermost boundary lines are omitted, the Wei-Qi board has four 8x8 quadrants, and can represent the Clifford algebra Cl(0,8). The 19-line Wei-Qi board is similar to the 19-line grid used by the Egyptians for art and architecture. The Mayans may have used a similar grid.  

In the JohnNash biography movie A Beatiful Mind (Universal DVD 2002) whenJohn Nash loses a gameof Wei-Qi as a Princeton mathematics graduate student, he says to hisvictorious opponent:

"... You should not have won. I had the first move. My playwas perfect. ... The game is flawed. ...".

Since the Wei-Qi board is an square array of 381 = 19x19vertices,and since 19 is an odd number, the board has a CENTERvertex. However, just playing the center vertex on the first move andthen mirroring each opposition move thereafter will NOT assurevictory, because, since the 19x19 Wei-Qi board is finite, the centervertex is NOT the only distinguished vertex. ALL of the PERIMETERvertices are also distinguished, and taking the center vertex on thefirst move of the game allows the opposition to have the first movemore directly affecting the perimeter. The only way to avoid thedistinguished perimeter vertices is to have an infinite board or acyclic finite board (for one example, a flat torus), but doing awaywith the distinguished perimeter vertices also does away with thedistinguished nature of a center vertex as well. Wei-Qi on either aninfinite board or a finite cyclic board would be interesting due tothe lack of any distinguished perimeter vertices or centervertex.

Wei-Qi could have begun with a 16x16 pattern corresponding to the 256 elements of IFA and the Cl(8) Clifford Algebra that is the basis of the D4-D5-E6-E7-E8 VoDou Physics model
x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x
The 256 elements are in four 8x8 blocks of 64 elements each. The division into 4 blocks is a natural Clifford Algebra subdivision. Each of the 8x8 blocks of 64 elements looks like the I Ching.Now, add 33 elements of a central row and column to form the 17x17 pattern of 289 elements, the new elements corresponding to the Symmetric Space E6 / Spin(10)xU(1) (and its U(1), marked as o) representing the CL(8) Spinors of the D4-D5-E6-E7-E8 VoDou Physics model. Acccording to Needham (Science and Civilization in China, Cambridge Un. Press, vol. III, page 139) Shen Kua refers to old Wei Qi boards with 17 rows and columns.
x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x o x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x
To get to the 19x19 Wei Qi board, add an outer border of 72 = 17 + 28 + 27 elements,17 of which correspond to the Symmetric Space Spin(10) / Spin(8)xU(1) (and its U(1), marked as o) representing Vectors in the D4-D5-E6-E7-E8 VoDou Physics model,28 of which correspond to the Spin(8) gauge group (whose 4 Cartan Subalgebra elements are marked as o) of the D4-D5-E6-E7-E8 VoDou Physics model, and27 of which correspond to the Complex dimensionality of the Symmetric Space E7 / E6xU(1) (with its 3 rank elements marked as o) representing the MacroSpace of the Super Implicate Order of the D4-D5-E6-E7-E8 VoDou Physics model.
o x x x x x x x x o x x x x x x x x ox x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xo x x x x x x x x o x x x x x x x x ox x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xo x x x x x x x x o x x x x x x x x o
Now we have added a total of 33 + 72 = 105 elements to the original 256, and produced the Wei Qi board with 19x19 = 361 elements.Since 105 = 78 + 27, you can say that78 of the new elements are the 78-real-dimensional Lie group E6 that, in the D4-D5-E6-E7-E8 VoDou Physics model, corresponds to the SpaceTime, Fermions, and Gauge Bosons of one World of the Many-Worlds, and27 of the new elements are the 27-complex-dimensional symmetric space E7 / E6xU(1) that, in the D4-D5-E6-E7-E8 VoDou Physics model, corresponds to the MacroSpace of Many of the Worlds of the Many-Worlds.The 9 elements at the center and the ends of the new rows and columns have been marked with o. They correspond to the total rank of the 105 new elements, sincethe 78-real-dimensional Lie Group E6 has rank 6 andthe 27-complex-dimensional symmetric space E7 / E6xU(1) has rank 3. Therefore, the 19x19 = 361 elements of Wei Qi correspond to:the 256 elements of IFA and Cl(8), made up of four copies of the I Ching;the 78 elements of Tarot and E6, which in turn are made up of
the 28 elements of Spin(8);the 16+1 elements of Spin(10) / Spin(8)xU(1) plus the 1 U(1);the 32+1 elements of E6 / Spin(10)xU(1) plus the U(1);
the 27 elements of the Sri Yantra, the 22 Hebrew Letters plus 5 Finals, and MacroSpace E7 / E6xU(1). Another way to describe the Wei Qi board is to put the 27 MacroSpace elements and the 6 E6 Cartan Subalgebra elements in the 33 inner central row and column spaces, and then put the 72 E6 root vector elements in the 72 outer row and column spaces:
x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x o x x x x x x x x xx x x x x x x x x x x x x x x x x x x

 

 

What about Wei Qi in Higher Dimensions?

In apost to a thread SOC of "Go game" on sci.physics.research,Mitsuhiro Itakura says:

"... I've made a program which simulates "random go game", by tweaking my Monte Carlo code of Ising model. http://www.geocities.co.jp/SiliconValley-SanJose/9606/src/go-mc.tgz It is for UNIX/X11. You can compile it by executing the script "go-mc/mk". The rule of Go is nicely summarized in John Baez's "This Week's Finds in Mathematical Physics (Week 142)" http://math.ucr.edu/home/baez/week142.html In my simulation, the following rule is omitted for simplicity: "First, you are not allowed to put a stone someplace where it will immediately die, *unless* doing so immediately kills one or more of the other player's stones - in which case their stones die, and yours lives." By running the code, you can observe occurrence of large "avalanches" in which a large cluster dies. It is reminiscent of the "sand pile" model which shows self-organized criticality: When a last grain of sand is added and the critical gradient is exceeded, a large scale avalanche occurs. As a result of these avalanches, the configuration becomes very irregular shaped as shown below: http://www.geocities.co.jp/SiliconValley-SanJose/9606/img/go2.gif These avalanches occur when a stone is placed at the last vacant grid inside the cluster. If you forbid these "suicidal" moves, an equilibrium is reached. The following figure shows a resulting configuration: http://www.geocities.co.jp/SiliconValley-SanJose/9606/img/go1.gif You can observe that there is a typical size of clusters. The following figure shows variance of "block spin", namely (number of white - number of black) in a cell of LxL size, normalized by variance of uncorrelated case (=LxL), plotted against various L:
16 ++-------+--------+-------+--------+--------+-------+A    +        +        +       +        +        +        + 14 ++                      A                           ++    |                                             AAA    |    |                      A   A                        A| 12 ++                AA A   A         A    AA          ++    |                     A           A A     A AA   A   | 10 ++           A AAA        A AAA  A     A   A     A  ++    |           A A     A                A    A       AA |    |          A       A            A     A              | 8 ++      AAA               A    A                    ++    |      A                                             | 6 ++    A                                             ++    |    A                                               |    |   A                                                | 4 ++  A                                               ++    |                                                    | 2 ++ A                                                ++    | A                                                  |    +        +        +       +        +        +        +  0 ++-------+--------+-------+--------+--------+-------++    0       10       20      30       40       50       60

It can be seen that it saturates at around L=20, indicating that the typical linear size of clusters is around 20. This result is striking if you remember that the game of go is played on a 19X19 grids board. This finiteness of cluster size is partly because that the critical concentration of site-percolation on a square lattice is approximately 58%, slightly above 50%. If you played Go game on a cubic lattice, the critical concentration of site-percolation is around 30%, so the domain of each player "percolates". The resulting configuration will be two intersecting large clusters with huge genus number, which seems less attractive than the 2D case. ...".

RalphHartley posted:

"... no finite size board gives the same behavior as an infinite board. On an infinite board each point changes color infinitely many times (prove?), but I don't think there is a equilibrium distribution of waiting times. The changes become infinitely clustered, and the clusters get infinitely rare. A fractal hierarchy with no top level. I think 2 dimensions is special for Go. In 1D the it takes a constant number (2) of stones to kill a group, so the behavior should converge to a simple (statistical) equilibrium fairly quickly. In 3D it is easier to "connect" and harder to "cut". There will be infinite groups of both colors, which can never die. Eventually empty spaces become infinitely rare, but stones almost never die, so a given region becomes static. ...

... On an infinite board there isn't even a well defined equilibrium, and time averages may diverge, so it is tricky. ... I took the liberty of playing with your [Mitsuhiro Itakura's] program a bit. My version is at: http://www.aic.nrl.navy.mil/~hartley/go.tar.gz It has an option to implement the suicide rule (which has no qualitative effect). It permits multiple players (which appears to lower the fractal dimension). I was interested in what would happen in 3D with more players. With two players they would both build an infinite group, but with more players connections are harder to make. It turns out that *all* the players make (incipient) infinite groups (after some losses), so 3D is boring even with many (at least up to 8) players. The topology of the board was changed to a torus to eliminate edge effects. Also, it runs much faster. ...".

Iposted:

"... My main comment is that a cubic lattice might not be the most natural higher-dimensional generalization of the 2-D Go board, and that diamond-type lattices (actually technically maybe not lattices, but, as Conway and Sloane say, a 3-D diamond configuration is a packing rather than a lattice, but often I abuse language and call it a lattice anyway) may be the most natural generalization, particularly since in dimensions 1, 2, 4, and 8 they are related to the "integral" (again an abuse of language) versions of division algebras. Here are some pictures by Ishihama Yoshiaki of some 3-D Go "boards" http://www.asahi-net.or.jp/~hq8y-ishm/3dgo/3dgo.html ...

... [Note that a 3-dimensional diamond configuration has 4 (tetrahedral) links from each vertex to a nearest neighbor ...

... octahedral

buckyball

dodecahedral

graphite ...

... just as in 2-dimensions the Wei Qi boark has 4 (square/diamond) links from each vertex to a nearest neighbor. Conway and Sloane (in their book Sphere Packings, Lattices, and Groups, Third Edition, Springer 199) say on page 119:

"... Formally we define Dn+ = Dn u ( [1] + Dn ). ... Dn+ is a lattice packing if and only if n is even. D3+ is the tetrahedral or diamond packing ... and D4+ = Z4. When n = 8 this construction is especially important, the lattice D8+ being known as E8 ...".] ...

... and [here is] a web page with links to some (Macintosh) 3-D Go programs http://www.asahi-net.or.jp/~hq8y-ishm/game.html

and here is a web page about diamond Go http://www.nrinstruments.demon.co.uk/diamond/diamintro.html

and here is a page with a .exe type 3-D Go program http://www.nrinstruments.demon.co.uk/diamond/diamprog.html

I would like to see, but have not seen, 4-D and 8-D programs with hyperdiamond boards, since I think they may be related to generalized Feynman checkerboards and spin networks. ... One more comment is that I prefer the Chinese name Wei-Qi, but I realize that the Japanese term Go is more prevalent in Euro/American circles (and Japan). (In Korea, it is Baduk.) ...".

 

 


Tony's Home

......