Enumerating Three-Glider Collisions

For scripts to aid with computation or simulation in cellular automata.
User avatar
Hdjensofjfnen
Posts: 1742
Joined: March 15th, 2016, 6:41 pm
Location: re^jθ

Re: Enumerating Three-Glider Collisions

Post by Hdjensofjfnen » July 22nd, 2018, 7:52 pm

What about this?

Code: Select all

x = 24, y = 13, rule = B3/S23
7bo14bo$8bo14bo$6b3o12b3o3$4b2o13b2o$5b2o13b2o$4bo14bo2$2o$b2o12b2o$o
15b2o$15bo!

Code: Select all

x = 5, y = 9, rule = B3-jqr/S01c2-in3
3bo$4bo$o2bo$2o2$2o$o2bo$4bo$3bo!

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

carsoncheng
Posts: 470
Joined: June 11th, 2022, 11:24 pm

Re: Enumerating Three-Glider Collisions

Post by carsoncheng » July 23rd, 2022, 8:52 pm

There has been some discussion yesterday on the wiki talk page of "3-glider collisions" (https://conwaylife.com/wiki/Talk:3-glider_collision), and I would like to ask some of those questions about the 3-glider database on the forums.

1.
GUYTU6J wrote:
July 23rd, 2022, 12:21 pm
After recognizing subtleties in interactions, an enumeration was done by 2718281828 in late 2017; the resulting database contains 464745 entries and has been used widely since then. However, many entries are practically duplicated results up to rotation, reflection and evolution, so the total number should not be cited as a precise count. No attempt to reproduce the result, verify exhaustiveness, purge duplicates or adaption to new organization has been made for the data.
Is this statement true?

2. Regarding the completeness of the database:
GUYTU6J wrote:
July 23rd, 2022, 10:04 am
I cannot see a substantiated proof that the enumeration of "interesting" results is complete. (Dvgrn used "fairly", which is not guarantee.)
Is this statement true?
Last edited by carsoncheng on July 23rd, 2022, 8:56 pm, edited 1 time in total.

hotdogPi
Posts: 1586
Joined: August 12th, 2020, 8:22 pm

Re: Enumerating Three-Glider Collisions

Post by hotdogPi » July 23rd, 2022, 8:55 pm

I remember a number that's around 190,000, which I believe is the list with the duplicates removed.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576

S: SKOP
G: gun

carsoncheng
Posts: 470
Joined: June 11th, 2022, 11:24 pm

Re: Enumerating Three-Glider Collisions

Post by carsoncheng » July 23rd, 2022, 8:58 pm

hotdogPi wrote:
July 23rd, 2022, 8:55 pm
I remember a number that's around 190,000, which I believe is the list with the duplicates removed.
Could you access the script which is used to remove duplicates? If so, the result can be reproduced and added to LifeWiki.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » July 25th, 2022, 2:40 pm

It's also not at all guaranteed that 2718281828's enumeration has at least one entry for every glider collision that should be considered unique. Didn't someone find a 3G collision in the last year or two, with output that didn't show up in a synthesise-patt.py or synth-const-4G.py search?

There are certainly examples like this one that aren't represented in the current 3G databases. The example there seems like it's definitely a "non-trivial" example, because the initial two-glider explosion interacts at T=439 with the secondary explosion in the northeast an output glider plus the third glider.

If you keep moving the third glider northward two steps at a time, I think pretty soon you'll get to where you always get the same population, just with the two blobs of ash at different distances from each other. Maybe all of those collisions, with Blob1+[Blob2 at some distance away], should count as a single 3G collision. But until that point is reached, it seems like each 3G crash might possibly be a source of novelty.

User avatar
EvinZL
Posts: 847
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

Re: Enumerating Three-Glider Collisions

Post by EvinZL » August 11th, 2022, 2:12 pm

dvgrn and I were briefly talking about on Discord how we should build a 3g collision search that uses octohashes to determine matches.

To do so, you would:
  1. Download https://github.com/dvgrn/octohash
  2. Replace 12x12-1G-octohash/collisions-for-fingerprints-12x12-455380.txt by https://github.com/dvgrn/glider-collisi ... es.txt.bz2 (after unzipping)
  3. Fix the paths in 12x12-1G-octohash/fingerprint-Python3.py
  4. Run 12x12-1G-octohash/fingerprint-Python3.py in Golly
  5. Find out why it isn't working
  6. Define fingerprintfile in 12x12-1G-octohash/split-octohash-file.py
  7. Replace 45538 by 46475
  8. Run 12x12-1G-octohash/split-octohash-file.py
  9. Fix paths in 12x12-1G-octohash/find-octohash-Python3.py
  10. Use octohash
Unfortunatedly, I couldn't do step 5.

NOTE to dvgrn: I did use the correct file
Last edited by EvinZL on August 11th, 2022, 2:33 pm, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » August 11th, 2022, 2:26 pm

EvinZL wrote:
August 11th, 2022, 2:12 pm
dvgrn and I were briefly talking about on Discord how we should build a 3g collision search that uses octohashes to determine matches.
...
Unfortunatedly, I couldn't do step 5.
This looks like a very good start. But in step 2 you linked to colseqs.txt.bz2, whereas I think you'd need to be using rles.txt.bz2 -- right?

Might that have anything to do with the step-5 stumbling block? I haven't tried to look any farther at what kind of specific formatting the fingerprint-Python3.py script might be expecting -- maybe there's some adjustment needed there.

The general idea is that it's going to be necessary to re-generate the colseqs.txt file and make it a lot bigger, using 10-character octohashes (9 characters with a space delimiter, encoding the first 7 bytes of SHA256 hash) -- instead of the single-byte population-based hashes that are in there at the moment.

Side note: it might be a good idea to use the hash-generating code from the octo3obj project, instead of from the octohash project. I already don't remember the details, but I'm pretty sure there was some annoying reason why the generating code wasn't exactly the same...!

Side side note: there are still very much faster ways of calculating these kinds of hashes, via lifelib for example, without losing the nice feature of the search script remaining Golly Python only with no dependency on lifelib. But it's more complicated and the required code is not already lying around waiting to be used... and the plan EvinZL has posted should work fine, just needing an overnight run instead of just an hour or two.

EDIT 8/15/2022: Sounds like the "octo3g" hash-recording process is complete, so now the results are being uploaded somewhere. (?)

User avatar
EvinZL
Posts: 847
Joined: November 8th, 2018, 4:15 pm
Location: A tungsten pool travelling towards the sun
Contact:

Re: Enumerating Three-Glider Collisions

Post by EvinZL » August 15th, 2022, 3:47 pm

It is, indeed, complete. The files can be found at https://drive.google.com/drive/folders/ ... sp=sharing. Warning: there are 20 octohash files instead of 10.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » August 16th, 2022, 4:04 pm

EvinZL wrote:
August 15th, 2022, 3:47 pm
It is, indeed, complete. The files can be found at https://drive.google.com/drive/folders/ ... sp=sharing. Warning: there are 20 octohash files instead of 10.
It took me a while to figure out that the old octohash hash-generating code was used to generate the hash files, instead of the new octo3obj function. It was probably a bad idea for me to ever allow there to be two different versions of that function, but I remember having some kind of reasonable reason at the time.

Anyway, here's a script that works for me to look through EvinZL's new 3g-collision hash files. This means, for example, that I can find out that there are 54 "vanish collisions" in the 3g database that have a final obo$obo! spark, but only three collisions that end with a final o2bo$o2bo!

Code: Select all

# find-octo3g.py
# Dave Greene, 15 August 2022 (Golly Python3)
######## Download hash files from https://drive.google.com/drive/folders/1l6TQEgNpXpFd6ATU7Tgrf7k-76MJcVi3
######## Then update line 10 below with your chosen location for the downloaded files

import golly as g
import hashlib


basepath = "C:/path/to/3g/hashes/"  ###### UPDATE THIS TO MATCH YOUR DOWNLOAD LOCATION

searchfiles = "octohashes3g_0.txt,octohashes3g_1.txt,octohashes3g_2.txt,octohashes3g_3.txt,octohashes3g_4.txt," + \
              "octohashes3g_5.txt,octohashes3g_6.txt,octohashes3g_7.txt,octohashes3g_8.txt,octohashes3g_9.txt," + \
              "octohashes3g_10.txt,octohashes3g_11.txt,octohashes3g_12.txt,octohashes3g_13.txt,octohashes3g_14.txt," + \
              "octohashes3g_15.txt,octohashes3g_16.txt,octohashes3g_17.txt,octohashes3g_18.txt,octohashes3g_19.txt"
searchlist = searchfiles.split(",")

NUMLINES = 464746

chardict = {}
for i in range(37, 127):
  chardict[i-37] = chr(i)

chardict[92-37] = "!"  # backslash
chardict[39-37] = "#"  # apostrophe
chardict[44-37] = "$"  # comma

def get9char(inputstr):
  h = hashlib.sha1()
  h.update(inputstr.encode())
  i = 0  # convert first seven bytes of SHA1 digest to an integer
  for char in h.digest()[:7]:
    i = i*256 + char
  s = ""
  while len(s)<9:
    d = i//90
    r = i - d*90
    s = chardict[r] + s
    i = (i - r) // 90   
  return s

def getoctohash(clist):
  ptr = 0
  g.new("Octotest"+str(count))
  for orientation in [[1,0,0,1],[0,-1,1,0],[-1,0,0,-1],[0,1,-1,0],[-1,0,0,1],[1,0,0,-1],[0,1,1,0],[0,-1,-1,0]]:
    g.putcells(clist,ptr*2048,0,*orientation)
    ptr += 1
  for j in range(8):
    g.select([2048*j-1024,-1024,2048,2048])
    g.shrink()
    r = g.getselrect()
    if r == []: r = [0,0,1,1]
    pat = g.getcells(r)
    deltax, deltay = 0, 0
    if pat != []:
      deltax, deltay = -pat[0], -pat[1]
    if j==0:
      minstr = str(g.transform(pat, deltax, deltay))
    else:
      strpat = str(g.transform(pat, deltax, deltay))
      if  strpat < minstr:
        minstr = strpat
  return " " + get9char(minstr)

g.setalgo("HashLife")
g.setrule("B3/S23")

try:
  g.fitsel()
except:
  pass
r = g.getselrect()
if r==[]:
  r = g.getrect()
  if r==[0]:
    g.exit("No pattern found to search for.")
  g.select(r)

count = NUMLINES
outptr = 0
pat = g.getcells(r)

g.addlayer()  # do tests in a new layer, then put results there
hash = getoctohash(pat)
g.new("Output")
g.putcells(pat,-pat[0]-128,-pat[1])
g.fit()
g.update()

for fingerprintfile in searchlist:
  with open(basepath+fingerprintfile, "r") as f:
    for line in f:
      count -= 1
      if hash in line:
        matchingpat = line[:line.index(" ")]
        g.putcells(g.parse(matchingpat),outptr*64,0)
        outptr+=1
        g.fit()
        g.update()
      if count % 1000 == 0:
        g.show("Searching.  Lines remaining: " + str(count/1000) + "K lines.")
plural = "" if outptr==1 else "s"
g.show("Found " + str(outptr) + " line" + plural + " matching " + hash + " in " + str(NUMLINES) + " lines of the octo3obj database.")
The old synthesise-patt.py either gives no results at all, or lots of false positives, in any case like this where a recognizable population sequence can't be generated for the target pattern -- so this is a huge improvement on what we had before.

EDIT: Created a octo3g git repo for the above code. The current download location for the roughly one gigabyte of hash files is given in the script comments. Many of the individual files are over GitHub's "warning level" of 50MB, so I'm not too inclined to attempt to check in such oversized files into the repo at the moment. Maybe if they were split into a total of 37 or so files of less than 30MB each, it might be worth it? -- along with adding octohash files for the 4G collisions used by synth-const-4G-Python3.py.

That last item should be pretty easy, so I'll probably take care of that in the next week or so if nobody else gets to it first.

We still definitely need versions of these octo* search scripts, that mark where the output pattern is in each search result, and rotate/reflect each search result so they're all in the same orientation and lined up, and maybe (optionally?) show the full LifeHistory reaction envelope as well. That's really not a particularly painful programming effort, though it will be slow for cases where thousands of results are being displayed, so we might need an option to turn off that reorienting/post-processing functionality.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: Enumerating Three-Glider Collisions

Post by GUYTU6J » September 30th, 2022, 4:15 am

So, how to summarize the full process of octo3g database generation starting from scratch? Is it like
  1. Generate a list two-glider collisions in gencols;
  2. Observe their evolution and decide some parameters for complete enumeration of interesting collisions;
  3. Generate a list of three-glider collisions in gencols;
  4. Process the list to give each entry a unique octohash identifier;
  5. Remove duplicate entries in the list to finish a database;
  6. Write a script to search for entries upon user request;
  7. Pack the database and script and publish.
?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Enumerating Three-Glider Collisions

Post by dvgrn » September 30th, 2022, 12:21 pm

GUYTU6J wrote:
September 30th, 2022, 4:15 am
So, how to summarize the full process of octo3g database generation starting from scratch? Is it like
  1. Generate a list two-glider collisions in gencols;
  2. Observe their evolution and decide some parameters for complete enumeration of interesting collisions;
  3. Generate a list of three-glider collisions in gencols;
  4. Process the list to give each entry a unique octohash identifier;
  5. Remove duplicate entries in the list to finish a database;
  6. Write a script to search for entries upon user request;
  7. Pack the database and script and publish.
?
That's more or less it. Here's the Quibbles 'N' Caveats List:

1) The first three steps above have only ever been done by 2718281828, back in October 2017. Nobody has done the work since then to cross-check that list.
2) The original work was apparently done semi-manually, resulting in quite a few duplications though it's not a big proportion of the 3G database. If you start with a two-glider collision and add all possible third gliders, among the results you'll end up with some exact matches with each of the other two-glider collisions with all possible third gliders added.
3) The fourth and fifth steps above were never actually done, except by wildmyron in converting a small subset of 3G and 4G collisions (the ones that produce useful constellations) to Shinjuku format, which makes it trivial to weed out duplicates.
4) The use of gencols is not a requirement: for a really good independent cross-check, it might be better to write some custom code to enumerate collisions of a third glider with all possible phases of each two-glider collision, recording the apgcode or octohash value of the 2G-collision active pattern at the tick before the first collision with the third glider. That way, when we were done, we could confidently record which 2G collisions allow for a complete enumeration of all unique third gliders interacting with them.

For the 2G collisions that produce gliders and can't be completely enumerated, at least we could record exactly how many ticks we went out from the initial 2G collision, to build our 3G-Version-2.0 database. None of that information is available for the 3G-Version-1.0 database, so we really have no idea how much might have been missed.

BokaBB
Posts: 2973
Joined: December 30th, 2019, 11:55 am
Location: Serbia

Re: Enumerating Three-Glider Collisions

Post by BokaBB » February 6th, 2023, 3:07 pm

This reminds me of Gustavo's old conspiracy theory about some Morse code transmissions. I think it claimed an universal constructor could be made with 385 gliders or so. Who knows, if there are this many 3-glider collisions and the number keeps rising at a similar speed that seems potentially plausible to me.
Good morning/afternoon/evening/night and sweet dreams!
Enjoy your life and all the best! May THE LORD help you!
Have a suuuuperior day (and this all also to your own)!

BokaBB
777
I CAN APGSEARCH NOW!


Sure, I was a bad person, but I have changed myself.
I'd love to befriend anybody who's interested.
Have a good day!

BokaBB

Post Reply