И снова к старой теме. В старой статье я сделал два предположения:
Гипотезы
Первая гипотеза касается окончания 'движухи' - в широком диапазоне изначальных плотностей p от 0.1 до 0.7, после окончания 'движухи' 'пепел' имеет одну и ту же плотность, около 0.027
Так как ружья накачают 'вселенную' глайдерами при сколь угодно малой изначальной плотности, и снова начнется 'движуха', то вторая гипотеза сильнее:
В пределе при любой плотности p (кроме вырожденных случаев p=0, p=1) получается 'пепел' плотности 0.027
На Julia, имея теперь огромные мощности, я решил проверить обе. Вас ждет красивое видео.
Первая гипотеза: предельная плотность при эволюции случайной конфигурации
Я проследил эволюцию матрицы 10_000 x 10_000 (как всегда, c краями замкнутыми на тор), с начальными плотностями от 0.01 до 0.99 до 20_000 шагов (практически время релаксации случайной конфигурации составляет около 15_000 шагов). Это 1.96 * 10^14 клетко-шагов, то есть 196_000 миллиардов клетко-шагов! Мой AMD Ryzen 5 3600X 6-Core Processor 3.79 GHz пыхтел целый день. Вот результат:
Практически это 'плато' с точностью до небольшого шума:
Это соответствует результату из коммента @Miiko
Из работы https://hal.archives-ouvertes.fr/hal-02399681/document
It appears in simulations [21, 27, 24, 16] that there is an interval 0.15 < ρin < 0.75 for which the density ρ∗ of the final quiescent state is constant within the accuracy of the simulation
ρ∗ = 0.02872 ± 0.00001
Вторая гипотеза: даже при малых плотностях, "ружья" накачают вселенную материей.
Вот это мне хотелось увидеть воочию.
Создаем начальную конфигурацию с плотностью 3%. Вначале она быстро эволюционирует:
Напомню обозначения цветов. Они такие же, как в предыдущей статье:
Синий - мертвая материя - blocks, blinkers
Зеленый - активная жизнь
Красный - глайдеры
Так как поле 10k * 10k сжималось в 10 раз по каждой оси, каждый пиксель может иметь разную яркость и комбинации цветов (голубой - смесь живой и неживой материи)
После 15000 шагов случайным образом создавались 100 "ружей", стреляющих в разные стороны:
"Лучи" глайдеров создавали новую материю:
Но сами "ружья" постепенно гибнут в процессе. Чем ниже плотность, тем более они сохранны и тем больше материи могут создать, однако вопрос итоговой плотности остается открытым.
Все хорошо видно на видео, охватывающим 159_000 шагов, это главный результат работы.
https://www.youtube.com/watch?v=mgd-XiNlh4Y
Время в видео ускорено ближе к концу, чтобы не было скучно.
Комментарии (15)
pharo
18.12.2022 19:22+1Интересно, как то иногда захожу на форум сайтa nedopc.org
и они добавили к дизайну странички Game of Life in JavaScript
так вот, введя некоторую произвольную начальную комбинацию клеток и проведя симуляцию по шагам, на клике, где то, через 2000 поколений не увидел изменения клеток симулятора. :)
P.S. А, вообще, правила игры жизнь относятся к ранее исследовавшейся теории клеточных автоматов. В рускоязычном переводе была и издана книга Тоффоли Т., Марголус Н. Машины клеточных автоматов
Были и аппаратные воплощения для симуляции клеточных автоматов в проекте CAM8: a Parallel, Uniform, Scalable Architecture for Cellular Automata Experimentation
nin-jin
18.12.2022 21:29+5Можно здорово сэкономить на вычислениях, если пересчитывать не все клетки на каждом шагу, а лишь те, которые находятся рядом с активными. В своей реализации, я вместо поля 32K x 32K храню лишь множество координат активных клеток, упакованных в int30. Из-за особенностей v8 с int30 работать куда эффективнее, чем с большими числами. В Julia думаю можно таким образом сделать поле 64K x 64K. Заполнить квадрат 1000x1000 случайными клетками можно таким кодом, если интересно попробовать:
points = new Set for( let x = -500; x < 500; ++x ) for( let y = -500; y < 500; ++y ) if( Math.random() < .1 ) points.add( $mol_coord_pack( x, y ) ) $hyoo_life.Root(0).Map().state( points )Ещё оптимальнее было бы пересчитывать лишь клетки, рядом с теми, которые на предыдущем шаге переключились. Тогда многочисленные улья и караваи не будут влиять на перфоманс.
Tzimie Автор
18.12.2022 21:41Я тут пишу следующую статью по экстремальной оптимизации на julia, будет интересно сравнить с вашей версией. Пингану по готовности!
nin-jin
19.12.2022 08:01+4Добавил эту оптимизацию - пересчёт окрестностей лишь горячих клеток (которые изменили состояние в предыдущей итерации). Получилось снизить объём вычислений в полтора раза на время активной эволюции с постепенным снижением до 3 раз (относительно размера популяции), когда эволюция подходит к концу и остаются лишь стабильны фигуры и осциляторы.
Tzimie Автор
19.12.2022 09:31Можете проверить скорость на квадрате 10к ?
nin-jin
19.12.2022 10:14-1Вы же сами можете проверить у себя, выполнив в браузерной консоли приведённый выше код для заселения. У меня 100мс уходит на расчёт окрестностей 30к горячих клеток, где бы они ни находились на торе 32К на 32К, плюс рендеринг видимой области.
Ivnika
Спасибо, интересно! Видео вообще отдельная песня!
Чисто побрюзжать - хотелось бы видео на всю ширину, а то пол экрана на счетчик как-то много :)