Problém s andělem a ďáblem

Problém anděla a ďábla je problém teorie her navržený Conwayem v roce 1982. [1] .

Formulace

Pravidla hry

Hrají dva hráči , kterým se říká anděl a ďábel. Hra se odehrává na nekonečné šachovnici . Anděl má "sílu" k (je to přirozené číslo 1 nebo více), která se nastavuje před začátkem hry. Na začátku hry stojí anděl na jedné z cel. Každým tahem se anděl přesune do další volné buňky, do které lze dosáhnout maximálně k tahů krále. Ďábel zase může blokovat jednu buňku, která nemá anděla. Anděl může skákat přes zablokovaná místa, ale nemůže na ně přistát. Ďábel vyhraje, pokud se anděl nemůže pohnout. Anděl vyhraje, pokud bude žít nekonečně dlouho.

Otázka

Může anděl vyhrát, pokud má dostatek síly?

Přesněji řečeno, je nutné najít vítěznou strategii pro jednoho z hráčů. Pokud může ďábel vyhrát, musí tak učinit v konečném počtu tahů. Pokud ďábel nemůže vyhrát, pak vždy existuje akce, kterou může anděl podniknout, aby se vyhnul prohře, a vítěznou strategií je zvolit takový tah. To znamená, že množina tahů vedoucích k vítězství anděla je uzavřena v přirozené topologii na množině všech tahů a takové hry jsou známé jako deterministické .

Historie

Problém byl poprvé publikován v roce 1982 ve Winning Ways od Berlekampa , Conwaye a Guye [2] pod názvem „The Angel and the Square Eater“.

Conway vypsal odměnu za obecné řešení problému (100 $ za vítěznou strategii pro anděla s dostatečnou silou a 1 000 $ za důkaz, že ďábel může vyhrát bez ohledu na sílu anděla).

Pro dvourozměrný případ jsou zde některé první výsledky:

Pokud je síla anděla 1, pak má ďábel vítěznou strategii. (Podle Conwaye je tento výsledek zásluhou Alvina Berlekampa ).
Pokud anděl nikdy nezmenšuje souřadnice, pak má ďábel vítěznou strategii (Conway, 1982).
Pokud anděl vždy zvětšuje vzdálenost od centrální buňky, pak má ďábel vítěznou strategii (Conway, 1996).

U trojrozměrné desky bylo prokázáno, že:

Pokud anděl vždy zvětšuje vzdálenost od centrálního pole a ďábel může hrát ve stejné rovině, pak má anděl vítěznou strategii.
Pokud anděl vždy zvyšuje souřadnice a ďábel může hrát pouze na dvou rovinách, pak má anděl vítěznou strategii.
Anděl má vítěznou strategii, pokud je jeho síla 13 nebo vyšší.
Pokud existuje nekonečný počet čertů a všichni hrají na dálku , pak může anděl stále vyhrát, pokud má dostatečně velkou sílu. (Hrou na dálku rozumíme omezení, že čert nesmí hrát v menší vzdálenosti od startovního pole.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Nakonec byly v roce 2006 (krátce po vydání knihy Petera Winklera Mathematical Puzzles , která tento problém zpopularizovala) předloženy čtyři nezávislé a téměř totožné důkazy, že anděl má vítěznou strategii na ploché desce. Bowditchův [3] proof pracuje s power pracuje s power angel 2.[4]proof 'sAndré MateKlosteraOddvaradůkazzatímco,angel Důkazy Bowditch a Mate byly publikovány v Combinatorics, Probability and Computing (editoři Bolobas a Leader ). Klosterův důkaz je publikován v Theoretical Computer Science .

Evidenční skici

Důkaz "Stráž"

Důkazem toho, že 3D verze hry s dostatečně silným andělem má vítěznou strategii, jsou „stráže“. Pro jakoukoli kostku jakékoli velikosti existuje strážce, který kostku hlídá. Před každým pohybem se strážný rozhodne, zda je kostka, kterou sleduje, nebezpečná, bezpečná nebo téměř bezpečná. Měly by být vyjasněny definice „bezpečný“ a „téměř bezpečný“ – toto rozhodnutí je založeno čistě na hustotě blokovacích bodů v krychli a velikosti krychle.

Pokud není pohyb anděla předem daný, jednoduše se posuneme nahoru. Pokud jsou některé kostky, které anděl opouští, v bezpečí, pak strážce největší kostky dostane pokyn, aby zajistil, že anděl opustí kostku jednou ze stěn krychle. Pokud je strážce instruována, aby doprovázela anděla směrem ven k určitému okraji, strážce tak učiní vybudováním cesty skrz bezpečné podkostky. Strážci v těchto kostkách jsou instruováni, aby doprovázeli anděla přes jeho podkostky. Cesta anděla v podkrychli není definována, dokud anděl do krychle nevstoupí. I tak je cesta zhruba vymezena. Strategie zajišťuje, že ďábel nemůže vybrat místo v cestě anděla dostatečně daleko, aby ho zablokoval.

Dá se prokázat, že strategie funguje, protože čas, který čertovi trvá, než promění bezpečnou kostku v cestě anděla v nebezpečnou, je delší než doba, za kterou anděl ke kostce dosáhne.

Tento důkaz publikovali Lider [ a Bolobas v roce 2006 [5] . Podobný důkaz publikoval Martin Kutz v roce 2005 [6] [7] .

Proof of Mate pro anděla se silou 2

Mate [4] představil taktního ďábla , který nikdy nezničil celu, kterou předtím obýval anděl. Pokud anděl hraje proti taktnímu čertovi, předpokládá se, že ďábel vyhraje, pokud omezí pohyb anděla na omezenou oblast (jinak anděl jen skáče tam a zpět ve dvou polích a nikdy neprohraje!).

Mate dal explicitní vítěznou strategii pro anděla proti taktnímu ďáblovi a ukázal, že pokud anděl zvítězí nad taktním ďáblem, pak anděl zvítězí nad skutečným ďáblem.

V prvním díle anděl vítězí nad taktním ďáblem tím, že předpokládá, že je zničena celá levá polorovina (kromě všech buněk zničených ďáblem), a se zničenými buňkami zachází jako se stěnami labyrintu, který je obejít podle pravidla "levé ruky". To znamená, že anděl drží levou ruku na stěně labyrintu a prochází po stěně. Dá se prokázat, že taktní ďábel nemůže zajmout anděla, který si osvojí takovou strategii.

Druhá část je dokázána protikladem, a proto Mateův důkaz nedává okamžitou vítěznou strategii proti skutečnému ďáblu. Mate však poznamenává, že tento důkaz lze v zásadě upravit pro získání takové strategie.

Bowditchův důkaz pro anděla se silou 4

Bodwich definuje [3] variantu (hra 2) úvodní hry s následujícími změnami pravidel:

Anděl se může vrátit na kterékoli pole, které již navštívil, i když se ho pak ďábel pokusil zablokovat.
K-ďábel musí buňku navštívit k-krát, než bude zablokována.
Anděl se posune o jednu buňku nahoru/dolů/doleva/doprava.
Aby anděl vyhrál, musí následovat kruhovou cestu popsanou níže.

Kruhová dráha je dráha , kde je polonekonečný oblouk (samostatně nesouvislá dráha s počátečním bodem, ale bez koncového bodu) a jedná se o párové disjunktní smyčky s následujícími vlastnostmi: $\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$ kde je délka i-té smyčky. $|\gamma _{i}|$

(Abychom byli úplně konkrétní , musí začínat a končit v koncovém bodě a končit v počátečním bodě .) ${\displaystyle \gamma _{i))$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich navrhuje variantu (hra 1) hry se změnami 2 a 3 a 5-ďábel. Ukázal, že vítězná strategie v této hře by dala vítězné strategii původní hry pro anděla síly 4. Ukázal také, že anděl hrající proti ďáblovi s 5 (hra 2) může dosáhnout vítězství pomocí poměrně jednoduchého algoritmu.

Bodwich uvádí, že 4-silný anděl může vyhrát původní verzi hry tím, že si představí fantomového anděla hrajícího proti 5-ďáblovi ve hře 2.

Anděl sleduje možnou cestu fantomového anděla, ale vyhýbá se smyčkám. Protože cesta je polonekonečný oblouk, anděl se nevrátí na žádné pole, které již navštívil, a proto bude cesta vítěznou cestou původní hry. $\sigma$

Variace a zobecnění

Ve 3D prostoru, vzhledem k tomu, že anděl vždy zvyšuje souřadnici y a ďábel je omezen na tři roviny, není známo, zda má ďábel vítěznou strategii.

Viz také

Killer driver problem , další matematická hra, ve které se pomalý, ale hbitý hráč pokouší předběhnout rychlejšího, ale méně obratného nepřítele.
Zaručená teorie vyhledávání

Poznámky

↑ John H. Conway. Hry bez šance / Richard Nowakowski. - MSRI Publications, 1996. - V. 29. - S. 3-12. Andělský problém Archivováno 29. září 2020 na Wayback Machine
↑ Elwyn R. Berlekamp , John H. Conway a Richard K. Guy , Vítězné cesty pro vaše matematické hry, svazek 2: Hry zejména , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Andělská hra v letadle , Kombinace. Pravděpodobně. Počítat. 16(3):345-362,2007.
↑ 1 2 András Máthé, Anděl síly 2 vítězí , Kombinace. Pravděpodobně. Počítat. 16(3):363-374,2007
↑ B. Bollobás a I. vůdce, Anděl a ďábel ve třech rozměrech. Journal of Combinatorial Theory. Řada A. sv. 113 (2006), čís. 1, str. 176-184
↑ Martin Kutz, Conwayův anděl ve třech rozměrech, Theoret. Comp. sci. 349(3):443-451,2005.
↑ Martin Kutz, The Angel Problem, Positional Games a Digraph Roots, PhD práce archivována 11. prosince 2007 na Wayback Machine FU Berlín, 2004