Page 3 of 3

Re: Small Tori in B3/S23

Posted: June 29th, 2018, 4:33 pm
by F_rank
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

7 x 7 tori in B3/S23

Posted: August 16th, 2018, 4:43 pm
by 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

p7 on T7 - the only one so far

Posted: August 16th, 2018, 4:59 pm
by 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 8)
And here it is:

Code: Select all

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

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

Posted: August 16th, 2018, 5:21 pm
by F_rank
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!

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

Posted: September 1st, 2018, 5:34 pm
by 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!

Re: Small Tori in B3/S23

Posted: September 9th, 2018, 11:04 pm
by 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.

Re: Small Tori in B3/S23

Posted: September 9th, 2018, 11:27 pm
by Saka
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!

Re: Small Tori in B3/S23

Posted: September 10th, 2018, 1:06 am
by Hunting
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.

Re: Small Tori in B3/S23

Posted: September 10th, 2018, 2:13 am
by Redstoneboi
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);
        }
    }
}

Re: Small Tori in B3/S23

Posted: September 10th, 2018, 3:41 am
by 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?

Re: Small Tori in B3/S23

Posted: September 10th, 2018, 3:52 am
by Redstoneboi
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.

Re: Small Tori in B3/S23

Posted: September 10th, 2018, 7:28 am
by 77topaz
Yeah, I think Hunting's posts are a lot closer to spam than F_rank's are...

Re: Small Tori in B3/S23

Posted: September 27th, 2018, 10:00 pm
by Quantum Tunnel
Don’t give up F-rank!

Re: Small Tori in B3/S23

Posted: September 27th, 2018, 10:50 pm
by KittyTac
Do more.