| к содержанию |
Примечание: Иллюстрации в этом и других выпусках данной рассылки представлены в формате RLE. Для их просмотра вам понадобится программа просмотра паттернов Жизни. Я рекомендую программу Life32. Чтобы просмотреть диаграмму, скопируйте ее в буфер обмена и вставьте прямо на поле программы.
В первом выпуске нашей рассылки мы рассматривали программы-просмотрщики, необходимые для чтения материалов этой рассылки. Однако, если вы всерьез заинтересовались Игрой Жизнь, то, думаю, скоро вам будет недостаточно только читать о Жизни и просматривать достижения других. Вам захочется найти что-нибудь свое, возможно новое, такое, которого еще никто не видал.
Несмотря на то, что уже скоро 40 лет энтузиасты постоянно что-то находят в Жизни, не стоит думать, что там уже все открыто и найдено. Опыт показывает, что Игра Жизнь еще очень далека от исчерпания. В ней можно найти сложные вещи, не найденные или не построенные до сих пор в силу своей сложности или недостаточной мощности компьютеров, но время от времени находятся удивительно простые объекты и реакции, никем до сих пор не замеченные, хотя, казалось бы, ничто не мешало обнаружить их 3 года назад или 10 лет назад, или даже 30 лет назад.
Что же нужно, чтобы эффективно работать в Жизни? Прежде всего нужны удобные программы-редакторы. Это те же самые просмотрщики, которые я вам рекомендовал в первом выпуске, то есть Life32, Golly и MCell. Повторю, что мне наиболее удобной из них кажется Life32. Конечно, здесь есть элемент субъективности, но на мой взгляд у этих трех программ и разные области применения. Для большинства паттернов в обычной Жизни (имеется в виду Конуэевский клеточный автомат с правилами B3/S23) предпочтительна именно Life32 с ее очень удобными механизмами редактирования паттернов. Для исследования регулярно растущих образцов с очень большими временами развития, конечно, лучше пользоваться Golly. А если вы интересуетесь больше альтернативными правилами, особенно автоматами с несколькими живыми состояниями, то вам больше подходит MCell.
Как проводится поиск новых паттернов с помощью этих программ? Прежде всего, поиск должен быть осмысленным и систематическим. Если вы будете просто рисовать случайные рисунки на поле, а затем наблюдать их развитие, вряд ли вы найдете что-нибудь новое. Скорее всего результатом развития всех ваших паттернов окажется несколько десятков самых часто наблюдаемых объектов начиная с блоков и мигалок и кончая, возможно, скрепками и пульсарами.
Вы должны научиться узнавать в лицо (то есть по процессу развития) такие развивающиеся объекты, как B-гептамино (Гершел), Пи-гептамино, ЛОМ, r-пентамино, столетие. Представляют интерес именно реакции этих объектов с простыми натюрмортами, глайдерами а также друг с другом. Учитывая достаточно длительное время развития этих объектов, всевозможных столкновений между ними может быть очень большое количество. Поэтому хорошо заранее составить план действий, чтобы не пропустить какой-нибудь интересный вариант.
Предположим, мы исследуем реакции Пи с глайдером (я проделывал такую работу, вы можете выбрать для исследования другие столкновения). Нам надо расположить исходный глайдер во всех позициях, двигаясь из которых он столкнется с развивающимся Пи. При этом глайдер может двигаться как навстречу Пи, так и догонять его. Следует также учесть 4 возможные начальные фазы глайдера. Каждый из этих случаев запускается на выполнение и просматривается. Большинство реакций приводит к "мусору" на поле, который никак нельзя использовать. Но некоторые реакции дают интересные результаты. Такие реакции желательно сохранять, чтобы в дальнейшем их можно было как-то использовать. Поскольку интересных реакций набираются сотни, то в именах файлов надо как-то отображать результат реакции, чтобы при дальнейшей обработке не рыться в сотнях файлов, когда потребуется найти то, что вам нужно.
Какие же результаты считать интересными при столкновениях Пи с глайдерами? Прежде всего это реакции, производящие новое Пи. Если мы имеем новое Пи, то на него мы можем направить новый глайдер, что в конечном счете может дать устойчивое движение Пи, поддерживаемое потоком глайдеров. Особенно интересны "чистые" случаи, когда образуется только Пи и больше ничего (или других продуктов сравнительно мало). В чистых или почти чистых случаях интересны повороты Пи, повторение которых может дать новый осциллятор (при этом, если имеется немного других продуктов, то возможно их удастся уничтожить какими-нибудь пожирателями).
Еще интересно образование новых глайдеров, особенно если глайдеров несколько, или вместе с глайдерами образуется какой-нибудь простой объект типа блока или мигалки. При этом имеется в виду, что два глайдера или комбинации глайдер плюс блок или глайдер плюс мигалка могут дать новое Пи. Конечно, чтобы получить новое Пи в этом случае, надо еще умудриться направить глайдеры в нужное место, но это уже следующий этап.
Самый интересный результат — это тот редкий случай, когда результатом реакции являются глайдер плюс Пи. В этом случае есть все, чтобы повторить реакцию, получив осциллятор или агар.
#C p300 agar x = 822, y = 787, rule = S23/B3 147b3o381b3o$149bo383bo$148bo383bo35$75bo191bo191bo191bo$75bobo189bobo 189bobo189bobo$75boo18bobo169boo18bobo169boo18bobo169boo18bobo$95bobo 189bobo189bobo189bobo$95bobo189bobo189bobo189bobo$96bo191bo191bo191bo 18$96boo190boo190boo190boo$96bobo189bobo189bobo189bobo$96bo191bo191bo 191bo50$o191bo191bo191bo191bo$obo189bobo189bobo189bobo189bobo$oo190boo 190boo190boo190boo18$192bo191bo191bo191bo$191bobo189bobo189bobo189bobo $191bobo189bobo189bobo189bobo$171boo18bobo169boo18bobo169boo18bobo169b oo18bobo$171bobo189bobo189bobo189bobo$171bo191bo191bo191bo35$244bo191b o191bo191bo$245bo191bo191bo191bo$243b3o189b3o189b3o189b3o22$147b3o189b 3o189b3o189b3o$149bo191bo191bo191bo$148bo191bo191bo191bo35$75bo191bo 191bo191bo$75bobo189bobo189bobo189bobo$75boo18bobo169boo18bobo169boo 18bobo169boo18bobo$95bobo189bobo189bobo189bobo$95bobo189bobo189bobo 189bobo$96bo191bo191bo191bo18$96boo190boo190boo190boo$96bobo189bobo 189bobo189bobo$96bo191bo191bo191bo50$o191bo191bo191bo191bo$obo189bobo 189bobo189bobo189bobo$oo190boo190boo190boo190boo18$192bo191bo191bo191b o$191bobo189bobo189bobo189bobo$191bobo189bobo189bobo189bobo$171boo18bo bo169boo18bobo169boo18bobo169boo18bobo$171bobo189bobo189bobo189bobo$ 171bo191bo191bo191bo35$244bo191bo191bo191bo$245bo191bo191bo191bo$243b 3o189b3o189b3o189b3o22$147b3o189b3o189b3o189b3o$149bo191bo191bo191bo$ 148bo191bo191bo191bo35$75bo191bo191bo191bo$75bobo189bobo189bobo189bobo $75boo18bobo169boo18bobo169boo18bobo169boo18bobo$95bobo189bobo189bobo 189bobo$95bobo189bobo189bobo189bobo$96bo191bo191bo191bo18$96boo190boo 190boo190boo$96bobo189bobo189bobo189bobo$96bo191bo191bo191bo50$o191bo 191bo191bo191bo$obo189bobo189bobo189bobo189bobo$oo190boo190boo190boo 190boo18$192bo191bo191bo191bo$191bobo189bobo189bobo189bobo$191bobo189b obo189bobo189bobo$171boo18bobo169boo18bobo169boo18bobo169boo18bobo$ 171bobo189bobo189bobo189bobo$171bo191bo191bo191bo35$244bo191bo191bo 191bo$245bo191bo191bo191bo$243b3o189b3o189b3o189b3o22$147b3o189b3o189b 3o189b3o$149bo191bo191bo191bo$148bo191bo191bo191bo35$75bo191bo191bo 191bo$75bobo189bobo189bobo189bobo$75boo18bobo169boo18bobo169boo18bobo 169boo18bobo$95bobo189bobo189bobo189bobo$95bobo189bobo189bobo189bobo$ 96bo191bo191bo191bo18$96boo190boo190boo190boo$96bobo189bobo189bobo189b obo$96bo191bo191bo191bo50$o191bo191bo191bo191bo$obo189bobo189bobo189bo bo189bobo$oo190boo190boo190boo190boo18$192bo191bo191bo191bo$191bobo 189bobo189bobo189bobo$191bobo189bobo189bobo189bobo$171boo18bobo169boo 18bobo169boo18bobo169boo18bobo$171bobo189bobo189bobo189bobo$171bo191bo 191bo191bo35$244bo191bo191bo191bo$245bo191bo191bo191bo$243b3o189b3o 189b3o189b3o22$147b3o189b3o189b3o189b3o$149bo191bo191bo191bo$148bo191b o191bo191bo!
Еще интересно, если в результате реакции образуются другие простые развивающиеся объекты из вышеперечисленных, причем опять же желателен чистый вариант. Правда в этих случаях повторить так просто реакцию не удастся, но в любом случае эти реакции стоят того, чтобы их сохранить. Может в дальнейшем, исследуя ЛОМ, столетие или B-гептамино, вам удастся найти обратную реакцию, в которой производится Пи — и объединение этих двух реакций позволит построить новый осциллятор, горящий фитиль или еще что-нибудь.
Какие еще случаи достойны запоминания? Это получение редких натюрмортов или осцилляторов. Если вы получили скрепку или лодку с хвостом, вполне вероятно, что найденный вами синтез еще не известен (фактически это синтез из трех глайдеров, так как Пи есть результат столкновения двух глайдеров). Сюда же можно отнести и образование ортогональных стандартных космических кораблей.
А если ничего ожидаемого вроде не получилось, но реакция все никак не закончится, то не спешите прерывать процесс. Возможно, вы натолкнулись на нового долгожителя. Неплохо, если развитие продолжается более 5000 поколений, совсем хорошо, но очень мало вероятно, если время жизни окажется более 10000 поколений, а известных долгожителей, живущих дольше 20000 поколений, можно пересчитать по пальцам.
Конечно, описываемая работа очень трудоемка. Но тем меньше вероятность того, что ее проделал кто-то другой. И удовольствие, полученное от построенных в результате паттернов, с лихвой компенсирует все затраты.
Допустим, вы нашли очень интересную реакцию, но чистые реакции редки, и в вашей реакции наряду с нужными объектами образуется дополнительный мусор. Если бы этого мусора не было, то все было бы чудесно... В этом случае имеет смысл попытаться приручить непокорную реакцию, то есть найти подходящий пожиратель или источник искр, которые уничтожили бы мусор и обеспечили бы условия для повторения реакции. О применении пожирателей я подробно рассказывал во втором выпуске рассылки. Поэтому приведу пример с источниками искр, очищающими реакцию.
#C p126 forced oscillator x = 89, y = 102, rule = S23/B3 86bobo$86boo$87bo18$43boo$42bobo$42bo$40boob4o$36boobobobobbo$36boobob oo4boo$39bobob4obbo$39boboobobboobo$40bo4bo4bo$41b3o3b3o$43bobobo$44b 3o9bo$54boo$31boo22boo$30bobbo$29bobobo$29boboboo$27boobo4bo$27bobbobo boo39boo$24boobobboo3bo13b3o23boo$24bobboobobboo14bobo$25boobbobobo15b obo21b4o$27b5obo38bo4bo$27bo4bo38bob5o$28b4o39bobbo3boo$70boobob3obbo$ 28boo43boboboboo$28boo37boobboobobbo$72boboboo$70boobobo$71bobobo$71bo bbo$59bo12boo$59bo$$57bo3bo$55b3obob3o$54bo3boo4bo$54boboobboobobo$55b obboobboobo$56boobbooboboboo$58bobboboboboo$58b4oboo$62bo$60bobo$60boo 3$32b3o$34bo$33bo29$boo$obo$bbo!
Если вкратце, то сам процесс приручения напоминает процесс исследования реакций. Поколение за поколением развивающийся объект просматривается, и в каждом поколении во все влияющие точки подставляется пожиратель или искра. Если результат приводит к успеху, то проверяется полное развитие образца с тем или иным источником подобных искр. При этом возможно разрушение источника искр в предыдущих или последующих поколениях.
Сюда же можно отнести и технологию очистки выхлопа паровозов с помощью кораблей-источников искр или кораблей, восстанавливающих кромку. Эта технология широко применяется для построения граблей. Есть вероятность построить грабли меньшего размера или других периодов на основе тех же паровозов, но поскольку этим занимались настоящие специалисты своего дела, то эта вероятность низка.
Но довольно часто (по крайней мере мне) бывает нужен паровоз определенного периода, производящий какие-нибудь простые объекты (допустим, блоки). Систематических коллекций таких паровозов нет, есть только коллекции граблей. Конечно, можно взять два экземпляра граблей и синтезировать из испускаемых ими глайдеров блоки. Но обычно всегда можно обойтись одним экземпляром, ведь человек, приручавший грабли, наверняка наталкивался на варианты, когда паровоз производил блоки, но они ему были не нужны. Логика здесь такая: грабли — более ценная вещь: они производят глайдеры, а из глайдеров можно произвести почти все что угодно. А блоки, мигалки и прочие объекты из хорошо дымяшего паровоза получить намного проще, поэтому ценность их меньше. Я же ломаю его грабли, убирая искрящие корабли, и начинаю приручение по-новой. Почти наверняка путем переделки граблей можно найти паровозы блоков, мигалок, ульев, караваев, лодок, прудов или бадей, поскольку перечисленные объекты рождаются более часто, чем глайдеры.
Вот пример растущего космического корабля, состоящего из двух c/2 p20 паровозов, производящих блоки, и найденного мной 10c/23 горящего фитиля, сжигающего эти блоки. Для сравнения справа показаны p20 грабли, которые были переделаны в паровозы путем убирания последнего ЛКК и приручения выхлопа с помощью ТКК.
#C 2c/4 + 10c/23 growing spaceship x = 82, y = 42, rule = S23/B3 bbo13bo7bo13bo24bo13bo$b3o11b3o5b3o11b3o22b3o11b3o$boboo4bo5boboo3boob o5bo4boobo22boboo4bo5boboo$bb3o3b3o5b3o3b3o5b3o3b3o24b3o3b3o5b3o$bboo 3boobbo4boo5boo4bobboo3boo24boo3boobbo4boo$7booboo17booboo34booboo$7bo bb3o15b3obbo34bobb3o$8boboo17boobo36boboo$10bo19bo40bo$b3obbo3bo19bo3b obb3o22b3obbo3bo$obbo3bobo21bobo3bobbo20bobbo3bobo$3bo4bo23bo4bo26bo4b o$3bo33bo26bo$obo35bobo20bobo3$17bo5bo$16b3o3b3o$11boobboobo3boboobboo 42boo5bo$15b3o5b3o52b3o$15b3o5b3o52boboo$16boo5boo54b3o$73boo4boo$73b 3o$10bobo4bo5bo4bobo40bobbo$11boo3b3o3b3o3boo42boo$15boo7boo$17bo5bo$$ 16bobbobobbo$15bobbo3bobbo$12boo4bo3bo4boo$$11bo4bo7bo4bo$14boo9boo$ 11boo15boo49bo$80bo$16boo5boo53b3o$16boo5boo$14b3o7b3o$13bobo9bobo$13b obo9bobo!
Еще одна разновидность создания новых объектов Жизни с помощью программ-редакторов — это так называемое конструирование сложных объектов. Это сборка более крупных объектов из мелких известных частей.
На первый взгляд, конструирование представляет собой менее творческую работу, чем другие ранее упомянутые здесь. Самые интересные конструкции, это конструкции, реализующие новые идеи. Так безусловно интересно было создавать первый генератор простых чисел в пространстве Жизни или первое ружье, стреляющее паровозами. Но и повторения известных идей, улучшающие первоначальные конструкции (например, уменьшающие их размеры) или придающие им новые качества — тоже весьма благодарное занятие.
Так, например, появление паровозных двигателей новых периодов, как правило, влечет за собой сперва приручение грязных паровозов с целью получения глайдерных граблей всех возможных кратных периодов, а затем конструирование из них граблей, производящих стандартные космические корабли. При этом используются стандартные давно известные реакции глайдерного синтеза. И тем не менее в силу важности этих конструкций эта работа не считается тривиальной, ведь получаются грабли неизвестных до этого периодов.
Вот пример, когда найденный Девидом Беллом новый p27 грязный паровоз был им приручен до получения p27 глайдерных граблей и паровоза блока, а затем из двух экземпляров граблей и одного паровоза были сконструированы ЛКК грабли, стреляющие в сторону.
#C A period 27 c/3 sideways LWSS rake. #C This uses two period 27 backward rakes and a period 27 block puffer. x = 84, y = 128 42b3o17b3o$37booboobo19bobooboo$37boo4boboo13boobo4boo$36bobbo3bobobo 11bobobo3bobbo$43boboboboo5boobobobo$41bo3boboboo5boobobo3bo$42bobobob 3o5b3obobobo$$46b3o9b3o$46b3obobobobob3o$47b5obob5o$52bobo$52b3o$49bob o3bobo$$47boob3ob3oboo$47bo11bo$46bobbo7bobbo$46bo4bo3bo4bo$51bo3bo$ 45b6o5b6o$44boo15boo$36bo16bo$34b4o13booboo$33boo3bo13bobo$32bo5b3o12b o11bo$35bobo4boo20b4o$32bob4o4boo15bo3bo3booboo$31b8ob4o9bo4b4o5bobboo $31boo20bo3bo3bo7bobbo$36bo5boo9bo4bobobbo$35bobo3bobbo17bo$38bobobbo$ 36b4o$36b4o8bo$9bo19bo8bobbo4bo$7b4o17b4o12boo3bo3bobo$3b3obo3bo15bo3b ob3o8bo4bo3bobbo$bbo3bobboboo13boobobbo3bo7bobboo5boo$3boo3booboboo9b ooboboo3boo9bobo$8bobboboboo5boobobobbo$8boobobo3bo3bo3boboboo$11b4obo 5bob4o$11boo13boo25b3o17b3o$12boboo7boobo14boo5booboobo19bobooboo$16bo b3obo18boo5boo4boboo13boobo4boo$12bo3bo5bo3bo20bobbo3bobobo11bobobo3bo bbo$14b3o5b3o29boboboboo5boobobobo$17booboo30bo3boboboo5boobobo3bo$18b 3o32bobobob3o5b3obobobo$14boobbobobboo$13boobbo3bobboo31b3o9b3o$12boob 3o3b3oboo30b3obobobobob3o$12boo11boo14boo15b5obob5o$16bo5bo18boo20bobo $11bobboobo3boboobbo35b3o$10b7o5b7o31bobo3bobo$10boob3o3bo3b3oboo3boo$ 18bobo11booboo21boob3ob3oboo$18bobo10boboboo21bo11bo$19bo10b3obboo20bo bbo7bobbo$7boo17b3obobob3o20bo4bo3bo4bo$4booboo16bo11boobboo19bo3bo$b 4obboo4boo4bo6bobobbo9boo13b6o5b6o$o4bo4booboo3b3o14bobbo11bo4boo15boo $boo7boo3bo10boo5bo14b4o12bo$10boo6bobo4bobbo3boo13boo3bo9booboo$18b3o 8bo16bo5b3o8bobo$29bo3bo15bobo4boo6bo11bo$29bo3bo12bob4o4boo17b4o$30b oo13b8ob4o12bo3bo3booboo$41boobboo17bo4b4o5bobboo$27bo13boo7bo5boo6bo 3bo3bo7bobbo$23bo4bo20bobo3bobbo5bo4bobobbo$21bobobb3o23bobobbo15bo$ 21bo28b4o$50b4o$52bobbobboo$57bo$56bo3bo3bobo$41boo17bo3bobbo$41boo16b o5boo$56bobo6$33bo$34boo5boo$33boo6boo$51bo$50bo$50b3o5$41boo$41boo8$ 43b4o$42bo3bo$46bo$42bobbo6$58boo$56booboo$56b4o$57boo5$69bobbo$73bo$ 69bo3bo$70b4o!
Иногда между выдвижением идеи новой конструкции и ее реализацией проходит значительное время в силу того, что не все детали будущей конструкции еще известны. Так например идею Гусеницы (космического корабля на базе Пи-гептамино, ползущих по трекам из мигалок) Девид Белл выдвинул в сентябре 2002 года, а построена она была Габриэлем Нивашем в конце декабря 2004 года.
Основные этапы появления новой конструкции обычно включают: появление идеи, подбор частей будущей конструкции, конструирование макета, оптимизация конструкции. Ясно, что конструирование требует высокой квалификации конструктора. Так уже подбор частей невозможен без знания достижений других исследователей, ведь желательно выбрать самые маленькие из известных варианты. Если вам нужны отражатели, вы должны уметь выбирать из них те, которые обеспечат требуемый сдвиг фаз. При создании макета надо уметь синхронизировать между собой разные части конструкции. Оптимизация представляет собой сжатие конструкции до минимально возможных размеров. При этом отдельные части не только придвигаются друг к другу, но и меняют фазы. А иногда статоры сдвигаемых осцилляторов приходится сваривать между собой, что требует применения поисковых программ.
Вот пример, когда для поддержания развития Пи вместо четырех ружей был специально сконструирован трек Гершела, стреляющий глайдерами с четырех сторон. Это было сделано с помощью программы hersrch, о которой я расскажу ниже.
#C p292 oscillator x = 248, y = 248, rule = S23/B3 50bo157boo$38bo11b3o17boo6boo12bo115boo$36b3o14bo16boo4bobbo12b3o$20bo 14bo16boo22booboboo12bo99boo$20b3o12boo42bobobo10boo29boo69bo$23bo52b oobo3bo41boo5boo62bobo$22boo43boo7boobbobboo47boo63boo$66bo12boo8bo 114b3o$70bo17b3o113boobbo$23boo42bo3bo17bobo38boo60boo9bobboobo$23boo 5b3o9boo24bobboo13bo4boo37boo52bo7boo8bobo3boo$30bobo9boo24b5o17boo44b oo46b3o16bo3boo$28bo3bo36bo3bo14b3o29boo14boo49bo19boo$28boboobbo35b3o 15boo30boo64boo18b3o$28bo3bo38bo5boo9bo30bobbo83boobboo$30boo48bo35bo bboboo55boo30boo$36bo38boo4boo32bobbo60bo24boo4bo$30bo5bobboo33boo6bo 33bobo60bobo22bo5boo7boo$30bo4bo3bo20boo11b3obboobbo82boo13boo22boob3o 10bo$33b3o5bo19bo16boobo83boo39bo3bo9bobo$21boo17boo16b3o154b3o3bobo 19boo$21boo13boo20bo163bo3boo15bo$36bo122boo3b3o59boo13bobo$25bobo9b3o 37boo39booboo36boo3bo72boobboo$20bo4boo12bo38bo30boo6bobobobo40boobo5b oo62boo$19bobo4bo48b3o25boo5bo6bobobbo43boo8bo$20bo54bo27bobob3o6boobo 51boo4boo31bo3boo$17b3o76boo7bobo7bo3boo49boo6bo30b3obboo$17bo78boo7b oo9bobobbobo11boo32b3obboobbo29bo3bo$115booboobboo11boo21boobboo10boob o29bobboo$158booboo29boo8boo4b3o$162boo28boobboo5bo$26boo135b3o12bo3b oo12bobob3o$26boo136boo11bobo3bo14bobo$143boo20bo11boo3bo15boo4boo$ 143bo37bo21bobo4boo31boo$35boo92boo10bobo20boo11b5obo19bo6boo13boo16bo bo$35boo91bobo10boo21boo11bo4boo18boo20bobo18bo$oo115boo11bo47b3o43bo 20boo$oo115boo61boboo39boo4boo9bo$181bobo43bobbo9bo$121boo104boo7bo$ 34boo85boo6bo107bo$34bo91bobobo105bobo$30boo3b3o88boobo$30bobo4bo81boo 57boo$32bo87bo57bobo$32boo83b3o60bo54boo$19bo14bo82bo62boo$5boo10boobo 11b3o83boo5b3o$6bo24bo87bo4booboo117boo$3b3o10bo14boo86bobobboobobo 116bo$3bo13bob3o98boo3bo3bo110bo3bobo$14bo3bo3bo102bobbo108bo6boo$9boo 3bo4bo3bo6boo94b3o108bobbo$9boo3bobo3bobo7boo138boo64b3o$16b3obbo117bo 30boo64b3o$14bobbo119b3o21boo73bobbo$16bo119bo24bobbo61boo9bobo$136boo 19boo4boo62bo9b3o$12boo126boo16bo20boo46bobo$11bobo127bo16bobo18bo48b oo$11bo127bo19boo16bobo$10boo127boo36boo$32boobbooboo$32bobobbobo123b oo$17boo16boo3bo7bo114boo$18bo17boboo6b3o11bo101bobbo$15b3o15bobbobo6b o14b3o96bobboboo$15bo16bobobobo6boo16bo14bo63boo14bobbo$33booboo24boo 12b3o44boo17boo15bobo83boo$75bo47boo120boo$51bo4bobo16boo$47bo4boo4bo 170boo$46boo4b3ob3o63boo47boo56boo$45boo6boo19boo47bo47boobboo44boo$ 46bo27boo44b3o12boo38bobo44bo18booboo$47bo7boo63bo14bo41bo44bobo16boob o$53b4o79b3o38boo44boo21bo$53b3o82bo101bob5o$240boo$18boo223boo$18boo 224bo$24boo32boo181b3o$24boo33bo181bo$57bo$57boo178boo$22boo37boo174b oo$22boo5boo31bo$29boo28b3o$59bo$$245boo$245bo$235bo7bobo$230boobbobbo 5boo$219boo9boo3boo$219boo$$223b3o9bob4o$222bo12bo4bo$223boo15bo$222b oo13bobo$34bo186boo15bo$34b3o49bobo35bo97bo$37bo49boo34bo95b3o$36boo 22boo7boo16bo35b3o93bo$60bobbo156boo$56boo4boo4boboboo147bo$57bo10bob oo6boo141bobo$11boo44bobo9b3o6bo143boo$11boo19bo25boo16bobo$30b4o42boo $29boo3boo$5boo25bo3bo$5boo25bo3bo181bobo$9boo21bobboo181boobo$9boo19b o3bo80b3o81boo7boo11b3o$26bo87bo3bo79bobo7boo8boo4bo$24boo88booboo77b 3obobo15bob5o$25boo143boo23bo5boo17bo$4boo165bo23boo22bo3boo$4boo165bo bo44bo3bobo$70boo100boobboo40boo3bo$24bo3boo40boobboo100boo$23bobo3bo 44bobo165boo$23boo3bo22boo23bo165boo$27bo17boo5bo23boo143boo$23b5obo 15bobob3o170boo$23bo4boo8boo7bobo171bo$24b3o11boo7boo164bo3bo19boo$26b oboo181boobbo21boo$27bobo181bo3bo25boo$211bo3bo25boo$212boo3boo$170boo 42b4o$169bobo16boo25bo19boo$24boo143bo6b3o9bobo44boo$24bobo141boo6boob o10bo$26bo147boobobo4boo4boo$26boo156bobbo$28bo131bo16boo7boo22boo$26b 3o130boo49bo$25bo133bobo49b3o$9bo15boo186bo$8bobo13boo$7bo15boo$7bo4bo 12bo$7b4obo9b3o$$27boo$11boo3boo9boo$3boo5bobbobboo$bbobo7bo$bbo$boo$$ 188bo$186b3o28boo$185bo31boo5boo$9boo174boo37boo$9boo178boo$190bo$6bo 181bo33boo$4b3o181boo32boo$3bo224boo$3boo223boo$6boo$b5obo101bo82b3o$b o21boo44boo38b3o79b4o$3boboo16bobo44bo41bo14bo63boo7bo$bbooboo18bo44bo bo38boo12b3o44boo27bo$25boo44boobboo47bo47boo19boo6boo$17boo56boo47boo 63b3ob3o4boo$17boo170bo4boo4bo$171boo16bobo4bo$boo120boo47bo$boo83bobo 15boo17boo44b3o12boo24booboo$86bobbo14boo63bo14bo16boo6bobobobo16bo$ 82boobobbo96b3o14bo6bobobbo15b3o$82bobbo101bo11b3o6boobo17bo$83boo114b o7bo3boo16boo$83boo123bobobbobo$207booboobboo$69boo36boo127boo$68bobo 16boo19bo127bo$18boo48bo18bobo16bo127bobo$18bobo46boo20bo16boo126boo$ 8b3o9bo62boo4boo19boo$8bobo9boo61bobbo24bo119bo$8bobbo73boo21b3o119bo bbo$9b3o64boo30bo117bobb3o$9b3o64boo138boo7bobo3bobo3boo$7bobbo108b3o 94boo6bo3bo4bo3boo$bboo6bo108bobbo102bo3bo3bo$bobo3bo110bo3bo3boo98b3o bo13bo$bo116boboboobbobo86boo14bo10b3o$oo117booboo4bo87bo24bo$120b3o5b oo83b3o11boboo10boo$66boo62bo82bo14bo$11boo54bo60b3o83boo$67bobo57bo 87bo$68boo57boo81bo4bobo$118boboo88b3o3boo$9bobo105bobobo91bo$10bo107b o6boo85boo$11bo7boo104boo$7bo9bobbo43bobo$7bo9boo4boo39boobo61boo115b oo$boo20bo43b3o47bo11boo115boo$bbo18bobo20boo18boo4bo11boo21boo10bobo 91boo$bbobo16boo13boo6bo19bob5o11boo20bobo10boo92boo$3boo31boo4bobo21b o37bo$42boo4boo15bo3boo11bo20boo$47bobo14bo3bobo11boo136boo$45b3obobo 12boo3bo12b3o135boo$44bo5boobboo28boo$37b3o4boo8boo29booboo$36boobbo 29boboo10boobboo21boo11boobbooboo$35bo3bo29bobboobb3o32boo11bobobbobo 9boo7boo78bo$32boobb3o30bo6boo49boo3bo7bobo7boo76b3o$32boo3bo31boo4boo 51boboo6b3obobo27bo54bo$71bo8boo43bobbobo6bo5boo25b3o48bo4bobo$9boo62b oo5boboo40bobobobo6boo30bo38bo12boo4bo$5boobboo72bo3boo36booboo39boo 37b3o9bobo$4bobo13boo59b3o3boo122bo$4bo15boo3bo163bo20boo13boo$3boo19b obo3b3o154b3o16boo17boo$25bobo9bo3bo39boo83boboo16bo19bo5b3o$27bo10b3o boo22boo13boo82bobboobb3o11boo20bo3bo4bo$27boo7boo5bo22bobo60bobo33bo 6boo33boobbo5bo$37bo4boo24bo60bobbo32boo4boo38bo$36boo30boo55boobobbo 35bo48boo$36boobboo83bobbo30bo9boo5bo38bo3bo$39b3o18boo64boo30boo15b3o 35bobboobo$39boo19bo49boo14boo29b3o14bo3bo36bo3bo$39boo3bo16b3o46boo 44boo17b5o24boo9bobo$38boo3bobo8boo7bo52boo37boo4bo13boobbo24boo9b3o5b oo$38boboobbo9boo60boo38bobo17bo3bo42boo$39bobboo113b3o17bo$41b3o114bo 8boo12bo$49boo63boo47boobbobboo7boo43boo$49bobo62boo5boo41bo3boboo52bo $51bo69boo29boo10bobobo42boo12b3o$51boo99bo12booboboo22boo16bo14bo$ 153b3o12bobbo4boo16bo14b3o$38boo115bo12boo6boo17b3o11bo$38boo157bo!
Другой способ нахождения новых объектов Жизни — это применение специальных программ, позволяющих подключить к этому делу всю мощь современной вычислительной техники.
Самый простой способ поиска это так называемый brute-force способ, при котором перебираются все возможные варианты заполнения какого-либо участка вселенной Жизни, причем каждый раз конфигурация запускается на выполнение и фиксируется "интересный" результат. Казалось бы, компьютер может перебрать очень большое число вариантов, ведь ячейка может находиться только в двух возможных состояниях — живом и мертвом. Если мы ограничим поиск квадратом 5х5, то число возможных вариантов равно 2^25 или 33,5 миллиона. Это в самом деле не проблема для современных компьютеров. Но уже для квадрата 6х6 это число превращается в 69 миллиардов, что уже требует значительного времени поиска. Но ведь объект размером 6х6 это еще очень маленький объект. А например регион 10х10 уже невозможно обыскать ни за какое разумное время ни современными компьютерами, ни теми, которые появятся через 100 лет — такое это огромное число 2^100 или 10^30.
Поэтому поисковые программы, реализующие этот способ поиска, вы в интернете вряд ли найдете. Если для каких-то своих задач программисты и пишут их (ведь алгоритм здесь очень простой), не имеет особого смысла доводить до "товарного" вида и предлагать другим столь мало эффективный инструмент.
Наиболее известен алгоритм поиска по дереву, реализованный в таких программах, как lifesrc Девида Белла и WinLifeSearch Джейсона Саммерса и Карела Сухайды. В этом алгоритме число проверяемых ячеек умножается на число поколений, интересующих исследователя. То есть поиск производится сразу во всех поколениях. Кажется, что это должно еще более увеличить число рассматриваемых вариантов. Но дело в том, что все поисковое пространство представляется в виде двоичного дерева, причем дерево составляется так, чтобы влияющие друг на друга ячейки располагались по-возможности в соседних узлах дерева. При этом противоречащие правилам или условиям поиска варианты отбрасываются вместе с ветвями дерева, вытекающими из этих вариантов. Это резко ограничивает количество остающихся вариантов и позволяет находить существенно более крупные объекты, чем brute-force алгоритм.
Программа lifesrc является консольной программой. Она распространяется в виде исходных текстов на языке C. Это позволяет откомпилировать ее для любой платформы и использовать на любом типе компьютера. Конечно, человек, желающий с ней работать должен иметь для этого соответствующую квалификацию.
Для пользователей Windows Джейсон Саммерс и Карел Сухайда создали визуальную оболочку для этой программы, что позволяет жизнелюбам не заморачиваться проблемами компиляции, а сразу пробовать искать. Полученная программа (WinLifeSearch) является очень мощным инструментом, имеющим множество настроек и возможностей. Я работаю с этой программой уже более 3 лет, но все еще не могу сказать, что испробовал все возможные варианты настроек поиска.
Конечно, законы больших чисел и здесь делают свое дело, что ограничивает размеры искомых паттернов. Здесь имеется очень сильная зависимость от периода — максимальный период найденных мной с помощью этой программы объектов равнялся 8. Для каждого данного периода существует предельная ширина поискового пространства, превышение которой грозит превратить поиск в многолетнюю занятость процессора без видимых результатов. А вот длина паттерна при разумной ширине практически неограниченна. Правда, в самой программе зашито ограничение в 132 ячейки, но это ограничение вызвано не процессом поиска, а только размерами массивов, располагаемых в оперативной памяти. Думаю, что сейчас это значение можно было бы смело увеличить в несколько раз, так как за последние годы размер оперативной памяти компьютеров значительно возрос.
Программа позволяет искать осцилляторы, космические корабли, некоторые бесконечные и горящие фитили, а также находить одно или несколько поколений предков для данного паттерна. Поскольку эффективность поиска в значительной степени зависит от порядка обхода ячеек (то есть от их расположения в дереве поиска), в программе много настроек, позволяющих изменять этот порядок. Хотя, на мой взгляд, можно было бы добавить к существующим настройкам еще некоторые. Программа может искать объекты не только в Конуэевской Жизни, но и в других жизнеподобных клеточных автоматах. Спектр пригодных для поиска клеточных автоматов ограничивается автоматами с соседством по Муру (то есть с 8 соседями), правила рождения/выживания которых можно записать формулой типа B/S, а также одномерными автоматами. Впрочем, при некоторой модификации исходников программы можно заставить ее работать и для некоторых других правил — такой опыт есть, например, у Артема Дергачева.
Достоинств у этой программы много, но к сожалению есть и несколько глюков, из которых самый плохой — это зависание программы после нескольких (порядка 10) запусков с редактированием начальных условий (особенно если изменяются размеры поля). Для малых периодов при отсутствии "защитных" строк из пустых клеток вверху и/или внизу поля программа может в качестве решения выдать неустойчивый паттерн (который устойчив только при индуктивной поддержке сверху и снизу). При поиске образцов-перевертышей (флипперов) программа неправильно отсеивает субпериоды.
Кроме того за время работы с WLS накопилась целая куча пожеланий по поводу возможных улучшений ее работы. К сожалению, авторы пока не собираются ее дорабатывать. Я несколько раз брался за ее исходники, но хронический недостаток времени не дает пока серьезно втянуться в процесс переделки программы.
Другая поисковая программа gfind создана Девидом Эппстейном. Эта программа не менее мощна, чем lifesrc, но процесс поиска базируется на других принципах. Я знаю, что в ее алгоритме используется работа с графами Де Брейна, но не вникал подробно, как это делается. Программа существует только в консольном варианте. Ее исходники на языке C можно найти в интернете. Благодаря другим принципам поиска программа может легко найти те образцы, которые трудны для lifesrc (впрочем, обратное тоже верно). В активе этой программы единственный известный корабль периода 7 — уикендер и ряд осцилляторов трудных периодов.
Еще одна программа afind создана Евгением Лангвагеном. Сам автор находил с ее помощью некоторые паттерны в альтернативных правилах и неоконченные, но достаточно большие фрагменты корабля-коня в Конуэевской Жизни. Я не знаю, чтобы кто-нибудь другой использовал эту программу для поиска. Алгоритм поиска, использованный в этой программе, основан на алгоритме программы gfind, но в него внесены некоторые изменения.
Кроме поисковых программ "широкого профиля" существует ряд более узко специализированных программ.
Одна из таких программ RandomAgar, предназначенная для поиска агаров, написана Габриэлем Нивашем. Программа заполняет поле поиска (прямоугольник) случайными комбинациями живых и мертвых ячеек и запускает их, при этом фиксируя удачные варианты. Программа способна распознавать повторяющиеся комбинации с учетом всех возможных типов отражения и сдвига.
Другая программа Габриэля Ниваша Catalist ищет катализаторы, то есть объекты, участвующие в реакции и выходящие из нее в неизменном виде. К подобным объектам относятся пожиратели. Но понятие пожирателя подразумевает некоторую универсальность. В отдельных же реакциях могут проявлять себя объекты, не являющиеся в широком смысле пожирателями, но в данной реакции ведущие себя как катализаторы.
Программа gencols Пола Каллахана позволяет автоматизировать исследование реакций. Она просматривает все возможные столкновения между двумя объектами Жизни и выдает наиболее интересные результаты.
Программа Glue (ссылки в настоящее время нет, хотя сама программа у меня есть) каталогизирует столкновения глайдеров с натюрмортами и простейшими осцилляторами. Ее удобно применять для нахождения реакций так называемого медленного глайдерного синтеза. Обычно синтез начинается с одинокого блока. В этот блок запускается глайдер, превращающий блок в другой объект или набор объектов. Затем эти объекты следующими глайдерами преобразуются в другие объекты и т.д. пока не будет получен синтезируемый паттерн. Программа Glue сохраняет результаты всех столкновений, запущенных в ней, и позволяет составлять из них цепочки и находить наиболее короткие пути синтеза. Программа написана Полом Чепменом.
Программа hersrch Карела Сухайды не является поисковой программой. Скорее, это программа автоматического конструирования. Кирпичиками для конструирования являются известные элементарные трубопроводы Гершела. Результаты — замкнутые петли необходимых периодов (практически готовые ружья) или треки, приводящие Гершел в указанную точку за указанное число поколений. С появлением этой программы были найдены улучшенные ружья для огромного числа периодов.
Если вы нашли что-то на ваш взгляд новое и невиданное, это еще не значит, что ваша находка действительно нова. За годы существования игры Жизнь ее энтузиасты обнаружили огромное количество объектов, обладающих самыми разнообразными свойствами. Конечно, упомнить все известные объекты нет никакой возможности, но самые важные из них можно найти во многих коллекциях, созданных жизнелюбами, или в общедоступных статьях и справочниках.
Прежде всего, вы должны разбираться в классификации объектов Жизни и уметь правильно классифицировать свою находку. Я, пожалуй, посвящу один из ближайших выпусков рассылки вопросам классификации, тем более, что заготовка статьи, посвященной этой теме, у меня уже есть. А пока я могу вам посоветовать пользоваться Словарем Жизни, составленным Стивеном Сильвером. Русский перевод Словаря вы можете найти на моем сайте. В словаре вы можете найти определения для всех типов объектов Жизни а также примеры наиболее характерных их представителей. Кроме того русский перевод Словаря может помочь начинающим жизнелюбам правильно понимать англоязычные статьи по этой теме, поскольку в нем отражены практически все применяющиеся в игре Жизнь термины.
Большое количество объектов, классифицированным по типам, периодам, скоростям и размерам, можно найти на сайте Генриха Кенига. Здесь же изложены основы глайдерного синтеза а также предложены основы классификации осцилляторных роторов.
Очень полезной может быть также страница сайта Джейсона Саммерса, посвященная современному статусу Жизни. На ней показано, объекты каких типов, скоростей, периодов найдены в настоящее время, а какие еще не известны. Для многих периодов и скоростей указан год создания первого объекта и исследователь, которому удалось это сделать.
На том же сайте вы можете найти одну из самых полных и самых современных коллекций объектов жизни jslife (часть 1, часть 2), составленную Джейсоном Саммерсом. Здесь же выложены также наиболее полные в настоящий момент коллекции осцилляторов all-osc, ружей (часть 1, часть 2) и коллекция фитилей wicks. Там же имеется ряд более узко специализированных коллекций.
Из более старых классических коллекций достойны упоминания следующие:
Если вас интересует глайдерный синтез, то загляните на сайт Марка Нимика. На нем вы можете найти все известные достаточно маленькие объекты, классифицированные по типам, периодам и числу живых ячеек. Для каждого из объектов здесь приведены все известные реакции, синтезирующие данный объект из сталкивающихся глайдеров.
Для интересующихся космическими кораблями и технологиями построения космических кораблей и паровозов новых периодов полезной может быть серия статей Девида Белла. Русский перевод этих статей также имеется на моем сайте. К сожалению, в статьях не отражены достижения последних лет — прежде всего технология ортогональной скорости c/5, разработанная Полом Туком, а также начала технологии диагональной скорости c/4, первые паровозы которой создавались Девидом Беллом и Джейсоном Саммерсом на базе кораблей, найденных Хармутом Хольцвартом и мной. Возможно, кое-что из этого я представлю вам в дальнейших выпусках этой рассылки.
Коллекции космических кораблей, паровозов и граблей можно найти на уже упоминавшемся сайте Джейсона Саммерса. О космических кораблях в иных правилах очень много информации на сайте Девида Эппстейна.
Я тоже создал пару коллекций. Одна из них представляет собой дальнейшее развитие собрания диагональных космических кораблей скорости c/4 Джейсона Саммерса. Мне пришлось ее сделать, поскольку я активно занимался поиском таких кораблей, причем нашел довольно большое количество новых кораблей. Чтобы не объявлять об открытии уже известных космических кораблей, пришлось постоянно обновлять справочник таких кораблей.
Вторая коллекция была создана в процессе работы над словарем Стивена Сильвера. В нее вошли объекты, имеющие собственные названия. Таких объектов довольно много и бывает трудно вспомнить правильное название известного объекта. Перерывать весь Словарь в поисках нужной статьи — довольно трудоемкая работа. Коллекция облегчает эту работу — достаточно заглянуть в файл, в котором содержатся все именованные объекты данного типа, найти нужный паттерн и в комментариях к файлу прочитать его название.
В каких областях нет достаточно удобных коллекций? Нельзя найти коллекции интересных реакций — вероятно потому, что это слишком необъятная тема.
Очень плохо с коллекциями глайдерных отражателей — то, что имеется в jslife слишком неполно, чтобы это можно было практически применять. У меня собрана намного более полная коллекция, но она пока годится только для собственных нужд. Чтобы ее выложить для общего пользования, ее надо значительно переработать.
Не имеется в настоящее время и коллекции известных агаров. Правда, о начале работы по созданию такой коллекции объявил Анджей Окрасинский. Подождем, может быть в скором времени он представит свою работу.
Кроме того известно, что Джейсон Саммерс работает над коллекцией горящих фитилей — пока что файл fuses.lif в коллекции wicks содержит слишком мало примеров, чтобы считать это полноценной коллекцией.
Николай Белюченко
| к содержанию |