1. Райський сад [ правити | правити код ]
2. «Цифри» [ правити | правити код ]

Гра «Життя» ( англ. Conway's Game of Life) - клітинний автомат , Придуманий англійським математиком Джоном Конвеем в 1970 році .

• Місце дії цієї гри - «всесвіт» - це розмічена на клітини поверхню або площину - безмежна, обмежена, або замкнута (в межі - нескінченна площина).
• Кожна клітина на цій поверхні може перебувати в двох станах: бути «живою» (заповненої) або бути «мертвої» (порожній). клітка має вісім сусідів , Що оточують її.
• Розподіл живих клітин на початку гри називається першим поколінням. Кожне наступне покоління розраховується на основі попереднього за такими правилами:
  • в порожній (мертвої) клітці, поруч з якою рівно три живі клітини, зароджується життя;
  • якщо у живої клітини є дві або три живі сусідки, то ця клітина продовжує жити; в іншому випадку, якщо сусідів менше двох або більше трьох, клітина вмирає ( «від самотності» або «від перенаселеності»)
• Гра припиняється, якщо
  • на полі не залишиться жодної «живої» клітини
  • конфігурація на черговому кроці в точності (без зрушень і поворотів) повторить себе ж на одному з попередніх кроків (складається періодична конфігурація)
  • при черговому кроці жодна з клітин не змінює свого стану (складається стабільна конфігурація; попереднє правило, вироджені до одного кроку назад)

Ці прості правила призводять до величезного розмаїття форм, які можуть виникнути в грі.

Гравець не приймає прямої участі в грі, а лише розставляє або генерує початкову конфігурацію «живих» клітин, які потім взаємодіють згідно з правилами вже без його участі (він є спостерігачем).

Джон Конвей зацікавився проблемою, запропонованої в 1940-х роках відомим математиком Джоном фон Нейманом , Який намагався створити гіпотетичну машину, яка може відтворювати сама себе. Джону фон Нейманом вдалося створити математичну модель такої машини з дуже складними правилами. Конвей спробував спростити ідеї, запропоновані Нейманом, і врешті-решт йому вдалося створити правила, які стали правилами гри «Життя».

Вперше опис цієї гри було опубліковано в жовтневому ( 1970 рік ) Випуску журналу Scientific American , В рубриці «Математичні ігри» Мартіна Гарднера (Martin Gardner) [1] .

У комп'ютерних реалізаціях гри поле обмежено і (як правило) верхня межа поля «з'єднана» з нижньої, а ліва межа - з правого, що представляє собою емуляцію поверхні тора , Але на екрані поле завжди відображається у вигляді рівномірної сітки.

Найпростіший алгоритм «зміни покоління» послідовно переглядає всі осередки решітки і для кожного осередку підраховує сусідів, визначаючи долю кожної клітини (не зміниться, помре, народиться). Такий найпростіший алгоритм використовує два двовимірних масиву - один для поточного покоління, другий - для наступного.

Більш складний, але і більш швидкий алгоритм складає списки клітин для перегляду в наступному поколінні; клітини, які не можуть змінитися, в списки не вносяться. Наприклад, якщо будь-яка клітина і жодна з її сусідів залишилися незмінними на попередньому ходу, то ця клітина не зміниться і на поточному ходу.

Незабаром після опублікування правил було виявлено кілька цікавих шаблонів (варіантів розстановки живих клітин в першому поколінні), зокрема: r -пентаміно і планер (Glider).

Деякі такі фігури залишаються незмінними у всіх наступних поколіннях, стан інших періодично повторюється, в деяких випадках зі зміщенням всієї фігури. Існує фігура (Diehard) всього з семи живих клітин, нащадки якої існують протягом ста тридцяти поколінь, а потім зникають.

Конвей спочатку припустив, що ніяка початкова комбінація не може привести до необмеженого розмноження і запропонував премію в 50 доларів тому, хто доведе або спростує цю гіпотезу. Приз був отриманий групою з Массачусетського технологічного інституту , Яка придумала нерухому повторювану фігуру, яка періодично створювала рухомі «планери». Таким чином, кількість живих клітин могло рости необмежено. Потім були знайдені рухомі фігури, що залишають за собою «сміття» з інших фігур.

До теперішнього часу більш-менш склалася наступна класифікація фігур:

• стійкі фігури : Фігури, які залишаються незмінними
• довгожителі : Фігури, які довго змінюються, перш ніж стабілізуватися [2] .
• періодичні фігури : Фігури, у яких стан повторюється через деякий число поколінь
• Рухомі фігури : Фігури, у яких стан повторюється, але з деяким зміщенням
• рушниці : Фігури, у яких стан повторюється, але додатково з'являється рухається фігура
• паровози : Рухаються фігури, які залишають за собою сліди у вигляді стійких або періодичних фігур
• пожирачі : Стійкі фігури, які можуть пережити зіткнення з деякими рухомими фігурами
• Фігури, які при зіткненні з деякими фігурами дублюються.

Райський сад [ правити | правити код ]

Приклад Райського саду

райським садом (Сад Едему) називається таке розташування клітин, у якого не може бути попереднього покоління. Практично для будь-якої гри, стан клітин в якій визначається декількома сусідами на попередньому кроці, можна довести існування садів Едему, але побудувати конкретну фігуру набагато складніше.

«Цифри» [ правити | правити код ]

За допомогою найпростішого «шрифту» розміром 3 на 5 клітин, запропонованого, по всій видимості, Еріком Анджеліни в 2007 році, можна отримати дуже багато фігур. Наприклад, число 90, записане цим шрифтом, породжує планер [3] .

Хоча гра складається всього з двох простих правил, проте вона більш сорока років привертає увагу вчених. Гра «Життя» і її модифікації вплинули (в ряді випадків взаємно) на багато розділів таких точних наук, як математика, інформатика, фізика [4] . Це, зокрема:

Крім того, багато закономірностей, виявлені в грі, мають свої аналогії в інших, часом абсолютно «нематематичних» дисциплінах. Ось список наук, теорії яких мають цікаві точки дотику з феноменами «Життя»:

• кібернетика . Сама гра є вдалою спробою Конвея довести існування простих самовідтворюються систем, а також поява якогось «розуму» у самовідтворюються систем.
• Біологія . Зовнішня схожість з розвитком популяцій примітивних організмів вражає.
• бактеріологія . Деякі цікаві варіації гри з додатковими умовами можуть з точністю повторити розмноження бактерій, які з випадковою ймовірністю можуть мутувати (за умовою модифікації).
• фізіологія . Народження і смерть клітин подібні процесу виникнення і зникнення нейронних імпульсів.
• Астрономія . Еволюції деяких складних колоній дивним чином схематично повторюють етапи розвитку спіралеподібних галактик [5] [6] .
• Фізика твердого тіла . Теорія автоматів взагалі і гра «Життя» зокрема використовуються для аналізу «явищ переносу» - дифузії , в'язкості і теплопровідності .
• Квантова фізика . Поведінка «життєвих» осередків (народження нових і взаємне знищення) багато в чому нагадують процеси, що відбуваються при зіткненні елементарних частинок .
• Наномеханіка . Стаціонарні і пульсуючі колонії є показовим прикладом найпростіших пристроїв, створених на основі нанотехнологій.
• Електротехніка . Правила гри використовуються для моделювання самовідновлюються електричних ланцюгів .
• хімія . Конфігурації, подібні будуються в грі, виникають під час хімічних реакцій на поверхні, зокрема в дослідах М. С. Шакаевой виникають рухомі молекулярні конструкції аналогічні «життєвому» планеру. Також робляться спроби пояснити періодичні хімічні реакції за допомогою багатовимірних клітинних автоматів. Самоорганізацією елементарних частинок також займається Супрамолекулярна хімія .

Можливо, ця гра пов'язана і з іншими науковими явищами, в тому числі і з тими, про які сучасній науці поки невідомо. Також можливо, що ні відкриті на сьогодні закони природи і суспільства стануть більш зрозумілими завдяки «Життя» і її модифікаціям.

• Правила гри такі, що ніяка взаємодія не може передаватися швидше ходу шахового короля . Його швидкість - одна клітина в будь-якому напрямку - часто називають « швидкістю світла ».
• Фігура «планер» в 2003 році була запропонована в якості емблеми хакерів .
• Перше російськомовне згадка «Game of Life» відноситься до 1971 році і в перекладі журналу «Наука і життя» відома як «Еволюція».
• Якщо ввести в Google «conway's game of life», то на екрані буде подобу цієї гри [7] [8] .

• Існують модифікації гри «Життя» / «Еволюція» по: розмірності - на площині, в обсязі; кольоровості - однотонового, чорно-біла (шахова), повнокольоровий; напрямку алгоритму - прямий, зворотний; констант еволюції - класичні (B3 / S23), змінені; розмірами ігрового поля - обмежене, необмежене, напівобмеженого; активності поля - активне, пасивне; кількості гравців - zero-game, один, два; активності гри - пасивна, активна; геометрії поля - прямокутна, шестикутна.
• Цікавим є зворотна задача Конвея - пошук попередника заданої фігури [9] . Для вирішення її може залучатися апарат статистики: метод Монте-Карло , імітаційне моделювання , А також весь арсенал евристичних методів .
• Ефективним алгоритмом повноколірного гри є декомпозиція вихідного зображення на однотонового, з подальшою, після застосування до них класичних правил життя, їх суперпозицією; для об'ємних варіантів - ортогональний алгоритм перетворень. Приклади практичного застосування цього - всілякі заставки, абстрактні зображення, дизайн творів мистецтва.
• У шаховому, чорно-білому варіанті беруть участь два гравці, колір народження визначається за переважанням кольору в породжує тріаді, запис ходів здійснюється за правилами шахових нотацій. Крім оригінальних граничних утворень тут спостерігаються колізії кольору, наприклад, «глайдер» в нотації: білі a2b2c2, чорні c3b4 - повністю знебарвлюється за цикл перетворень, а то ж: білі a2b2, чорні c2c3 b4 - демонструється хроматична циклічність «глайдера» в рамках його геометричній циклічності.
• В активній шаховій грі гравцям надається можливість впливати на події «Життя / Еволюції» одиничним введенням - виведенням обмеженої кількості фішок свого кольору з метою експансії, стабілізації ходу історії, протидії в цьому противнику. Теоретичні основи тут - методи прийняття рішення , апарат теорії ігор .

• Andrew Adamatzky. Game of Life Cellular Automata. - Springer-Verlag London, 2010. - ISBN 978-1-84996-216-2 , 978-1-4471-6154-7, 978-1-84996-217-9. - DOI : 10.1007 / 978-1-84996-217-9 .
• Paul Rendell. Turing Machine Universality of the Game of Life. - Springer International Publishing, 2016. - (Emergence, Complexity and Computation; vol. 18). - ISBN 978-3-319-19841-5 , 978-3-319-19842-2. - DOI : 10.1007 / 978-3-319-19842-2 .
• Уезерелл Ч. Етюди для програмістів. - М.: Мир, 1982. - С. 19-22.
• Гарднер М. Хрестики-нулики. - М.: Мир, 1988. - С. 287-343. - ISBN 5030012346 .
• Щеглов Г. Шахова Еволюція. - Lambert Academic Publishing, 2012. - 88 с. - ISBN 9783848424603 .
• Трофимов М. Життя на Макінтош // Монітор, 1995. - № 2, с.72; № 4, с.72; № 5, с.66.
• Журнал Наука и Жизнь. № 8, 1971, с. 130-133.
• Журнал В світі наукових відкриттів. № 5.4 (11), 2010, с. 50-53, 139. ISSN 2072-0831 (print), ISSN 2307-9428 (online)
• Додаток до журналу Юний технік. № 8 серпень 1989, с. 11-13