Joined: 26 Nov 2008 13:54 Posts: 6 Location: Москва-Кассиопея
Я когда-то давно делал эксперименты с этой игрой - какие конструкции получаются из случайного распределения на предельно большом поле. Можно поиграться с моим приложением, взяв его отсюда:
Joined: 08 Jan 2003 23:22 Posts: 22730 Location: Silicon Valley
andyp wrote:
Я когда-то давно делал эксперименты с этой игрой - какие конструкции получаются из случайного распределения на предельно большом поле. Можно поиграться с моим приложением, взяв его отсюда:
Да я тоже экспериментировал в 1994 году - оказалось, что со временем жизнь замирает (остаются только всякие мигалки, да стабильные конструкции) - жизнь поддерживалась только там, где были посторонние возмущения - "мутации" на краях карты (моя программка не сильно чисто обрабатывала пограничные области) - вот там было весело
Shaos wrote:
Shaos wrote:
Shaos wrote:
Особенности реализации - клетки являются ячейками таблицы, в которых хранится количество соседей (и это количество визуально видно). По ходу пересчёта временное состояние ячеек сохраняется путём установки других (не white или blue) цветов - red для умирающих клеток и purple для рождающихся - но глазом это не заметно т.к. они потом быстро заменяются на нормальные цвета во втором проходе, когда корректируются числа соседей для клеток около которых произошло рождение или смерть.
Ещё раз объясню суть своего алгоритма 15 летней давности (смотреть по сишному коду) - вместо двухмерного массива булеанов имеем двумерный массив байтов, где храним (в младших 4 битах) заранее подсчитанное количество живых соседей для каждой клетки. В старших битах имеем один бит на текущее состояние и два бита на будущее - бит на рождение и бит на смерть. Пробегая по массиву нам уже не надо обегать каждую клетку считая соседей - они уже посчитаны - просто сверяемся по текущему состоянию и числу соседей - если клетка занята и не 2 и не 3 соседа - взводим флаг смерти, если клетка свободна и имеется ровно 3 соседа - взводим флаг рождения. После того как все флаги взведены - пробегаем по таблице ещё раз, обращая внимание только на те клетки где есть флаг смерти или флаг рождения, в соответствии с которыми декрементируем или инкрементируем суммы живых соседей в клетках вокруг. По моим понятиям вычислений будет сильно меньше, нежели в случае "честного" алгоритма, который считает соседей у каждой клетки каждый раз.
Попробовал этот JS-код в разных браузерах - оказалось что он работает нормально только в Firefox...
В Firefox v16 тоже перестало работать - оказалось, что нельзя называть одним и тем же словом объект и функцию - поправил и теперь этот код работает в Firefox, Chrome, Safari и Opera, а вот в IE останавливается на втором шаге:
Автор данных сигналов Alan Hensel, 1995. Два сигнала справа легко поглащяются правой кромкой "канала", а вот крайний слева разбивает конструкцию, дойдя до конца...
чтобы не разбивал, надо чуть более изощрённый конец изобразить (см. ниже) и ещё интересно, что такой сигнал может толкать впереди точку, а может не толкать - и тот, и этот вариант можно слопать в конце "провода" без ущерба для провода:
Можно сказать получился троичный сигнал - точка это минус, а отсутствие конструкции - ноль
Год назад я обратил внимание на другие конструкции - ZIP и WIRE (и те и другие передают информацию с максимально возможной скоростью - одна клетка за такт и причём по вертикали или горизонтали, а не как диагональные глайдеры). Кроме того для передачи таких "скоростных" сигналов необходима среда распостранения - канал передачи данных (см. тут). Проблема в том что для таких каналов известны паттерны сигналов, но только у некоторых есть паттерны генераторов и совсем у небольшого количества есть паттерны терминаторов (пожирателей сигналов без разваливания конструкции)...
Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал
На самой картинке можно видеть генератор (слева) и терминатор (справа) - причём генерируют они некие трёхклеточные конструкции, ползующие слева-направа. Перебором подобрать подобные паттерны генератора и терминатора - дело не простое, поэтому мне нужна распределённый вычислитель где есть много-много CPU
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.
Научился пользоваться программкой dr (см. https://www.conwaylife.com/wiki/Drifter) которая была написана в 1997 году одним энтузиастом Игры Жизнь (Dean Hickerson из университета Беркли) для поиска двигающихся объектов и осцилляторов - пытаюсь с помощью неё найти заглушку, которая бы съедала единичный простой шагающий сигнал:
P.S. Можно написать программку, которая тупым перебором найдёт все сигналы, способные ползать по 4-полосному коридору - высота таких объектов составляет 5 точек, а ширина до 6 точек, соответственно 30 битами можно полностью покрыть все варианты - начать скажем с симметричных и автоматически исключать зеркальные варианты (если нашли объект ползущий влево, то объект ползущий вправо получается простой перестановкой столбиков). Полосатость можно считать состоянием по умолчанию, т.е. все 5 нулей в столбике будут означать 2 полосы:
Для представления более "длинных" конструкций просто добавляем битов в начало - т.е. при переполнее 32-битного целого, можно легко перейти к 64-битным (при этом можно будет покрыть все ходилки-ползалки до 12 колонок в длинну, однако реально перебрать все варианты в этом случае будет практически невозможно)...
Кроме того больше суток гонял самодельную программку, которая тупо перебирала ВСЕ варианты простой заглушки (показана иксами - 5 битов, потом 11 битов, потом ещё 11 битов и ещё хвост из 1 бита и ещё один бит только начала обрабатывать - помечен ?):
т.е. программа прогнала 269 025 730 вариантов и для каждого просимулировала 11 поколений - ничего не нашлось
P.S. Надо универсиализировать программу, чтобы с любыми вводными работала, а также добавить хэши, чтобы не перепроверять конфигурации, на которые программа уже натыкалась в прошлом...
Кроме того больше суток гонял самодельную программку, которая тупо перебирала ВСЕ варианты простой заглушки...
В BOINC её
Да я свой сервер планирую написать и клиента надо пошустрее - с хешами и т.д.
P.S. Посмотрел внимательнее по меткам времени на файлах - гонял 16 часов примерно, получается 4670 вариантов в секунду обрабатывалось (по 11 поколений каждый вариант) - по идее с хэшами было бы намного быстрее
P.P.S. Кроме хешей можно ещё добавить логику, которая на первом же поколении отбросит кучу неживучих вариантов, если они нестабильны (поглащатель должен быть стабильным неменяющимся объектом, пока в него не въедет сигнал)
Я для начала решил выбрать сигнал с нижней картинки (автор: Noam Elkies, July 1997) - он хорош тем, что он может идти в фазе, противофазе и без сигнала (просто прямая горизонтальная линия) - самый натуральный троичный сигнал
На самой картинке можно видеть генератор (слева) и терминатор (справа) - причём генерируют они некие трёхклеточные конструкции, ползующие слева-направа. Перебором подобрать подобные паттерны генератора и терминатора - дело не простое, поэтому мне нужна распределённый вычислитель где есть много-много CPU
На самом деле эти картинки - просто осцилляторы с периодами 6 и 5 тактов (линейный осциллятор называют wick) и по сути обман зрения - никакие сигналы никуда не бегут, а просто создаётся иллюзия движения в процессе осцилляции...
С другой стороны возможно периодичность должна упростить конструкции передатчиков и приёмников - например можно сделать период 8 тактов и точкой кодировать "1", а дыркой - "0" (на картинке сигналы ползут вправо, а глушилка их глушит если они приходят в правильной фазе):
Attachment:
wires1.png [ 2.15 KiB | Viewed 8306 times ]
Видео процесса проползания сигналов:
P.S. Или лучше такую пару выбрать, чтобы визуально длина была одинакова:
Для представления более "длинных" конструкций просто добавляем битов в начало - т.е. при переполнее 32-битного целого, можно легко перейти к 64-битным (при этом можно будет покрыть все ходилки-ползалки до 12 колонок в длинну, однако реально перебрать все варианты в этом случае будет практически невозможно)...
Users browsing this forum: No registered users and 7 guests
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum