Bellman

For scripts to aid with computation or simulation in cellular automata.
User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Post by simsim314 » April 23rd, 2015, 5:12 pm

Kazyan wrote:the output files give the catalysts and everything, but max-active is 10
Are you sure you did everything correctly (like saving the changes of the .in file and you pass the correct .in file)?

I can assure you no logic for max-active 10 is hardcoded into bellman.

I don't have linux station to check out how it works there unfortunately. Please check again, and if you absolutely sure you did everything correctly - contact me on PM I'll try to "debug" it on your station (add prints and see what happen).

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Bellman

Post by Kazyan » April 23rd, 2015, 5:54 pm

I fiddled with my input files once again and it's working as expected now. There might have been a zero-width character in the max-active line that interfered with the read operations somehow.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » April 23rd, 2015, 8:45 pm

It seems the symmetry syntax changed, but not in the test cases in the bellman repository. The syntax is:
#S symmetry-horiz-odd 17
right?

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Post by simsim314 » April 24th, 2015, 4:34 am

Scorbie wrote:It seems the symmetry syntax changed
Yes you right. Sorry about that. The syntax change was part of a preparation for the more full list of symmetries, and I didn't get my hands to finish it. See line 141 in bellman.c, and below.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Post by simsim314 » April 24th, 2015, 4:35 am

Kazyan wrote:I fiddled with my input files once again and it's working as expected now.
Great, so we can say BellmanWin works on Linux as well without (new) issues?

User avatar
codeholic
Moderator
Posts: 1147
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Post by codeholic » April 24th, 2015, 6:35 am

I acknowledge I could compile and run it on Mac OS X.
Ivan Fomichev

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » June 20th, 2015, 11:44 am

There seems to be some sort of problem in the LifeBellman rule.

Code: Select all

x = 13, y = 27, rule = LifeBellman
7E$8E$9E$10E$2.C.E2.2C2E$6.C3.2E$6.2C2.3E$10.3E$10.3E$.A9.2E$.2A8.2E$
.A8.C2E$11.2E$9.4E$11.2E$.A8.C2E$.2A8.2E$.A9.2E$10.3E$10.3E$6.2C2.3E$
6.C3.2E$2.C.E2.2C2E$10E$9E$8E$7E!
Also, as a suggestion, why don't we use a script like this, and save the LifeBellman rule seperately?

Code: Select all

import sys, os, glob
import subprocess
import golly as g 
from glife.text import make_text

def AddText(val, x, y):
	t = make_text(val, "mono")
	newt = []
	cnt = 0 

	for i in t:
	   cnt += 1
	   newt.append(i)
	   
	   if cnt % 2 == 0:
		  newt.append(4)
		  
	if len(newt) % 2 == 0:
	   newt.append(0)
	   
	g.putcells(newt, x, y)


def putcells(outfile, dxy):
	dx, dy = dxy
	tileCount = -1
	maxTileX = -1
	maxTileY = -1

	with open(outfile, "r") as data:
		for line in data:
			
			if tileCount >= 0:
				
				chars = list(line)
				
				for x in xrange(0, len(chars)):
					ch = chars[x]
					
					if ch == '@':
						g.setcell(dx + tileDX + x, dy + tileCount + tileDY, 1)
					if ch == '*':
						g.setcell(dx + tileDX + x, dy + tileCount + tileDY, 3)
					if ch == '?':
						g.setcell(dx + tileDX + x, dy + tileCount + tileDY, 5)
					
						
				tileCount += 1
			
			if line.startswith("#S"):
				continue 
			
			if line.startswith("#P"):
				vals = line.split()
				tileDX = int(vals[1])
				tileDY = int(vals[2])
				tileCount = 0
				
				if tileDX > maxTileX:
					maxTileX = tileDX
				
				if tileDY > maxTileY:
					maxTileY = tileDY
				
	return (maxTileX, maxTileY)

class Category:
    def __init__(self, category):
        self.category = category
        self.results = []
 
def FillCategories(path):
	
	files = glob.glob(os.path.join(path, "*.out"))
	g.show("Loading {0} files, please  wait...".format(str(len(files))))

	cats = {}
	idx = 0
	
	for f in files:
		
		lines = subprocess.Popen([os.path.join(os.path.dirname(os.path.realpath('__file__')), "bellman.exe"), "-c", f], stdout=subprocess.PIPE,  shell=True).communicate()[0]
		lines = lines.split("\n")
		d = {}
		for l in lines:
			idx = l.find(":")
			if idx > 0:
				key = l[:idx].strip()
				val = l[idx+1:].strip()
				if d.has_key(key):
					prev = d[key] + "\n"
				else:
					prev = ""
				d[key] = prev + val
		category = d["hash"]
		
		if not cats.has_key(category):
			cats[category] = Category(category)
			
		cats[category].results.append((f, d["log"]))
		
		
	return cats

def Place(path):
    
	cats = FillCategories(path)
	keysL = sorted(cats.keys(), key=lambda x: cats[x].results[0][0])
	g.show("Found {0} Categories".format(len(keysL)))
	
	dx, dy = 0, 0
	
	for c in keysL:
		results = cats[c].results
		AddText(str(len(results)), dx - 30, dy + 10)
		
		for i in xrange(0, len(results)):
			fname = os.path.splitext(os.path.basename(results[i][0]))[0]
			fname = fname.replace("result", "").lstrip("0").replace("-4", "")
			
			mdx, mdy = putcells(results[i][0], (dx, dy))
			
			AddText(fname, dx + int(mdx / 2), dy - 10)
			
			dx += mdx + 60
				
		dy += 60 + mdy
		dx = 0
	
	AddText(path, 0, -100)

#Start Here 
g.new("")
g.setrule("LifeBellman")
Place('')

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Post by simsim314 » June 20th, 2015, 12:41 pm

Scorbie wrote:There seems to be some sort of problem in the LifeBellman rule.
You right. Here is the fixed rule:

Code: Select all

@RULE LifeBellman

@TABLE

# state 0:  OFF
# state 1:  ON
# state 2:  History ON now OFF
# state 3:  Catalyst ON 
# state 4:  Catalyst OFF
# state 5:  Catalyst UNKNOWN

n_states:6
neighborhood:Moore
symmetries:rotate8

var a={0,2,4,5}
var b={0,2,4,5}
var c={0,2,4,5}
var d={0,2,4,5}
var e={0,2,4,5}
var f={0,2,4,5}
var g={3}
var h={0,1,2,5}
var i={0,1,2,3,4,5}
var j={0,1,2,3,4,5}
var k={0,1,2,3,4,5}
var l={0,1,2,3,4,5}
var m={0,1,2,3,4,5}
var n={0,1,2,3,4,5}
var o={0,1,2,3,4,5}
var p={0,1,2,3,4,5}

var i1={0,1,2,3,4,5}
var j1={0,1,2,3,4,5}
var k1={0,1,2,3,4,5}
var l1={0,1,2,3,4,5}
var m1={0,1,2,3,4,5}
var n1={0,1,2,3,4,5}
var o1={0,1,2,3,4,5}
var p1={0,1,2,3,4,5}

var q={1,3}
var R={1,3}
var S={1,3}
var T={1,3}
var u={3,4}

# Catalyst-doesn't change with unknown neighbour
3,5,i,j,k,l,m,n,o,3
5,3,i1,j1,k1,l1,m1,n1,o1,5
0,5,3,j1,k1,l1,m1,n1,o1,0
0,5,j1,3,k1,l1,m1,n1,o1,0
0,5,j1,k1,3,l1,m1,n1,o1,0
0,5,j1,k1,l1,3,m1,n1,o1,0
0,5,j1,k1,l1,m1,3,n1,o1,0
0,5,j1,k1,l1,m1,n1,3,o1,0
0,5,j1,k1,l1,m1,n1,o1,3,0

# Catalyst-neighbour birth
4,R,S,T,a,b,c,d,e,3
4,R,S,a,T,b,c,d,e,3
4,R,S,a,b,T,c,d,e,3
4,R,S,a,b,c,T,d,e,3
4,R,S,a,b,c,d,T,e,3
4,R,a,S,b,T,c,d,e,3
4,R,a,S,b,c,T,d,e,3

# Catalyst-neighbour survival
g,R,S,T,a,b,c,d,e,g
g,R,S,a,T,b,c,d,e,g
g,R,S,a,b,T,c,d,e,g
g,R,S,a,b,c,T,d,e,g
g,R,S,a,b,c,d,T,e,g
g,R,a,S,b,T,c,d,e,g
g,R,a,S,b,c,T,d,e,g

# normal 3-neighbour birth
h,R,S,T,a,b,c,d,e,1
h,R,S,a,T,b,c,d,e,1
h,R,S,a,b,T,c,d,e,1
h,R,S,a,b,c,T,d,e,1
h,R,S,a,b,c,d,T,e,1
h,R,a,S,b,T,c,d,e,1
h,R,a,S,b,c,T,d,e,1

# 2-neighbour survival
q,R,S,a,b,c,d,e,f,q
q,R,a,S,b,c,d,e,f,q
q,R,a,b,S,c,d,e,f,q
q,R,a,b,c,S,d,e,f,q

# ON states 3 and 5 go to history state 4 if they don't survive
g,i,j,k,l,m,n,o,p,4

# Otherwise ON states die and become the history state
q,i,j,k,l,m,n,o,p,2

@COLORS

1    255  255    255
2    0    0  0
3  0  191  225
4  255    0    0
5  120  255    0
Scorbie wrote:why don't we use a script like this, and save the LifeBellman rule seperately?
Personal preference. This is really minor issue, but if someone doesn't has LifeBellman rule installed, the script installs the rule automatically. You don't need to look for the rule folder, which could be annoying.

EDIT I've also fixed the rule script, in BellmanWin repository.

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » August 20th, 2015, 11:16 pm

I've made a fork of BellmanWin to try out some ideas:

- I've made explicit the last generation that a reactivation may happen, and max generations is set to allow it to complete any activation. This means that no type 1 solutions will be created.

- I've added a continuation mode. After a solution is accepted and saved as a result file, it will continue to evolve with the possibility to add new catalysts that activate later.

- Global and local complexity parameters. Complexity is calculated as a function of the size of the rectangle where added static on-cells fit, and of the number of on-cells added. There is a parameter to specify how many local rectangles that are allowed in the global rectangle.

A lot of testing and documentation is needed. This is just to let people know I'm working on this.

(Edit: It may look much faster than previously, but that is mostly because prunes are counted in a different way than before. It seems to be slightly faster however.)

The repository is here
(Edit: I'm new to GitHub, sorry for any mistakes I make...)

EDIT 2: Released v0.73, "forbidden" was broken.
Changed some parameter names, updated test file to work with this version.

EDIT 3: August 17, 2016, update to version 0.74 here, and updated the test file below for this version.

Here is a test file to try it out. It uses a new style of parameter names. Old style parameters are allowed for backward compatibility.

Basically it asks to look for two catalysts, each of which fit in a 3-by-3 box, and where both together fit in about a 13-by-13 box:

Code: Select all

#S min-first-active-gen 20
#S max-first-active-gen 30
#S strictly-gen-by-gen 1
#S max-last-active-gen -1
#S max-active-window-gens 48
#S max-active-gens-in-a-row 16
#S accept-alt1-inactive-gens -1
#S accept-alt2-active-inactive-gens 10
#S accept-alt2-min-inactive-gens 2
#S continue-after-accept 1
#S max-added-static-oncells -1
#S max-active-cells 6
#S filter-below-min-active-cells -1
#S max-local-rect-complexity 10
#S max-overall-local-complexity -1
#S max-local-rects 2
#S min-rect-separation-squared 8
#S max-global-complexity 40
#S new-result-naming -1
#P 0 0
................................................................
................................................................
................................................................
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
...........???????????????????????????????????????????..........
..............????????????????????????????????????????..........
................?........?????????????????????????????..........
...........................???????????????????????????..........
.............................?????????????????????????..........
.........................@....????????????????????????..........
.........................@.@...???????????????????????..........
.........................@@@...???????????????????????..........
...........................@...???????????????????????..........
..............................????????????????????????..........
.............................?????????????????????????..........
...........................???????????????????????????..........
...........?..........????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
..........????????????????????????????????????????????..........
................................................................
................................................................
................................................................
................................................................

Last edited by simeks on August 17th, 2016, 5:02 pm, edited 4 times in total.

User avatar
gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

Re: Bellman

Post by gmc_nxtman » August 22nd, 2015, 9:17 pm

How does the coordinate system work for filters in bellman? I want to add a filter that restores the block in the right place, so I don't get trivial solutions (as I'm getting right now) and please don't just post only the input file.

Code: Select all

#S first-encounter 28
#S last-encounter 36
#S repair-interval 10
#S stable-interval 15
#S max-live 20
#S max-active 5
#P 0 0

.......................
.?????????????????????.
.?????????????????????.
.?????????????????????.
.?????...........?????.
.?????...........?????.
.?????...........?????.
.?????...........?????.
.?????...........?????.
.?????...........?????.
.?????...........?????.
.......................
.......................
.......................
.......................
.......................
.......................
.......................
..........@@...........
..........@@...........
.......................
..........@............
.........@@@...........
.........@@@...........
.......................
........@@@@...........
........@@@@@..........
.........@.@@..........
.......................

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » August 23rd, 2015, 10:34 am

gmc_nxtman wrote:How does the coordinate system work for filters in bellman?
Doesn't that input file crash Bellman?
You normally need to have two lines of empty cells on the top side and two columns of empty cells on the left side. This is a known limitation of Bellman.

On the top side you actually have two empty lines, because the blank line between "#P 0 0" and the first line of dots counts as an empty line.
I would recommend replacing the blank line with a line of dots to make it easier to count coordinates later.

To actually find anything you need to increase last-encounter and add some more full lines of unknown cells on the top side.
I tested with "last-encounter 46" and 4 extra lines of unknown cells.

Now coordinates:
The first "." after "#P 0 0" (assuming you removed the blank line) has coordinates (0, 0).
Assume you want to use a 4 by 4 cells filter like this:

....
.**.
.**.
....

Note that a filter always uses "*" not "@".
Count downwords line by line starting at 0 to the top cell to include in the filter.
With the 4 lines I added it is line 22.
Then count from the start of the line to the left cell in the filter, that is cell 10 with the blank column I added.

Without catalysts the block gets restored at generation 53, but with catalysts it is often destroyed shortly afterwords.
I tried to set the filter at generation 80, so it becomes:

#F 80 10 22
....
.**.
.**.
....

Again avoid a blank line between "#F 80 10 22" and the cell data.

Here is the input file I tested:

Code: Select all

#S first-encounter 28
#S last-encounter 46
#S repair-interval 10
#S stable-interval 15
#S max-live 20
#S max-active 5
#P 0 0
........................
........................
..?????????????????????.
..?????????????????????.
..?????????????????????.
..?????????????????????.
..?????????????????????.
..?????????????????????.
..?????????????????????.
..?????...........?????.
..?????...........?????.
..?????...........?????.
..?????...........?????.
..?????...........?????.
..?????...........?????.
..?????...........?????.
........................
........................
........................
........................
........................
........................
........................
...........@@...........
...........@@...........
........................
...........@............
..........@@@...........
..........@@@...........
........................
.........@@@@...........
.........@@@@@..........
..........@.@@..........
........................

#F 80 10 22
....
.**.
.**.
....

User avatar
gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

Re: Bellman

Post by gmc_nxtman » August 23rd, 2015, 11:50 pm

The search was interesting, and the catalyses I get are interesting, however they don't restore the block.

Code: Select all

x = 167, y = 41, rule = B3/S23
11bobo$10bob2o30b2o$10bo33bo$8b2ob2obo31bo$7bobobob2o27b5o74bobo$6bobo
33bo43b2o32bob2o$7bo37b4o32bo4bobob2obo26bo$34b2o9bo2bo32b3o4bobob2o
24b2ob2obo$35bo48bo3b2o27bobobob2o$ob2o31bobo45b2o31bobo$2obo32b2o79bo
44b2o$162bo$164bo$160b5o$160bo$163b4o$163bo2bo5$8b2o$8b2o32b2o$42b2o$
8bo76b2o$7b3o32bo42b2o31b2o$7b3o31b3o74b2o$41b3o41bo$6b4o74b3o31bo$6b
5o29b4o40b3o30b3o$7bob2o29b5o72b3o$41bob2o38b4o73b2o$83b5o28b4o40b2o$
84bob2o28b5o$117bob2o39bo$159b3o$159b3o2$158b4o$158b5o$159bob2o!
The only modification I did was change max-active to 6.

Does the search give trivial results to you?

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » August 24th, 2015, 12:36 am

I think the encounter generation could be the problem. The transparent block is restored at gen 53 so you should set first-encounter and last-encounter much later than 28 and 46, respectively. (The block that appears around gen 30 is in the wrong place, in case you didn't notice.)

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » August 24th, 2015, 11:54 am

gmc_nxtman wrote:The search was interesting, and the catalyses I get are interesting, however they don't restore the block.
If you're getting results where the block isn't present at generation 80, that is most likely because you're using an older version of Bellman.

Bellman used to have that issue, that if all other conditions for a solution were met at a generation earlier than the generation when the filter should be applied, then it just ignored the filter and generated a solution.

simsim314 fixed this when he was working on BellmanWin, and it should work fine in his latest version here.

Note that the latest compiled version is the one with "T64" in its name - bellmanT64.exe. The bellman.exe file is older and may still have that issue.

If you still need to make the search in an earlier version, you'll need to increase the stable-interval parameter, so that (first-encounter + stable-interval) is at least the same as the generation the filter should be applied.

In the input-file above that would mean changing stable-interval to 52 as (28 + 52) = 80.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Post by simsim314 » August 24th, 2015, 4:59 pm

simeks wrote:I've made a fork of BellmanWin to try out some ideas:
Wow so many new flags... very nice! Didn't took the time to look in the code, can you explain in few words all the new flags you've added?

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » August 24th, 2015, 10:05 pm

simsim314 wrote:Didn't took the time to look in the code, can you explain in few words all the new flags you've added?
I will soon, but this is still work in progress, and I just noticed a few silly bugs, and I'm a little short on time the next few days... ;)

In the mean-time did you try to run the test-file? Despite the search-area it's just a 30 seconds run. I think it will explain something about what I'm trying to do.

User avatar
gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

Re: Bellman

Post by gmc_nxtman » October 13th, 2015, 11:29 am

This input instantly gives no results. Is this because there aren't any, or is there something wrong? I want to find a stable glider pusher that restores the block, and I know that filters aren't working (and I can't use BellmanWin)

gliderpusher.in

Code: Select all

#S first-encounter 20
#S last-encounter 60
#S repair-interval 10
#S stable-interval 25
#S max-live 50
#S max-active 15
#P 0 0
.............................
.............................
.........................**..
.........................*...
.......................*.*...
..???????..............**....
..????????...................
..?????????..................
..??????????.....@...........
..???????????.....@..........
..?????????.....@@@..........
..?????????..................
..?????????..................
..?????????............**....
..?????????......@@....*.*...
..?????????......@@......*...
..?????????..............**..
.............................
.............................

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » October 13th, 2015, 7:05 pm

gmc_nxtman wrote:This input instantly gives no results. Is this because there aren't any, or is there something wrong?
It's because the eater 1:s are specified as pre-existing catalysts (using "*") instead of as part of the evolving pattern (using "@").

Both ways are possible, but if you have them as pre-existing catalysts you will notice that they activate in generation 19. Because you use "first-encounter 20", Bellman then considers all encounters to be too early.

User avatar
gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

Re: Bellman

Post by gmc_nxtman » May 1st, 2016, 3:28 pm

The following search crashes bellman and gives errors that it would give if the input had no border, but it has a 2-cell border. Why?

Code: Select all

#S first-encounter 95
#S last-encounter 125
#S stable-interval 24
#S repair-interval 9
#S max-live 20
#S max-active 7
#P 0 0

....................................
....................................
......@@.@..........................
......@.@@..........................
....................................
.......@@@@@..@................@....
..@@..@....@..@@@............@@@....
..@..@..@........@..........@.......
...@.@.@@.......@@..........@@......
..@@.@.....@........................
.....@....@.@.......................
.....@@..@..@.......................
..........@@........................
....................................
....................................
....................................
....................................
....................................
..........@.........................
..........@.@.......................
..........@@@.......................
............@.......................
....................................
....................................
...........................???????..
...........................???????..
...........................???????..
...........................???????..
...............???????????????????..
...............???????????????????..
...............???????????????????..
...............???????????????????..
....................................
....................................

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Bellman

Post by chris_c » May 1st, 2016, 7:25 pm

gmc_nxtman wrote:The following search crashes bellman and gives errors that it would give if the input had no border, but it has a 2-cell border. Why?
I've very rarely run Bellman but I remember this post suggests not to have any "???" cells on a 64x32 boundary. Maybe you can flip/rotate your pattern to put all the "???" near the origin?

Actually.... I just ran your pattern with "P 0 0" replaced with "P -5 -5" and it seems not to crash any more.

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » May 3rd, 2016, 11:47 am

gmc_nxtman wrote:The following search crashes bellman and gives errors that it would give if the input had no border, but it has a 2-cell border. Why?
As chris_c wrote above this is because the two cells closest to the border of each tile may not contain unknown cells.

The tile size of the original Bellman was 64 wide by 32 high.

In simsim314s version, which I guess is pretty much the standard version now, the tile size is increased to 64-by-64, see this post.

According to this and this post, it works well on most platforms.

If you still need to use an older version, setting the origin to (-5, -5) as suggested by chris_c solves the problem, but it will use four tiles, which will be pretty slow. A different solution would be to replace the Eater3 with just the loaf, which will work the same for the purposes of this search.

Incidently, my experimental version with this input, that increases the search area and adds the max-global-complexity parameter, which limits the bounding box of the on-cells of the catalyst...

Code: Select all

#S first-encounter 95
#S last-encounter 125
#S stable-interval 24
#S repair-interval 9
#S max-live 20
#S max-active 7
#S max-global-complexity 25
#P 0 0
................................................................
................................................................
..............@@.@..............................................
..............@.@@..............................................
................................................................
...............@@@@@..@................@........................
..........@@..@....@..@@@............@@@........................
..........@..@..@........@..........@...........................
...........@.@.@@.......@@..........@@..........................
..........@@.@.....@............................................
.............@....@.@...........................................
.............@@..@..@...........................................
..................@@............................................
................................................................
................................................................
................................................................
................................................................
................................................................
..................@.............................................
..................@.@...........................................
..................@@@...........................................
....................@...........................................
................................................................
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................??????????????????????????????????????..........
................................................................
................................................................
... finds this, which is perhaps not connectible, but a bit interesting:

Code: Select all

x = 30, y = 34, rule = LifeHistory
4.2A.A$4.A.2A2$5.5A2.A16.A$2A2.A4.A2.3A12.3A$A2.A2.A8.A10.A$.A.A.2A7.
2A10.2A$2A.A5.A$3.A4.A.A$3.2A2.A2.A$8.2A6$8.A$8.A.A$8.3A$10.A9$15.C$
11.C2.C.C.C$11.4C.C.3C$15.C5.C$13.C6.2C$13.2C!

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » May 4th, 2016, 12:52 pm

I am currently trying to find out what the parameters are.
I think this project would be more active if there are minimal docs explaining all the params.

These are all the params, right? (code from bellman.c:251~270)

Code: Select all

        // New style parameters
        match |= match_parameter ("min-activation-gen", param, value, 0, 0, 1023, &min_activation_gen);
        match |= match_parameter ("max-first-activation-gen", param, value, 0, 0, 1023, &max_first_activation_gen);
        if (match_parameter ("max-reactivation-gen", param, value, 0, 0, 1023, &max_reactivation_gen))
        {
            match = YES;
            explicit_max_reactivation_gen = YES;
        }
        match |= match_parameter ("max-active-gens-in-a-row", param, value, 0, 1, 1023, &max_active_gens_in_a_row);
        match |= match_parameter ("inactive-gens-at-accept", param, value, 0, 1, 1023, &inactive_gens_at_accept);
        match |= match_parameter ("sum-of-active-inactive-gens-at-accept", param, value, 0, 0, 1023, &sum_of_active_inactive_gens_at_accept);
        match |= match_parameter ("continue-after-accept", param, value, 0, 0, 1, &continue_after_accept);
        match |= match_parameter ("max-added-static-oncells", param, value, 0, 0, 1023, &max_added_static_oncells);
        match |= match_parameter ("max-activated-cells", param, value, 0, 0, 1023, &max_activated_cells);
        match |= match_parameter ("filter-below-min-activated-cells", param, value, 0, 0, 1023, &filter_below_min_activated_cells);
        match |= match_parameter ("max-local-complexity", param, value, 0, 0, 1023, &max_local_complexity);
        match |= match_parameter ("max-local-areas", param, value, 0, 1, MAX_MAX_LOCAL_AREAS, &max_local_areas);
        match |= match_parameter ("min-local-area-separation-squared", param, value, 0, 0, 8191, &min_local_area_separation_squared);
        match |= match_parameter ("max-global-complexity", param, value, 0, 0, 1023, &max_global_complexity);
        match |= match_parameter ("old-result-naming", param, value, 0, 0, 1, &old_result_naming);
I am not sure of the followings:
  • blah-at-accept means "blah" is needed to accept a pattern, right?
  • the cats can react from min-activation-gen to max-reactivation-gen, and **must** react some time before max-activation-gen, right?
  • what does sum-of-active-inactive-gens-at-accept mean?
  • what does "static-oncells" mean? The catalyzing cells(*), or cells of state 3 in LifeBellman?
  • simeks wrote: Global and local complexity parameters. Complexity is calculated as a function of the size of the rectangle where added static on-cells fit, and of the number of on-cells added. There is a parameter to specify how many local rectangles that are allowed in the global rectangle.
    Can you elaborate on how the params are calculated? I would like the result to contain fairly small catalysts (that can be used in self-constructing circuitry, with the eater 2 being the most complex one) and there isn't enough information on how much I should set as complexity.
  • If I got it right, filter-below-min-activated-cells would be better if renamed to min-activated cells. What's the criteria for 'activated cells'? Can I tweak this param to filter useless single cell catalysts but include rock catalysts in the search area?
  • max-local-areas seem to be the number of catalysts, right?
  • I am not sure what's min-local-area-seperation-squared.
Thanks in advance.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » May 4th, 2016, 2:23 pm

Bellman-szlim seems to be very useful in reducing the search space.
Another question: Here's my attempt on finding a pi-based factory.
Bellman-szlim ignores filters...Why?
Is Bellman-szlim suitable for these kinds of tasks?

Code: Select all

#S min-activation-gen 40
#S max-first-activation-gen 65
#S max-reactivation-gen 100
#S max-active-gens-in-a-row 8
#S inactive-gens-at-accept 6
#S continue-after-accept 0
#S max-added-static-oncells 32
#S max-activated-cells 5
#S max-local-complexity 10
#S max-local-areas 3
#S min-local-area-separation-squared 15
#S max-global-complexity 100
#S old-result-naming 0
#P 19 19
?????????????????????????.
?????????????????????????.
?????????????????????????.
?????????????????????????.
?????????????????????????.
??????????......?????????.
??????????......?????????.
??????????..@@..?????????.
??????????..@@..?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
??????????......?????????.
?????????????????????????.
?????????????????????????.
?????????????????????????.
?????????????????????????.
????????????????????????@.
???????????????????????@@.
???????????????????????@.@
#F 31 26 120
**
**

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Bellman

Post by simeks » May 4th, 2016, 4:44 pm

Scorbie wrote:I think this project would be more active if there are minimal docs explaining all the params
I know I left this project in an unfortunate state... First real life got in the way, and then this happened, that made me switch focus.

I plan to get back to working on the Bellman_szlim project eventually, and I don't want to spend too much time documenting the current state, as things are likely to change.

In the meantime I'll try to answer questions from anyone interested in trying this version out.

Let me start with "filter-below-min-activated-cells":
I use this name to stress that a catalyst that has fewer than this number of active cells, is still an "accepted solution" in the terminology of the other parameters. It just gets "filtered" from being reported at a solution. I used to call it just "min-activated-cells", but as I remember it got me confused about its meaning.

"inactive-gens-at-accept" is the same as "stable-interval", except it should be one higher to get the same result (if set to 8, the solution is accepted on the 8:th generation in a row with no active cells)
I added "sum-of-active-inactive-gens-at-accept" to get some more interesting results without being overwhelmed by a lot of uninteresting ones. This Pi-to-G was the inspiration for that parameter:

Code: Select all

x = 16, y = 18, rule = LifeHistory
5.2D$5.2D7.2D$14.D$12.D.D$12.2D$4.3E$6.E$4.3E4$4.C$3.C.C.2C$.3C.C.C$C
3.C4.C$.C2.C.3C.C$2.C.C.C2.C$3.C3.2C!
Note how the big catalyst on its own, is active from generation 9 to 16, a total of 8 generations, and than stays inactive for just 2 generations before going active again. In standard Bellman, to find that catalyst, you would have to set "stable-interval" to 1 to find it, which will give a lot of junk results. But if you set "sum-of-active-inactive-gens-at-accept" to 10, you can still find that catalyst (8 generations active + 2 generations inactive = 10) without seeing all blocks that survives for 2 generations after being restored, for example.

An active cell in a particular generation is either a static on-cell (a blue cell in the LifeBellman rule) that is currently off, or any neighbour-cell to a static on-cell, that is normally off when the catalyst in its stable state, but is on in the current generation.
The first time any cell goes active must happen between "min-activation-gen" and "max-first-activation-gen", or the current search branch will be ended.

If a pattern has returned to inactive, but then goes active again at a generation later than "max-reactivation-gen", that search branch is ended and will not generate any more solutions. On the other hand any reactivation that happens no later than "max-reactivation-gen" will be allowed to be evolved for enough generation to find out if it can generate a solution. How many generations that is depends on "max-active-gens-in-a-row", "inactive-gens-at-accept" and "sum-of-active-inactive-gens-at-accept".
Standard Bellman generates "Type 1" solution when a reactivation happens too late to determine if it will generate a solution or not. My new parameters means that no "Type 1" solutions will ever be generated. Any solution reported is a "real" solution, and those that would be "Type 1" solution just didn't match the search parameters and are not reported.

I use the term "static on-cells" for the blue (state 3) cells in LifeBellman. This is both "*"-cells present in the initial search patterns, and "*" in the result that were added in the search process. The parameter is called "max-added-static-oncells", because only those added in the search process, and not those already present are counted. This is exactly how standard Bellman works with the "max-live" parameter.
Scorbie wrote:Can you elaborate on how the params are calculated?
This is a bit ad-hoc, but this is how it works currently:

"max-global-complexity" looks at the full set of LifeBellman blue cells in the solution: If there are n blue cells, and the bounding box of the blue cells is l×s, then the complexity is 2×l + s + max (0, n - 9).

For example:

Code: Select all

x = 44, y = 37, rule = LifeBellman
44E$44E$44E$44E$44E$44E$44E$44E$17E5.22E$15E2.C4.22E$15E.C3.C.C21E$
15EC3.C.C4.18E$15E2C3.C6.17E$15E14.15E$.15E14.14E$4.10E17.13E$6.E24.
13E$31.13E$31.13E$15.A15.13E$15.A.A12.14E$15.3A11.15E$17.A9.17E$26.
18E$23.21E$22.22E$.E13.29E$44E$44E$44E$44E$44E$44E$44E$44E$44E$44E!
The bounding box of the blue cells is 8×4, so the complexity from that is 2×8 + 4 = 20. There are 10 blue cells. As suggested by the formula, the first 9 cells are "free", so 10 cells adds 1 to the complexity.
This means to find this particular result, "max-global-complexity" must be 21 or higher. The complexity of canonical Eater2 is 17.
The time to complete a search is very sensitive to this setting. As a rule of thumb, adding 2 to "max-global-complexity" will triple the search time (a low setting of "max-active-cells" makes it a bit less sensitive).
Scorbie wrote:What's the criteria for 'activated cells'? Can I tweak this param to filter useless single cell catalysts but include rock catalysts in the search area?
There is still the problem with single cell catalysts everywhere, that never activate. Limiting the allowed bounding box of the catalyts with "max-global-complexity" reduces this problem a lot, however.

Still, the problem with single cell catalysts that never activate is not only a lot of duplicate solutions, but it also makes the search many times slower than it could be. Solving this is not simple, but I'm considering a solution: When the value of two adjacent static-unknown cells are needed, but setting just one of them to on doesn't cause an activation, instead of splitting the search tree in four parts for all combinations of the two cells, we just split it in two: one with both cells on, and the other with both cells still unknown, but here we add this pair of cells to a list of "forbidden pairs" that is maintained for the current search path. I'm not sure how well that would work, but it would be interesting to try.

"max-local-areas" is indeed the number of catalysts, except depending on the value of "max-local-complexity", more than one catalyst could sometimes fit in a single local area.

"max-local-complexity" is calculated the same as "max-global-complexity", except that the number of "free" cells are just 4 instead or 9, this means for example that the local complexity of Eater2 is 22 instead of 17.

"min-local-area-separation-squared" determines if cells belong to the same local area or not. If the closest cells in two catalysts have coordinates (x, y) and (x + dx, y + dy), then they belong to the same local area if (dx * dx) + (dy * dy) is less or equal to the value of this parameter. For example:

Code: Select all

x = 44, y = 37, rule = LifeBellman
44E$44E$44E$44E$44E$44E$44E$44E$44E$44E$19E.2C3.19E$18E2.C.C2.19E$18E
3.C5.17E$17E10.C16E$.15E9.C.C16E$4.10E11.2C.16E$6.E21.16E$28.16E$28.
16E$15.A11.17E$15.A.A8.18E$15.3A7.19E$17.A6.20E$24.20E$23.21E$22.22E$
.E13.29E$44E$44E$44E$44E$44E$44E$44E$44E$44E$44E!
These two catalysts would belong to the same local area if "min-local-area-separation-squared" is 18 or higher, because dx = 3 and dy = 3. I use a value of 8 for this parameter most of the time.
Scorbie wrote:Bellman-szlim ignores filters...Why?
I think you just switched the order of the parameters... The first one should be the generation count. This means you filter on a block placed at (26, 120), and as I remember there is a bug that filters that end up in a 64-by-64 tile which isn't used by the pattern, don't work correctly.

Also, you should normally set "continue-after-accept" to 1 when searching for more than one catalysts, or the search will only find catalysts that activate close in time to each other.

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » May 4th, 2016, 9:33 pm

simeks wrote:I plan to get back to working on the Bellman_szlim project eventually, and I don't want to spend too much time documenting the current state, as things are likely to change.

In the meantime I'll try to answer questions from anyone interested in trying this version out.
Ahh, I see. I think this is enough for anyone to try it out for now :) Thanks a lot for your detailed explanation!

Edit:

Code: Select all

#S inactive-gens-at-accept 8 (Let's call this 1)
#S sum-of-active-inactive-gens-at-accept 10 (Let's call this 2)
These were in your sample search file. Does it mean the solution is accepted if "either 1) or 2) happens" or "both 1) and 2) happens"?

Edit2:
Well, I was setting the search to find something similar to the syringe.
That means: 1) Multiple catalysts 2) Block restoration with filter.
But with "#S continue-after-accept 1" the search only seems to continue adding catalysts ONLY IF the bait is restored by the first catalyst.

Post Reply