Ongelma enkelistä ja paholaisesta

Enkeli ja paholainen -ongelma on peliteorian ongelma, jonka Conway ehdotti vuonna 1982. [1] .

Sanamuoto

Pelin säännöt

Kaksi pelaajaa , joita kutsutaan enkeliksi ja paholaiseksi, pelaa. Peli tapahtuu loputtomalla shakkilaudalla . Enkelillä on "voima" k (se on luonnollinen luku 1 tai enemmän), joka asetetaan ennen pelin alkua. Pelin alussa enkeli seisoo yhdellä soluista. Jokaisella liikkeellä enkeli siirtyy toiseen vapaaseen soluun, johon pääsee korkeintaan k kuninkaan siirrolla. Paholainen puolestaan voi estää yhden solun, jossa ei ole enkeliä. Enkeli voi hypätä tukkeutuneiden tilojen yli, mutta ei voi laskeutua niiden päälle. Paholainen voittaa, jos enkeli ei voi liikkua. Enkeli voittaa, jos se elää loputtomasti.

Kysymys

Voiko enkeli voittaa, jos sillä on tarpeeksi voimaa?

Tarkemmin sanottuna on välttämätöntä löytää voittostrategia yhdelle pelaajista. Jos paholainen voi voittaa, hänen on tehtävä se rajallisella määrällä liikkeitä. Jos paholainen ei voi voittaa, enkeli voi aina ryhtyä toimiin välttääkseen häviämisen, ja voittostrategia on valita tällainen liike. Toisin sanoen enkelin voittoon johtava siirtosarja on suljettu luonnollisessa topologiassa kaikkien liikkeiden joukossa, ja tällaisten pelien tiedetään olevan deterministisiä .

Historia

Ongelma julkaistiin ensimmäisen kerran vuonna 1982 Winning Ways -julkaisussa Berlekamp , Conway ja Guy [2] otsikolla "The Angel and the Square Eater".

Conway julisti palkinnon ongelman yleisestä ratkaisusta (100 dollaria riittävän vahvan enkelin voittostrategiasta ja 1 000 dollaria todisteesta, että paholainen voi voittaa enkelin vahvuudesta riippumatta).

Kaksiulotteisen tapauksen osalta tässä on joitain varhaisia tuloksia:

Jos enkelin vahvuus on 1, niin paholaisella on voittostrategia. (Conwayn mukaan tämä tulos johtuu Alvin Berlekampista ).
Jos enkeli ei koskaan pienennä koordinaatteja, niin paholaisella on voittostrategia (Conway, 1982).
Jos enkeli lisää aina etäisyyttä keskussolusta, niin paholaisella on voittostrategia (Conway, 1996).

Kolmiulotteisen levyn osalta on todistettu, että:

Jos enkeli lisää aina etäisyyttä keskusaukiolta ja paholainen voi pelata samalla tasolla, enkelillä on voittostrategia.
Jos enkeli kasvattaa aina koordinaatteja ja paholainen voi pelata vain kahdella tasolla, niin enkelillä on voittostrategia.
Enkelillä on voittostrategia, jos sen voima on 13 tai suurempi.
Jos paholaisia on ääretön määrä ja kaikki pelaavat etäisyyksillä , enkeli voi silti voittaa, jos sillä on tarpeeksi suuri voima. ("Etäpelillä " tarkoitamme rajoitusta, että paholainen ei saa pelata pienemmällä etäisyydellä aloitusruudusta.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Lopulta vuonna 2006 (pian sen jälkeen, kun Peter Winklerin matemaattiset palapelit julkaistiin , mikä teki tästä ongelmasta suositun), esitettiin neljä riippumatonta ja melkein identtistä todistetta siitä, että enkelillä on voittostrategia tasaisella laudalla. Bowditchin [3] todistus toimii toimivat voimaenkelin 2.4][todistusAndré MatentodistusKlosterinOddvarkun taas,voimaenkelin Bowditchin ja Maten todisteet julkaistiin Combinatoricsissa, Probability and Computingissa (toimittajat Bolobas ja Leader ). Klosterin todistus on julkaistu Theoretical Computer Science -lehdessä .

Todistusluonnokset

Todiste "Vartija"

Todiste siitä, että pelin 3D-versiossa, jossa on riittävän vahva enkeli, on voittostrategia, käyttää "vartijoita". Minkä tahansa kokoiselle kuutiolle on vartija, joka valvoo kuutiota. Ennen jokaista liikettä vartija päättää, onko hänen katsomansa kuutio vaarallinen, turvallinen vai melkein turvallinen. "Turvallinen" ja "melkein turvallinen" määritelmiä tulisi selventää - tämä päätös perustuu puhtaasti kuution estopisteiden tiheyteen ja kuution kokoon.

Jos enkelin liikettä ei ole ennalta määrätty, siirrymme yksinkertaisesti ylöspäin. Jos jotkin enkelin jättämät kuutiot ovat turvallisia, suurimman kuution vartijaa kehotetaan varmistamaan, että enkeli poistuu kuutiosta kuution toisen pinnan kautta. Jos vartijaa kehotetaan saattamaan enkeli ulos tiettyyn reunaan, vartija tekee sen rakentamalla polun turvallisten alakuutioiden läpi. Näissä kuutioissa olevia vartijoita ohjataan saattamaan enkeli sen alakuutioiden läpi. Alakuutiossa olevan enkelin polkua ei määritellä ennen kuin enkeli tulee kuutioon. Siitä huolimatta polku on karkeasti määritelty. Strategia varmistaa, että paholainen ei voi valita paikkaa enkelin tieltä riittävän kauas estääkseen sen.

Voidaan todistaa, että strategia toimii, koska aika, joka paholaisella kestää muuttaa enkelin tiellä oleva turvallinen kuutio vaaralliseksi, on pidempi kuin aika, joka kuluu enkelin saavuttamiseen kuutioon.

Tämän todisteen julkaisivat Lider [ ja Bolobas vuonna 2006 [5] . Martin Kutz julkaisi samanlaisen todisteen vuonna 2005 [6] [7] .

Proof of Mate enkelille, jolla on voimaa 2

Mate [4] esitteli tahdikkuuden paholaisen , joka ei koskaan tuhonnut solua, jota enkeli oli aiemmin miehittänyt. Jos enkeli pelaa tahdikasta paholaista vastaan, paholaisen oletetaan voittavan, jos se rajoittaa enkelin liikkeen rajoitetulle alueelle (muuten enkeli vain hyppää edestakaisin kahdessa ruudussa eikä koskaan häviä!).

Mate esitti selkeän voittostrategian enkelille tahdikkaista paholaista vastaan ja osoitti, että jos enkeli voittaa tahdikkuutta vastaan, niin enkeli voittaa todellista paholaista vastaan.

Ensimmäisessä osassa enkeli voittaa tahdikkuuden paholaisen olettamalla, että koko vasen puolitaso tuhoutuu (kaikkien paholaisen tuhoamien solujen lisäksi), ja kohtelee tuhoutuneita soluja labyrintin seininä, mikä on ohitetaan "vasemman käden" säännön mukaan. Eli enkeli pitää vasenta kättään labyrintin seinällä ja kävelee seinää pitkin. Voidaan todistaa, että tahdikas paholainen ei voi vangita enkeliä, joka omaksuu tällaisen strategian.

Toinen osa on todistettu ristiriitaisesti, ja siksi Maten todiste ei anna välitöntä voittostrategiaa todellista paholaista vastaan. Mate kuitenkin huomauttaa, että tätä todistetta voidaan periaatteessa mukauttaa tällaisen strategian saamiseksi.

Bowditchin todiste voimakkaasta enkelistä 4

Bodwich määrittelee [3] avauspelin muunnelman (peli 2), jossa on seuraavat sääntömuutokset:

Enkeli voi palata mille tahansa aukiolle, jossa se on jo käynyt, vaikka paholainen olisi yrittänyt estää sen.
K-paholaisen täytyy käydä solussa k kertaa ennen kuin se estetään.
Enkeli siirtää yhden solun ylös/alas/vasemmalle/oikealle.
Voittaakseen enkelin on seurattava alla kuvattua ympyräreittiä.

Ympyrämäinen polku on polku, jossa on puoliääretön kaari (itsehajottava polku, jolla on aloituspiste, mutta ei päätepistettä) ja ne ovat pareittain hajallaan olevia silmukoita, joilla on seuraavat ominaisuudet: $\pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$ ${\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i))$ ${\näyttötyyli {\gamma _{i))}$

$\forall i:|\gamma _{i}|\leq i$ missä on i:nnen silmukan pituus. $|\gamma _{i}|$

(Ollakseen täysin täsmällinen , täytyy alkaa ja päättyä loppupisteessä ja sen on päätyttävä aloituspisteeseen .) ${\näyttötyyli \gamma _{i))$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich ehdottaa pelin muunnelmaa (peli 1), jossa on muutoksia 2 ja 3 sekä 5-paholainen. Hän osoitti, että tämän pelin voittostrategia antaisi alkuperäisen pelin voittostrategian voiman enkelille 4. Hän osoitti myös, että enkeli, joka pelaa 5-paholaista vastaan (peli 2), voi saavuttaa voiton käyttämällä melko yksinkertaista algoritmia.

Bodwich toteaa, että 4-voimainen enkeli voi voittaa pelin alkuperäisen version kuvittelemalla haamuenkelin pelaavan 5-paholaista vastaan pelissä 2.

Enkeli seuraa haamuenkelin mahdollista polkua, mutta välttää silmukoita. Koska polku on puoliksi ääretön kaari, enkeli ei palaa mihinkään neliöön, jossa se on jo käynyt, ja siksi polku on alkuperäisen pelin voittopolku. $\sigma$

Muunnelmia ja yleistyksiä

3D-avaruudessa, koska enkeli kasvattaa aina y -koordinaattia ja paholainen on rajoitettu kolmeen tasoon, ei tiedetä, onko paholaisella voittostrategia.

Katso myös

Tappajakuljettajan ongelma , toinen matemaattinen peli, jossa hidas mutta ketterä pelaaja yrittää päihittää nopeamman mutta vähemmän ketterän vihollisen.
Taatun haun teoria

Muistiinpanot

↑ John H. Conway. Pelit ilman mahdollisuutta / Richard Nowakowski. - MSRI Publications, 1996. - V. 29. - S. 3-12. Enkeliongelma Arkistoitu 29. syyskuuta 2020 Wayback Machinessa
↑ Elwyn R. Berlekamp , John H. Conway ja Richard K. Guy , Winning Ways for your matematical plays, osa 2: Games in Particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Enkelipeli lentokoneessa , Yhdistä. Todennäköisesti. Comput. 16(3):345-362, 2007.
↑ 1 2 András Máthé, Voiman enkeli 2 voittaa , Yhdistä. Todennäköisesti. Comput. 16(3):363-374, 2007
↑ B. Bollobás ja I. Johtaja, Enkeli ja paholainen kolmessa ulottuvuudessa. Journal of Combinatorial Theory. Sarja A. voi. 113 (2006), nro. 1, s. 176-184
↑ Martin Kutz, Conwayn enkeli kolmessa ulottuvuudessa, teoria. Comp. sci. 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, PhD Thesis Arkistoitu 11. joulukuuta 2007 Wayback Machine FU Berlinissä, 2004