Probléma egy angyalról és egy ördögről

Az angyal és az ördög probléma egy játékelméleti probléma, amelyet Conway javasolt 1982-ben. [1] .

Megfogalmazás

Játékszabályok

Két játékos játszik , akiket angyalnak és ördögnek hívnak. A játék egy végtelen sakktáblán zajlik . Az angyalnak van k "ereje" (ez egy természetes szám 1 vagy több), amelyet a játék kezdete előtt állítanak be. A játék elején az angyal az egyik cellára áll. Az angyal minden mozdulattal egy másik szabad cellába lép, ahová a király maximum k lépésével lehet eljutni. Az ördög viszont blokkolhat egy sejtet, amelyben nincs angyal. Az angyal átugorhat az elzárt helyeken, de nem tud leszállni rájuk. Az ördög győz, ha az angyal nem tud mozdulni. Az angyal győz, ha a végtelenségig él.

Kérdés

Nyerhet-e egy angyal, ha van elég ereje?

Pontosabban, meg kell találni a nyerő stratégiát az egyik játékos számára. Ha az ördög nyerni tud, azt véges számú mozdulattal kell megtennie. Ha az ördög nem tud nyerni, akkor az angyal mindig megtehet valamit, hogy elkerülje a veszteséget, és a nyerő stratégia az, hogy egy ilyen lépést választ. Ez azt jelenti, hogy az angyal megnyeréséhez vezető lépések halmaza az összes lépés halmazán zárva van a természetes topológiában , és az ilyen játékokról ismert, hogy determinisztikusak .

Történelem

A problémát először 1982-ben publikálta a Winning Ways -ben Berlekamp , Conway és Guy [2] "The Angel and the Square Eater" címmel.

Conway meghirdette a jutalmat a probléma általános megoldásáért (100 dollár egy nyerő stratégia egy kellő erősségű angyalért és 1000 dollár azért, hogy bebizonyítsa, hogy az ördög az angyal erejétől függetlenül is nyerhet).

A kétdimenziós eset esetében íme néhány korai eredmény:

Ha az angyal ereje 1, akkor az ördögnek van nyerő stratégiája. (Conway szerint ez az eredmény Alvin Berlekampnak köszönhető ).
Ha az angyal soha nem csökkenti a koordinátákat, akkor az ördögnek van nyerő stratégiája (Conway, 1982).
Ha az angyal mindig növeli a távolságot a központi sejttől, akkor az ördög nyerő stratégiával rendelkezik (Conway, 1996).

Egy háromdimenziós tábla esetében bebizonyosodott, hogy:

Ha az angyal mindig növeli a távolságot a központi tértől, és az ördög ugyanazon a síkon tud játszani, akkor az angyalnak van nyerő stratégiája.
Ha az angyal mindig növeli a koordinátákat, és az ördög csak két síkon tud játszani, akkor az angyalnak van nyerő stratégiája.
Egy angyal nyerő stratégiával rendelkezik, ha ereje 13 vagy nagyobb.
Ha végtelen számú ördög van, és mindenki távol játszik , akkor az angyal akkor is nyerhet, ha elég nagy ereje van. (A "távolban való játék " alatt azt a korlátozást értjük, hogy az ördög nem játszhat kisebb távolságban a kezdőmezőtől.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Végül 2006-ban (röviddel Peter Winkler matematikai rejtvényeinek megjelenése után, amely ezt a problémát népszerűvé tette) négy független és szinte azonos bizonyítékot mutattak be arra vonatkozóan, hogy egy angyalnak van nyerő stratégiája egy lapos táblán. Bowditch [3] bizonyítása a hatalom hatalom angyalával 2. erővel működika [4]bizonyításaAndré MatebizonyításaKlosterOddvarmíg,angyalával Bowditch és Mate bizonyítékait a Combinatorics, Probability and Computing (szerkesztők : Bolobas és Leader ) publikálták. Kloster bizonyítása az Theoretical Computer Science című folyóiratban jelent meg .

Bizonyítékvázlatok

Proof "Guard"

A bizonyíték arra, hogy a játék 3D-s változata egy kellő erejű angyallal nyerő stratégiával rendelkezik, „őröket” használ. Bármilyen méretű kockához van egy őr, aki vigyáz a kockára. Az őr minden lépés előtt eldönti, hogy az általa figyelt kocka veszélyes, biztonságos vagy majdnem biztonságos. A „biztonságos” és a „majdnem biztonságos” definícióit tisztázni kell – ez a döntés pusztán a kocka blokkolópontjainak sűrűségén és a kocka méretén alapul.

Ha az angyal lépése nincs előre meghatározott, egyszerűen feljebb lépünk. Ha néhány kocka, amelyet az angyal hagy, biztonságos, akkor a legnagyobb kocka védője arra utasítja, hogy az angyal a kocka egyik lapján keresztül lépjen ki a kockából. Ha az őrt arra utasítják, hogy kísérje ki az angyalt egy bizonyos szélig, az őr ezt úgy teszi meg, hogy utat épít a biztonságos alkockákon keresztül. Az ezekben a kockákban lévő őrök azt az utasítást kapják, hogy kísérjék az angyalt az alkockákon keresztül. Az angyal útja egy alkockában nincs meghatározva, amíg az angyal be nem lép abba a kockába. Ennek ellenére az út nagyjából meg van határozva. A stratégia biztosítja, hogy az ördög ne válasszon ki egy helyet az angyal útján elég messze ahhoz, hogy elzárja azt.

Bizonyítható, hogy a stratégia működik, mert az az idő, ami alatt az ördög az angyal útjában lévő biztonságos kockát veszélyessé változtatja, hosszabb, mint amennyi idő alatt az angyal eléri a kockát.

Ezt a bizonyítékot Lider [ és Bolobas publikálta 2006-ban [5] . Hasonló bizonyítékot publikált Martin Kutz 2005-ben [6] [7] .

Proof of Mate for angel with angel with 2

Mate [4] bemutatott egy tapintatos ördögöt , aki soha nem pusztított el egy angyal által korábban elfoglalt sejtet. Ha egy angyal egy tapintatos ördög ellen játszik, akkor feltételezhető, hogy az ördög nyer, ha korlátozott területre korlátozza az angyal mozgását (ellenkező esetben az angyal csak két mezőn ugrik előre-hátra, és soha nem veszít!).

Mate egy határozott nyerési stratégiát adott egy angyalnak a tapintatos ördög ellen, és megmutatta, hogy ha egy angyal nyer egy tapintatos ördög ellen, akkor az angyal nyer egy igazi ördög ellen.

Az első részben az angyal úgy győzi le a tapintatos ördögöt, hogy feltételezi, hogy a teljes bal félsík elpusztult (az ördög által elpusztított összes sejten kívül), és az elpusztult sejteket egy labirintus falaiként kezeli, ami a "bal kéz" szabálya szerint megkerülve. Vagyis az angyal a bal kezét a labirintus falán tartja, és végigmegy a falon. Bizonyítható, hogy egy tapintatos ördög nem tud elfogni egy ilyen stratégiát alkalmazó angyalt.

A második részt ellentmondás bizonyítja, ezért Mate bizonyítása nem ad azonnali nyerő stratégiát az igazi ördög ellen. Mate azonban megjegyzi, hogy ez a bizonyíték elvileg adaptálható egy ilyen stratégia eléréséhez.

Bowditch bizonyítéka egy erős angyalra 4

Bodwich meghatározza [3] a nyitómeccs egy változatát (2. játék), a következő szabálymódosításokkal:

Az angyal visszatérhet bármely térre, ahol már járt, még akkor is, ha az ördög megpróbálta elzárni azt.
A k-ördögnek k-szer kell meglátogatnia a cellát, mielőtt blokkolná.
Az angyal egy sejtet mozgat fel/le/balra/jobbra.
A nyeréshez az angyalnak az alább leírt körpályát kell követnie.

A körkörös útvonal egy félvégtelen ív (egy önállóan diszjunkt útvonal kezdőponttal, de nincs végpont), és páronként diszjunkt hurkok a következő tulajdonságokkal: $\pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$ ${\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i))$ ${\gamma _{i))$

$\forall i:|\gamma _{i}|\leq i$ hol az i-edik hurok hossza. $|\gamma _{i}|$

(A teljes konkrétság érdekében a végponton kell kezdődnie és véget érnie , és a kezdőpontban kell végződnie .) ${\displaystyle \gamma _{i))$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich a játék egy változatát (1. játék) javasolja 2-es és 3-as változtatásokkal, valamint 5-ördöggel. Megmutatta, hogy ebben a játékban a nyerő stratégia megadja az eredeti játék nyerő stratégiáját az erő angyalának 4. Megmutatta azt is, hogy egy 5-ös ördög ellen játszó angyal (2. játék) egy meglehetősen egyszerű algoritmussal nyerhet.

Bodwich kijelenti, hogy egy 4 erősségű angyal meg tudja nyerni a játék eredeti verzióját, ha elképzel egy fantomangyalt, aki egy ötös ördög ellen játszik a 2. játékban.

Az angyal követi a fantomangyal lehetséges útját, de elkerüli a hurkokat. Mivel az ösvény egy félig végtelen ív, az angyal nem tér vissza egyetlen olyan mezőre sem, amelyet már meglátogatott, így az útvonal lesz az eredeti játék nyerőútja. $\sigma$

Változatok és általánosítások

A 3D-s térben, mivel az angyal mindig növeli az y -koordinátát, és az ördög három síkra korlátozódik, nem ismert, hogy az ördögnek van-e nyerő stratégiája.

Lásd még

Killer driver probléma , egy másik matematikai játék, amelyben egy lassú, de agilis játékos megpróbál lehagyni egy gyorsabb, de kevésbé agilis ellenséget.
Garantált keresés elmélete

Jegyzetek

↑ John H. Conway. Esélytelen játékok / Richard Nowakowski. - MSRI Publications, 1996. - V. 29. - S. 3-12. Az angyalprobléma archiválva : 2020. szeptember 29. a Wayback Machine -nél
↑ Elwyn R. Berlekamp , John H. Conway és Richard K. Guy , Nyertes utak matematikai színdarabjaihoz, 2. kötet: Games in Particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Az angyaljáték a repülőben , Combin. Valószínűleg. Comput. 16(3):345-362, 2007.
↑ 1 2 Máthé András, A hatalom angyala 2 nyer , Combin. Valószínűleg. Comput. 16(3):363-374, 2007
↑ Bollobás B. és I. Vezető, Az angyal és az ördög három dimenzióban. Journal of Combinatorial Theory. sorozat A. köt. 113. (2006), 1. sz. 1, pp. 176-184
↑ Martin Kutz, Conway angyala három dimenzióban, elmélet. Összeg. sci. 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Position Games, and Digraph Roots, PhD értekezés archiválva 2007. december 11-én a Wayback Machine FU Berlinben, 2004