Тази статия се нуждае от вниманието на редактор с по-задълбочени познания. Ако смятате, че имате необходимите знания, подобрете тази страница.
За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. Шаблонът е поставен на 12:55, 9 ноември 2016 (UTC).
Играта „Живот“ (на английски: Game of Life, Conway's Game of Life) е популярна игра с нула на брой играчи, измислена през 1970 година от Джон Хортън Конуей (на английски: John Horton Conway), която е най-известният пример за клетъчен автомат. Пространството на играта е (крайна или безкрайна) двумерна решетка от квадратни клетки, всяка от които може да се намира в едно от общо две възможни състояния: жива или мъртва. Всяка клетка от решетката взаимодейства с осемте си съседа: съседните клетки по хоризонтал, вертикал и диагонал. На итеративен принцип, състоянието на всяка клетка в решетката запазва или променя състоянието си в зависимост от предварително зададен списък от правила.
Играта е пример за способности като възникване (самопораждане) и самоорганизация. С демонстрацията на това как от прилагането на прости правила се генерират сложни структури тя представлява интерес за физици, биолози, икономисти, математици, философи и учени от други научни направления.
Произход
Конуей е бил заинтересован от проблем, поставен през 1940-те от математика Джон фон Нойман, който се е опитал да разработи хипотетична машина, която да може да създава копия на себе си. Успява, когато намира математически модел за такава машина с изключително сложни правила и правоъгълна решетка. „Живот“ е резултат от успешния опит на Конуей да опрости драстично идеите на фон Нойман. Играта излиза за пръв път в Scientific American през октомври 1970 в колонката на Мартин Гарднър „Математически игри“. От теоретична гледна точка играта е интересна, защото има свойствата на универсалната машина на Тюринг, което означава, че всичко, което може да бъде програмирано посредством алгоритъм, може да бъде програмирано с „Живот“. Гарднър пише:
„
Играта прави Конуей известен моментално, но също така отваря цяла нова област в математическото проучване – областта на клетъчните автомати. Поради аналогията на „Живот“ с появата, пада и промените на едно общество от живи организми, играта принадлежи към развиващия се жанр на така наречените „игри симулации“ (игри, които пресъздават процеси от истинския живот).
“
От публикацията си насам, „Живот“ привлича голям интерес с изненадващите начини, по които могат да еволюират създадените модели. „Живот“ предоставя пример за пораждане и самоорганизация. Учени в различни сфери (компютърни науки, физика, биология, биохимия, икономика, математика, философия и генеративни науки) извличат полза от начина, по който от прилагането на простите правила на играта могат да се появят сложни модели. Играта също така може да служи като поучителна аналогия, която да показва донякъде противоестествената представа, че „дизайн“ и „организация“ могат да възникнат спонтанно в отсъствието на дизайнер/създател. Например Даниел Денет, философ и когнитивен учен, използва аналогията с вселената на „Живот“, за да покаже възможната еволюция на сложни философски конструкции като съзнание и свободна воля от относително простия набор детерминистични физически закони, които действат в нашата вселена.
Популярността на „Живот“ е подпомогната от появата ѝ точно в момент, в който на пазара са пуснати ново поколение достъпни миникомпютри. Играта е можела да върви с часове на тези машини, които иначе биха останали неизползвани нощем. В това отношение играта предвещава по-късната популярност на компютърно генерирани фрактали. За много „Живот“ е просто софтуерно предизвикателство – забавен начин да се използва иначе прахосано време на процесора. За други обаче, „Живот“ има по-философско значение. Около нея през 1970-те и по-късно е сформиран култ. Текущите разработки са стигнали толкова далеч, че се създават теоретични емулации на компютърни системи, вместени в рамките на „Живот“.
Конуей избира правилата внимателно, след значително количество експерименти, така че да отговарят на следните критерии:
Не трябва да има рязък растеж.
Трябва да съществува малки начални модели с хаотично, непредсказуемо развитие.
Трябва да има потенциал за универсални конструктори на фон Нойман (възможност за саморазвитие).
Правилата трябва да са колкото е възможно по-прости и да се придържат към горепосочените правила.
Правила
Оригиналните правила на играта „Живот“ са следните:
Всяка жива клетка с по-малко от две живи съседни клетки умира (от самота).
Всяка жива клетка с повече от три живи съседни клетки умира (от пренаселеност).
Всяка жива клетка с две или три живи съседни клетки остава жива и на следващата итерация.
Всяка мъртва клетка с точно три живи съседни клетки се превръща в жива клетка.
Тези правила могат да търпят множество модификации по отношение стойностите, определящи състоянието на дадена клетка.
Началното състояние на полето се разглежда като своеобразен посев. На всяка итерация (още наричана „генерация“, „поколение“) правилата на системата се прилагат едновременно към всяка отделна клетка в полето и новите „раждания“ и „смърти“ на клетките се случват едновременно. По този начин всяка итерация е функция, зависеща само от състоянието на системата от предходната итерация, и няма елемент на случайност. В този смисъл играта е за нула играчи: това означава, че развоят ѝ се определя само от началното ѝ състояние, без да е необходима намеса от човек. Взаимодействието на човека с играта се изчерпва със задаването на началните стойности на клетките в полето, наблюдението на развитието ѝ и евентуалното ѝ прекъсване след определен брой итерации.
Примерни конфигурации
Най-ранните интересни модели в „Живот“ са открити без употребата на компютър. Най-простите статични модели (still lifes) и повтаряеми модели (осцилатори) са открити при проследяването на развитието на различни малки стартови конфигурации, използвайки милиметрова хартия, черни дъски, игрови дъски (като играта Го) и подобни. По време на това ранно проучване, Конуей открива, че R-пентомино не успява да се стабилизира в малък брой поколения. Всъщност отнема 1103 поколения да се стабилизира, а дотогава има популация от 116 и е изстреляла шест „глайдера“ (това са структури, които запазват поулацията си, като се придвижват в произволна посока).
Много различни типове модели се появяват в „Живот“ включително статици, осцилатори и мозайки, които се пренасят по полето, оприличавани на космически кораби и совалки. Някои често срещани примери от тези три класа са показани по-долу, където живите клетки са обозначени в черно, а мъртвите в бяло.
Статични мозайки
Блок
Kошер
Пита
Лодка
Осцилатори
Мигач (период 2)
Жаба (период 2)
Фар (период 2)
Пулсар (период 3)
Петнадесетобой (период 15)
„Пулсарът“ е най-често срещаният 3-периоден осцилатор. Голямото мнозинство от естествено възникващо осцилатори са двупериодни, като блинкър и жаба, но се знае, че съществуват и многопериодни осцилатори, 4, 8, 14, 15 и 30-периодни осцилатори са били откривани от произволни начални условия.
За модели, наречени „Матусал“ отнема много периоди, за да се стабилизират, като първият открит „Матусал“ е именно R-пентомино.
“Умирай трудно“ е модел, който впоследствие изчезва (вместо да се стабилизира) след 130 поколения, за което се смята, че е максимумът за фигури със седем или по-малко клетки.
За „Жълъд“ са нужни 5206 поколения да генерира 633 клетки, от които 13 са глайдери.
Глайдери
Р-Пентомино
Умирай трудно
Жълъд
Конуей първоначално заключва, че никоя фигура не може да расте безкрайно – с други думи, всяка начална конфигурация с ограничен брой живи клетки, популацията не може да порасне над определен краен брой. С първоначалното излизане на играта в „Математически игри“ Конуей предлага награда от 50 долара на първия, който успее да докаже или отхвърли хипотезата му. Наградата е спечелена през ноември същата година от отбор от MIT, воден от Бил Госпър. „Глайдер оръдието на Госпър“ произвежда първия си глайдер на 15-о поколение и по един глайдер на всяко 30-о поколение нататък. Дълго време това е най-малкият познат „глайдер оръдие“ (структура, генерираща глайдери). През 2015 е открито 120-периодно „оръдие“, което има по-малко живи клетки, но по-голяма ограничителна кутия.
Глайдер оръдие на Госпер
По-късно са открити и по-малки модели, които също могат да растат безкрайно. Всяка една от следните три фигури расте безкрайно – първите две създават един „блоков двигател“, а третата създава два. Първата има само 10 живи клетки (което е доказано, че е минимумът). Втората се вмества в квадрат 5х5. Височината на третата е само една клетка:
По-късни открития включват други „оръдия“, които са стационарни/неподвижни и изстрелват глайдери или совалки. „Параходче“ оставя след себе си диря от остатъци и „носачи“, които се движат и произвеждат совалки. Госпър също така създава първата мозайка с асимптотично оптимална геометрична скорост на растеж, наречена „развъдник“ или „омар“, която работи, като оставя следа от оръдия.
Възможно е глайдерите да взаимодействат с други обекти по интересни начини. Например, ако два глайдера са изстреляни в блок по точно определен начин, блокът ще се премести по-близо до източника на глайдерите. Ако три глайдера са изстреляни по точно определен начин, блокът ще се премести по-надалеч. Тази „памет“ на плъзгащия блок може да се използва като симулация на брояч. Възможно е да се построят логически елементи като AND, OR и NOT използвайки глайдери. Също така е възможно да се построи мозайка, която работи като краен автомат, свързан с два брояча. Това има същия програмен капацитет като универсалната машина на Тюринг, тоест „Живот“ е теоретично толкова мощна, колкото всеки друг компютър с неограничена памет и време – тя е Тюринг завършена.
Също така, една мозайка може да съдържа набор от оръдия, които изстрелват глайдери по такъв начин, че да построяват нови обекти, включително копия на оригиналната фигура. Може да бъде построен универсален конструктор, в който да е включен Тюринг завършен компютър и който може да строи множество видове сложни обекти, включително и копия на себе си.
Самовъзпроизвеждане
На 18 май 2010 Андрю Уейд обяви самопострояваща се мозайка, наречена Близнаци (Gemini), която създава копия на себе си и унищожава оригинала. Тази мозайка се възпроизвежда в 34 милиона поколения и използва наръчник, направен от глайдери, които осцилират между две стабилни конфигурации, направени от Чапмън-Грийн строителни ръце. Тези на свой ред създават копия на мозайката и унищожават предишното копие. Gemini е също така и совалка, която всъщност не е нито ортогонална, нито диагонална (тези са наречени конници).
На 23 ноември 2013 Дейв Грийн построява първия репликатор в „Живот“, който създава завършено копие на себе си, включително и наръчника.
Итерация
От произволна начална мозайка от живи клетки на полето, наблюдателите ще видят как популацията се сменя постоянно поколение след поколение. Мозайките, които се образува от простите правила, могат да бъдат разгледани като форма на математическа красота. Малки изолирани подмозайки без начална симетрия имат склонността да се превръщат в симетрични. Веднъж случило се, симетрията може да стане по-богата, но не може да бъде изгубена освен ако съседна подмозайка не се приближи достатъчно близко, за да я разруши. В много малък брой случаи обществото умира изцяло, но това се случва след голямо количество поколения. Повечето начални мозайки „изгарят“ в един момент, оставяйки стабилни фигури или мозайки, които осцилират между две или повече състояния. Множество също произвеждат един или повече глайдера или совалки, които пътуват безкрайно надалеч от началната точка. Заради правилата, базирани на съседство, никаква информация не може да пътува по полето с по-голяма скорост от една клетка на период затова и тази скорост е определена като скоростта на светлината в клетъчните автомати и се обозначава с C.
Алгоритми
Ранните форми с неопределено развитие, като Р-пентомино, подтикнали програмистите по света да пишат програми, с които да проследят развитието на формите от играта. Повечето ранни алгоритми били подобни: клетките се представяли като двуизмерен масив в паметта на компютъра. Най-често се ползват два масива: първият представлява множеството от клетки от текущото поколение, а във втория се изчислява и записва множеството от клетки от следващото поколение. Обикновено за описание на съответната клетка – жива или мъртва се ползват съответно 1 или 0. За обхождане на масива и за изчисленията се имплементират вложени цикли, като се итерира през елементите и за всеки един елемент се итерира през съседните му, преброявайки онези, които са живи, като от резултата от преброяването се определя дали съответната клетка е жива или мъртва. Резултатът се записва в съответната клетка на втория масив. Масивът се изобразява на екрана. След като обхождането приключи, масивите се разменят, като масивът – наследник от предишната итерация вече се третира като настоящ.
Съществуват многообразни леки подобрения, които могат да се приложат към тази обща схема, които спомагат за редуциране на някои излишни изчисления. Например, ако съществува зона от масива (дадена клетка с всичките ѝ съседни клетки), в която не са настъпили промени в състоянията на елементите по време на текущата итерация, то със сигурност няма да настъпят промени и в следващата. По този начин могат да се следят само активните зони и да се пропусне обхождане и актуализация на неактивните.
За да се избегнат разклонения на процеса по време на обхождането във вътрешния цикъл, можем да прибегнем от егоцентрична перспектива, където се разглеждат отделните взаимовръзки между централната клетка и нейните съседи към по-общата перспектива на „научно наблюдение“: ако сумата на всички 9 клетки е равна на 3, то състоянието на централната клетка в следващото поколение ще е „живот“ (1), без да се взима предвид моментното ѝ състояние. Ако сумата е равна на 4, клетката не променя състоянието си. При всяка друга стойност на сумата, състоянието ѝ става „смърт“ (0).
При нужда от пестене на памет, вторият двумерен масив може да бъде заменен с 3 линейни едномерни буферни масива – в първия буфер се записва резултата от изчислението на един ред от двумерния масив, след това във втория буфер се записва резултата от изчисленията на следващия ред, като на предходния ред се презаписва съдържанието на първия буфер, който вече е свободен да приеме резултатите от изчисленията на третия ред от масива и т.н. до края. В случай, че се ползва тороидален масив, е нужен и трети буфер, който да пази началното състояние на първия ред, докато не се изчисли последния ред.
Снимка на puffer-type breeder (червени), който оставя глайдер оръжия (зелени) по пътя си, които на свой ред създават глайдери (сини)
По принцип полето, върху което се разпростира играта „Живот“, е безкрайно, но компютрите имат крайна величина памет. Това може да породи проблем, когато се итерира около границите на масива. Програмистите използват няколко стратегии за справяне с този проблем. Най-простата стратегия е да се допусне, че клетките извън масива са мъртви (0). Този подход се имплементира лесно, но води до неправилни резултати, когато активната зона пресече граница на масива. По-сложния подход е да краищата на масива да се считат за съседни – левия и десния от една страна и горния и долния от друга, което обуславя масив с тороидална форма. В резултат на това, когато активната област премине да кажем долния (десния) край, тя се появява в горния (левия) край. И при този стратегия е възможна появата на някои неточности, свързани с голямото нарастване на активната зона, но поне може да се избегнат патологични ефекти по краищата. Техники, свързани с динамично преоразмеряване на полето, също могат да влязат в употреба, създавайки все по-голям масив, в който да се развиват формите, които излизат отвъд първоначалните граници.
Като алтернатива програмистите могат да изоставят идеята да използват двуизмерен масив като игрално поле и да употребят друга структура от данни, като например вектор от координати (X, Y), в който да се пазят живите клетки. Този подход позволява на формата да се движи безпрепятствено по полето, стига популацията да не превишава големината на координатната система. Недостатък е, че преброяването на живите съседи става чрез алгоритми за търсене, което забавя скоростта на симулация, но може да се преодолее чрез прилагане на по-сложни структури от данни.
За да се симулира еволюцията на голям брой клетки в дългосрочен план, в употреба влизат по-сложни алгоритми, като например Hashlife. Съществува и метод, приложим и върху други клетъчни автомати за имплементиране на играта „Живот“, ползващ случайни асинхронни обновявания, които емулират точно поведението при синхронна имплементация.
Съществува сорс код, базово имплементиращ играта, написан на различни езици за програмиране, в т.ч. C, C++, Java и Python.
Модификации
След играта „Живот“ се развиват нови сходни клетъчни автомати. Стандартната „Игра на живота“ се представя със символите „B3/S23“: Една клетка се счита за „Родена“ (Born), ако има точно 3 съседни, „Остава жива“ (Stays Alive), ако има 2 или 3 живи съседни клетки, в противен случай умира. Първото условие или списък от условия е свързано с това какво е необходимо, за да може една мъртва клетка да се роди отново. Следващият набор включва изискването как една жива клетка да оцелее до следващо поколение. Следователно „B6/S16“ означава, че една клетка е родена, ако има 6 съседни, и ще живее, докато около нея има 1 или 6 съседни. Клетъчният автомат на двумерната решетка, който може да бъде описан по този начин, е познат като Life-like клетъчен автомат. Друг често срещан Life-like автомат – Highlife, е описан от правилото „B36/S23“, защото имайки 6 съседки клетки в допълнение на първоначалното правило на играта „B3/S23“, става причина за раждане. HighLife е добре познат заради често срещаните му двойници. Съществуват и допълнителни Life-like клетъчни автомати, въпреки че по-голямата част от тях създават вселени, които или са твърде хаотични, или твърде пусти, за да представляват интерес.
Някои модификации на играта променят както геометрията на вселените, така и самото правило. Можем да приемем, че горните модификатори са 2D квадрати, защото светът е двуизмерен и е поставен в квадратна решетка. 1D квадратните модификатори (познати като първичен клетъчен автомат) и 3D квадратните модификатори са били разработени, тъй като имат 2D шестоъгълни и 2D триъгълни модификатори. Изработен е бил също така и вариант, използващ непериодична мрежа.
Правилото на Конуей може също да бъде обобщено така, че вместо две състояния (жив или мъртъв), има три или повече. След това стадийната промяна се определя от система за претегляне или чрез таблица, определяща отделните правила за преминава на всяко състояние. Например: всяко от многоцветната „Таблица с правила“ на Mirek's Cellebration и фамилията от правила „Weighted Life“ включва правила подобни на „Живот“.
В определени Life-like модификатори могат да се наблюдават и структури, свързани с фрактали и фрактални системи. Например автомат „B1/S12“ генерира четири много близки приближения на триъгълника на Серпински, когато се прилага за една-единствена жива клетка. Триъгълникът на Серпински също може да се наблюдава в „Играта на живота“ на Конуей, чрез изследване на дългосрочния растеж на дълга линия на живи клетки с дебелина една клетка, както и в Highlife, Seeds („B2/S“), и правилото на Волфрам (Wolfram's Rule 90).
„Имиграция“ е модификатор, който е много подобен на „Играта на живота“ на Конуей, с изключение на това, че има две „живи“ състояния (често изразени в два различни цвята). Всеки път, когато се роди нова клетка, тя приема „живо“ състояние, когато е най-голямата от трите клетки, които са се родили. Тази функция може да се използва, за да се разгледа взаимодействието между космически кораби и други „обекти“ в рамките на играта. Друг подобен модификатор, наречен QuadLife, включва 4 различни живи състояния. Когато се роди нова клетка от 3 различни живи съседни клетки, тя приема четвъртата стойност. Друг случай като имиграцията, приема преобладаващата стойност. С изключение на модификаторите сред живите клетки, два от тези модификатори се държат по същия начин като живите.
