Newsgroup: it.hobby.enigmi
Titolo: L'angelo e il diavolo [SOL]

Weekend piovoso, dalle mie parti. E allora PC.
Avrei la presunzione di aver risolto il quesito proposto
da LordBeotian. Poiche' la cosa e' contro corrente, cioe'
si legge qua e la' in rete e su riviste che il problema e'
irrisolto e forse irrisolvibile, un po' di prudenza non
guasta. Chiedo quindi a questo dotto NG se qualcuno ha voglia
di torchiare la mia soluzione con il max senso critico.
Il problema, per quelli a cui fosse sfuggito, e' il seguente:
Un angelo scappa su una scacchiera infinita avendo a disposizione
la mossa del Re degli scacchi: una casella alla volta in ogni 
direzione. Un diavolo cerca di intrappolarlo potendo distruggere 
una qualunque casella alla volta, eccetto quella su cui si trova
l'angelo. La domanda e': esiste una strategia che consenta 
all'angelo di scappare all'infinito?
La mia risposta e': NO, perche' esiste almeno un algoritmo che
permette in ogni caso di intrappolare l'angelo.
Per rendere la cosa interessante ho messo l'algoritmo in un
automa di un video-game, dove potete provare a sostenere la 
parte dell'angelo. Il programma si trova qua nella versione
completa di Setup su Windows [1.38 MBytes]:
http://members.theglobe.com/liviozucca/download/demon.zip
Oppure qua per coloro che sono compatibili con VB5.0 
[13 KBytes soltanto]:
http://members.theglobe.com/liviozucca/download/demonvb5.zip
A disposizione per qualunque problema incontraste.
Ciao a tutti    :o)
Livio Zucca
-------------------------
Giu' le mani da internet!
http://www.geocities.com/liviozuc
-- 
Posted from 
mta15-acc.tin.it
 [212.216.176.46] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Ciao Livio,
Non mi riesce assolutamente di battere il tuo automa in quanto si impegna a
costruire un reticolo  e sbarra la strada quando mi avvicino, secondo me é
imbattibile, ora il discorso sta tutto nel minimizzare il numero di mosse
che permettono di far vincere il diavolo, infatti il gioco si fa su una
scacchiera infinita, per quanto riguarda la soluzione del gioco basterebbe
fare il reticolo vincente sulla piů piccola figura che permetta la vincita
in ogni caso.
GDR

......anziché fare la trappola quadrata, risparmieresti mosse se la faresti
pseudo-circolare, comunque ancora non sono riuscito a capire la minima
dimensione di trappola funzionale come posso trovarla, il fatto é che
bisogna stare lì a farsene l'avvocato dell'angelo per capire il metodo che
più mette in difficoltà il diavolo, sono quasi certo che la migliore
strategia (per l'angelo) é quella di muoversi sempre nella stessa direzione
fino a che non viene sbarrata la strada con degli occhialini.....quindi la
migliore é(per il diavolo):
COSTRUIRE UN MURO FORATO IN DIREZIONE DI MOVIMENTO DELL'ANGELO, stando
attenti a mettere i mattoni  prima nelle parti più raggiungibili
dall'angelo, il diavolo inoltrre deve prendere in ipotesi di ridurre le
dimensioni della trappola quando la posizione dell'angelo lo permette, così
secondo me si arriva a vincere anche su una porzione di reticolo ben minore
dei 25*25 quadratini.
GDR

 permette in ogni caso di intrappolare l'angelo.
Sicuramente hai ragione, l'algoritmo esiste. Nel tuo bel programma perņ si
verifica un bug nello schema 25x25.
Se infatti l'angelo percorre la diagonale SudOvest (premendo sempre '3')
fino ad arrivare nei pressi dell'angolo, alla fine riesce sempre a scampare
al diavolo. Cmq basterebbe perfezionare l'algoritmo, rendendolo sensibile
alla direzione presa dall'angelo.
Ciao (;-)
Francesco

 alla direzione presa dall'angelo.
Giocando angelicamente sono riuscito a superare anche il quadrato 65x65,
percorrendo i primi 26 passi verso NE e i successivi verso NW.
A parte i possibili perfezionamenti comunque, mi pare che non si possa
ancora affermare che l'angelo abbia vinto (sulla scacchiera infinita).
Infatti, una volta che l'angelo è uscito dal quadrato, il gioco continua con
il diavolo che si trova in una situazione certamente migliore rispetto a
quella iniziale. Infatti Satanasso può costruire un nuovo quadrato adiacente
al primo, e dal momento che l'angelo non vorrà suicidarsi rientrando nel
quadrato iniziale, il diavolo dovrà lavorare solo su tre lati, aumentando il
ritmo di produzione (o di distruzione), e quindi può (forse) compensare
eventuali bug del primo tentativo.
Si tratta di verificare se la posizione diabolica migliora con continuità,
all'uscita di ciascun quadrato, o se a un certo punto si arriva ad una
situazione di stallo.
ciao
paolo

Ho testato il tuo programma e fino a 57 di lato l'angelo riesce a scappare; ho letto in seguito che anche con 65x65
l'angelo vince, ma la tecnica di Paolo è identica e dunque il ragionamento che segue non cambia:
- Con quadrato 57x57 e considerando l'angolo superiore sx = (1,1) -
Direzione 7 fino a (6,6) poi direzione 9 fino al perimetro.
Penso che il tuo algoritmo sia estremamente ben fatto ma potresti cercare di ridurre il quadrato minimo necessario
concentrando il riempimento del diavolo sull'angolo preso di mira dall'angelo.
Dato che l'unica strategia vincente per l'angelo è appunto dirigersi in diagonale verso uno degli angoli hai il
vantaggio di non dover riempire immediatamente l'angolo opposto, sprecando mosse preziose.
Il tuo algoritmo, direzione 7 mossa 4, riempie inutilmente l'angolo (57,57).
In seguito il diavolo continua la sua opera sull'angolo opposto invece di considerare "pericoloso" l'avvicinamento
dell'angelo all'angolo (1,1).
Arrivati alla mossa 20 il diavolo ha sprecato 5 mosse sull'angolo (57,57), un vantaggio decisivo per l'angelo.
Con quadrati sotto il 49 di lato penso non ci siano speranze per il diavolo, perlomeno considerando solo il primo
quadrato di perimetro.
Un bel UNDO permetterebbe di testare varianti senza ripartire dall'inizio, ma forse chiedo troppo! :-)
Sei stato geniale, complimenti!
Ciao
LW

Ringrazio tutti quanti dell'interesse e dell'impegno, che non mi 
aspettavo gia' nella notte stessa!
DEVO ALCUNE PRECISAZIONI:
=========================
1) Considero l'algoritmo imbattibile per lati superiori a 137 caselle,
anche se, nelle attuali condizioni della R1.0 non sono mai riuscito a
battere la versione con 81 caselle di lato.
2) Usando il tastierino numerico abilitato, le partite si possono
svolgere molto velocemente. Per l'Undo dovrete attendere la versione
shareware :o) Tenete conto che il programma e' nato in una notte e
l'algoritmo in due.
3) C'e' un bug che abortisce il programma ma solo per lati piu'
piccoli di 50. Correggero'.
4) In opzione 2 Players potete giocare in due manualmente e abbastanza
agevolmente se l'angelo usa il tastierino e il diavolo usa il mouse.
CONSIDERAZIONI SULL'ALGORITMO:
==============================
Non e' il primo algoritmo che mi e' venuto in mente. Non ho cercato
la max compattezza, ma la dimostrabilita' matematica.
1) Ho scelto il quadrato perche' e' la superficie con il minimo
perimetro. Non e' il cerchio perche' la mossa in diagonale dell'angelo
passerebbe tra due caselle distrutte in diagonale.
2) Ho sperimentato e poi scartato l'analisi della direzione dell'angelo
o addirittura delle sue intenzioni. Sono indeducibili. Ogni mossa
nuova dell'angelo non e' influenzata dalla storia. Conta solo la
posizione istantanea da cui l'angelo puo' prendere nuove decisioni.
3) Ho affrontato prima l'algoritmo che permette di non far superare
all'angelo una retta prefissata dal diavolo. I metodi possono essere
tanti, bisogna solo cautelarsi dall'attacco in diagonale. L'algoritmo
che ho adottato permette di sbarrare la strada all'angelo da una
distanza minima di 8 caselle. E' basato sulla costruzione di un muro
traforato con il riempimento dei buchi per distanze entro le quattro
caselle.
4) Risolto il problema dell'arresto su una retta, sembrerebbe 
sufficiente chiudere l'angelo tra 4 rette. In realta' gli angoli
diventano un tallone di Achille. Allora ho pensato di fare
un quadrato abbastanza grande in modo da fortificare gli angoli
per QUALUNQUE mossa dell'angelo piu' lontana di otto caselle dal
bordo. Ecco perche' il quadrato DEVE essere grande. Fortificando
gli angoli con una distruzione 8x8 si ha la matematica certezza
di bloccare l'angelo. Per fare cio' serve un quadrato:
8+15x4+1+15x4+8=137 caselle di lato. In realta' alcuni trucchetti
permettono gia' di ridurre questa dimensione.
EVOLUZIONI.
===========
Se ci saranno ulteriori versioni e correzioni di bugs, le faro'
solo sul file demonvb5.zip [13KB] che genera Demon.exe che si
puo' sostituire semplicemente anche a quello prodotto dal
setup completo di 1.38 MB.
Trattandosi di hobby fatto di entusiasmo, come al solito non
riusciro' a prendermelo come impegno  :o)))
Ciao a tutti e grazie :)
Livio Satanasso
PS: e' uscito il sole.
-- 
Posted from 
mta23-acc.tin.it
 [212.216.176.76] 


 caselle.
Mi pare che sia sufficiente una distanza di 5 caselle (6 caselle
considerando sia la posizione dell'angelo sia quella della retta).
L'angelo è bloccato se si trova (in proiezione) al centro di un blocco di
tre caselle consecutive distrutte.
Consideriamo una retta orizzontale, indico solo le ascisse di Angelo e
Diavolo:
1 : A1, D1
2 : A2, D2 (se 2:A1 ...D2, se 2A0 ...D0; le posizioni sono equivalenti salvo
riflessioni o traslazioni)
3 : A3, D4 (se 3:A2...D3, se 3:A1...D0, e in entrambi i casi l'angelo è
bloccato)
4 : A4, D5 (se 4:A3 o 4:A2... D3 e l'angelo è bloccato)
5 : A5, D6 (oppure 5:A4 o 5:A3...D3; l'angelo è comunque bloccato)
in sostanza l'angelo è bloccato al max in 5 mosse, pertanto l'algoritmo di
chiusura della retta può iniziare da una distanza di 5 caselle.
In questo modo sarebbe sufficiente un quadrato 101*101: modifico un po' il
tuo algoritmo, operando così:
Nelle prime 44 mosse il Demone chiude i 4 angoli in questo modo (11 caselle
per ciascun angolo)
._ _ _ _ _ _ _ _ _ _ _ _ ...
|_|_|_|_|_|D|_|_|...
|_|_|_|_|_|D|_|_|...
|_|_|_|_|_|D|_|_|...
|_|_|_|_|_|D|_|_|...
|_|_|_|_|_|D|_|_|...
|D|D|D|D|D|D|_|_|...
|_|_|_|_|_|_|_|_|...
|_|_|_|_|_|_|_|_|...
|_|_|_|_|_|_|_|_|...
...
...
realizzando quattro rettangoli 6*89, con i lati minori bloccati.
Il *rovesciamento* degli angoli rende i quattro rettangoli indipendenti; non
so se la cosa sia necessaria, ma certamente male non fa.
All'angelo occorrono almeno 44 mosse per raggiungere un rettangolo, quindi
l'opera diabolica sarà comunque completa.
Una volta che l'angelo è nel rettangolo, il demone parte con l'algoritmo di
chiusura della retta.
______________
Trovata la dimostrazione che su questo piano le forze del male vincono,
provo a rilanciare (non picchiatemi :-)
Sappiamo che Angeli e Diavoli sono alati, quindi:
in una scacchiera tridimensionale infinita......
ciao
paolo

 > aspettavo gia' nella notte stessa!
Avrei voluto partecipare anch'io, anche per verificare
l'affermazione dello stesso Conway, dice che se l'angelo
adotta una strategia a spirale non dovrebbe correre grossi
rischi, ma purtroppo non riesco a scaricare il tuo
programma, mi arriva un "filino" da 6 Kb indezippabile (si
puo' dire?).
ciao :) dario

 alla direzione presa dall'angelo.
Non č detto!!
Per dimensioni troppo piccole del quadrato il diavolo non puņ far nulla per
fermare l' angelo!! Puņ non esserci alcun modo per perfezionare l'
algoritmo in modo che vinca nello schema 25x25!
Ciao
Marco

 aspettavo gia' nella notte stessa!
Ciao Livio!! Complimenti, è bellissimo il tuo programma!
Non è affatto difficile convincersi che il tuo algorritmo è imbattibile in
un quadrato abbastanza grande da consentire di tappare i 4 angoli per
(diciamo) almeno 20 caselle in cascuna direzione (cioè 40 per angolo [sto
facendo una stima rozzissima]) prima che l' angelo sia a meno di 10 caselle
di distanza dal bordo.
Credo che tu abbia risolto il dilemma: vince il diavolo, contro ogni
aspettativa!! (Ci si potrebbe chiedere cosa accadrebbe raddoppiando la
velocità dell' angelo o triplicandola... io ho il sospetto che non sia una
questione di velocità: il diavolo probabilmente vince sempre col tuo
algoritmo o con qualcosa di simile, a patto di prendere un quadrato
abbastanza grande.)
Se vuoi poi ti dico qual' era la rivista di matematica che proponeva il
gioco, ora non ricordo, dovrei andare in biblioteca.
Ciao e complimenti!!
Marco

ciao :) dario
.
Ciao Dario,
se mi dai qualche indizio in piu'
provo ad aiutarti.Ho riprovato i download ora e tutto e' andato bene.Se hai
l'ambiente VB5 posso spedirti il file da 13KB direttamente in attach con
una email. Se no posso anche spedirti l'altro, ma mi devi autorizzare
altrimenti rischio di intasarti l'email (1.38MB). Lo zip e' WinZip.
Theglobe.com di solito e' veloce, ma butta spesso molta pubblicita'. Prova
su IE o su Netscape ad abilitare/disabilitare Java, i biscottini, ecc.
Fammi sapere. Posso anche spedirti un FD.
.
Ciao  :o)
Livio
--------------------------------
Inviato via 
http://usenet.iol.it
 


Beh... se non usano una quarta dimensione...
Ci
penso.
