[seqfan] Re: Finding the longest period Life-patterns on nxn toroidal board?

[Antti Karttunen]

Thanks to everybody taking so much interest in this problem!

Now, as a background, where it arose. As I mentioned on another
thread, I have used the 132-period pattern (which I conjecture to be a
longest for 8x8 board) depicted in
https://oeis.org/A179412
for a musical application.

Now, how did I find it? Well, the Verilog-code for the FPGA
controlling the machine:
https://github.com/karttu/lifemidi
checks whether the board has entered a cycle of one (which includes
wholly dead board) or is oscillating with period 2. (see the wire
"has_stagnated" in
https://github.com/karttu/lifemidi/blob/master/src/lifemidi.v ) and if
so, then reseeds the board with essentially a (pseudo-)random pattern
(actually the binary contents of the registers containing current one
of the permutations that are iterated over, independently of the
Life-pattern). So, it was at a certain hobbyist fair in Helsinki where
a member of our hacklab noticed that suddenly the machine had started
playing quite interesting stuff, after which I quickly paused the
machine, and carefully copied to my notebook the pattern that was then
shown in the leds (of that old Mefisto chess computer matrix).

Iterating from that with a separate program, I soon found the neat
starting pattern depicted first in the A179412.

Now... intuitively it seems that it is just the longest pattern (and
all of its rotations, etc, or _a_ longest pattern, if there are
fundamentally different ones which has the same period) that must have
much larger "basins of attraction" than shorter patterns, like e.g.
https://oeis.org/A179409
especially because Conway's life has strong tendency for many-to-one mappings.

So, seeding any nxn board repeatedly with some random stuff (with an
appropriate density, I guess) and then running it for a whole, would
almost certainly find most of the longest cycles for each, unless the
longest ones are really really exotic or contrived, right?

But how we could be certain that they are the longest? Can this
concept made more exact somehow? Also, I can imagine that in larger
grids there could be wholly separate regions each running their period
p_1, ..., p_j pattern, so that the whole period is LCM of them, and
these might not be so natural attractors anymore.

BTW, would incorporating some aspects of
https://en.wikipedia.org/wiki/Hashlife
make sense here?

Best regards,

Antti


On 6/15/19, Rob Pratt <robert.william.pratt at gmail.com> wrote:
> Nice!  Good to see that your count of equivalence classes agrees with
> https://oeis.org/A255016
>
> Now is there some way to get only the 351 interesting ones without having to
> enumerate the rest?  For example, we can ignore any board that contains
> fewer than 3 live cells because it will eventually be absorbed into the
> empty board, which is a still life, and hence cannot appear in any cycle.
>
> On Jun 14, 2019, at 8:54 AM, David Seal <david.j.seal at gwynmop.com> wrote:
>
>>> On 05 June 2019 at 21:14 Rob Pratt <robert.william.pratt at gmail.com>
>>> wrote:
>>>
>>> You can model the problem as finding a longest cycle in a directed graph
>>> with 2^(n^2) nodes and the same number of links. Each node corresponds to
>>> a 0-1 nxn matrix and has a link to its successor after applying the Life
>>> rules.  Because each node has outdegee 1, the cycles are just the
>>> strongly
>>> connected components.  For n = 1 to 5, I get maximum cycle lengths
>>> 1, 1, 1, 8, and 20, respectively.
>>
>> Using a somewhat more sophisticated version of that technique, I get 24
>> for n=6, the only positions with period 24 being a glider making its way
>> across the board at one diagonal step every 4 generations and so returning
>> to where it started in 24 generations.
>>
>> The more sophisticated technique is to look at equivalence classes under
>> the 288 symmetries of the 6x6 board generated by:
>>
>> * the 6 cyclic rotations of the rows;
>> * the 6 cyclic rotations of the columns;
>> * the 8 reflection/rotation symmetries of a non-toroidal square board.
>>
>> The equivalence classes associated with the vast majority of the possible
>> positions can be expected to contain 288 positions each, with a small
>> number being associated with equivalence classes of size a proper divisor
>> of 288 (ranging down to the equivalence classes of the completely empty
>> board and of the completely full board. There could therefore be expected
>> to a bit over 2^36 / 288 = 238,609,294.222... equivalence classes, so I
>> expected to be able to store all of them in under 2 GB of memory (assuming
>> each is stored in a 64-bit word), or maybe 3-6 GB including some
>> additional information about each equivalence class, such as its 'child',
>> i.e. which equivalence class contained the next generation of the
>> position.
>>
>> I could then identify 'orphans' (equivalence classes with no 'parents')
>> and disregard their 'parent'/'child' relationships with their 'children'
>> in the 'parent' counts. That would reduce 'parent' counts and so would
>> find any 'second-order orphans' (i.e. equivalence classes with 'parents'
>> but no 'grandparents') and disregard them similarly, and repeat the
>> process disregarding higher and higher order 'orphans' until no further
>> equivalence classes were disregarded. The remaining equivalence classes
>> would then be the ones in the cycles of equivalence classes, for the same
>> reason that Rob Pratt gives.
>>
>> Some care needs to be taken about interpreting the resulting cycles,
>> because the cycle length in the equivalence class graph may be a proper
>> factor of the cycle length in the full position graph. Examples are a
>> blinker, which has period 1 in the equivalence class graph but period 2 in
>> the full position graph, and a glider, which has period 2 in the
>> equivalence class graph but period 24 in the full position graph. This can
>> be dealt with by choosing an arbitrary position in any equivalence class
>> in the cycle and tracking its Life generations forward until one returns
>> to the original position. I refer to the period in the full position graph
>> as the 'full period' and the period in the equivalence class graph as the
>> 'minimised period' (to reflect the fact that it is the minimum number of
>> generations one needs to look at to make it clear that the position is in
>> a cycle).
>>
>> I have now written and debugged (hopefully fully!) such a program. A brief
>> summary of its results in case anyone wants to try confirming them:
>>
>> Equivalence classes: 239,123,150
>> Equivalence classes disregarded as 'orphans': 239,122,799
>> (of levels ranging up to 90)
>> Equivalence classes in cycles: 351
>> Number of cycles with minimised period 1, full period 1: 241
>> (these are the "still life" positions)
>> Number of cycles with minimised period 1, full period 2: 39
>> Number of cycles with minimised period 1, full period 6: 3
>> Number of cycles with minimised period 2, full period 2: 10
>> Number of cycles with minimised period 2, full period 4: 6
>> Number of cycles with minimised period 2, full period 6: 1
>> Number of cycles with minimised period 2, full period 8: 1
>> Number of cycles with minimised period 2, full period 12: 1
>> Number of cycles with minimised period 2, full period 24: 1
>> Number of cycles with minimised period 3, full period 3: 3
>> Number of cycles with minimised period 3, full period 6: 1
>> Number of cycles with minimised period 4, full period 8: 3
>> Number of cycles with minimised period 4, full period 12: 1
>>
>> I can supply more details if desired.
>>
>> The program is written in C99 and optimised highly specifically for the
>> 6x6 toroidal board, so I haven't confirmed any of the values Rob Pratt
>> gives for n = 1 to 5. It could be modified to do other sizes of board, but
>> significant amounts of work would be required on it either to adapt it to
>> another specific size of board or to deal with different sizes more
>> generally, and the latter would almost certainly slow it down
>> significantly.
>>
>> The obvious next target is the 7x7 toroidal board, but the number of
>> equivalence classes for it can be similarly expected to be a bit over 2^49
>> / (7*7*8) = 1,436,096,819,952.326..., i.e. about six thousand times larger
>> than for n=6. As a first approximation, this could be expected to increase
>> both the execution time and memory requirements of the program by the same
>> factor. That would raise the execution time of my desktop from a bit over
>> 6 minutes to a bit under a month, which is long but feasible, but the
>> memory requirement would grow from about 4 GB to about 24 TB, which
>> certainly isn't! So n=7 will require a completely different program...
>>
>> David
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>