Glider guns vs случайная конфигурация в игре «Жизнь»

[Ivnika]

Спасибо, интересно! Видео вообще отдельная песня!

Чисто побрюзжать - хотелось бы видео на всю ширину, а то пол экрана на счетчик как-то много :)

[pharo]

Интересно, как то иногда захожу на форум сайтa nedopc.org
и они добавили к дизайну странички Game of Life in JavaScript
так вот, введя некоторую произвольную начальную комбинацию клеток и проведя симуляцию по шагам, на клике, где то, через 2000 поколений не увидел изменения клеток симулятора. :)

P.S. А, вообще, правила игры жизнь относятся к ранее исследовавшейся теории клеточных автоматов. В рускоязычном переводе была и издана книга Тоффоли Т., Марголус Н. Машины клеточных автоматов

Были и аппаратные воплощения для симуляции клеточных автоматов в проекте CAM8: a Parallel, Uniform, Scalable Architecture for Cellular Automata Experimentation

[Tzimie]

А какой был размер матрицы? чем больше матрица, тем дольше теплится жизнь хоть где нибудь.

[pharo]

А, там, она представлена размером 16x16 клеток :)

[Tzimie]

Надо хотя бы тысяча на тысячу.

[nin-jin]

Можно здорово сэкономить на вычислениях, если пересчитывать не все клетки на каждом шагу, а лишь те, которые находятся рядом с активными. В своей реализации, я вместо поля 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]

Я тут пишу следующую статью по экстремальной оптимизации на julia, будет интересно сравнить с вашей версией. Пингану по готовности!

[Tzimie]

А что интересного вы делаете на такой большой матрице, 32к в квадрате?

[nin-jin]

Да особо ничего. Это позволяет иметь квазибесконечную матрицу (очень большой тор), и при этом не тратить кучу ресурсов на расчёт популяций в тысячу-другую клеток.

[nin-jin]

Добавил эту оптимизацию - пересчёт окрестностей лишь горячих клеток (которые изменили состояние в предыдущей итерации). Получилось снизить объём вычислений в полтора раза на время активной эволюции с постепенным снижением до 3 раз (относительно размера популяции), когда эволюция подходит к концу и остаются лишь стабильны фигуры и осциляторы.

[Tzimie]

А вообще какая скорость?

[Tzimie]

Можете проверить скорость на квадрате 10к ?

[nin-jin]

Вы же сами можете проверить у себя, выполнив в браузерной консоли приведённый выше код для заселения. У меня 100мс уходит на расчёт окрестностей 30к горячих клеток, где бы они ни находились на торе 32К на 32К, плюс рендеринг видимой области.

[s_f1]

Если уж у вас всё равно компьютер без дела простаивает… )
Интересно было бы сравнить плотность «пепла» классических правил, с плотностью его же для различных правил рождения и гибели клеток.

[Tzimie]

Да, если успею, простаиваю в основном я между работами)