Bellman

For scripts to aid with computation or simulation in cellular automata.
User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Post by Scorbie » January 7th, 2015, 9:39 am

codeholic wrote:The filter just checks that there is a certain pattern in a certain point of time on the board. Question marks are not allowed there, only whitespace (unknown or don't-care), dots (dead) and asterisks (alive).
Another possibility...

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

Re: Bellman

Post by codeholic » January 7th, 2015, 9:41 am

codeholic wrote:The filter just checks that there is a certain pattern in a certain point of time on the board. Question marks are not allowed there, only whitespace (unknown or don't-care), dots (dead) and asterisks (alive).
According to MikeP, this one was fixed.
Ivan Fomichev

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 9:50 am

codeholic wrote:I see you made borders of width 3 just in case
I made a huge border as the pattern was failing to run.
codeholic wrote:Question marks are not allowed there, only whitespace
From documentation 3.1.2 Filter definition:

Filters don't have to be rectangular; use '?' in a filter pattern to indicate a
“don't care” cell which will match any evolving pattern.


Anyway I'll remove the "?" just to check.
codeholic wrote: you need to specify all filters
What do you mean? I specified two filters what exactly I need to add?

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

Re: Bellman

Post by Scorbie » January 7th, 2015, 9:51 am

Uh, oh... The source from me (and probably Sokwe) was the version before MikeP fixed that... So it'll have the problems...
EDIT: I deleted only the 4 ?s from your pattern and bellman still gives me two-block catalysts... Which is probably what you want to filter out. So the problem may be something else.

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 10:01 am

I run Sokwe's 32 bit version as it has images, so the results make more sense.

OK removed the "?" from the filter, checking it now. But we must have some sort of "main" repository.

I think I'll manage my own versions of the search utilities (which are bsd/mit licensed anyway), and try to keep up with the updates.

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

Re: Bellman

Post by codeholic » January 7th, 2015, 10:16 am

simsim314 wrote:What do you mean? I specified two filters what exactly I need to add?
I meant all the other filters (see snark.in for the full list). Though, as I said, I'm not sure if they work only if all of them are given.
Ivan Fomichev

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

Re: Bellman

Post by Scorbie » January 7th, 2015, 10:22 am

codeholic wrote:According to MikeP, this one was fixed.
Where can I get the newest version? The one on sourceforge(downloaded 10 minutes ago) isn't fixed...

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 10:30 am

Didn't help to remove the "?" from the filter. Bellman still reports everything.

Here is how it looks now:

Code: Select all

#S repair-interval 10
#S last-encounter 20
#P 10 10
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............@@@............@@@..............
..............@.@............@.@..............
..............@@@............@@@..............
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
................@@@........@@@................
................@.@........@.@................
................@@@........@@@................
..............................................
..............................................
..............................................
................@@@........@@@................
................@.@........@.@...??????????...
................@@@........@@@...??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
..............@@@.....??????.@@@.??????????...
..............@.@.....??????.@.@.??????????...
..............@@@.....??????.@@@.??????????...
......................??????.....??????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
..............................................
..............................................
..............................................
#F 23 39 50
.....
.***.
.*.*.
.***.
.....
#F 23 37 41
.....
.***.
.*.*.
.***.
.....
I guess there is some bug in case when the iterator that checks for catalyst doesn't reach the generation of the filter. I'll need to hack the source code...for now I've added stable-interval 10 just to reduce the spam. But it's obviously not the best solutions as it could ignore some good solutions.

I really don't think I need to "hack" input parameters for bellman, this is why filters were created in the first place, and I'm using the correctly.

EDIT Adding stable interval helped, but it's really a hack. So I already see four major requests:

1. mkstill should work faster and start from smaller patterns and expand.
2. Filters should work for catalysts that don't reach the generation of the filter.
3. Tiles should stop throwing exceptions and handled internally.
4. "?" should work in filter as mentioned in documentation.
Last edited by simsim314 on January 7th, 2015, 11:08 am, edited 1 time in total.

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

Re: Bellman

Post by Scorbie » January 7th, 2015, 11:07 am

simsim314 wrote:I really don't think I need to "hack" input parameters for bellman, this is why filters were created in the first place, and I'm using the correctly.
I agree with you, but the program is still ongoing project, and your bug is the first of its kind AFAIK.--I was talking about #2 here.
simsim314 wrote:1. mkstill should work faster and start from smaller patterns and expand.
2. Filters should work for catalysts that don't reach the generation of the filter.
3. Tiles should stop throwing exceptions and handled internally.
4. "?" should work in filter as mentioned in documentation.
codeholic says that #4 is implemented, but bellman for windows isn't up to date yet.
#1 (never found any catalysts so... nothing to say here.)
#3 agreed.

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 11:15 am

Some basic requests should be added:

bellman:

1. Catalyst survive until generation.
2. Remove redundant solutions (delete catalysts that have extra cell that doesn't influence anything).

mkstill :

1. Report all possible solutions.
2. Query the solution space (like prefer spartan).

---

Please add more requests.

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

Re: Bellman

Post by codeholic » January 7th, 2015, 11:46 am

  1. I'd really love if Bellman handled eater2 in a friendlier manner ;) E. g. if a solution with an eater2 is found, all other eater2 variants in the same position are pruned.
  2. I wonder how feasible it is to upgrade it to search not only for p1 catalysts, but also for p2+ ones
Ivan Fomichev

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

Re: Bellman

Post by Scorbie » January 7th, 2015, 12:00 pm

A little off topic but why don't you add stable-interval 1 instead of 10? (Tried 0 and the catalyst stabilized into a different still life)edit: mistaken
Last edited by Scorbie on January 7th, 2015, 12:04 pm, edited 1 time in total.

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 12:02 pm

codeholic wrote:I'd really love if Bellman handled eater2 in a friendlier manner E. g. if a solution with an eater2 is found, all other eater2 variants in the same position are pruned.
It's the same problem with redundant solution. It's not about the eater, but the fact that bellman reports the same solution in million variants, because single cell that has "some influence" of the interaction considered part of catalyst, and should be removed if it has no influence on the result.

NOTE Why do you call it eater2? In wiki the eater called iter1

iter2 is this one, and bellman doesn't seems to have problem with it.
Last edited by simsim314 on January 7th, 2015, 12:21 pm, edited 1 time in total.

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 12:06 pm

Scorbie wrote:why don't you add stable-interval 1 instead of 10?
Stable interval 1 will make sure that the catalysts survives for extra generation. So the iterator will still not reach generation 23. Surviving 10 generations in P23 oscillator seems logical anyway, and a good balance to insure most of the searches will reach generation 23, on the other hand doesn't disregards too many cases.

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

Re: Bellman

Post by Scorbie » January 7th, 2015, 12:07 pm

@simsim314
there are many close variants to the eater2 , and bellman reports every one of them. Mentioned in the documentation file.

@simsim314 yup...

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 12:48 pm

Why this one doesn't find eater2 (the real one)?

Code: Select all

#S last-encounter 60
#P 0 0
............................
............................
...@........................
....@.......................
..@@@.......................
.......@....................
........@...................
......@@@...................
...........@................
............@...............
..........@@@...............
...............@............
................@...........
..............@@@...........
............................
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
............................
............................

EDIT Added the last encounter to increase the max-gen. It should be part of the "survive until generation flag".

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

Re: Bellman

Post by codeholic » January 7th, 2015, 1:52 pm

I also wish Bellman had more symmetry options (in particular, D2 diagonal)

@simsim314 I meant eater2. It has so many variants, that it slows down the search significantly.
Ivan Fomichev

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

Re: Bellman

Post by simsim314 » January 7th, 2015, 4:28 pm

@codeholic Can you bring an example where eater2 is harming the performance of the search?

NOTE: Do you know why bellman failed to find eater2 in the 4 glider array case I posted?

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

Re: Bellman

Post by codeholic » January 7th, 2015, 5:23 pm

simsim314 wrote:@codeholic Can you bring an example where eater2 is harming the performance of the search?

Take even snark (inputs/snark.in). If you remove two dots surrounded by '?' the search will take much longer. That's why I usually make a sample run with low number of active cells first (max-active 4 finds an eater2), and after that I replace one of the cells where eater2's block should be, with a dot (usually the one that is closest to the stabilisation, this way you can still have eater1 at the same place).
simsim314 wrote:NOTE: Do you know why bellman failed to find eater2 in the 4 glider array case I posted?
Because the gliders are not on the same lane :wink:
If you arrange them correcly, you'll find it:

Code: Select all

#S last-encounter 60
#P 0 0
.
.
...@.
....@.
..@@@.
.
.......@.
........@.
......@@@.
.
...........@.
............@.
..........@@@.
.
...............@.
................@.
..............@@@
............................
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
................?????????...
............................
............................
Ivan Fomichev

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

Re: Bellman

Post by dvgrn » January 7th, 2015, 10:47 pm

codeholic wrote:
simsim314 wrote:NOTE: Do you know why bellman failed to find eater2 in the 4 glider array case I posted?
Because the gliders are not on the same lane...
Well, but the idea was to find something with the eater2's impressive multi-lane eating abilities:

Code: Select all

x = 22, y = 21, rule = B3/S23
bo$2bo$3o$5bo$6bo$4b3o$9bo$10bo$8b3o$13bo$14bo$12b3o3$15b2obo$15b2ob3o
$21bo$15b2ob3o$16bobo$16bobo$17bo!

MikeP
Posts: 105
Joined: February 7th, 2010, 9:51 am
Location: Ely, Cambridgeshire, UK

Re: Bellman

Post by MikeP » January 8th, 2015, 6:46 am

simsim314 wrote:(if we had github version I would make a pool request).
You can fork projects on Sourceforge too. Click on "Code" (at the top) and then "Fork" (in the left hand bar).
Scorbie wrote:2)There is this "envelope.exe" that's neither in the documentation nor looks like some test. What does it do?
It's a quick hack which evolves an input pattern for a given number of generations and then prints an output showing which cells it grew into during those generations. I use it to help me decide where to place the '?' regions.
codeholic wrote:According to MikeP, this one was fixed.
Actually, I said I'd fix it "soon", but real life intervened, so it hasn't been done yet. I'm sure I'll get to it at some point! Sorry about that. I'll post in this thread when it's been fixed.
simsim314 wrote:1. mkstill should work faster and start from smaller patterns and expand.
2. Filters should work for catalysts that don't reach the generation of the filter.
1: I think at the moment mkstill just iterates over the cells in a raster-scan-like order when choosing the next cell to search. It would probably benefit from a more intelligent search order.

2: Yes, you're right. Patterns should always be evolved until the generation number of the last filter, even when the search stops before that. Another thing I've been meaning to fix!

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

Re: Bellman

Post by simsim314 » January 8th, 2015, 7:43 am

Hey Mike thx for the reply.

Let me see if I manage to fork your project.

There is a small nuance that I've got now, not sure why it happens:

If you use this:

Code: Select all

#S last-encounter 60
#P 0 0
..............
...@..........
.@.@..........
..@@..........
..............
..............
.....??.?.....
.....??.???...
...........?..
.....??.???...
......?.?.....
......?.?.....
.......?......
..............
You'll get 0 results.

But adding the max-live value will solve it:

Code: Select all

#S last-encounter 60
#S max-live 200
#P 0 0
..............
...@..........
.@.@..........
..@@..........
..............
..............
.....??.?.....
.....??.???...
...........?..
.....??.???...
......?.?.....
......?.?.....
.......?......
..............
I guess the "official" recomendation should be - never leave parameters to their defaults. Instead set them to high/low number if you don't care.

EDIT Woops you can't set the repair-interval or the stable-interval to be too high as it really harms performance. And the issue was with max-live or maybe max-active.

EDIT2 Real life is known issue for game of life... hope it's something good.

MikeP
Posts: 105
Joined: February 7th, 2010, 9:51 am
Location: Ely, Cambridgeshire, UK

Re: Bellman

Post by MikeP » January 8th, 2015, 8:37 am

The default for max-live is only 10 which is too small to find the eater2.

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

Re: Bellman

Post by simsim314 » January 8th, 2015, 10:00 am

OK this one did work and manage to find eater2 without any residual junk.

Code: Select all

#S last-encounter 60
#S max-live 500
#S max-active 800
#S repair-interval 50
#S stable-interval 15
#P 0 0
.........................
..@......................
...@.....................
.@@@.....................
......@..................
.......@.................
.....@@@.................
..........@..............
...........@.............
.........@@@.............
..............@..........
...............@.........
.............@@@.........
.........................
.........................
................???????..
................???????..
................???????..
................???????..
................???????..
................???????..
................???????..
.........................
Comments:

last-encounter 60 - is a hack to increase max_gen (not sure if helps).

max-live 500 - should be always set for any serious search, as the default is not enough.

max-active 800 - don't care and don't trust the default. Probably should be optimized for real search. One of the ways to increase performance without reducing the results too much.

repair-interval 50 - as the time it takes between the first glider to collide and the las block to regenirate is 47 geenrations, the eater will be considered by bellman in active state for all this time. This is the most influential parameter as it comes to performance.

stable-interval 15 - not setting this parameter will yield a lot of junk.

---

NOTE The repair interval is sort of depth of recursion, so it always should be set, and deepend step by step. the max-active parameter, is sort of hack to minimize the time waste for large repair intervals. So the proccess of search should consist of:

1. Increase repair-interval one by one. Set other parameters to large values.
2. If repair-interval is too large and the search takes way too long, set the repair-interval to be large and the max-active to some low value, and increase it one by one.

NOTE One could use repair-interval 5 and stable-interval 1 for eater2 search, get a lot of junk, and in it there would be eater2 among other things. The search would take so much less time, but it will be much harder to find eater2 in all the junk.

NOTE2 What I'm getting from expirience thus far, is that bellman is not "passive" magical search tool, that you can feed with any input and it will find something already. The major limitation of bellman is the depth of the search (the recovery time). The longer the recovery time is, the deeper the search will be. As this parameter influence performance exponentially, one can't just hope the default would suffice, almost always one would get either no results or too many irrelevant results. So this fine tuning is sort of art that should be mastered in order to use bellman effitiently.

---

Finally here are some variations on eater2 I've found with WinLifeSearch (using bellman output - Sokwe's trick):

Code: Select all

x = 90, y = 30, rule = B3/S23
4$4bo29bo29bo$5bo29bo29bo$3b3o27b3o27b3o$8bo29bo29bo$9bo29bo29bo$7b3o
27b3o27b3o$12bo29bo29bo$13bo29bo29bo$11b3o27b3o27b3o$16bo29bo29bo$17bo
29bo29bo$15b3o27b3o27b3o$23b2o$23bo59b2o$18b2obobo24b2obo2bo23b2obo2bo
$18b2ob2o25b2ob4o23b2ob2o2$18b2ob2o25b2ob2o25b2ob2o$19bob2o26bob2o23bo
2bob2o$16b3o30bo26b2o$16bo31b2o!
EDIT Turns out that bellman does support multiple encounters with fast repair interval, as small repair-interval. I.e. four gliders would be considered four interactions each one of them with small repair interval. So to insure only etaer2 is reported in 4 lanes case, one should only make the stable-interval large enough so that the two collision will fail this parameter, and one can use repair-interval with small value (i.e. 6).
Last edited by simsim314 on January 10th, 2015, 2:25 pm, edited 3 times in total.

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

Re: Bellman

Post by Scorbie » January 8th, 2015, 10:27 am

Thank you. That's really helpful.

Post Reply