Игра ЖИЗНЬ на LifeGE.NET

[Shaos]

Пожалуй солью вместе блоги LifeGE.net и shaos.net, который возможно смогу притянуть к своему платному хостингу...

Продлил http://www.lifege.net ещё на один год...

И ещё на один...

забыл отметиться в прошлом 2011 году - тогда я тоже продлил LifeGE.net ещё на год и вот теперь приходит время задуматься о продлении в 2012 году

Продлил http://www.lifege.net ещё на один год....

[andyp]

Я когда-то давно делал эксперименты с этой игрой -
какие конструкции получаются из случайного распределения на предельно большом поле. Можно поиграться с моим приложением, взяв его отсюда:

http://andyplekhanov.narod.ru/soft/soft.htm

[Shaos]

Я когда-то давно делал эксперименты с этой игрой -
какие конструкции получаются из случайного распределения на предельно большом поле. Можно поиграться с моим приложением, взяв его отсюда:

http://andyplekhanov.narod.ru/soft/soft.htm

Да я тоже экспериментировал в 1994 году - оказалось, что со временем жизнь замирает (остаются только всякие мигалки, да стабильные конструкции) - жизнь поддерживалась только там, где были посторонние возмущения - "мутации" на краях карты (моя программка не сильно чисто обрабатывала пограничные области) - вот там было весело

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

Написал про это в своём блоге http://shaos.net а также вывесил на http://lifege.net

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

Попробовал этот JS-код в разных браузерах - оказалось что он работает нормально только в Firefox...

В Firefox v16 тоже перестало работать - оказалось, что нельзя называть одним и тем же словом объект и функцию - поправил и теперь этот код работает в Firefox, Chrome, Safari и Opera, а вот в IE останавливается на втором шаге:

http://lifege.net/life/life.html

[BarsMonster]

О, и тут жизнь
Моя реализация на JS тут - http://3.14.by/ru/some404
Исходники во View Source сразу видны.

[Shaos]

О, и тут жизнь
Моя реализация на JS тут - http://3.14.by/ru/some404
Исходники во View Source сразу видны.

Как-то длинновасто выглядит, да ещё и на canvas

[BarsMonster]

Как-то длинновасто выглядит, да ещё и на canvas

Все ради скорости
Без канваса и со "стандартной" реализацией на компьютерах по-дохлее выжирало бы 100% CPU

[Shaos]

Как-то длинновасто выглядит, да ещё и на canvas

Все ради скорости
Без канваса и со "стандартной" реализацией на компьютерах по-дохлее выжирало бы 100% CPU

Надо мой табличный вариант чтоли замерить

[Shaos]

Купил себе обратно домен LifeGE.net (я его где-то после 2014 отпустил)

[Shaos]

Другой пример оттуда же:



Автор данных сигналов Alan Hensel, 1995. Два сигнала справа легко поглащяются правой кромкой "канала", а вот крайний слева разбивает конструкцию, дойдя до конца...

чтобы не разбивал, надо чуть более изощрённый конец изобразить (см. ниже) и ещё интересно, что такой сигнал может толкать впереди точку, а может не толкать - и тот, и этот вариант можно слопать в конце "провода" без ущерба для провода:



Можно сказать получился троичный сигнал - точка это минус, а отсутствие конструкции - ноль

[Shaos]

Год назад я обратил внимание на другие конструкции - ZIP и WIRE (и те и другие передают информацию с максимально возможной скоростью - одна клетка за такт и причём по вертикали или горизонтали, а не как диагональные глайдеры). Кроме того для передачи таких "скоростных" сигналов необходима среда распостранения - канал передачи данных (см. тут). Проблема в том что для таких каналов известны паттерны сигналов, но только у некоторых есть паттерны генераторов и совсем у небольшого количества есть паттерны терминаторов (пожирателей сигналов без разваливания конструкции)...

Вот пара примеров с вышеуказанного сайта (https://web.archive.org/web/20080516135727/http://www.yucs.org/~gnivasch/life/lightspeed/index.html):





Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал

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

По поводу этих конструкций вот тут ещё написано: https://www.conwaylife.com/ref/lexicon/lex_l.htm#lightspeedwire

The following diagram shows an older example of a lightspeed wire, with a small defect that travels along it at the speed of light. As of June 2018, no method has been found of creating such a defect in the upstream end of this particular stable wire, or of non-destructively detecting the arrival of the defect and repairing the wire at the downstream end.

Code: Select all

....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
..........................................................
..OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO..
.O......O...............................................O.
O.OOOOO....OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO.O
.O.....O................................................O.
..OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO..
..........................................................
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....

[Shaos]

Научился пользоваться программкой dr (см. https://www.conwaylife.com/wiki/Drifter) которая была написана в 1997 году одним энтузиастом Игры Жизнь (Dean Hickerson из университета Беркли) для поиска двигающихся объектов и осцилляторов - пытаюсь с помощью неё найти заглушку, которая бы съедала единичный простой шагающий сигнал:

Code: Select all

....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
..........................................................
..OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO..
.O......O...............................................O.
O.OOOOO....OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO.O
.O.....O................................................O.
..OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO..
..........................................................
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....
....OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO..OO....

Пока безрезультатно...

P.S. Можно написать программку, которая тупым перебором найдёт все сигналы, способные ползать по 4-полосному коридору - высота таких объектов составляет 5 точек, а ширина до 6 точек, соответственно 30 битами можно полностью покрыть все варианты - начать скажем с симметричных и автоматически исключать зеркальные варианты (если нашли объект ползущий влево, то объект ползущий вправо получается простой перестановкой столбиков). Полосатость можно считать состоянием по умолчанию, т.е. все 5 нулей в столбике будут означать 2 полосы:

Code: Select all

OOOOOOOOO <- игнорируем (всегда есть)
..O..
....OOOOO <- обычный полосатый канал
.O..O
....OOOOO <- обычный полосатый канал
...O.
OOOOOOOOO <- игнорируем (всегда есть)
vvvvv
||||\_01110 ->                     01110
|||\__00001 ->                00001
||\___10000 ->           10000
|\____00100 ->      00100
\_____00000 -> 00000
                ^ ^  ^ ^  ^ ^  ^ ^  ^ ^ <инверсия
               0101001110110100101100100 =======> 0x0A76964
               +----++++----++++----++++

Для представления более "длинных" конструкций просто добавляем битов в начало - т.е. при переполнее 32-битного целого, можно легко перейти к 64-битным (при этом можно будет покрыть все ходилки-ползалки до 12 колонок в длинну, однако реально перебрать все варианты в этом случае будет практически невозможно)...

[Shaos]

Кроме того больше суток гонял самодельную программку, которая тупо перебирала ВСЕ варианты простой заглушки (показана иксами - 5 битов, потом 11 битов, потом ещё 11 битов и ещё хвост из 1 бита и ещё один бит только начала обрабатывать - помечен ?):

Code: Select all

....................
....................
....@@.@@.@@.xxx....
....@@.@@.@@.xx?....
.............xx.....
....@@@@@@@@xxx.....
...@..@.....xxx.....
..@.@@....@@xxx.....
...@...@....xxx.....
....@@@@@@@@xxx.....
.............xx.....
....@@.@@.@@.xx.....
....@@.@@.@@.xx.....
....................
....................

Вот последнее, что программа попробовала, прежде чем я её остановил:

Code: Select all

TRY 0x00000000 0x100901C2
1 (99,98)-(118,112)
....................
....................
....@@.@@.@@..@.....
....@@.@@.@@.@.@....
.............@......
....@@@@@@@@.@@.....
...@..@.....@.......
..@.@@....@@........
...@...@............
....@@@@@@@@........
....................
....@@.@@.@@........
....@@.@@.@@........
....................
....................
11 (99,97)-(118,112)
....................
....................
.....@@@@...........
.....@@.@...........
.....@.@@.@.........
....@.@@.@@.........
...@@@@@.@@.........
...@...@@....@.@....
..@.@..@......@.....
...@..@@.@....@.....
...@@...@@@.........
....@......@........
....@.....@.........
....@....@..........
.....@@.@...........
....................
BROKEN on 11
CLR 11 (99,97)-(118,112)

т.е. программа прогнала 269 025 730 вариантов и для каждого просимулировала 11 поколений - ничего не нашлось

P.S. Надо универсиализировать программу, чтобы с любыми вводными работала, а также добавить хэши, чтобы не перепроверять конфигурации, на которые программа уже натыкалась в прошлом...

[Shaos]

Кроме того больше суток гонял самодельную программку, которая тупо перебирала ВСЕ варианты простой заглушки...

В BOINC её

Да я свой сервер планирую написать и клиента надо пошустрее - с хешами и т.д.

P.S. Посмотрел внимательнее по меткам времени на файлах - гонял 16 часов примерно, получается 4670 вариантов в секунду обрабатывалось (по 11 поколений каждый вариант) - по идее с хэшами было бы намного быстрее

P.P.S. Кроме хешей можно ещё добавить логику, которая на первом же поколении отбросит кучу неживучих вариантов, если они нестабильны (поглащатель должен быть стабильным неменяющимся объектом, пока в него не въедет сигнал)

[Shaos]

Вот пара примеров с вышеуказанного сайта (https://web.archive.org/web/20080516135727/http://www.yucs.org/~gnivasch/life/lightspeed/index.html):





Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал

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

На самом деле эти картинки - просто осцилляторы с периодами 6 и 5 тактов (линейный осциллятор называют wick) и по сути обман зрения - никакие сигналы никуда не бегут, а просто создаётся иллюзия движения в процессе осцилляции...

С другой стороны возможно периодичность должна упростить конструкции передатчиков и приёмников - например можно сделать период 8 тактов и точкой кодировать "1", а дыркой - "0" (на картинке сигналы ползут вправо, а глушилка их глушит если они приходят в правильной фазе):

wires1.png

Видео процесса проползания сигналов:



P.S. Или лучше такую пару выбрать, чтобы визуально длина была одинакова:

wires2.png

Видео проползания и съедания на конце:

[Shaos]

...Полосатость можно считать состоянием по умолчанию, т.е. все 5 нулей в столбике будут означать 2 полосы:

Code: Select all

OOOOOOOOO <- игнорируем (всегда есть)
..O..
....OOOOO <- обычный полосатый канал
.O..O
....OOOOO <- обычный полосатый канал
...O.
OOOOOOOOO <- игнорируем (всегда есть)
vvvvv
||||\_01110 ->                     01110
|||\__00001 ->                00001
||\___10000 ->           10000
|\____00100 ->      00100
\_____00000 -> 00000
                ^ ^  ^ ^  ^ ^  ^ ^  ^ ^ <инверсия
               0101001110110100101100100 =======> 0x0A76964
               +----++++----++++----++++

Для представления более "длинных" конструкций просто добавляем битов в начало - т.е. при переполнее 32-битного целого, можно легко перейти к 64-битным (при этом можно будет покрыть все ходилки-ползалки до 12 колонок в длинну, однако реально перебрать все варианты в этом случае будет практически невозможно)...

Вот сделал онлайн тестилку объектов
http://lifege.net/life/osd.php?cat=5&hex=A76964
В строке адреса меняем код и глядим
http://lifege.net/life/osd.php?cat=3&hex=4B3
http://lifege.net/life/osd.php?cat=5&hex=53B60
http://lifege.net/life/osd.php?cat=5&hex=A72B64
http://lifege.net/life/osd.php?cat=5&hex=A52B64
P.S. И это могут быть статические объекты тоже
http://lifege.net/life/osd.php?cat=5&hex=E56D4E
P.P.S. А также большие осциллирующие объекты
http://lifege.net/life/osd_.php?cat=13&hex=3BB9555ABB49D2AEB556BAA5C96EAD554EEE