apgsearch v4.0

[calcyman]

Thank you very much for discovering this bug!

I've now fixed the (incredibly annoying and subtle) bug, which only affected spaceships which fit in an 8x8 box. The problem was that I have a 2-layer mechanism of caching decompositions of objects:

• Firstly, there is a map (from strings to vectors of strings) entitled decompositions, which maps an apgcode of a (possibly pseudo) object to its list of constituents;
• Secondly, there is a map (from uint64s to strings) entitled bitcache, which maps a 2-state 8-by-8 pattern to its apgcode.

I'd made the assumption in one part of the code that anything that appears as a value in bitcache also appears as a key in decompositions. But in another part of the code, I stupidly entered the object into bitcache *before* decompositions, which temporarily violated that assumption. This was originally unproblematic because the interstitial code (in the area where the assumption was violated) never called the code that made the assumption. Later, to improve spaceship separation, I made the code more recursive, and suddenly this bug appeared.

Anyway, it's fixed in v4.972.

[77topaz]

Nice! I ran some more hauls in b2n3aijkr4j5cek6ci7c8s2-ci3-acky4einrtz5anr6c7 with v4.972, and none of them show either the xq2_1b1 or xs5_174 bugs, and correspondingly the number of objects per haul is also a lot more consistent, so the bug does indeed appear to be fixed. Perhaps the two bug-affected hauls (l_q49qHzuxdkcK and l_hc7gsQdKS3h5) could be backed individually out of the census?

[77topaz]

I can also report some major speed improvements over the last few weeks for b35s2467/C1: from about a million soups per minute for v4.86, to two million per minute for v4.91 to around three million per minute (~55000 soups/sec) for v4.972. Impressive!

[Macbi]

Can apgsearch be used to catagolue a single pattern in many rules?

[Sarp]

Can apgsearch be used to catagolue a single pattern in many rules?

I would say that would be possible but we'll have to modify apgsearch to stop when the pattern gets too large. Also due to the way apgcodes work they wouldn't be too helpful for object separation and custom apgcodes that tell the rule would cause too much strain on the catagolue. Even with these difficulties I would really love a way to do they to help the 5s and the small oscillator projects

[77topaz]

Can apgsearch be used to catagolue a single pattern in many rules?

I suppose you could do that by submitting one-soup hauls of the object across many different rules, but that's not really server-load-friendly.

[Moosey]

stupid question:
How do you end a search prematurely?

[dvgrn]

stupid question:
How do you end a search prematurely?

If you're using Cygwin or you're on Linux or Mac (anything POSIX, apparently), then type "q" and wait some number of seconds. Your partial haul will be submitted and the search will exit gracefully.

[77topaz]

stupid question:
How do you end a search prematurely?

If you're using Cygwin or you're on Linux or Mac (anything POSIX, apparently), then type "q" and wait some number of seconds. Your partial haul will be submitted and the search will exit gracefully.

And in the cases when that does not work (i.e. if apgsearch has frozen), you can use "ctrl+C", which does not submit the partial haul but does exit instantly, if not gracefully.

[Hdjensofjfnen]

How do you get precompiled apgsearch to search rules other than Life? I followed the directions on the box but the Command Prompt gives the following error:

Code: Select all

Rule b3s23 does not match desired rule b38s38

[wildmyron]

How do you get precompiled apgsearch to search rules other than Life? I followed the directions on the box but the Command Prompt gives the following error:

Code: Select all

Rule b3s23 does not match desired rule b38s38

Which directions did you follow? Precompiled apgsearch is configured for b3s23/C1 and cannot recompile itself - that's the whole point, you don't need the source repository plus development environment in order to use it.

stupid question:
How do you end a search prematurely?

If you're using Cygwin or you're on Linux or Mac (anything POSIX, apparently), then type "q" and wait some number of seconds. Your partial haul will be submitted and the search will exit gracefully.

As 77topaz mentioned, there are cases where this won't work - in particular if the -p option for running in parallel was used.

[wildmyron]

Can apgsearch be used to catagolue a single pattern in many rules?

Neither apgsearch nor Catagolue are suited to this purpose.

In particular, apgmera would be extremely inefficient because it needs to be recompiled for every rule - resulting in a search speed of less than 1 soup per second. The original Python version might be a bit better, but it also has the overhead of auxiliary rule generation.

Catagolue is not set up for this either because it is intended to collect a large amount of statistical data about a relatively small number of rules. First off, this modified apgsearch would need to bypass the 10000 soup minimum per haul, and secondly calcyman mentioned that Catagolue maintains a record of all rules searched in a zipped text file. This kind of search would very rapidly blow that file over the 1MB limit.

I've considered two main options for speeding up the searchRules scripts - both of which involve rewriting it as a C application. The first option is to use Golly's quicklife as the iterator, and the second is to use a custom iterator which would be something like the one used in two-cell-oscillators.cpp, probably with a 6 or 8 bit wide lookup table in front of the iterator. A large part of that code could alternatively come from ntzfind. I haven't looked at any of these options in earnest though, so I don't know if the overhead of rule switching would be a limiting factor for them - but we already know that quicklife can change rules reasonably efficiently with the Python interface as evidenced by the search speed of searchRules-matchPatt.py

That's only part of the problem if you actually want a full census though. In that case it might be better to use the censusing functionality of apgsearch but bolt that on to an iterator which doesn't need to be recompiled for every new rule (probably quite a lot of lifelib's architecture that would need to be modified to support this scheme)

[Hdjensofjfnen]

How do you get precompiled apgsearch to search rules other than Life? I followed the directions on the box but the Command Prompt gives the following error:

Code: Select all

Rule b3s23 does not match desired rule b38s38

Which directions did you follow? Precompiled apgsearch is configured for b3s23/C1 and cannot recompile itself - that's the whole point, you don't need the source repository plus development environment in order to use it.

There is a precompiled Windows binary, only for b3s23/C1, available from
here.
When executed, it will prompt you for the haul size, number of CPUs to use,
and your payosha256 key. For
finer control, it can be run from the Command Prompt with any combination
of the options mentioned in the Example Usage above.

[wildmyron]

@Hdjensofjfnen: and if you look through the examples in the Example Usage section you will see that the only options mentioned are -n, -k, and -p.

--rule and --symmetry are only mentioned in the section above Example Usage. Perhaps there is some potential for confusion, but I think the directions are clear enough.

[77topaz]

There is a precompiled Windows binary, only for b3s23/C1, available from
here.
When executed, it will prompt you for the haul size, number of CPUs to use,
and your payosha256 key. For
finer control, it can be run from the Command Prompt with any combination
of the options mentioned in the Example Usage above.

It says "only for b3s23/C1" for a reason.

[Hdjensofjfnen]

It says "only for b3s23/C1" for a reason.

[wildmyron]

There seems to be something odd going on with the misclassification of some high period oscillators as Pathological. I noticed this pattern with a p544 oscillator mentioned and searched by 77topaz. See here. It seems to me that most of the misclassifications happen when the soup evolves into the oscillator via a pattern made up of 3 or 4 isolated dots. I wondered if there was perhaps some short-circuit code in lifelib which is causing stabilisation of this pattern to be aborted early.

But after looking at the soup stabilisation code in apgmera I see that's very unlikely, as it does pretty much the same as the Python version and for any soup in this rule containing the p544 naivestab() is going to run it for 8000 gen no matter what. However there is something really strange going on with this pattern in lifelib. When I ran one of the sample soups from the Pathological category through apgsearch with --symmetry stdin I got the following census:

Code: Select all

@CENSUS TABLE
xs1_1 4
xp4_14 1
xp2_7 1

And here's what a slightly older verision of liflelib thinks of that oscillator (using python-lifelib and jupyter notebook):

Code: Select all

import lifelib
print(lifelib.__version__)
lt = lifelib.load_rules("b2cik3aeiq4aeijnr5cejy6-ak7cs02-ak3ace4cekqrz5ainqy6cn8").lifetree()

Output: 2.1.11

Code: Select all

p544h = lt.pattern("obobo")
print(p544h.population, p544h[272].population, p544h[544].population, p544h[1088].population)

Output: 3 3 18 15

Code: Select all

p544v = lt.pattern("o2$o2$o")
print(p544v.population, p544v[272].population, p544v[544].population, p544v[1088].population)

Output: 3 3 3 3

p544h[544].viewer() shows the pattern to have evolved into a dot, two blinkers and a small c/5 spaceship

[calcyman]

Wow -- thank you for investigating! It appears this bug could potentially have affected any isotropic non-totalistic rule. The problem was in the following routine for populating a lookup table:

Code: Select all

    void assemble_mix18() {
        std::cerr << "Computing 2^18-entry mixing table...";
        mix18 = (uint32_t*) std::malloc(0x100000); // see above.
        for (uint64_t i = 0; i < 0x3ffff; i++) {
            mix18[i] = (i & 0x3f) | (((i >> 4) & 0x3f) << 8) | (((i >> 8) & 0x3f) << 16) | (((i >> 12) & 0x3f) << 24);
        }
        std::cerr << "done!" << std::endl;
    }

Specifically, the loop condition i < 0x3ffff means that it only populates 2^18 - 1 of the entries; it should have been either i < 0x40000 or i <= 0x3ffff. So when we actually retrieve the final element of that table (which occurs during the evolution of that oscillator, depending on its position and orientation), a random uint32 is retrieved from an uninitialised memory location (very bad!).

The result is then further processed and used to index into another lookup table, which could then cause a segfault in some cases and erroneous corruption of patterns in other cases.

I've fixed the problem in lifelib v2.1.18 and apgsearch v4.98.

[wildmyron]

Thanks for fixing this. I would never have guessed it would be a fencepost error but I'm glad you were able to debug so quickly. I can confirm that my updated apgluxe does indeed correctly detect the p544 in both orientations.

[Macbi]

I'm not sure if this is the same bug, but this p3410 is being stored under two apgcodes.

[77topaz]

Okay, I have something both confusing and concerning to report: a major speed decrease in at least some rules between v4.972 and v4.98. Specifically, for b35s2467/C1, v4.972 averaged about 55000-60000 soups/sec/core and and about 81.9 tiles/soup. However, with v4.98, the speed nearly halves to 30000 soups/sec/core with around 226 tiles/soup.

However, for another rule, b2cei3aekqr4aijkny5cky6-ai78s02ai3jknq4jtyz5-acjy6-an7e/C1, there is a speed increase from around 1200-1300 soups/sec/core to 1600-1700 soups/sec/core, with the tile rate going from around 3800 tiles/soup to 2100 tiles/soup (there is a lot more variation with this rule compared to b35s2467/C1).

As a third reference point, b2k3acijr4ijqy6i7cs2aek3ijnqr4it5n/C1 goes from ~240000 tiles/soup... to around ~240000 tiles/soup, so that appears to be unaffected.

As a fourth reference point, b3-ekqr4nt5r6is02-c3/C1 goes from 4800-4900 soups/sec/core and ~490 tiles/soup to around 3800-3900 soups/sec/core and ~660 tiles/soup, another major slowdown.

Is a correction of one part in 2^18 really expected to cause such huge changes, or is something else going on here?

[calcyman]

That's probably my 'sparser population checking' update that's responsible for speed changes between rules. There's essentially no free lunch here: the best way to do this would be for apgsearch to tune itself by experimenting with varying the hyperparameters and seeing how it affects soup searching speed. At this point, we're in the realm of reinforcement learning.

[77topaz]

Hmm... would it be possible to have some kind of permanent database for those hyperparameters that apgsearch could refer to whenever it is recompiled, which would contain information like (effectively) "use the v4.98 methods rather than v4.972 for b2cei3aekqr4aijkny5cky6-ai78s02ai3jknq4jtyz5-acjy6-an7e/C1" and "use the v4.972 methods rather than v4.98 for b35s2467/C1"? For this, it might be useful to have some kind of testing mode that users could run that tries various methods/hyperparameters and compares (by making it a separate mode, data would only be generated for rules users find sufficiently interesting, thus lessening server load) and uploads that information to a central document on the server which other instances of apgsearch can then refer to. Would that be feasible?

[calcyman]

Would that be feasible?

Potentially, yes, but I've realised a simpler improvement (now integrated into v4.981). Effectively, v4.972 spent a long time testing for period-8 periodicity, and v4.98 spent a long time testing for period-12 periodicity. But now, whenever the population changes between successive measurements (thereby failing the periodicity check), it flips between 8 and 12 (and analogously when it tests larger periods).

I've tried it on your reference points, and it's close to being the best in each case. So now the code is:

Code: Select all

int naivestab_awesome(UPATTERN &pat) {

    // Copied almost verbatim from the apgsearch Python script...
    int depth = 0;
    int prevpop = 0;
    int currpop = 0;
    int period = 12;
    int security = 15;

    for (int i = 0; i < 1000; i++) {

        if (i == 40) { security = 20; }
        if (i == 60) { security = 25; }
        if (i == 80) { security = 30; }

        if (i == 400) { period = 18; }
        if (i == 500) { period = 24; }
        if (i == 600) { period = 30; }

        pat.advance(0, 0, period);
        #ifndef HASHLIFE_ONLY
        if (pat.modified.size() == 0) { return 2; }
        #endif

        currpop = pat.totalPopulation();
        if (currpop == prevpop) {
            depth += 1;
        } else {
            depth = 0;
            period ^= 4;
        }
        prevpop = currpop;
        if (depth == security) {
            // Population is periodic.
            return period;
        }
    }

    return 0;

}

where the period ^= 4 statement gives the desired flipping behaviour. So it now (effectively) is able to try periods {8, 12} simultaneously, then {14, 18}, then {24, 28}, and finally {26, 30}.

[Moosey]

Having just gotten apgluxe, what command would I run to search b3-ck4e5k6is2-in35i6c8? (I use #anon)
When I try it just searches life.