400spartans wrote: December 16th, 2023, 7:24 pm
So, the maximum average on cell density for any periodic pattern is 17/28.
a) It is slightly more powerful, since it's the maximum average density for
any evolution (in the limit), not just periodic
I guess the only distinction would be spacefiller or smth, but still
----
b) That strategy is kinda... generalizable
Choose
any set of cell-moments in GoL's "spacetime"
Assign each of them a weight, summing to S
If all possible universe evolutions passing through that set don't cover more than C total weight with alive cells, then C/S is an upper bound on the density
(same idea - put that set on all possible displacements, sum over live cells over sets == sum over sets over live cells == S*live <= C*sets == C*all_cells)
b2) There isn't anything limiting weights to integers ...so optimal values for any cellset are findable via linear programming
Code: Select all
Given weights and upper bound Limit
We need to minimize [Limit], subject to constraints:
Summ of all weights == 1 //normalisation
for each legal evolution:
sum of weights in live cells - Limit <= 0
Sadly, now complexity isn't in the weights/upper bound calculation - but in listing all the legal evolutions through the chosen set.
Some optimizations are possible, tho
b3) If our "2+1D" shape is symmetric (in space), then asymmetric weights can be summed with the "mirrored" version to still get same upper bound - thus we can limit ourselfs to symmetric weights, thus symmetric cell-moments can be combined into single weight variables, and evolutions that rotate into each other result in same inequalities
b4) I can't think how to rule out some individual weights being negative.
But, we can use non-negative-weight subset of solutions anyway, since all weight sets give
some kind of an upper bound.
Continuing with that restriction, we can shrink the "
all legal evolutions" line to only the "
maximal" ones - i.e. those where you can't filp any amount of the dead cells into life and still have legal evolution (because any added live cell guarantees non-decrease in weight, thus making lesser evolutions redundant)
This doesn't seem that important on the first glance for brute force, but this loop-over-evolutions most likely will be done with SAT-solvers - where each step now can be encoded not as "at least one cell is different from previous", but as a more powerful "at least one now-dead cell is alive" (just don't forget to make solver prefer live cells as the first choice in all guesses)
-----
c) Given what's stated above, most simple shape I chose to test was "single step", i.e. 3x3+1x1 inverted pyramid
all 8 "edge" cells on upper layer symmetric-ize into each other, while evolutions collapse into 2 maximal ones:
111
111 0
111
and
110
110 1
000
Code: Select all
from scipy.optimize import linprog
#edg, ctr, next, lim
c=[0, 0, 0, 1]
A_ub = [
[ 8, 1, 0, -1],
[ 3, 1, 1, -1],
]
b_ub = [0]*len(A_ub)
A_eq = [
[8, 1, 1, 0]
]
b_eq = [1]
res = linprog(c, A_ub=A_ub, b_ub = b_ub, A_eq=A_eq, b_eq=b_eq)
print(res.fun, res.x)
Denormalizing result back gives
111
101 5
111
solution, which results in 8/13 (0.615) density - equal to the
previous record.
Interestingly, I think it's even possible to track same "copy of the set on all displacements" and "only use the maximal evolutions" steps in that proof as well, just not with full perspective realized like now
If you unbound all the variables, but forget to add all the evolutions - then that center weight would go to -inf, dragging Limit along
Funny "Limit=0" result:
1 1 1
1 -8 1 5
1 1 1
Fixed, obviously, by inserting the whole transition table
A_ub = [[8,1,0,-1], [7,1,0,-1], [6,1,0,-1]...]
Same solution tho
---
3x3x2 results in
222 | 010
202 | 161
222 | 010
and 16/26 = 8/13 (0.615)
3x3x3 solution is optimal
222 | 010 | 000
202 | 171 | 010
222 | 010 | 000
17/28 (0.607)
3x3x4 took ~20-25 minutes of python bruteforce with stupid prunning, no maximal-based optimizations
12 12 12 | 3 9 3 | 0 4 0 | 0 0 0
12 0 12 | 9 42 9 | 4 9 4 | 0 4 0
12 12 12 | 3 9 3 | 0 4 0 | 0 0 0
130/215 = 26/43 (0.605, slightly below 17/28)
if anyone wants to try larger shapes, I invite you to try
Edit:
5x5+3x3+1x1 i.e. 3-high pyramid, i.e. 2 generations
0 8 8 8 0
8 24 24 24 8 | 11 27 11
8 24 32 24 8 | 27 48 27 | 39
8 24 24 24 8 | 11 27 11
0 8 8 8 0
320/559 (0.572, even smaller than 26/43)
Edit 2:
p2 (i.e. center cell loops back to the same state) weights
06 12 022 12 06
16 56 068 56 16 | 25 057 25
22 68 127 68 22 | 57 108 57
16 56 068 56 16 | 25 057 25
06 12 022 12 06
[s]I forgot to write down the "max live/total" :/
Maybe someone wants to take it as a puzzle?[/s]
736/1299 (0.567)
I tried p1 as well (middle 3x3 stays the same)
0 0 0 0 0
0 1 1 1 0
0 1 3 1 0
0 1 1 1 0
0 0 0 0 0
6/11 (0.545)
I have no idea why there's so many zeroes and how this would change as area grows
I've looked into the still live limit=1/2 paper, and it actually has weights! ...for S4 and S5 rules, where this way is more optimal than alternatives
So this technique isn't new, credit should go to "Greg Kuperberg". Makes me wonder why he didn't try oscillators/why his results aren't known
Edit 3:
p2 where live cells in gen0 aren't forced dead by gen1 (it was only "center cell is same" before)
0 2 2 2 0
2 4 6 4 2 | 3 5 3
2 6 11 6 2| 5 8 5
2 4 6 4 2 | 3 5 3
0 2 2 2 0
64/115 (0.557)