| к содержанию |
Примечание: Иллюстрации в этом и других выпусках данной рассылки представлены в формате RLE. Для их просмотра вам понадобится программа просмотра паттернов Жизни. Я рекомендую программу Life32. Чтобы просмотреть диаграмму, скопируйте ее в буфер обмена и вставьте прямо на поле программы.
Наша Вселенная устроена так, что прошлое неизменно. То, что было, оно было таким, как было, и никаких вариантов прошлого не может быть. Мы можем предполагать, строить гипотезы, о причинах происшедшего. Но это только от недостатка информации. На самом деле мы прекрасно понимаем, что если бы мы могли охватить своим умом всю Вселенную полностью, то никаких вариантов в прошлом нет. Оно уже случилось, и изменить его нет никакой возможности.
Именно поэтому, как бы ни была привлекательна идея машины времени, она возможна только в сказке. И авторы фантастических произведений, в основном, эксплуатируют идею многослойной Вселенной, когда попадание героев в прошлое вызывает совсем другой поток событий и приводит совсем к другому настоящему. То есть вмешательство в ход времени порождает уже совсем другое состояние. А прошлое исходного состояния Вселенной, из которого происходило воздействие, все равно однозначно.
Что касается будущего, то тут мы имеем более сложную проблему. С одной стороны, вся классическая физика говорит о том, что мы, в принципе, можем рассчитать будущее любой системы, зная исходное состояние ее частиц. Мешают только 2 фактора — сложность реальных физических систем и опять же отсутствие информации об исходном состоянии. Но природе и то, и другое не помеха, и отсюда следует, что будущее так же однозначно, как и прошлое, определяется настоящим, и что варианты невозможны.
Против такого детерминизма восстает вся наша сущность. Ведь если будущее однозначно, то вся наша жизнь теряет смысл. Это значит, что мы ничего не делаем сами — все наши желания, все проблемы и их решения были предопределены давным-давно, когда только возникала наша Вселенная. И, не желая жить в таком бессмысленном мире, мы ищем утешениях в других учениях, которые играют на нашем желании хоть что-то значить в этом мире. Это всевозможные религии и философские концепции, декларирующие свободу воли, по крайней мере, для мыслящих существ. Как нам хочется верить, что будущее неоднозначно, и мы можем хоть немного влиять на него!
Но физика не ограничивается одной механикой. Статистическая физика и основанная на ней термодинамика тоже успешно и однозначно прогнозируют будущее физических систем на основе заданного "сейчас" состояния. Но в отличие от механики эти физические теории ничего не могут сказать о прошлом системы. Более того, они прямо утверждают, что для некоторых термодинамических состояний существует множество предшествующих. И как бы точно мы ни описали такое "сейчас", мы не можем выбрать из возможных прошлых состояний какое-либо одно — все они одинаково "истинны".
Конечно, против этого есть возражение, что статистическая физика и не претендует на абсолютную точность, она рассматривает "ансамбли" частиц, а не каждую частицу в отдельности. И оперирует она такими интегральными характеристиками, как термодинамические потенциалы, температура, давление и пр. А если рассмотреть каждую частицу, то тогда можно и возвращаться во вполне определенное прошлое в своих расчетах. Но дело то все в том, что это уже за рамками статфизики. А сама по себе статфизика не знает однозначного прошлого. Заметьте, что именно в этом разделе физики направленность времени наиболее ярко выражена.
Да и, если подумать (здесь я попытаюсь подвергнуть сомнению свой самый первый тезис), то откуда в нас такая уверенность, что прошлое в самом деле однозначно? Из того факта, что свое прошлое мы помним, а о будущем в нашей голове никакой информации нет. Но что есть память? Это сиюминутное состояние наших нейронов. Естественно, оно однозначно. Но не может ли одно и то же состояние наших нейронов вызываться разными предшествующими состояниями окружающего мира? Например, память компьютера сразу после загрузки операционной системы всегда практически одинакова — это не смотря на то, что мы можем ежедневно выполнять на нем самые разные действия.
Вы встречались со старыми друзьями после долгой разлуки? Все помнят некоторые наиболее яркие события общей жизни. Но поразительно, насколько могут отличаться описания одних и тех же событий, излагаемых разными их участниками. А ведь каждый убежден, что именно так оно и было — ведь он сам был там и все прекрасно помнит... И какое из этих прошлых было на самом деле? Даже по горячим следам описания одного и того же события разными очевидцами могут кардинально отличаться. Это прекрасно знают следователи, работающие со свидетельскими показаниями.
А как интересно можно обыграть идею многозначного прошлого в фантастике! Кажется, еще ни один писатель не додумался до этого, а ведь здесь огромный непаханый клин. Допустим, хрононавт отправляется в прошлое, чтобы изменить настоящее, он что-то делает существенное, но вернувшись в точку отправления обнаруживает, что настоящее ни на иоту не изменилось — все его усилия съела неподатливая сущность времени. Тогда он придумывает более радикальное воздействие и отправляется в новое путешествие. И ему удается сдвинуть с мертвой точки время. Он меняет то реперное событие, по которому контролирует свое воздействие. Но вернувшись, видит, что первая точка возврата в самом деле изменилась, но она уже ушла в прошлое, а вот для нового настоящего абсолютно все равно, было это изменение или нет...
Но вернемся к физике. В ней есть еще одна общепринятая теория, описывающая поведение мельчайших частиц материи — это квантовая механика. В ней даже "сейчас" нельзя описать однозначно, не говоря уже о "потом". Мешает соотношение неопределенностей. И это не только теория — эксперименты все это подтверждают. Как только мы пытаемся определить координату частицы, пропуская ее, например, через диафрагму, так мы теряем всякую информацию о ее скорости и направлении полета — после диафрагмы она может отклониться от первоначального направления полета. И отклоняется.
В этой теории будущее предсказывается только с какой-то вероятностью, причем, как утверждают создатели этой теории, эта вероятность не есть результат неполного знания о системе — она идет от самой природы. Просто, так устроен мир. О прошлом квантовая теория вообще ничего не говорит — не было у этой теории такой цели — смотреть в прошлое. Хотя, судя по симметричности ее уравнений относительно знака времени, прошлое в ней будет описываться так же неопределенно, как и будущее.
Видите, и физика в конце концов пришла к выводу о неопределенности будущего (такой желанный результат!), причем эта неопределенность имеет место на самом элементарном уровне материи, и ее невозможно устранить. Правда, физики говорят, что на нашем, макроскопическом уровне эта неопределенность настолько ничтожна, что ее можно не учитывать. Но ведь начало нашей воли находится где-то в мозгу, ее первые толчки появляются в виде микроскопических потенциалов, вызванных движением электронов в отростках нейронов — а этот уровень намного ближе к тому элементарному, где уже работает соотношение неопределенностей.
Конечно, и с этим можно спорить, и я уверен, что была бы тема, а спорщики найдутся... Но я затеял этот разговор вовсе не для этого.
В игре Жизнь с природой времени все ясно. Здесь будущее любой конфигурации всегда однозначно. Правила рождения-выживания не допускают никаких вариантов. Мертвая клетка с тремя соседями однозначно оживет в следующем поколении, а если соседей больше или меньше — останется мертвой. Живая клетка, у которой число соседей не 2 и не 3 обречена на умирание, а если 2 или 3 — проживет еще одно поколение. И так из поколения в поколение. Поэтому, нарисовав какую-нибудь конфигурацию, мы тем самым уже определили ее развитие на любое число поколений вперед, хотя, может быть, сами еще не знаем, как именно она будет развиваться. Но будущее конфигурации уже предопределено. Осталось только запустить программу Life32 и реализовать это будущее.
А попробуйте-ка определить прошлое конкретного паттерна хотя бы на поколение назад. Хотя бы блока. Из какой конфигурации он мог быть получен? Может быть, это усмешка? А может, трехточечный уголок — предблок? А может четырехточечная фигура, напоминающая квадратный корень? Или две параллельные черточки — одна длиной в 4 клетки, а другая — всего в 2? Или линия в 4 клетки и две точки рядом? Или еще какая-либо комбинация из точек и линий.
x = 37, y = 21, rule = S23/B3 bobbo12bo13boboo$bboo13boo13bo7$3boo13bobo10booboo$$b4o11b4o11b4obo8$o boobo9boboboo9boobboo$$b4o11b4obo7bob4obo!
А если еще учесть, что добавив к любой из этих фигур точку, искру домино, диагональную двухточечную искру или несколько таких искр в любом свободном месте поля так, чтобы при взаимодействии с другими элементами они ничего не родили в следующем поколении, мы все равно на следующем ходу получим блок, то напрашивается вывод, что родителей у блока не просто много, а бесконечно много. Но это же относится и к любой другой фигуре! Если мы нашли для нее хоть одного родителя — рассыпьте на свободном месте кучу искр, и вы получите сколько угодно родителей.
Здесь я употребил слово "родитель". Это общепринятый термин в игре Жизнь, означает он предыдущее поколение данного паттерна. Есть еще понятие "предок". Это конфигурация, которая в своем развитии приходит к данной. При этом количество поколений может быть любым. То есть родитель, это непосредственный предок, предок, который порождает данный паттерн всего за один шаг развития. Иногда применяется понятие "дедушка" — это родитель родителя, то есть предок, приходящий к данному паттерну за 2 шага. Интересно, что в сторону детей семейная терминология не продвинулась. Говорят просто "первое поколение", "второе поколение", а не "сын" или "внук". Иногда употребляется только общее "потомок", как антипод "предка".
Садом Эдема называется конфигурация, не имеющая родителей. Некоторые читатели могут удивиться — как же так, разве такое в игре Жизнь возможно? Да, для сложных конфигураций родителей найти трудно, но стоит обнаружить только одного, и их сразу станет бесконечное множество — только набросай искр на свободное место. Да и, ограничивая место вокруг паттерна в предыдущем поколении слоем всего в одну свободную клетку, чтобы избежать бесконечностей, и не интересуясь, что просходит на остальной части поля, мы можем посчитать число родителей для простейших паттернов. Так живая точка имеет 140 родителей, искра домино — 417, уголок-предблок — 1164. То есть имеется явная тенденция к росту числа родителей с ростом размера рассматриваемого участка паттерна. Откуда же могут появиться сироты в столь богатом родителями мире игры Жизнь?
В предыдущем рассуждении имеется логическая ошибка. "Если существует хотя бы один родитель" или "стоит обнаружить хотя бы одного родителя" — это только предположения. Если они верны, то вывод о бесконечном числе родителей верный. Но откуда мы взяли, что эти предположения верны? Из того, что все конфигурации, с которыми мы сталкивались, либо имели родителей, либо были очень сложны? Но из второго "либо" вообще ничего не следует. А тенденции — не доказательство. Если продолжить наш ряд дальше, мы увидим, что уже у блока 1005 родителей, то есть меньше, чем у предблока. Правда, далее, добавляя по спирали по одной живой клетке, мы увидим, что опять пойдет нарастание: P-пентамино — 3141, но предулей — 2835, далее 8797, 7918, 7268, 23415, 21576, 20648, 65342, 62390, 60038, 59165, 177559... Вроде рост побеждает, но есть и участки, где количество родителей уменьшается с ростом количества живых клеток.
Создатель игры Жизнь Джон Конуэй не задавался вопросом, есть ли сады Эдема в игре Жизнь. Он с самого начала знал, что есть. Дело в том, что он знал теорему о садах Эдема, которая была сформулирована и доказана намного раньше, чем была придумана игра Жизнь. И это не парадокс — в теореме нет упоминания об игре Жизнь, она формулируется для очень широкого класса клеточных автоматов, а игра Жизнь — только один из клеточных автоматов. И придумали этот клеточный автомат не для нашего развлечения, а как удобный объект для формулирования и доказательства некоторых математических утверждений, например, существования универсальных конструктора и компьютера. Так уж получилось, что математики из группы Конуэя на время увлеклись некоторыми не относящимися к основному вопросу аспектами игры Жизнь, а популяризатор Мартин Гарднер, искавший чего-нибудь такого занимательного для своей колонки в Научном Американце, увидел это и очень красиво описал.
Что же это за теорема такая, которая позволяет чуть ли не с первого взгляда на новый клеточный автомат сделать вывод о том, что в нем существуют такие неочевидные объекты, как сады Эдема? Пожалуйста, формулировка теоремы вмещается в одну строчку: Класс сюръективных клеточных автоматов совпадает с классом инъективных над конечными конфигурациями клеточных автоматов. И слава профессиональным математикам, которые сразу все поняли!
Я думаю, не все мои читатели профессиональные математики, поэтому посвящу немного места разъяснениям. Конечными конфигурациями или конечными паттернами считаются такие, которые имеют конечное число живых клеток. Здесь все ясно, следует только напомнить о том, что могут существовать клеточные автоматы не с одним, как в Жизни, а со многими живыми состояниями — они тоже учитываются в этой формулировке.
Теперь что такое инъективный? Инъективный клеточный автомат — это такой, в котором не существует двух отличающихся друг от друга конфигураций, отображающихся на одну и ту же конфигурацию. Это кажется непонятным, если не знать, что понимается под отображением. А отображение — это просто преобразование паттерна в результате смены поколения. То есть в Жизни, например, предблок отображается на блок, а блок отображается сам на себя. То есть, получается, что инъективный — это такой клеточный автомат, в котором не существует двух отличающихся паттернов, переходящих при смене поколения в одну и ту же конфигурацию. Жизнь под это слово никак не подходит — в ней куча примеров, когда две разные конфигурации переходят в одно и то же — только что мы рассматривали кучу вариантов получения блока. То есть, другими словами — инъективный клеточный автомат — это такой, в котором ни у одной конфигурации нет неоднозначного прошлого. Если прошлое есть (здесь я пытаюсь не упустить из рассмотрения сады Эдема, о которых мы пока еще ничего не знаем), то оно однозначно — вот это и значит инъективность.
Но теорема говорит не обо всех инъективных автоматах, а об инъективных над конечными конфигурациями автоматах. То есть о тех автоматах, в которых инъективность соблюдается для конечных конфигураций. Поскольку о бесконечных конфигурациях ничего не говорится, то для них инъективность может и не соблюдаться. Сформулируем еще раз, с чем же мы имеем дело: инъективные над конечными конфигурациями клеточные автоматы — это такие, в которых не существует двух отличающихся друг от друга конечных конфигураций, переходящих при смене поколения в один и тот же конечный паттерн. Или, можно сказать, нет конечных паттернов, имеющих больше одного родителя.
А что за зверь скрывается за словом "сюръективный"? Сюръективными клеточными автоматами называются такие, в которых каждая конфигурация является отображением некоторой другой кофигурации. Вспоминая, что отображение — это смена поколения, получаем, что сюръективные клеточные автоматы — это те, в которых все паттерны имеют родителей (заметьте, о числе родителей ничего не говорится кроме того, что они должны быть). Другими словами — это клеточные автоматы без садов Эдема.
Так вот, теорема, оказывается, утверждает, что все клеточные автоматы, в которых нет конечных конфигураций с двумя или более родителями, не имеют и конфигураций без родителей. И наоборот, все автоматы, в которых нет конфигураций без родителей, не имеют конечных паттернов с двумя или более родителями. Отсюда следует, что если бы в Жизни не существовало садов Эдема, то в ней бы и не было ни одной конечной конфигурации с несколькими родителями.
Вдумайтесь: существование садов Эдема следует из, казалось бы, противоположного факта наличия нескольких конечных родителей у хотя бы одной конечной конфигурации. Ясно, что здесь даже у блока родителей можно не искать. Достаточно рассмотреть пустое поле. Это конечная конфигурация. Оно образуется, во-первых, из пустого поля, во-вторых, при сгорании одной точки (тоже конечная конфигурация). Имеем двух родителей. Значит, сады Эдема есть!
Еще раз обращаю внимание на требование конечности паттернов при определении инъективности. В общем случае эта теорема выполняется только в одну сторону. То есть, инъективные в общем смысле клеточные автоматы будут инъективными и над конечными конфигурациями, а значит будут сюръективными (математики в этом случае говорят, что они биективны). Но из сюръективности следует только инъективность над конечными конфигурациями и вовсе не следует инъективность над бесконечными конфигурациями — она может быть, а может и не быть. Другими словами, если какая-либо бесконечная конфигурация имеет нескольких родителей — это еще не повод делать выводы о существовании садов Эдема.
Я хочу проиллюстрировать теорему о садах Эдема на упрощенном примере. Предупреждаю, что это не доказательство общего случая, а только иллюстрация того, как ее просто можно было бы доказать, если бы число возможных конфигураций было конечно. Такой случай имеет место, например, на поверхности тора — там число клеток конечно, а значит и конечно (хотя может быть и очень велико) число возможных конфигураций. Все паттерны на торе также конечны, так что выделять это не имеет смысла, хотя, как мы увидим, это обстоятельство и не используется далее. Мы будем говорить в дальнейшем не о торе конкретно, а просто об автомате с конечным числом паттернов. И еще раз хочу отметить, что это доказательство ни в коем случае нельзя переносить на бесконечную вселенную Жизни — там все сложнее.
Рассмотрим множество всех конфигураций. Пусть их количество равно N. Рассмотрим связи между конфигурациями согласно правилам данного клеточного автомата. Вы можете представить себе конфигурации в виде кружочков, а связи в виде стрелочек, исходящих из каждого кружочка и кончающихся на другом (а может быть и том же) кружочке. Так как будущее поколение всегда определяется однозначно, на каждую конфигурацию придется ровно одна исходящая от нее связь. То есть число связей тоже равно N. Допустим, что какая-то конфигурация имеет двух или более предков. Это означает, что число входящих связей для нее 2 или более. Значит, на остальные N-1 конфигурацию придется N-2 или менее входящих связей. Отсюда следует, что хотя бы для одной конфигурации не хватит входящей связи, то есть она окажется садом Эдема.
Могу предложить и другое наглядное представление — суть доказательства от этого не изменится. Пронумеруем все конфигурации числами от 1 до N и составим табличку, в первом столбце которой будут номера всех конфигураций по порядку, а во втором номера тех конфигураций, в которые превращаются за 1 ход соответствующие им конфигурации из первого столбца. Тогда, если во втором столбце хоть один номер встретится дважды, то хотя бы один номер там не встретится вообще, так как оставшихся N-2 мест во втором столбце не хватит, чтобы разместить все оставшиеся N-1 номера. Этот номер, не попавший во второй столбец, и будет номером сада Эдема.
Термин "сад Эдема" появился в теории клеточных автоматов намного раньше, чем была придумана игра Жизнь. Ассоциации создателей термина были такими: паттерн, не имеющий родителей, не может появиться во вселенной клеточного автомата в результате развития по законам этой вселенной. Он мог быть внесен в эту вселенную только извне подобно объектам, которые в нашем мире принято называть артефактами — объектам, привнесенным в наш мир искусственно каким-то высшим существом, не подчиняющимся законам природы. Напрашивается аналогия с богом и его творением. Таким творением согласно Библии был сад Эдема. И еще есть в этом намек на недолговечность садов Эдема — ведь только в начале истории он был исключительным объектом — творением божьим, а затем, подчиняясь земным законам, смешался с окружающим миром и стал неотличимым от него.
Но термин "сад Эдема" не укладывается в наметившуюся "родственную" схему именования паттернов — родитель, предок, потомок, дедушка. В этом смысле для него, наверное, подошло бы имя Адам, хотя в другом смысле — Адам — единственный праотец, предок всех живущих, а конфигураций без родителей может быть много. Да и сад Эдема по Библии был всего один, так что и он не очень подходит. Может быть поэтому, а может по другим соображениям Джон Конуэй предпочитал называть сады Эдема сиротами. Здесь и в "родственную" схему все ложится, и неисключительность таких конфигураций налицо. Только мистический смысл сверхъестественного творения несколько поблек — сироты в нашем мире вовсе не артефакты, и постоянно появляются в полном соответствии с его жестокими законами.
Игра Жизнь за годы ее существования несколько отошла от терминологии, которую употребляют в клеточных автоматах вообще. Так осцилляторами в игре Жизнь называются только неподвижные периодические объекты, тогда как в КА — любые, то есть в терминах игры Жизнь и осцилляторы, и космические корабли. Впрочем, космические корабли в клеточных автоматах называют чаще глайдерами, а в игре Жизнь глайдер — это конкретный вид космического корабля. Но вот предложенный Конуэем "сирота" поначалу не слишком прижился в игре Жизнь, намного чаще употреблялся термин "сад Эдема". И только когда поиском садов Эдема в Жизни занялся немецкий математик Ахим Фламменкамп, он придал термину "сирота" несколько другой смысл, и сейчас эти два термина означают близкие по смыслу, но неэквивалентные вещи. Это произошло не так давно, всего несколько лет назад, так что даже в последней версии словаря Жизни Стивена Сильвера от февраля 2006 года эти термины еще считаются синонимами.
Когда мы говорим о садах Эдема, требуется более строгий подход к терминологии, чем в других областях игры Жизнь. Вот, например, возьмем такие понятия, как "конфигурация", "паттерн" и "объект". Это синонимы или это разные понятия? Допустим, мы имеем два блока, расположенные на каком-то расстоянии друг от друга. Можем ли мы назвать каждый из этих блоков объектом? Да. А паттерном? Вроде тоже да. А конфигурацией? А конфигурацией уже нет. Во всяком случае, в том смысле, в котором мы употребляли это слово при доказательстве теоремы о садах Эдема, блок не есть конфигурация, если он не единственный на поле. Ведь конфигурация — это состояние всей вселенной игры Жизнь, в конфигурацию входят все точки — и живые точки объектов, расположенных в этой вселенной, и бесконечное число мертвых точек. И если где-то на удалении состояние одной точки будет отличаться, например она будет живой, то это будет уже другая конфигурация, отличная от той, где это точка мертвая. Несмотря на то, что эта точка никакого влияния на другие объекты не оказывает. И, если мы имеем две конфигурации, состоящие каждая из единственного блока, но эти блоки расположены в разных точках, то эти две конфигурации — разные.
Тогда объект — это часть конфигурации, выделенная по каким-нибудь признакам. Поэтому осцилляторы, космические корабли, натюрморты — это все объекты. Но и части объектов — это тоже объекты — искры, тагалонги, компоненты, радикалы, роторы и т.д. Но определение объекта, как части конфигурации не совсем верное. Слово "конфигурация" относится к одному определенному поколению, а объект часто подразумевает развитие. Пентадекатлон — это не пентадекатлон в определенном поколении — это пентадекатлон во всех своих пятнадцати поколениях. Навозные глыбы (ЛоМ) — это не только ступенчатое гексамино, но и рукопожатие, в которое оно переходит через 2 поколения, и все 64 формы, которые оно принимает, пока не окажется блокадой.
А что же тогда означает "паттерн"? А паттерн — это либо объект, либо конфигурация в зависимости от контекста, в котором это слово употребляется.
Если вы почувствовали разницу между конфигурацией и объектом, то вам будет понятна разница между садом Эдема и сиротой. Сад Эдема — это конфигурация, у которой нет родителей. То есть сад Эдема — это всегда вся вселенная игры Жизнь в одном из ее возможных состояний. Оно отличается от других состояний тем, что никакое из возможных состояний не может породить данное состояние. А сирота — это часть сада Эдема, какое-то количество живых и мертвых клеток, которое не может образоваться "естественным" путем, то есть по правилам Жизни. Есть еще понятие минимального сироты — это такой сирота, при изменении состояния любой клетки которого на противоположное он перестает быть сиротой. Ясно, что сирота — это та часть, которая делает конфигурацию садом Эдема. Во всей остальной вселенной может твориться что угодно — если на поле есть сирота, то эта конфигурация является садом Эдема. Найдя одного сироту, мы можем на его базе создать сколько угодно садов Эдема. Поэтому интерес представляет именно сирота. И простейший сад Эдема с найденным сиротой — это сирота, дополненный пустым полем. Обычно в таком виде и демонстрируют сады Эдема.
Но, дополняя сироту до сада Эдема, мы теряем информацию о том, какие мертвые клетки принадлежали сироте, а какие были добавлены при образовании сада Эдема. Поэтому при демонстрации именно сироты, а особенно минимального сироты, используют различные ухищрения, чтобы показать, какие клетки входят в него, а какие нет. На рисунках используют 3 цвета — для живых клеток, для мертвых клеток сироты и для безразличных клеток окружающей вселенной. Безразличные клетки обычно тоже считаются мертвыми, но они могут быть любыми — все равно будет получаться сад Эдема. Так как RLE формат не позволяет задать в игре Жизнь, да и в других автоматах два мертвых состояния, я, например, использую для изображения сироты следующий прием: слева изображаю сироту, а справа его маску, в которой как живые отмечены все клетки сироты — и живые, и мертвые. Тогда, чтобы узнать, входит ли данная клетка в сироту, надо только посмотреть на его маску.
Наверное, понятно, что количество садов Эдема в игре Жизнь бесконечно. Ведь имея даже всего одного конечного сироту, мы можем дополнять его до сада Эдема огромным количеством способов — бесконечным количеством способов на бесконечном поле игры Жизнь — и каждый раз будут получаться новые сады Эдема. Возникает вопрос, а каких конфигураций в игре Жизнь больше — имеющих родителей или садов Эдема? В общем случае сравнение двух бесконечностей бывает довольно сложным делом. Мы и не будем этого делать, а рассмотрим ситуацию на большом, но конечном подмножестве вселенной Жизни.
Рассмотрим долю сирот среди всех паттернов, умещающихся в прямоугольник A x B. Ясно, что при маленьких A или B в рассматриваемый прямоугольник не поместится ни одного сироты. Так нетрудно рассмотреть вручную все комбинации живых и мертвых клеток, прямоугольников 2 x 2 или 2 x 3 и убедиться, что все они могут быть получены при развитии других паттернов, то есть имеют родителей. Но так же ясно, что начиная с некоторых величин A и B некоторые комбинации живых и мертвых ячеек окажутся сиротами. Это тоже доказуемо, но для нас достаточно того факта, что такие комбинации (в игре Жизнь) обнаружены на практике.
Сейчас мы докажем, что сироты преобладают для некоторых достаточно больших размеров прямоугольника на поле Жизни. Причем, увеличивая размеры прямоугольника, мы можем сделать долю сирот сколько угодно близкой к 100%. Пусть доля сирот в прямоугольнике A x B равна конечному числу P. Рассмотрим прямоугольник MA x NB, больший первого прямоугольника в M раз по одной стороне и в N раз — по другой. Разобьем его на M x N прямоугольников первоначального размера. Перебрав все возможные комбинации живых и мертвых клеток большого прямоугольника, мы тем самым многократно переберем все возможные комбинации каждого из малых прямоугольников. При этом доля сирот в каждом из малых прямоугольников останется равной P. А доля не-сирот (1-P). Учитывая, что большой прямоугольник может оказаться не-сиротой только в том случае, когда все малые прямоугольники окажутся не-сиротами, получим, что доля не-сирот большого прямоугольника меньше, чем произведение долей не-сирот малых. То есть, меньше, чем (1-P)^MN. Так как (1-P) < 1, то всегда можно сделать MN достаточно большим для того, чтобы доля не-сирот большого прямоугольника оказалась меньше любого наперед заданного числа.
Теперь, почему мы перешли с категоричного "равно" на половинчатые "меньше" и "больше"? Потому что мы не учли тех сирот, которые входят в большой прямоугольник, но не входят ни в один из малых, так как располагаются в них только частично, разрезаясь границами между прямоугольниками. Мы не учли также тех сирот, чьи минимальные сироты имеют больший размер и не помещаются ни в один из малых прямоугольников. Но все эти неучтенные сироты только увеличат долю сирот большого прямоугольника, а мы и без них убедились, что можем выбрать размеры большого прямоугольника такими, чтобы доля сирот в нем была близка к единице.
Почему мы не стали рассматривать все возможные малые прямоугольники, полученные сдвигом одного из них на любое целое количество ячеек? Доля сирот каждого такого прямоугольника будет также равна P, но вот умножать доли не-сирот мы бы не смогли, так как такие прямоугольники не являются независимыми — некоторые из них имеют общие области. И в результате мы бы ничего не доказали.
Уже в 1971 году группа жизнелюбов из Массачусетского технологического института (так называемая M.I.T. группа) задалась вопросом о размере прямоугольника, достаточном для того, чтобы в его пределах мог существовать сирота. Путем сложных логических умозаключений Роджеру Бэнксу и Стиву Уорду при участии Рича Шроэппеля и Майка Билера удалось доказать, что для этого достаточно прямоугольника 9 x 33. Но исследователи не ограничились этим — Роджер Бэнкс провел трудоемкий компьютерный поиск в пределах указанного прямоугольника, и ему удалось найти одного из таких сирот, содержащего 226 живых ячеек.
x = 33, y = 9, rule = B3/S23 33o$oobob3ob3oboobobobobobobobobobo$obob3ob3ob4ob3obobobobobobo$5ob3ob 3ob4ob14o$oboboob3ob3obob3obobobobobobo$4ob3ob3ob5oboobobobobobobo$boo b3ob3ob3obobob13o$ooboob3ob3oboob4obobobobobobo$18ob14o!
Сейчас трудно предполагать, каким образом был получен именно этот образец сада Эдема, но, судя по его структуре, поиск включал следующие этапы. Сперва в качестве исходного образца пытались применить повторяющиеся узоры, которые являются садами Эдема на торе с небольшим размером поля. Такие сады Эдема очень легко находятся вручную. Вот два образца, которые на торах соответственно 4x4 и 2x6 являются садами Эдема:
x = 17, y = 6, rule = B3/S23 3o12boo$oobo12bo$b3o11bo$oboo11boo$15bo$16bo!
Наверное, таких кандидатов в структуру сада Эдема было больше. Но среди них надо было отобрать такие, которые образуют сады Эдема высотой в 9 ячеек на цилиндрах. То есть, это структуры, которые на бесконечном поле Жизни, имея высоту 9 ячеек и бесконечно повторяясь в обе стороны по горизонтали, близки к садам Эдема. Они не имеют родителей с шириной повторяющейся структуры, совпадающей с шириной исходного цилиндра, но могут иметь бОльшие ширины.
x = 17, y = 9, rule = B3/S23 oboo11boo$3o13bo$oobo11bo$b3o11boo$oboo11bo$3o13bo$oobo11boo$b3o12bo$o boo11bo!
Найти такие структуры тоже не слишком сложная задача. Но в сироте Роджера Бэнкса применены не эти структуры, а следующие, полученные из них заменой верхней и нижней горизонтальных линий на сплошные линии из живых ячеек. Они также являются садами Эдема на цилиндрах шириной 4 и 2 ячейки.
x = 17, y = 9, rule = B3/S23 4o11boo$3o13bo$oobo11bo$b3o11boo$oboo11bo$3o13bo$oobo11boo$b3o12bo$4o 11boo!
Из полученных бесконечных вдоль одной координаты конфигураций, близких к садам Эдема, вырезаются куски длиной в 33 ячейки, но вот беда — все они не являются сиротами. Для того, чтобы довести их до состояния садов Эдема, требуется некоторая их модификация, то есть изменение состояния некоторых ячеек. Но после каждого изменения состояния одной ячейки требуется проверка, является ли полученный образец садом Эдема. И нельзя предсказать, сколько именно вариантов придется перебрать, а число возможных вариантов может быть очень большим. Даже сейчас, когда время проверки на наличие родителей занимает доли секунды (дольше вручную менять состояние ячеек) на нахождение сада Эдема таким способом могут понадобиться иногда минуты, иногда часы, а, возможно, и дни. Что же говорить о 70-х годах — тогда, вероятно, проверка каждого варианта требовала нескольких часов расчетов. Хотя, конечно, многое зависит от опыта, которого первопроходцам, как обычно, взять негде. Вот, например, взяв первый вариант структуры без приведения верхней и нижней линий к сплошному варианту и изменив состояние всего 1 ячейки в образце, я получил сад Эдема. Правда, мне для этого пришлось перебрать около 30 вариантов замен. Работа отняла 10 минут вместе с вводом начальной структуры на рабочее поле программы WLS. Такой быстрый результат получен благодаря тому, что исходное заполнение прямоугольника очень близко к саду Эдема — ведь в цилиндрической вселенной шириной 4 это было садом Эдема, бесконечная полоса, образованная этим узором, имела небольшое количество родителей, а длина 33 достаточно большая для того, чтобы количество родителей, появившихся в результате обрезания бесконечного образца, было также малым, и его можно было свести в ноль небольшой коррекцией структуры.
x = 33, y = 9, rule = S23/B3 3ob3ob3ob3ob3ob3ob3ob3obo$ob3ob3ob3ob3ob3ob3ob3ob3o$b3ob3ob3ob3ob3ob3o b3ob3o$oob3ob3ob3ob3ob3ob3ob3oboo$3ob3ob3ob3ob3ob3ob3ob3obo$ob3ob3ob7o b3ob3ob3ob3o$b3ob3ob3ob3ob3ob3ob3ob3o$oob3ob3ob3ob3ob3ob3ob3oboo$3ob3o b3ob3ob3ob3ob3ob3obo!
Но, все мы умны задним умом. Кстати, длина этого сада может быть сокращена до 22 ячеек.
Исследователям, судя по всему, пришла в голову другая мысль — состыковать в пределах одного образца две разные структуры. За счет различий в структурах такая стыковка может значительно уменьшить число родителей (что, в общем-то, спорно). Сад Эдема сразу не получился. А тот результат, который мы имеем, говорит нам, что такой состыкованный образец потребовал значительных модификаций — было проверено не менее нескольких десятков, а возможно и нескольких сотен вариантов. Я представляю, сколько на решение этой задачи было потрачено такого дорогостоящего в то время машинного времени! Модификации производились в области стыка и на одном из концов. До другого конца, по-видимому, очередь не дошла — сад Эдема был найден раньше.
Вот таким образом, по моему предположению, создавался первый сад Эдема. Мне этот сценарий представляется вполне вероятным. Правда, участник тех событий Рич Шроэппель вспоминает другие варианты — составление огромных таблиц состояний, постепенное добавление столбцов в попытке уменьшить количество родителей, работы с полосами шириной 5, 6, 7 ячеек. "Правда, Роджер имел возможность работать с полосами в 9 ячеек..." — говорит он, но я думаю, что каждый из них шел немного своим путем, и каждый запомнил особенности именно своего поиска. А реализован был именно 9-ячеечный вариант ширины, самый трудный при последовательном добавлении столбцов, но вполне перспективный при использовании структур садов Эдема из цилиндрической Жизни. Да и следов индивидуального подбора каждого столбца в структуре полученного сада немного. Зато налицо периодичность структур.
Сейчас, если находится интересный в каком-либо смысле сад Эдема, то автор практически всегда находит для него минимального сироту. Тогда работа по поиску минимального сироты требовала очень большой дополнительной работы и значительного времени, да и важность этого еще не осознавалась. Я думаю, что как только первый сад Эдема был найден, все работы с ним были прекращены. Это и без того было огромным достижением. Конечно, позже, когда были созданы другие поисковые программы, найденный Роджером Бэнксом образец был проверен на отсутствие родителей, но никто его не пытался "пощупать" поплотнее. И только в июне 2004 года Ахим Фламменкамп заметил, что сад Эдема Роджера Бэнкса содержит целых 5 лишних колонок. То есть, если эти 5 колонок обрезать, мы получим паттерн размером 9 x 28, и он при этом будет оставаться садом Эдема.
Я нашел минимального сироту для первого сада Эдема. Вы можете сравнить его с образцом 1971 года и увидеть, сколько ячеек в нем можно удалить, а он при этом так и останется конфигурацией, не имеющей родителей. Напоминаю, что слева расположен сам образец, а справа его сиротская маска, которая указывает, какие ячейки образца должны находиться в том состоянии, которое указано на образце слева. Состояние остальных ячеек может быть любым, поскольку они не входят в состав минимального сироты. Итак, первый найденный сад Эдема (171 бит, 228 обязательных ячеек).
x = 68, y = 9, rule = S23/B3 b5obboob4ob3oboo19b5obboob4ob3oboo$bobob3oboboboobobobobobobo14b9ob16o $obob3ob3ob4ob3obobobo14b27o$b4ob3ob3ob4ob8o14b26o$oboboob3ob3obob3obo bobobo12b28o$4ob3ob3ob5oboobobobo13b27o$boob3ob3ob3obobob8o12b28o$oob oob3ob3oboob4obobobo13b28o$oob3ob3obb6ob3ob5o12boob3ob3obb10ob5o!
В 1973 году Жан Ардуэн-Дюпарк из университета Бордо I, Франция выпустил статью, посвященную определению минимально возможной ширины сада Эдема в игре Жизнь. По всей видимости, в его статье было показано, что садов Эдема с шириной менее, чем 6 ячеек, существовать не может. Для того, чтобы доказать существование садов Эдема шириной 6 ячеек, Жан Ардуэн-Дюпарк провел компьютерный поиск таких садов Эдема. Ему удалось найти 2 таких образца — один длиной 122 ячейки, а другой длиной 117 ячеек. К сожалению, информации об этих садах Эдема больше никакой нет. Мне не удалось найти изображений самих паттернов — в имеющемся у меня скане статьи никаких изображений или RLE-диаграмм нет, как нет их и в коллекциях любителей игры Жизнь. К тому же, статья на французском языке, что позволяет судить о ее содержании только по весьма кратким резюме некоторых жизнелюбов старшего поколения. Так, в Словаре Жизни Стивена Сильвера об этом всего одна фраза. Переводов статьи на английский и тем более на русский язык обнаружить не удалось. В таком же положении находится, насколько я знаю, Ахим Фламменкамп, который тоже говорит о содержании этой статьи в весьма предположительных тонах. Если кто-либо из моих подписчиков может переводить с французского и имеет математическое образование (статья написана профессиональным математиком, и переводить ее не-математику бесполезно), то я бы мог выслать этому человеку сканы статьи и был бы очень благодарен за перевод.
В конце 1990 — начале 1991 года поиском садов Эдема занялся немецкий математик Ахим Фламменкамп. Им была разработана программа для поиска садов Эдема, впрочем, сведения о ней весьма скупы. В январе 1991 года был обнаружен сад Эдема размером 14 x 14 и количеством живых клеток 143.
x = 14, y = 14, rule = S23/B3 ooboboboboobo$ob3ob3oboobo$4ob3oboobo$3obobobob4o$b3obob3oboo$7ob4obo$ bobob8o$ob3oboobobobo$6ob6o$oboob5obobo$3ob9o$b3obobobob3o$3oboboboboo bo$ob12o!
Напомню, что сад Эдема Роджера Бэнкса имел, с учетом последующих уточнений, 171 бит. Но и для этого сада Эдема не был найден минимальный сирота — в 1991 году не хватало для такого уточнения мощности компьютеров, да и программ, которые могли бы достаточно быстро идентифицировать сад Эдема, тоже не было. Поэтому Ахим ограничился только идентификацией самого сада Эдема. Сейчас все условия для определения минимального сироты появились. Ниже я привожу минимального сироту для этого сада Эдема. Как видим, он имеет всего 127 живых ячеек и 175 обязательных.
x = 39, y = 14, rule = S23/B3 ooboboboboobo12boob10o$ob3ob3oboo13b13o$b3ob3oboobo13b13o$boobobobob4o 12b13o$b3obob3oboo12b14o$7ob4obo11b14o$bobob8o12b13o$ob3oboobobobo11b 14o$6ob6o12b13o$oboob5obo13b13o$3ob9o12b14o$b3obobobob3o12b13o$boobobo bobbo14b9oboo$bb4o20b5o!
По-видимому, нахождение этого сада Эдема оказалось тогда почти на пределе вычислительных возможностей персональных компьютеров, а старинный рецепт (от 1971 года) получения практически без компьютера близких к садам Эдема структур был забыт, так, впрочем, ни разу по-настоящему и не реализовавшись. Во всяком случае, прошло еще 13 лет, прежде чем работы по поиску меньших садов Эдема были продолжены.
14 июня 2004 года Ахим Фламенкамп сообщает сообществу любителей игры Жизнь, что он доработал свою старую программу по поиску садов Эдема, и она после нескольких часов работы нашла 92 сада Эдема размером 13 x 13. Поработав с полученными паттернами, он улучшил один из них, уменьшив его до размера 13 x 12. При этом минимальный сирота имел всего 81 живую ячейку и 136 обязательных ячеек.
x = 33, y = 12, rule = S23/B3 bbob3o15b6o$oobob5obo8b12o$oboboobobo10b12o$b4obob3o9b12o$oboboob3obo 8b12o$b3oboobobo9b12o$bbo3b3obboo7b13o$bobooboboboo8b12o$3ob4obobo8b 12o$bob4o3bo10b11o$boboboobbo11b11o$boobobboobbo9b11o!
А дальше, как говорил Льюис Кэролл, начинается путаница.
23 июня 2004 года Ахим Фламменкамп находит сад Эдема, вписывающийся в прямоугольник 11 x 12. Он имеет 72 живых ячейки и 113 обязательных. Это явно новое достижение — побиты рекорды и по ограничивающему прямоугольнику, и по числу живых ячеек, и по обязательным ячейкам. Но почему-то Ахим об этом никому не сообщает. Вот этот сад Эдема.
x = 32, y = 11, rule = S23/B3 bobooboobbo10b10o$bbob3ob3o10b10o$bboob3obobo10b10o$bob3ob3obo9b11o$5o bb4o9b12o$boob3obobbo8b12o$b3obobobbo10b11o$boob3obboo10b11o$ob3ob3obo 9b12o$obboobbobobo8b12o$10bo18boo!
В январе 2005 года выходит 23 версия Словаря Жизни Стивена Сильвера. В статье "Сад Эдема" в качестве иллюстрации приводится не сад Эдема от 1991года, как во всех предыдущих версиях Словаря, а новый сад Эдема от 14 июня 2004 года. В 24 версии Словаря, вышедшей в феврале того же года, в качестве рекордного приводится тот же, уже устаревший, сад Эдема размером 12 x 13.
Через год — 11 февраля 2006 года я получаю письмо от некоего Андрея из Киева, в котором тот просит меня объяснить, как может быть построен алгоритм поиска предков конфигураций игры Жизнь. Я, как могу, рассказываю ему об этом. Заодно рассказываю о поисковой программе WLS, куда такой алгоритм изначально встроен, и в качестве "бонуса" подробно объясняю, как с помощью этой программы определить, является данный пример сиротой или нет. Чтобы не ошибиться в мелочах, я запускаю программу, ввожу на ее поле минимальную известную мне конфигурацию сада Эдема, то есть конфигурацию от 14 июня 2004 года, и начинаю с ней играть.
Все, что нужно для написания ответа Андрею, уже уточнено, но вот конфигурация на поле очень уж занозистая. И заноза — это единственная живая ячейка, торчащая вправо и занимающая целый столбец. Вот если бы ее не было, то паттерн бы вписывался в квадрат 12 x 12. Убираю эту ячейку — естественно, тут же находятся родители. Пытаюсь изменить состояние других ячеек — в одних случаях первый родитель находится сразу, в других — программа на некоторое время задумывается, но родителя все равно находит. Если бы дать ей возможность найти всех родителей, то по числу родителей можно судить, насколько мы близки к саду Эдема. Но поиск всех родителей — это значительное время расчета. Тогда я принимаю за условный критерий близости к саду Эдема число итераций программы до нахождения первого родителя, понимая, что этот параметр только чуть-чуть коррелирует с тем, что мне нужно, и сильно зависит от других факторов, например от порядка опроса ячеек. Испытываю ячейку за ячейкой, оставляя измененными те, что значительно увеличивают время поиска первого родителя. Ячейки кончаются, иду по второму кругу. Время расчета каждого варианта также увеличивается. Наконец, на исходе второго часа ковыряния в недрах бывшего сада Эдема программа выдает: количество найденных объектов — 0! Сад Эдема, в который не очень-то и верилось — слишком авантюрным был способ поиска — найден. Удовлетворенный, пишу короткое сообщение в сообщество любителей Жизни, а Андрею сообщаю, что ответ на его вопрос я сообщу завтра, и ложусь спать.
Оказалось, что в итоге я всего лишь переставил на другие места 2 живые ячейки, не считая удаленной "торчащей". Параметры полученного сада Эдема: 12 x 12, 80 живых ячеек и 134 обязательных.
x = 32, y = 12, rule = S23/B3 bbob3o15b6o$oobob5obo8b12o$oboboobobo10b12o$b4obob3o9b12o$oboboob3obo 8b12o$b3oboobobo9b12o$bbo3b3obbo8b12o$boboobobobo9b12o$3ob4obobo8b12o$ oob4o3bo9b12o$boboboobbo11b10o$boobobboobo10b10o!
В следующей версии словаря Жизни в качестве примера минимального сада Эдема был уже мой вариант Ахимовского сада, как и полагается, со всеми необходимыми оговорками относительно небольшой моей доработки.
Удивительно, как равнодушны средства массовой информации ко всяким непонятным им "заумным" вещам, но как они любят ухватиться за единственное как-бы понятное им красивое слово "сад Эдема" и, несмотря на то, что это слово может употребляться совсем в другом смысле, сразу с жаром рассказывать о чем-то ТАКОМ. Уже через полгода моя фамилия склонялась в интернете на всех языках мира от корейского до албанского. И это не смотря на то, что она вообще не склоняется. :) И не смотря на то, что мое достижение — всего лишь случайность. Я не занимался проблемой садов Эдема, не нашел до этого ни одного сада, да и этот был найден Ахимом — вся моя роль в этом — только незначительное улучшение его параметров. Я не пользовался никакими специальными методами, не составлял никаких программ — просто пару часов от нечего делать потыкал мышкой в коврик.
И кроме того, мой паттерн не был рекордным — давно существовал 11 x 12 образец Ахима Фламменкампа. Как выяснилось, он все это время был выложен на сайте Ахима, но в силу не слишком удачного дизайна сайта остался незамеченным. Ведь чтобы перейти на страничку со следующими достижениями, надо после риторического вопроса: А можете ли вы сделать лучше? ткнуть мышкой в короткую ссылку YES. Причем первоначально на протяжении многих лет этой ссылки вообще не было — была страничка с садом Эдема 1991 года, а риторический вопрос был просто риторическим вопросом. Затем появилась ссылка YES на страничку, где был представлен 12 x 13 образец, а уже с этой страницы через аналогичный вопрос и аналогичное YES можно было попасть на страничку с садом Эдема 11 x 12. Там тоже был аналогичный вопрос, но ссылки YES пока не было. В настоящее время череда страничек увеличилась, и, чтобы добраться до самого последнего рекорда, вам придется пройти значительный путь через все предыдущие достижения. Естественно, более-менее постоянные посетители сайта Ахима Фламенкампа заглядывали туда, но, не вчитывались в уже знакомый текст, а, видя каждый раз одно и то же, покидали ее.
Такая "матрешка" с сюрпризом обнаружилась в декабре 2007 года после того, как один из внимательных интернет-читателей, посетитель блога Генриха Кенига обратился к Кенигу с недоуменным вопросом по этому поводу.
Но, так или иначе, а несправедливо свалившуюся на мою голову славу надо было отрабатывать. Тем более, что тема эта интересовала меня давно.
Еще в 2003 году я написал несколько, впрочем, достаточно элементарных, программок, подсчитывающих количество родителей. В общих чертах был понятен алгоритм, как это можно использовать для поиска садов Эдема. Даже заготовка нынешней программы с серым полем и заголовком Eden была сделана тогда. Помню, меня удивила шустрость программ, ищущих родителей, при обработке огромных массивов информации. Удивила, но недолго радовала. Как только величина динамических массивов достигала пределов оперативной памяти, начинались жуткие тормоза. У меня стояло тогда 256 Мб, это по тем временам было очень неплохо. Помню, как наш сисадмин ходил обалделый, когда поставил на сервер гиг! Но оказалось, что хваленая виртуальная память, якобы расширяющая пределы оперативки — это фикция. То есть, она расширяет оперативку, когда выталкивает заснувшую задачу в своп-файл, а в микросхемы ОЗУ вместо нее помещает активную. Но если одна задача использует больше памяти, чем имеется, то своп-файл превращает коня в черепаху.
И было ясно, что добавление памяти до 512 Мб и даже до тогда почти нереального гига ничего не изменит — я смогу увеличить исследуемый образец на несколько клеток и достигну нового предела. Мне требовались объемы, в десятки раз большие. Мне нужны были объемы, сравнимые с объемами тогдашних винчестеров. А в некоторых случаях превышающие их. Поэтому поиск садов Эдема был отложен до лучших времен.
В апреле 2007 года я вернулся к программе LifeEden, впрочем, ненадолго. Был отлажен интерфейс — рисование-уничтожение клеток на поле программы, и, уже не помню по какой причине, все снова заглохло.
К лету 2009 года практически исчерпала себя программа RandAgar (это — отдельная тема), и я решил разморозить старый недострой — программу по поиску садов Эдема. Идея, которую хотелось попробовать на первых порах, была простой. Человек мышкой рисует на поле программы паттерн (левой кнопкой — живую ячейку, правой — мертвую, этими же кнопками можно откорректировать состояние или убрать уже нарисованную ячейку). Компьютер на каждое изменение паттерна реагирует соответствующим образом: добавляет или убавляет ячейки — соседи, выделяя их своим цветом, затем на множестве всех ячеек с явно указанными состояниями и их соседей рассчитывает всех родителей данного паттерна. Причем расчет множества родителей ведется на базе результатов предыдущего расчета — таким образом мы можем сильно уменьшить время расчета. Естественно, это же накладывает и некоторые ограничения на возможности корректировки уже введенных ячеек паттерна — можно корректировать или убирать только одну ячейку, а именно последнюю введенную. При корректировке других ячеек можно было бы использовать другой алгоритм расчета множества родителей, типа того, который применяется в программе WLS, но, во-первых, это будет работать намного медленнее, то есть, в этом месте программа задумается надолго, а во-вторых, пока я обходился без таких корректировок. Поэтому эта часть программы до сих пор не написана, и если попытаться скорректировать или убрать не последнюю введенную ячейку, а какую-либо иную, то видимая корректировка поля будет произведена, а вот изменения в массив родителей не будут внесены, и все последующие расчеты окажутся неверными.
Именно для сохранения массива родителей и требуется так много памяти. Сам расчет производится следующим образом — последовательно читаются все родители, сохраненные при вводе предыдущей ячейки. Для каждого родителя перебираются все возможные состояния вновь появившихся соседей, и если по правилам жизни это дает введенное пользователем состояние, новая конфигурация родителя записывается в другой массив, в противном случае — в альтернативный массив. В следующем расчете в качестве исходного будет использоваться либо этот "другой", либо альтернативный массив в зависимости от того, оставит пользователь введенное им состояние неизменным или заменит его на противоположное. Из-за большого количества родителей, особенно в середине расчета, массивы приходится выполнять в виде файлов на жестком диске компьютера, это же вынуждает нас запускать программу только с диска, на котором есть не менее 30, а лучше 100 Гб свободного места.
Рассчитанное число родителей выводится на экран компьютера. При этом выводится и результат предыдущего расчета. Сравнивая эти числа с учетом того, сколько новых ячеек добавилось в родительский паттерн, можно сделать какой-то вывод о том, насколько соответствует состояние установленной ячейки нашей цели — получить в конечном итоге сад Эдема. Может быть, стоит изменить его на противоположное, если это снизит число родителей. Вот и вся программа. По-существу, только последовательный подсчет родителей с выводом результатов. Интерпретация результатов и принятие решений по возможному изменению состояния ячейки, а также последовательность добавления ячеек к паттерну — все это доверяется пользователю. Мне и нужна была такая программа, которая позволила бы определить некоторые особенности процесса поиска и понять, в каком направлении двигаться дальше.
После первых пробных запусков выяснилось два обстоятельства. Во-первых, самый простой и очевидный алгоритм — выбирать для каждой устанавливаемой ячейки то состояние, которое в этот момент имеет меньше родителей — далек от совершенства. Мне не удалось закончить ни одного паттерна, строившегося по этому алгоритму. С ростом размеров образца нарастало количество родителей, потом оно достигало максимума, затем медленно начинало снижаться. И когда до заветного нуля оставалось установить совсем немного, может быть, 20-50 ячеек, достигался предел программы — 256 ячеек в родительском образце. Да и образец получался слишком насыщенным живыми ячейками. Например, если устанавливать ячейки по спирали, закрученной вокруг первой ячейки, то согласно этому правилу все первые 41 ячейки окажутся живыми, и только 42-я ячейка будет мертвой. Далее мертвые ячейки встречаются несколько чаще, но общая плотность получается удручающе высокой. А те примеры садов Эдема, которые мы имели к этому времени, были намного менее плотны. И лучшие из них имели меньшие размеры.
Поэтому было решено в тех случаях, когда установка живой ячейки дает меньше родителей, чем установка мертвой, но разница не слишком значительна, устанавливать мертвую ячейку. Мы жертвовали тактическим преимуществом при построении сада Эдема, но обычно уже следующая живая ячейка снижала число родителей настолько, насколько две живые, установленные подряд, не смогли бы снизить. Но было неизвестно, какую разницу считать значительной, а какую нет. Поэтому был введен параметр, названный форой, меняя который, можно было менять преимущество, передаваемое мертвым ячейкам.
В целом, ситуацию можно уподобить игре, в которую играют два игрока. Один ставит черные фишки (живые), другой — белые (мертвые). Цель — привести число родителей к нулю. Черный изначально играет лучше, то есть каждый его шаг с большей вероятностью снижает число родителей на данном этапе. Он ленив, зачем ему стараться, если он лучше. Он снижает число родителей, но чуть-чуть. Но для достижения конечной цели каждый данный этап не так важен — важна общая скорость снижения родителей. И она может быть достигнута, если дать белым некоторую фору — разрешить им ставить свои фишки не только тогда, когда это снижает общее число родителей, но и тогда, когда это немного повышает его. При этом и черные начинают играть лучше — у них как бы появляется интерес к игре. И общий результат улучшается.
Фора задается в процентах к среднему. То есть, если на данном этапе построения сада Эдема установка живой ячейки даст паттерн, имеющий 900 родителей, а установка мертвой — 1100 родителей, то среднее число родителей будет 1000. Допустим, при этом используется фора 15%. Это значит, что граница, по которой отдается преимущество, составляет 1000-1000*0.15=850. То есть, живая ячейка была бы установлена, если бы она давала до 850 родителей, но так как она дает 900, то надо установить мертвую. Число родителей на данном этапе повысится, но на следующем этапе или через этап это повышение будет скомпенсировано.
Второе обстоятельство состояло в том, что учет форы в уме — достаточно утомительное занятие, чреватое ошибками, поэтому в интерфейс программы были внесены изменения. Добавилось окошко для ввода форы (обычно перед началом поиска, хотя не запрещается и на любом другом этапе построения) и поле, где высвечивался рекомендуемый цвет. Цвет высвечивается после окончания расчета количества родителей. Если он совпал с цветом установленной ячейки, вы предугадали правильно и можете продолжать. При несовпадении цвета, вы можете изменить цвет ячейки на рекомендуемый. Впрочем, решение всегда остается за человеком. Если же вы во всем доверяете своему компьютеру, то можете поставить галочку, включающую автокоррекцию, и компьютер сам будет менять цвет ячейки на поле на рекомендуемый. В этом случае вам остается только указывать компьютеру следующую ячейку. Что бы вы туда ни поставили, компьютер все равно все поправит в соответствии со своими рекомендациями (точнее, в соответствии с установленной вами форой).
После переделки программы с форой 10 % был получен первый мой сад Эдема. На него ушло не больше часа (предыдущие попытки отнимали по несколько дней). Он не бил рекорды (12x13), но это был созданный с нуля своими руками сад Эдема!
После этого начались эксперименты с разными величинами форы, разным порядком строительства. Пробовались разные ширины паттерна, начиная от 8, при этом значении уже не хватало длины, а предел в 256 клеток родителя исчерпывался (то есть, намечавшиеся сады эдема имели длину более 23, соответственно, родители должны были быть длиннее 25 при ширине 10). Принудительно вводились неестественные начала, например квадрат 2x2 из мертвых ячеек в центре паттерна, или произвольный симметричный узор, вокруг которого наращивался уже с учетом форы сам паттерн. Были попытки половину строительства вести на одной форе, а вторую половину — на другой. Получался сад эдема, например, с малой плотностью в центре и плотной "корочкой". Была выявлена верхняя граница форы (около 40 %), при которой получавшиеся паттерны уже, как и при низких форах, не укладывались в лимит. В качестве начала сада Эдема вводился фрагмент предыдущего найденного сироты, и уже вокруг него шло новое строительство.
Сады Эдема получались, количество найденных сирот росло, но все они были немного великоваты. Единственный сад размером 11x12 получился, когда в качестве начальной затравки был использован фрагмент рекордного сада Эдема Ахима Фламменкампа. И то, по количеству живых и обязательных ячеек он не дотягивал до Ахимовского сироты.
В то же время все более крепло мнение, что в квадрате 14x14 садов Эдема не так уж мало. Можно было выбирать почти произвольное, но не слишком "пустое" начало в пределах 5x5, или можно было вопреки основному алгоритму допускать до десятка "ошибок" среди точек первой сотни — в дальнейшем все эти "возмущения" заглаживались, и получались сады Эдема. И другое мнение возникало. Что мой алгоритм "игры с форой" весьма далек от оптимального. Он корректирует только одну клетку, а этого явно мало. Нужен алгоритм, работающий на большую "глубину". Правда, при глубине в 2 ячейки понадобится уже 7 дисковых массивов, а при 3 — 15. Соответственно возрастет и время расчета.
Но для начала хотелось посмотреть, насколько мой алгоритм отличается от чисто случайного раскрашивания ячеек — может быть уже при 14x14 доля садов Эдема достаточно велика? В дальнейшем я внес некоторые изменения и попробовал чисто случайное заполнение. И убедился, что "игра с форой" все-таки чего-то стоит. Случайное заполнение дает только невероятные тормоза, и даже до признаков начала снижения числа родителей не удается добраться (правда, именно из-за тормозов — до заполнения квадрата еще очень далеко). Чтобы избежать этих тормозов, не нужно подсчитывать родителей после добавления каждой ячейки, ведь эти числа не используются — надо добавить сразу все ячейки, а потом считать родителей уже другими методами. Тогда можно замерить долю садов Эдема в зависимости от размеров поля. Это интересная задача, но пока я к ней не готов.
А потом пришла немного безумная идея попробовать построить симметричный сад Эдема. Ведь до этого было твердое, хоть и никем никогда не высказанное мнение, что сады Эдема должны быть асимметричны. И все предыдущие сады бывали несимметричными, и мой алгоритм тоже избегал симметрии. А если попробовать делать симметрично? Первую точку ставим по рекомендации компьютера в соответствии с форой, а следом симметричные ей красим в тот же цвет, даже если рекомендации будут другими. Попробовал. Сразу пришлось снизить фору, иначе получалась слишком низкая плотность (было еще и такое заблуждение, что оптимальной должна быть плотность 0.6-0.8). Итак, при форе 7% получилось несколько садов Эдема с разными типами симметрии. Хоть по-прежнему великоватые, но некоторые из них красивые, напоминающие цветы. Это уже было интересно. Ничего подобного никто никогда не получал.
Например, этот сад Эдема. Он имеет 3 минимальных сироты (если не учитывать полученных из них поворотами и отражениями), которые менее симметричны, чем сам сад Эдема.
x = 89, y = 14, rule = S23/B3 3bobboobbo17b8o17b8o17b8o$3bob4obo15b12o13b12o13b12o$bboboboobobo14b 12o13b12o13b12o$oobob4oboboo11b14o11b14o11b14o$bboboboobobo13b14o11b 14o11b14o$bobob4obobo13b13o12b13o12b12o$14o11b14o11b14o11b14o$14o11b 14o11b14o11b14o$bobob4obobo13b13o11b14o11b14o$bboboboobobo13b14o11b14o 11b14o$oobob4oboboo11b14o11b14o11b14o$bboboboobobo14b12o13b12o13b12o$ 3bob4obo15b12o13b12o13b12o$3bobboobbo17b8o17b5oboo17b8o!
А этот сад Эдема избыточен. Лишние живые клетки здесь присутствуют только для симметрии. У него также насколько минимальных сирот, показаны маски двух из них. Как видно, пожертвовав степенью симметрии можно даже уменьшить размер ограничивающего прямоугольника.
x = 65, y = 15, rule = S23/B3 5bo3bo20bo3bo20bo3bo$bb3obobob3o14b11o14b11o$bobob5obobo13b12o13b12o$b oobob3oboboo13b12o12b13o$boboob3oboobo12b13o12b13o$obobbobobobbobo12b 13o12b13o$b4ob3ob4o12b13o12b13o$bb11o13b13o12b13o$b4ob3ob4o12b13o12b 13o$obobbobobobbobo10b15o11b14o$boboob3oboobo12b13o14b11o$boobob3obob oo13b12o13b12o$bobob5obobo14b11o14bob9o$bb3obobob3o16b5obo19b4oboo$5bo 3bo20bo!
Два сада Эдема с поворотной симметрией, полученные при разных значениях форы. У первого показана только одна из возможных минимальных масок. Как видим, этот сад Эдема также содержит несколько не обязательных живых клеток, которые обеспечивают только симметрию. Как и у предыдущего сада Эдема, у этого тоже можно найти сиротскую маску, которая бы уменьшила размер ограничивающего прямоугольника. У второго сада Эдема симметричны как сам сад, так и его сиротская маска.
x = 38, y = 38, rule = S23/B3 bbob3o20b5o$b4obobbobo14b11o$bboobobob4o13b10o$b4obb5o14b12o$3bobobobo boo13b12o$bb3obobobobo13b11o$oo3b3o3boo13b11o$obobobob3o15b11o$oobobob obo15b12o$b5obb4o13b12o$4oboboboo16b10o$bobobbob4o14b3ob6o$6b3obo20b5o 13$bobobooboboo13b4oboob5o$ob4ob4obo12b13o$4ob3ob3o13b13o$b4ob7o12b13o $oobobobobobo13b12o$b4obobob3o13b12o$oboob3oboobo12b13o$3obobob4o13b 12o$boboboboboboo13b12o$7ob4o13b13o$b3ob3ob4o12b13o$ob4ob4obo12b13o$b ooboboobobo13b5oboob4o!
К этому времени у меня возникло предположение, что мой алгоритм не слишком правильно рекомендует состояние устанавливаемых ячеек в конце поиска, когда количество родителей становится невелико. В результате поиск затягивается, появляются лишние ряды ячеек, которые в оптимальном случае, возможно, и не появились бы. Я решил увеличить количество родителей за счет оставленного в центре паттерна квадрата 2x2 с неопределенным состоянием. Предполагалось, что структура построенного сада Эдема окажется более оптимальной, что позволит после его построения за счет подбора состояний ячеек центрального квадрата сократить несколько строк и столбцов, и, возможно, достичь меньшего размера.
Построение оказалось очень трудоемким. Количество родителей промежуточных паттернов было огромно. Расчет каждой следующей точки отнимал иногда до 8 часов. А в результате оказалось, что сад Эдема не помещается в предельные для моей программы габариты 14x14. Правда, сделав определенными 2 из 4 центральных точек, я превратил недостроенный образец в сад Эдема, но оставшихся двух точек было слишком мало для существенного сокращения размеров.
Поэтому этот расчет дал только одно: впервые был получен сад Эдема с отверстием в центре сиротской маски.
x = 33, y = 14, rule = B3/S23 ob3ob5obo7b13o$3obobooboboo7b13o$oboboobbobobo7b13o$bobobbobooboo7b13o $ob3obboob3o7b13o$bobboobobbo9b13o$oobobo3boboo7b6ob6o$bbobboboo11b6ob 6o$bobboobob3o8b13o$obboobobobobo7b13o$oboobo3b4o7b13o$b3obbobobo9b12o $4obob3obo8b12o$4bob5o12b9o!
Но вот в области симметричных садов Эдема еще далеко не все было ясно. Я начал очередной поиск паттерна с поворотной симметрией, поставив фору на уровне 20%. Ничего хорошего от этого варианта я не ждал: у меня к этому времени сложилось убеждение, что оптимальная фора не превышает 15%, а для симметричных образцов она должна быть еще меньше. Но меньшие значения форы для этого типа симметрии уже пробовались. И вот всего через 20 минут построений, количество родителей резко начало уменьшаться и быстро обратилось в ноль. А размер паттерна был всего 11x11! Это был новый рекорд. На следующий день я нашел для него сиротскую маску, и новый сад Эдема (вместе с другими найденными мной за это время, но не столь выдающимися садами Эдема) был отправлен любителям игры Жизнь.
x = 31, y = 11, rule = S23/B3 b3obboo13b7o$boobobob3o10b10o$b3obb5o10b10o$obobobobobo9b11o$4obobobo 10b11o$4b3o13b11o$bobobob4o9b11o$obobobobobo9b11o$5obb3o10b10o$3obobob oo10b10o$3boobb3o13b7o!
Позже этот сад Эдема был назван цветком Эдема. Его параметры: 69 живых ячеек, 109 обязательных. 90-градусная поворотная симметрия. Представлен в LifeCA group 6 сентября 2009 года.
После этого началась доработка программы LifeEden. Меня уже не устраивал ручной способ поиска, когда для добавления каждой ячейки я должен был тыкнуть мышкой в поле. Мне хотелось, чтобы компьютер делал это сам. Но для этого он должен был знать заранее порядок поиска. Я задал жесткий порядок поиска — спираль вокруг начальной ячейки. Но если порядок поиска один и тот же, и фора не меняется, то будет находиться один и тот же паттерн. Поэтому вместо жесткого значения я предусмотрел диапазон, в котором может находиться фора. А сама величина форы для каждой новой ячейки выбирается случайно с равномерным распределением в заданном диапазоне. Это позволило для не слишком узких диапазонов получать каждый раз другой сад Эдема.
Еще надо было сохранять найденные паттерны. Я не стал переводить каждый найденный сад Эдема в RLE формат и сохранять его в отдельный файл, полагая, что большая часть из них не понадобится. Вместо этого результаты записываются в один и тот же LOG-файл, причем каждый сад Эдема занимает в этом файле всего одну строчку. При этом в лог-файл пишется и число ячеек найденного образца, что позволяет сразу оценить его размер. А для конвертации отдельных паттернов из лог-файла в LIF формат написана отдельная программка Log2Lif. Эта же программка отображает выбранный паттерн и выдает некоторые его параметры, в частности, число живых ячеек.
По-началу, доработанная программа начала бойко выдавать ошибочные результаты. Полученные паттерны практически всегда не являлись садами Эдема, но отличались от них незначительно, и их легко можно было с помощью небольшой подгонки "напильником" (то есть программой WLS) превратить в сады Эдема. Но позже, когда ошибка была найдена и исправлена, оказалось, что доля найденных маленьких паттернов также снизилась.
Программа работала день и ночь, выдавая огромное количество садов Эдема. Но большая часть их имела размеры, большие чем 12x12. Садов 11x12 при самых удачных выборах диапазонов находилось 2-3 штуки в день, а сад 11x11 появлялся в результатах приблизительно раз в неделю. Где-то через месяц общее количество найденных программой садов Эдема превысило 10000.
При этом, как правило, более крупные сады Эдема отнимали и больше времени для построения, поскольку имели в середине построения намного больше родителей. Поэтому в программу был встроен механизм раннего выявления таких "неперспективных" случаев и прекращения расчета для них. Сперва это было просто ограничение на количество родителей. Затем оно было доработано до линейной функции, учитывающей минимальное значение числа родителей для данной точки построения с некоторым заданным коэффициентом и постоянную составляющую. При применении ограничений выход маленьких садов Эдема увеличился, хотя общее количество найденных образцов уменьшилось.
В последних версиях программа сама решает, где располагать массивы родителей — в памяти компьютера или на жестком диске. Пока массивы небольшие, все происходит в памяти. Если величина массива превосходит некоторую заранее заданную величину, этот массив будет расположен на диске. Это ускоряет время расчета в начале, то есть пока паттерн еше маленький, и в конце, когда паттерн начинает приближаться к саду Эдема. Граница перехода задается следующей строкой INI файла (обычно это LifeEden.ini, другое имя INI файла может быть, если вы сменили имя EXE файла):
[Limits] MemoryBufferExponent=20
При этом цифра 20 означает, что до 2^20 = 1048576 родителей всегда будут располагаться в памяти компьютера, а при превышении этой цифры начнет использоваться дисковое пространство. Если учесть, что сведения о каждом родителе занимают 32 байта, то на диск будут сбрасываться массивы размером более 32 Мб, а меньшие будут располагаться в оперативной памяти. Но это же означает, что программе для работы необходимо около 100 Мб оперативной памяти (3*32=96 для массивов плюс немного для самой программы). Если изменить этот параметр на 24, то это увеличит границу до уровня 512 Мб. Такое допустимо только если вы имеете не менее 2 Гб памяти. Если указанное значение не превышает 9 или вообще не указано, или отсутствует INI файл с совпадающим с программой именем, то граница между массивом, расположенным в памяти и расположенным на диске будет 2^9=512 родителей или 16 кб, а если точнее, то размер буфера памяти будет выбран равным размеру дискового буфера. Кстати сам размер дискового буфера можно менять строкой (строка может отсутствовать, при этом по умолчанию будет выбрана цифра 9):
DiskBufferExponent=9
Но делать это не целесообразно, так как при меньших значениях снижается скорость работы с диском, а большие не обеспечиваются системой (программа просто перестанет работать). Есть еще параметр MemoryBuffer, позволяющий задать величину буфера под массив более тонко, чем MemoryBufferExponent. Если строка с этим параметром присутствует в INI файле, и указанное значение не ноль, то тогда MemoryBufferExponent не учитывается, а величина буфера берется из MemoryBuffer. При этом "MemoryBuffer=1048576" — это то же самое, что и "MemoryBufferExponent=20". Причем, для чисел, больших дискового буфера, будет произведено округление в меньшую сторону до величины, кратной дисковому буферу (то есть, кратной 512).
Применение ограничения на количество родителей вместе с правильным выбором величины буфера памяти на машинах, имеющих не менее 2 Гб ОЗУ, позволяет почти не обращаться к диску, а весь расчет производить в оперативной памяти.
Кроме того, в последней версии программы добавлен еще один параметр — процент ошибки. Это процент случаев, когда выбор состояния ячейки производится не в соответствии с рекомендацией компьютера, а вопреки ей. Этим я пытался сымитировать описанную выше ситуацию, когда при ошибочной работе программы выход маленьких паттернов увеличивался. Пока реальной пользы от этого параметра не замечено.
Вот такую эволюцию прошла программа поиска садов Эдема со времени нахождения Цветка Эдема. А что же с результатами?
15 октября найден сад Эдема, имеющий население 64 бита. Это на 5 бит меньше, чем у Цветка Эдема. И хотя этот сад крупнее (его размеры 11x12, а количество обязательных ячеек 113), по населению это рекордно малый сад Эдема.
x = 32, y = 11, rule = B3/S23 4bobo16b4o$oobob3obo10b10o$oboboobbobo9b11o$3boobb4o9b11o$obob3obo11b 11o$boboboobbobo8b12o$bb4obobboo8b12o$oobobbobobo9b11o$obobbob3o10b10o $oobbobobobo9b11o$oboobobobo10b4ob6o!
18 ноября представлен сад Эдема с тем же населением 64, но с габаритами 11x11. Этот образец только по количеству обязательных ячеек не дотягивает до Цветка Эдема — у него 119 ячеек должны быть определены, а у цветка Эдема 109.
x = 31, y = 11, rule = B3/S23 bobobb3o12b9o$bobobbobbo10b11o$ob3obb4o9b11o$3bobobobo10b11o$oobbob3o 11b11o$obobboobbo10b11o$5obboboo9b11o$b3obbobobo9b11o$oboobobobo10b11o $boobobboo11b11o$oboobbob3o9b11o!
Вместе с ним представлены 2 сада Эдема с населением 62 бита, но имеющие размеры 11x12.
x = 32, y = 31, rule = B3/S23 3bobobo15b7o$bobobbobbo11b10o$ob4obb3o9b11o$3boobb3o10b11o$oboboboobbo 9b12o$oobb3oboboo8b12o$obooboboboo9b12o$3obo3bo11b12o$bboobb4obo8b12o$ bobobobobbo9b12o$bbobobbo3bo9b11o10$6bobo14b6o$b3obobobo11b10o$oob3obb 3o9b11o$b4ob3obbo8b12o$bbobob3obo9b12o$boboboobbobo8b12o$obobobbobbo9b 11o$bobobbob3o9b11o$3obbobobo10b11o$bobbobb4o10b10o$obbobbo13b8o!
Но подходящие режимы работы программы поиска, наконец, определились, и в этот же день программа выдает 60-битный сад Эдема.
x = 32, y = 11, rule = B3/S23 bbobobobo13b5obo$bboobobobo10b10o$bbobob3oboo8b12o$bob3obobbo9b12o$o3b obobboo9b12o$b3obobboobo8b12o$obobobbobo10b12o$b3obbobobo9b12o$obobbob obobo8b12o$bobbo3bobo9b12o$obb4o13b9oboo!
24 ноября находится 59-битный сирота, вписывающийся в квадрат 11x11 (количество обязательных ячеек пока еще 113, что на 4 больше, чем у цветка Эдема):
x = 31, y = 11, rule = B3/S23 bboobo15b6o$boobobbobo11b10o$bboobbob3o10b10o$obbobobobo10b11o$oobbobo bobo9b11o$obobbobboo10b11o$obboobbobbo9b11o$b3oboobobo9b11o$boboobobb oo9b11o$obobbob3o10b11o$obboobbobo10b10o!
27 ноября я нахожу сад Эдема с габаритами 10x12. Этот ограничивающий прямоугольник содержит на 1 ячейку меньше, чем 11x11. Но по другим параметрам сад Эдема далек до существующих на этот момент рекордов — его население 64 живых ячейки, а количество обязательных ячеек 118. Надо сказать, что программа LifeEden не может найти такой сад в автоматическом режиме из-за спирального добавления ячеек. Этот сад переделан из найденного сада Эдема с габаритами 11x12. Все другие рекордные сады Эдема также подвергались ручной доработке в программе WLS — это позволяло иногда сократить один из размеров и почти всегда уменьшить количество живых ячеек. Работа с найденным образцом в программе WLS также необходима для определения того, какие из найденных ячеек являются обязательными.
x = 32, y = 10, rule = B3/S23 4oboobbobo8b10obo$boboboobobo9b12o$ob3obbobo10b12o$oobbobobbo10b12o$o bbobobb4o8b12o$obobobbo3bo8b12o$boobboobobo9b12o$oboboobboobo8b12o$obb obboboboo8b12o$booboob3obo9b11o!
В этот же день находится сад Эдема с 57 живыми ячейками. Размеры его 11x12, число обязательных ячеек 120.
x = 32, y = 11, rule = B3/S23 6bobobo15b5o$bobboobobbo10b11o$ob3obbobobo8b12o$bobboboboo10b12o$3bobo bobbo9b12o$obobobobbobo8b12o$boobbobbobo9b12o$boboobbobo10b12o$obbobbo boboo8b12o$boobboboo11b10o$ob3obobbo10b10o!
А через 2 дня удается найти 55-битный сад Эдема. Он также 11x12 и имеет 121 обязательную ячейку.
x = 32, y = 11, rule = B3/S23 bbobo3bo11b9o$bobobobobo10b11o$bboboboobbo9b12o$obbobobbobbo8b12o$oobb obobbo10b12o$obobbobobboo8b12o$obbobbobobbo8b12o$boobobbobobo9b11o$bb oobobbobo10b11o$3boobobbobo10b10o$bbobobboobo11b9o!
Ахим Фламменкамп отмечает, что последние находки имеют очень низкую плотность. Но плотность последнего сироты 55/121=0.4545 не является минимально возможной. На следующий день я привожу в качестве примера найденный несколькими днями раньше сад Эдема с плотностью 58/139=0.417.
x = 33, y = 12, rule = B3/S23 bbo6bo12b8o$bbobbobbobo11b10o$bbobboboobboo9b11o$4bobobbobo9b12o$bobob obbobo10b12o$obobobbobobbo7b13o$3bobboobbo9b13o$bo3bobbobbo8b13o$obobo bobboboo7b13o$bobobobbobobo8b12o$bbobobbobobo9b11o$bo3boobboo10b11o!
И новый рекорд. На этот раз 49 живых клеток при обязательных 110. До рекордных 109, достигнутых цветком Эдема, не хватает одной ячейки. Габариты 11x11, плотность 0.445. Этот паттерн подвергся существенной переработке и сильно отличается от найденного программой прототипа. После обычной оптимизации половинка образца, имеющая меньшее количество ячеек, была симметрично отражена, что и дало этот симметричный образец.
x = 31, y = 11, rule = B3/S23 bobbobbo13boob4o$obbobobbo11b9o$bbobobb3o10b10o$bobobbobobo9b11o$obobb obo12b11o$bobb3obbo10b11o$3bobobbobo9b11o$obobobbobo10b10o$b3obbobo11b 11o$obobbobobbo9b11o$bobobbobbo11b9o!
Месяц декабрь начался с нахождения 47-битного сироты. Это не принципиально новый сад Эдема, это предыдущий образец, подвергнутый еще некоторой переработке. В результате 2 живых ячейки удалось сократить, увеличив количество обязательных ячеек до 115. Полученная плотность 0.409 — меньше, чем у приводившегося ранее образца. Тип симметрии также сменился на центральную.
x = 31, y = 11, rule = B3/S23 bobbobbo13b9o$3bobobbobo10b10o$bbobobb3o10b11o$bobobbobobo9b11o$obobbo bo12b11o$bobb3obbo10b11o$3bobobbobo9b11o$obobobbobo10b11o$b3obbobo11b 11o$obobbobo12b10o$3bobbobbo11b9o!
И еще один сирота, полученный из того же сада Эдема ручной переработкой. Он имеет 51 живую ячейку, и в этом смысле он уже не рекордсмен. Но количество обязательных ячеек у него 107, что на 2 меньше, чем у цветка Эдема. Таким образом, все параметры цветка Эдема на 1 декабря уже улучшены, правда, рекордные значения параметров достигнуты разными образцами.
x = 31, y = 11, rule = B3/S23 boboobbo13b7o$obbobobbo11b9o$bbobobb3o10b10o$oobobbobobo9b11o$obobbobo 12b11o$bobb3obbo10b11o$3bobobbobo9b11o$obobobboboo9b11o$b3obbobo12b10o $bbobbobobbo11b9o$3bobboobo13b7o!
Еще один шаг на пути к заветной цели — минимальному саду Эдема сделан 21 декабря 2009 года. В этот день найден сирота со всего 45-ю живыми ячейками. Поскольку число обязательных ячеек у него 113, то плотность равна 0.398 — это меньше, чем у любого образца, найденного ранее.
x = 31, y = 11, rule = B3/S23 3boo3bo12b8o$bbobbobobo10b10o$bobobbo3bo9b11o$obobobbobo10b11o$obbobo bbo11b11o$bobb3obbo10b11o$bbobbobobbo9b11o$bobobbobobo9b11o$o3bobbobo 10b11o$bobobobbo12b10o$bbo3boo14b8o!
Но одновременно с этим паттерном был представлен сирота большего размера, имеющий еще меньшую плотность 50/129=0.388.
x = 32, y = 12, rule = B3/S23 bo18b4o$obbobbobbo10b10o$bo3bobbo11b10o$bbobobbob3o8b12o$obbobobbo11b 12o$boobobobbo10b12o$obobbobobbo9b12o$bobobbobobbo8b12o$4bobbobo10b12o $obobbobbobo9b12o$bobbobobbo10b11o$obboboobbo10b10o!
И, наконец, 30 декабря был найден сад Эдема, не претендующий на рекорды, но уникальный тем, что все его живые ячейки имеют менее 4 соседей. 12x12, 51/120.
x = 32, y = 12, rule = B3/S23 bboobobobbo11b9o$bobbo3boo11b9o$obobbobobbo9b11o$obbobbobo11b11o$bobbo bbobo10b11o$obobboo3bo9b12o$3bobobbobbo8b12o$obobobboboo9b12o$bobobbob obbo8b12o$bobbobbo12b9o$obobbobo12bob7o$6bobo16b4o!
Итак, на сегодняшнее число достигнуты следующие минимальные параметры для садов Эдема:
Сразу после нахождения Роджером Бэнксом первого сада Эдема, то есть в 1971 году Джон Конуэй предложил вниманию любителей Жизни 2 проблемы. За их решение Конуэй пообещал выплатить небольшую премию по 50 долларов за каждую, но задачки оказались достаточно трудными, и деньги пока никто не получил.
Первая проблема, так называемая проблема дедушки заключается в следующем. Надо найти конфигурацию, которая имела бы родителей, но не имела ни одного дедушки. Это означает, что все родители этой конфигурации должны быть садами Эдема. Решением этой пробемы будет считаться также строгое доказательчтво существования или не существования такой конфигурации в игре Жизнь. Как видим, даже нахождение садов Эдема, основу которого составляет нахождение родителей, то есть предков первого порядка, представляло собой почти до настоящего времени довольно трудоемкую вычислительную задачу. Что же говорить о нахождении предков второго порядка?
И тем не менее, некоторые соображения о том, как можно попытаться решить эту проблему, уже имеются. Например, при построении садов Эдема с помощью моей программы в ручном режиме можно заметить, что на последнем этапе построения недостроенный сад Эдема имеет очень мало родителей. Иногда попадается конфигурация, имеющая только одного родителя. Конечно, слова "только одного" относятся только к части плоскости, включающей все существенные клетки конфигурации и их соседей. Впервые конфигурацию, имеющую только одного родителя, обнаружил в 2004 году Ахим Фламменкамп, ее можно увидеть на его сайте. В настоящее время нахождение таких конфигураций не сложно.
А решение проблемы дедушки в данном случае сводится к проверке, является ли этот единственный родитель садом Эдема. Такую проверку можно осуществлять, добавив к моей программе поисковый алгоритм типа того, который применяется для поиска родителей в программе WLS. Тогда, если считать, что программа LifeEden при удачном выборе диапазона форы способна выдавать 30 садов Эдема в час, и пусть только 1 из этих 30 имеет на последнем этапе только одного родителя. Проверка этого родителя на сад Эдема сейчас занимает считанные секунды. Так что, в течение суток будет проверено 24 кандидата на роль сиротских детей. А если проверять конфигурации, имеющие не только одного родителя, а, все конфигурации за шаг до сада Эдема, причем проверку прекращать как только первый дедушка будет найден, то количество кандидатов можно значительно увеличить. Я уверен, что за приемлемое время такая программа могла бы найти решение проблемы дедушки.
Сейчас я пока не готов к этой работе, но принципиальных трудностей не вижу. Может быть, кто-нибудь из моих читателей сможет набраться решимости и доработать мою программу, чтобы закрыть эту затянувшуюся проблему.
Вторая проблема — так называемая проблема единственного родителя. Причем имеется в виду вовсе не тот единственный родитель, который фигурировал в обсуждении проблемы дедушки. Конуэй сформулировал эту проблему приблизительно так: существует ли конфигурация, имеющая единственного родителя, причем этот единственный родитель — сама конфигурация? То есть существует ли конфигурация-натюрморт, не имеющая иных родителей (опять же, в зоне ближайших соседей)? Причем в качестве решения лучше всего найти такую конфигурацию, либо доказать, что она невозможна. Более широко сформулированная аналогичная проблема: существует ли замкнутая цепочка конфигураций, каждая из которых имеет единственного родителя, входящего в эту цепочку? В такой форме это осциллятор или космический корабль, каждая фаза которого имеет единственного родителя.
Походы к решению этой проблемы еще более туманны. Хотя... Программа WLS способна находить огромное количество натюрмортов на достаточно большом пространстве. Она же способна искать родителей. Просто две эти задачи она решает в существенно разных режимах. Натюрморт и объекты других периодов ищутся в режиме, когда предком нулевого поколения является последнее поколение (для натюрморта — оно же). А при поиске родителей цепочка размыкается — предком первого поколения является нулевое, а предки нулевого поколения вообще не ищутся. Но ведь можно программу доработать так, чтобы она сперва находила натюрморт, а затем сдвигала его в первое поколение и, разорвав цепочку поколений, искала в нулевом поколении других родителей. Конечно, некоторые программистские ухищрения здесь понадобятся, но, опять же, принципиальных трудностей в организации такого поиска я не вижу.
Еще один трудный вопрос, связанный с садами Эдема, сформулирован Дейвом Грином. Каков наименьший размер прямоугольной плитки, которая при расширении на всю плоскость давала бы агар, являющийся садом Эдема? Ясно, что такой размер может быть меньше, чем размер конечного сада Эдема, и, возможно, такую плитку можно было бы найти методом полного машинного перебора (так называемый brute-force метод). Но дело в том, что обычное для Жизни сведение агара к тороидальной вселенной для садов Эдема не годится. Агар и замкнутая в тор плитка этого агара эквивалентны только при рассмотрении развития конфигурации в следующих поколениях, то есть только при взгляде в будущее. При взгляде в прошлое у агара могут быть родители с размерами элементарной плитки, большими, чем размеры плитки исходного агара, которые не могут быть учтены в тороидальной вселенной. Чтобы их учесть, пришлось бы рассматривать все торы с кратными размерами вплоть до бесконечности. Так что этот вопрос тоже пока остается открытым.
Ну и основной вопрос, который пытались решить все исследователи садов Эдема — это каков наименьший размер сироты в Жизни? Достигнутый мной результат, скорее всего, можно улучшить. Я почти уверен, что существуют 10x11 сироты, и весьма вероятно их существование даже в квадрате 10x10. Насчет меньших размеров у меня такой уверенности нет. Я думаю, что в квадрате 8x8 скорее всего нет сирот. Эти цифры ни в коем случае не претендуют на какое-либо доказательство, это просто интуиция человека, довольно тесно поработавшего с садами Эдема.
В этом повествовании уже были лирические или философские отступления. Позволю себе еще одно. На этот раз мне хочется сравнить сады Эдема в Жизни с некоторыми ситуациями в шахматах. Конечно, шахматы — это не далеко не игра Жизнь. Но что-то общее найти все-таки можно. И там, и тут мы имеем дело с клетчатым полем. В шахматах поле ограничено размерами шахматной доски. Каждая клетка этого поля может находиться либо в мертвом состоянии (то есть быть пустой), либо в одном из 12 живых состояний (то есть, на ней может стоять одна из 12 возможных фигур). Шахматная доска с расставленными на ней фигурами образует конфигурацию (в шахматах это называется позицией). Причем в характеристики позиции входит не только расположение фигур, но и некоторый внешний признака, который в шахматных диаграммах не отображается, а указывается отдельно в виде фразы "ход белых" или "белые начинают..." — очередность хода.
Шахматные правила, как и в Жизни, задают правильность или неправильность перехода от данной позиции к следующей. Но, в отличие от Жизни, в шахматах в общем случае существует не одна, а несколько позиций, которые могут получиться из данной. То есть, шахматы — это игра с многозначным будущим. И прошлое, то есть предшествующее данной позиции состояние, тоже многозначно. Но многозначность прошлого еще не дает нам основания применить к шахматам теорему о садах Эдема — этому мешает многозначность будущего.
Тем не менее, в шахматах существуют позиции, которые в клеточных автоматах назывались бы садами Эдема. Это, например, позиции, в которых белая пешка стоит на первой горизонтали. Или такие, в которых при ходе черных белый король находится под шахом. Или при ходе белых белому королю угрожают сразу 3 фигуры черных. Знатоки шахматной игры могут возразить: какие же это сады Эдема, это просто глупые, невозможные в шахматной игре расстановки фигур. Но ведь с точки зрения игры Жизнь сады Эдема тоже выглядят невозможными — их нельзя получить из других конфигураций. А менее глупыми они кажутся только потому, что в игре Жизнь не существует какой-либо начальной конфигурации — развитие можно начать с любой конфигурации, и это будет по правилам. В шахматах же игра всегда начинается с одного и того же расположения фигур (и с хода белых) — это одно из правил шахмат.
Но в шахматах существуют также позиции, которые имеют родителей, но, тем не менее, не могут быть получены из начальной конфигурации. Пример (тоже очень примитивный) — это когда на доске присутствуют более 9 ферзей одного цвета. Или (еще глупее) отсутствует один из королей. Однако, могут быть очень правдоподобные, но все равно невозможные в обычной игре позиции — иногда они встречаются в шахматных задачах. Существует даже целый раздел в шахматной теории, называемый ретроспективным анализом, который помогает выяснять, возможна данная позиция или нет.
Такие невозможные позиции не являются садами Эдема, но чем-то на них похожи. А еще больше эти позиции напоминают те, о которых идет речь в нерешенных проблемах Конуэя. Отличие в том, что в шахматах давно известно существование таких позиций, а в игре Жизнь никто не знает существуют ли конфигурации без дедушек, натюрморты-артефакты, осцилляторы-артефакты и т.д. А в общем случае — существуют ли классы конфигураций, не совпадающие со всем множеством конфигураций, такие, что не все конфигурации, входящие в эти классы, являются садами Эдема, но все их предки относятся к тому же классу. Как видим, в такой формулировке, обе проблемы Конуэя оказываются объединенными в одну. И, надо думать, рещение этой пробемы стоит вдвое дороже :)
Эта последняя часть моей рассылки будет интересна только тем, кто хотел бы попробовать сам поработать с садами Эдема.
Прежде всего, нужна программа, способная проверить, является ли данная конфигурация садом Эдема. В принципе, любая поисковая программа, использующая алгоритм lifesrc, способна это сделать, ведь поиск родителей является частью этого алгоритма. Во всех версиях программы WLS есть специальная опция "Find parents only" или "Только искать предков", позволяющая разомкнуть цепочку поколений и ограничиться поиском предков конфигурации, заданной в ненулевом поколении. Если для конфигурации, заданной в первом поколении, мы не можем найти ни одного родителя, то мы имеем дело с садом Эдема.
Правда, для этого надо еще правильно ограничить область поиска. Проверка конфигурации на принадлежность к садам Эдема производится следующим образом. Размеры поля устанавливаются приблизительно на 10 больше, чем размеры исследуемой конфигурации. Период устанавливается равным 2 (он такой и по умолчанию). Движком в левом нижнем углу выбирается поколение 1.
По центру поля вводятся живые и мертвые точки конфигурации. Напоминаю, что живые ячейки устанавливаются левой кнопкой мыши, а мертвые — правой. Можно также использовать клавиши s и a клавиатуры — они ставят живую или мертвую ячейку в позицию, на которую указывает курсор. Клавиша c очищает ячейку, а клавиша x делает ее неопределенной. Клавиши клавиатуры работают только в английской раскладке клавиатуры. После того, как все значимые ячейки сироты введены, можно приступить к вводу неопределенных ячеек (клавишей x, "мышиного" эквивалента нет). В первом поколении надо сделать неопределенными все свободные ячейки поля, а в нулевом только те, которые не заняты в первом и не являются их соседями. Поскольку из нулевого поколения занятые ячейки первого "просвечивают", удобнее сперва ввести неопределенные ячейки нулевого поколения, а потом уже делать это в первом поколении. А если нажимать не просто x, а shift+x (или, что то же самое, заглавную X), то неопределенные ячейки будут ставиться сразу в обоих поколениях, что может значительно ускорить процедуру ввода без переключений в нулевое поколение и обратно. Еще больше можно ускорить ввод, выделяя мышкой прямоугольные области и ставя x или X в одну из ячеек области.
После этого заходим в Options->Search settings (Опции->Настройка поиска) и ставим галочку Find parents only (Только искать предков). Кроме того, для сокращения времени поиска важно выбрать порядок поиска. Лучше всего, если поиск будет начинаться от середины паттерна. Поэтому ставим галочки "Sort to try middle columns first" и "Sort to find wide objects". В русской редакции программы WLS им соответствуют "Начинать со средних столбцов" и "Стараться искать широкие объекты". Но в русском варианте можно еще попробовать добавить "Диагональный порядок поиска" (в английской версии диагональный порядок от середины не работает). А лучше всего вместо двух или трех галочек поставить всего одну "Начинать с центральных клеток" (в английском варианте WLS такой опции нет, но она есть в программе JLS, впрочем, этой программой я не пользовался) — опыт показывает, что именно такой порядок поиска для садов Эдема наиболее эффективен.
Конфигурация введена, необходимые опции установлены. Нажимаем ctrl+g, и программа начинает поиск. Если в результате вы получили "Поиск завершен: найдено 0 объектов"(Search completed: 0 objects found), то это значит, что родителей не обнаружено, то есть мы ввели конфигурацию-сироту. А если программа остановилась с сообщением: "Найден объект 1" (Object 1 found), то в нулевом поколении можно посмотреть на найденного родителя нашей конфигурации (которая, конечно же, не сад Эдема) и даже сохранить его в буфер обмена (ctrl+c) с последующим пересохранением в файл, например, через Life32. Если хотите, можно продолжить поиск, нажав на пробел, и найти других родителей, а при достаточном терпении даже определить их число. А можно просто прекратить поиск, нажав ctrl+r.
После этого можно подкорректировать конфигурацию в поколении 1 и снова попытаться проверить наличие родителей. Иногда, имея достаточно близкую к саду Эдема исходную конфигурацию, серией проверок и корректировок можно выйти на сад Эдема, но в общем случае нахождение сада Эдема с помощью программы WLS, несмотря на почти мгновенную проверку каждой конфигурации, может потребовать от вас неприемлемо большого времени.
Скачать программу WLS с английским интерфейсом вы можете здесь, а русскоязычный вариант — здесь. Ява-версия поисковой программы, имеющая название JLS.
Теперь немного о программе поиска садов Эдема LifeEden. Описание работы программы было дано выше. Здесь я расскажу о функциональном назначении элементов ее интерфейса, тем более, что для интерфейса использовался английский язык, как язык, употребляемый большинством потенциальных пользователей программы. Кнопка Clear очищает поле программы. Ячейки первого поколения паттерна вводятся при помощи правой и левой кнопок мыши точно так же, как и в программе WLS. Но, в отличие от WLS, ввод с помощью клавиатуры не предусмотрен. Неопределенное состояние автоматически присваивается всем ячейкам, которые не были заданы как живые или мертвые. Они имеют серый цвет, причем соседние определенным ячейки имеют более светлый оттенок — именно в пределах более светлой области и производится подсчет числа родителей. Живые ячейки рисуются зеленым цветом, а мертвые — белым.
Программа после каждого изменения на поле выводит следующие параметры: число живых ячеек (ON), число мертвых ячеек (OFF), число определенных ячеек (ON+OFF), число ячеек родителя (Gen 0), количество родителей (Parents count), количество родителей на предыдущем шаге расчета (Old value).
Возможна корректировка только одной последней введенной ячейки. Для облегчения оценки необходимости такой корректировки служит цветной квадрат Recomended, который показывает какой цвет ячейки рекомендует программа с учетом параметров поиска, введенных пользователем. Такая рекомендация поступает только после того, как ячейка установлена, и количество родителей на данном этапе подсчитано. Если рекомендуемый цвет не совпадает с цветом, установленным пользователем, пользователь может изменить этот цвет. Можно также поставить галочку AutoCorrect, и тогда цвет будет меняться на рекомендуемый автоматически.
Основной изменяемый параметр, влияющий на рекомендацию компьютера — это фора (OFF odds). Смысл этого параметра разъяснялся выше. Фора измеряется в процентах и может задаваться либо в виде одного числа, либо в виде диапазона. Для задания форы в виде диапазона необходимо поставить галочку RandCorrect. Случайный выбор форы в указанном диапазоне дает большое разнообразие получаемых программой садов Эдема.
Ручное заполнение поля с помощью щелчков мыши позволяет произвольно менять порядок заполнения поля и за счет этого также получать отличающиеся один от другого результаты. Однако возможно и автоматическое заполнение поля путем нажатия на кнопку Start. При автоматическом заполнении порядок заполнения один и тот же — ячейки устанавливаются по спирали против часовой стрелки вокруг центральной клетки. Преимуществом автоматического заполнения является более высокая скорость заполнения. После автоматического заполнения найденный паттерн записывается в лог-файл. При ручном заполнении запись в лог-файл не производится, так как неизвестен порядок заполнения. Если вы при этом обнаружили интересный результат, то его сохранение возможно только "срисовыванием", например, в программу Life32.
Установка RandomCorrect без установленной галочки AutoCorrect приведет к чисто случайному заполнению паттерна, причем верхний предел форы будет задавать плотность получаемого образца, а нижний — не будет учитываться. Процент выхода садов Эдема при этом будет очень низким, но определить его для разных плотностей было бы интересно. Я намечал провести такую работу, но не нашел для этого достаточно времени, так что все ограничилось одним-двумя пробными запусками.
Параметр "Blunder %" задает процент случаев, когда при автоматической корректировке цвета ячейки компьютер поступает вопреки собственным рекомендациям. Некоторые такие промахи могут быть безобидными, другие же могут серьезно изменить рисунок получаемого паттерна, и, возможно, иногда привести к саду Эдема, имеющему какие-либо преимущества перед полученными "по-правилам" образцами. Я не достаточно много рабтал с этим параметром, чтобы делать выводы о его фактической действенности.
Если вы установите галочку AutoRestart, то программа, запущенная кнопкой Start, после нахождения и сохранения каждого паттерна будет повторять поиск в автоматическом режиме, пока эта галочка не будет снята. Такой режим поиска позволяет заставить программу длительное время искать сады Эдема с указанными параметрами, а потом ознакомиться с результатами, сохраненными в лог-файле.
Установка ненулевых значений параметров, указанных под словом Limits (пределы), приведет к тому, что программа будет отсеивать неудачные паттерны еще до окончания их полной прорисовки. Критерием отсева служат минимальные значения числа родителей на каждом этапе поиска, полученные при нахождении предыдущих садов Эдема. При этом самый первый паттерн всегда ищется до нахождения сада Эдема или до заполнения квадрата 14x14, а поиск последующих может прекращаться в зависимости от данных, полученных для предыдущих найденных садов Эдема. То есть, программа является самообучающейся. При отсеве учитываются параметры Factor и AddMember. Минимальное значение количеств родителей для данного этапа поиска, полученное для предыдущих найденных паттернов, умножается на Factor (коэффициент), и к нему прибавляется AddMember (добавочный член). Если число родителей на данном этапе не превышает полученный результат, поиск продолжается. В противном случае поиск прерывается, и программа начинает новый поиск с нуля.
Если Factor=0, то число родителей на всех этапах ограничено постоянным числом AddMember. В этом случае достаточно эффективны его значения в пределах от 6000000 до 10000000. Меньшие значения приводят к тому, что программа почти ничего не находит, а большие — к уменьшению скорости поиска за счет пропускания явно бесперспективных слишком больших паттернов.
Задание ненулевого Factor позволяет уменьшить AddMember. При этом в начале и в конце поиска, когда число родителей мало, будет работать AddMember, а в середине — будет производиться учет предыдущих результатов с коэффициентом Factor. Опыт показал, что значения Factor, близкие к единице, являются слишком жестким ограничением. Вероятно, это происходит из-за того, что для разных паттернов минимальные значения родителей достигаются на разных этапах. Неплохие результаты получаются при задании Factor в пределах от 2 до 10.
Не забудьте также, что большое значение имеет настройка программы под конфигурацию компьютера (количество оперативной памяти) с помощью параметра MemoryBufferExponent, задаваемом в ини-файле. Об этом подробно говорилось ранее.
Полученные в автоматическом режиме поиска данные, записанные в лог-файл, можно просмотреть и сохранить в общепринятом LIF формате с помощью программы Log2Lif.exe. Программа очень простая. Кнопка Open Log открывает лог-файл для просмотра. Паттерн, соответствующий строке лог-файла, в которой находится курсор, отображается вверху правой панели. Под ним отображаются главные его параметры — размеры, количество обязательных ячеек (Cells count), количество живых ячеек (ON count). Кнопка Save LIF служит для сохранения выбранного паттерна. Кнопка Close закрывает программу.
Последняя версия архива с программами LifeEden и Log2Lif лежит здесь, а исходники здесь. Если кто-то захочет разобраться в них, прошу не удивляться совершенно разным стилям программирования в разных частях программы — это следствие того, что эти части писались в разные годы, в течение которых мой стиль существенно менялся.
Николай Белюченко.
| к содержанию |