Ängelproblem

Den blå prickade regionen visar var en ängel med makt 3 kan nå

Ängelproblemet är en fråga inom kombinatorisk spelteori som föreslås av John Horton Conway . Spelet kallas vanligtvis för änglar och djävlar . Spelet spelas av två spelare som kallas ängeln och djävulen. Det spelas på ett oändligt schackbräde (eller motsvarande poängen i ett 2D- gitter ). Ängeln har en makt k (ett naturligt tal 1 eller högre), specificerad innan spelet startar. Tavlan börjar tom med ängeln i en ruta. Vid varje tur hoppar ängeln till en annan tom ruta som kan nås med högst k drag av en schackkung , dvs avståndet från startrutan är högst k i oändlighetsnormen . Djävulen kan i sin tur lägga till ett block på vilken ruta som helst som inte innehåller ängeln. Ängeln kan hoppa över blockerade rutor, men kan inte landa på dem. Djävulen vinner om ängeln inte kan röra sig. Ängeln vinner genom att överleva på obestämd tid.

Ängelproblemet är: kan en ängel med tillräckligt hög kraft vinna?

Det måste finnas en vinnande strategi för en av spelarna. Om djävulen kan tvinga fram en vinst så kan den göra det i ett begränsat antal drag. Om djävulen inte kan tvinga fram en vinst så finns det alltid en åtgärd som ängeln kan vidta för att undvika att förlora och en vinnande strategi för det är alltid att välja ett sådant drag. Mer abstrakt är "utbetalningsuppsättningen" (dvs uppsättningen av alla spel där ängeln vinner) en sluten uppsättning (i den naturliga topologin på uppsättningen av alla spel), och det är känt att sådana spel bestäms . Naturligtvis, för alla oändliga spel, om spelare 2 inte har en vinnande strategi, kan spelare 1 alltid välja ett drag som leder till en position där spelare 2 inte har en vinnande strategi, men i vissa spel, helt enkelt spela för evigt ger ingen vinst till spelare 1, så obestämda spel kan finnas.

Conway erbjöd en belöning för en allmän lösning på detta problem ($100 för en vinnande strategi för en ängel med tillräckligt hög makt, och $1000 för ett bevis på att djävulen kan vinna oavsett ängelns makt). Framsteg gjordes först i högre dimensioner. I slutet av 2006 löstes det ursprungliga problemet när oberoende bevis dök upp som visade att en ängel kan vinna. Bowditch bevisade att en 4-ängel (det vill säga en ängel med kraften k = 4) kan vinna och Máthé och Kloster gav bevis på att en 2-ängel kan vinna.

Grundläggande strategier och varför de inte fungerar

Många intuitiva flyktstrategier för ängeln kan besegras. Till exempel, om ängeln försöker fly från nära block, kan djävulen göra en jättehästsko långt norrut och sedan sticka ängeln i fällan genom att upprepade gånger äta kvadraten strax söder om ängeln. Om ängeln försöker undvika fällor som satts väldigt långt bort, kan djävulen göra en liten hästsko i norr och sedan sticka ängeln i fällan genom att äta rutorna långt söderut.

Det verkar som att ängeln borde kunna vinna genom att gå upp så fort han kan, kombinerat med enstaka sicksack öster eller väster för att undvika uppenbara fällor. Denna strategi kan besegras genom att notera att denna ängels möjliga framtida positioner ligger i en kon, och djävulen kan bygga en vägg tvärs över konen i fjärran på ett visst sätt, så att när ängeln äntligen kommer på avståndet, har djävulen skapat en ogenomtränglig vägg, och eftersom ängeln insisterar på att flytta norrut, kan ängeln inte röra sig alls.

Historia

Problemet publicerades först i boken Winning Ways från 1982 av Berlekamp, Conway och Guy, under namnet "ängeln och kvadratätaren". I två dimensioner inkluderade några tidiga delresultat:

Om ängeln har makt 1, har djävulen en vinnande strategi (Conway, 1982). (Enligt Conway beror detta resultat faktiskt på Berlekamp .) Detta kan läsas i avsnitt 1.1 i Kutzs tidning.
Om ängeln aldrig minskar sin y-koordinat, så har djävulen en vinnande strategi (Conway, 1982).
Om ängeln alltid ökar sitt avstånd från ursprunget, så har djävulen en vinnande strategi (Conway, 1996).

I tre dimensioner visades det att: ^{[ citat behövs ]}

Om ängeln alltid ökar sin y-koordinat, och djävulen bara kan spela på ett plan, så har ängeln en vinnande strategi.
Om ängeln alltid ökar sin y-koordinat, och djävulen bara kan spela i två plan, så har ängeln en vinnande strategi.
Ängeln har en vinnande strategi om den har styrka 13 eller mer.
Om vi har ett oändligt antal djävlar som var och en spelar på avstånd $d_{1}<d_{2}<d_{3}<\cdots$ så kan ängeln fortfarande vinna om den har tillräckligt hög kraft. (Med "spela på distans $d$ " menar vi att djävulen inte får spela inom detta avstånd från ursprunget). ^{[ tveksamt – diskutera ]}

Slutligen, 2006 (inte långt efter publiceringen av Peter Winklers bok Mathematical Puzzles , som hjälpte till att offentliggöra ängelproblemet) dök det upp fyra oberoende och nästan samtidigt bevis på att ängeln har en vinnande strategi i två dimensioner. Brian Bowditchs bevis fungerar för 4-ängeln, medan Oddvar Klosters bevis och András Máthés bevis fungerar för 2-ängeln. Dessutom har Péter Gács ett hävdat bevis som kräver en mycket starkare ängel; detaljerna är ganska komplicerade och har inte granskats av en tidskrift för noggrannhet. Bevisen av Bowditch och Máthé har publicerats i Combinatorics, Probability and Computing . Beviset av Kloster har publicerats i Theoretical Computer Science .

Ytterligare olösta frågor

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

Bevisskisser

Klosters 2-änglar bevis

Oddvar Kloster upptäckte en konstruktiv algoritm för att lösa problemet med en 2-ängel. Denna algoritm är ganska enkel och också optimal, eftersom, som nämnts ovan, djävulen har en vinnande strategi mot en 1-ängel.

Vi börjar med att dra en vertikal linje omedelbart till vänster om ängelns startposition, ner till $y=-\infty$ och upp till $y=\infty$ . Den här linjen representerar vägen som ängeln kommer att ta, som kommer att uppdateras efter vart och ett av djävulens drag, och delar upp brädans rutor i en "vänster uppsättning" och en "höger uppsättning". När en ruta väl blir en del av den vänstra uppsättningen kommer den att förbli så under resten av spelet, och ängeln kommer inte att göra några framtida drag till någon av dessa rutor. Varje gång djävulen blockerar en ny ruta söker vi över alla möjliga modifieringar av banan så att vi flyttar en eller flera rutor i den högra uppsättningen som djävulen har spärrat av till den vänstra uppsättningen. Vi kommer bara att göra detta om banan ökar i längd med högst dubbelt så många blockerade rutor som flyttas till den vänstra uppsättningen. Av sådana kvalificerande vägar väljer vi en som flyttar det största antalet blockerade rutor till den vänstra uppsättningen. Ängeln gör sedan två steg längs denna väg och håller banan till vänster när den rör sig framåt (så om djävulen inte blockerade rutor skulle ängeln resa norrut på obestämd tid). Observera att när du går medurs runt ett hörn kommer ängeln inte att röra sig ett steg, eftersom de två segmenten som rör vid hörnet har samma ruta till höger.

Máthés 2-änglar bevis

Máthé introducerar den snälla djävulen, som aldrig förstör en ruta som ängeln kunde ha valt att ockupera vid en tidigare tur. När ängeln spelar mot den snälla djävulen medger den nederlag om djävulen lyckas begränsa den till en ändlig avgränsad del av spelplanen (annars kan ängeln bara hoppa fram och tillbaka mellan två rutor och aldrig förlora!). Máthés bevis delas upp i två delar:

han visar att om ängeln vinner mot den snälla djävulen, så vinner ängeln mot den riktiga djävulen;
han ger en tydlig vinnande strategi för ängeln mot den snälla djävulen.

Grovt sett, i den andra delen vinner ängeln mot den snälla djävulen genom att låtsas att hela det vänstra halvplanet är förstört (utöver alla rutor som faktiskt förstörts av den trevliga djävulen), och behandla förstörda rutor som väggarna i en labyrint , som den sedan går över med hjälp av en "hand-på-väggen"-teknik. Det vill säga, ängeln håller sin vänstra hand på labyrintens vägg och springer längs väggen. Man bevisar då att en snäll djävul inte kan fånga en ängel som anammar denna strategi.

Beviset för den första delen är motsägelsefullt, och därför ger Máthés bevis inte omedelbart en explicit vinnande strategi mot den verkliga djävulen. Máthé påpekar dock att hans bevis i princip skulle kunna anpassas för att ge en sådan explicit strategi.

Bowditchs 4-änglar bevis

Brian Bowditch definierar en variant (spel 2) av originalspelet med följande regeländringar:

Ängeln kan återvända till vilken ruta den redan har varit på, även om djävulen senare försökte blockera den.
En k-djävul måste besöka en kvadrat k gånger innan den blockeras.
Ängeln rör sig antingen upp, ner, vänster eller höger med en ruta (ett hertigdrag).
För att vinna måste ängeln spåra en slingrig väg (definierad nedan).

En kretsväg är en väg $\pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$ där $\sigma =\cup _{i=1}^{\infty }\sigma _{i}$ är en halvoändlig båge (en icke självkorsande väg med en startpunkt men ingen slutpunkt) och ${\gamma _{i}}$ är parvis disjunkta loopar med följande egenskap:

$\forall i:|\gamma _{i}|\leq i$ där $|\gamma _{i}|$ är längden på den ith-slingan.

(För att vara väl definierad måste $\gamma _{i}$ börja och sluta i slutpunkten för $\sigma _{i}$ och $\sigma _{i}$ måste sluta vid startpunkten för ${\displaystyle \sigma _{i+1}} .$ )

Bowditch överväger en variant (spel 1) av spelet med ändringarna 2 och 3 med en 5-djävul. Han visar sedan att en vinnande strategi i detta spel kommer att ge en vinnande strategi i vårt ursprungliga spel för en 4-änglar. Han fortsätter sedan med att visa att en ängel som spelar en 5-djävul (spel 2) kan uppnå en vinst med en ganska enkel algoritm.

Bowditch hävdar att en 4-ängel kan vinna den ursprungliga versionen av spelet genom att föreställa sig en fantomängel som spelar en 5-djävul i spel 2.

Ängeln följer den väg som fantomen skulle ta men undviker slingorna. Eftersom vägen $\sigma$ är en semi-oändlig båge så återvänder inte ängeln till någon ruta den tidigare har varit på och så är vägen en vinnande väg även i det ursprungliga spelet.

3D-version av problemet

"Guardian" bevis

Beviset, som visar att i en tredimensionell version av spelet har en kraftfull ängel en vinnande strategi, använder sig av "väktare". För varje kub av valfri storlek finns det en väktare som vakar över den kuben. Väktarna bestämmer vid varje drag om kuben de vakar över är osäker, säker eller nästan säker. Definitionerna av "säker" och "nästan säker" måste väljas för att säkerställa att detta fungerar. Detta beslut baseras enbart på tätheten av blockerade punkter i den kuben och storleken på den kuben.

Om ängeln inte får några order, så går den bara uppåt. Om några kuber som ängeln upptar upphör att vara säkra, instrueras väktaren av den största av dessa kuber att ordna så att ängeln lämnar genom en av kubens gränser. Om en väktare instrueras att eskortera ängeln ut ur sin kub till ett speciellt ansikte, gör väktaren det genom att rita ut en väg av underkuber som alla är säkra. Väktarna i dessa kuber instrueras sedan att eskortera ängeln genom sina respektive subkuber. Ängelns väg i en given subkub bestäms inte förrän ängeln kommer till den kuben. Även då är vägen bara grovt bestämd. Detta säkerställer att djävulen inte bara kan välja en plats på vägen tillräckligt långt längs den och blockera den.

Strategin kan bevisas fungera eftersom tiden det tar djävulen att konvertera en säker kub på ängelns väg till en osäker kub är längre än den tid det tar för ängeln att komma till den kuben.

Detta bevis publicerades av Imre Leader och Béla Bollobás 2006. Ett väsentligen liknande bevis publicerades av Martin Kutz 2005.

Se även

Det mordiska chaufförsproblemet , ett annat matematiskt spel som ställer en kraftfull och manövrerbar motståndare mot en mycket påhittig men mindre mäktig fiende.

externa länkar