dvgrn wrote: ↑June 3rd, 2020, 8:45 am
If my
search for a perfect census match ever comes up with something, I'll post it here also. The search has been running for weeks now, and the mismatch score has crept down to 4 instead of 6, but there's no sign of it going any lower.
The script ran for another week and change and tested 50443600 candidate patterns, getting a population match every 600 attempts on average. But the score never went lower than 4. Also there seems to be a strange bug in the code that I'll have to find, because I intended the score to be 6 if there were two one-off mismatches and a two-off mismatch.
Specifically, there's a long boat that the text doesn't mention, one extra block, and two missing blinkers. I've slightly modified the pattern so that it technically makes a true statement about itself now, but it definitely isn't nearly as impressive as a non-cheating version would be without the four extra gliders off to the northwest:
Code: Select all
x = 370, y = 245, rule = B3/S23
bo$2bo$3o$87bo$88bo$10bo75b3o$11bo$9b3o7$7bo$8bo$6b3o172$236b5obo3bob
3o2b4o5b4o3b3o2b5ob5ob5ob4o2bo3bob2o2b4o6b3o3b4obo3bo$238bo3bo3bo2bo2b
o9bo3bobo3bo3bo5bo3bo5bo3bobo3bo2bobo9bo3bobo5bo3bo$238bo3bo3bo2bo2bo
9bo3bobo3bo3bo5bo3bo5bo3bob2o2bobo2bo9bo3bobo5bo3bo$238bo3b5o2bo3b3o6b
4o2bo3bo3bo5bo3b4o2b4o2bobobo5b3o6bo3bo2b3o2b5o$238bo3bo3bo2bo6bo5bo5b
5o3bo5bo3bo5bobo3bo2b2o8bo5b5o5bobo3bo$238bo3bo3bo2bo6bo5bo5bo3bo3bo5b
o3bo5bo2bo2bo3bo8bo5bo3bo5bobo3bo$238bo3bo3bob3ob4o6bo5bo3bo3bo5bo3b5o
bo3bobo3bo4b4o6bo3bob4o2bo3bo4$237b3o3b3o2bo3bob5o2b3o2b3obo3bo2b4o6b
2o2b3o6b4o2b5ob5obo3bob3obo3bob5o2b4o$236bo3bobo3bobo3bo3bo3bo3bo2bo2b
o3bobo9bo2bo4bo5bo3bobo5bo5bo3bo2bo2bo3bobo5bo$236bo5bo3bob2o2bo3bo3bo
3bo2bo2b2o2bobo12bo4bo5bo3bobo5bo5bo3bo2bo2bo3bobo5bo$236bo5bo3bobobob
o3bo3bo3bo2bo2bobobo2b3o8bo3b2o6b4o2b4o2b4o2b5o2bo2bo3bob4o3b3o$236bo
5bo3bobo2b2o3bo3b5o2bo2bo2b2o5bo6bo6bo5bo3bobo5bo5bo3bo2bo2bo3bobo9bo$
236bo3bobo3bobo3bo3bo3bo3bo2bo2bo3bo5bo5bo7bo5bo3bobo5bo5bo3bo2bo3bobo
2bo9bob2o$237b3o3b3o2bo3bo3bo3bo3bob3obo3bob4o6b4ob3o6b4o2b5ob5obo3bob
3o3bo3b5ob4o3bo$346bo3$237b3o5bo6b3o3b3o2bo3bob5o2b4o9b2o7b3o2bo5b3ob
3o3b5ob4o3b4o$236bo8bo5bo3bobo3bobo3bobo5bo12bo2bo5bo3bobo6bo2bo2bo2bo
5bo3bobo$236bo8bo5bo3bobo3bobo3bobo5bo12bo2bo5bo5bo6bo2bo3bobo5bo3bobo
$236b3o6bo5bo3bobo3bobo3bob4o3b3o10b3o5bob3obo6bo2bo3bob4o2b4o3b3o$
236bo2bo5bo5bo3bob5obo3bobo9bo11bo5bo3bobo6bo2bo3bobo5bobo7bo$236bo2bo
5bo5bo3bobo3bo2bobo2bo9bob2o8bo5bo3bobo6bo2bo2bo2bo5bo2bo6bob2o$237b2o
6b5o2b3o2bo3bo3bo3b5ob4o3bo5b3o7b4ob5ob3ob3o3b5obo3bob4o3bo$281bo55bo
3$236bo2bob3o6b4o2bo5b3obo3bobo3bob5ob4o3b4o8b3o7b4obo3bob3ob4o3b4o$
236bo2bo4bo5bo3bobo6bo2bo3bobo2bo2bo5bo3bobo15bo5bo5bo3bo2bo2bo3bobo$
236bo2bo4bo5bo3bobo6bo2b2o2bobobo3bo5bo3bobo15bo5bo5bo3bo2bo2bo3bobo$
236b4o2b2o6b4o2bo6bo2bobobob2o4b4o2b4o3b3o10b2o7b3o2b5o2bo2b4o3b3o$
239bo4bo5bo3bobo6bo2bo2b2obobo3bo5bobo7bo11bo9bobo3bo2bo2bo9bo$239bo4b
o5bo3bobo6bo2bo3bobo2bo2bo5bo2bo6bob2o8bo9bobo3bo2bo2bo9bob2o$239bob3o
6b4o2b5ob3obo3bobo3bob5obo3bob4o3bo5b3o6b4o2bo3bob3obo5b4o3bo$296bo43b
o3$236bo2bo2b2o6b4o2bo6b3o3b3o2bo3bo2b4o9bo6b4o3b3o2bo3bob3o11b3o5b4o
3b3o3b3o2b5o2b4o$236bo2bobo2bo5bo3bobo5bo3bobo3bobo2bo2bo12b2o6bo3bobo
3bobo3bobo2bo9bo8bo3bobo3bobo3bo3bo3bo$236bo2bo4bo5bo3bobo5bo3bobo5bob
o3bo13bo6bo3bobo3bob2o2bobo3bo8bo8bo3bobo3bobo3bo3bo3bo$236b4o3bo6b4o
2bo5bo3bobo5b2o5b3o10bo6b4o2bo3bobobobobo3bo8b3o6b4o2bo3bobo3bo3bo4b3o
$239bo2bo7bo3bobo5bo3bobo5bobo7bo9bo6bo5bo3bobo2b2obo3bo8bo2bo5bo3bobo
3bob5o3bo7bo$239bobo8bo3bobo5bo3bobo3bobo2bo6bob2o6bo6bo5bo3bobo3bobo
2bo2b2o5bo2bo5bo3bobo3bobo3bo3bo7bo$239bob4o5b4o2b5o2b3o3b3o2bo3bob4o
3bo5b3o5bo6b3o2bo3bob3o4bo6b2o6b4o3b3o2bo3bo3bo3b4o$286bo38bo3$237b3o
2bo3bob3o8bo6b5obo3bob4o$236bo3bobo3bobo2bo6b2o8bo3bo3bobo3bo$236bo3bo
b2o2bobo3bo6bo8bo3bo3bobo3bo$236bo3bobobobobo3bo6bo8bo3bo3bob4o$236b5o
bo2b2obo3bo6bo8bo3bo3bobo3bo$236bo3bobo3bobo2bo7bo8bo3bo3bobo3bob2o$
236bo3bobo3bob3o7b3o7bo4b3o2b4o2b2o!
#C [[ X 112 Y 94 Z 3.5 ]]
dvgrn wrote: ↑June 3rd, 2020, 8:45 am
Eventually I'll stop the search and see if I can get a decent estimate of how long a census search like this would be expected to take before it finds an exact match. I suspect it's going to be best measured in CPU-years, or maybe CPU-decades.
Here's the raw data for the scores that showed up each time the population matched the expected population:
Even though the scores are apparently slightly buggy, they do seem to be good enough to get a sense of the size of the problem -- higher scores mean a less perfect match, and if I'd seen a score of zero that would have been the perfect pattern I was looking for. Here's a histogram of the scores, excluding the really rare outliers at the upper end of the range:
- Distribution-of-scores.png (21.08 KiB) Viewed 1886 times
And here's what the relatively close-to-zero score counts look like, on the left side of the above graph.
- Individual-score-counts.png (31.47 KiB) Viewed 1886 times
Here's the population-match score list in a less annoying format:
I guess there's an exponential-ish curve on the left side of the score-count graph, that maybe someone clever with statistics could use to extrapolate a probable number of CPU-years before a lucky match would be likely to be found. At 600 censuses per population match, and my not particularly speedy computer devoting one thread to a horribly inefficient Python-based implementation of the census, my guess would be something over one CPU-year but probably less than 10 CPU-years.
... I think I'll switch to some other type of search for now, and just hope that someone is inspired to implement something using lifelib, and/or run a multi-threaded search.