| к содержанию |
Эта рассылка будет посвящена Игре Жизнь. Я не собираюсь систематически излагать основы игры — их вы можете почитать в литературе или в интернете. Посмотрите прежде всего мой сайт, а если вам это станет интересно, то на сайте достаточно ссылок на другие ресурсы. Для самого первого знакомства могу вам посоветовать статьи Гарднера, которые вы можете найти на моем сайте и скачать в виде файла формата chm.
Впрочем, некоторые выпуски рассылки будут посвящены давно известным вещам — это будет своеобразный ликбез для начинающих. В других выпусках, возможно, более сложных, я буду знакомить вас с последними находками в Жизни. И, наконец, некоторые выпуски будут представлять собой обзоры ваших писем — по мере их получения, и если в них будут затронуты интересные вопросы. Я постараюсь, чтобы рассылка выходила более-менее регулярно, но ничего гарантировать не могу. После выпуска очередного номера рассылки он будет помещаться на мой сайт. Таким образом, вы сможете найти архив рассылки на моем сайте.
Я предполагаю, что для многих из моих читателей поначалу будет непривычной терминология, применяемая в Жизни. Я постараюсь разъяснять многие термины, но многое вы сможете посмотреть и сами в Словаре Жизни, английская версия которого имеется на сайте Стивена Сильвера, а русская версия — на моем сайте. И ту, и другую версии вы можете скачать на свой компьютер и пользоваться ими в офф-лайне, когда вам будет необходимо.
Игра Жизнь это одна из самых известных математических игр, придуманная в 1970 году английским математиком Джоном Конуэем. При очень простых правилах она представляет собой почти неограниченный простор для исследования и нахождения все новых и новых конфигураций. Впрочем, первоначальный массовый энтузиазм после публикации первых статей Мартина Гарднера через несколько лет несколько утих, и верными Игре остались несколько десятков человек, в основном профессиональные математики или программисты.
Любителей игрушек хочу сразу предупредить: Игра Жизнь это не совсем игра. Здесь не с кем играть, т.е. нет игроков; кроме того здесь нельзя выиграть. Это ближе к пасьянсам или математическим головоломкам, но цели несколько другие. В пасьянсе цель сложить его и получить моральное удовлетворение. А какую цель преследуют жизнелюбы? Это зависит от квалификации любителя Жизни.
Начинающих, как правило, увлекает созерцание развития тех или иных конфигураций, неожиданные превращения узоров. Программисты, ознакомившись с правилами Жизни, сразу усекают, что такую штуку несложно написать самому, и пишут очередную программу Жизни. Ежегодно выходит несколько таких программ, но большинство их годится только для целей созерцания развития того, что либо нарисовал пользователь, либо по случайному закону разбросал по полю компьютер. Однако постепенно любитель Жизни понимает, что разглядывать узоры конечно приятно, но ведь хочется создать что-то такое, до чего другие не додумались. И что созданные им узоры в конце концов похожи друг на друга и вряд ли новы. А в коллекциях, которые собирают настоящие асы, таких случайных узоров вовсе нет — там объекты, обладающие удивительными свойствами — они либо колеблются с каким-то периодом, либо движутся, либо что-то испускают, либо растут по необычному закону. И что при случайном рисовании на поле такие объекты вряд ли получишь. А отсюда следует, что рисовать надо не случайно, а с умом. А для этого надо знать, что и зачем ты рисуешь, и что из созданного другими может помочь тебе, и какие приемы ты можешь применить в том или другом случае. И вот те, кто втягивается во все эти премудрости, и могут стать настоящими Жизнелюбами. То есть в Жизни ценится не только способность решать головоломки, но прежде всего способность придумывать новые, причем желательно, чтобы они были разрешимы имеющимися средствами.
Для просмотра примеров, которые будут приводиться в рассылке вам понадобятся программы-просмотрщики. Я предлагаю вам использовать одну из следующих трех программ.
Life32 — мощный и удобный редактор, который применяется большинством жизнелюбов, использующих Windows. Позволяет вводить паттерны вручную, из файлов всех более-менее распространенных форматов, из буфера обмена. Здесь вы можете выделить часть конфигурации, перенести или скопировать ее на другое место, повернуть или отразить. При запуске паттернов можно регулировать такие параметры, как увеличение и скорость показа. В широких пределах можно менять внешний вид вселенной Жизни. Можно также изменять правила игры и замыкать поле в цилиндр или тор. Программа снабжена Automation интерфейсом, что позволяет эффективно использовать ее при кропотливых систематических исследованиях. До недавнего времени это была самая быстрая из программ-редакторов. Размер ее поля более чем 1000000Х1000000 клеток. При всем этом программа не лишена некоторых недостатков. Например, залипание курсора на краю поля при скроллинге; переполнение буфера, в котором запоминаются ранее запущенные паттерны, и, как результат, забывание последних запускаемых примеров; не совсем правильный формат заголовка при сохранении в RLE файл, что затрудняет чтение этого файла другими программами; некорректная работа механизма запоминания запущенного паттерна при использовании HiperTreading; тормоза в тех редких случаях, когда живые ячейки расположены вблизи границы "бесконечность-минус бесконечность". Так много недостатков связаны прежде всего с тем, что эту программу я знаю намного лучше других и постоянно с ней работаю — а это уже говорит в ее пользу. Из этих недостатков самый большой пожалуй связан с невозможностью полноценного использования программы в HiperTreading режиме работы процессора. Лично я отключил этот режим в BIOS'е — и не только из-за Life32, но и из-за невозможности работы поисковых программ при полной загрузке процессора (т.е. максимум загрузки процессора поисковой программой составляет 50%, что фактически превращает 3000 МГц компьютер в два по 1500).
MCell — роскошная программа с красивым интерфейсом. Ее основное достоинство — возможность моделирования практически любого клеточного автомата. Если встроенных возможностей не хватает для создания клеточного автомата по вашим правилам, вы имеете возможность создать свою пользовательскую DLL, в которой будут реализованы ваши правила. С программой поставляется довольно большая библиотека паттернов не только из Жизни, но и из многих других автоматов. Программа заинтересует тех, кто любит красивые вещи, поскольку автоматы с несколькими живыми состояниями представлены в цвете, и развитие некоторых паттернов просто зачаровывает. В то же время, если вы интересуетесь только Жизнью, то эта программа во многом уступает Life32: она более медлительна, поле ее ограничено, а редактирование конфигураций не настолько удобно. Впрочем, это мои личные впечатления, а я сравнительно мало пользовался MCell.
Golly — новая программа. Только что вышел ее первый релиз, до этого выпускались пробные весии. Программа реализована сразу для нескольких платформ — кроме исходников имеются исполняемые файлы под Windows, Linux и MacOS. Пока заметных глюков у Golly нет, но и пользуются ей очень немногие. Основная изюминка этой программы — это использование алгоритма hashlife для расчета развития конфигураций. Этот алгоритм до сих пор был реализован только в программах командной строки. Суть его, если в кратце, заключается в том, что программа постоянно сохраняет в захешированном виде части уже рассчитанных конфигураций, и если подобные части появляются вновь, то она не тратит времени на расчет того, что уже рассчитано, а просто прогнозирует развитие этих частей. Например, нет нужды рассчитывать каждое поколение полета глайдера в пустоту — можно просто предсказать, в какой точке и какой фазе он будет через 1000 или через 1000000000 поколений. За счет хеширования программа способна показать развитие некоторых конфигураций в течение совершенно фантастических времен за вполне разумное время. Так за 20-30 минут можно увидеть, как будет изменяться паттерн в течение 10^50 поколений. Размеры Вселенной тоже практически неограниченны. Благодаря этому эта программа прежде всего необходима тем, кто интересуется долго живущими объектами. И эти люди с большим успехом уже начали ее применять: находки Ника Готтса и Дина Хикерсона последних месяцев во многом обязаны именно этой программе. Кроме того, в этой программе есть практически все, что есть в Life32 кроме, пожалуй, Automation. Но зато имеется возможность управлять программой с помощью скриптового языка Python — такая замена естественна для межплатформенной программы.
Все три описанные программы имеют англоязычный интерфейс, что может представлять некоторые трудности для людей, плохо знающих английский. К сожалению, я не знаю ни одной русскоязычной программы, которая могла бы называться полноценным редактором Жизни. Думаю, если среди участников рассылки окажутся люди, имеющие опыт русификации англоязычного софта, и если они заинтересуются этой проблемой, то создание русских версий было бы прекрасным подарком для остальных.
Для обмена результатами жизнелюбы создали несколько форматов описания конфигураций. Чаще всего встречаются следующие два.
Life 1.05 — назван по одной из первых программ-просмотрщиков под DOS. Первая строка всегда #Life 1.05. В строках #D записывается комментарий. В строке #R указываются правила. Если правила не указаны, то подразумевается Конуэевская Жизнь. Затем идет строка #N. Конфигурация ограничивается минимально возможным прямоугольником, и координаты его верхнего левого угла указываются в строке #P. Все остальное — это сам паттерн, строка за строкой, закодированный следующим образом: точкой (.) обозначается мертвая клетка, а звездочкой (*) или буквой o — живая. Есть некоторые приемы, сокращающие изображения. Так, если оставшаяся часть строки содержит только точки, то их можно не указывать. Другой прием заключается в том, что весь паттерн разбивается на несколько прямоугольников, и для каждого указываются сначала координаты верхнего левого угла, а затем дается изображение самого прямоугольника в виде точек и звездочек. Во многих случаях все вспомогательные строки опускаются, и дается только само изображение, состоящее из точек и звездочек. Так поступает например Стивен Сильвер в своем словаре (см. русский перевод). В этом формате паттерны очень наглядны, и можно составить о них некоторое впечатление даже не пользуясь никакими программами. Кроме того, их можно просто скопировать и вставить в любую из перечисленных мной программ, а также и в некоторые другие.
Вот например как выглядит найденный мной в 2004 году челнок периода 6 в этом формате:
O............. OOO........... ...O.......... ..OO.......... .............. ......O....... .....OOOO..... ......O..O.... .......OOO.... .............. ..........OO.. ..........O... ...........OOO .............O
RLE — более компактный текстовый формат, но совершенно не наглядный. Здесь мертвая клетка кодируется символом b, а живая символом o. Для перехода на следующую строку используется символ $, а для окончания записи паттерна символ !. Если более двух одинаковых клеток идут подряд, то они не выписываются все, а перед соответствующим символом ставится число повторений. Повторения ставятся также перед символом переноса строки $, если более одной строки оказываются пустыми. Закодированный в виде длинной строки символов паттерн разбивается на строки не длиннее, чем 80 символов, причем есть правило переноса, согласно которому число вместе со следующим за ним символом нельзя разбивать на части — каждая такая группа должна полностью перенестись на следующую строку, если она не помещается в предыдущей. Обязательной является также вводная строка (заголовок), в которой указываются размеры ограничивающего прямоугольника и, возможно, правила. Комментарии к паттерну записываются либо в начале до заголовка в строках, начинающихся с #C, либо в конце после знака ! (в этом случае комментарий больше никак не выделяется — все, что записано после восклицательного знака, считается комментарием). Этот формат также поддерживается всеми уважающими себя программами Жизни, и иллюстрации, записанные в этом формате также легко могут быть скопированы в буфер обмена и вставлены в программу-просмотрщик. Практически весь обмен примерами между любителями Жизни в настоящее время осуществляется в этом формате. Я буду пользоваться тоже почти исключительно им.
В качестве примера посмотрите, как выглядит тот же самый p6 челнок в формате RLE:
x = 14, y = 14, rule = S23/B3 o$3o$3bo$bboo$$6bo$5b4o$6bobbo$7b3o$$10boo$10bo$11b3o$13bo!
Для описания паттернов в Играх со многими состояниями используются другие форматы, в частности формат .mcl программы MCell, но в принципе он является модифицированным RLE.
Для чтения рассылки кроме знаний основ и терминологии и программы-просмотрщика больше ничего не нужно. Однако если вам захочется поискать чего-нибудь самому, то вам надо знать как минимум основы технологии такого поиска и научиться владеть некоторым инструментарием. Знакомству с технологией и инструментами я и посвящу один из следующих выпусков рассылки. Возможно, это будет второй выпуск, хотя более вероятно, что вторым будет выпуск, посвященный пожирателям — он уже наполовину написан.
Николай Белюченко.
| к содержанию |