Gra życia

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”.

Zasady

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 Gol-blinker1.pngdaje następny obrót konfiguracji, Gol-blinker2.pngktóra następnie zwraca pierwszą.

Możemy również sformułować tę ewolucję w następujący sposób:

Gol-born.png Tak jest w przypadku zielonej komórki w konfiguracji po lewej stronie; Gol-nochange.png W przypadku konfiguracji lewej komórka znajdująca się między dwiema żywymi komórkami pozostaje martwa w następnym etapie; Gol-dead.png Tak jest w przypadku krwinki czerwonej w konfiguracji po lewej stronie.

Następny stan komórki to: (S = 3) LUB (E = 1 AND S = 2).

Z:

Legenda do schematów

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:

Historia

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

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:

Stabilne konstrukcje

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.

Oscylatory

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”.

Statki

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.

Mathusalems

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.

Puffers

W puffeurs (angielski puffer „generator dymu”) są konfiguracje które poruszają pozostawiając szlak składa się z gruzu.

Armaty

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ń.

Ogrody Edenu

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 .

Konstruktorzy uniwersalni

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.

Wymiar i złożoność

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.

Pytania matematyczne

Wykazano pewne właściwości gry w życie, w szczególności:

Obliczalność

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.

Symulacja

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.

Warianty

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.

Bibliografia

Dokument użyty do napisania artykułu : dokument używany jako źródło tego artykułu.

Uwagi i odniesienia

Uwagi

Bibliografia

  1. ( Gardner 1970 ).
  2. ( Codd 1968 ).
  3. (w) „  Lista oscylatorów  ” na LifeWiki
  4. (w) Stworzony statek kosmiczny Adam P. Goucher Oblique Life , Game of Life News, 19 maja 2010 (dostęp: 11 maja 2010).
  5. Thomas Morin, „  Ograniczenie prędkości statków: pokaz  ” ,9 maja 98(dostęp 27 lutego 2019 ) .
  6. Bernard Feltz et al, Emergence and Reductionism: from the Game of Life to Science of Life , w SELF-ORGANIZATION AND EMERGENCE IN LIFE SCIENCES , Springer Netherlands Editor , 2006, ( ISBN  978-1-4020-3916-4 ) ( Drukuj ) 978-1-4020-3917-1 ( online ) [1]
  7. NM Gotts, Emergent fenomena in large sparse random arrays of Conway's Game of Life , in INTERNATIONAL JOURNAL ON SYSTEM SCIENCES, tom 31, wydanie 7 lipiec 2000 , strony 873 - 894 [2]
  8. Jean-Claude Perez, „NOWE DROGI W KIERUNKU SZTUCZNEJ INTELIGENCJI: wielodyscyplinarność, samoorganizacja i sieci neuronowe”, 1988, wyd. Masson Paris (wznowiona w 1989), strony 261-262, ( ISBN  2-225-81815-0 ) .
  9. ER Berlekamp, ​​JH Conway, RK Guy, Winning Ways for Your Mathematical Plays, AK Peters / CRC Press; 2. edycja (30 marca 2004)
  10. http://mirekw.com/ca/download.html
  11. H. Bersini, V. Detours, „Asynchrony Induces Stability in Cellular Automata Based Models”, In Proceedings of the IVth Conference on Artificial Life - MIT Press / Bradford Books, 1994.
  12. CL Nehaniv, „Evolution in Asynchronous Cellular Automata”, Artificial Life VIII , 65-73, MIT Press, 2002.
  13. CL Nehaniv, „Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network”, International Journal of Algebra & Computation , 14 (5-6): 719-739, 2004.
  14. Golly na SourceForge.net .
  15. pl: Lista mistyfikacji Google i pisanek # Search

Zobacz też

Powiązane artykuły

Linki zewnętrzne