ConwayLife.com

The latest version is here. The information below is obsolete.

--------

I would like to present my new half-baked search program, CopperSearch.

As trivial as it sounds, the program runs all small patterns with some kind of symmetry and checks if they repeat, possibly with some offset. And as surprising as it sounds, this algorithm has never been implemented before. (Proof: if it had, the implementation would have found Copperhead.)

The current version may contain errors (although I have tested it) and definitely has the following disadvantages:

• Only runs under Windows.
• Tests only about 500-700 patterns per second.
• B3/S23 is hardcoded.

You can join a distributed search here or ask me for instructions on how to run a custom search.

Have fun!

how2search? all it does is halt at "This is CopperSearch version 0.2", even when I specify the field file.

I think gsearch was supposed to work this way. Unfortunately it hasn't found the c/10 spaceship for some obscure reason.

>sees new spaceship is discovered
>it looks like a snake
>copper is my favourite metal
>there is a copperhead snake
>name ship copperhead
>search program called copper search is created
>profit


In all seriousness, I'm going to try this out tomorrow. Up until this point being a Windows PC owner has been somewhat unforgiving, so I'll see how this is like

So apgnano & apgmera are both able to run substantially more soups per second than cs. Yet all that cs is doing is checking for repeating behavior. Is there anything in cs that couldn't just be done by tweaking the soup generator for apgnano? Because any pattern that acts as a small medium-period spaceship will be censused as such, and similarly for ship ancestors, ship + SL..

Basically, Adam has built this great platform for evolving and censusing B3S23 life really fast, and lots of other nifty search programs could be built rather painlessly from just modifying it. An exhaustive search of all 33-cell patterns within a specific bounding box, for example, that doesn't report to catagolue and only says anything to the user if the pattern begins xqN for N > 4, seems pretty easy.

biggiemac: Unfortunately, I don't know C, and therefore I'll mess everything up if I try to modify apgnano so seriously. If anyone else were willing to do the hack, I would trash CopperSearch immediately and switch to their program. For now, however, CopperSearch is what we have.

Anyway, I was going to describe the algorithm in more detail.

How does it work?

CopperSearch starts by loading a .field file. The file contains an array of dots (dead cells), asterisks (live cells), and variables, which can be numbers or case-sensitive letters. The symmetry is imposed by using each variable more than once:
If you search a part of the search space, some variables are held constant while other ones change.

To find a period of a pattern, CopperSearch does the following:

• Run the pattern for 22 generations without checking anything.
• Save this generation to memory.
• Run the pattern further, comparing it with the pattern in memory.
• If the patterns ran for 41 gens and doesn't seem to be periodic, discard it.
• If the pattern has period 1,2,3,4,5,6,8, or 15, discard it.
• Otherwise, save it.

The program does not distinguish oscillators and spaceships.

How do I use it?

If you want to run your own search, create the field file in the folder where the program sits. A simple way to do this is to add title to the field like I did above, copy everything, run cs, and enter save. The .field file will then be created automatically.

Then you run cs and enter search <field title> <part>/<number of parts>.

biggiemac wrote:Basically, Adam has built this great platform for evolving and censusing B3S23 life really fast, and lots of other nifty search programs could be built rather painlessly from just modifying it. An exhaustive search of all 33-cell patterns within a specific bounding box, for example, that doesn't report to catagolue and only says anything to the user if the pattern begins xqN for N > 4, seems pretty easy.

It was pretty easy to do with the old Python-based apgsearch, anyway. I had no trouble making the necessary changes to substitute an exhaustive enumeration for the random-hash soups.

-- Well, not much trouble, anyway: the patch worked, but it was fairly messy. I should probably try a little harder next time.

Even a rebuild of CopperSearch based on the old Python script apgsearch might be fairly competitive in terms of speed, I think. The Life generating algorithm in CopperSearch appears to be the simplest possible fixed-size-grid one -- well, the grid grows with the pattern, but I don't see any bit-twiddling or tiles or tracking-only-live-cells or other shortcuts -- so it's an order of magnitude or two slower than it could be.

And an apgsearch variant would certainly return a lot more information, and wouldn't miss as much good stuff -- like small diagonal c/8 spaceships, which it sounds like CopperSearch would just throw away...!

Of course, what I'd really like to see is a real distributed system, more along the lines of Catagolue, with a modified apgnano/apgmera reporting to it, and the server recommending unclaimed fractions of a huge search space to each instance of the client code, just as Alexey is doing manually in the other thread. It might be worth cloning Catagolue and modifying it, if someone wants to take on the project.

(I'm not counting on persuading Calcyman to clutter up the current system with that much new functionality -- Catagolue might already be enough of a maintenance nightmare for one person to handle, at least if the person has any other (real) Life plans.)

Could you describe a simple way to improve my trivial generating algorithm?

Try using 32-bit integers and bitwise operators to compute 32 cells in parallel. (Or does this language that you're using not have bitwise operators? If so, um....run?)

Thanks for doing this.

Out of curiosity, what is the rationale for throwing away period 8 and period 15?
Also, how much would it speed up the search to skip step 1, and do you think it might be worth it?

EricG wrote:Thanks for doing this.

Out of curiosity, what is the rationale for throwing away period 8 and period 15?
Also, how much would it speed up the search to skip step 1, and do you think it might be worth it?

The search with diagonal symmetry finds a figure eight approximately once every two seconds. An asymmetric search finds one pentadecathlon per minute. These are boring results which make noticing real gems more difficult.

I haven't checked, but my intuition says that step one should not be omitted. After all, CopperSearch as it is can find Copperhead by checking 2^33 patterns (11x3 + symmetry). Without step one, it would take 2^36 (12x3 + symmetry). Even if the removal of step one seriously improves the speed, it will not compensate for the eight-fold increase in the search space.

Rather than discard all period 8 and period 15 patterns, I wonder if you could have a final step at the very end which you run just once where boring results are weeded out? Or if it is too much work to check against known period 8 and period 15 oscillators, maybe you could have a simple test for "is it a spaceship?", and keep those?

For anyone puzzling over Alexey's answer regarding eliminating step 1, I'm pretty sure he is referring to the smaller predecessor Sokwe found here: viewtopic.php?f=2&t=2057&start=100#p28173
I was puzzled, until I remembered.

This is a naive question which maybe I should think about instead of asking out loud, but what the heck: I wonder what percentage of spaceships have smaller predecessors?

fluffykitty wrote:Try using 32-bit integers and bitwise operators to compute 32 cells in parallel. (Or does this language that you're using not have bitwise operators? If so, um....run?)

Bit-twiddling does seem to be the method of choice among fast Life simulators -- Life32, QuickLife, etc.

If that's a little too ugly to tackle with your current coding scheme, there's an intermediate algorithm that I _think_ would speed things up a bit (no pun intended). Is Delphi/Object Pascal relatively quick at maintaining sorted lists, and determining whether an item is in a list or not?

If so, then maybe you can just keep a list of the ON cells, check if any of them should be turned OFF due to too many or two few neighbors, and check if any of the cells neighboring the active list have exactly three neighbors themselves and should be added to the active list for the next generation.

Then... if on some step the active list doesn't change, the pattern has stabilized and there's no need to do any more work. A little more checking will catch p2 stabilization, and that's also probably worth the extra overhead.

In general, the first thing to try to avoid is the very common case where a pattern dies out or becomes boring, and yet the generation algorithm blindly goes on checking every neighbor of every individual cell for the full 41 ticks, to see if something different will happen this time around (!).

Your mileage may vary, but even just figuring out how to avoid all those iteration steps on the boring OFF cells in the corners of your grid bounding box, might be enough to speed things up a little.

The next step up on the way to bit-twiddling optimization might be to divide the grid into reasonable-sized tiles, and be able to certify each one separately as p2 stabilized (so it doesn't need any more attention unless a neighboring active tile is changing.) That's probably too much to tackle for this particular project, though -- you might as well just jump straight to the bit-twiddling solution.

The biggest improvement for the least amount of work seems like it would be re-implementing CopperSearch using an existing library, probably simsim314's Life API. You could certainly learn C/C++ enough to get that working -- I'm not saying it won't be painful, but I bet people here would be happy to help (if they don't get impatient and do the whole rewrite themselves).

EDIT: If you really had to, you could probably stick with Delphi, and use C wrappers for LifeAPI calls. That makes it harder for most people to help with the coding, though, and on balance it's likely to be an unnecessary headache.

Alternatively, just make the minor adjustments to the old apgsearch Python script, which calls Golly. Maybe that won't be much of a speed increase, but at least you get all the cataloguing and censusing functionality for free, and everyone can stop worrying about throwing away perfectly good p8 or p15 spaceships...!

Thank you for your replies.

I have just run a small side-by-side comparison of static and dynamic arrays. Static arrays are almost exactly 1.5 times faster, so the next version of CopperSearch will use those.

Delphi sorted lists are an easy hack, but they are classes and therefore they are almost definitely not going to speed anything up. (Some time ago I participated in a programming olympiad, and my program kept exceeding time constraints until I discarded lists and implemented MergeSort myself.)

Bit-twiddling and LifeAPI are good ideas... Maybe they will get incorporated in MoreFreeTimeCopperSearch, but it won't happen at least until summer.

biggiemac wrote:So apgnano & apgmera are both able to run substantially more soups per second than cs. Yet all that cs is doing is checking for repeating behavior. Is there anything in cs that couldn't just be done by tweaking the soup generator for apgnano? Because any pattern that acts as a small medium-period spaceship will be censused as such, and similarly for ship ancestors, ship + SL.

Good idea. I've added support for D2_+2 and D2_+1 to apgmera v3.12, and am currently running searches in each of the following censuses:

• b3s23/C1 (52 cores)
• b3s23/D2_+2 (48 cores)
• b3s23/D2_+1 (12 cores)
• b36s245/C1 (2 cores)

The b3s23/D2_+1 search has already turned up an x66 after about half an hour:
The b3s23/D2_+2 search is producing 9 * 10^9 objects per hour, so hopefully a copperhead may appear pretty soon. (Indeed, I'm surprised it hasn't turned up in either D8_4 or D4_+2 yet, which each have 31 billion objects.)

Alexey_Nigin wrote:I would like to present my new half-baked search program, CopperSearch.

I started working on something quite similar after the Copperhead was found. It wouldn't be very difficult to allow it to read a *.field file instead of having the search space specified in the source, as it is now.

Let me see if I can find the time to implement this.

In the meantime, here is the source as it is now, in case anyone is curious. Much of it was written as part of this project (which is still under development, but very slowly at the moment...):

The included Windows executable is set up to do an exhaustive search of all patterns with even symmetry, and at most 26 on-cells, in a 8-by-11 box, and it rediscovers the Copperhead after a while.

(The output slows down after a while, because each identical result is reported only once, but it might be a good idea to redirect the output to a file: space4 >out.txt)

How fast is it?

Version 0.3. This version has a bug, so please do not use it.
Advantages over v0.2:

• Approximately an order of magnitude faster.
• Much more user-friendly.
• Distinguishes oscillators and spaceships.

Version 0.4

This version fixes a nasty bug which was present in v0.3. Please upgrade.

Alexey_Nigin wrote:How fast is it?

When running 22 gens before storing the reference pattern and then another 41 gens of checking, as CopperSearch does, the speed is about 300000 patterns/s (on a 3,7GHz Intel Haswell core).

I keep posting in the wrong thread

A preview of a reimplementation of CopperSearch in C.
Sample usage: cs d 132/256

This gives different results in your & my programs:
I think that this is probably a feature, not a bug, but I want to make sure.

Alexey_Nigin wrote:This gives different results in your & my programs:
...
I think that this is probably a feature, not a bug, but I want to make sure.

In the preview I added a filter for oscillators of period 3, 4, 5, 6, 8 and 15, and spaceships of period 4, to copy the behaviour of CopperSearch.

But before that, my version reported all results, starting at oscillators of period 3 and spaceships of period 2. That's why it needs to filter results that are identical to something that's been seen before.

I've verified that it indeed finds all three Copperhead predecessors if I remove that check.

For the next version I'll add some user control of what to report and what to filter, both for duplicate results and for common oscillator periods.

What does part mean? I tried and And when I press enter it closes.
Help?
EDIT:
I also tried EDIT 2: works, but doesn't find anything.
WHAT DOES PART MEAN?