Realizing CGOL a 3d tiling

For general discussion about Conway's Game of Life.
User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Realizing CGOL a 3d tiling

Post by simsim314 » March 10th, 2019, 3:05 pm

As we already realized SLs as planar tiling, I was thinking about realizing 3d tilind that enforce CGOL rule. I know it's only an idea. I have not done any work on that just a thought, still any ideas of implementation? This definitely sounds very similar to 2d tiling, and as the rules of CGOL are local - the implementation of such tiling should be possible within finite steps. As tiles have inherently rotation/reflection symmetry, it should be possible to do with less than 512 * N tiles i.e. I guess in the range of several dozens of different tiles. Reminds me a bit LifeHistory rule cases.

The point being kids playing while iterating CGOL step by step. This sounds to me as cool project regardless.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 10th, 2019, 3:47 pm

I am interested, as you are probably not surprised to hear. I think we went a little overboard trying to minimize the set of still life tiles (e.g. splitting up the two neighbor cases). It may still be necessary to compose overcrowding tiles out of smaller components but then the tiles themselves need to be larger to be usable.

I had it in the back of my mind to work on 3D tiles. There are some questions, such as whether the tiles only have to fit together three dimensionally or whether they must fill up all space (and then how do you see the patterns). I had an idea for "don't care" transitions that would ignore the previous cell. That is sufficient for all cases except two-neighbor survival and could save us some pieces.

Can we get it down to 50 distinct pieces or less? It does not have to be minimal. There are a lot of different Lego pieces, for instance, and in business terms that is a feature not a bug. I think there is potential for a usable set of snap-together pieces that enforce Life rules, but I have not thought about it hard in a long time.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 10th, 2019, 5:04 pm

pcallahan wrote: how do you see the patterns
Yes the only thing one must realize is that unlike 2D tiles which could be fun only looking on them, the fun part about 3d game of life tiles is building them. Just like the regular 3d puzzles you combine it together and the fan is not to have it but to solve it. Like Rubiks cube or something. You see the starting pattern and the ending pattern. Lets say a snark. Then in the middle you see it evolving by the rules, you can start from the beginning or from the end or have partial generation K for half of the cube and generation M for the other half. It is sort of looking at the CGOL in 3D but with the limitation we are 3d creatures.

Oh I hope Adam will show up and save us from our miseries but I will start:

Code: Select all

x = 10, y = 78, rule = LifeHistory
3$4.BAB$4.BCB$4.3B7$4.2BA$4.BCB$4.3B9$4.B2A$4.BCB$4.3B8$4.BAB$4.BCA$
4.3B8$4.BAB$4.BCB$4.2BA7$4.BAB$4.BCB$4.BAB9$4.B2A$4.BCA$4.3B8$4.B2A$
4.BCB$4.2BA!


Thinking about it - this is only scriptable, who will make 50 different puzzle pieces by hand? We should think about the algorithm which we use in the 2d tiles in order to generate constrains? Was it just some random shape we used just to fit two different of them together?

How hard would it be to automate this proccess?

EDIT I-m trying to figure out our space. So we have natural symmetries of our 3d universe. Those symmetries create tiling symmetry in our problem. Now we only need to take all the possible cases which I want to compute their number and then and define the fit don't fit function. Which is probably the hard part.

1 cell - 2 cases
2 cells - 6
3 cells - 6 + 2 = 8
4 cells - not sure how to compute. probably here I would start scripting.

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

Re: Realizing CGOL a 3d tiling

Post by 77topaz » March 11th, 2019, 5:56 pm

I'm fairly certain I once read about a (2D) tiling of puzzle pieces, each representing CGoL cells, which could only form a proper tessellation with gaps if the CGoL pattern they encoded was a still life; that could be useful for this 3D tiling. I can't remember where exactly I saw that, though, I'll have to look it up.

...a few minutes later...

Oh wait, looks like it was you who created that tiling. :lol:

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 11th, 2019, 8:54 pm

77topaz wrote: Oh wait, looks like it was you who created that tiling. :lol:
Actually it was me, or anyway I designed an initial set. simsim314 made the 3D printer plans though.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing CGOL a 3d tiling

Post by calcyman » March 12th, 2019, 9:47 am

I think it's possible using 30 distinct tiles, where you place them down in layers, Lego-style, to simulate GoL:
  • 6 blue tiles
  • 6 red tiles
  • 2 yellow tiles
  • 2 green tiles
  • 6 magenta tiles
  • 4 cyan tiles
  • 4 monochrome tiles (1 black, 3 white)
The monochrome tiles are coloured so that when the top layer is monochrome, you can see only the current generation of the pattern visibly rendered on the top of the tile-stack. Between a pair of successive monochrome layers, there are four 'intermediate calculation' layers (solely blue, then blue/yellow/red, then blue/yellow/green/red, and finally cyan/magenta). Here's an abstract diagram of which coloured tiles occupy which layers, and how they communicate (if the bottom of one colour shares an edge with the top of another). You'll need to paste it into Golly to get the colours correct:

Code: Select all

x = 29, y = 31, rule = Codd
F.F.F.F.F.F.F.F.F.F.F.F.F.F.F$.F.F.F.F.F.F.F.F.F.F.F.F.F.F$F.F.F.F.F.
F.F.F.F.F.F.F.F.F.F$.F.F.F.F.F.F.F.F.F.F.F.F.F.F$F.F.F.F.F.F.F.F.F.F.
F.F.F.F.F2$19E.9G$19E.9G$19E.9G$19E.9G2$4A.4A.4D.4C.4B.4A$4A.4A.4D.4C
.4B.4A$4A.4A.4D.4C.4B.4A$4A.4A.4D.4C.4B.4A$4A.4A.4D6.4B.4A$4A.4A.4D.
9B.4A$4A.4A.4D.9B.4A$4A.4A.4D.9B.4A$4A.4A.4D.9B.4A$4A.4A16.4A$29A$29A
$29A$29A2$F.F.F.F.F.F.F.F.F.F.F.F.F.F.F$.F.F.F.F.F.F.F.F.F.F.F.F.F.F$
F.F.F.F.F.F.F.F.F.F.F.F.F.F.F$.F.F.F.F.F.F.F.F.F.F.F.F.F.F$F.F.F.F.F.
F.F.F.F.F.F.F.F.F.F!
The functions of the tiles are as follows, based on a logic circuit by Tom Rokicki:
  • Blue: gather a cell state and its two horizontally adjacent neighbours, and propagate the 5 values {centre, left-and-right, left-xor-right, majority-of-3, parity-of-3} upwards;
  • Red: gather the left-xor-right from one position and the parity-of-3 from the two vertically adjacent neighbours, and propagate the 2 values {majority-of-3, total-parity} upwards;
  • Green: propagate the majority-of-3 upwards from the red tile;
  • Yellow: propagate the left-and-right upwards from the blue tile;
  • Magenta: take in the majority-of-3 from the blue tiles of the two vertically adjacent neighbours, together with the outputs of the green and yellow tiles, and return 'true' if exactly one of the four inputs is 'true'.
  • Cyan: take the 'centre' cell state from the blue tile and the 'total-parity' output from the red tile, and take their logical disjunction (OR).
  • Monochrome: take the logical conjunction (AND) of the outputs from the cyan and magenta tiles. This should be coloured black if the output is 'true', and white if the output is 'false'.
The green and yellow tiles function simply to arrange that the four inputs to the magenta tile are in four perfectly rotationally-symmetric positions, which allows the number of distinct magenta tiles to be cut down from 16 (2^4) to 6. Similarly, twofold symmetry allows us to make do with only 6 distinct red and blue tiles, instead of 8 of each.

Each cell-generation computation involves 7 tiles (one from each of the seven colour class).

Now there's the exercise of designing the shapes of the tiles so that they possess the requisite symmetry properties and tile correctly. Different tiles of the same colour class have identical shapes, except for the types of notches/grooves (say, circle = true, diamond = false) on the top/bottom of the tile.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing CGOL a 3d tiling

Post by calcyman » March 12th, 2019, 11:55 am

It appears you need two cyans per layer, but that doesn't affect the number of distinct tiles. Here's a full schematic (EDIT: see later post for the corrected schematic).

Every tile is a simply-connected 3D polyomino with protrusions on the top and indentations on the bottom in the locations (as marked). Each protrusion/identation pair 'communicates' a Boolean value upwards.

There are 6 layers in total (I had to do split one of the layers and do some other rearranging, but the logical circuit is still the same as in the previous post) including the monochrome layer, and the blocks in the monochrome layer are 6x6x1. As such, a cell-generation is elegantly a 6x6x6 cube.
Last edited by calcyman on March 12th, 2019, 4:33 pm, edited 1 time in total.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 12th, 2019, 3:06 pm

Wow! I will need to read that a lot more carefully to understand it. Do you think these tiles can be made usable if they are the size, roughly, of Lego pieces and not require an excess amount of effort to build simple oscillators (e.g. stabilized p30 shuttle)? I think this could be a commercial product if it met some usability requirements (not a fan of patents, but if it seems fun in addition to everything else, that might be a reasonable precaution). Of course, you'd want something transparent so you could see what you built unless it is purely intended as a puzzle.
calcyman wrote:As such, a cell-generation is elegantly a 6x6x6 cube.
EDIT: OK, you partially answered if I had just read far enough. A queen bee shuttle has a 22x7 bounding box and 30 generations, so you get a 132x42x180 assembly with 6x6x6 per cell. That's big for a puzzle but not crazy for a lego project (Actually, that is nearly a volume of 1 million.) How many cubes are in a typical 3D polyomino?

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing CGOL a 3d tiling

Post by calcyman » March 12th, 2019, 4:32 pm

pcallahan wrote:Wow! I will need to read that a lot more carefully to understand it. Do you think these tiles can be made usable if they are the size, roughly, of Lego pieces and not require an excess amount of effort to build simple oscillators (e.g. stabilized p30 shuttle)?
As per your calculations, these things could get pretty big. Even if we manage to make each cube 8mm in each dimension, so the cell-generations are 48mm x 48mm x 48mm, then a pulsar in its 15x15 square would be 72cm x 72cm -- quite big!
I think this could be a commercial product if it met some usability requirements (not a fan of patents, but if it seems fun in addition to everything else, that might be a reasonable precaution). Of course, you'd want something transparent so you could see what you built unless it is purely intended as a puzzle.
If you make all the pieces apart from the monochrome ones transparent, then you can look into the side and see the individual generations as 'floors' of a multistorey car park structure.
EDIT: OK, you partially answered if I had just read far enough. A queen bee shuttle has a 22x7 bounding box and 30 generations, so you get a 132x42x180 assembly with 6x6x6 per cell. That's big for a puzzle but not crazy for a lego project (Actually, that is nearly a volume of 1 million.) How many cubes are in a typical 3D polyomino?
Each cell-generation involves 8 pieces:
  • One 'monochrome' (black or white) tile of 36 cubes;
  • One blue tile of 50 cubes;
  • One red tile of 34 cubes;
  • One yellow tile of 51 cubes;
  • One green tile of 9 cubes;
  • Two cyan tiles each of 8 cubes (so 16 cubes total);
  • One magenta tile of 20 cubes;
which sum to 216 cubes as a sanity check. Here's the corrected diagram:
whiteboard_corrected.jpg
whiteboard_corrected.jpg (56 KiB) Viewed 12894 times
I think it is usable, in that you only need to emplace 8 tiles to run a cell for one generation, and they're designed so that (when done in the correct order) they can slot vertically downwards without colliding with existing tiles.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 12th, 2019, 9:31 pm

I had some thoughts about this a few weeks ago that I'll sketch below, because it's a different approach from calcyman's. I like the way his uses only polyominoes, but it seems harder to visualize how it works. Is it generalizable to other CAs defined with boolean logic and not as a simple threshold count? How hard is it to write a script that generates the polyominoes from a definition of the logic function?

The still life tiles are explained at viewtopic.php?f=7&t=2188

Instead of trying to apply a logic circuit, the still life tiles literally use octagon neighborhoods representing relations between pairs of neighbors: live-live, dead-dead, dead-live. Octagons don't tile the plane, so there are six shapes of tiles that match up relations across diagonals (allowing the signals to cross).

The downside is that you need a different octagon for every possible combination of live neighbors or a way of composing one from smaller pieces. The upside is that it preserves rotational and flip symmetry (EDIT but flips won't do much good if pieces have a time orientation unless I'm missing something), so there aren't that many possibilities for smaller numbers of neighbors.

Right now, the tiles represent unchanging neighborhoods, but it should be possible to introduce tiles that represent transitions from live-to-dead and dead-to-live. As with calcyman's construction, the tiles would have protrusions and indentations to fit successive generations together.

In most cases, the past generation does not matter. It's any-to-dead for 0, 1, 4, 5, 6, 7, 8 neighbors, any-to-live for 3 neighbors, and live-to-live, dead-to-dead for two neighbors. "Any" could be represented by an indentation that fit both protrusions. That seems a little sloppy since it leaves empty space, so alternatively, a live/any and dead/any adapter could be constructed. I'm a little worried that it would increase complexity and be hard to handle though if there were real tiles.

One of key issues in minimizing the still life tile construction involved splitting the octagons into smaller tiles that could only be fitted together to get the allowed tiles. I think that is necessary to represent death by overcrowding, because there are so many possibilities, but it might be better just to have whole tiles for neighborhoods up to size 3. Note that there are a lot of different kinds of lego pieces too and finding the right one is probably easier than building it. For mathematical purists, these could be labeled as compound tiles from the best minimal tile set.

Emphasis above, because I think that is something we might need for any physical realization to be usable. You could even have larger tiles spanning empty regions just to avoid unnecessary tedium, and they would be identified by the atomic tiles that you could use for them. It is a like a physical approximation to hash life. (Note: not just empty space; we could have compound tiles for gliders and other common objects).

I had also wondered if there was a way to have just one kind of tile representing "same to same" that would work for neighborhoods of size three. What I guess I imagined is a protrusion in the lowest layer that could propagate up through holes in successive three neighbor tiles. I never came to a conclusion on whether that was possible or not, but it would probably require small "adapter" pieces, reducing usability.

Finally, I had some half-baked ideas about enforcing higher period oscillations. You could drill holes through the tiles through which a rod of a fixed length could be inserted, with attachments at each end to enforce equality of cell values. That may be taking things to extremes, but I throw it out there in case anyone wants to run with it.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing CGOL a 3d tiling

Post by calcyman » March 13th, 2019, 4:53 am

pcallahan wrote:I had some thoughts about this a few weeks ago that I'll sketch below, because it's a different approach from calcyman's. I like the way his uses only polyominoes, but it seems harder to visualize how it works. Is it generalizable to other CAs defined with boolean logic and not as a simple threshold count?
If you don't exploit any symmetry, then yes, it's routine:
  • Embed the Boolean logic circuit in the 3D torus (R^3 / Z^3), with information travelling upwards;
  • Create a tile for each logic gate, and expand the tiles until they partition space (Voronoi style);
  • Annotate the tiles with protrusions and indentations, where each n-input m-output logic gate becomes 2^n distinct tiles (one for each possible input combination).
So a 2-input gate 'costs' 4 tiles, a 3-input gate 'costs' 8, and so forth.

In the case of Tom Rokicki's circuit (modified to fuse various gates together), you'd get a total of 8 + 8 + 16 + 4 + 4 = 40 tiles. My construction modifies this slightly by adding identity gates to increase this to:

8 + 8 + 2 + 2 + 16 + 4 + 4 = 44 tiles

in such a way that many of the tiles are rotations of each other. Removing duplicates (tiles related by rotations), it reduces to:

6 + 6 + 2 + 2 + 6 + 4 + 4 = 30 tiles
Finally, I had some half-baked ideas about enforcing higher period oscillations. You could drill holes through the tiles through which a rod of a fixed length could be inserted, with attachments at each end to enforce equality of cell values. That may be taking things to extremes, but I throw it out there in case anyone wants to run with it.
Ooh, I like that idea!

Observe that you've reduced the problem of finding a period-p m-by-n oscillator to 'exact cover'.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 7:00 am

I know Adam's solution is better and before I dive into his mind with 30 tiles I want to present simpler solution to grasp (it's only NxM block sets which are always binary counters) with 54 tiles. I'm obviously inspired by the general approach.

My tiles also have 4 layers between two life states. They also work for any totalistic automaton.
I represent each life cell as 4x4.

- 6 Blue (4x4) (16 options up to rotation symmetry)
- 8 Orange (4x1)
- 8 Green (4x2)
- 32 Black/White.(4x4 + 4x2 layer below)

Everything is also built like lego pieces with different connector types. I use filled and not filled notation.

The overview: Blue tiles are passing the information from neighborhood to the inner part of the square. The orange+green represent the binary summ. I summate the neighborhood twice with 4 orange pieces and another two layers and get 16 bits of summation. Then I use 32 Black/White tiles to represent the rule. I get "only" 54 because I reuse the orange tiles.

So:
Layer1: everything black and white.
Layer2: everything blue.
Layer3: orange+green summoning up the bits once.
Layer4: orange connected to orange+two greens+orange summons the bits second time
Layer5: The rule using the bits.

[attachment]Blue.png[/attachment]

[attachment]Orange_Green.png[/attachment]

EDIT I forgot the dot in the left represents the center state.

[attachment]Black_White.png[/attachment]

EDIT Although there is a lot of tiles - the player will be able to recognize the pattern very simply as it's just a number he needs to calculate from 5 bits to find the correct part.

It's possible to add another layer - calculate the 4 orange bits up to 180 rotation which is 10, and in case of CGOL we will just need 6 more tiles in the end.

Maybe it's possible to make the orange symmetrical in 180 degrees and then we'll have 5 instead of 8

So we will get 6 layers and:
6 - blues
8 - green
5 - oranges
10- summoning the oranges with symmetrical adder piece. The sums have 3 options - 2,3, not 2, 3.
6 - to code in CGOL.

I got to 37 or 39 if I use only bricks. This is obviously the main feature.
Attachments
Blue.png
Blue.png (20.95 KiB) Viewed 12809 times
Orange_Green.png
Orange_Green.png (24.89 KiB) Viewed 12829 times
Black_White.png
Black_White.png (14.51 KiB) Viewed 12829 times
Last edited by simsim314 on March 13th, 2019, 9:49 am, edited 1 time in total.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Realizing CGOL a 3d tiling

Post by calcyman » March 13th, 2019, 8:56 am

Very elegant! Your 54-tile solution only requires 40 tiles, because only 18 of the 32 black/white tiles can actually arise in practice.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 9:21 am

I've solved it with 29 tiles now (see below for 26 reduction). I hope the reader is familiar with the previous solution of 37 and the color codes. As I don't want to draw.

The blue remains. 6 blue.

The orange overgone transformation and there is no green now: The input state (x y-y z) will push down all the bits but will not represent them in binary system, and print the center value in the top with special shape. For example:
(0 1-1 0) -> (1,0,0,C1)
(0 0-0 1) -> (1,0,0,C0)
(1 1-1 0) -> (1,1,0,C1)

I'm using two layers of orange now placed in 90 degree. Thus I'll get something like:
Cx CC-CC Cz
Ct 0- 0 a1
Cu 0 a2 a3
Cv 0 a4 a5

The ai will need to be underneath some diagonal and on top of it 0s.

Now I'm adding a special connector shape which I call "don't care". For example I can have two directions \,/ and the shape X will mean don't care. Turns out that 11 shapes is enough for summation (it's actually eight), because after the summ reaches 4 I can use don't care for 5 and more. The output will still be 3,4 or not 3,4 (As I include the center into the count). This is purple layer.

To make the remaining 4 Black/White we need to connect the real center the others to don't care with the 3,4 results. {3,4} + {C1,C0} - create group of 4 tiles black and white. Then we use "don't care" shape to generate the white tile if the sum is not 3 or 4. To reduce the group of 5 tiles to 4, just notice that C1 should be only connected to 3, the 4 shape should be don't care.

Lets count:
6 blue
8 orange
11 purples
4 B/W
Total 29.

Layer count: Blue, two oranges, purple, B/W. Total 5.

In two dimensions the don't care shape is much more problematic as it creates holes in the final pattern. In 3d no one sees that - they simply connect or disconnect that's it.

Note You can mash up the orange connectors as they're symmetrical, but then you'll no be able to connect it anywhere as the B/W connectors expect the centers to be aligned in a line. Rotating everything is allowed - all the computation is completely symmetrical.

Note2 The second orange layer has only 3 orange pieces as the first orange layer had create an edge of center shapes which don't connect to the orange piece at all.

Note3 For production it might be beneficial to use L shape with height of 1 layer in the orange piece i.e. push the C line upwords one layer, thus the B/W layer will also need to be L shape of height 1.

EDIT What I like the most about this solution, every operation makes some sort of sense and clear to the player. He just pushes the bits twice that's all. This feels very natural evolution of the state.

EDIT2 Notice some of the solutions of the purple pieces might require rotation in 90 degrees, thus the output should include two solutions or single C4 symmetry.

EDIT3 Managed to reduce it still to 26! The number of purples is now 8.

X is the don't care connector, 0,1 is the must be 0 or must be 1 connector.

To cover all 0,1,2 cases:
X 0 0
X 0 0
0 X X

To cover 3 the regular 0, 1 connectors (2 cases):
0 0 0 --- 0 0 0
0 0 0 --- 0 0 1
1 1 1 --- 0 1 1

To cover 4 - also regular 3 cases.
0 0 1 --- 0 0 0 --- 0 0 0
0 0 1 --- 0 0 1 --- 0 1 1
0 1 1 --- 1 1 1 --- 0 1 1

To cover 5+:
X X 1 --- X X 1
X X 1 --- X 1 1
1 1 1 --- X X 1
Last edited by simsim314 on March 13th, 2019, 1:09 pm, edited 6 times in total.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 13th, 2019, 10:37 am

First, I'd like to address my own late objection to my approach (emphasis added) since this looks fixable.
pcallahan wrote:The upside [of using octagons] is that it preserves rotational and flip symmetry (EDIT but flips won't do much good if pieces have a time orientation unless I'm missing something), so there aren't that many possibilities for smaller numbers of neighbors.
You can have flat pieces with a symmetric hole in them. The only tile that fits in that hole would carry the nub to void between generations, so the piece with the hole would be flippable but the center would be oriented in time. The 0, 1, and 2 neighborhoods never need to be flipped anyway and do not need this gadget. (You'd still need to enforce that the bottom layer is all nubs, or maybe there is a way to get that to come out naturally.)
calcyman wrote:Observe that you've reduced the problem of finding a period-p m-by-n oscillator to 'exact cover'.
Well, I got the idea by thinking "what would a physical implementation of lifesrc (dbell/drh's oscillator algorithm) look like?". I think if you really wanted to push rods through the tiles, the tiles would have to be pretty big to be usable. But maybe a set for finding small period 3 oscillators is feasible. Is there some way to apply this to spaceship search; slanted rods seem problematic. Maybe some way to shift initial and final generations. (Alternatively, just require the user to match generations based on a picture.)

Anyway, I'll put aside the octagons and try to understand the circuit-based solutions better now.
simsim314] wrote:In two dimensions the don't care shape is much more problematic as it creates holes in the final pattern. In 3d no one sees that - they simply connect or disconnect that's it.
I agree, though it depends on whether the goal is a mathematical proof or a physical construct. One way to think of this is that you still have a "don't care to value" adapter in your tile set (for your proof), but when fabricating it, you note that this adapter is made out of air.

Another question: do we really want space-filling tiles, or ball-and-stick models like a molecular set? I assume we want the former, but the latter would make it easier to see the full pattern.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 10:58 am

pcallahan wrote:mathematical proof or a physical construct
In mathematical proof we also don't have to feel all the gaps just enforce CGOL rules. Only space fillers as special additional rule could claim the solution is not working. Not sure if space filling tiling such an important issue - but if so, then yes.
pcallahan wrote:ball-and-stick models like a molecular set?
I think those models are not that useful for large sizes. I mean this is completely advanced lego now. We can suggest to lego community the tiling design. The only issue I see is the semi transparent material can be used to print the 4 intermediate layers.

-------------

I wonder how come I didn't think about Adam's approach at all to use several layers? I mean I knew tiles are the same as computation, I even talked about that with Paul in different project. Yet still I couldn't think about it myself.

Do you think the 26 tiles solution is optimal? Or maybe let it settle down for several days before starting to build 3d models?

EDIT For the lego set we will need 6 more edgy pieces to simulate the zeros outside the universe:

4 blue domino edges:
0 0 --- 0 1 --- 0 1 --- 0 0
0 0 --- 0 1 --- 0 0 --- 0 1
0 0 --- 0 1 --- 0 1 --- 0 0
0 0 --- 0 1 --- 0 0 --- 0 1

And two blue corners:
0 0 --- 0 0
0 0 --- 0 1

I think as for number of pieces the edges are growing as √N. But you can't build a nice "LifeCube" without 3d printing all the pieces, including the edges.

EDIT I was thinking about the name&branding and "LifeCube" puzzle series sounds good to me. i.e. LifeCube glider, LifeCube The Snark, LifeCube Simkin Glidergun, LifeCube Silver Reflector, LifeCube Caterloopillar in 250 years (we will just start the project now), LifeCube Metacell, LifeCube accelerating spaceship. Every pattern we've thought of we could also build. Oh maybe I'll code this in roblox. I thought about very similar game but building something simpler. Maybe on the contrary this will be sort of the gimik of my game.
Last edited by simsim314 on March 13th, 2019, 2:11 pm, edited 1 time in total.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 13th, 2019, 1:56 pm

simsim314 wrote: I wonder how come I didn't think about Adam's approach at all to use several layers? I mean I knew tiles are the same as computation, I even talked about that with Paul in different project. Yet still I couldn't think about it myself.
I'm going to claim (with no way to prove it) that I started to think along those lines before developing the still life tiles I posted in 2016. It had occurred to me, anyway, that I could spread counts horizontally, then vertically, then test them (like I have done in some coded solutions). This is at least a multi-layer approach. But what bothered me for years was the thought that counts are totally symmetric and I should at least be able to exploit the geometric symmetry of an octagon. So that's what I was really aiming for and I did not think hard about multi-layers.

I like the idea of polyominoes though, since they don't involve a lot of oblique angles and also will seem more familiar to puzzle solvers. My goal is to give someone a puzzle they're totally comfortable with ("fit these blocks to make the top layer look like this") and tricking them into finding a 3rd generation predecessor of some Life pattern.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 2:24 pm

pcallahan wrote:My goal is to give someone a puzzle they're totally comfortable with ("fit these blocks to make the top layer look like this") and tricking them into finding a 3rd generation predecessor of some Life pattern.
Wow this is already a genius idea indeed - if I'll implement physical life tiles roblox this will mean that we can give inside a game virtual money to people who solve puzzles that we want. We will start from building just a single puzzle physical or virtual, and then we will explain there is no need to build them golly does it faster. From puzzle reality into CA studio. Wow now I see - we already build this puzzle backwards as well. Maybe people will not want to solve this specific puzzle but they might want to. We already have the design for the physical pieces. People might want to attach them in the wrong order. We can make it part of the rewards in the game.

But the question is how would the monetary system work? Are we the only ones who decide it? Like CGOL dictatorship? Or maybe we can give ratings to players and higher rated players will have more influence on the monetary system? I'm talking about the room in roblox where I'll put our puzzles. And the work people will be doing is connecting the pieces in the right order to get some specific correct result. And we will start from evolving glider backwards, evolving Queen Bee backwards etc. Or even simpler evolving still life backwards. Many such puzzles. I just need to make 3d models and write some lua script how the pieces connect, such that in the game they will snap.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 2:37 pm

pcallahan wrote:But what bothered me for years was the thought that counts are totally symmetric and I should at least be able to exploit the geometric symmetry of an octagon. So that's what I was really aiming for and I did not think hard about multi-layers.
Hmm interesting. How many years were you working on it? As for the octagon, I don't believe my rotational intuition in squared CAs. For me octagon is an illusion created by symmetric reality in which I live in but not CGOL. CGOL metric is different and it's square.

But for me the largest realization was to think about tiles just as functions I implement in C. I know to write code, ech layer is turing complete so I can write code with my tiles. This I couldn't see without Adam although you have showed me this idea in several occasions. I couldn't find myself the way, I started to think combinatorially low level, just like we did in the case of 2d tiles. I didn't think it's even possible to think of 3d tiles as a turing complete software. When I only start to think this way I solve the puzzle. But I simply don't start, it's like N+1 dimensional blindness. I really remember of thinking on this questions, I see a lot of ways it can be solve, and I'm completely missing the coding direction. Like I miss a move in chess - it doesn't pops up to my mind. Like a blind spot, someone needs to show me the direction. Afterwards I start to see.

EDIT As for octagons and CAs. We can use Octagon + Square tiling to make a CA. Didn't find this specific tiling in ready. Do you know if someone explored whis tiling space?

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 13th, 2019, 4:26 pm

simsim314 wrote: Hmm interesting. How many years were you working on it?
It was in the back of my mind for a long time. Ten years or more? But I don't know how long I was working on the tiles seriously. I think the turning point was realizing that I could match up the diagonal connections (which is not new, but I had to work it out myself). A few years before that, I had worked on some tiles to implement Wolfram rule 110 and that made me more optimistic I could tackle still life tiles. No deadlines, just something that kept bothering me.
simsim314 wrote: As for the octagon, I don't believe my rotational intuition in squared CAs. For me octagon is an illusion created by symmetric reality in which I live in but not CGOL. CGOL metric is different and it's square.
The very first time I ever heard of Conway's Life, I was really annoyed at the fact that diagonal neighbors were used at all, let alone added in the same as orthogonal neighbors (a grad student colleague once drew a two-layer picture that convinced me that it was a uniform neighborhood, but I really don't remember what he drew--see comment added at the bottom). I got over the objection, needless to say. I also do not think of the neighborhood as truly octagonal, but I wanted to get the most I could out of symmetries. Maybe this is less useful moving on to multiple layers. Clearly if you view the problem as find a count of cells in a 3x3 window, combining rows and then columns makes sense.

ADDED: The octagon notion is more pragmatic than anything else. I want to do something: count bits. I want to embed it on a "computational platform": tiles with all available rigid-body symmetries. Counting is a more symmetrical operation than rigid-body symmetry, but I thought if I used the most symmetric object that fits (an octagon), I could reduce the number of special cases. This is probably the most concise explanation I can give for my approach. Hope it makes sense.
simsim314 wrote: I didn't think it's even possible to think of 3d tiles as a turing complete software.
I envision a world in which from a young age, everyone (or everyone with some math education) immediately thinks of generalized tiling problems as Turing complete and therefore undecidable. But this is clearly counterintuitive. "In 1961, [Hao] Wang conjectured that if a finite set of Wang tiles can tile the plane, then there exists also a periodic tiling." Wikipedia link. Wang must have been aware of Turing machines. Laying out tiles in successive rows is no different from writing to a tape, except that it gives a more natural way to express non-determinism. But the point must have eluded him when he made his conjecture.
simsim314 wrote: EDIT As for octagons and CAs. We can use Octagon + Square tiling to make a CA. Didn't find this specific tiling in ready. Do you know if someone explored whis tiling space?
I'm not completely sure I am answering your question, but a CA based on squares and octagons might not have the same appeal since there are two kinds of cells and neighborhoods.

ADDED: I think I might be able to construct the "justification" of diagonal neighbors, but my most vivid memory (sometime in the early 90s) of this was being impressed by my colleague's speed of reply and quality of his whiteboard drawing with perspective and oblique angles. He was from Bulgaria, just around or after the end of the Cold War and I wondered if he was just showing me some standard math that is not taught in the US. He was a serious Computer Science student not really given to math recreation hobbies as far as I know, and I am not sure how Life came up or where he had learned about it.

Anyway, here's what he might have done. Take the grid of cells and split it into two grids of "white" diagonals and "black" diagonals like a chess board. With unit grid edges, diagonal neighbors are sqrt(2) apart. Now displace the white and black grids to unit distance (along the z axis) so that orthogonal neighbors are also sqrt(2) apart. We are then talking about neighbors at a uniform distance (though I still feel it's a cheat, but I was impressed then, or at something better that I have since forgotten). Is this a standard technique of some sort?

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 6:01 pm

pcallahan wrote: No deadlines, just something that kept bothering me.
I think like most of such projects. Amazingly how fast we cracked it. To be fair Adam was to first to understand the technique.

I'm sure you can implement it with octagons as well. My problem with the octagon is that I don't see how they don't intersect.

Say we have CGOL cells
A B
C D

How the information passing from A-D is not intersecting the information C-B?
pcallahan wrote:CA based on squares and octagons might not have the same appeal since there are two kinds of cells and neighborhoods.
To me it has more appeal as I can explore a larger space of automata. There is a glider on penrose tiling, but now I see it also has only 4 neighbors always. What's the problem to define rules using A: the geometrical shape B: dynamic adjacency graph? I can also write infinite rule that will be possible to execute on any possible graph there is. Getting something interesting is hard - thinking about it maybe fully connected 1000 vertices graph could be interesting to explore anyway wouldn't call it "cellular" automaton.

Maybe I'll write something quick in golly overlay...
pcallahan wrote:Is this a standard technique of some sort?
Never heard of it. Sounds quite shocking to you... He basically rotated the grid 45 degrees in valid mathematically way that's all. I'm not thinking in this way about CGOL anyway - for me it's just a graph. The rotational symmetry is coming from geometric intuitions for me, while CGOL is graph theory/combinatorics with nice 2d visuals. You can move the vertices as much as you like they don't need to be regular at all, as long as they keep the same adjacency graph. I was more thinking in the direction of non euclidean geometry, like hyperbolic geometry but with good visualization.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 13th, 2019, 6:15 pm

simsim314 wrote: Never heard of it. Sounds quite shocking to you... He basically rotated the grid 45 degrees in valid mathematically way that's all.
Well, it was shocking for anyone to attempt to answer my complaint at all. I think most people stop with "Why not include diagonal neighbors?" I do tend to prefer Euclidean geometry, but I agree it's arbitrary.

But I think the neighborhood is the same as two layers of a cubic close packing of spheres. https://en.wikipedia.org/wiki/Close-pac ... pheres.png That may have been his point.

Anyway, this is going off on a tangent so I'll stop.

ADDED: To address a more serious question.
Say we have CGOL cells
A B
C D

How the information passing from A-D is not intersecting the information C-B?
Because all the information is conveyed in the square that fits between the four cells. That's how I do it in the old still life tiling. E.g., if I have octagons labeled 0 or 1 on sides, I make these squares (dots are corners, and numbers are side labels).

Code: Select all

.0.  .1.  .0.
1 1  1 1  0 0
.0.  .1.  .0.
Tiling these between octagons and requiring labels to match gives the effect (particularly with the first one) of two signals "crossing." There are really a lot of ways to accomplish this. For a connecting piece to "cross" m states and n states, it just has to be able to hold mn distinct states. (Above works because there are actually 4 tiles including rotations).

Side note: have you ever seen the "planar crossover" circuit using just NAND gates (I can't find a link). But you can see how to do it with XOR pretty easily. C = A xor B, B = A xor C, A = C xor B. That can be laid out without crossing to get A,B in, B,A out. There is a similar construction to get XOR from NAND. Point being, you don't have to worry about "crossing wires" if there is a way to keep some sort of mixed state and extract the original states from it. Without that, I would have not had any chance to make the octagonal still life tiling.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 13th, 2019, 7:49 pm

pcallahan wrote:Well, it was shocking for anyone to attempt to answer my complaint at all.
I have a good intuition of what bothers you and what he did - but I really can't formulate it well mathematically either so never mind.

I've a theory that intuition is working axiomatically. I'm trying to learn the different axioms people hold in order to understand stuff or why people miss things. For example in the current case I saw it's possible to make several layers but I could find the reason to do so that I could make sense of this space at all. I prefered to think about single layer as I at least know I can converge. I saw the multi layers space, just didn't know how to use it in a meaningful way.
pcallahan wrote:all the information is conveyed in the square that fits between the four cells.
Yes I see now where you were stuck. It really never occured to you, simply have 4 bulks in the corners to copy everything 4 times to the local square? You just couldn't have the orange pieces because you had all the information in the small corner, trying to connect it to the octagon in a meaningful way. Somewhat similar to my issue I took from 2d tiling - trying to think through all the possible cases, instead of writing small "tiling script" in several layers like Adam did.
pcallahan wrote:ave you ever seen the "planar crossover" circuit using just NAND gates
I'd rediscovered this gate several weeks ago and posted it all over the other automata forum. You can play with it here.
Attachments
wire crossing small.png
wire crossing small.png (12.84 KiB) Viewed 12734 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing CGOL a 3d tiling

Post by pcallahan » March 14th, 2019, 12:30 pm

I wrote:I think if you really wanted to push rods through the tiles, the tiles would have to be pretty big to be usable. But maybe a set for finding small period 3 oscillators is feasible. Is there some way to apply this to spaceship search; slanted rods seem problematic. Maybe some way to shift initial and final generations. (Alternatively, just require the user to match generations based on a picture.)
Just to circle back on this, I'm sure you could build tiles in any framework to shift the pattern around, so if you wanted a physical realization of Dean Hickerson's c/3 spaceship search from way back, you would have three generations worth of Life tiles, another layer (I think just one) to shift the pattern back one position orthogonally, and rods going through with end pieces (*) that somehow matched up initial and final cell values.

Constructing this may be more of an exercise in masochism than a fun puzzle, but it is certainly realizable in concept.

Representing glide reflection seems tougher since the cells do not all move by the same displacement.

(*) The various rods would have to have the same cross-section (probably circular) to fit through holes in tiles. At least one end of the rod needs to be no wider than the hole. The tip of that rod would only be compatible (like a driver bit) with one kind of cap, and that would have the indentation to match the top protrusion. This is getting into high precision fabrication, but should work.

ADDED: I don't know if there is any interest in Margolus neighborhood or block cellular automata but I believe the "lego" implementation for these is very simple (unless I made a mistake below). I am tempted to prototype some of these with actual legos.

The idea is to use a 4x4 square for for each 2x2 block neighborhood. To require blocks to shift at each step, you move the position of bumps/dents from outside to center. The left square shows the bottom of the lego, and the right shows the top:

Code: Select all

a..b    ....
....    .ef.
....    .gh.
c..d    ....
This implements the transition:

Code: Select all

ab   -->   ef
cd         gh
The 4x4s have to be layered with shifts at each layer to match up the position of values. Rules are symmetric, so you only need 6 distinct tiles for the 16 possible 2x2 blocks.

Unfortunately, there is less outside awareness of rules like Critters, but these would be nearly trivial to assemble compared to the CGOL constructions.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Realizing CGOL a 3d tiling

Post by simsim314 » March 14th, 2019, 8:41 pm

It's definitely possible to build a virtual game where the rules you are talking about will be enforced. I don't see a possible way to force closing the loop in 3 steps even for oscillators let alone spaceships. Are the tiles circular in this game? lets say we have circles with 3 pieces. each piece is an X,Y cross section of single cell in all periods of time. Then we need to enforce rules inside a stack of circles with different radiuses but still the same (rows,cols) of lifesrc. So we have those layers of dependencies between Gen i -> Gen i + 1. How would we enforce them? if this is inside a circle the cell X,Y in gen + 1, is very far away relative to X, Y in gen. But we have to have circles which are closing and N arcs otherwise we will not be able to enforce rules, other than by implementing super algorithms to pass information inside multi layered tiles. It's already simpler to write a regular C compiler to this kind of things. I mean I'm trying to think visually so on some more advanced visual language we will simply implement the idea, and have a special compiler to tiles as well. Just like it's possible to compile to CGOL, Serizawa, GeminoidParticles, QCA. But the lifesrc algorithm is kinda tough. So I suggest to start from predecessors search a project that we can introduce with current tile but a snaky predecessor search. And this is my weekend project (the second weekend).

Think that our tiles build a pattern forward. But we can with the same tiles as CGOL enforced create iterate backwards. We don't need anything else. Now I'm solving this puzzle step by step in several layers. I mean you search in a spiral pattern from the center and search like in lifesrc. But when the area of the predecessor N is big enough you already search for predecessor N + 1 you don't wait for the previous generation level solution to converge. If you think about it as a 3d tile puzzle you don't need to invent anything - just to switch the order, and here you have lifesrc algorithm already. Part of it, not implemented exactly like lifesrc but hey - we don't need to invent circular tiles, instead we can work on promoting solving this puzzle and it's lifesrc based. If virtual reality will become good enough we could move to virtual reality game with high control to general public and make this tiles construction more appealing to the virtual community. So my point is for now - I'm moving in another direction which I think more important for the project in general, but I would like to think more on this direction of spaceships as well... mainly to make it appealing I think, as it's not appealing and only a thought what can be done in very virtual reality where masochistic people solve CGOL backwards puzzles using tiles evolving them by hand like lifesrc algorithms, then maybe we can start from something simpler and more fun and this is my main question I guess. Where to start from and how to make it fun. So many people like to play with puzzles, and they search for better quality more thinking, more challenge physical puzzles. This is already an existing market - so fitting inside it is much simpler task. This is what I'm at least concerned with.

As for reversible CAs they're much simpler to simulate regarding tiling but they're less interesting in the sense of puzzles. I don't need anyone to reverse the order and solve the puzzle backwards - as with reversibles it's like solving it forward. For CGOL I can give a puzzle using the current technology to evolve it. So on the contrary, I would like to make immersive complex 3d puzzle which is open problem rather than simple one. Yet still maybe some people would like the simple case, so I noticed your point. Just pay attention that we still need to colors to enforce margolius rules, but it duplicates of the same idea they're just enforced to be aligned differently. Maybe it can be done with single color - need to think a bit. Yeah I think it's possible to enforce the margolius rules with some sort of "keys" which force the tiles to arrange around different center. Maybe it's possible to make more complex computation in this case.

Post Reply