Пользователь
0,0
рейтинг
8 июля 2009 в 10:01

Поиграем в жизнь

Представьте себе листок бумаги в клетку. Подозреваю, что уже на этом этапе некоторые хабралюди догадались, о чем пойдет речь. Что ж, моё почтение им. Остальные же продолжают представлять себе листок бумаги в клетку. Во всех подробностях. В мельчайших деталях.

А теперь представьте, что на этом простом листочке мы создадим простой, но оттого не менее впечатляющий симулятор жизни. Ни больше, ни меньше. Конечно, он будет очень упрощенный, но ведь чтобы понять что-то сложное надо начать с простого, не так ли? Этот симулятор можно применить ко множеству наук и с каждой из них он будет иметь множество достаточно интересных точек соприкосновения. От социологии до астрономии, от биологии до электротехники.

Ладно, хватит завлекалок. Пора удариться в математику.




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

Спустя 30 лет другой ученый по имени Джон Конвей (да, Джон — очень популярное имя) заинтересовался этой машиной и решил её упростить. Как это снова ни странно, но и ему это удалось. Талантливые ученые, что и говорить.

Правила


И так. Снова по-быстрому рисуем у себя в голове бумагу с клетками. Правила очень простые:
  • Каждая клетка может находиться в одном из двух состояний: живая (заполненная) или мёртвая (пустая).
  • Каждый ход у каждой клетки определяется ее состояние и состояние всех её 8-ми соседей.
  • Если это пустая клетка и соседей ровно 3, то эта клетка оживает. Во всех остальных случаях пустая клетка остается пустой.
  • Если же это живая клетка, то подсчитывается количество живых соседей.
  • Если соседей 0 или 1, то клетка умирает от одиночества.
  • Если соседей 2 или 3, то клетка продолжает жить.
  • Если соседей 4 или больше, то клетка умирает от перенаселения.

Простой пример эволюции пяти вариантов триплетов (фигур из трех клеток):

image


Ничего сложного, не так ли? По большому счету, от игрока зависит только начальное расположение живых клеток, после чего они будут жить самостоятельно, а создателю останется за ними только следить. Но тут-то и возникает та самая причина, по которой этой игрой интересуются уже почти 40 лет.

Просто представьте себе количество вариантов расстановки клеток на минимальном поле, пусть хотя бы 10*10 клеток. Это 2100. И каждый из этих вариантов будет развиваться. Какой-то — всего несколько десятков ходов, а какой-то может зациклиться. Что уж тогда говорить о больших полях типа 100*100 или тем более о замкнутых по принципу тора.

image


Фигуры


В ходе полевых испытаний этой игры, сначала на бумаге, а затем и с помощью компьютерного моделирования было выявлено множество фигур, которые по их поведению можно рассортировать по нескольким классам.

  • Устойчивые фигуры: фигуры, которые остаются неизменными
  • Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений
  • Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением
  • Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура
  • Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур
  • Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами

Самым простым примером двигающейся фигуры является Глайдер (планер):

image


Неинтересно?
Тогда взгляните на ружьё:

image


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

Интерес для науки


Прежде чем я дам вам возможность самим попробовать составлять фигуры, позвольте сказать пару слов о пользе всей этой фигни для науки.

Вообще, если говорить научными терминами, то эта игра является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей, а короче говоря — клеточным автоматом. То есть решетка, в которой каждая ячейка имеет конечное число состояний, а само это состояние определяется через жестко заданные правила перехода.

Данная игра являет собой едва ли не простейший клеточный автомат. А представьте себе, что каждая клетка имеет не два, а с десяток разных состояний, и их изменения зависят не только от соседних 8-ми клеток, но и от 16-ти на «втором периметре».

Такие клеточные автоматы — это один из самых простых примеров того, что иногда называют «самоорганизованные системы». Эта предметная область привлекла внимание ученых и математиков из различных областей. В ней изучается построение сложных структур и форм поведения на основе очень простых правил. Например, появление лепестков роз или полос на зебре из растущих рядом клеток. Поэтому изучение конечных автоматов может привести к совершенно неожиданным результатам в абсолютно разных науках. Так, например, эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик. Равно как они во многом совпадают с законами поведения популяций примитивных организмов.

Практика


Ну а теперь настало время самим попробовать это в деле.
  • Здесь можно и нужно почитать про «жизнь» подробнее. Тут описано множество фигур и принципов. Да и вообще много полезного.
  • Здесь можно поиграть в «жизнь» на флэше. Настроек никаких нет. Всё упрощено до минимума. Чисто для ознакомления.
  • Здесь же можно скачать программу-эмулятор с расширенными возможностями. Регулировка скорости времени. Возможность сохранения и загрузки начальных конфигураций. Изменяемый масштаб поля. В общем, полная свобода действий. Для хардкорщиков. К сожалению, только под Windows.
  • Ну а здесь лежит подобный эмулятор для всех платформ (Windows (2000+), Mac OS X (10.3.9+) and Linux (GTK+)). Его я сам не запускал, но судя по описанию, возможностей у него не меньше, чем у предыдущей программы.
Вперед на испытания. И да пребудет с вами random ))
Алексей Хляпов @falldown
карма
54,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (109)

  • +2
    Пошел играться.

    Кстати, любые выпуклые многоугольники и кружочки, как я понимаю, живут вечно?
    А вот скажем заполненный квадрат (3*3 и больше) сразу «выгорает», кроме угловых точек — которые, впрочем, потом тоже умирают от одиночества.

    Спасибо за статью, очень интересно!
  • +22
    И чо, кто-то не знает о таких боянах?
    • +9
      Ну, судя по предыдущему комментарию — кто-то не знает. Да и на хабре я статьи об этом не нашел.
      • 0
        Плохо искали, точно была статья, девушка писала про написание игры для Android и в качестве примера как раз была игра «жизнь».
    • +11
      Выросло новое поколение, более привычное к другим игрушкам. Помню как мы с братом Лайф без компа гоняли взяв в качестве доски кучу шашек и клетчатое одеяло.
      • 0
        А правила и условия победы? С учетом некомпьтерности?
        • +1
          Да нет, не против друг-друга, а совместно, чтоб побыстрее обновлять доску. 8-)

          Компьютера у нас тогда еще не было.
        • +1
          Помню, на компьютере играл в игрушку, напомниающую классическую Жизнь
          Есть поле в клеточку, у каждого игрока свой цвет, есть какие-то начальные зарисованные клетки. А потом по очереди делается ход игроком и происходит «ход» жизни клеток. При этом учитываются все возможных цвета клеток. Условия выживания можно придумать :) Ну и цель, остаться в живых, победив противников.
          • 0
            Filler?
      • +9
        Думаю, что до написания своего варианта эмулятора Life, рано или поздно доходят многие программисты.
        Сам через это прошёл лет 10 назад. Сначала был классический Life с двумя состояниями клеток, затем классический замкнутый, а потом, начитавшись Паутины, захотелось полноцвета… Вот тут и ушло в трубу ...-надцать недель)))
      • 0
        А я на нокии 3660 игрался в эту игру.
        • 0
          Там же экран маленький.
          • 0
            Я уже размеры не помню, но точки там были очень маленькие!
  • +3
    Кстати, глайдер является эмблемой хакеров.
    Подробности тут http://catb.org/hacker-emblem/
  • 0
    где то читал что по этой игре даже чемпионаты мира проводят, русские пару лет назад первое место взяли, источник не могу найти
    • 0
      Хм, интересно, какие там условия? Создать самую долгоживующую динамическую модель?
      • +3
        X
        X
        X
        • 0
          Под динамической я имел в виду не циклическую, а постоянно развивающуюся.
          • 0
            Х Х
            Х Х
            Х

            ?
            • 0
              блин, пробелы съело

                 Х Х
              Х Х 
                 Х 
              
      • 0
        Я когда-то читал, что соревнуются в скорости обработки. В былые времена на 32х битных процессорах был рекорд, кажется, 4.5 клетки за такт процессора за счет обработки элементов группами. На 16ти битных — меньше.
    • +2
      Не слышал про чемпионаты. Есть интернациональное сообщество математиков, которые занимаются изучением Жизни, в нем участвует несколько русских. Но они занимаются поиском новых форм и конструированием сложных клеточных автоматов, вроде элементарного компьютера на «языке» жизни. Не знаю, насколько там все продвинулось, но элементы памяти и некоторые другие механизмы уже пару лет назад были разработаны.
      Глайдер в таких машинах является битом. Или электроном. Вообще глайдер самая быстро движущаяся структура. Сейчас точно не помню, но кажется скорость движения глайдера условно считается скоростью света, как самой большой достижимой скоростью.
      • 0
        Если быть точнее, то скорось глайдера равна 0.5 максимальной скорости перемещения (1 клетка за 1 ход).
        • 0
          А если еще точнее, то с/4 :)
        • 0
          Ну не суть важно, я уже не помню терминологии. Можно было бы взять c=1 клетка\ход, а можно и c=0,5 клетка\ход (все равно быстрее ничего нет). Нет смысла брать за скорость света ту скорость с которой ни один объект не способен двигаться.

          Кстати, вот что гугл мне сказал по секрету: «Весьма примечательно, что сам Конвэй формально назвал скорость глайдера скоростью света»
          • 0
            Хотя у гугла много мнений, а правильного я уже и не помню.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +3
      • НЛО прилетело и опубликовало эту надпись здесь
  • –7
    Увидел картинку с ружьем, — подумал, что на упячку попал =\
    • 0
      А что там с ружьем?
  • +2
    В подобные игры люди играют уже тысячи лет: ru.wikipedia.org/wiki/%D0%93%D0%BE
  • 0
    кстати хорошее задание для студентов — ключевой момент такую ( лабу а может курсовую ) будет интересно выполнять, и приятно потом поглядеть =)
    • +1
      у нас на матфаке на 1 курсе такая лаба
    • 0
      да, у нас была в универе задача — реализовать эту игру с использованием java.util.concurrent. каждая клетка работала в своем потоке, а мы изучали барьеры для потоков и прочие интересные штуки.
  • 0
    Может это надо было в «антиквариат»? :)
    Интересно, сколько человек, из тут присутствующих, собственноручно писали Life?
    • 0
      Ну вот, блин. Думал что-то новое рассказал или хотя бы хорошо забытое старое, а оказалось мало того, что старое, так еще и отлично сохранившееся в памяти )))
      Остается загадкой, почему на хабре про это до сих пор не написали? Всё-таки это же не столь очевидные вещи, как, скажем, таблица умножения…
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Мда. Так вот пишешь и не знаешь, известная это тема или нет. Прошлый пост писал об indie-играх, которые у меня на компе уж три года валяются. Тоже та еще древность. Ан нет — оказалась очень популярная тема. А тут вот не угадал, видимо.
          • 0
            Сравнили игры 3хлетней давности и 30тилетней :)
        • 0
          Ну хоть кто-то не знает. Статья интересная, и я кое-что новое узнал.
        • 0
          Мне вот только интересно, почему «жизнь» называется игра? Тут процесс наблюдения сплошной. Примерно как костёр игрой называть.
          • 0
            Потому что изначально предлагалось фишки на доске двигать. Ну не работой же это называть?
            Это игра — типа игры в куклы, а не соревнования.
    • 0
      Писал лет 20 назад на «Специалисте», это был такой компьютер на 580-ом процессоре. Писал даже не на ассемблере а машинными кодами.
      • 0
        а я в 1990-м для IBM XT писал, на Паскале…
    • +1
      я писал :)
    • +1
      скорее всего большинство. и на всех языках и платформах. например, не так давно здесь проскакивала статья описывающая создание Жизни для Android'a
  • +1
    Ага. Я диплом когда-то бакалаврский писал по этой игре. С распределенными вычислениями больших полей на кластерах и совместным редактированием рабочей области несколькими удаленными клиентами. Игра прикольная, но только как упражнение для мозгов. За пару недель надоедает смертельно — как люди ее годами изучают, я не понимаю.
  • 0
    статья классная ) но она требует продолжения — не слова ни сказано о применении клеточных автоматов в моделировании физических, биологических и социальных систем
  • 0
    Интересно, а кто-нибудь пытался эту игру применять к построению P2P-сетей?
    • 0
      Как это? Ждем статьи от вас
      • 0
        к сожалению, не дождетесь — я заминусован :(
        • 0
          Так это легко исправить :)
          Все же было бы интересно увидеть такую статью )
  • +1
    Писал программу которая это эмулировала на олимпиаде как-то :-)
  • –2
    Офигеть, интересно, сколько еще общеизвестных топиков не были освещены на Хабрахабре.
  • +6
    А я пошёл дальше — реализовал «жизнь» в железе на микроконтроллере :)
    Вечером выложу фотки, если не забуду.
    • 0
      В железе — это на микросхемах серии K155!
      А так на микроконтроллере — все равно программно :)
      • 0
        Май факин шит… *вспоминая эксперименты в 8 классе над к155ид1*
        • 0
          хорошее было время.
          сто лет не брал в руки паяльник, а как выглядит транзистор кт315 — помню.

          Ах )
          • 0
            *продолжая ностальгические ози и ахи*
            На ТТЛ чипах уже лет 10-20 назад мало что делали, в осноном на КМОП все самоделки делались.
            Вот в 10 классе на двух микросхемах 565 серии кажется (генератор + счётчик) придя после школы и заскучав, я за час собрал таймер-детонатор для «бомбы» и запихал это всё в спичечный коробок вместе с батареей. Лампочка с открытой нитью накаливания через 10 тактов поджигала зажигательную смесь (уже не помню какой состав). Короче, бомба успешно рванула раза три :) до сих пор валяется где-то.
        • 0
          • 0
            КТ3102/КТ3107 :) фактически аналоги, тока в другом корпусе.
  • 0
    У меня получилась нация, которая не вымирает, со временем стабилизируется, и при этом запускает двух космонавтов в свободное плавание )
    А вообще жутко затягивает, вспомнил детство, на работе включать нельзя!
  • 0
    в детстве помню подарили мне книгу (что то типо занимательной математики… не помню точно названия) где было рассказано про эту игру… с тех пор постоянно в свободное время (в школе) играл в неё…

    у меня были целый тетрадки изрисованные непонятными ( для других людей) фигурками =)
  • 0
    Весьма занимательная «игра» — не знаю как правильно назвать.
    Даже в качестве игры — это весьма занимательно и хорошо отнимает время :)
  • +3
    я на паскале это писал в школе, помню =)
    правда не написал тогда.
  • –3
    я на паскале это писал в школе, помню =)
    правда не написал тогда.
  • +1
    Похоже на немного расширенные правила игры Го
  • +3
    А что книжку Уэзерелла «Этюды для программистов» никто не мучал в детстве? В мое время было очень популярное занятие. «Жизнь» одна из первых моих программ была, на gwbasic'е. ;))
  • +2
    странно — по-моему через Жизнь прошли, наверное, все программисты :)
  • –1
    круто
  • 0
    думал речь про Го пойдет, или ее аналог, названный среди школьников «Точки»

    ксо, я — недопрограммист( впервые о чем то подобном слышу…
  • +1
    Мой дядя в своё время написал «Жизнь» на флеше:
    magic.ntl.nnov.ru/flash/Life/Life.html

    Вот тут описание:
    magic.ntl.nnov.ru/flash/Life/YLife.htm

    «Жизнь Конвея»:
    magic.ntl.nnov.ru/flash/Life/ЖизньКонвея.htm
    • 0
      *«Жизнь» Конвея:
      magic.ntl.nnov.ru/flash/Life/Life1.htm

      предыдущая ссылка не работает.
  • +1
    Еще до того как прочитал заголовок поста, увидел картинку и вырвалось «о, это ж глайдер!» — и правда, оказался он :)
    Эх было время. Еще на старенький 486 скачал эмулятор «жизни» и сотню расстановок и весь вечер открывал, запускал и наслаждался
    • +1
      Не поверите, долго рыскал по инету в поисках фотографии тетрадного листа для оформления. Потом решил что проще самому сфотографировать. Ну и глайдер нарисовал для тех кто в теме ))
  • +1
    Моя первая «большая» программа =)
  • +1
    Это ж мое задание на летнюю практику! )) Забавно получилось: решил отвлечься от кода, зайти на хабр, а тут снова — оно ))

    Поделюсь тогда, пожалуй, ссылочками:

    www.conwaylife.com/wiki/index.php?title=Main_Page — большая коллекция паттернов
    entropymine.com/jason/life/ — еще паттерны: ружья, осцилляторы и т.д.

    beluch.boom.ru/lifelex/lexr.htm — перевод словаря Жизни, полезно для ознакомления с терминами

    written.ru/programs/life/ — еще один неплохой симулятор Жизни.
    • +1
      Жабы-убийцы против крученых Т-тетсонов II. Мой мозг )))
  • 0
    Стоит добавить, что «Жизнь» является тьюринг-полной, т.е. на ее основе можно реализовать любой алгоритм.
  • 0
    Вооще вот хороший эмулятор онлайн (java) www.conwaylife.com/
    Его основной плюс — зум, управление скоростью и большой набор стандартных паттернов для загрузки
  • 0
    писали на курсе втором. В Mathematica. Писали-писали, получился жуткий огромный код. А как оказалось, смысл лабы был освоить одну из фишек. В итоге наваяли всё 3-4 строчками (+5 строк вывод красивой анимации).
  • 0
    Еще один хороший эмулятор — lucidlife
  • +3
    Статья, хотья и боянистая, но хорошая, просто потому что описывает такую хорошую вещь как Life.
    Можно было бы и побольше информации об игре собрать. С ходу вспомнилось пара моментов:
    — Сам Конуэй «устойчивые фигуры» называл «любителями спокойной жизни».
    — Была гипотеза (если не ошибаюсь выдвинутая самим Конуэем), что при бесконечном поле невозможно сделать конфигурацию из конечного числа живых клеток, которая бы бесконечно увеличивалась. Опровержением гипотезы стало то самое глайдерное ружье.
    — Ничего не сказано про огромное количество интересных конфигураций — «большие глайдеры» (крейсеры и линкоры и необходимость их эскортирования меньшими глайдерами), «осцилографы», «бикфордовы шнуры», «паравозы».
    — Ничего нет про «сады Эдема» — конфигурации у которых нет предков.
    • 0
      Мне кажется, что если писать про Life, то статья должна быть очень обширной (балго в инете материала тонны), всеобъемлющей, я бы сказал, фундаментальной. Чтоб даже давно знакомые с этой игрой люди, узнали что-то новое, а «новички» восхитились простотой и гениальностью, красотой и изяществом идеи.
    • 0
      Еще вспомнил про определение «скорости света» в Life — скорость передвижения шахматного короля — 1 клетка в ход. Никакой процесс в Life не может идти быстрее «скорости света». Например, скорость полета глайдера 0,25 «скорости света».
    • 0
      Изначально так и хотел всё это расписать, но потом подумал, что слишком большая получится и неудобно будет читать. Кому уж совсем интересно — я там привел ссылку в конце на другую статью. Там всё это и расписано подробно на 4х страницах.
      Хотя, сейчас перечитал. Соглашусь с вами, что на самом интересном месте — описание фигур — она как бы обрывается.
      • +1
        Сделайте цикл статей. И хотя в свое время я много читал про Life, но гарантирую, что как минимум одного благодарного читателя вы получите.
    • 0
      Да и как-то не думал я, что столько людей про нее знают и мало того что знают — сами писали…
      • 0
        Да, очень многие программисты пишут свою версию Life, многим дают задание в школе и вузах. Я тоже писал, правда очень «уродскую» версию на ЭВМ «Агат» и сохранял на кассету.
  • 0
    Маленькая простая штука может уничтожить сложную стабильную структуру — и впрямь все как в жизни!
  • +1
    Давным-давно (лет 10 назад) написал программу (назвал CLife, это была моя первая программа на Visual Studio C++). Даже сделал сайт и выложил ее. Пароли от сайта давно потеряны. Но сайт не закрыли :)
    Кому интересно: clife.chat.ru/
    • 0
      Сайт тоже мой самый первый, поэтому юзабилити «на уровне», поэтому поясню: скачать программу можно на странице Download, кликнув по картинке около «CLife v.2.3».
  • 0
    • 0
      Ага, в таком маштабе поинтереснее наблюдать.
  • –1
    статья из серии «обратимся к истории». спасибо, вспомнил! )
    кстати, т.н. «глайдер» когдато давно был символом хакеров, благодаря этой игре
  • 0
    Давно читал в книге, которую взял у отца про жизнь, потом в универе лабораторную писал.
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    В раннем студенчестве писал эмулятор «жизни» на winapi. Эх… Жаль, что не сохранилось ни исходников, ни самой программы.
  • 0
  • 0
    Я этими штуками увлекался, когда в ADOM травку выращивал по таким правилам.
    Эх, ностальгия…
  • –1
    Так вот какие баяны надо постить на хабре? А я-то думал тут новое должно быть…
  • 0
    Реализация для Drupal: drupal.org/project/conwayslife
  • 0
    Эхххх ))) старый-добрый Лайф)

    Как бы то не было, но это одна из немногих «игрушек», которую я люблю))

    Автор, спасибо за линк и мемори)
    • 0
      Вам спасибо, что прочитали ))
  • 0
    В универе на практике по лиспу такое изучали :)
  • 0
    я правильно понимаю, что в итоге такая система либо придет в состояние покоя либо уйдет в бесконечный цикл?
    • 0
      Думаю да, либо покой, либо цикл, либо двигающийся цикл
      • 0
        Поскольку на ней можно реализовать машину Тьюринга, то результатом может быть эмуляция любого детерминированного алгоритма

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.