An update to Andrew's search-rule.lua:
The main changes are to generate a small soup in a larger grid and to allow symmetric soups to be searched. The search is able to find most of the small ships in Bays' 2006 paper with appropriate rule and symmetry settings. Adjustment of the soup_size and soup_range parameters is required in some cases in order to find the ships in a reasonable time. It will also find various 3D4,7/5,8 photons, including the 10c/10 if D2_+2 symmetry is used.
Oscillators and spaceships have different minimum period parameters so it is possible to avoid frequently finding common oscillators whilst searching for low period spaceships. I'm not sure what effect grid size has on the search but I typically use a size between 30-50.
Code: Select all
-- This script must be run from within 3D.lua.
-- It searches the current rule for oscillators and spaceships.
-- Author: Andrew Trevorrow (andrew@trevorrow.com), May 2018.
-- Contributor(s): Arie Paap
-- Changelist
-- v0.2
-- - Run search in larger grid with fixed size small soup
-- - Manually generate soup with SetCell() for performance
-- - Support D2 and D4 symmetry (applied to YZ plane)
--
-- v0.1 - Initial release
-- - Generate random soups in a 3D CA.
-- - Evolve soups and stop search when a periodic pattern is found.
local g = golly()
local op = require "oplus" -- for op.process
-- search parameters
local soup_size = 4 -- size of the base random soup
local min_period = 5 -- ignore oscillators with periods less than this.
local min_ship_period = 2 -- ignore spaceships with periods less than this.
local soup_sym = "D4_+4" -- soup symmetry to search: "C1", "D2_+1", "D2_+2", "D4_+1", "D4_+2", "D4_+4".
local soup_range = {30, 40} -- soup density range
-- initialize lists
local hashlist = {} -- for pattern hash values
local genlist = {} -- corresponding generation counts
local poplist = {} -- corresponding population counts
local boxlist = {} -- corresponding bounding boxes
----------------------------------------------------------------------
local function SymSoup(size, perc, sym)
-- Symmetry is applied to the YZ plane (ships with D4 symmetry travel along x-axis)
-- sym can be one of "C1", "D2_+1", "D2_+2", "D4_+1", "D4_+2", "D4_+4"
-- Do random soup generation to replace calls to RandomPattern()
ClearCells()
-- May not be necessary, but clear history to prevent potential problems.
-- Would be nice to disable Undo History instead.
ClearUndoRedo()
-- Determine symmetry operations
local ysym, zsym = false, false
if sym:sub(1, 2) == "C1" then
if sym:sub(1, 2) == "D2" then
if sym:sub(4, 5) == "+1" then
zsym = 0
elseif sym:sub(4, 5) == "+2" then
zsym = -1
else
g.warn("Unsupported D2 symmetry string")
return false
end
elseif sym:sub(1, 2) == "D4" then
if sym:sub(4, 5) == "+1" then
ysym, zsym = 0, 0
elseif sym:sub(4, 5) == "+2" then
ysym, zsym = 0, -1
elseif sym:sub(4, 5) == "+4" then
ysym, zsym = -1, -1
else
g.warn("Unsupported D4 symmetry string "..sym)
return false
end
else
g.warn("Unsupported symmetry string")
return false
end
-- Generate the soup
maxval = size-1
for z = 0, maxval do
for y = 0, maxval do
for x = 0, maxval do
if math.random(0,99) < perc then
SetCell(x, y, z, 1)
if zsym then
-- First symmetry plane
SetCell(x, y, zsym-z, 1)
if ysym then
-- Second symmetry planes
SetCell(x, ysym-y, z, 1)
SetCell(x, ysym-y, zsym-z, 1)
end
end
end
end
end
end
return true
end
----------------------------------------------------------------------
local function HashPattern(bbox)
local minx, maxx, miny, maxy, minz, maxz = table.unpack(bbox)
local hash = 31415962
for z = minz, maxz do
local zshift = z - minz
for y = miny, maxy do
local yshift = y - miny
for x = minx, maxx do
if GetCell(x, y, z) > 0 then
-- ~ is Lua's bitwise XOR
hash = (hash * 1000003) ~ zshift
hash = (hash * 1000003) ~ yshift
hash = (hash * 1000003) ~ (x - minx)
end
end
end
end
return hash
end
----------------------------------------------------------------------
local function oscillating(popcount)
-- return >= 1 if the pattern is stable or oscillating, otherwise 0
-- get the current pattern's bounding box
-- ie. { minx, maxx, miny, maxy, minz, maxz }
local pattbox = GetBounds()
-- calculate a hash value for the current pattern
local h = HashPattern(pattbox)
-- determine where to insert h into hashlist
local gencount = GetGeneration()
local pos = 1
local listlen = #hashlist
while pos <= listlen do
if h > hashlist[pos] then
pos = pos + 1
elseif h < hashlist[pos] then
-- shorten lists and append info below
for i = 1, listlen - pos + 1 do
table.remove(hashlist)
table.remove(genlist)
table.remove(poplist)
table.remove(boxlist)
end
break
else
-- h == hashlist[pos] so pattern is probably oscillating, but just in
-- case this is a hash collision we also compare pop count and box size
local box = boxlist[pos]
if popcount == poplist[pos] and
pattbox[2]-pattbox[1] == box[2]-box[1] and
pattbox[4]-pattbox[3] == box[4]-box[3] and
pattbox[6]-pattbox[5] == box[6]-box[5] then
local period = gencount - genlist[pos]
local moving = true
if box[1] - pattbox[1] == 0 and box[3] - pattbox[3] == 0 and
box[5] - pattbox[5] == 0 then
moving = false
end
return period, moving
else
-- look at next matching hash value or insert if no more
pos = pos + 1
end
end
end
-- store hash/gen/pop/box info at same position in various lists
table.insert(hashlist, pos, h)
table.insert(genlist, pos, gencount)
table.insert(poplist, pos, popcount)
table.insert(boxlist, pos, pattbox)
return 0, nil
end
----------------------------------------------------------------------
local pattcount = 0
local oldms = 0
while true do
-- get and ignore most user events so they don't get queued up
-- and then acted on after this script terminates, but we do call
-- op.process so user has access to some safe menu items
op.process(g.getevent())
-- write another function to find the rule's goldilocks density!!!
-- note that some (many?) rules have a very small density range at which
-- interesting patterns emerge; eg. for 3D4,7/5,8 the density is around 8%
if not SymSoup(soup_size, math.random(table.unpack(soup_range)), soup_sym) then
goto found_something
end
-- initialize lists
hashlist = {}
genlist = {}
poplist = {}
boxlist = {}
pattcount = pattcount + 1
local newms = g.millisecs()
local initpop = GetPopulation()
while true do
local pop = GetPopulation()
if pop == 0 then
break -- pattern died
elseif pop > 2 * initpop then
break -- pattern exploded
end
local period, moving = oscillating(pop)
if moving and period >= min_ship_period then
SetMessage("Found spaceship with period = "..period)
goto found_something
elseif (not moving) and period >= min_period then
SetMessage("Found oscillator with period = "..period)
goto found_something
elseif period > 0 then
break -- stable or low period oscillator or spaceship
end
Step()
end
if newms - oldms >= 1000 then -- show msg every second
oldms = newms
SetMessage("Searching... (hit escape to abort) patterns="..pattcount)
Update()
end
end
::found_something::
Andrew: I started out using the 3D.lua api to generate the random soups but switched to manually generating the soup for performance reasons. Here are some observations about the api:
- The "full" option to RandomPattern() is nice, but it's inconvenient that there's no way to fill a smaller selection. I wanted to generate a small soup in a larger grid so I changed the grid size down, random filled, and changed the grid size back up again (to 40) . The last step is very slow (~15ms).
- I also checked NewPattern(). This was surprisingly slow for larger grids, once again taking 15-20ms for a size 40 grid.
- I don't know what the best way to deal with Undo History is in the search script. I'm not even sure if it would have an impact, but it would be nice to be able disable it. Instead, I call ClearUndoRedo() for every soup - which seems like overkill.
- There's no way to manually reset the generation count after calling ClearCells().
- Copying and pasting a random soup in order to generate symmetric soups seemed to be reasonable, performance wise, but it does clobber the clipboard of course. It turned out to be easier and faster to do that directly as part of the soup creation. I hope the api for cell lists will make this easy and fast.
It feels bizarre that so much Golly functionality is being completely re-implemented in lua in order run 3D CA. Did you consider implementing a 3D neighbourhood natively in Golly in a similar way to LtL? I only ask because I'm curious about the trade-offs that you had to make. On the other hand, I wonder how much of this editing and simulation functionality which has been directly implemented in 3D.lua will be reusable by you or someone else wanting to simulate CA on other neighbourhoods not supported natively by Golly.
Edit: Fixed missing assignment to maxval. Which means I've been doing a lot of testing with a script that didn't assign to maxval. Only noticed it after restarting 3D.lua. Also fixed broken C1 symmetry support. These symmetry labels are of course wrong, but I'm referring to a 2D plane so they are applicable.
Edit 2: Apologies for the non-functional versions of the script. Should work for all supported symmetry modes now, and fail gracefully if an unsupported symmetry string is used. Here's a few nice results - found with C1 search, Grid size 41, soup_size 15, soup_range = {8, 8}.
56c/56 spaceship in 3D4,7/5,8.
Code: Select all
3D version=1 size=40 pos=15,17,17 gen=94069
x=10 y=6 z=6 rule=3D4,7/5,8
$$7bo/$$7bobo$9bo$7bo/7bo$7bobo$9bo$9bo$6bobbo/$9bo$9bo$oo7bo$6bobb
o$7bo/$7bo$6bobbo$6bobbo$o6boo/3$7bo!
30c/30 spaceship in 3D4,7/5,8
Code: Select all
3D version=1 size=40 pos=19,18,18 gen=113731
x=4 y=5 z=6 rule=3D4,7/5,8
$bo$bo/$3bo$oboo/bboo$3bo$3bo$3bo$bo/3bo$obbo$3bo$3bo/$b3o$3bo$oo/$$
bo!