Живот (игра)

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Играта „Живот“ (на английски: Game of Life, Conway's Game of Life) е популярна игра с нула на брой играчи, измислена през 1970 година от Джон Хортън Конуей (на английски: John Horton Conway), която се явява най-известният пример за клетъчен автомат. Пространството на играта е (крайна или безкрайна) двумерна решетка от квадратни клетки, всяка от които може да се намира в едно от общо две възможни състояния: жива или мъртва. Всяка клетка от решетката взаимодейства с осемте си съседа, т.е. клетките разположени в съседство от нея по хоризонтал, вертикал и диагонал. На итеративен принцип, състоянието на всяка клетка в решетката запазва или променя състоянието си в зависимост от предварително зададен списък от правила.

Играта е пример за способности като възникване (самопораждане) и самоорганизация. С това как сложни структури се генерират от прилагането на прости правила тя представлява интерес за физици, биолози, икономисти, математици, философи и учени от други научни направления.

Произход[редактиране | редактиране на кода]

Конуей е бил заинтересован в проблем, поставен през 40-те от математика Джон фон Нeйман, който се е опитал да разработи хипотетична машина, която да може да създава копия на себе си. Успява, когато намира математически модел за такава машина с изключително сложни правила и правоъгълна решетка. "Живот" е резултат от успешния опит на Конуей да опрости драстично идеите на фон Нойман. Играта излиза за пръв път в изданието на Scientific America през октомври 1970 в колонката на Мартин Гарднър „Математически Игри“. От теоритична гледна точка играта е интересна, защото има свойствата на универсалната машина на Тюринг, което означава, че всичко, което може да бъде програмирано посредством алгоритъм, може да бъде програмирано с "Живот". Гарднър пише:

Играта прави Конуей става известна моментално, но също така отваря цяла нова област в математическото проучване – областта на клетъчните автомати. Поради аналогията на "Живот" с появата, пада и промените на едно общество от живи организми, играта принадлежи към развиващия се жанр на така наречените „игри симулации“ (игри, които пресъздават процеси от истинския живот).

От публикацията си насам, "Живот" е привлякла голям интерес заради изненадващите начини, по които модели могат да еволюират. "Живот" предоставя пример за раждане и само-организация. Учени в различни сфери включително компютърни науки, физика, биология, биохимия, икономика, математика, философия и генеративни науки са извлекли полза от начинът, по който сложни модели могат да се появят от прилагането на простите правила на играта. Играта също така може да служи като поучителна аналогия, която да показва донякъде противоестествената представа, че „дизайн“ и „организация“ могат да възникнат спонтанно в отсъствието на дизайнер/създател. Например, Даниел Денет, философ и когнитивен учен, използва аналогията с вселената на "Живот", за да покаже възможната еволюция на сложни философски конструкции като съзнание и свободна воля от относително простия набор детерминистични физически закони, които действат в нашата вселена.

Популярността на "Живот" е била спомогната от появата ѝ точно в момент, в който ново поколение достъпни миникомпютри са пуснати на пазара. Играта е можела да върви с часове на тези машини, които иначе биха останали неизползвани нощем. В това отношение играта предвещава по-късната популярност на компютърно генерирани фрактали. За много "Живот" е била просто програмистко предизвикателство – забавен начин да използват иначе прахосани цикли на процесора. За други обаче, "Живот" е имала по-философско значение. Около нея е сфромиран култ през 70-те и по-късно. Текущите разработки са стигнали толкова далеч, че се създават теоритични емулации на компютърни системи, вместени в решетката на "Живот".

Конуей избира неговите правила внимателно след значително количество експерименти, така че да отговарят на следните критерии:

  1. Не трябва да има рязък растеж.
  2. Трябва да съществува малки начални модели с хаотично, непредсказуемо развитие.
  3. Трябва да има потенциал за универсални конструктори на фон Нойман (възможност за саморазвитие).
  4. Правилата трябва да са колкото е възможно по-прости и да се придържат към горепосочените правила.

Правила[редактиране | редактиране на кода]

Оригиналните правила на играта „Живот“ са следните:

  1. Всяка жива клетка с по-малко от две живи съседни клетки умира (от самота).
  2. Всяка жива клетка с повече от три живи съседни клетки умира (от пренаселеност).
  3. Всяка жива клетка с две или три живи съседни клетки остава жива и на следващата итерация.
  4. Всяка мъртва клетка с точно три живи съседни клетки се превръща в жива клетка.

Тези правила могат да търпят множество модификации по отношение стойностите, определящи състоянието на дадена клетка.

Началното състояние на полето се разглежда като своеобразен посев. На всяка итерация (още наричана „генерация“, „поколение“) правилата на системата се прилагат едновременно към всяка отделна клетка в полето и новите „раждания“ и „смърти“ на клетките се случват едновременно. По този начин всяка итерация е функция, зависеща само от състоянието на системата от предходната итерация, и няма елемент на случайност. В този смисъл играта е за нула играчи: това означава, че развоят ѝ се определя само от началното ѝ състояние, без да е необходима намеса от човек. Взаимодействието на човека с играта се изчерпва със задаването на началните стойности на клетките в полето, наблюдението на развитието ѝ и евентуалното ѝ прекъсване след определен брой итерации.

Примерни конфигурации[редактиране | редактиране на кода]

Най-ранните интересни патерни в "Живот" са били открити без употребата на компютър. Най-простите статични патерни (still lifes) и повтаряеми патерни (осцилатори) са били открити при проследяването на развитието на различни малки стартови конфигурации, използвайки милиметрова хартия, черни дъски, игрови дъски (като Go) и подобни. По време на това ранно проучване, Конуей открива, че R-пентомино не успява да се се стабилизира в малък брой поколения. Всъщност отнема 1103 поколения да се стабилизира, а до тогава има популация от 116 и е изстреляла шест глайдера (това са били първите открити глайдери).

Много различни типове патерни се появяват в "Живот" включително статици, осцилатори и мозайки, които се пренасят по полето, оприличавани на космически кораби и совалки. Някои често срещани примери от тези три класа са показани по-долу, където живите клетки са обозначени в черно, а мъртвите в бяло.

Статични мозайки
Блок Game of life block with border.svg
Koшер Game of life beehive.svg
Пита Game of life loaf.svg
Лодка Game of life boat.svg
Осцилатори
Мигач (период 2) Game of life blinker.gif
Жаба (период 2) Game of life toad.gif
Фар (период 2) Game of life beacon.gif
Пулсар (период 3) Game of life pulsar.gif
Петнадесетобой (период 15) I-Column.gif

„Пулсарът“ е най-често срещания 3-периоден осцилатор. Голямото мнозинство от естествено възникващо осцилатори са двупериодни, като блинкър и жаба, но се знае, че съществуват и многопериодни осцилатори, 4, 8, 14, 15 и 30-периодни осцилатори са били откривани от произволни начални условия.

За патерни, наречени „Матусал“ отнема много периоди, за да се стабилизират, като пъривят открит „Матусал“ е именно R-пентомино. “Умирай трудно“ е патерн, който в последствие изчезва (вместо да се стабилизира) след 130 поколения, за което се смята, че е максимума за фигури със седем или по-малко клетки.

За „Жълъд“ са нужни 5206 поколения да генерира 633 клетки, от които 13 са глайдери.

Глайдери
Р-Пентомимо Game of life fpento.svg
Умирай трудно Game of life diehard.svg
Жълъд Game of life acorn.svg

Конуей първоначално заключва, че никоя фигура не може да расте безкрайно – с други думи, всяка начална конфигурация с ограничен брой живи клетки, популацията не може да порасне над определен краен брой. С първоначалното излизане на играта в „Математически игри“ Конуей предлага награда от 50 долара на първия човек, който успее да докаже или отхвърли хипотезата му. Наградата е спечелена през ноември същата година от отбор от MIT, воден от Бил Госпър. „Глайдер оръдието на Госпър“ произвежда първия си глайдер на 15-то поколение и по един глайдер на всяко 30-то поколение нататък. Дълго време това е бил най-малкият познат „глайдер оръдие“. През 2015 е открито 120-периодно “оръдие“, което има по-малко живи клетки, но по-голяма ограничителна кутия.

Глайдер оръдие на Госпер Game of life glider gun.svg

По-късно са открити и по-малки патерни, които също могат да растат безкрайно. Всяка една от следните три фигури растат безкрайно – първите две създават „блоков двигател“,а третата създава два такива. Първата има само 10 живи клетки (което е доказано, че е минимума). Втората се вмества в квадрат 5х5. Височината на третата е само една клетка:

Game of life infinite1.svg
Game of life infinite2.svg

Game of life infinite3.svg

По-късни открития включват други „оръдия“, които са стационарни/неподвижни и изстрелват глайдери или совалки. „Параходче“ оставя след себе си диря от остатъци и „носачи“, които се движат и произвеждат совалки. Госпър също така създава първата мозайка с асимптотично оптимална геометрична/ скорост на растеж, наречена „развъдник“ или „омар“, която работи като оставя следа от оръдия.

Възможно е глайдерите да взаимодействат с дуги обекти по интересни начини. Например, ако два глайдера са изстреляни в блок по точно определен начин, блокът ще се премести по-близо до източника на глайдерите. Ако три глайдера са изстреляни по точно определен начин, блокът ще се премести по-надалеч. Тази „памет“ на плъзгащия блок може да се използва като симулация на брояч. Възможно е да се построят логически елементи като AND, OR и NOT използвайки глайдери. Също така е възможно да се построи мозайка, която работи като краен автомат, свързан с два брояча. Това има същия програмен капацитет като универсалната машина на Тюринг, тоест "Живот" е теоритично толкова мощна, колкото всеки друг компютър с неограничена памет и време – тя е Тюринг завършена.

Също така, една мозайка може да съдържа набор от оръдия, които изстрелват глайдери по такъв начин, че да построяват нови обекти, включително копия на оригиналната фигура. Универсален конструктор може да бъде построен, в който да е включен Тюринг завършен компютър и който може да строи множество видове сложни обекти, включително и копия на себе си.

Самовъзпроизвеждане[редактиране | редактиране на кода]

На 18 Май 2010, Андрю Уейд обяви само-построяваща се мозайка, наречена Близнаци, която създава копия на себе си и унищожава оригинала. Тази мозайка се възпроизвежда в 34 милиона поколения и използва наръчник, направен от глайдери, които осцилират между две стабилни конфигурации, направени от Чапмън-Грийн строителни ръце. Тези на свой ред създават копия на мозайката и унищожават предишното копие. Gemini е също така и совалка, която всъщност не е нито ортогонална, нито диагонална (тези са наречени конници) На 23 ноември 2013 Дейв Грийн построява първия репликатор в "Живот", който създава завършено копие на себе си, включително и наръчника.

Итерация[редактиране | редактиране на кода]

От прозиволна начална мозайка от живи клетки на полето, наблюдателите ще видят как популацията се сменя постоянно поколение след поколение. Мозайките, които се образува от простите правила могат да бъдат разгледани като форма на математическа красота. Малки изолирани под-мозайки без начална симетрия имат склоността да се превръщат в симетрични. Веднъж случило се, симетрията може да стане по-богата но не може да бъде изгубена освен ако съседна под-мозайка не се приближи достатъчно близко, за да я разруши. В много малък брой случаи обществото умира изцяло, но това се случва след голямо количество поколения. Повечето начални мозайки „изгарят“ в един момент, оставяйки стабилни фигури или мозайки, които осцилират между две или повече състояния. Множество също произвеждат един или повече глайдера или совалки, които пътуват безкрайно надалеч от началната точка. Заради правилата, базирани на съседство, никаква информация не може да пътува по полето с по-голяма скорост от една клетка на период затова и тази скорост е определена като скоростта на светлината в клетъчните автомати и се обозначава с C.

Алгоритми[редактиране | редактиране на кода]

Ранните форми с неопределено развитие, като Р-пентомино, подтикнали програмистите по света да пишат програми, с които да проследят развитието на формите от играта. Повечето ранни алгоритми били подобни: клетките се представяли като двуизмерен масив в паметта на компютъра. Най-често се ползват два масива: първия представлява множеството от клетки от текущото поколение, а във втория се изчислява и записва множеството от клетки от следващото поколение. Обикновено за описание на съответната клетка – жива или мъртва се ползват съответно 1 или 0. За обхождане на масива и за изчисленията се имплементира чрез вложени цикли, като се итерира през елементите и за всеки един елемент се итерира през съседните му, преброявайки онези, които са живи, като от резултата от преброяването се определя дали съответната клетка е жива или мъртва. Резултатът се записва в съответната клетка на втория масив. Масивът се изобразява на екрана. След като обхождането приключи, масивите се разменят, като масивът – наследник от предишната итерация вече се третира като настоящ.

Съществуват многообразни леки подобрения, които могат да се приложат към тази обща схема, които спомагат за редуциране на някои излишни изчисления. Например, ако съществува зона от масива (дадена клетка с всичките ѝ съседни клетки), в която не са настъпили промени в състоянията на елементите по време на текущата итерация, то със сигурност няма да настъпят промени и в следващата. По този начин могат да се следят само активните зони и да се пропусне обхождане и актуализация на неактивните.

За да се избегнат разклонения на процеса по време на обхождането във вътрешния цикъл, можем да прибегнем от егоцентрична перспектива, където се разглеждат отделните взаимовръзки между централната клетка и нейните съседи към по-общата перспектива на „научно наблюдение“: ако сумата на всички 9 клетки е равна на 3, то състоянието на централната клетка в следващото поколение ще е „живот“ (1), без да се взима предвид моментното ѝ състояние. Ако сумата е равна на 4, клетката не променя състоянието си. При всяка друга стойност на сумата, състоянието ѝ става „смърт“ (0).

При нужда от пестене на памет, вторият двумерен масив може да бъде заменен с 3 линейни едномерни буферни масива – в първия буфер се записва резултата от изчислението на един ред от двумерния масив, след това във втория буфер се записва резултата от изчисленията на следващия ред, като на предходния ред се презаписва съдържанието на първия буфер, който вече е свободен да приеме резултатите от изчисленията на третия ред от масива и т.н. до края. В случай, че се ползва тороидален масив, е нужен и трети буфер, който да пази началното състояние на първия ред, докато не се изчисли последния ред.

Alt text
Снимка на puffer-type breeder (червени), който оставя glider guns (зелени) по пътя си, които на свой ред създават gliders (сини). (animation)

По принцип полето, върху което се разпростира играта „Живот“ е безкрайно, но компютрите имат крайна големина памет. Това може да породи проблем, когато се итерира около границите на масива. Програмистите използват няколко стратегии за справяне с този проблем. Най-простата стратегия е да се допусне, че клетките извън масива са мъртви (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 генерира четири много близки приближения на триъгълника на Sierpiński, когато се прилага за една-единствена жива клетка. Триъгълникът на Sierpiński също може да се наблюдава в „Играта на живота“ на Конуей, чрез изследване на дългосрочния растеж на дълга едноклетъчна-дебела линия на живи клетки, както и в Highlife, Seeds (B2/S), и правилото на Волфрам (Wolfram's Rule 90).

Имиграцията е модификатор, който е много подобен на „Играта на живота“ на Конуей, с изключение на това, че има две „живи“ състояния (често изразени в два различни цвята). Всеки път, когато се роди нова клетка, тя приема „живо“ състояние, която е най-голямата от трите клетки, които са се родили. Тази функция може да се използва, за да се разгледа взаимодействието между космически кораби и други "обекти" в рамките на играта. Друг подобен модификатор, наречен QuadLife, включва 4 различни ON състояния. Когато се роди нова клетка от 3 различни ON съседни клетки, тя приема четвъртата стойност. Друг случай като имиграцията, приема преобладаващата стойност. С изключение на модификаторите сред живите клетки, два от тези модификатори се държат по същия начин като живите.

Външни препратки[редактиране | редактиране на кода]

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Conway's Game of Life“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.