L' angelo e il diavolo
LordBeotian
Ecco a voi un giochino molto intrigante; premetto che sulla rivista in cui
l' ho trovato dicevano che non era ancora pervenuta alcuna soluzione.
Il gioco è semplicissimo:
Si gioca su una scacchiera infinita.
L' angelo ha una pedina che si muove in ogni turno come il re negli scacchi
(una casella alla volta in qualsiasi direzione).
Il diavolo non ha pedine: può distruggere in ogni turno una casella in modo
permanente. Le caselle distrutte non sono più occupabili dall' angelo.
Il diavolo vince se riesce a bloccare l' angelo in una casella circondata
da caselle distrutte.
Domanda: esiste una strategia per l' angelo che impedisce al diavolo di
vincere?
----
Osservazioni mie:
a dispetto della semplicità con cui è formulato, il problema sembra essere
complicatissimo:
le prime strategie che mi vengono in mente sono:
1) l' angelo sceglie una direzione e cerca di mantenerla. Questa strategia
fallisce: è sufficiente che il diavolo capisca qual' è la direzione e in
una zona lontana lungo quella direzione inizi a costruire una trappola.
Allora viene in mente quest' altra cosa:
2) l' anglo si muove sempre nella direzione in cui la scacchiera è più
sgombra, cioè dove ci sono meno caselle distrutte. Fallisce anche così:
basta che il diavolo si metta a distruggere caselle attorno all' angelo in
un modo casuale ma che alla fine formano un grosso circolo: l' angelo
cambierà continuamente direzione poichè di volta in volta la scacchiera
sarà "più sgombra" (anche se di poco) in direzioni diverse. Più in generale
con questa strategia l' angelo non è al riparo dalla possibilità di tornare
sui suoi passi e quindi rischia di essere troppo lento e di farsi chiudere.
Insomma l' angelo deve conciliare una buona "velocità" con la possibilità
di cambiare direzione all' occorrenza e le due cose sembrano escludersi.
Spero di avervi "stuzzicato" abbastanza...
Ciao!!
Marco
Wizzent
>
> Ecco a voi un giochino molto intrigante; premetto che sulla rivista in cui
> l' ho trovato dicevano che non era ancora pervenuta alcuna soluzione.
> Il gioco è semplicissimo:
>
> Si gioca su una scacchiera infinita.
> L' angelo ha una pedina che si muove in ogni turno come il re negli scacchi
> (una casella alla volta in qualsiasi direzione).
> Il diavolo non ha pedine: può distruggere in ogni turno una casella in modo
> permanente. Le caselle distrutte non sono più occupabili dall' angelo.
> Il diavolo vince se riesce a bloccare l' angelo in una casella circondata
> da caselle distrutte.
>
> Domanda: esiste una strategia per l' angelo che impedisce al diavolo di
> vincere?
Dico la mia.
Premessa: l'angelo per perdere deve rimanere chiuso in un quadrato di celle
distrutte.
Considerazioni:
1: una cella è circondata da 8 celle.
2: 2 celle consecutive in orizzontale o verticale sono circondate da 10 celle.
3: 3 celle consecutive in orizzontale o verticale sono circondate da 12 celle.
4: x celle consecutive in orizzontale o verticale sono circondate da 8+2(x-1)
celle
5: 2 celle consecutive in diagonale sono circondate da 12 celle.
6: 3 celle consecutive in diagonale sono circondate da 16 celle.
7: x celle consecutive in diagonale sono circondate da 8+4(x-1) celle
Prendendo x come le mosse dell'angelo (e del diavolo), dalle considerazioni 4
e 7 si vede che l'angelo ha già in partenza un vantaggio di 8 mosse e per ogni
spostamento aumenta il vantaggio al massimo di 4 caselle se si muove in
diagonale in linea retta, mentre se torna sui propri passi aumenta il
vantaggio di 0. Dato che il diavolo cancella una casella per volta è "più
veloce" dell'angelo solo se questo torna sui propri passi (o comunque torna
indietro, anche se non passa sulle celle dove è già passato). Ma anche in
questo caso l'angelo per perdere deve commettere più volte questo errore.
La risposta che ho dato è un tantino incasinata e non sono riportati tutti i
ragionamenti fatti, comunque secondo me la conclusione è che l'angelo è di
molto più veloce del diavolo e per vincere basta che si muova sempre "verso
l'esterno".
Ciao
----------------------------------------------------------------
Wizzent
"Odio le citazioni al fondo delle e-mail" (by Aristotele)
Livio Zucca
>
>Si
gioca su una scacchiera infinita.
>L' angelo ha una pedina che si muove in
ogni turno come il re negli scacchi (una casella alla volta in qualsiasi
direzione).
>Il diavolo non ha pedine: può distruggere in ogni turno una
casella in modo permanente. Le caselle distrutte non sono più occupabili
dall' angelo. Il diavolo vince se riesce a bloccare l' angelo in una
casella circondata da caselle distrutte.
.
>Domanda: esiste una strategia
per l' angelo che impedisce al diavolo di vincere?
.
.
Che vi piaccia
o no, per rispondere bisogna mettersi dalla parte del diavolo e vedere se
LUI ha una cattivissima strategia vincente. Se e' cosi', come temo, per
l'angelo non c'e' niente da fare. Ben lo sa la Chiesa, furrrrrba, che tra
le sue istituzioni ha inventato l'Avvocato del Diavolo.
Dunque, questo
povero diavolo avrebbe pensato a questa strategia. Se qualcuno vuole fare
l'Avvocato dell'Angelo, provi a cavarsela:
Dalla posizione iniziale
dell'angelo, traccio mentalmente un quadrato di una quarantina di caselle
di lato con la posizione iniziale dell'angelo nel baricentro. Per ogni
direzione intrapresa dall'angelo io distruggo la casella sulla sua
traettoria e sul quadrato. Se quella casella e' gia' distrutta, ne
distruggo una tra le piu' vicine e sempre sul quadrato, avendo cura di
lasciarne una intera. Cioe' costruisco un muro bucato alternativamente, una
casella distrutta, una intera, e cosi' via. Se l'angelo cincischia tornando
sui suoi passi, e' fottuto perche' prima o poi completo la trappola. Se si
avvicina al muro traforato, cercando di prendere il varco, io gli tappero'
i buchi, potendo andare ad una velocita' doppia della sua!
Sono stato
abbastanza diabolico? Se si', stasera si cena con arrosto di angelo, hi hi
hi!
.
.
Ciao :o)
Livio Satanasso
--------------------------------
Inviato via http://usenet.iol.it
LordBeotian
Livio Zucca <l...@tin.it> wrote
> Dalla posizione iniziale
> dell'angelo, traccio mentalmente un quadrato di una quarantina di caselle
> di lato con la posizione iniziale dell'angelo nel baricentro. Per ogni
> direzione intrapresa dall'angelo io distruggo la casella sulla sua
> traettoria e sul quadrato. Se quella casella e' gia' distrutta, ne
> distruggo una tra le piu' vicine e sempre sul quadrato, avendo cura di
> lasciarne una intera. Cioe' costruisco un muro bucato alternativamente,
una
> casella distrutta, una intera, e cosi' via. Se l'angelo cincischia
tornando
> sui suoi passi, e' fottuto perche' prima o poi completo la trappola. Se
si
> avvicina al muro traforato, cercando di prendere il varco, io gli
tappero'
> i buchi, potendo andare ad una velocita' doppia della sua!
> Sono stato
> abbastanza diabolico? Se si', stasera si cena con arrosto di angelo, hi
hi
> hi!
Sei veramente perfido, ma sei sicuro di poter riuscire nei tuoi biechi
intenti?
Io non so se il tuo metodo funziona, però ti faccio notare questo:
Tu parli di un mega quadrato di una quarantina di caselle: perchè proprio
quaranta? Potrebbero bastarne meno. Ora se provi ad adottare la tua
strategia con quadrati più piccoli scoprirai che fallisce: l' angelo riesce
ad uscire indenne dal tuo quadrato, non fai in tempo a bloccarlo (prova a
farti un disegnino se non ci credi). E a occhio direi che la cosa vale
anche per i quadtrati più grandi.
A lei la parola avvocato.
Ciao!!
Marco
LordBeotian
Wizzent <mrc...@inwind.it> wrote
> La risposta che ho dato è un tantino incasinata e non sono riportati
tutti i
> ragionamenti fatti, comunque secondo me la conclusione è che l'angelo è
di
> molto più veloce del diavolo e per vincere basta che si muova sempre
"verso
> l'esterno".
Anche a me sembra intuitivamente giusto che il diavolo sia troppo lento
rispetto all' angelo. L' idea è che se io mi mettessi a giocare come angelo
immagino che saprei sempre fare la mossa giusta per svignarmela senza farmi
mai intrappolare.
Il problema è formalizzare questa intuizione: esiste un algoritmo che
esegue quello che io farei se stessi giocando riuscendo a scappare sempre?
Tu parli di muoversi sempre "verso l' esterno", ma come formalizzaresti
questa idea?
Potresti sempre essere costretto dal diavolo a deviare dalla tua direzione
(dalla retta via :)). Come fai ad essere certo che deviando troppo tu non
finisca per descrivere un cerchio (che significa tornare sui tuoi passi) o
una spirale (che significa allontanarsi lentamente)? Che strategia adotti
per scongiurare questa eventualità?
Ciao!!
Marco
fulvio
"LordBeotian" <mard...@tin.it> ha scritto nel messaggio
news:9af1dd$lui$1...@fe2.cs.interbusiness.it...
La mia impressione netta e' che il diavolo ci riesca , ma
dopo infinite mosse!
Non e' una battuta, putroppo non ho la sufficiente dimestichezza
con Cantor e company, per riuscire a spirgarlo, spero che qualcuno di
voi intuisca quello che intendo e dia una conferma (o una smentita)
Ciao a tutti
fulvio
Livio Zucca
>
>Sei veramente perfido, ma sei sicuro di poter riuscire nei tuoi biechi
>intenti?
>Io non so se il tuo metodo funziona, però ti faccio notare
questo:
>Tu parli di un mega quadrato di una quarantina di caselle: perchè
proprio
>quaranta? Potrebbero bastarne meno. Ora se provi ad adottare la
tua
>strategia con quadrati più piccoli scoprirai che fallisce: l' angelo
>riesce
>ad uscire indenne dal tuo quadrato, non fai in tempo a bloccarlo
(prova a
>farti un disegnino se non ci credi). E a occhio direi che la
cosa vale
>anche per i quadtrati più grandi.
>A lei la parola avvocato.
>Ciao!!
>Marco
.
.
Abbiamo provato a simulare la scacchiera
infinita con un foglio di carta quadrettata (qualcuno ci ha visto e ha
detto: state giocando a punto e croce!). Non so il vostro angelo, il mio ha
un'intelligenza media e l'ho sempre battuto usando un quadrato di circa 40
di lato. Piu' grande? piu' piccolo? Non saprei. Se molto piccolo non
funziona. Voi trovate una strategia per l'angelo, poi io metto tutt'e due
le strategie in due automi e vediamo. Poi falliro' nel mio lavoro, quello
della pagnotta, ma, vuoi mettere, una soddisfazione!!!
.
Ciao :o)
Livio
Satanasso
P.S. Il gioco dell'Hex usava una strategia del genere.
Wizzent
Vediamo un po' (spero di non dilungarmi troppo)..
Come detto prima la via migliore è quella in diagonale proseguendo da dove si
arriva, in quanto risulta essere la via più veloce.
Inevitabilmente capiterò di dover modificare questa strada, perchè il diavolo
sicuramente prima o poi distruggerà una casella sulla traiettoria dell'angelo.
L'importante è muoversi il più possibile "verso l'esterno". Ora cerco di
spiegare cosa intendo dire con questo. Supponiamo che siano già state fatte un
certo numero di mosse. Per capire dov'è l'esterno basta calcolare dov'è il
baricentro della figura disegnata dal percorso dell'angelo (*) e seguire la
semiretta che parte da questo punto e passa per la posizione attuale
dell'angelo. Questo dovrebbe essere il percorso ideale. Più l'angolo creato
tra la semiretta immaginaria e il reale percorso dell'angelo è grande, meno
sono le celle guadagnate dall'angelo, fino al punto di poter perdere celle di
vantaggio. La strategia del diavolo dovrebbe essere quella di tentare di
bruciare questo vantaggio che l'angelo ha già in partenza e che può crescere
molto facilmente e velocemente.
La mia conclusione è (in due parole, molto poco matematica): se l'angelo ha un
minimo di intelligenza, il diavolo s'attacca... :)
(*)-la figura deve ricoprire l'area più ampia possibile. Questo vuol dire che
se l'angelo ha fatto un percorso tipo questo
_ _ _ _ _ _ _ _
|A|_|_|_|_|_|_|_|
|_|A|_|_|A|_|_|_|
|_|_|A|A|_|A|_|_|
|_|_|_|_|_|A|_|_|
|_|_|_|A|A|_|_|_|
|_|_|A|_|_|_|_|_|
l'area è
_ _ _ _ _ _ _ _
|A##########|_|_|
|#|A|_|_|A|#|_|_|
|#|_|A|A|_|A|_|_|
|#|_|_|_|_|A|_|_|
|#|_|_|A|A|#|_|_|
|####A######|_|_|
LordBeotian
Livio Zucca <l...@tin.it> wrote
> Abbiamo provato a simulare la scacchiera
> infinita con un foglio di carta quadrettata (qualcuno ci ha visto e ha
> detto: state giocando a punto e croce!). Non so il vostro angelo, il mio
ha
> un'intelligenza media e l'ho sempre battuto usando un quadrato di circa
40
> di lato. Piu' grande? piu' piccolo? Non saprei. Se molto piccolo non
> funziona. Voi trovate una strategia per l'angelo, poi io metto tutt'e due
> le strategie in due automi e vediamo. Poi falliro' nel mio lavoro, quello
> della pagnotta, ma, vuoi mettere, una soddisfazione!!!
Se ho capito bene la tua strategia, l' angelo può salvarsi sempre in questo
modo:
punta un lato del quadrato e ci si incammina andando a zig-zag (alternando
due diagonali), così:
o o o o o o o ...
o o o o o o o ... ->
In tal modo il diavolo distrugge sempre caselle laterali di quel lato
(quelle lungo le diagonali percorse nello zig-zag) e mai quelle davanti
all' angelo. Sicchè alla fine l' angelo può passare attraversare il bordo
del quadrato indisturbato. O almeno ha potuto farlo in tutte le mie prove.
Questa scappatoia sembra funzionare indipendentemente dalla grandezza del
quadrato.
Il male non trionferà così facilmente.
Ciao!!
Marco
LordBeotian
Wizzent <mrc...@inwind.it> wrote
Ok, credo di aver capito.
Ora il problema è questo:
Ammettiamo che la strategia dell' angelo consista solo nel "muoversi sempre
verso l' esterno".
Per come l' hai definita tu, questa strategia non si preoccupa affatto di
quello che fa il diavolo, se non nel momento in cui siamo costretti a
cambiare direzione perchè qualcuna delle caselle adiacenti è distrutta.
In particolare, se il diavolo non ti disturba mai la strategia ti porta a
muoverti in linea retta lungo una qualche direzione.
Ora considera questa strategia del diavolo: vede in che direzione ti stai
muovendo e a 10000 caselle di distanza, lungo la tua direzione inizia a
distruggere alcune caselle in modo da formare una "scatola" con un buco
lungo la tua traiettoria. Appena passi di lì la chiude.
Tu mi potresti dire: sì ma non sono mica scemo ad andare dentro la sua
tappola. E avresti ragione, ma la tua strategia di "andare sempre verso l'
esterno" non ti tiene al riparo da questi comportamenti stupidi.
Come perfezioneresti la tua strategia?
Ciao!!
MArco
Livio Zucca
>
>
>Se ho capito bene la tua strategia, l' angelo può salvarsi sempre in
questo modo:
>punta un lato del quadrato e ci si incammina andando a zig-
zag (alternando due diagonali), così:
>
> o o o o o o o ...
> o o
o o o o o ... ->
>
>In tal modo il diavolo distrugge sempre caselle
laterali di quel lato (quelle lungo le diagonali percorse nello zig-zag) e
mai quelle davanti all' angelo. Sicchè alla fine l' angelo può passare
>attraversare il bordo del quadrato indisturbato. O almeno ha potuto farlo
in tutte le mie prove. Questa scappatoia sembra funzionare
indipendentemente dalla grandezza del quadrato.
>
>Il male non trionferà
così facilmente.
>
>Ciao!!
>Marco
>
>
.
Non sempre e' facile
algoritmizzare una strategia: il diavolo deve costruire il muro traforato
che intercetti la reale traettoria dell'angelo. Un automa rudimentale puo'
essere tratto in inganno, ma un diavolo no! Se cmq. dovessi fare l'automa,
cercherei di basarmi anche sulla media delle ultime direzioni e sulla
vicinanza ad un muro. Ad esempio con un filtro trasersale che prenda il 50%
della direzione dell'ultima mossa, il 25% della penultima, il 12% della
terzultima, e cosi' via. Ma la tecnica del muro traforato resta potente. Il
diavolo comincera' a tappare i buchi quando l'angelo si avvicinera' a
distanza 2 (3 nell'angolo) per evitare gli *occhiali*, cioe' la
possibilita' di andare a scelta in uno dei due varchi piu' vicini. Dopo di
che il diavolo, tappando i buchi andra' a velocita' doppia e appena avra'
distanziato l'angelo, riprendera' la sua strategia di costruttore del muro
traforato. (Il diavolo e' un *buon* concreto architetto, l'angelo se non lo
fai volare... :). Nelle prove che ho fatto io, si fronteggiano due umani
che interpretano al meglio le proprie strategie e il diavolo risulta
vincente. Non posso negare che l'avvocato del diavolo sia stato un po' piu'
motivato. Bisognerebbe far incontrare persone equivalenti. E qui bisogna
ammettere che i mezzi informatici sono ancora un po' carenti.
Se no
rischiamo di far scontrare algoritmi, non strategie, che sono almeno due
scalini sotto (in mezzo c'e' la tattica). E chi costruisce l'algoritmo
dopo, conoscendo quello dell'avversario e' favorito. Adesso ad esempio
potrei dire che se l'algoritmo dell'angelo e' quello di andare a zigzag,
allora il mio sara' quello di fare la media tra le ultime due direzioni, al
che tu risponderesti con un'altra strada, e cosi' via.
Ciao :o)
Livio
Satanasso
Wizzent
> Ok, credo di aver capito.
> Ora il problema è questo:
> Ammettiamo che la strategia dell' angelo consista solo nel "muoversi sempre
> verso l' esterno".
> Per come l' hai definita tu, questa strategia non si preoccupa affatto di
> quello che fa il diavolo, se non nel momento in cui siamo costretti a
> cambiare direzione perchè qualcuna delle caselle adiacenti è distrutta.
> In particolare, se il diavolo non ti disturba mai la strategia ti porta a
> muoverti in linea retta lungo una qualche direzione.
> Ora considera questa strategia del diavolo: vede in che direzione ti stai
> muovendo e a 10000 caselle di distanza, lungo la tua direzione inizia a
> distruggere alcune caselle in modo da formare una "scatola" con un buco
> lungo la tua traiettoria. Appena passi di lì la chiude.
> Tu mi potresti dire: sì ma non sono mica scemo ad andare dentro la sua
> tappola. E avresti ragione, ma la tua strategia di "andare sempre verso l'
> esterno" non ti tiene al riparo da questi comportamenti stupidi.
> Come perfezioneresti la tua strategia?
>
E' vero, hai ragione. Non ho specificato esplicitamente che comunque l'angelo
deve sempre guardare che sta facendo il diavolo: diciamo che era compreso in
quel "se l'angelo ha un minimo di intelligenza".. :)
Comunque adesso voglio pensarci su per benino: non mi è ancora ben chiaro il
perchè ma c'è un lato oscuro in tutto questo ragionamento che non mi convince
al 100%..
Livio Zucca
angelo ha una pedina che si muove in ogni turno come il re negli scacchi...
.
.
.
This is a famous problem mentioned in Winning Ways. It's unsolved.
.
--Ed!
http://www.mathpuzzle.com
(Ed Pegg Jr by Livio)
Livio Zucca
.
.
.
Caro Marco Beotian,
.
mi sa che mi hai fregato. Con la tua aria innocente, "Sapete, c'e' un
giochino scemino... su una rivista non l'hanno risolto... un angelo e un
diavolo..." mi hai precipitato nel baratro di un gioco godelliano e non
c'e' niente di piu' serio del gioco, lo sappiamo bene da bambini, poi ce lo
dimentichiamo.
Non ti conosco, ma tu mi sa che sei tutt'altro che
sprovveduto, sei arrivato a questo gioco con un ragionamento top-down, se
mi sbaglio mi corriggirai, come disse Carlino. Il mondo si divide in due :)
quelli che hanno capito il teorema di Godel e quelli no. Tu devi
appartenere alla prima. Poi ovviamente c'e' il sentiero di mezzo, compresi
quelli che non sanno cosa sia ma lo applicano e quelli che credono di aver
capito tutto e non hanno capito un Ca-z2-O. Io temo di appartenere a
quest'ultima :)
Nei normali giochi a due contendenti, come gli scacchi,
siamo di fronte ad un albero di gioco finito. Magari molto grande, che non
riusciamo a contenere in una ragionevole memoria, ma finito. E questa
solida certezza ci fa lavorare sereni a cercare automi sempre piu' bravi.
Probabilmente e' anche possibile inventare giochi con alberi infiniti. Ma
questo caso e' peggio: e' indicibile, forse. Questo non vuol dire che
domani un pirla di passaggio non ci dica: "Ma basta fare cosi'!" e noi
Ehhh?!? alla Manera. Ma finche' non succedera' non siamo autorizzati a
sostenere il contrario. E ci arrovelleremo.
.
La mia meta' angelica ti
ringrazia, la mia meta' diabolica ti... :o)
Ciao :o)
Livio
LordBeotian
Livio Zucca <l...@tin.it> wrote
Ciao Livio,
Converrai che se vogliamo fare un' analisi rigorosa dobbiamo parlare solo
di algoritmi, no?
Non c'è altro modo per dimostrare che esiste una strategia vincente: la
strategia deve essere "calcolabile", cioè un algoritmo.
In teoria è anche possibile che non esistano strategie vincenti
calcolabili, cioè che per ogni algoritmo arbitrariamente complicato ne
esista sempre uno che lo neutralizza. Se così è sarebbe interessante
poterlo dimostrare (chissà se storicamente si sono mai ottenuti risultati
di questo tipo...).
Torniamo a noi:
La tua idea del filtro trasversale che "intuisce" la direzione intrapresa
dall' angelo sicuramente è buona per neutralizzare la mia controstrategia.
Ideare una controstrategia per questo tuo algoritmo più raffinato del muro
traforato diventa veramente difficile.
Un aspetto interessante della tua tecnica è che riconduci il gioco a
qualcosa di più semplice: ovvero data una scacchiera finita NxN con l'
angelo al centro, può l' angelo raggiungere il bordo prima che il diavolo
lo distrugga tutto? Questo problema per N non troppo grandi potrebbe essere
risolubile via computer (a differenza del gioco infinito)... Se la risposta
è NO hai trovato la soluzione del gioco infinito. Se è SI il gioco infinito
rimane irrisolto.
La cosa che mi lascia perplesso è che per N piccoli il problema ha risposta
SI (l' angelo scappa), possibile che esista un N al di sopra del quale la
risposta diventa improvvisamente NO? Quanto dev' essere grande? Insomma,
sarebbe una cosa sorprendente.
E d' altra parte non sembra banale superare il tuo muro traforato...
Ciao!!
Marco
LordBeotian
Livio Zucca <l...@tin.it> wrote
Caro Livio Satanasso,
Dannazione mi hai smascherato!! Hai scoperto il diavolo che si cela dietro
la mia ingenuità falsamente condiscendente, ma tanto ormai sei inoffensivo,
chiuso tra gli abissi di una trappola Godeliana da cui uscirai solo dopo un
tempo infinitamente lungo.
Scherzi a parte mi fa piacere che il giochino abbia suggestionato te come
ha suggestionato me (ultimamente ci medito sopra anche mentre porto a
spasso il cane).
L' ho letto casualmente in una rivista in biblioteca e non so niente di più
di quello che ho detto e che dico adesso, giuro!!
Da una ricerca in rete ho scoperto oggi che gli ideatori del giochino sono
Thurston e Conway (quest' ultimo è un matematico famoso nonchè il genio che
ha inventato l' automa cellulare denominato "life", se hai presente).
Insomma ci sono due geni che non l' hanno risolto, il che ci può
scoraggiare come può invece stimolare il nostro orgoglio nel farci sentire
ingaggiati in un' impresa titanica.
Non so quanto sia "Godeliano" (o in che senso possa esserlo) ma le
possibilità sono queste (credo):
1) esiste una strategia (algoritmica) per l' angelo tale che qualunque
strategia (algoritmica) usi il diavolo non riuscirà ad acciuffarlo entro un
tempo finito
2) esiste una strategia (algoritmica) per il diavolo per la quale qualunque
cosa faccia l' angelo prima o poi sarà spacciato
3) per ogni strategia del diavolo ne esiste una dell' angelo che la
neutralizza, senza che ne esista una migliore di tutte
Dimostrare una qualunque di queste 3 asserzioni può essere facile (se ad
esempio la tua strategia del muro traforato funzionasse...) o quasi
impossibile (se vince l' angelo).
Ciao!!
Marco
Livio Zucca
>
>Ciao Livio,
>Converrai che se vogliamo fare un' analisi rigorosa dobbiamo
parlare solo
>di algoritmi, no?
.
.
.
Ciao Marco,
.
mi sento
proprio intrappolato. Per fortuna ci sara' un weekend senza PC, speriamo
che passi. Ci sto lavorando da ore ed e' mezzanotte suonata da un pezzo. Il
fatto che il resto del mondo non l'abbia risolto non riesce a smontarmi. Ho
costruito un programma in VB5 con quadrati parametrizzabili da 9 a 100 di
lato. Si puo' giocare in due a mano, uno sposta l'angelo col tastierino,
l'altro distrugge le caselle col click del mouse. Poi ho costruito un
automa *diavolo* con l'algoritmo del muro traforato. Io, questa volta
faccio la parte dell'angelo. Ho presto abbandonato l'idea del filtro
trasversale per capire l'intenzione dell'angelo. Se ci pensi, la storia dei
movimenti dell'angelo non ha nessuna influenza sulle sue prossime mosse.
Conta solo la sua posizione attuale. Per adesso siamo al punto in cui io
batto facilmente l'automa e l'automa batte mia moglie. Non fa testo, OK. Se
il gioco fosse: "Io diavolo traccio una retta ad una certa distanza
dall'angelo e lo sfido ad attraversarla", avrei quasi certamente
l'algoritmo vincente. E' un'evoluzione del muro traforato, una specie di
metodo dicotomico dove si distruggono caselle ad una certa distanza tra di
loro, dimezzando questa distanza man mano che l'angelo si avvicina. Se
funziona per una retta, si potrebbe pensare che possa funzionare per le
quattro che passano sui lati di un quadrato. In realta' ho visto che gli
angoli sono un punto debole. (angoli/angeli!). Ecco perche' penso ad un
quadrato grande: mentre l'angelo e' ancora lontano, potrei rinforzare gli
angoli. Provero'. In fondo le possibilita' per il diavolo sembrano gia' ora
aumentare all'aumentare delle dimensioni (mia moglie batte l'automa su
quadrati piccoli!). Speriamo che la funzione non sia asintotica
all'infinito. Ma anche dimostrare questo sarebbe una soluzione.
.
Buona
notte :o)
Livio
GDR
Blackstorm
>
> Ecco a voi un giochino molto intrigante; premetto che sulla rivista in cui
> l' ho trovato dicevano che non era ancora pervenuta alcuna soluzione.
> Il gioco è semplicissimo:
>
> Si gioca su una scacchiera infinita.
> L' angelo ha una pedina che si muove in ogni turno come il re negli scacchi
> (una casella alla volta in qualsiasi direzione).
> Il diavolo non ha pedine: può distruggere in ogni turno una casella in modo
> permanente. Le caselle distrutte non sono più occupabili dall' angelo.
> Il diavolo vince se riesce a bloccare l' angelo in una casella circondata
> da caselle distrutte.
>
> Domanda: esiste una strategia per l' angelo che impedisce al diavolo di
> vincere?
Si... ma prima vediamo il tuo commento...
> ----
> Osservazioni mie:
> a dispetto della semplicità con cui è formulato, il problema sembra essere
> complicatissimo:
> le prime strategie che mi vengono in mente sono:
> 1) l' angelo sceglie una direzione e cerca di mantenerla. Questa strategia
> fallisce: è sufficiente che il diavolo capisca qual' è la direzione e in
> una zona lontana lungo quella direzione inizi a costruire una trappola.
La piu' triste strategia attuabile... gia'.
> Allora viene in mente quest' altra cosa:
> 2) l' anglo si muove sempre nella direzione in cui la scacchiera è più
> sgombra, cioè dove ci sono meno caselle distrutte. Fallisce anche così:
> basta che il diavolo si metta a distruggere caselle attorno all' angelo in
> un modo casuale ma che alla fine formano un grosso circolo: l' angelo
> cambierà continuamente direzione poichè di volta in volta la scacchiera
> sarà "più sgombra" (anche se di poco) in direzioni diverse. Più in generale
> con questa strategia l' angelo non è al riparo dalla possibilità di tornare
> sui suoi passi e quindi rischia di essere troppo lento e di farsi chiudere.
Uhm... vero.
>
> Insomma l' angelo deve conciliare una buona "velocità" con la possibilità
> di cambiare direzione all' occorrenza e le due cose sembrano escludersi.
>
> Spero di avervi "stuzzicato" abbastanza...
>
Dunque la soluzione e' che l'Angelo, o meglio, l'Angelus, dovra' usare un
ologramma che inganni il diavolo facendogli credere che stia in una
direzione invece che in qll in cui sta andando... pero'... uhm... senti,
ma l'angelo vince? Oppure gioca perche' non ha nulla da fare e non deve
vincere?
---
Blackstorm
*Vicario d'Armi di idf*
Tittums e' il nostro gatto, ed ha le dimensioni di un rotolo di soldini.
Inarcava la schiena e bestemmiava come uno studente in medicina.
(Jerome Klapka Jerome)
E da oggi anche su ICQ! UIN 116647346 (nick: blacks)