Small Tori in B3/S23

For general discussion about Conway's Game of Life.
F_rank
Posts: 29
Joined: March 28th, 2018, 6:01 pm
Location: Frankfurt, Germany

Re: Small Tori in B3/S23

Post by F_rank » June 29th, 2018, 4:33 pm

Hooloovoo wrote: 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
Posts: 29
Joined: March 28th, 2018, 6:01 pm
Location: Frankfurt, Germany

7 x 7 tori in B3/S23

Post by F_rank » August 16th, 2018, 4:43 pm

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
Posts: 29
Joined: March 28th, 2018, 6:01 pm
Location: Frankfurt, Germany

p7 on T7 - the only one so far

Post by F_rank » August 16th, 2018, 4:59 pm

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 8)
And here it is:

Code: Select all

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

F_rank
Posts: 29
Joined: March 28th, 2018, 6:01 pm
Location: Frankfurt, Germany

p3 on T7 with 26/49 (53.1%) peak density

Post by F_rank » August 16th, 2018, 5:21 pm

F_rank wrote: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
Posts: 29
Joined: March 28th, 2018, 6:01 pm
Location: Frankfurt, Germany

p3 on T7 with 28/49 (57.1%) peak density

Post by F_rank » September 1st, 2018, 5:34 pm

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
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Small Tori in B3/S23

Post by Hunting » September 9th, 2018, 11:04 pm

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.

User avatar
Saka
Posts: 3627
Joined: June 19th, 2015, 8:50 pm
Location: Indonesia
Contact:

Re: Small Tori in B3/S23

Post by Saka » September 9th, 2018, 11:27 pm

Hunting wrote: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
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Small Tori in B3/S23

Post by Hunting » September 10th, 2018, 1:06 am

Saka wrote:
Hunting wrote: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.

User avatar
Redstoneboi
Posts: 429
Joined: May 14th, 2018, 3:57 am

Re: Small Tori in B3/S23

Post by Redstoneboi » September 10th, 2018, 2:13 am

Hunting wrote: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:
F_rank wrote: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);
        }
    }
}
c(>^w^<c)~*
This is 「Fluffy」
「Fluffy」is my sutando.
「Fluffy」has the ability to engineer r e p l i c a t o r s.
「Fluffy」likes to watch spaceship guns in Golly.
「Fluffy」knows Natsuki best girl.

Hunting
Posts: 4395
Joined: September 11th, 2017, 2:54 am

Re: Small Tori in B3/S23

Post by Hunting » September 10th, 2018, 3:41 am

[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?

User avatar
Redstoneboi
Posts: 429
Joined: May 14th, 2018, 3:57 am

Re: Small Tori in B3/S23

Post by Redstoneboi » September 10th, 2018, 3:52 am

Hunting wrote: 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.
c(>^w^<c)~*
This is 「Fluffy」
「Fluffy」is my sutando.
「Fluffy」has the ability to engineer r e p l i c a t o r s.
「Fluffy」likes to watch spaceship guns in Golly.
「Fluffy」knows Natsuki best girl.

User avatar
77topaz
Posts: 1496
Joined: January 12th, 2018, 9:19 pm

Re: Small Tori in B3/S23

Post by 77topaz » September 10th, 2018, 7:28 am

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

Quantum Tunnel
Posts: 10
Joined: June 15th, 2018, 6:38 pm

Re: Small Tori in B3/S23

Post by Quantum Tunnel » September 27th, 2018, 10:00 pm

Don’t give up F-rank!

User avatar
KittyTac
Posts: 535
Joined: December 21st, 2017, 9:58 am

Re: Small Tori in B3/S23

Post by KittyTac » September 27th, 2018, 10:50 pm

Do more.

Post Reply