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.

Bellman

Postby codeholic » July 4th, 2013, 4:56 am

I believe, there is no such a thread yet, but probably it makes sense to make one.

My particular question is why Bellman doesn't find the eater 3 with this input. (The pattern is a part of the rectifier.) Are search criteria too restrictive, or does Bellman simply not do exhaustive search within given criteria?

#S first-encounter 2
#S last-encounter 35
#S repair-interval 25
#S stable-interval 5
#S max-live 50
#S max-active 8
#P 0 0
............................
............................
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..?????????????.............
..????????????..............
..???????????....@@@..@@@...
..................@@..@@@...
...................@..@@....
............................
............................
............................


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

Re: Bellman

Postby MikeP » July 5th, 2013, 6:04 am

At its most active, 9 cells of the eater3 differ from its stable state. This happens twice: once when the loaf has been flipped over and is starting to interact with the pre-block, and again 2 generations later.

So max-active needs to be at least 9 to find an eater3.

One way to investigate questions like this is to tell it exactly what you want it to find. Here's an input file which fails to find the eater3, based on your search parameters but with a different pattern:

#S first-encounter 2
#S last-encounter 35
#S repair-interval 25
#S stable-interval 5
#S max-live 50
#S max-active 8
#P 11 11
................@
...............@
...............@@@

..............
..........??..
.....??..?..?.
..?..?....?.?.
.?.?.?.....?..
..?..?.??.....
.....?..?.....
......?....?..
.......?????..
..............
.........?....
........?.?...
.........?....
..............


As it stands this input file finds nothing, but increase max-active to 9 and the eater3 appears.
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby codeholic » July 5th, 2013, 6:59 am

MikeP wrote:At its most active, 9 cells of the eater3 differ from its stable state. This happens twice: once when the loaf has been flipped over and is starting to interact with the pre-block, and again 2 generations later.

Thank you very much for the explanation. There has been misunderstanding on my side. I thought that "the number of cells in the catalyst which are permitted to differ from their stable state" refers only to live cells, and also I thought that it refers to the number of differing cells in all generations overall, not in every particular generation. Now it's much clear.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby MikeP » July 5th, 2013, 7:09 am

To be specific, it counts either live cells, or dead cells which are adjacent to a live cell.
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby codeholic » July 28th, 2014, 6:06 am

Mike, would it be much trouble to add an option to Bellman to run in symmetrical modes (similarly to JLS or gfind)? I wonder, if Bellman could find interesting perturbations of the pre-pulsar.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby MikeP » August 2nd, 2014, 4:39 am

Yes, that ought to be doable. I think the easiest way to do this will be to modify bellman_choose_cells() to find the image(s) of the chosen point under the various symmetries and set them all at once before recursing.

Should it insist that the input pattern matches the symmetry constraints? Clearly the unknown '?' region should be symmetric, but what about the evolving pattern? This doesn't have to be symmetrical, but it might be confusing to allow this, and I'm not sure there's much use for it.
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby codeholic » August 2nd, 2014, 5:09 am

MikeP wrote:Clearly the unknown '?' region should be symmetric, but what about the evolving pattern? This doesn't have to be symmetrical, but it might be confusing to allow this, and I'm not sure there's much use for it.

I think it wouldn't be too confusing, but it would probably result in worse performance and more complicated code without clear benefits. So I would assume that the whole input pattern should be symmetrical, including '?' cells, '@' and catalysts.

What I think is important is to be able to specify odd- or even-symmetry for the input pattern.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby MikeP » August 2nd, 2014, 5:15 am

codeholic wrote:I think it wouldn't be too confusing, but it would probably result in worse performance and more complicated code


Actually, with my proposed change it'll be about the same - Bellman will still evolve and validate the entire universe. Yes, it's doing redundant work, but then it does quite a bit of redundant work anyway by working with 64-bit wide tiles. The real benefit comes from restricting the search space.

Also I think that specifying filter patterns will be easier if they're allowed to be asymmetrical because the user won't have to worry about which region of the universe to put them in and/or how to flip and rotate them as appropriate.
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby MikeP » August 2nd, 2014, 6:04 am

codeholic wrote:I wonder, if Bellman could find interesting perturbations of the pre-pulsar.


A quick hack found http://conwaylife.com/forums/viewtopic.php?f=2&t=279&p=12820#p12820 which I think proves that the principle works!
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby MikeP » August 2nd, 2014, 7:24 am

The latest version of Bellman at https://sourceforge.net/projects/bellman/ adds basic support for a single axis of reflectional symmetry.

Example:
#S first-encounter 1
#S last-encounter 10
#S repair-interval 10
#S stable-interval 5
#S max-live 10
#S max-active 10
#S symmetry 6:horiz-odd
#P 0 0

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


The new "symmetry" parameter specifies the coordinate of the axis and the type (horiz-odd, horiz-even, vert-odd, vert-even). The PDF document explains it a bit more precisely (hopefully).
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby codeholic » August 2nd, 2014, 5:58 pm

That was really prompt! Thank you!
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby Andrew » August 4th, 2014, 8:18 pm

A couple of tips for Mac users who want to build Bellman:

1. Edit universe.c and replace the "#include <values.h>" line with this:
#ifdef __APPLE__
    #include <limits.h>     // for INT_MAX
    #define MAXINT INT_MAX
#else
    #include <values.h>
#endif


2. To install the gd library, download and install this:
http://code.google.com/p/rudix/download ... 0.35-0.dmg

Then run make and the code should compile without any problems.
User avatar
Andrew
Moderator
 
Posts: 716
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia

Re: Bellman

Postby MikeP » August 5th, 2014, 4:48 am

Andrew wrote:
#ifdef __APPLE__
    #include <limits.h>     // for INT_MAX
    #define MAXINT INT_MAX
#else
    #include <values.h>
#endif


Actually I think your way to do it is correct on all platforms, because INT_MAX is defined by the C standard but MAXINT doesn't seem to be defined anywhere as far as I can see from a quick bit of Googling.

I'll fix this later today.
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby MikeP » August 5th, 2014, 1:24 pm

MikeP wrote:I'll fix this later today.


Done!
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby Scorbie » November 9th, 2014, 2:46 am

Sorry to wake up an old thread... Could anyone help me with filter options with bellman?
Mine doesn't work with this input file. It works when there's no filter.
EDIT: It does work when the ? cells are deleted in the filter pattern... Still, I didn't quite understand how the filter works.
#S first-encounter 1
#S last-encounter 2
#S repair-interval 4
#S stable-interval 1
#S max-live 6
#S max-active 1
#P 0 0
......
..@...
...@..
.@@@..
......
......
...??.
....?.
...?..
...??.
......

#F 4 0 0
......
......
...*..
..*.*.
...**.
......
...??.
....?.
...?..
...??.
......
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby codeholic » November 10th, 2014, 3:24 am

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).
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby MikeP » November 10th, 2014, 6:25 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).


This is a bug. '?'s in the filter are meant to work as Scorbie expects - but looking at the code, there's no way it can work! I'll fix this soon. Thanks Scorbie!
MikeP
 
Posts: 81
Joined: February 7th, 2010, 9:51 am
Location: Cambridge, UK

Re: Bellman

Postby simsim314 » January 7th, 2015, 5:44 am

I've added a real time report for the mkstill - because sometimes I've wasted too much time on not interesting results waiting for mkstill to finish optimize something not important.

Use attached findstill.c (if we had github version I would make a pool request).

Now you can see the result in real-time, and stop mkstill (you can also test the pattern while mkstill continue to optimize).

---

Python script that converts golly state into bellman input.

Using the selection rectangle:
0->"."
1->"@"
2->"?"

Copies the result into clipboard.

import golly as g

rect = g.getselrect()

str = ""

for y in xrange(rect[1], rect[1] + rect[3] + 1):
   for x in xrange(rect[0], rect[0] + rect[2] + 1):
      if g.getcell(x, y) == 1:
         str += "@"
      if g.getcell(x, y) == 0:
         str += "."
      if g.getcell(x, y) == 2:
         str += "?"
   str += "\n"
g.setclipstr(str)
Attachments
findstill.c
(6.02 KiB) Downloaded 373 times
User avatar
simsim314
 
Posts: 1640
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby Scorbie » January 7th, 2015, 8:40 am

Just some questions:
1)In my computer, bellman crashes almost every pattern I feed in. It says something like:
Handle tile wrap: (10,8) something
What does it mean and what should I do?
2)There is this "envelope.exe" that's neither in the documentation nor looks like some test. What does it do?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby codeholic » January 7th, 2015, 9:00 am

Scorbie wrote:1)In my computer, bellman crashes almost every pattern I feed in. It says something like:
Handle tile wrap: (10,8) something
What does it mean and what should I do?

This question has been already answered.
MikeP wrote:Yes, it's a bug (or at least something that hasn't been implemented yet). I need to find some time to update it to fix this and a few other issues - at the time I thought it was more important to get it online so that others could try to use it. Sorry about that!

As codeholic points out, you can work around it for now by making sure there are no '?' cells at the edges of the pattern by adding a border of '.'s.

viewtopic.php?p=8064#p8064
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby Scorbie » January 7th, 2015, 9:08 am

According to codeholic, MikeP wrote:As codeholic points out, you can work around it for now by making sure there are no '?' cells at the edges of the pattern by adding a border of '.'s.
Oh, I already wrapped the cells with "." cells with every input file and it still gives me errors.
Here's a typical input file of mine and it gave me this error after... um... about 10 minutes.
#S first-encounter 5
#S last-encounter 13
#S repair-interval 14
#S stable-interval 4
#S max-live 50
#S max-active 13
#P 0 0
.........................
...?????????.............
..???????????............
.?????????????...........
.?????????????...........
.?????????????...........
.????????????....@@......
.??????..........@@......
.??????..@...............
.........@...............
........@.@..............
...@@....@.........@.....
...@@....@.......@@.@@...
...................@.....
.........................
.........................
.........................
.........................
.........................
.......@.................
.....@@.@@.......@....@@.
.......@.........@....@@.
................@.@......
.................@.......
.................@.......
........@@...............
........@@...............
.........................
.........................

#F 23 8 8
.*.
.*.
*.*
.*.
.*.
And here's the error file:
TODO: handle tile wrap! (11, 0, 4)
Dumping 0
   000:
   001: EXPAND_UP EXPAND_LEFT IS_DEAD DIFFERS_FROM_PREVIOUS DIFFERS_FROM_2PREV IS_LIVE
   002: EXPAND_UP EXPAND_LEFT IS_DEAD DIFFERS_FROM_PREVIOUS DIFFERS_FROM_2PREV IS_LIVE
   003: EXPAND_UP EXPAND_LEFT IS_DEAD DIFFERS_FROM_PREVIOUS DIFFERS_FROM_2PREV IS_LIVE
   004: EXPAND_UP EXPAND_LEFT IS_DEAD DIFFERS_FROM_PREVIOUS DIFFERS_FROM_2PREV IS_LIVE
Goes on for about 50 lines...
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby codeholic » January 7th, 2015, 9:13 am

Try borders of width 2 ;)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Postby Scorbie » January 7th, 2015, 9:19 am

codeholic wrote:Try borders of width 2 ;)
Laughing Out Loud. I'll hope that works :wink:
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: Bellman

Postby simsim314 » January 7th, 2015, 9:29 am

For some reason bellman ignores my filters.

Take a look at this .in:

#S repair-interval 10
#S last-encounter 20
#P 10 10
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
..............@@@............@@@..............
..............@.@............@.@..............
..............@@@............@@@..............
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
................@@@........@@@................
................@.@........@.@................
................@@@........@@@................
..............................................
..............................................
..............................................
................@@@........@@@................
................@.@........@.@...??????????...
................@@@........@@@...??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
.................................??????????...
..............@@@.....??????.@@@.??????????...
..............@.@.....??????.@.@.??????????...
..............@@@.....??????.@@@.??????????...
......................??????.....??????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
......................?????????????????????...
..............................................
..............................................
..............................................
#F 23 39 50
......
.***.?
.*.*.?
.***.?
.....?
#F 23 37 41
......
.***.?
.*.*.?
.***.?
.....?


I added two filters to avoid many trivial solutions. But bellman reports all the solutions, into .out format.

Am I missing something, and the .out is not bound by the filters?
User avatar
simsim314
 
Posts: 1640
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

Postby codeholic » January 7th, 2015, 9:37 am

I see you made borders of width 3 just in case :)

simsim314 wrote:But bellman reports all the solutions, into .out format.


I don't know for sure, because I didn't look into the source code, but my guess is that you need to specify all filters, if you want to filter results somehow (if you don't need a certain filter, you can still put it there just with an exaggerated number).
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Next

Return to Scripts

Who is online

Users browsing this forum: No registered users and 2 guests