Adapting apgsearch/Catagolue for searching expanding rules like Maze

For general discussion about Conway's Game of Life.
Post Reply
ColorfulGabrielsp138
Posts: 288
Joined: March 29th, 2021, 5:45 am

Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by ColorfulGabrielsp138 » July 2nd, 2021, 5:48 am

I just visited Catagolue and found there are no censuses for maze-like rules except for one that simply says "Please specify a symmetry type" without showing an option.
So In my opinion, apgsearch/Catagolue should added maze-like rules (like Maze, Mazectric and xvaMazectricg) to its censuses.
But instead of searching for oscillators and still lives, apgsearch might search for rotors and islands instead.
It is still accepted to search for regular infinite growths.
Thanks.

Code: Select all

x = 21, y = 21, rule = LifeColorful
11.E$10.3E$10.E.2E$13.E4$2.2B$.2B$2B$.2B15.2D$19.2D$18.2D$17.2D4$7.C$
7.2C.C$8.3C$9.C!
I have reduced the glider cost of quadratic growth to eight and probably to seven. Looking for conduits...

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

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by dvgrn » July 2nd, 2021, 8:06 am

ColorfulGabrielsp138 wrote:
July 2nd, 2021, 5:48 am
I just visited Catagolue and found there are no censuses for maze-like rules except for one that simply says "Please specify a symmetry type" without showing an option.
So In my opinion, apgsearch/Catagolue should added maze-like rules (like Maze, Mazectric and xvaMazectricg) to its censuses.
But instead of searching for oscillators and still lives, apgsearch might search for rotors and islands instead.
It is still accepted to search for regular infinite growths.
Thanks.
It's just plain not a simple task to add the ability to census expanding rules.

Expanding rules generally have no reasonable limit on the number of distinct objects they can generate. Would it be useful for a census to display one hundred million objects, each of which appears only once? If you only choose a subset of those objects, how exactly should the choice be made?

Your suggestion is to search for "rotors and islands" instead of oscillators or still lifes, but for an arbitrary rule, how would the automated analysis work that would find rotors and islands in an expanding rule -- and how can you guarantee that there won't be an unmanageably large number of them? Expanding rules are generally unsearchable precisely because you can't run them to completion -- patterns expand and quickly overflow the available memory and CPU resources, instead of settling into anything that can be counted.

The above are not just rhetorical questions. If you go ahead and write an experimental script (in Python or Lua, let's say) that can analyze soups in expanding rules and extract interesting census information about them, and people are able to use the script to find interesting things, then that would make it much more likely that apgsearch/Catagolue would eventually be adjusted to support generating and storing those censuses.

Until then, what you've written really only _looks_ like a feature request. It's not really a feature request, because it's completely unclear how to implement it.

User avatar
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by wwei47 » July 2nd, 2021, 10:17 am

Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

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

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by dvgrn » July 2nd, 2021, 11:41 am

wwei47 wrote:
July 2nd, 2021, 10:17 am
What about xp2_spaceinvaderstest? It skips soups that explode, and it works...
I had explosion problems with these rules before.
What about it, exactly? I don't have anything against special-case rules that can actually be censused even though they sometimes explode.

I just don't see any way to write a general algorithm that censuses rules that do pretty much always explode, but maybe count something different from what you'd normally count.

User avatar
wwei47
Posts: 1651
Joined: February 18th, 2021, 11:18 am

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by wwei47 » July 2nd, 2021, 12:02 pm

dvgrn wrote:
July 2nd, 2021, 11:41 am
wwei47 wrote:
July 2nd, 2021, 10:17 am
What about xp2_spaceinvaderstest? It skips soups that explode, and it works...
I had explosion problems with these rules before.
What about it, exactly? I don't have anything against special-case rules that can actually be censused even though they sometimes explode.
I'm saying that explosive rule searching has been done in the past.
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

User avatar
blah
Posts: 311
Joined: April 9th, 2016, 7:22 pm

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by blah » July 2nd, 2021, 12:04 pm

dvgrn wrote:
July 2nd, 2021, 11:41 am
I just don't see any way to write a general algorithm that censuses rules that do pretty much always explode, but maybe count something different from what you'd normally count.
What if you don't actually want a comprehensive census?

This thread reminded me of an idea I had a while ago, and finally got me to implement it. Here's a soup searcher for Brian's Brain:

Code: Select all

--[[
	23src.lua
	blah 2021

	This program searches for p1 spaceships in Brian's Brain by running an
	explosive simulation in a 256*256 torus and occassionally stopping the
	simulation, then taking random slices of the pattern and checking to see if
	any of them contain spaceships.

	The results are displayed lined up at the end.

	This program is a proof of concept and is not expected to have serious
	utility.
]]
-- SETTINGS
local SLICEX=12
local SLICEY=7
local SLICES_PER_STOP=20
local STOP_GAP=20
local STOPS=200
-- PROGRAM
local g=golly()
local results={}

g.addlayer()
g.setrule("/2/3:T256,256")

-- generate random soup, run for long enough to init
for i=1, 500 do g.setcell(math.random(100),math.random(100),1) end
g.run(150)
local q, p -- q=candidate object, p=next gen
local sx,sy
for t=1, STOPS do -- stops
	g.run(STOP_GAP)
	for s=1, SLICES_PER_STOP do -- slices
		sx, sy = math.random(256-(SLICEX-1))-129,
		         math.random(256-(SLICEY-1))-129
		q=g.getcells{sx,sy,SLICEX,SLICEY}

		-- skip empty slices
		if #q == 0 then goto skip end

		-- skip if border not empty
		for i=2, #q, 3 do
			local x, y = q[i-1] - sx, q[i] - sy
			if x==0 or y==0 or x==SLICEX-1 or y==SLICEY-1 then
				goto skip end end

		-- get the next step
		g.run(1)
		p=g.getcells{sx,sy,SLICEX,SLICEY}

		-- skip if different population
		if #p ~= #q then goto skip end

		-- check if it moved
		local hash={}
		for i=3,#q,3 do hash[q[i-1]*SLICEX+q[i-2]]=q[i] end
		for i=3,#p,3 do
			if hash[p[i-1]*SLICEX+p[i-2]-1]~=p[i] then
				goto skip
			end end

		-- result found
		results[#results+1] = q
		::skip::
	end
end

g.dellayer()
g.addlayer()
g.setrule("/2/3")
for i, v in ipairs(results) do
	g.putcells(v, -v[1], i*SLICEY*2-v[2])
end
g.warn(#results.." spaceships found.")
I think there's some unexplored potential in this sort of methodology. Has anyone done anything like this before?
succ

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

Re: Adapting apgsearch/Catagolue for searching expanding rules like Maze

Post by dvgrn » July 2nd, 2021, 12:36 pm

blah wrote:
July 2nd, 2021, 12:04 pm
What if you don't actually want a comprehensive census?
Sure, that's a possibility. Which means there are questions that would need to be answered very specifically, before anything could sanely be added to apgsearch/Catagolue. They're in the five-paragraph post above:
dvgrn wrote:Expanding rules generally have no reasonable limit on the number of distinct objects they can generate. Would it be useful for a census to display one hundred million objects, each of which appears only once? If you only choose a subset of those objects, how exactly should the choice be made?

Post Reply