Problem om en engel og en djævel

Engle- og djævelproblemet er et spilteoretisk problem foreslået af Conway i 1982. [1] .

Ordlyd

Spilleregler

To spillere spiller , kaldet en engel og en djævel. Spillet foregår på et endeløst skakbræt . Englen har "styrke" k (det er et naturligt tal 1 eller mere), som indstilles før spillet starter. I begyndelsen af spillet står englen på en af cellerne. Med hvert træk flytter englen til en anden fri celle, som kan nås i maksimalt k træk af kongen. Djævelen kan til gengæld blokere én celle, der ikke har en engel. Englen kan hoppe over blokerede rum, men kan ikke lande på dem. Djævelen vinder, hvis englen ikke kan bevæge sig. Englen vinder, hvis den lever på ubestemt tid.

Spørgsmål

Kan en engel vinde, hvis den har nok kraft?

Mere præcist er det nødvendigt at finde en vinderstrategi for en af spillerne. Hvis djævelen kan vinde, skal han gøre det i et begrænset antal træk. Hvis djævelen ikke kan vinde, så er der altid en handling, som englen kan tage for at undgå at tabe, og den vindende strategi er at vælge sådan et træk. Det vil sige, at sættet af træk, der fører til vinderen af englen, er lukket i den naturlige topologi på sættet af alle træk, og sådanne spil er kendt for at være deterministiske .

Historie

Problemet blev første gang udgivet i 1982 i Winning Ways af Berlekamp , Conway og Guy [2] under titlen "The Angel and the Square Eater".

Conway annoncerede en belønning for den generelle løsning af problemet ($100 for en vindende strategi for en engel med tilstrækkelig styrke og $1.000 for at bevise, at djævelen kan vinde uanset englens styrke).

For det todimensionelle tilfælde er her nogle tidlige resultater:

Hvis englens styrke er 1, så har djævelen en vinderstrategi. (Ifølge Conway skyldes dette resultat Alvin Berlekamp ).
Hvis englen aldrig reducerer koordinaterne, så har djævelen en vindende strategi (Conway, 1982).
Hvis englen altid øger afstanden fra den centrale celle, så har djævelen en vindende strategi (Conway, 1996).

For en tredimensionel tavle er det blevet bevist, at:

Hvis englen altid øger afstanden fra den centrale plads, og djævelen kan spille på samme plan, så har englen en vinderstrategi.
Hvis englen altid øger koordinaterne, og djævelen kun kan spille på to planer, så har englen en vindende strategi.
En engel har en vindende strategi, hvis dens styrke er 13 eller højere.
Hvis der er et uendeligt antal djævle, og alle spiller på afstand , så kan englen stadig vinde, hvis den har en stor nok kraft. (Med "spil på afstand " mener vi begrænsningen, at djævelen ikke må spille på en mindre afstand fra startfeltet.) $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Endelig blev der i 2006 (kort efter udgivelsen af Peter Winklers Matematiske puslespil , som gjorde dette problem populært) præsenteret fire uafhængige og næsten identiske beviser på, at en engel har en vinderstrategi på et fladt bord. Bowditchs [3] bevis virker med arbejder med kraftengel 2.[4]bevisAndré MatesbevisKlostersOddvarmens,4 kraftengel Beviserne for Bowditch og Mate blev offentliggjort i Combinatorics, Probability and Computing (redaktørerne Bolobas og Leader ). Klosters bevis er publiceret i Theoretical Computer Science .

Bevis skitser

Bevis "Vagt"

Et bevis, der viser, at en 3D-version af spillet med en engel med tilstrækkelig styrke har en vindende strategi, bruger "vagter". For enhver terning af enhver størrelse er der en vagt, der holder øje med terningen. Før hvert træk beslutter vagten, om den terning, han ser, er farlig, sikker eller næsten sikker. Definitionerne af "sikker" og "næsten sikker" bør præciseres - denne beslutning er udelukkende baseret på tætheden af blokeringspunkter i kuben og størrelsen af kuben.

Hvis englens træk ikke er forudbestemt, rykker vi simpelthen op. Hvis nogle terninger, som englen efterlader, er sikre, så instrueres vagten af den største terning om at sikre, at englen kommer ud af terningen gennem en af terningens flader. Hvis vagten bliver instrueret i at eskortere englen udad til en bestemt kant, gør vagten det ved at bygge en sti gennem de sikre underkuber. Vagterne i disse terninger bliver instrueret i at eskortere englen gennem dens underkuber. En engels vej i en underkube er ikke defineret, før englen går ind i den terning. Alligevel er stien groft defineret. Strategien sikrer, at djævelen ikke kan vælge et sted på englens vej langt nok til at blokere det.

Det kan bevises, at strategien virker, fordi den tid, det tager djævelen at forvandle en sikker terning på englens vej til en farlig, er længere end den tid, det tager for englen at nå terningen.

Dette bevis blev udgivet af Lider [ og Bolobas i 2006 [5] . Et lignende bevis blev offentliggjort af Martin Kutz i 2005 [6] [7] .

Proof of Mate for en engel med styrke 2

Mate [4] introducerede en taktfuld djævel , der aldrig ødelagde en celle, som en engel tidligere havde besat. Hvis en engel spiller mod en taktfuld djævel, antages djævelen at vinde, hvis den begrænser englens bevægelse til et begrænset område (ellers hopper englen bare frem og tilbage i to felter og taber aldrig!).

Mate gav en eksplicit vinderstrategi for en engel mod en taktfuld djævel og viste, at hvis en engel vinder mod en taktfuld djævel, så vinder en engel mod en rigtig djævel.

I den første del vinder englen over den taktfulde djævel ved at antage, at hele venstre halvplan er ødelagt (udover alle de celler, der er ødelagt af djævelen), og behandler de ødelagte celler som væggene i en labyrint, hvilket er omgået efter "venstrehånds"-reglen. Det vil sige, at englen holder sin venstre hånd på labyrintens væg og går langs væggen. Det kan bevises, at en taktfuld djævel ikke kan fange en engel, der vedtager en sådan strategi.

Anden del er bevist ved modsigelse, og derfor giver Mates bevis ikke en umiddelbar vinderstrategi mod den rigtige djævel. Mate bemærker dog, at dette bevis i princippet kan tilpasses til at opnå en sådan strategi.

Bowditchs bevis for en engel med styrke 4

Bodwich definerer [3] en variant (spil 2) af åbningsspillet med følgende regelændringer:

Englen kan vende tilbage til enhver plads, den allerede har besøgt, selvom djævelen så forsøgte at blokere den.
K-djævelen skal besøge cellen k gange, før den blokeres.
Englen flytter en celle op/ned/venstre/højre.
For at vinde skal englen følge den cirkulære sti beskrevet nedenfor.

En cirkulær sti er en sti, hvor er en semi-uendelig bue (en selvadskillende sti med et startpunkt, men intet endepunkt) og er parvist adskilte sløjfer med følgende egenskaber: $\pi =\kop _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$ ${\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i))$ ${\gamma _{i))$

$\forall i:|\gamma _{i}|\leq i$ hvor er længden af den i-te løkke. $|\gamma _{i}|$

(For at være helt specifik skal den begynde og slutte ved slutpunktet og skal slutte ved startpunktet .) ${\displaystyle \gamma _{i))$ $\sigma_i$ $\sigma_i$ $\sigma _{i+1}$

Bodwich foreslår en variant (spil 1) af spillet med ændringer 2 og 3 og 5-djævel. Han viste, at vinderstrategien i dette spil ville give det originale spils vinderstrategi for en engel med styrke 4. Han viste også, at en engel, der spillede mod en 5-djævel (spil 2), kunne opnå en sejr ved hjælp af en ret simpel algoritme.

Bodwich udtaler, at en engel med 4 styrker kan vinde den originale version af spillet ved at forestille sig en fantomengel, der spiller mod en 5-djævel i spil 2.

Englen følger fantomenglens mulige vej, men undgår løkkerne. Da stien er en semi-uendelig bue, vil englen ikke vende tilbage til nogen firkant, den allerede har besøgt, og derfor vil stien være den vindende vej i det originale spil. $\sigma$

Variationer og generaliseringer

I 3D-rum, givet at englen altid øger y -koordinaten og djævelen er begrænset til tre planer, er det uvist, om djævelen har en vindende strategi.

Se også

Killer driver problem , endnu et matematikspil, hvor en langsom, men adræt spiller forsøger at løbe fra en hurtigere, men mindre adræt fjende.
Garanteret søgeteori

Noter

↑ John H. Conway. Spil uden chance / Richard Nowakowski. - MSRI Publications, 1996. - V. 29. - S. 3-12. Engleproblemet Arkiveret 29. september 2020 på Wayback Machine
↑ Elwyn R. Berlekamp , John H. Conway og Richard K. Guy , Winning Ways for your matematiske skuespil, bind 2: Games in Particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , Englespillet i flyet , Kombin. Sandsynligvis. Comput. 16(3):345-362, 2007.
↑ 1 2 András Máthé, Magtens engel 2 vinder , Kombiner. Sandsynligvis. Comput. 16(3):363-374, 2007
↑ B. Bollobás og I. Leader, Englen og djævelen i tre dimensioner. Tidsskrift for kombinatorisk teori. Serie A. vol. 113 (2006), nr. 1, s. 176-184
↑ Martin Kutz, Conways engel i tre dimensioner, Teoret. Comp. sci. 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, PhD-afhandling Arkiveret 11. december 2007 på Wayback Machine FU Berlin, 2004