Bellman

For scripts to aid with computation or simulation in cellular automata.
Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Bellman

Post by Sokwe » January 8th, 2015, 4:20 pm

I've always been somewhat confused about what the "max-active" parameter measures. is max-active a limit on the number of catalyst cells that can change each generation, or is it a limit on the total number of catalyst cells that can change through all generations. Does it count any "?" cell that changes, or does it only count cells that are alive in the catalyst?

For example, it seems that I need max-active set to 4 to find the eater 2. Why is that enough?
-Matthias Merzenich

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

Re: Bellman

Post by simsim314 » January 8th, 2015, 4:37 pm

I guess max-active is maximal active cells in specific generation. It's made to fast filter "explosions" (according to documentation). Eater2 at each generation of the "consumption" differs maximum 4 cells from the original (I guess the dead cells that become live cells also counts "active").

If I'm right, this one differs by 4:

Code: Select all

x = 9, y = 7, rule = B3/S23
2bo4b2o$3bobo2bo$3b4o$3bo$2b2ob2o$o2bob2o$2o!

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Bellman

Post by Sokwe » January 8th, 2015, 11:23 pm

simsim314 wrote:I guess max-active is maximal active cells in specific generation. It's made to fast filter "explosions" (according to documentation). Eater2 at each generation of the "consumption" differs maximum 4 cells from the original (I guess the dead cells that become live cells also counts "active").
I think you're right. Of course, I'd still like to hear it from MikeP. This is the same sort of restriction that Dean Hickerson's drifter search uses.
-Matthias Merzenich

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

Re: Bellman

Post by codeholic » January 9th, 2015, 3:12 am

It's what this topic began from.
Ivan Fomichev

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

Re: Bellman

Post by simsim314 » January 9th, 2015, 5:01 am

Sokwe wrote:Dean Hickerson's drifter search
Another great search utility, that we don't hear too often about, but was involved in many GOL discoveries.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: Bellman

Post by Sokwe » January 9th, 2015, 5:32 pm

codeholic wrote:It's what this topic began from.
Well that's embarrassing! :oops:
-Matthias Merzenich

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

Re: Bellman

Post by simsim314 » January 9th, 2015, 7:18 pm

Some updates:
mkhtml.py.gz
(1.02 KiB) Downloaded 428 times

- with results sorted by filename (you now can go to the end of the html for latest results). Also fixed the path to work with all OS.

---
bellman.c
(44.07 KiB) Downloaded 433 times

- Filter is now behaves correctly for "?" (ignoring it)
- Evolving until the last filter. (In case the catalyst workes before the filter reached).

NOTE I'm using Scorbie version with all the image handling marked. Please note this detail for merging.

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

Re: Bellman

Post by simsim314 » January 10th, 2015, 12:46 pm

Great news for those who want to compile bellman on other OS and don't like the dependency on image library, but still want nice report (especially useful for "give me all the junk" approach).

I've created BellmanReport.py script for golly, that has most of the nice features of the html report inside golly. The script creates new rule, and allows evolving bellman output results inside golly. It only needs bellman.exe in the same folder (to categorize the output files - exactly as mkhtml.py does).

I've also created a repository on github for the new bellman version, that has no unusual external dependencies (thx to Scorbie - BTW I would like to add you as contributer, but not sure how to address you).

===

EDIT As for new feature requests for bellman I think I would like to have more advanced filtering mechanism:

1. Negative filter: report everything which doesn't correspond to the filter (mainly used to get "non empty" results).
2. Add state to filter that will mean: the cell can be part of the Catalyst OR dead/alive. Say we want pure eater but we don't want to filter the catalyst cells.
3. For oscillator search it would be nice to define a cell as "not stable" - probably we'll need a range of generations.
4. Something like "Locators" in LifeAPI. Option to define a search for pattern, independent of generation/position. Maybe also auto removal will be nice, but for starters just an indication the pattern exists sometimes somewhere.

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

Re: Bellman

Post by simsim314 » January 10th, 2015, 6:52 pm

Few updates on new bellman version:

1. Stabilization and re-ignition case handle added. Now you can search for eater2 (using four lane glider input) setting the repair-interval to 4 and stable interval to 15. Previously bellman was counting from the very first encounter 15 generations. Now it counts from the last re-ignition 15 stable generations.

In simple words - using low repair-interval will now give you a bit more good results than previously.

2. Symmetry is now truly optimized without doing any extra job. Bellman was turning ON the same "cell pairs" many times, in symmetrical searches, losing a lot of time on the same case (as the search is recursive, this was serious performance issue for symmetrical searches), now it fixed.

This includes also small bug fix: the max-live of symmetrical case was handles as single case (while turning two cells ON). This was fixed - but beware, some previous searches that somehow enjoyed the bug might not work now - if you set max-live to be too low. If you did symmetrical searches, just double the max-live value now.

I run codeholics p29 finding to make sure I didn't screw up anything. Looks nice and works pretty fast.

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

Re: Bellman

Post by Scorbie » January 10th, 2015, 8:47 pm

BellmanReport.py seems to have some typos.
At line 131, is g.setrule("LifeBellman") in where it should be? Golly throws Errors because it there isn't a rule called LifeBellman. (CreateRule not executed?)
Last edited by Scorbie on January 11th, 2015, 6:43 am, edited 1 time in total.

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

Re: Bellman

Post by simsim314 » January 11th, 2015, 3:46 am

Scorbie wrote:s g.setrule("LifeBellman") in where it should be?
Woops.... The rule generator wasn't called + the generated rule didn't work (I forgot new line character).

Now fixed and I made sure to works properly. The report itself looks very nice.

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

Re: Bellman

Post by Kazyan » January 21st, 2015, 2:28 am

The latest version of Bellman is acting weird. I ran a simple "let's see what you can do to this Pi" life through it, and it kept giving false positives--catalysts that completely disintegrate are reported as successful. The one I got about a week ago doesn't have this problem, except that the symmetry doesn't work.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

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

Re: Bellman

Post by simsim314 » January 21st, 2015, 2:39 am

Kazyan wrote:The latest version of Bellman is acting weird.
Yes sorry, I had a bug that gave wrong results for few days. Now it's fixed.

I can say the current version is working well and very fast (about x3-x10 times faster than the original) - I was getting deep into the search core to scratch some more performance improvements and small (and very stupid) bug that I missed was accidentally committed (I ran checks for codeholic's p29 and snark - and it worked...I noticed the bug only when I ran search on Hersch). Anyway everything is working properly now.

By the way the symmetry definition now is a bit different:

You need to use one of those:

#S symmetry-horiz-even 10
#S symmetry-vert-even 10
#S symmetry-horiz-odd 10
#S symmetry-vert-odd 10

It's preparation made to allow more types and more complex types of symmetries.

In few days I hope to add all the common symmetries and post an update.

---

EDIT As for performance improvements:

I made an optimization based on the fact that universe of unknowns (or no active cells with many unknowns) has no information and doesn't need to be iterated any further. This improved ballman performance drastically, especially where max-gen was getting a bit high (try to run with old bellman something with max-gen of 150, and first encounter < 10).

I also added an option to bellman iterator that stable data should not be calculated and just remain the same. This actually gave extra 10%, not so major improvement -but for large universes it is very significant.

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

Re: Bellman

Post by simsim314 » January 21st, 2015, 7:51 am

I think next I must handle the tile wrap and messaging system for bad inputs. Here is a sample I even didn't managed to run with any setup I could think of, and any trick that came into my mind (like adding stable cells on edges or increasing the wrap, removing the symmetry etc.).

Code: Select all

#S first-encounter 10
#S last-encounter 38
#S repair-interval 12
#S stable-interval 2
#S max-live 60
#S max-active 10
#S symmetry-horiz-odd 20
#P 0 0
..........................................................................
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
.........@...............................@.........?????????????????????..
.........@...............................@.........?????????????????????..
.........@...............................@.........?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
.....@.......@.......................@.......@.....?????????????????????..
...@@.@@...@@.@@...................@@.@@...@@.@@...?????????????????????..
.....@.......@.......................@.......@.....?????????????????????..
...................................................?????????????????????..
.....@.......@.......................@.......@.....?????????????????????..
...@@.@@...@@.@@...................@@.@@...@@.@@...?????????????????????..
.....@.......@.......................@.......@.....?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
.........@...............................@.........?????????????????????..
.........@...............................@.........?????????????????????..
.........@...............................@.........?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
...................................................?????????????????????..
..........................................................................
..........................................................................
#F 41 35 17
..*.......*...
**.**...**.**.
..*.......*...
..............
..*.......*...
**.**...**.**.
..*.......*...
It crashes after minute of run.

NOTE Notice I use the new symmetry notation... but it's really doesn't matter.

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

Re: Bellman

Post by Scorbie » January 21st, 2015, 9:10 pm

Just out of curiosity, "why" do we need to handle tile wrap when it's a perfectly valid input?
Last edited by Scorbie on January 22nd, 2015, 9:38 am, edited 3 times in total.

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

Re: Bellman

Post by simsim314 » January 22nd, 2015, 2:10 am

I meant I need to fix this tile-wrap issue. Sometimes you simply can't use bellman at all because of it.

I thought it was just annoying nuance, and I could live with that - but the example above shows its blocking bellman from working at all in some cases.

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

Re: Bellman

Post by Scorbie » January 22nd, 2015, 9:41 am

I wrote:Just out of curiosity, "why" do we need to handle tile wrap when it's a perfectly valid input?
I should have been clearer. What I tried to say is this:
"Why" do the tile-wrapping problems occur, despite the input being perfectly valid?

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

Re: Bellman

Post by simsim314 » January 22nd, 2015, 11:12 am

I was recently looking into the code that deals with tiles.

Turns out that bellman divide the universe into rectangles of 64x32 (64 is the length), and they called tiles. Currently bellman can't have unknown stables in two different tiles, more precisely it doesn't support switching the cells ON and OFF in two different tiles. But it doesn't always need to do any switching to unknown stable, as it has optimization to switch only cells that are adjacent to active cells in some generation (this is why snark worked, all the switched unknowns were in the same tile). The reason is that Mike just didn't finish this part - as he thought it's not that crucial (and I guess he didn't understood the consequences).

So in order to make something like the sample above to work, one needs to place all the unknowns into some place where all of them would be inside the same 64x32 tile. This is of course temporary solution (I'll introduce the full fix in couple of days hopefully) , but here is sample of the same input that will work with current bellman:

Code: Select all

#S first-encounter 20
#S last-encounter 38
#S repair-interval 25
#S stable-interval 10
#S max-live 60
#S max-active 14
#S symmetry-vert-odd 27
#P 0 0
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.........................@...@.........................
.........................@...@.........................
........................@.@.@.@........................
.........................@...@.........................
.........................@...@.........................
.......................................................
.................@@@...............@@@.................
.......................................................
.........................@...@.........................
.........................@...@.........................
........................@.@.@.@........................
.........................@...@.........................
.........................@...@.........................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.........................@...@.........................
.........................@...@.........................
........................@.@.@.@........................
.........................@...@.........................
.........................@...@.........................
.......................................................
.................@@@...............@@@.................
.......................................................
.........................@...@.........................
.........................@...@.........................
........................@.@.@.@........................
.........................@...@.........................
.........................@...@.........................
.......................................................
.......................................................
.......................................................
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
..???????????????????????????????????????????????????..
.......................................................
.......................................................
#F 41 24 51
.*...*..
.*...*..
*.*.*.*.
.*...*..
.*...*..
........
........
........
.*...*..
.*...*..
*.*.*.*.
.*...*..
.*...*..
........
The reason this works is because the unknowns are all inside the same tile placed at (0, 64).

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

Re: Bellman

Post by Kazyan » February 7th, 2015, 12:16 am

The newest version of Bellman is still giving me grief. Catalysts that disintegrate are still reported as solutions. What's more, sometimes Bellman will stop printing updates to the console and no new solutions will appear. I'm using an older, less efficient version due to these issues.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

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

Re: Bellman

Post by simsim314 » February 7th, 2015, 1:15 pm

Kazyan wrote:The newest version of Bellman is still giving me grief.
Sorry I'm aware of that - didn't took the time to see into the problem though. I'm using the newer version, and although I get those annoying false positives, I still get nice results most of the time. But I can't guarantee anything, so yes better use older version.
Kazyan wrote:What's more, sometimes Bellman will stop printing updates to the console and no new solutions will appear.
This probably means the search had finished. Just press some key to make sure. I'll add some print to indicate termination.

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

Re: Bellman

Post by Kazyan » February 7th, 2015, 1:29 pm

simsim314 wrote:Sorry I'm aware of that - didn't took the time to see into the problem though. I'm using the newer version, and although I get those annoying false positives, I still get nice results most of the time. But I can't guarantee anything, so yes better use older version.

This probably means the search had finished. Just press some key to make sure. I'll add some print to indicate termination.
Alright. Thank you for all your coding work! This stuff's hard.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: Bellman

Post by David » February 16th, 2015, 3:16 am

Excuse me...
I've compiled Bellman on Windows 8.1 (using MinGW and Code::Blocks), but I don't know how to view output files.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

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

Re: Bellman

Post by simsim314 » February 16th, 2015, 6:04 pm

David wrote:but I don't know how to view output files.
Take a look at this script. To run place it in golly scripts folder together with bellman.exe.

David
Posts: 212
Joined: November 3rd, 2009, 2:47 am
Location: Daejeon, South Korea

Re: Bellman

Post by David » February 18th, 2015, 12:00 am

simsim314 wrote:Take a look at this script. To run place it in golly scripts folder together with bellman.exe.
Doesn't work. It simply draws the string I inputed.
Call me "Dannyu NDos" in Forum. Call me "Park Shinhwan"(박신환) in Wiki.

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

Re: Bellman

Post by simsim314 » February 20th, 2015, 11:19 am

Did you entered the directory folder with all .out files and placed bellman.exe into the folder with this script?

If yes: what operating system are you on?

Post Reply