ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

French student trying to work on GoL

For general discussion about Conway's Game of Life.

French student trying to work on GoL

Postby Minos » June 19th, 2013, 2:18 pm

Hello,
As the titles shows, I'm a French student (so please excuse my poor grammar), age 18. I have to work on a project for next year, on a subject of my choice linked to physics or maths. After some researches, i've found that Game of Life seems pretty interesting to chose as a subject. The problem is this work needs a "personnal contribution", so I thought of programming some scripts related to Game of Life, but my knwoledge in programming is very low (I only know some Java), and I don't know if I would manage to fulfill my goals.
So let's come to the point : could you tell me hwo complicated the algorithms to search patterns (that's the point I'm the most interested in) are, and if you think it is possible for a programming novice ta manage to write one simple, basic one ? And what is the most suitable language ?
I would also appreciate some links explaining those algorithms, or the theories behind them, if such exist.

Thank you
Minos
 
Posts: 2
Joined: June 19th, 2013, 2:03 pm

Re: French student trying to work on GoL

Postby dvgrn » June 20th, 2013, 6:58 am

Minos wrote:... could you tell me [how] complicated the algorithms to search patterns (that's the point I'm the most interested in) are, and if you think it is possible for a programming novice to manage to write one simple, basic one ? And what is the most suitable language ?

If you're interested in "simple and basic", and you're working with Golly, then the language of choice is probably Python. Some programmers prefer Perl, but from my experience there's a steeper learning curve there for a beginner. A Python script won't win any prizes for speed, but depending on what you're looking for that may not be a problem.

Here's an example of a search problem that came up for me a few weeks back: the conjecture was that "no 2xN pattern, for finite n, can 'touch' every cell in the plane if left to run indefinitely".

I wrote a Python script to find the pieces I needed for a counterexample -- see below. Maybe you can judge from this whether Golly scripting is something you want to tackle. The short summary is that there are certainly still new results that are within easy reach of simple searches, if you pick your topic carefully.

For the counterexample, I wanted to show that it was possible to glider-construct something like Dean Hickerson's total-periodic or total-aperiodic pattern (see Golly's Patterns/Hashlife/totalperiodic.mc) by crashing together pairs of gliders that were generated indirectly from a 2xN starting pattern.

Hickerson's Life-integer investigations showed that it's possible to construct arbitrarily complex objects from a one-dimensional line of spaceships -- see Golly's Scripts/Python/life-integer-gun30.py . So the first thing to find out was whether 2xN patterns can actually create clean spaceships.

If multiple types and/or phases of spaceships were available, they could probably be crashed together to make as many gliders as might be needed. It's very convenient, though possibly not strictly necessary, to be able to generate gliders with at least two different phases. I didn't make any attempt to come up with the actual glider collisions needed to build Hickerson's total-aperiodic or some equivalent -- that's a fairly minor engineering problem, just very time-consuming.

So I just got to where I could see that a 2xN pattern can construct anything that a Gemini replicator unit can construct... But that's all getting a bit too far from this topic, I think! I stopped running the script when it had produced the following:

x = 165, y = 2, rule = Life
o6b3obo5bo5b3obo5bo4b3obo20b2ob8o2b2ob8o16bo4b3obo3bo4b3obo7bob3o4bo
11b8ob2o$b6ob3o7b5ob3o7b4ob3o23b2o3b2o6b2o3b2o19b4ob3o5b4ob3o9b3ob4o
14b2o3b2o!

There were a few more finds -- clean lightweight spaceships at 436729, 436731, 456361, 612087, and 980649, before the odd-phase ones finally showed up at 1496565 and 1562085. A clean MWSS output showed up at 1526447. There were also quite a few false positives, like the "dirty" LWSS outputs at 1378651 and 1504623.

The 2xN MWSS and HWSS recipes shown at left in the above pattern were not found by searching -- I just tried extending the original LWSS recipe by one cell, and it worked...!

Here's what the script looked like by the time it found what I needed:
import golly as g

c=1 # edit this number to restart a search after stopping the script --
    # I didn't search much past 1562085
g.setrule("Life")
while c:
  g.new("test")
  x,y,d=0,-1,c
  while 1:
    y+=1
    if y>1:
      x+=1
      y=0
    if d:
      state=d%2
      d=(d-state)/2        # convert integer d to binary,
      g.setcell(x,y,state) # and turn on its ON bits in a two-cell-high strip
    else:
      break
  g.run(1024)
  p=int(g.getpop())
 
  if p>0 and p<100: # has to be something there after 1024 ticks, but not too much
    r=g.getrect()
    g.run(4)
    s=g.getrect() # see if the pattern is still moving
    if r[1]==s[1] and r[3]==s[3]:  # no change in location or width in y direction
      if r[0]!=s[0] or r[2]!=s[2]: # change in location or absolute width in x direction
        g.fit()
        g.update()
        g.note(str(c) +": Next?")
  c+=2 # only look at every other pattern
         # (eventually a reflected/rotated copy of every skipped pattern will be tested)
  if c%100==1:
    g.show(str(c))
    g.update()

I also copied the first part of the code into a separate short script to translate input integers into 2xN patterns. That way I could just write down interesting results as they went by without stopping the search script, and regenerate the patterns later:

import golly as g

s=g.getstring("Enter integer to see its equivalent 2xN pattern:")
c=int(s)
g.setrule("LifeHistory")
g.new("test")
x,y,d=0,-1,c
while 1:
  y+=1
  if y>1:
    x+=1
    y=0
  if d:
    state=d%2
    d=(d-state)/2
    g.setcell(x,y,state)
  else:
    break

It would have been much more elegant to dump the results to a file, or output them to a new layer in Golly, or in general do everything in a more user-friendly way. But that wasn't the point. I got the search results that I needed, not very efficiently in terms of CPU time but with very minimal programming effort.

I don't think I used any code that would be beyond the reach of a novice... but let me know if you have any questions!
User avatar
dvgrn
Moderator
 
Posts: 5743
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: French student trying to work on GoL

Postby Minos » June 25th, 2013, 4:23 pm

Thanks for your answer !
It gave me some ideas for a future work, but the first thing i have to do is learning python, though it doesn't seem to be really hard.
My lack of knowledge in this language prevent me to fully understand your whole script, but I think I caught the main ideas.
Thank you again, i'll make some researches and post again if I have some question.
Minos
 
Posts: 2
Joined: June 19th, 2013, 2:03 pm

Re: French student trying to work on GoL

Postby codeholic » July 5th, 2013, 3:14 pm

Another idea for a master thesis or simply an article for a journal could be a program, that would generate a slow salvo recipe out of a glider synthesis. :roll: That would be a real bridge between the large knowledge base of glider syntheses and spartan universal constructor technology.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests