ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Bellman

For scripts to aid with computation or simulation in cellular automata.

Re: Bellman

Postby Kazyan » February 20th, 2015, 11:40 pm

I've noticed that Bellman re-discovers the same solutions repeatedly when there are extraneous cells that have to be determined alive or dead, but don't actually affect the evolution of the pattern. This seems to happen when 6 cells around a target square are determined to be dead, but the remaining two consist of a nearby live cell from one part of the catalyst (active or otherwise) and a "?" cell. Is there a way to tell Bellman that the "?" cell doesn't need to collapse its waveform, so to speak, or will that just slow down the program with If statements and workaround code?
Tanner Jacobi
User avatar
Kazyan
 
Posts: 843
Joined: February 6th, 2014, 11:02 pm

Re: Bellman

Postby simsim314 » February 21st, 2015, 4:43 am

Kazyan wrote: Is there a way to tell Bellman that the "?" cell doesn't need to collapse its waveform


Bellman code is very simple and straight forward in this matter. Bellman can't know beforehand there will be a success, and as bellman is concerned it's different branch of the tree search.

I would prefer bellman just not to report those duplicates - i.e. to categorize better, and report solution only for new category. But it's still not straight forward - as categorizing currently can place few different solution into same category and it might increase the memory, if there are many "different" solutions.

There also might be better way to find the next cell to explore that could avoid this issue - but there is a cost as well, in complexity of code (and could cost more performance).
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Kazyan » February 21st, 2015, 6:07 am

simsim314 wrote:Bellman code is very simple and straight forward in this matter. Bellman can't know beforehand there will be a success, and as bellman is concerned it's different branch of the tree search.


Maybe I'm not explaining this well--I'm asking if Bellman can avoid splitting "?" cells into two branches of the search tree (regardless of if it will be a success in the end) when, in the immediate next generation, both branches will have the same effect. Example:

x = 8, y = 6, rule = LifeBellman
8E$8E$3E$2ED$2E3.2C$2E2.C2.C!


Say the red cell is a "?" cell. If I'm understanding the explanation MikeP posted that one time correctly, Bellman would split the search tree into two states when the white cell turns on, one where the red cell is alive and one where it is dead, and then keep chugging along. This is because it needs to determine the state of the dead cell between the red and the white. But this cell is already surrounded by 6 cells that are known to be dead--so theoretically, there's no reason to deal with the red cell's state at all; no matter if it is alive or dead, the cell between it and the white cell will remain dead either way. If this is the only time the red cell's state comes into play, it should be a computation-saver because the search tree does not need to be evaluated through two "identical" branches instead of just one.

I'm aware that checking for this 6-dead situation every time will cause a global slowdown, but I've currently got Bellman running through many variants where this happens during a Herschel-related search at this moment. If it didn't do this, my results would look more like the bottom than the top:

x = 50, y = 70, rule = LifeBellman
50E$50E$50E$36E2C12E$34E.C5.9E$8E3.C22E.C2.2C.9E$8E3C.C8E8.2E4.C.C.C
2.8E$7E7.E.3C2EC2.2C2.C2EC2.C.C7.6E$7E2C.2C4.C2.C4.2C3.2E3.2C9.5E$7E.
C.2C17.E15.5E18$28.3A$29.A$27.3A11$50E$50E$50E$36E2C12E$34E.C5.9E$8E
3.C22E.C2.2C.9E$8E3C.C8E8.2E4.C.C.C2.8E$7E7.E.3C3E2.2C2.4E2.C.C7.6E$
7E2C.2C4.C2.C4.2C3.2E3.2C9.5E$7E.C.2C17.E15.5E18$28.3A$29.A$27.3A!


...or do I just have a totally wrong conception of how Bellman works? Because if I do, I'll stop.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 843
Joined: February 6th, 2014, 11:02 pm

Re: Bellman

Postby simsim314 » February 21st, 2015, 10:59 am

Kazyan wrote:-I'm asking if Bellman can avoid splitting "?" cells into two branches of the search tree...when, in the immediate next generation, both branches will have the same effect.


Bellman split cells only when the intermediate generation is undetermined. Most of the time gaining only one extra generation until all the universe becomes unknown again. Only very few times when the universe becomes known can bellman decode whether there is a solution or a failure.

In other words at the moment the "split" was done, all the options seemed possible because usually there would be many unknowns around and that's it (this is exactly the place where bellman do its split - on the "border" between the known and unknown, "pushing" the unknown a bit further).

If bellman could determine whether the cell is dead or alive - it won't try to "split" it. Only the unknown states at some generation (neighboring already known cells) will split. So the answer is: there could be some cases when switching to 1 and to 0 will be the same, and this could optimize bellman a little bit - but the chances are they both bring almost the same amount of unknown on the next generation, so most of the time it's impossible to use information from the next generation for anything (maybe only in 0.01%), because the next generation most of the time remain almost entirely unknown, except of few cases.

What causing the extra results is that few different branches that at the beginning were unknown, "converge" into very similar solution from "different paths", and bellman couldn't do anything about the split at the time of the split because most of the universe at that time was unknown.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Kazyan » March 3rd, 2015, 1:15 am

Is there a way to get Bellman to not report solutions of Type 1? I left my computer for a few hours while Bellman was examining an R-pentomino and now I have a directory full of 1.4 million Type 1 solutions, and from experience, I'm pretty sure they're all just SL configurations of the same thing. This makes the actual search results unusable; Windows chokes on directories that large.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 843
Joined: February 6th, 2014, 11:02 pm

Re: Bellman

Postby simsim314 » March 5th, 2015, 4:02 am

Kazyan wrote: I have a directory full of 1.4 million Type 1 solutions


I'm aware of the problem, also had it few times. Can you please post the .in file?
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Kazyan » March 16th, 2015, 7:48 am

simsim314 wrote:I'm aware of the problem, also had it few times. Can you please post the .in file?


This should start acting up within one minute.

#S repair-interval 6
#S stable-interval 6
#S max-live 500
#S max-active 6
#S first-encounter 25
#S last-encounter 35

#P 0 0
.............@@@
...@@.......@...@
...@..@.....@@.@@
....@@@
.........................?????..
@@.@.@@.................??????
@.@@.@.................???????
.....@...............?????????
.....@@.............??????????
.................?????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.........?????????????????????
.
.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 843
Joined: February 6th, 2014, 11:02 pm

Re: Bellman

Postby Scorbie » April 7th, 2015, 10:20 pm

The latest version of Bellman just freezes instead of showing an error message, So I'm not sure whether something is wrong or bellman is slow on updating the screen.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1380
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby simsim314 » April 13th, 2015, 5:52 pm

I've lately fixed the source of bellman and now it works fine - without giving the nasty false positives it gave previously.

I've also increased the size of the tile to 64x64 - it seems to improve the old bug concerning tiles.

NOTE If you don't compile yourself take the bellmanT64.exe. Here is a link to bellman version.

NOTE2 I didn't compile bellman.exe - so it's still the version with the bug. I also didn't noticed any significant performance decrease in for 64 tile height.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby biggiemac » April 14th, 2015, 1:42 am

When bellman determines the important region for a catalyst, would it be possible to have it first poll the catagolue for natural patterns that contain that region, and only use findstill if none exist?
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: Bellman

Postby codeholic » April 14th, 2015, 2:50 am

I think these are different tasks that I wouldn't mix up. It's quite easy to write a script that would match patterns fetched from "text census" against a catalytic center defined as two sets of off and on cells. I've been in fact considering to write one since Catagolue went online, but I've been too tired these days.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby simsim314 » April 14th, 2015, 5:28 pm

biggiemac wrote:would it be possible to have it first poll the catagolue for natural patterns


At the moment the catagolue will allow api to search for SLs with unknowns. For the moment we don't have any utility that make queries in the catagolue SLs. I've posted such request in the apgsearch thread, but it seems Adam is pretty busy these days.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby codeholic » April 16th, 2015, 2:23 pm

I've written a script to match patterns from Catagolue.

https://github.com/conwaylife/census-tools

Unfortunately the method of adding new pattern masks isn't convenient yet. (You need to specify 'wanted' and 'unwanted' cells in RLE.) I'll probably rewrite it as a Golly script and make it work with LifeBellman rule.

Here is an interesting eater2 variant that it matched: http://catagolue.appspot.com/object?apg ... rule=b3s23
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby codeholic » April 16th, 2015, 2:34 pm

@simsim314 Is there a way I can make BellmanReport.py work with the original bellman, given search results are located in an arbitrary folder?
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby simsim314 » April 16th, 2015, 2:41 pm

codeholic wrote: Is there a way I can make BellmanReport.py work with the original bellman, given search results are located in an arbitrary folder?


I'm not sure what is your request? Just place the original bellman.exe in the BellmanReport.py folder. It should work I think.

Another point is that the current bellman bugs (although I fixed them in the latest version) have nothing to do with BellmanReport.py. So you can take bellman.exe just for the BellmanReport.py.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby codeholic » April 16th, 2015, 2:51 pm

simsim314 wrote:I'm not sure what is your request? Just place the original bellman.exe in the BellmanReport.py folder. It should work I think.

I don't use BellmanWin, but the original Mike Playle's version. Maybe I have a different problem, anyway. That's what I'm getting when I try to run BellmanReport.py from Scripts/Python folder:
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/Users/ifomichev/Downloads/golly-2.6-mac109/Scripts/Python/BellmanReport.py", line 257, in <module>
    Place(dir)
  File "/Users/ifomichev/Downloads/golly-2.6-mac109/Scripts/Python/BellmanReport.py", line 215, in Place
    cats = FillCategories(path)
  File "/Users/ifomichev/Downloads/golly-2.6-mac109/Scripts/Python/BellmanReport.py", line 203, in FillCategories
    category = d["hash"]
KeyError: 'hash'

My result files are located in /Users/ifomichev/work/bellman and this is also the parameter that I'm entering in the dialog box. (I'm sorry if I ask too much instead of reading the code to understand what it does, maybe that would be a better idea :roll:)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby simsim314 » April 16th, 2015, 3:04 pm

codeholic wrote:I don't use BellmanWin, but the original Mike Playle's version.


BellmanWin is just more user friendly version. You can download the code and try to compile it for Linux (right?).

I see no good reason why it wouldn't work. I think you just need to compile it with GCC. Compilation batch files are part of the version as well. I would be glad to get feedback if it didn't compile at your system.

And as for your question - I'm not really sure why previous version of bellman doesn't work. The error message basically says - it couldn't use bellman.exe to generate categories. The call for bellman.exe in BellmanReport.py is at line 190 check out if the return result is reasonable.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby codeholic » April 16th, 2015, 3:26 pm

Thanks for the hint! After removing ".exe" and shell=True it worked.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby simsim314 » April 16th, 2015, 3:29 pm

codeholic wrote:Thanks for the hint! After removing ".exe" and shell=True it worked.


Great! Thanks for the feedback.

EDIT You're welcome to post the Linux version for BellmanReport.py to benefit other Linux users (I can also add it to the repository).

EDIT2 I really recommend to check out my latest bellman version as it is much faster than the original bellman (about X5-X10) - this is due to the fact Mikes bellman was running a lot of unknown universes (actually Mikes version runs 90% of the time entirely unknown universes). It also has less issues with the tile (I just increased the TILE_HEIGHT but many of bellman searches were crushing after a while just because of the tile bug - and fixing will require some work).
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Scorbie » April 16th, 2015, 8:48 pm

One minor thing: I have to press Enter after the search is finished. Why?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1380
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby Freywa » April 17th, 2015, 2:20 am

I think it's a remnant from debugging (as all Life search programs have to undergo) so as to see some technical information; such signals would not be printed out anywhere and would be deleted when the terminal closes.
Princess of Science, Parcly Taxel
User avatar
Freywa
 
Posts: 567
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

Re: Bellman

Postby simsim314 » April 17th, 2015, 3:53 am

Scorbie wrote:One minor thing: I have to press Enter after the search is finished. Why?


The main reason is if you run it directly from batch file you could see the results (the window will close automatically otherwise). I should add some finish calculation print, and "press any key...".

If this really bothers you, and you can compile bellman yourself: remove getchar(); on line 1095 from bellman.c
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Scorbie » April 17th, 2015, 4:09 am

simsim314 wrote:The main reason is if you run it directly from batch file you could see the results (the window will close automatically otherwise).
Oh, you made a CUI for Bellman??? There's run.bat in the .gitignore file but not on your repository. I don't mind the command line, but I'm curious what you put in the batch file.
simsim314 wrote:If this really bothers you, and you can compile bellman yourself: remove getchar(); on line 1095 from bellman.c
Thanks for the tip! Did see that getchar() was the only one inside main() but wasn't sure whether I'm not doing something wrong.
simsim314 wrote:It also has less issues with the tile (I just increased the TILE_HEIGHT but many of bellman searches were crushing after a while just because of the tile bug - and fixing will require some work).
I'm not sure what you mean by this... Does it mean there still are problems, but less than the original?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1380
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby simsim314 » April 17th, 2015, 7:28 am

Scorbie wrote:There's run.bat in the .gitignore file but not on your repository.


Just place the usual bellman command line into any .bat file and double click it.

Scorbie wrote:Does it mean there still are problems, but less than the original?


Yes. you should now be aware that your borders are of size 64x64 and make the .in input based on this. Previously you had only 64x32 and it was jumping out of the tile much more frequently.

To be more exact you should place all your UNKNOWN cells into the same 64x64 square. You needed to do it previously with 64x32 square.
User avatar
simsim314
 
Posts: 1694
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Kazyan » April 23rd, 2015, 3:55 pm

I'm dumbfounded--after switching from Windows to Linux, BellmanWin keeps changing max-active to 10 regardless of what I tell it to be in the input file. The output files give the catalysts and everything, but max-active is 10, and I can tell because the search takes so long. The source is apparently unchanged...
Tanner Jacobi
User avatar
Kazyan
 
Posts: 843
Joined: February 6th, 2014, 11:02 pm

PreviousNext

Return to Scripts

Who is online

Users browsing this forum: No registered users and 1 guest