simeks wrote: ↑February 20th, 2023, 2:52 pm
carsoncheng wrote: ↑February 20th, 2023, 9:18 am
Thanks! I have been running this for about 14 hours now with a speed of ~470000 soups/second (because I have 7 separate searchers up). Hasn't been finding anything new, though it found some syntheses that were not known in 2017 (e.g., xs19_69b88gz69d11, xs17_02llicz696), when you first ran the program. Is it possible to add support for finding oscillators (i.e., periodicity detection for some LCMs of common periods, such as 8, instead of period 1 for still lifes)? I think the key lies in the while-true loop in the run_seed function, but I'm not so sure about how to do it.
EDIT: I added a for-loop around lines 469-471. It doesn't look like it's the right way to do it, though; it didn't even detect the blinker, whose period is a factor of 8.
Adding support for oscillators is of course possible, there are two things to consider:
- What is a good definition of a "strict" oscillator? Or maybe we don't need to care, but there might be thousands of copies of a blinker with a block at some random distance from it.
- We need to find a canonical hash value of an oscillator. That should be easy enough to do, but I have no easy-to-plug-in solution for that right now.
GoLGrid_evolve_inline evolves a grid from a source grid to a destination grid. Doing that 8 times in a row is the same as doing it once, so that won't help much. "m" should be interpreted as "minus". So "m2" means "current generation minus 2".
I think you've notices, but if anyone else is trying it out: On line 562 there is a seed value for the pseudo random generator. It is a good idea to modify this so you don't run the exact same search as someone else has done already.
Other things that could be useful to modify are MAX_GENS on line 22, lane_cnt on line 593 and prog_cnt on line 594. "prog" is short for progression, which basically means how many possible generations each glider may at most have progressed from a starting baseline towards the center of events.
Oh, I probably understand why I'm not finding anything new (and why it still found some smaller glider_stdin syntheses). Your original search was 64 lanes wide and 160 generations deep, but the version you posted was 32 lanes wide and 80 generations deep (if I understand correctly).
For the case of oscillators, maybe we should just assign different hashes to different phases. I have written a parsing program that analyzes the output of each file, and it's apgcode-based, meaning that those different phases are assigned to the same apgcode and the same pattern regardless. But if I need to separate "strict" oscillators, I would probably first opt to use golgrid's still life separator (it's probably based on detecting islands), and if anything goes wrong, maybe I should pipe those soups with oscillators (instead of still lifes) to apgsearch!
EDIT: I have managed to find a way to add periodic object detection; replace the run_seed function in coll.c with this:
Code: Select all
static never_inline void run_seed (SearchState *st)
{
static int static_init = FALSE;
static GoLGrid *m9;
static GoLGrid *m8;
static GoLGrid *m7;
static GoLGrid *m6;
static GoLGrid *m5;
static GoLGrid *m4;
static GoLGrid *m3;
static GoLGrid *m2;
static GoLGrid *m1;
static GoLGrid *m0;
static GoLGrid *temp_1;
static GoLGrid *temp_2;
static GoLGrid *can_m0;
if (!static_init)
{
static_init = TRUE;
m9 = alloc_evolve_grid ();
m8 = alloc_evolve_grid ();
m7 = alloc_evolve_grid ();
m6 = alloc_evolve_grid ();
m5 = alloc_evolve_grid ();
m4 = alloc_evolve_grid ();
m3 = alloc_evolve_grid ();
m2 = alloc_evolve_grid ();
m1 = alloc_evolve_grid ();
m0 = alloc_evolve_grid ();
temp_1 = alloc_evolve_grid ();
temp_2 = alloc_evolve_grid ();
can_m0 = alloc_evolve_grid ();
}
GoLGrid_copy (st->seed, m0);
int allow_out_of_bounds = FALSE;
u32 gen = 0;
while (TRUE)
{
GoLGrid *temp = m9;
m9 = m8;
m8 = m7;
m7 = m6;
m6 = m5;
m5 = m4;
m4 = m3;
m3 = m2;
m2 = m1;
m1 = m0;
m0 = temp;
/*GoLGrid_evolve_inline (m9, m8);
GoLGrid_evolve_inline (m8, m7);
GoLGrid_evolve_inline (m7, m6);
GoLGrid_evolve_inline (m6, m5);
GoLGrid_evolve_inline (m5, m4);
GoLGrid_evolve_inline (m4, m3);*/
//GoLGrid_evolve_inline (m3, m2);
//GoLGrid_evolve_inline (m2, m1);
GoLGrid_evolve_inline (m1, m0);
gen++;
if (GoLGrid_is_equal_inline (m0, m8) || GoLGrid_is_equal_inline(m0, m6) || GoLGrid_is_equal_inline (m0, m5))
{
if (GoLGrid_is_empty (m0))
break;
if (!GoLGrid_is_equal (m0, m8) && !GoLGrid_is_equal(m0, m6) && !GoLGrid_is_equal (m0, m5))
break;
if (!is_strict_still_life (m0))
break;
u64 hash = GoLGrid_make_canonical (m0, &st->rda, temp_1, temp_2, can_m0);
int is_previously_known = HashTable_void_is_marked (&st->known_hashtable, hash);
int is_reported = HashTable_void_is_marked (&st->new_hashtable, hash);
if (is_reported)
break;
HashTable_void_mark (&st->new_hashtable, hash, NULL);
if (is_previously_known)
{
st->prev_cnt++;
printf ("Previously known still-life %d:\n", st->prev_cnt);
}
else
{
st->new_cnt++;
printf ("First occurence of new still-life %d, hash = %" PRIu64 "\n", st->new_cnt, hash);
}
GoLGrid_print (m0);
GoLGrid_print_life_history (st->seed);
fflush (stdout);
break;
}
if (gen % 16 == 0)
if (has_escaping_corner_glider (st, m0))
break;
Rect bb;
GoLGrid_get_bounding_box (m0, &bb);
if (!Rect_is_subset (&bb, &st->field_stop))
break;
int is_within_bounds = Rect_is_subset (&bb, &st->field);
if (allow_out_of_bounds && !is_within_bounds)
break;
if (!allow_out_of_bounds && is_within_bounds)
allow_out_of_bounds = TRUE;
if (gen >= MAX_GENS)
break;
}
}
The still life separator does a surprisingly good job at separating oscillators, though in some cases it fails to do so, such as when a length-2 surface attaches to a beacon, for example the "beehive on beacon" pseudo-oscillator shown below:
Code: Select all
x = 5, y = 8, rule = B3/S23
b2o$o2bo$b2o2$b2o$b2o$3b2o$3b2o!
EDIT on Feb 23: That minor flaw turned out to be very useful, as it helped improve some syntheses of some pseudo-oscillators. I don't want to clutter this post up, so I have posted them in the Synthesising Oscillators thread (
https://conwaylife.com/forums/viewtopic.php?p=158119#p158119)