Newsgroup: it.comp.programmare
Titolo: IL PROBLEMA DELLO GNAMMY DIGITALE

Dunque sono davanti ad un problemino informatico che magari per
qualcuno di voi e' una cavolata, ma che mi sta facendo diventare pazzo
!!! Quindi se qualcuno mi da una manina mi farebbe moooolto felice !
Allora, il problema e' il seguente:
cosrruire un software (in qualsiasi linguaggio, ma a me interessa il
provedimento teorico) che simuli il monmdo dello Gnammy che ha le
seguenti caratteristiche:
Una matrice 9 x 9 con all'interno una creaturina (lo gnammy appunto)
che deve muoversi in modo casuale all'interno della matrice occupando
sempre una sola casellina; ora lo gnammy dispone di 20 punti salute e
ogni mossa che fa ne perde uno, quando arriva a zero (quindi dopo
venti passi) muore.
All'interno della matrice l'unica speranza di vita e' una pizza che si
trova sempre ferma nella stessa posizione (che all'inizio della
simulazione viene decisa in modo casuale); quando lo gnammy capita
sulla casella della pizza se la mangia tutto contento e la sua salute
se ne torna a 20, a questo punto la puzza appare spostata di due
caselle a sinistra e di due in basso (eventualmente spuntando
dall'altra parte della matrice) e lo gnammy continua a camminare a
random finche' o muore di fame o ritrova la piuzza e cosi' via.
Domanda : supponendo che quando lo gnammy muore risorga in un punto
casuale della matrice (quindi di nuovo con salute 20 e ricominci a
scorrazzare libero, (mantenendo i suoi ricordi delle "incarnazioni
passate") come e' possibile far si che lo gnammy (inizialente
ignorante della propria sfigata condizione) cominci dopo una certa
n-esima generazione a cercare autonomamente la pizza, avendo capito
che e' il suo unico mezzo di sopredavvivenza ?
Grazie dell'attenzione.
Augusto Pucci
Webmaster di Prospektiva On-line
http://go.to/Prospektiva

>...gnammy continua a camminare a random finche' o muore di fame o ritrova
la piuzza e cosi' via.
1) Ma Gnammy può decidere i che direzione muoversi o è casuale?
Se diamo un intelligenza a Gnammy all'inizio si sposterà casualmente ma dopo
un po di tempo inizierà a spostarsi nella direzione in cui presuppone sia la
pizza....
Mi piacciono i "giochini" di I.A. (se così si può definirli...) se ti
interessa nella mia homepage puoi
trovare una versione di Life scrittp in VB.
Una soluzione, affrettata che mi viene in mente i queto momento è che si
potrebbe sfruttare il
principio di località per scegliere la direzione in cui mandare Gnammy.
Praticamente Gammy potrà
sfruttare la sua "memoria" per ricordarsi dove la pizza è comparsa per
l'ultima volta e "pensare" dove potrà ricomparire. Se dopo 50 vite la pizza
non è mai comparsa nella csella [9,9] allora Gnammy assumerà che la pizza
non compaia mai la....
Questa è la soluzione che mi è venuta il mente "al volo"... pensp possa
essere sicuramente migliorata.
Ciao
Nick
-----------------------------------------------------------
E-Mail    : 
nic...@nsoft.it
URL       : 
http://www.geocities.com/blues_nick/
ICQ       : 26032113
-----------------------------------------------------------

Direio che la cosa + furba potrebbe essere far si che lo gnammy
assegni un peso ad ogni casella a seconda se questo percorso o
quell'altro l'ha portato a morte certa, inoltre lo gnammy si comporta
come lo wumpus del mondo dei wumpus nel libro AI: A modern approach di
Russel e Norvig, quindi non conosce a priori dove sia la pizza se non
l'ha trovata ! In altre parole il su KB (base di conoscenza) e'
inizialmente nullo, per cui dando a qualunque casella peso 0
all'inizio lo gnammy si muoive per forza random, ma e' dopo un certo
numero di generazioni che acquisisce esperienza..ma il problema grosso
che resta da risolvere e': come diavolo fara' lo gnammy poi a capire
che la pizza, quando l'ha mangiata riappare spostata di 2 a sx e di 2
in basso ogni volta ?
In altre parole come far si che un agente (come e' lo gnammy) faccia
supposizxioni anche su un ambiente dinamico ? Che originariamente era
completamente ignoto, ma dopo n generazioni divenmta parzialmente
conosciuto.. il problema e' che l'ambiente shifta rispetto alla base
di conoscenzsa dello ganmmy in modo regolare, ma questo lo gnammy non
lo sa !!!!
E poi...che tipi distrutture dati potrebbero servire per implementare
un simile agente ?


Sylver wrote:
Si potrebbero a mio avviso salvare tutte le mosse dello Gnammy. Alla sua
morte si ricordano le ultime *n* mosse (quelle che presumibilmente lo hanno
portato alla morte). Si fa poi in modo che lo gnammy cerchi di evitare di
ritrovarsi nella stessa condizione.
Esempio:
Lista delle mosse (m - movimento; mp - movimento & mangiamento pizza).
m m m m m m m m m m mp m m m m m m m m m m m mp m m m m m m m m m m m m m m
m m m m m m (Muore)
posto *n*=10, la prossima generazione cercherà di evitare di avere 10 m
nelle ultime 10 mosse. Come? mettendoci un mp!
Il primo problema sta nello scegliere *n*... porre *n*<=20 è banale, poichè
lo gnammy si rende conto subito che senza pizza muore e cercherebbe fra
l'altro di abbuffarsi, mangiando almeno ogni *n*-1 turni. Con n>=20 non si
renderebbe invece conto che è la pizza a tenerlo in vita, poichè c'è un mp
nella sequenza delle *n* mosse da evitare (in particolare mp si troverebbe
sempre nelle prime *n*-20 mosse di tale sequenza).
Credo che per avvicinarsi più possibile ad un modello di trial/error, tipico
dell'intelligenza animale, *n* debba essere variabile.
Ad esempio, cominciare con *n* grande, meglio se uguale all'intero ciclo
vitale, e poi ridurlo:
Si confrontano le liste delle morti precedenti con quella dell'ultima morte.
Da un certo punto in poi saranno uguali, e quella è la sequenza da evitare.
Bisognerebbe insomma costruire una memoria delle sequenze fatali (sequenze
di mosse che hanno portato alla morte in altre occasioni). E' logico che nel
caso dello Gnammy essa conterrà solo una sequenza (quella di venti mosse e
nessuna mangiata), ma se ci fosse anche la pizza avvelenata, essa
conterrebbe anche tutte quelle che finiscono mangiando la pizza avvelenata
(tante).
Lo stesso metodo funzionerebbe anche se l'effetto mortale non fosse
immediato (pizza con veleno lento).
Esempio con veleno lento (il veleno uccide lo gnammy dopo 10 mosse).
La prima volta che lo gnammy mangia la pizza avvelenata, muore dopo 10 mosse
(supponiamo che nel frattempo non mangi nessun'altra pizza). Se gli dovesse
nuovamente capitare di mangiare una pizza avvelenata, cercherebbe di evitare
di fare altre 9 mosse, e quindi cercherebbe a) di mangiare una pizza o b) di
mangiare una pizza avvelenata. Morirà lo stesso, ma la sequenza finale
verrebbe aggiunta alla lista di sequenze da evitare.
Finchè lo gnammy non abbia esaurito tutte le combinazioni di mosse dopo
l'assunzione del veleno, la pizza avvelenata non verrebbe evitata in
generale.
Come si fa a far decidere allo Gnammy qual è la mossa migliore da fara per
evitare le varie "sequenze fatali" che ha nella sua memoria gnammosa?
Il metodo più semplice e immediato consiste nel costruire tutte le
combinazioni di mosse possibili a partire dalla attuale posizione dello
Gnammy. Poi si esaminano ad una ad una e si assegna un punteggio di 1 se la
sequenza non porta alla morte dello Gnammy oppure 0 se la sequenza porta
alla morte dello sventurato (ovvero se è uguale ad una delle sequenze fatali
già sperimentate). Lo Gnammy decide poi casualmente fra tutte le possibilità
marcate con "1".
Bisogna anche definire ogni quante mosse lo Gnammy decida cosa fare. La cosa
migliore secondo me è fare in modo che lo Gnammy pensi alla sequenza di
mosse da fare ogni qual volta ci sia un cambiamento ambientale (nel caso più
semplice quando la pizza cambia posizione ossia quando lo Gnammy se la
mangia). Sarebbe infatti inutile ricalcolare tutte le mosse dello Gnammy ad
ogni movimento.
Infine c'è da decidere quanto lunga debba essere la sequenza di mosse che lo
Gnammy decide volta per volta. Anche qui, sarebbe inutile decidere la 7^
mossa se alla 6^ lo Gnammy mangiasse la pizza, poichè ci sarebbe un
cambiamento ambientale. Di conseguenza bisognerebbe di fatto simulare ogni
singola mossa di ogni singola combinazione pensata dallo Gnammy, per andare
alla ricerca di un cambiamento ambientale.
Personalmente sono dell'idea che lo Gnammy dovrebbe perndere decisioni in
maniera leggermente stocastica. In tal caso lo Gnammy non sceglierebbe
sempre la miglior sequenza possibile, ma potrebbe scegliere volontariamente
una sequenza che porti a meno benefici. Ad ogni modo una valutazione 0/1
delle sequenze non si presta a questo gioco e bisogna quindi dare un
punteggio ad ogni sequenza per poi decidere preferenzialmente quella col
punteggio più alto, lasciando però una certa probabilità anche alle
successive.
Altri metodi di valutazione della migliore sequenza di mosse fra tutte
quelle possibili.
Lo Gnammy potrebbe dare un punteggio ad ogni sequenza in base all'energia
che avrebbe alla fine di essa, ma in base al criterio citato prima secondo
cui la n^ mossa è inutile se alla n-1^ lo gnammy mangia la pizza, tutte le
sequenza terminerebbero con energia 20. Bene, la scelta può allora cadere
sulla sequenza più corta (quella che porta lo Gnammy a mangiare la pizza il
prima possibile).
La possibilità di scegliere fra le altre, meno benefiche, possibilità
dovrebbe essere definita con una gaussiana, curva tipica dell'errore casuale
(se siete interessati a questo punto posso fornirvi una trattazione formale
del problema).
sim...@nsoft.it
