Kwestia anioła

Obszar z niebieską kropką pokazuje, gdzie może dotrzeć anioł mocy 3

Problem anioła jest zagadnieniem w kombinatorycznej teorii gier, zaproponowanym przez Johna Hortona Conwaya . Ta gra jest powszechnie nazywana aniołów i diabłów . W grze bierze udział dwóch graczy zwanych aniołem i diabłem. Gra się na nieskończonej szachownicy (lub równoważnie punktów siatki 2D ). Anioł ma moc k ( liczbę naturalną 1 lub wyższą), określoną przed rozpoczęciem gry. Plansza zaczyna się pusta z aniołem na jednym polu. W każdej turze anioł przeskakuje na inne puste pole, do którego można dotrzeć co najwyżej k posunięciami króla szachowego , czyli odległość od pola startowego wynosi co najwyżej k w normie nieskończoności . Diabeł w swojej kolejce może dodać bloczek na dowolne pole, na którym nie ma anioła. Anioł może przeskakiwać nad zablokowanymi polami, ale nie może na nich wylądować. Diabeł wygrywa, jeśli anioł nie może się ruszyć. Anioł wygrywa, przeżywając w nieskończoność.

Problem anioła polega na tym, czy anioł z wystarczająco dużą mocą może wygrać?

Musi istnieć zwycięska strategia dla jednego z graczy. Jeśli diabeł może wymusić wygraną, to może to zrobić w skończonej liczbie ruchów. Jeśli diabeł nie może wymusić wygranej, anioł zawsze może podjąć działanie, aby uniknąć przegranej, a zwycięską strategią jest zawsze wybranie takiego ruchu. Mówiąc bardziej abstrakcyjnie, „zbiór wypłat” (tj. zbiór wszystkich gier, w których anioł wygrywa) jest zbiorem zamkniętym ( w topologii naturalnej na zbiorze wszystkich gier) i wiadomo, że takie gry są zdeterminowane . Oczywiście w dowolnej grze nieskończonej, jeśli gracz 2 nie ma zwycięskiej strategii, gracz 1 zawsze może wybrać ruch, który prowadzi do pozycji, w której gracz 2 nie ma zwycięskiej strategii, ale w niektórych grach po prostu granie w nieskończoność nie przyznaje wygranej graczowi 1, więc mogą istnieć nieokreślone gry.

Conway wyznaczył nagrodę za ogólne rozwiązanie tego problemu (100 dolarów za zwycięską strategię dla anioła o odpowiednio dużej mocy i 1000 dolarów za dowód, że diabeł może wygrać niezależnie od mocy anioła). Najpierw dokonano postępu w wyższych wymiarach. Pod koniec 2006 roku pierwotny problem został rozwiązany, gdy pojawiły się niezależne dowody pokazujące, że anioł może wygrać. Bowditch udowodnił, że 4-anioł (czyli anioł o mocy k = 4) może wygrać, a Máthé i Kloster udowodnili, że 2-anioł może wygrać.

Podstawowe strategie i dlaczego nie działają

Wiele intuicyjnych strategii ucieczki anioła można pokonać. Na przykład, jeśli anioł próbuje uciec z pobliskich bloków, diabeł może zrobić gigantyczną podkowę daleko na północy, a następnie wciągnąć anioła w pułapkę, wielokrotnie zjadając kwadrat na południe od anioła. Jeśli anioł próbuje uniknąć pułapek ustawionych bardzo daleko, diabeł może zrobić małą podkowę na północy, a następnie wciągnąć anioła w pułapkę, zjadając kwadraty daleko na południu.

Wydaje się, że anioł powinien być w stanie wygrać, poruszając się tak szybko, jak to możliwe, w połączeniu z okazjonalnymi zygzakami na wschód lub zachód, aby uniknąć oczywistych pułapek. Tę strategię można pokonać, zauważając, że możliwe przyszłe pozycje tego anioła leżą w stożku, a diabeł może w pewien sposób zbudować ścianę w poprzek stożka w oddali, tak że kiedy anioł w końcu dotrze na odległość, diabeł ma stworzył nieprzeniknioną ścianę, a ponieważ anioł nalega na przejście na północ, anioł nie może w ogóle się ruszyć.

Historia

Problem został po raz pierwszy opublikowany w 1982 roku w książce Winning Ways autorstwa Berlekampa, Conwaya i Guya pod tytułem „anioł i zjadacz kwadratów”. W dwóch wymiarach niektóre wczesne wyniki cząstkowe obejmowały:

Jeśli anioł ma moc 1, diabeł ma zwycięską strategię (Conway, 1982). (Według Conwaya wynik ten jest w rzeczywistości zasługą Berlekampa .) Można to przeczytać w sekcji 1.1 artykułu Kutza.
Jeśli anioł nigdy nie zmniejsza swojej współrzędnej y, diabeł ma zwycięską strategię (Conway, 1982).
Jeśli anioł zawsze zwiększa odległość od źródła, diabeł ma zwycięską strategię (Conway, 1996).

W trzech wymiarach wykazano, że: ^{[ potrzebne źródło ]}

Jeśli anioł zawsze zwiększa swoją współrzędną y, a diabeł może grać tylko w jednej płaszczyźnie, to anioł ma zwycięską strategię.
Jeśli anioł zawsze zwiększa swoją współrzędną y, a diabeł może grać tylko na dwóch płaszczyznach, to anioł ma zwycięską strategię.
Anioł ma zwycięską strategię, jeśli ma siłę 13 lub więcej.
Jeśli mamy nieskończoną liczbę diabłów, z których $nadal$ wygrać ma wystarczająco dużą moc. (Przez „granie na odległość $rozumiemy, że$ diabeł nie może grać w tej odległości od początku). ^{[ wątpliwe – dyskutuj ]}

Wreszcie, w 2006 roku (niedługo po opublikowaniu książki Petera Winklera Mathematical Puzzles , która pomogła nagłośnić problem aniołów) pojawiły się cztery niezależne i niemal równoczesne dowody na to, że anioł ma zwycięską strategię w dwóch wymiarach. Dowód Briana Bowditcha działa dla 4-anioła, podczas gdy dowód Oddvara Klostera i dowód Andrása Máthé działają dla 2-anioła. Ponadto Péter Gács ma rzekomy dowód , który wymaga znacznie silniejszego anioła; szczegóły są dość złożone i nie zostały zweryfikowane przez czasopismo pod kątem dokładności. Dowody Bowditcha i Máthé zostały opublikowane w Combinatorics, Probability and Computing . Dowód Klostera został opublikowany w Theoretical Computer Science .

Dalsze nierozwiązane kwestie

W 3D, biorąc pod uwagę, że anioł zawsze zwiększa swoją współrzędną y , a diabeł jest ograniczony do trzech płaszczyzn, nie wiadomo, czy diabeł ma zwycięską strategię.

Szkice dowodowe

Dowód Klostera na 2 anioły

Oddvar Kloster odkrył konstruktywny algorytm do rozwiązania problemu z 2-aniołem. Ten algorytm jest dość prosty, a także optymalny, ponieważ, jak wspomniano powyżej, diabeł ma zwycięską strategię przeciwko 1-aniołowi.

Zaczynamy od narysowania pionowej linii bezpośrednio na lewo od pozycji początkowej anioła, w dół do $infty}$ $Displaystyle y = -$ i do góry . Ta linia reprezentuje ścieżkę, którą pójdzie anioł, która będzie aktualizowana po każdym ruchu diabła, i dzieli pola planszy na „zestaw lewy” i „zestaw prawy”. Gdy pole stanie się częścią lewego zestawu, pozostanie nim do końca gry, a anioł nie wykona żadnych przyszłych ruchów na żadne z tych pól. Za każdym razem, gdy diabeł blokuje nowe pole, przeszukujemy wszystkie możliwe modyfikacje ścieżki, tak aby przenieść jedno lub więcej pól z prawego zestawu, które diabeł zablokował, do lewego zestawu. Zrobimy to tylko wtedy, gdy ścieżka zwiększy się o nie więcej niż dwukrotność liczby zablokowanych kwadratów przesuniętych do lewego zestawu. Z takich ścieżek kwalifikacyjnych wybieramy taką, która przenosi największą liczbę zablokowanych kwadratów do lewego zestawu. Następnie anioł robi dwa kroki wzdłuż tej ścieżki, trzymając się ścieżki po lewej stronie, gdy porusza się w kierunku do przodu (więc gdyby diabeł nie blokował kwadratów, anioł podróżowałby na północ w nieskończoność). Zwróć uwagę, że idąc zgodnie z ruchem wskazówek zegara za rogiem, anioł nie poruszy się o jeden krok, ponieważ dwa segmenty stykające się z rogiem mają ten sam kwadrat po swojej prawej stronie.

Dowód 2 aniołów Mathégo

Máthé wprowadza miłego diabła, który nigdy nie niszczy pola, które anioł mógł zająć we wcześniejszej turze. Kiedy anioł gra przeciwko miłemu diabłu, przyznaje się do porażki, jeśli diabeł zdoła ograniczyć go do ograniczonego obszaru planszy (w przeciwnym razie anioł mógłby po prostu skakać tam iz powrotem między dwoma polami i nigdy nie przegrać!). Dowód Máthégo dzieli się na dwie części:

pokazuje, że jeśli anioł wygrywa z miłym diabłem, to anioł wygrywa z prawdziwym diabłem;
podaje wyraźną zwycięską strategię anioła przeciwko miłemu diabłu.

Z grubsza mówiąc, w drugiej części anioł wygrywa z miłym diabłem, udając, że cała lewa półpłaszczyzna jest zniszczona (oprócz pól faktycznie zniszczonych przez miłego diabła), a zniszczone kwadraty traktuje jak ściany labiryntu , którą następnie omija techniką „ręki na ścianie”. Oznacza to, że anioł trzyma lewą rękę na ścianie labiryntu i biegnie wzdłuż ściany. Następnie udowadnia się, że miły diabeł nie może uwięzić anioła, który przyjmuje tę strategię.

Dowód pierwszej części jest sprzeczny, a zatem dowód Máthégo nie daje od razu wyraźnej zwycięskiej strategii przeciwko prawdziwemu diabłu. Jednak Máthé zauważa, że jego dowód można w zasadzie dostosować, aby dać tak wyraźną strategię.

Dowód Bowditcha na 4 anioły

Brian Bowditch definiuje wariant (gra 2) oryginalnej gry z następującymi zmianami zasad:

Anioł może wrócić na dowolne pole, na którym już był, nawet jeśli diabeł próbował go później zablokować.
K-diabeł musi odwiedzić pole k razy, zanim zostanie zablokowany.
Anioł porusza się w górę, w dół, w lewo lub w prawo o jedno pole (ruch księcia).
Aby wygrać, anioł musi wytyczyć okrężną ścieżkę (zdefiniowaną poniżej).

π ${\ Displaystyle \ pi = \ kubek _ {i = 1} ^ {\ infty} (\ sigma _ {i} \ puchar \$ gdzie $\ Displaystyle \ sigma = \ kubek _ {i = 1} ^ {\ infty} \ sigma _ {i}}$ { nie przecinająca się ścieżka z punktem początkowym, ale bez punktu końcowego) i są parami rozłącznymi pętlami o następującej właściwości: ${\ displaystyle {\ gamma _ {i}}}$

${\ Displaystyle \ forall i:|\ gamma _ {i}|\ równoważnik i}$ gdzie ${\ Displaystyle |\ gamma _ {i}|}$ to długość i-tej pętli.

$Displaystyle$ Aby być dobrze zdefiniowanym, zaczynać się i kończyć w punkcie końcowym $\ sigma _ {i}}$ i ${\ Displaystyle \ sigma _ {i}} }$ musi kończyć się w punkcie początkowym ${\ Displaystyle \ sigma _ {i + 1}}$ .)

Bowditch rozważa wariant (gra 1) gry ze zmianami 2 i 3 z 5-diabłem. Następnie pokazuje, że zwycięska strategia w tej grze przyniesie zwycięską strategię w naszej oryginalnej grze dla 4-aniołów. Następnie pokazuje, że anioł grający 5-diabłem (gra 2) może osiągnąć zwycięstwo przy użyciu dość prostego algorytmu.

Bowditch twierdzi, że 4-anioł może wygrać oryginalną wersję gry, wyobrażając sobie widmowego anioła grającego 5-diabła w grze 2.

Anioł podąża ścieżką, którą wybrałby upiór, ale unika pętli. Stąd, ponieważ ścieżka $.$ pół-nieskończonym łukiem, anioł nie wraca do żadnego kwadratu, na którym był wcześniej, więc ścieżka jest zwycięską ścieżką nawet w oryginalnej grze

Wersja 3D problemu

Dowód „Strażnika”.

Dowód, który pokazuje, że w trójwymiarowej wersji gry potężny anioł ma zwycięską strategię, wykorzystuje „strażników”. Dla każdej kostki dowolnej wielkości jest strażnik, który czuwa nad tą kostką. Strażnicy przy każdym ruchu decydują, czy kostka, której pilnują, jest niebezpieczna, bezpieczna, czy prawie bezpieczna. Aby to zadziałało, należy wybrać definicje „bezpiecznego” i „prawie bezpiecznego”. Ta decyzja opiera się wyłącznie na gęstości zablokowanych punktów w tym sześcianie i rozmiarze tego sześcianu.

Jeśli anioł nie otrzymuje żadnych poleceń, po prostu porusza się w górę. Jeśli niektóre sześciany zajmowane przez anioła przestają być bezpieczne, wówczas strażnik największego z tych sześcianów ma zaaranżować wyjście anioła przez jedną z granic tego sześcianu. Jeśli strażnik ma wyprowadzić anioła z sześcianu do określonej twarzy, robi to, wyznaczając ścieżkę bezpiecznych podsześcianów. Strażnicy w tych kostkach otrzymują następnie polecenie eskortowania anioła przez odpowiednie podsześciany. Ścieżka anioła w danym podsześcianie nie jest określona, dopóki anioł nie dotrze do tego sześcianu. Nawet wtedy ścieżka jest określona tylko z grubsza. Dzięki temu diabeł nie może po prostu wybrać miejsca na ścieżce wystarczająco daleko i go zablokować.

Można udowodnić, że strategia działa, ponieważ czas potrzebny diabłu do przekształcenia bezpiecznej kostki na ścieżce anioła w niebezpieczną kostkę jest dłuższy niż czas potrzebny aniołowi na dotarcie do tej kostki.

Dowód ten został opublikowany przez Imre Leadera i Bélę Bollobása w 2006 roku. Zasadniczo podobny dowód opublikował Martin Kutz w 2005 roku.

Zobacz też

Zabójczy problem szofera , kolejna gra matematyczna, w której potężny i zwrotny przeciwnik walczy z bardzo zaradnym, ale mniej potężnym wrogiem.

Linki zewnętrzne