Newsgroup: it.comp.lang.c
Titolo: IL PROBLEMA DELLO GNAMMY INTELLIGENTE IN C

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

che e' il suo unico mezzo di sopredavvivenza ?
Bella vita girare come una mosca senza testa in una matrice 9x9 e cibarsi di 
pizza per l'eternita'... :-)
Scherzi a parte, perche' questo Gnammy dovrebbe preferire la "vita" alla 
"morte"?

xche deve essere la sua direttiva primaria sopravvivere e la vita per
lui deve essere il discriminante fra una serie di mosse corrette
(quelle che lo portano a nutrirsi) e quellew errate che gli fanno
tirare le cuoia


tirare le cuoia
Beh si', il problema che volevo porre era questo: finche' non crepa lo Gnammy 
non ha niente da imparare, mentre quando crepa e' gia' troppo tardi! 
Personalmente trovo piu' facile pensare a questa sfigata creatura come ad una 
specie di Tamagochi che qualcun altro cerca di tenere in vita il piu' 
possibile! Cio' detto, non ho idea di come risolvere il problema pero' un 
approccio che considererei e' questo: supponiamo che lo Gnammy abbia solo 2 
mosse per vita, appena sufficienti a sopravvivere. Dalla casella iniziale ci 
sono 8 possibili destinazioni, ed altre 8 per ognuna di queste: adesso
ci sara' un numero X di caselle raggiungibili, di cui solo una garantisce la 
sopravvivenza: se lo Gnammy arriva sulla pizza bene, se no elimino tutti i 
percorsi che arrivano all'ultima casella (o anche, per essere piu' onesti, 
solo il percorso effettivamente seguito ma in questo caso si impara piu' 
lentamente) visto che arrivare li' ne ha causato la morte... ma con 20 mosse a 
disposizione le cose si complicano notevolmente! Inoltre il fatto che lo 
Gnammy risuscita in posizione casuale gioca molto a sfavore, perche' anche 
supponendo che a quel punto abbia imparato dove si trova la pizza si reca 
sulla casella "giusta" e rimane a bocca asciutta, ma a questo punto ha 18 
mosse per esplorare 80 caselle e dato il fattore casuale c'e' ben poco da 
fare...
P.S. Si puo' fare che al termine delle 20 mosse lo Gnammy si addormenta solo? 
:-)

Ma, senti, io pensavo, ma non ero stato tanto chiaro nel dirlo, che
nel nostro caso lo gnammy quando rinasce possa avere memoria della sua
precedente (disastrosa o meno) esperienza.
Inoltre mi e' stato detto che la cosa + logica sarebbe far si che lo
ganmmy assegni alle caselle un certo peso a seconda se quel percorso
lo ha fatto arrivare alla pizza oppure morire.
Dopo un certo numero di generazioni lo gnammy dovrebbe avere dato i
pesi giusti a tutte le caselle, il problema ora pero' resta.. come
fargli capire che la pizza si sposta dopo che lui l'ha mangiata ?


Hemmm... scusate se mi aggiungo solo ora ma ci ho messo un po' a fare mente
locale...
quello che non ho capito io e': ma lo gnammy lo sa come funziona il gioco?
voglio dire, la "pizza" una volta magnata si sposta non in modo casuale ma
in modo preciso, allora supponiamo di far muovere lo gnammy inizialmente non
in modo casuale ma in modo ragionato.
Cioe': io comincio a passarmi la 'colonna' in cui mi trovo finche' non
ritorno alla posizione precedente meno una casella, da li' mi sposto di una
casella a destra (o a sinistra) e procedo cosi'.
Siccome lo gnammy ha 20 punti salute, dopo due colonne decede, ok, tutte le
caselle passate sono memorizzate, quindi io riparto ESCLUDENDO tali caselle
dalla 'lista', cio' significa che se sono nella stessa colonna di prima mi
sposto a destra e poi procedo in su o in giu' (insomma un po'
cervelloticamente).
Siccome la griglia e' di 9 x 9 ci vogliono 5 vite per girarla TUTTA,
supponendo uno gnammy mostruosamente sfigato.
A questo punto ho trovato la pizza.
Bene: siccome questa si rigenera sempre in modo 'standard', mi basta
spostarmi sempre di 2 caselle in diagonale per ritrovarla *sempre*. Quindi
se sta' bestia SA come si muove la pizza, dopo la prima 'debacle' si mangia
una pizza ogni 2 mosse.
Nell'ipotesi invece che questo NON SAPPIA che la pizza e' li, e' evidente
che il metodo migliore e' quello di ripulire tutta la matrice di caselle
'passate' e ripartire da 0. Detto questo mi pare ovvio pero' che se lo
gnammy si muove verso il basso e verso sinistra trovera' la pizza entro la
sua vita successiva (ma questo lo sa' l'umano che ha fatto il programma e
non la belva).
Ma esattamente lo scopo di questo test quale e'? fare ammattire tutti quelli
del NG?
Davide

Caro Davide la tua versione non mi sembra male, ma come la
implementeriesti ? Inoltre forse in questo modo lo gnammy necessita'
di un numero troppo grande di assiomi dati per scontato mentre
nell'idea originale dovrebbe essere un povero esserino dotato di
relativamente modesta intelligenza che dopo aver provato varie volte
l'oscura via della morte cominica a sviluppare un certo istinto di
sopravvivenza.
Comunque acnhe la tua idea non e' male secondo me.
Si, lo scopo di questo problemino e' proprio quello di far ammattire
la gente, o meglio quello di far valutare problemi non standard (del
tipo come si pulisce lo schermo) !


Un'altra cosa Davide, il tuo approccio al problema funzionerebbe
certamente ma supponendo di visualizzare il problema in termini di
albero decisionale, il tuo gnammy troverebbe la pizza al 100£ solo
dopo aver esplorato tutte le possibili istanze lungo l'albero, ma
questo sarebbe un po' come affrontare il problema delle 8 regine
provando tutte le possibili disposizioni delle 8 regine sulla
scacchiera (in modo che nessuna dia scacco all'altra) mentre il
requisito primario dello gnammy dovrebbe essere quello di non dover
ripartire da zero nella sua valutazione della nuova situazione in cui
si viene a trovare il suo mondo dopo che lui ha mangiato la pizza e
questa e' riapparsa shiftata di due a sx e due in basso (o qualcosa di
simile)...ma il bello e' proprio che originariamente lo Gnammy non sa
che la pizza si comporta in questo modo una volta mangiata !!! e
proprio qui sta il difficile.... ah, una cosa, non e' che io abbia
gia' trovato la soluzione e mi diverto sadicamente a proporvi il
problema..il bello e' che una soluzione definitiva che porti alla
implementazione secondo le specifiche richieste non l'ho trovata
nemmeno io, ma ci sto lavorando insieme a voi e a qualche amico.
Possiamo farcela a dominare la testolina dello gnammy forza forza !!!!
A proposito... voi che dite, se la matrice vine rappresentata
effettivamente come una matrix[9][9] quindi con indici da 0 a 8...
potrebbe forse convenire usare due matrici ..una per rappresentare la
posizione di gnammy e lo status attuale del suo mondo e l'altra
(perfettamente corrispondente) che rappresenta i "pesi" delle singole
posizioni.. voi che ne dite ?
Ma resta il gran problrema di far capire a gnammy come si sposta la
pizza..ma mi sembra che gia' finora abbiamo fatto dei passi avanti e
siamo in grado forse di implementare la parte riguardante la prima
ricerca della prima pizza.


 "morte"?
No, è solo che gli piace la pizza! :-)
--
Alessandro Monti

 non ha niente da imparare, mentre quando crepa e' gia' troppo tardi!
Si potrebbe fargli imparare geneticamente: vi sono 100 stanze, con i
rispettivi gnammy. Ognuno ha strategie diverse, immutabili e decise a
priori. Dopo la prima serie di mosse, gli gnammy rimasti vivi vengono messi
in competizione (a coppie o anche più, girone all'italiana o quello che
volete). Chiaramente il primo classificato è quello che funziona meglio (ha
"imparato" di più).
Se poi ripeti 100 volte queste prove, ricavi una buona fiducia nello gnammy
vincitore (o gli gnammy vincitori).
--
Alessandro Monti

priori. Dopo la prima serie di mosse, gli gnammy rimasti vivi vengono messi
La tua idea potrebbe anche funzionare, ma come ricordavo il problema
oltre che essere teorico deve anche essere risolto realizzando un
programma in C... come faresti a rappresentare la situazione ? Che
tipi di dato sceglieresti ? Il tuo approccio al problema lo trovo
molto originale e probabilmente migliore di quelòlo basato dsui
differenti pesi da dare  alle caselle... ma cher tipi di
rappresentazioni di dati suggeriresti di usare ?


 ricerca della prima pizza.
Beh, per fargli capire come si sposta la pizza si potrebbe fare una
cosa del genere: una volta trovata la prima pizza, si memorizzano le
coordinate e si cerca la seconda. Una volta trovata la seconda, si
confrontano con la prima:
x2 = x1 - 2
y2 = y1 - 2
poi si confrontano le coord. della terza con qualle della seconda:
x3 = x2 - 2
y3 = y2 - 2
e cosi' via...
Stabilito il numero di campioni necessari, si potrebbe fare una media
dello spostamento x e y dalla posizione precedente.
--
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it

dello spostamento x e y dalla posizione precedente.
Si, ma allora cominciamo a venire al sodo del problema ..che tipo di
strutture dati consiglieresti per implementare in C lo sfigato mondo
dello gnammy ?


 rappresentazioni di dati suggeriresti di usare ?
Direi che ogni strategia è un algoritmo pre-confezionato (o generato in
qualche modo) e numerato (per comodità).
Il numero ti serve solo come indice in modo da sapere quale strategia ha
vinto, e probabilmente corrisponderà con il numero di gnammy (o li vuoi
chiamare per nome?).
A questo punto, a parte la fatica di scrivere 100 strategie diverse o una
sola molto parametrizzata, il gioco è fatto. Ogni gnammy sarà un record del
tipo:
struct{
    int strategia;
    int salute;
    int x,y;
}
E non ti serve nient'altro che una funzione che, dato lo gnammy e la
posizione della pizza (che puoi includere per comodità nella strucu dello
gnammy), puoi decidere ogni passo.
Ah, probabilmente ti serve avere un contatore globale dei passi, e strutture
varie per raccogliere le statistiche.
Non sarebbe probabilmente male inglobare tutti gli gnammy "vivi" in una
lista. (a parte il fatto che risorgono subito).
Potresti anche fare in modo che ogni gnammy, una volta risorto, finisce in
fondo alla lista. Oppure conti semplicemente lo gnammy che ha punteggio più
elevato (probabilmente quello che ha imparato di più). Oppure aggiungi un
"contatore di morte" nello gnammy.
Le varie strategie potrebbero essere:
vai sempre a dx
vai sempre a sx
....
vai 1 a dx e poi 1 in alto (e ripete)
vai 2 a dx e poi 2 in alto
....
e così via all'infinito.
Nota che ogni strategia può essere codificata con un numero variabile di
bits. Ovvero:
Numeri le direzioni (4 se si muove solo ortogonalmente, 8 se sono ammesse le
diagonali, il che significa 2 o 3 bits per direzione).
Lo gnammy che va sempre a dx ha 2 bit che valgono (ad esempio) 00
Lo gnammy che va sempre a sx ha 2 bit che valgono (ad esempio) 01
Lo gnammy che va 1 a dx e 1 a sx ha 4 bit che valgono (ad esempio) 00 01
....
Lo gnammy che 1 a dx, 4 a sx ha 10 bit che valgono (ad esempio) 00 01 01 01
01
....
La cosa può essere interessante perchè:
- ogni strategia ha un numero ordinale molto preciso, nessun bit va sprecato
- questa codifica può essere paragonata alla codifica dei geni naturali
(quelli del DNA), per cui sono possibili anche operazioni di "riproduzione",
come in tutti gli algoritmi genetici, dando così anche un solido fondamento
teorico a questa soluzione.
Nota che potresti anche ampliare il dominioin molti modi.
Uno (facile) che mi viene in mente è il seguente: immaginiamo che
probabilmente il fatto di essere già morto (o di avere la salute sotto una
certa soglia) sia importante.
Possiamo codificare il tutto immaginando di avere 2 cromosomi: 1 per la
situazione "buona salute" e l'altro per "cattiva salute". A questo punto, ad
ogni passo devi seguire le mosse di un cromosoma o dell'altro a seconda
dello stato di salute del povero gnammy, e quindi aumentare notevolmente le
sue capacità di apprendimento.
Purtroppo, aumentando la complessità delle strategie possibili, aumenti
anche di molto la complessità del programma. La codifica della strategia
potrebbe non essere più contenibile in un int. Il fatto di avere N
cromosomi, implica che devi avere un array di strategie. Il fatto di avere
così tante possibilità implica anche che non ti bastano più le 100 arene che
avevo previsto, ma devi averne almeno tante quante sono gli gnammy, e
oltretutto devi ripetere molte volte i cicli in modo tale da dare qualche
possibilità allo gnammy che nasce in un punto a caso e pertanto non può
applicare la sua strategia, anche se fosse buona.
Spero di averti dato delle buone dritte, di più penso che potrei solo
scriverti io il programma, ma proprio non posso dediccarti tutto questo
tempo. Se fossi in te mi limiterei ad 1 solo cromosoma e a codificare circa
4 mosse. Non basterebbe a gestire la situazione del superamento del bordo, a
meno che i bordi non siano "atrraversabili", ma per iniziare credo che
basti. Probabilmente, se tutto ciò riesci a programmarlo e funziona, ti
sarai già stufato dello gnammy e ti dedicherai a cose più interessanti.
Ricordati solo di postarle dove questi problemi sono trattati, e cioè su
it.comp.ia, dove rimando ogni risposta.
--
Alessandro Monti

Ho risposto, spero definitivamente, su it.comp.ia, dove il problema è
pertinente, e sopratturro, esiste già.
--
Alessandro Monti

 

Mah, cosi' su due tasti ;-) mi vengono in mente solo alcune cose:
- una matrice per la posizione della pizza
- una matrice per il simpatico ma sfigato esserino
- un array per le precedenti posizioni della pizza, di dimensione da
  definire
