Bellman

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Bellman

Post by 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?

Code: Select all

#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

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

Re: Bellman

Post by 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:

Code: Select all

#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.

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

Re: Bellman

Post by 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

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

Re: Bellman

Post by 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.

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

Re: Bellman

Post by 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

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

Re: Bellman

Post by 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.

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

Re: Bellman

Post by 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

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

Re: Bellman

Post by 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

Post by 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. ... 820#p12820 which I think proves that the principle works!

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

Re: Bellman

Post by 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:

Code: Select all

#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).

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

Re: Bellman

Post by codeholic » August 2nd, 2014, 5:58 pm

That was really prompt! Thank you!
Ivan Fomichev

User avatar
Andrew
Moderator
Posts: 766
Joined: June 2nd, 2009, 2:08 am
Location: Melbourne, Australia
Contact:

Re: Bellman

Post by 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:

Code: Select all

#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.

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

Re: Bellman

Post by MikeP » August 5th, 2014, 4:48 am

Andrew wrote:

Code: Select all

#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

Post by MikeP » August 5th, 2014, 1:24 pm

MikeP wrote:I'll fix this later today.
Done!

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

Re: Bellman

Post by 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.

Code: Select all

#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
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Post by 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

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

Re: Bellman

Post by 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!

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

Re: Bellman

Post by 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.

Code: Select all

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 506 times

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

Re: Bellman

Post by 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
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Post by 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.
http://conwaylife.com/forums/viewtopic.php?p=8064#p8064
Ivan Fomichev

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

Re: Bellman

Post by 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.

Code: Select all

#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:

Code: Select all

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
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

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

Try borders of width 2 ;)
Ivan Fomichev

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

Re: Bellman

Post by 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
simsim314
Posts: 1731
Joined: February 10th, 2014, 1:27 pm

Re: Bellman

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

For some reason bellman ignores my filters.

Take a look at this .in:

Code: Select all

#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
codeholic
Moderator
Posts: 1142
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Bellman

Post by 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

Post Reply