Small Tori in B3/S23

[F_rank]

Have FPGAs been considered for this type of search? You could easily do one generation per clock cycle at around 200Mhz. This would give about 9 hours to run each of the 2^36 possible 6x6 grids (without canonicalization) for 100 generations if it were completely sequential. Since this problem can be parallelized arbitrarily, many (probably >100) of the evolver units could be placed into the same large FPGA.

On my Ryzen 1700 PC (8 cores, 16 threads) I need approx 10 hours (rough estimate) for the full 2^36 evalation, with canonicalization already included on top. BUT: the mean number of follow-up generations per start pattern is between 11 and 12, so significantly less than 100.

With very large RAM it would be possible to calculate only one generation per starting pattern (its successor, or child), for all possible initial patterns. You have now generated a hash table that immediately gives you the next generation without any calculations, so any evaluations would be quite a bit accelerated, I assume.
Let's do the math: we need (2^36) * (8 bytes for a 64bit integer) = 0.5 Terabyte RAM ...

To your other question: I have neither access nor any experience with FPGA's.

-F

[F_rank]

Dear all,

I have been quiet for a few weeks, but the work on the 7x7 torus has progressed continuously. I have now done more than the first one trillion patterns in the brute force approach (so all patterns of the first 40 bits, out of 49 cells/bits), and about another half trillion of randomly sampled initial patterns (to get a better picture of the entire pattern population, and also to prepare work on the 8x8 torus). I also recently added a density analysis, examining the relation between initial and final cell density. My software produces a massive amount of data waiting to be analyzed - these are csv files that I analyse with QlikView (a business intelligence software, similar to Microsoft's Tableau or Spotfire). I will publish some of my results so far over the next few days.

Please contact me if you are interested to join me in my efforts. I am happy to share my code (C++ on Microsoft Visual Studio). I am particularly interested in the collaboration with somebody familiar with existing CGoL libraries (lifelib) to check whether the actual computations of the next generation can be improved - I don't use lifelib yet. On my 8-core 16-thread Ryzen 1700 based PC, my software currently evaluates about 1 million random 7x7 patterns per second, following each pattern for an average of about 22 generations (until its fate is determined).

More to come ...
Frank

[F_rank]

A seven-period oscillator on a 7x7 torus (b3/s23)? Does not sound too exciting ...

But:

• So far, I have only identified one single p7 oscillator on T7 - in contrast, there were several oscillators with period 6 on T6
• This oscillator consists of only one (!) canonical pattern which is shifted by 3 rows each generation - oooh, a 3c pattern, or alternatively even 4c in the other direction

And here it is:

Code: Select all

x = 7, y = 7, rule = B3/S23:T7,7
3$7o2$7o$7o!

[F_rank]

I was wondering whether we can observe oscillators on small tori where at least one generation has a density > 0.5.
My results so far show that there is a 13-cell 'ash pattern' (these include all stages of oscillators) for a 5x5 torus and a 25-cell ash pattern for a 7x7 torus, so the answer is Yes. This leads immediately to the next very similar question: Is there any ash pattern with a density higher than (# of cells / 2) + 0.5?

The other day my log files showed me, out of 100 billion randomly sampled starting patterns, a single pattern that led to a canonical ash pattern of 26 cells - so more than 49 / 2 + 1 (you remember the discussion about maximum density). I thought this must be a mistake, in particular since initially I could not confirm this first finding. In the meantime though, I was able to identify the p3 oscillator (on T7) that oscillates with 22 - 22 - 26 cells (peak density 53.1%, average density 47.6%).

Here is the T7 p3 oscillator - very much resembling the swastika symbol - shown as 3 x 3 tiles on a 21 x 21 torus:

Code: Select all

x = 21, y = 21, rule = B3/S23:T21,21
2o2bob3o2bob3o2bobo$2bobo4bobo4bobo$3obob4obob4obobo2$b4obob4obob4obo$
bo4bobo4bobo4bo$2b3obo2b3obo2b3obo$2o2bob3o2bob3o2bobo$2bobo4bobo4bobo
$3obob4obob4obobo2$b4obob4obob4obo$bo4bobo4bobo4bo$2b3obo2b3obo2b3obo$
2o2bob3o2bob3o2bobo$2bobo4bobo4bobo$3obob4obob4obobo2$b4obob4obob4obo$
bo4bobo4bobo4bo$2b3obo2b3obo2b3obo!

[F_rank]

Ok, my previous hypothesis for a "natural" upper limit for the densitiy (numCells/2, or numCells/2+1) is completely shattered, with the pattern shown below.

This is a period 3 oscillator on a 7x7 torus (shown 9-fold on a 3x3 grid) that oscillates with 14-14-28 cells. The 14-cell patterns have two cells in each row and column, and the 28-cell pattern has 4 cells in each row and column. Quite beautiful, actually.

I assume this is the highest ever observed peak density for an oscillating torus pattern, so far.

Does anybody have a hypothesis what the maximum density, compatible with oscillating, may be? My new hypothesis, stimulated by this oscillator, is based on the number of cells per row (or column): That the maximum number of cells, compatible with oscillating, is (# of rows) x ([cells per row]/2+0.5). For a 7x7 torus, this would be 7 x (7/2+0.5) = 28, as observed in the pattern shown here.

Frank

Code: Select all

x = 21, y = 21, rule = B3/S23:T21,21
3b4o3b4o3b4o$3o3b4o3b4o3bo$2b4o3b4o3b4o$2o3b4o3b4o3b2o$b4o3b4o3b4o$o3b
4o3b4o3b3o$4o3b4o3b4o$3b4o3b4o3b4o$3o3b4o3b4o3bo$2b4o3b4o3b4o$2o3b4o3b
4o3b2o$b4o3b4o3b4o$o3b4o3b4o3b3o$4o3b4o3b4o$3b4o3b4o3b4o$3o3b4o3b4o3bo
$2b4o3b4o3b4o$2o3b4o3b4o3b2o$b4o3b4o3b4o$o3b4o3b4o3b3o$4o3b4o3b4o!

[Hunting]

STOP SEARCHING! This is just a useless uninteresting spam search. There are many script that can search for agar, so don't do this, anyway.
You can try LifeFind to find agars.

[Saka]

STOP SEARCHING! This is just a useless uninteresting spam search. There are many script that can search for agar, so don't do this, anyway.
You can try LifeFind to find agars.

chill. Let him do his thing. And I believe they are trying to find the highest density of a stable agar.
Am I correct on that last statement?

F_rank, please don't let that post stop you!

[Hunting]

STOP SEARCHING! This is just a useless uninteresting spam search. There are many script that can search for agar, so don't do this, anyway.
You can try LifeFind to find agars.

chill. Let him do his thing. And I believe they are trying to find the highest density of a stable agar.
Am I correct on that last statement?

F_rank, please don't let that post stop you!

Nope.

[Redstoneboi]

STOP SEARCHING! This is just a useless uninteresting spam search. There are many script that can search for agar, so don't do this, anyway.
You can try LifeFind to find agars.

“useless uninteresting spam”
people have opinions, ok? I personally think this IS an interesting search. it would be interesting to discover an agar with max/average density > 0.5 (50%), which would be contrary to intuition, since it’s been proven still life agars can’t have >50% density.
KEEP GOING!

also, you could try searching on “shifted” tori instead of squares, because of this:

my previous hypothesis for an upper limit for the densitiy is completely shattered.

I assume this is the highest ever observed peak density for an oscillating torus pattern, so far.

My new hypothesis is based on the number of cells per row: That the maximum number of cells is (# of rows) x ([cells per row]/2+0.5), as observed in the pattern shown here.

Code: Select all

x = 21, y = 21, rule = B3/S23:T21,21
3b4o3b4o3b4o$3o3b4o3b4o3bo$2b4o3b4o3b4o$2o3b4o3b4o3b2o$b4o3b4o3b4o$o3b
4o3b4o3b3o$4o3b4o3b4o$3b4o3b4o3b4o$3o3b4o3b4o3bo$2b4o3b4o3b4o$2o3b4o3b
4o3b2o$b4o3b4o3b4o$o3b4o3b4o3b3o$4o3b4o3b4o$3b4o3b4o3b4o$3o3b4o3b4o3bo
$2b4o3b4o3b4o$2o3b4o3b4o3b2o$b4o3b4o3b4o$o3b4o3b4o3b3o$4o3b4o3b4o!

which contains a 7*1 shifted 3 subtorus

Code: Select all

x = 7, y = 1, rule = B3/S23:T7-3,1
4o!

which is enough to specify the entire agar!
going from 2^(x^2) possibilities, to 2^(x*y*(x-1)), but with x and y’s values gone way down.
how to enumerate those tori i’m not so sure.

maybe calculate all tori with this?
c++

Code: Select all

for (int x = 1; true; x++) {
    for (int y = 1; y < x; y++) {
        //above for loops are usable for any operation with commutative property
        //such as addition, multiplication, and torus size.
        if (x != y) {
            //now all you need is to avoid enumerating mirror images (flip x, y, both)
            //don’t forget to add shift enumeration while doing pattern simulation
            unflippedTori(x, y);
        }
        else {
            //since the grid is a square, rotating a pattern 90 degrees is possible
            //so put your old square torus search code here, but with shift enumeration.
            isotropicTori(x);
        }
    }
}

[Hunting]

[quote="Redstoneboi"][/quote]
Ouches.
1. useless
I think "useful" in GoL means can be used in other structure. But how do you use agars to engineer patterns? I doubt that. (It can prove something, so maybe it's useful in math, but useless in GAME of Life.)
2. uninteresting
They are not so fun to watching in Lifeviewer or Golly, so I guess they are "uninteresting".
3. spam
We have plenty of agar searching programs, so I think we don't need to make new programs to do that, right?

[Redstoneboi]

Ouches.
1. useless
I think "useful" in GoL means can be used in other structure. But how do you use agars to engineer patterns? I doubt that. (It can prove something, so maybe it's useful in math, but useless in GAME of Life.)
2. uninteresting
They are not so fun to watching in Lifeviewer or Golly, so I guess they are "uninteresting".
3. spam
We have plenty of agar searching programs, so I think we don't need to make new programs to do that, right?

1. fine, if you use that definition, it’s useless. unless you want to discover a max population spacefiller (incredibly^3 unlikely)
2.interesting =/= fun to watch, there are interesting things like noah’s ark which isn’t necessarily fun to watch either.
3. “we have plenty of (agar search programs/spaceship search programs/oscillator search programs/branches of science/fps games/etc), so i think we don’t need new ones to do that, right?”
also you can’t go redefining spam like that, spam is repeatedly sending useless information to annoy people, not making different ways to solve the same family of problems.

[77topaz]

Yeah, I think Hunting's posts are a lot closer to spam than F_rank's are...

[Quantum Tunnel]

Don’t give up F-rank!

[KittyTac]

Do more.

[kercos]

Hi,

thanks F_rank for posting this.
I realize this is an old post.
Many thanks to dvgrn for bringing this up!

I was wondering if there has been any further investigation, I believe this is still a relevant discussion in 2024.

It is pretty easy to demonstrate that in a torus, any initial configuration will lead eventually to a pattern cycle of period N. If N s 1, the patter is defined as a still life. But if N>1 it is, in my opinion, more interesting. N cannot be larger than the number of possible combinations in the lattice. For instance, in a 4x4=16 grid, there are 65,536=2^16 combinations. If we analyze all possible patterns on a 4x4 grid, there is an interesting distribution of the number of patterns for each period N ranging from 1 (still life) to 8:
- N = 1: 56328
- N = 2: 3896
- N = 4: 64
- N = 8: 5248

Now 4x4 is a bit too small, but 8x8 is more interesting, yet can’t be fully explored exhaustively with current technologies (as far as I know). When sampling few thousand configuration we could still estimate the distribution, and here N seems to range from 1 to 132. Interestingly we observe a lot of simple gliders (featherweight spaceship) generating a cycle of period 32.

I’m currently exploring this to find interesting pattens occurring in this cycles with grid 16x16.
https://github.com/kercos/hashlife

If you have any thoughts or pointers to current fast implementation in a torus grid, please share.

[confocaloid]

[...] If you have any thoughts or pointers to current fast implementation in a torus grid, please share.

Here are several forum threads related to exploring what happens in toroidal universes:
viewtopic.php?f=2&t=6506 Maximum lifespan on torus
viewtopic.php?f=2&t=5248 Finite board census?
viewtopic.php?f=2&t=4795 Agar discussion thread
viewtopic.php?f=7&t=5858 Agars and other infinite patterns
viewtopic.php?f=7&t=3383 Small Tori in B3/S23 (= this thread)