Problem om en ängel och en djävul

Ängel- och djävulsproblemet är ett spelteoriskt problem som föreslogs av Conway 1982. [1] .

Formulering

Spelregler

Två spelare spelar , kallade en ängel och en djävul. Spelet utspelar sig på ett oändligt schackbräde . Ängeln har "styrka" k (det är ett naturligt tal 1 eller mer), som sätts innan spelet börjar. I början av spelet står ängeln på en av cellerna. Med varje drag flyttar ängeln till en annan fri cell, som kan nås i maximalt k drag av kungen. Djävulen kan i sin tur blockera en cell som inte har en ängel. Ängeln kan hoppa över blockerade utrymmen, men kan inte landa på dem. Djävulen vinner om ängeln inte kan röra sig. Ängeln vinner om den lever på obestämd tid.

Fråga

Kan en ängel vinna om den har tillräckligt med kraft?

Mer exakt är det nödvändigt att hitta en vinnande strategi för en av spelarna. Om djävulen kan vinna måste han göra det i ett begränsat antal drag. Om djävulen inte kan vinna, så finns det alltid en åtgärd som ängeln kan vidta för att undvika att förlora, och den vinnande strategin är att välja ett sådant drag. Det vill säga, uppsättningen av drag som leder till att ängeln vinner är stängd i den naturliga topologin på uppsättningen av alla drag, och sådana spel är kända för att vara deterministiska .

Historik

Problemet publicerades första gången 1982 i Winning Ways av Berlekamp , Conway och Guy [2] under titeln "The Angel and the Square Eater".

Conway tillkännagav en belöning för den allmänna lösningen av problemet ($100 för en vinnande strategi för en ängel med tillräcklig styrka och $1 000 för att bevisa att djävulen kan vinna oavsett ängelns styrka).

För det tvådimensionella fallet, här är några tidiga resultat:

Om ängelns styrka är 1, så har djävulen en vinnande strategi. (Enligt Conway beror detta resultat på Alvin Berlekamp ).
Om ängeln aldrig minskar koordinaterna, så har djävulen en vinnande strategi (Conway, 1982).
Om ängeln alltid ökar avståndet från den centrala cellen, så har djävulen en vinnande strategi (Conway, 1996).

För en tredimensionell bräda har det bevisats att:

Om ängeln alltid ökar avståndet från det centrala torget och djävulen kan spela på samma plan, så har ängeln en vinnande strategi.
Om ängeln alltid ökar koordinaterna och djävulen bara kan spela på två plan, så har ängeln en vinnande strategi.
En ängel har en vinnande strategi om dess styrka är 13 eller högre.
Om det finns ett oändligt antal djävlar, och alla spelar på avstånd , kan ängeln fortfarande vinna om den har tillräckligt stor kraft. (Med "spela på avstånd " menar vi begränsningen att djävulen inte får spela på ett mindre avstånd från startrutan.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Slutligen, 2006 (kort efter publiceringen av Peter Winklers Mathematical Puzzles , som gjorde detta problem populärt), presenterades fyra oberoende och nästan identiska bevis för att en ängel har en vinnande strategi på en platt bräda. Bowditchs [3] bevis fungerar med arbetar med kraftängel 2.4][bevisAndré MatesbevisKlostersOddvarmedan,kraftängel Bevisen för Bowditch och Mate publicerades i Combinatorics, Probability and Computing (redaktörerna Bolobas och Leader ). Klosters bevis publiceras i Theoretical Computer Science .

Bevisskisser

Bevis "Guard"

Ett bevis som visar att en 3D-version av spelet med en ängel med tillräcklig styrka har en vinnande strategi använder "vakter". För vilken kub som helst av alla storlekar finns det en vakt som vakar över kuben. Före varje drag bestämmer vakten om kuben han tittar på är farlig, säker eller nästan säker. Definitionerna av "säker" och "nästan säker" bör förtydligas - detta beslut baseras enbart på tätheten av blockeringspunkter i kuben och storleken på kuben.

Om ängelns drag inte är förutbestämt flyttar vi helt enkelt upp. Om några kuber som ängeln lämnar är säkra, instrueras vakten för den största kuben att se till att ängeln lämnar kuben genom en av kubens ytor. Om vakten instrueras att eskortera ängeln utåt till en viss kant, gör vakten det genom att bygga en väg genom de säkra subkuberna. Vakterna i dessa kuber instrueras att eskortera ängeln genom dess subkuber. Vägen för en ängel i en subkub definieras inte förrän ängeln går in i den kuben. Trots det är vägen grovt definierad. Strategin säkerställer att djävulen inte kan välja en plats i ängelns väg tillräckligt långt för att blockera den.

Det kan bevisas att strategin fungerar eftersom tiden det tar för djävulen att förvandla en säker kub på ängelns väg till en farlig är längre än tiden det tar för ängeln att nå kuben.

Detta bevis publicerades av Lider [ och Bolobas 2006 [5] . Ett liknande bevis publicerades av Martin Kutz 2005 [6] [7] .

Proof of Mate för en ängel med styrka 2

Mate [4] introducerade en taktfull djävul , som aldrig förstörde en cell som en ängel tidigare hade ockuperat. Om en ängel spelar mot en taktfull djävul, antas djävulen vinna om den begränsar ängelns rörelse till ett begränsat område (annars hoppar ängeln bara fram och tillbaka i två rutor och förlorar aldrig!).

Mate gav en explicit vinnande strategi för en ängel mot en taktfull djävul och visade att om en ängel vinner mot en taktfull djävul, så vinner en ängel mot en riktig djävul.

I den första delen vinner ängeln över den taktfulla djävulen genom att anta att hela det vänstra halvplanet är förstört (utöver alla celler som förstörts av djävulen), och behandla de förstörda cellerna som väggarna i en labyrint, vilket är förbigås enligt "vänsterhandsregeln". Det vill säga, ängeln håller sin vänstra hand på labyrintens vägg och går längs väggen. Det kan bevisas att en taktfull djävul inte kan fånga en ängel som antar en sådan strategi.

Den andra delen är bevisad genom motsägelse, och därför ger Mates bevis inte en omedelbar vinnande strategi mot den riktiga djävulen. Mate noterar dock att detta bevis i princip kan anpassas för att få en sådan strategi.

Bowditchs bevis för en ängel med styrka 4

Bodwich definierar [3] en variant (spel 2) av det inledande spelet med följande regeländringar:

Ängeln kan återvända till vilken ruta den redan har besökt, även om djävulen då försökte blockera den.
K-djävulen måste besöka cellen k gånger innan den blockeras.
Ängeln flyttar en cell upp/ner/vänster/höger.
För att vinna måste ängeln följa den cirkulära vägen som beskrivs nedan.

En cirkulär bana är en bana där det är en halvoändlig båge (en självupplösande bana med en startpunkt men ingen slutpunkt) och är parvis osammanhängande slingor med följande egenskaper: $\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$ var är längden på den i-te slingan. $|\gamma _{i}|$

(För att vara helt specifik , måste börja och sluta vid slutpunkten och måste sluta vid startpunkten .) ${\displaystyle \gamma _{i))$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich föreslår en variant (spel 1) av spelet med ändringar 2 och 3 och 5-devil. Han visade att den vinnande strategin i detta spel skulle ge originalspelets vinnande strategi för en ängel med styrka 4. Han visade också att en ängel som spelar mot en 5-djävul (spel 2) kunde uppnå en vinst med en ganska enkel algoritm.

Bodwich säger att en ängel med 4 styrkor kan vinna den ursprungliga versionen av spelet genom att föreställa sig en fantomängel som spelar mot en 5-djävul i spel 2.

Ängeln följer fantomängelns möjliga väg men undviker slingorna. Eftersom vägen är en semi-oändlig båge, kommer ängeln inte att återvända till någon ruta den redan har besökt, och därför kommer vägen att vara den vinnande vägen i det ursprungliga spelet. $\sigma$

Variationer och generaliseringar

I 3D-rymden, med tanke på att ängeln alltid ökar y -koordinaten och djävulen är begränsad till tre plan, är det okänt om djävulen har en vinnande strategi.

Se även

Killer driver problem , ett annat matematikspel där en långsam men smidig spelare försöker springa undan en snabbare men mindre smidig fiende.
Garanterad sökteori

Anteckningar

↑ John H. Conway. Spel utan chans / Richard Nowakowski. - MSRI Publications, 1996. - V. 29. - S. 3-12. Ängelproblemet Arkiverad 29 september 2020 på Wayback Machine
↑ Elwyn R. Berlekamp , John H. Conway och Richard K. Guy , Winning Ways for your matematiska pjäser, volym 2: Games in Particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Ängelspelet i planet , Combin. Probab. Comput. 16(3):345-362, 2007.
↑ 1 2 András Máthé, Maktens ängel 2 vinner , Kombinera. Probab. Comput. 16(3):363-374, 2007
↑ B. Bollobás och I. Leader, Ängeln och djävulen i tre dimensioner. Journal of Combinatorial Theory. Serie A. vol. 113 (2006), nr. 1, sid. 176-184
↑ Martin Kutz, Conways ängel i tre dimensioner, Teoret. Comp. sci. 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Positional Games och Digraph Roots, doktorsavhandling Arkiverad 11 december 2007 på Wayback Machine FU Berlin, 2004