Gra życia jest automat komórkowy wyobrazić przez John Horton Conway w 1970 roku i który jest prawdopodobnie najbardziej znany ze wszystkich automatów komórkowych. Pomimo bardzo prostych zasad, gra w życie jest kompletna w Turingu .
Gra w życie jest grą symulacyjną w sensie matematycznym, a nie zabawną. Chociaż nie jest to opisane przez teorię gier , niektórzy opisują ją jako „grę dla zero graczy”.
Gra w życie jest „ grą od podstaw”, ponieważ nie wymaga interwencji gracza podczas jej tworzenia. Jest to automat komórkowy , model, w którym każdy stan mechanicznie prowadzi do następnego stanu na podstawie wcześniej ustalonych reguł.
Gra toczy się na dwuwymiarowej siatce, teoretycznie nieskończonej (ale o skończonej długości i szerokości, w praktyce mniej lub bardziej dużej), której pudełka - zwane „komórkami”, przez analogię do żywych komórek - mogą przyjmować dwa różne stany: „ żywy lub martwy".
Komórka ma osiem sąsiadów, które sąsiadują ze sobą poziomo, pionowo i ukośnie.
Na każdym etapie ewolucja komórki jest całkowicie zdeterminowana stanem jej ośmiu sąsiadów w następujący sposób:
Zatem konfiguracja daje następny obrót konfiguracji, która następnie zwraca pierwszą.
Możemy również sformułować tę ewolucję w następujący sposób:
Następny stan komórki to: (S = 3) LUB (E = 1 AND S = 2).
Z:
Aby przedstawić ten proces, żywe komórki są zwykle przedstawiane na siatce, na tle bezbarwnych martwych komórek.
Diagramy w tym artykule są zgodne z następującymi konwencjami kolorów:
Gra w życie została wymyślona przez Johna Hortona Conwaya w 1970 roku, kiedy był profesorem matematyki na Uniwersytecie Cambridge w Wielkiej Brytanii .
JH Conway jest następnie zainteresowany problemem zaproponowanym przez matematyka Johna Leecha w dziedzinie teorii grup, który dotyczył gęstego ułożenia 24-wymiarowych sfer (znanych jako krata pijawki ). Odkrył kilka niezwykłych właściwości i opublikował wyniki swoich badań w 1968 roku. Conway interesował się także problemem przedstawionym około lat czterdziestych XX wieku przez znanego matematyka Johna von Neumanna .
Ten ostatni próbował znaleźć hipotetyczną maszynę, która mogłaby się reprodukować. Osiąga to, budując model matematyczny ze złożonymi regułami w kartezjańskim układzie współrzędnych. Conway próbuje uprościć pomysły von Neumanna i kończy się to sukcesem. Łącząc swoje poprzednie sukcesy z sieciami Leecha z pracą nad samoreplikującymi się maszynami, dał początek grze życia.
Pierwszy kontakt między ogółem społeczeństwa a tymi pracami miał miejsce w 1970 r. Poprzez publikację w Scientific American w rubryce Martina Gardnera : „ Mathematical Games ”.
Gardner pisze w swoich felietonach, że „gra w życie szybko rozsławiła Conwaya, a także otworzyła nowe pole badań matematycznych - automaty komórkowe. Rzeczywiście, analogie gry w życie z rozwojem, upadkiem i zmianami kolonii mikroorganizmów zbliżają ją do gier symulacyjnych, które naśladują procesy prawdziwego życia. "
Według Gardnera, Conway eksperymentował z kilkoma zestawami reguł dotyczących narodzin, śmierci i przeżycia komórki, zanim wybrał taką, w której populacja komórek nie wybuchła (co często ma miejsce, gdy warunki narodzin są złe. Mniej rygorystyczne), ale gdzie łatwo pojawiają się interesujące struktury . Początkowo John Conway grał go ręcznie, za pomocą siatki odchodzenie deskę i iść kamienie materializować żywych komórek.
Odkryto kilka interesujących konstrukcji, takich jak „szybowiec”, wzór, który przesuwa się po przekątnej co 4 pokolenia, lub różne „działa”, które generują niekończący się przepływ szybowców. Te możliwości zwiększają zainteresowanie grą w życie. Ponadto jego popularność rośnie w momencie, gdy na rynku pojawia się nowa generacja tańszych minikomputerów, co pozwala na testowanie konstrukcji z dnia na dzień, gdy nikt inny ich nie używa.
Pod koniec lat osiemdziesiątych moc komputerów była wystarczająca, aby umożliwić tworzenie wydajnych programów do automatycznego przeszukiwania struktur; w połączeniu z masowym rozwojem Internetu doprowadziły do ożywienia w produkcji ciekawych konstrukcji.
W końcu gra w życie cieszy się większym zainteresowaniem opinii publicznej automatami komórkowymi (m.in. dzięki różnym wygaszaczom ekranu ) niż np. Cała twórczość Edgara Franka Codda , uznanego specjalisty w tej dziedzinie. podręcznik Cellular automata (1968).
Struktury złożone z kilku komórek mogą pojawić się we wszechświecie; najbardziej klasyczne to:
Istnieją również inne konstrukcje, które pojawiają się znacznie rzadziej (jeśli w ogóle w Ogrodach Edenu) w świecie gry:
Te konstrukcje stabilne (w języku angielskim martwa natura ) są zestawy komórek o zatrzymał rozwój sytuacji: są w stanie stabilnym i zmieni więcej dopóki nie pojawi się destrukcyjnych elementów w ich sąsiedztwie. Blok czterech ogniw jest najmniejsza możliwa struktura stabilny.
Niektóre figury stabilizują się w strukturze kwiatowej po serii iteracji porównywalnych z kwitnieniem.
Te oscylatory kolei cyklicznie przez powlekanie kilka różnych form przed powrotem do stanu początkowego. Liczby tego typu są bardzo liczne: obecnie znamy ich setki. „Żaba” to struktura, która powtarza się co dwa pokolenia.
Mogą stosunkowo łatwo pojawić się w świecie gry dzięki spontanicznej ewolucji znacznie prostszych „nasion”.
Te statki - Transport - (angielski kosmiczne , „kosmiczne”) są struktury zdolne, po kilku pokoleń, aby kopie produktami pochodzącymi od siebie, ale przesunięte w uniwersum gry.
Ruch statku, który po n krokach wraca do swojej początkowej konfiguracji, przemieszczany o kwadraty A w poziomie i B w pionie, jest oznaczony jako AB , a jego prędkość (A, B) c / n , gdzie c oznacza „prędkość światła” w grze życia, to znaczy maksymalna prędkość komórki na pokolenie. Istnienie typu A - B naczyń dla każdego A i B wykazano . Wyróżniamy:
Pierwsze ukośne naczynie, zwane Gemini , zostało odkryte przez Andrew J. Wade'a w 2010 roku. Co 33 699 586 pokoleń przesuwa 5 120 komórek w pionie i 1024 komórki w poziomie. Istnieją warianty, w których jego prędkość i okres są różne. To także uniwersalny konstruktor .
Udowadniamy również, że statek typu A - B koniecznie ma okres N ≥ 2 (A + B) , tak że maksymalna prędkość dla statku diagonalnego wynosi (1, 1) c / 4, a dla statku ortogonalnego wynosi ( 2, 2) c / 4 = (1, 1) c / 2.
Znane jest konstruowanie naczyń o tak dużych rozmiarach i okresie, jak jest to pożądane, przy użyciu szeregu elementów. . Szybowiec jest najmniejszy statek w grze życia, który także oferuje najwyższą prędkość o przekątnej statku.
W Matuzalemów są aktywne konstrukcje, które mają czas przed stabilizuje. Niektóre, jak „króliki”, potrzebują ponad 15 000 pokoleń, zanim ustabilizują się w mniej lub bardziej dużej liczbie różnorodnych szczątków.
W puffeurs (angielski puffer „generator dymu”) są konfiguracje które poruszają pozostawiając szlak składa się z gruzu.
W armat lub wyrzutnie lub włóczni statki (w języku angielskim karabiny ) są jakoś oscylatory upuszczenie gruz, zdolne do wytwarzania naczyń w różnych cenach (co 15, 23, 30 lub 360 pokoleń, na przykład, albo w pozornie nieprzewidywalny sposób na pseudo- losowe wyrzutnie statków ).
Struktury takie można tworzyć z rozdmuchiwaczy, które są tak zmodyfikowane, że szczątki pasują do siebie w postaci naczyń. Pierwsze odkryte działo wypuszcza szybowiec co 30 pokoleń.
A Garden of Eden to konfiguracja bez możliwej przeszłości: żadna konfiguracja nie daje następnemu etapowi Garden of Eden.
Demonstracja matematyczna jest oparta na kombinatoryce i można ją znaleźć w szczególności w Winning Ways for your Mathematical Plays , książce opublikowanej w 1982 roku przez Berlekampa , Conwaya i Guya .
W 2010 roku odkryto Gemini, pierwszego uniwersalnego twórcę gry w życie. Ta ogromna liczba to 4217807 komórek z 4220191. Gdy porusza się do przodu, ta liczba tworzy swoją kopię, niszcząc poprzednią. Operacja trwa około 34 milionów pokoleń. Ponieważ Gemini porusza się i nie pozostawia nic za sobą, jest również statkiem. Jest to również pierwszy statek, który porusza się ukośnie, to znaczy ani prostopadle, ani po przekątnej.
Moc i pojemność pamięci komputerów osobistych od momentu przełączenia na 64 bity pozwala na eksplorację bardzo dużych przestrzeni komórkowych w grze życia. Możemy wtedy mieć nadzieję na pojawienie się złożonych struktur o wysokim poziomie samoorganizacji , a nawet estetyki. Stephen Wolfram i inni badali tę ścieżkę. Od lat 80-tych klaun wyłania się w iteracji 110 z dynamiki sieci zapoczątkowanej z początkowego U złożonego z 7 komórek (ogólnie nazywanych „pi heptomino”), tworząc obraz litery U.
Uwaga: klaun jest trenowany do góry nogami. Aby zobaczyć klauna jak na ilustracji, należy narysować odwrócone U.
Szczegóły dotyczące dynamiki sieci: to „U” z 7 komórek (zwane także heptomino pi) ewoluuje w kierunku złożonej i „organicznej” struktury, przechodząc przez bardzo estetyczne formy. Ponadto struktura jest samoodtwarzalna z przesunięciem fazowym, nowa struktura potomna (iteracja 45) w trakcie ewolucji koliduje z wersją struktury macierzystej (iteracja 15). W iteracji 110 otrzymujemy obraz „klauna”. Następnie sieć stabilizuje się na złożonej stabilnej postaci oscylacyjnej.
Wykazano pewne właściwości gry w życie, w szczególności:
Pomimo swojej prostoty, ta gra jest uniwersalną maszyną Turinga : można obliczyć dowolny algorytm pod warunkiem, że siatka jest wystarczająco duża, a warunki początkowe prawidłowe.
Kilka programów komputerowych symuluje grę w życie; w tym Mirek's Cellebration . Te napisane w Javie lub JavaScript można łatwo umieścić na stronie internetowej. Symulatory te nie są jednak zbyt skuteczne, gdy przedstawiają teren za pomocą dwuwymiarowej tabeli i są zadowolone, że komórki ewoluują zgodnie z zasadami Conwaya.
W 1980 roku Bill Gosper wynalazł, a następnie napisał Hashlife , znacznie wydajniejszy algorytm symulacyjny, umożliwiający manipulowanie kilkoma milionami komórek przez miliony pokoleń w krótszym czasie. Algorytm ten opierał się na innym pomyśle: rzeczywiście, jeśli weźmiemy pod uwagę część przestrzeni gry stosunkowo odizolowaną od sąsiadów, można ją „uruchomić” przez określoną liczbę n pokoleń, a następnie zapamiętać wynik . Jeśli konfiguracja początkowa jest odtwarzana w innym miejscu, możemy bezpośrednio „pominąć” n pokoleń w tej części gry. Ten nowy algorytm „obraca” różne części przestrzeni z różnymi prędkościami i pozwala zachować spójność na krawędziach. region w ten sposób zasymulowany. Używał tablicy skrótów do szybkiego przechowywania i pobierania lokalnych konfiguracji.
Gra w życie jest niezwykle wrażliwa na to, jak obliczyć następne pokolenie. Konwencjonalna implementacja jest synchroniczna , to znaczy stan każdej komórki generacji n + 1 jest obliczany ze stanu komórek generacji n . Bersini i Detours pokazali, że interesujące zachowania związane z grą w życie znikają wraz z prawie wszystkimi niezsynchronizowanymi wzorcami aktualizacji (gdzie stany n +1 mogą wpływać na siebie nawzajem, tak jak w prawdziwym życiu). Jednak Nehaniv wykazał, że każde zachowanie synchroniczne może być naśladowane przez asynchroniczne automaty komórkowe i dlatego można znaleźć zachowanie gry w życie bez „zegara globalnego” mierzącego ewolucję pokoleń.
Od 2008 roku wiele programów (z których najbardziej znanym jest Golly ) integruje ten algorytm w interfejsie graficznym. Umożliwiły one tworzenie ogromnych i bardzo pomysłowych konfiguracji oraz śledzenie ich ewolucji, nadając nową dynamikę już bardzo bogatemu studium tego automatu komórkowego.
Od 2012 roku wyszukiwanie w Google hasła „gra w życie Conwaya” powoduje wyświetlenie jajka wielkanocnego : w tle pojawia się interaktywna gra w życie.
Istnieją odmiany gry w życie, oparte na nieco innych zasadach sąsiedztwa, na przykład HighLife lub Day & Night . Ten wariant ma dwa typy komórek, „pozytywne” i „negatywne”, z których każda odpowiada tym samym regułom, w przeciwieństwie do znaku. Dodatnia komórka wymaga sumy 3, aby "narodzić się", a ujemna suma -3. Żywe komórki stają się częścią bilansu otaczających komórek, aby przetrwać lub zaniknąć. Te dwie populacje na ogół nie mogą przetrwać obok siebie.
: dokument używany jako źródło tego artykułu.