with Overview of Game Of Life
This exploration is inspired by the following paper:
"Asynchronism Induces Second Order Phase Transitions in Elementary Cellular Automata" by Nazim A. Fatès, Journal of Cellular Automata (2008)
http://hal.inria.fr/inria-00138051
So what is happening here? Well as we saw in the description of conway life above, what we do is start out with a pattern on a grid. Then for each cell in the grid we think of what the next generation of that cell will be depending on what its immediate neighbors are. We do this for the whole grid before replacing all the cells with their next generation computations. This is called synchronous, since we compute all the cells at once each time.
But real life isn't much like this! In chemistry, or biology, particles interact higgledy piggledy, real cells often react to each other at random times. So what if we rewrite our Conway Life simulator so that we only recompute a differewnt random bunch cells each time? This is What Fates did. In each generation he picked say, 10% of the cells at random and recomputed them. He got something that looked nothing like conway life. after all, think out computing a blinker. If you just compute one of the end cells, without computing the other end and the two side cells, all at once, you won't make it blink, you will just kill the end cell, leaving just two live cells left. this will eventually die. No blinker. The patterns in Conway Life depend on every part of the pattern being carefully calculated at once.
So we realize, lets just compute a FEW cells out of synchony and see what happens. Most of the patterns grow like conway patterns and just some few spots of chaos ensue. What if we keep executing runs of Conway Life with the percentage of cells that we compute synchronously to be less and less than 100%? more and more chaos should happen, right?
So: On the right hand side of the images are the usual runs of conway life from a random scattering of half cells on and half off, after a certain number of generations it settles down to the usual low density (about 0.01 live cells) scattering of beeloaves and blinkers and such. For this particular experiment we actually run it on a torus, that is.. if a glider flies off the right hand side, it reappears on the left, and if it flies off the top, it reappears on the bottom. the space is actually the surface of a donut! (you may ask where the hole is... I'm gonna have to explain that won't i?)
Anyway, as we go towards the left, the % of cells we calculate synchronously drops slowly and more chaos happens. some curious things though:
Because there is more chaos, and the usual still lives and blinkers can't stabilize, things stay in flux a lot longer than usual and the density of cells that are changing begins to rise as the % asynchronous drops. At 95% synchronous things usually settle quickl By 90% synchronous things take a long time to settle if at all, and the density begins to rise and things don't look quite conway lifey. By the time %synchronous drops to about .4 another curious thing happens: the density settles at about .4 to .45 and doesn't rise any higher. Also the pattern becomes a stable dynamic labyrinth shape you see on the left most pictures.
So we get two kinds of transitions, one from stable mostly motionless sparse conway life to nonstable fluid patterns around 90% synchrony and then by around 40% synchrony we get a stable fluid labyrinth state of density .4. Fates reports slightly different results but we may be using different algorithms.
Also, Fate reports what he claims is a phase transition rather sharply at around 90%, which is very curious. Phase transitions are of course wha makes the universe interesting. A similar thing happens to water as you raise the temperature continuously, you go suddenly from solid ice to fluid water and then suddenly again to expandable steam.
I have more to do on this topic!!!
For those of you who want to see my code, here it is in python. I use sets of live and neighboring coordinate pairs instead of calculating the whole NxN matrix. (this optimization is good for sparse conway life but not so much for asynchronous labyrinth pattern!)
grph2 is a silly plotting package i wrote. you just need something that opens up a canvas and plots points in x,y.
import grph2
import random as r
def async_conway(N,M,pat,gens,px,alpha,delay):
"""async_conway(pat,lim,px,tx,ty,alpha) --
run async conway on pat,up to lim gens, tx,ty is torus dims
alpha is percent of cells to update each gen
compile averate density =len(live_cells)/tx*ty and
activity which is numcells to change in a gen/tx*ty"""
canv=grph2.Grph(tx,ty,px,'conway torus '+str(tx)+'X'+str(ty)+
'alpha= '+str(alpha))
tot=N*M
live_cells=center(pat,N)
canv.gens=grph2.k.Label(canv.win)
canv.gens.pack()
canv.density=grph2.k.Label(canv.win)
canv.density.pack()
canv.activity=grph2.k.Label(canv.win)
canv.activity.pack()
adjacent_empties=calc_adjacent_empties(live_cells,tor=True,N,M)
display(live_cells,canv)
pop=len(live_cells); active=0
for n in xrange(gens):
for m in xrange(delay): pass
canv.gens.config(text=str(n))
canv.density.config(text=str(float(pop)/tot))
canv.activity.config(text=str(float(active)/tot))
pop,active=async_conway_gen(live_cells, adjacent_empties, canv,
tx,ty,alpha,pop,active)
def async_conway_gen(live_cells, adjacent_empties, canv, tx,ty,alpha,
pop, active):
"""update the conway world one generation
alpha is the percent of cells at random to update syncronously
update pop =len(live), active=numcells chg"""
die=[]; born=[]; erase=[]
for cell in live_cells:
if r.random()
#so num nbs is 0,1,4 or more
die.append(cell); canv.unput(*cell);
pop-=1; active+=1
for cell in adjacent_empties:
if r.random()
if c==3:
born.append(cell); canv.put(*cell);
pop+=1; active+=1
elif c==0:
#the cell is no longer adjacent to a live cell
#take it out of the adjacent_empties set
erase.append(cell)
#THIS IS A LITTLE FUNNY ASYNC. WE MIGHT WANT TO UPDATE ***ALL***
#THE EMPTIES. THINK IT OUT.
canv.upd()
adjacent_empties-=set(erase)
live_cells.update(born)
adjacent_empties-=set(born)
for cell in born:
adjacent_empties.update(set(nbs(tor,tx,ty, *cell))-live_cells)
adjacent_empties.update(die)
live_cells-=set(die)
return pop,activity
def nbs(tor,tx,ty, x,y):
"""nbs(tor,tx,ty,x,y) -- lazily return one neighbor at a time
if tor=True then calculate mod tx, ty
can be extended to cylinder or klein bottl"""
if tor:
yield((x-1)%ty,(y-1)%ty); yield(x,(y-1)%ty);
yield((x+1)%tx,(y-1)%ty)
yield((x-1)%ty,y); yield((x+1)%tx,y)
yield((x-1)%ty,(y+1)%ty); yield(x,(y+1)%ty)
yield((x+1)%tx,(y+1)%ty)
else:
yield(x-1,y-1); yield(x,y-1); yield(x+1,y-1)
yield(x-1,y); yield(x+1,y)
yield(x-1,y+1); yield(x,y+1); yield(x+1,y+1)
def conway_calc(live_cells,tor,tx,ty,x,y):
"""add up the number of neighbors of (x,y) that are live
stop when you get to 4 cause 5,6,7,8 is the same"""
sm=0
for nb in nbs(tor,tx,ty, x,y):
sm+=nb in live_cells
if sm==4:
break
return sm
def calc_adjacent_empties(cells,tor,tx,ty):
adjacent_empties=set([])
for cell in cells:
adjacent_empties.update(set(nbs(tor,tx,ty, *cell))-cells)
return adjacent_empties
def display(live_cells,canv):
for cell in live_cells:
canv.plot(*cell)
def center(pat,N,M=None):
if M==None: M=N
cx=N//2; cy=M//2
xmin, xmax, ymin, ymax=lims(pat)
xmid=(xmax+xmin)//2
ymid=(ymax+ymin)//2
return set([(x-xmid+cx,y-ymid+cy) for x,y in pat])
def lims(pat):
"""return xmin,xmax,ymin,ymax of points in pat"""
xmax=xmin=pat[0][0]
ymax=ymin=pat[0][1]
for x,y in pat[1:]:
xmax=max(xmax,x); xmin=min(xmin,x)
ymax=max(ymax,y); ymin=min(ymin,y)
return xmin, xmax, ymin, ymax
No comments:
Post a Comment