Newsgroup: it.comp.giochi.avventure.testuali
Titolo: COME FUNZIONA * I N T A R S I *

Iniziamo dal principio.
BackTracking
I metodi di BT vengono usati per la "risoluzione generale di problemi".
Tali metodi costruiscono degli alberi di obiettivi parziali e li percorrono
(potano(!)) in modo graduale durante la ricerca.
L'albero cresce in modo mostruoso e spesso è necessario servirsi di metodi
euristici, cioè metodi che permettono di eliminare a priori "percorsi"
sicuramente (o probabilisssssssimamente) ciechi (senza uscita).
Facciamo qualcosa di semplice: non ho voglia di spararvi definizioni astruse
e prive di significato anche per chi le ha scritte :-)
Immaginate di dovere scrivere un programma che trovi l'uscita da un
labirinto (tipico compito universitario quando si studia la ricorsione).
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 # 0 0 0 0 0 # # # # # 3 # # # 0
0 0 # 0 0 0 0 0 # 0 0 0 0 # 0 0 0 0
0 0 1 # # # # # 2 # # 0 0 # # # # 0
S # 0 0 0 0 0 0 # 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 # # # # # # # # # E
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 = muro
# = corridoio
S = partenza
E = arrivo (uscita)
1, 2, 3 = bivi
Come potremmo scrivere un algoritmo del genere?
Immaginiamo di poterci sdoppiare!
Ecco che cosa accade in modo schematico.
(I = individio,
Dn = n-esimo doppione,
Dn+1 renderà conto solo a Dn tranne D1 che renderà conto solo a I)
1) I parte da S e arriva al bivio 1
2) I invia D1 verso NORD
    1) D1 comunica a I che non ha trovato l'uscita e si autodistrugge!
3) I invia (un nuovo) D1 verso EST.
    1) D1 arriva al bivio 2.
    2) D1 invia D2 verso NORD
        1) D2 arriva al bivio 3
        2) D2 invia D3 a EST
            1) D3 comunica a D2 che non ha trovato l'uscita e si
autodistrugge!
        3) D2 invia D3 a SUD
            1) D3 comunica a D2 che non ha trovato l'uscita e si
autodistrugge!
        4) D2 vede che non esistono più strade percorribili e quindi,
comunicatolo a D1, si autodistrugge!
    3) D1 invia D2 verso SUD
        1) D2 comunica che ha trovato l'uscita e gli illustra il percorso da
D1 e E!!! Però poi è costretto ugualmente ad autodistruggersi...
    4) D1, tutto contento, comunica a I che ha trovato l'uscita e gli
illustra il percorso da I a E. Anche se non ha fallito, è costretto ad
autodistruggersi :-(
4) I conosce ora la strada che lo condurrà verso la salvezza.
Avrete certamente capito che "sdoppiarsi" significa chiamare ricorsivamente
se stessi, e che autodistruggersi significa ritornare al chiamante :-)
(avevato mai colto questo aspetto così tragico della ricorsione!?)
Ecco un piccolo pseudo codice (lo scrivo di getto quindi potrebbe contenere
errori):
GLOBAL_VAR Percorso                    // globale per semplicità
BOOL FindExit(posizione, direzione)
{
    prosegue finchè incontra soltanto #;     // ovviamente seguendo la
pista!
    aggiorna posizione;
    if (*posizione == vicolo_cieco) return 0;              // uscita non
trovata
    else if (*posizione == uscita)
    {
        aggiorna Percorso;
        return 1;                  // uscita trovata
    }
    // per esclusione, abbiamo un bivio
    for (ogni strada "cur_strada" del bivio)
    {
        if (FindExit(posizione, direction(cur_strada))        // s'intende
se FindExit ritorna 1
        {
            aggiorna Percorso;
            return 1;                                                //
strada trovata
        }
    }
    // se siamo qui non abbiamo trovato alcuna strada...architetto di
merda....:-)
    return 0;
}
Ho deciso di definire la variabile Percorso come globale, in modo da non
complicare il codice con troppi parametri o indirezioni varie...
Il BT può anche essere utilizzato per risolvere il problema delle 8 regine,
problema che Gauss non riuscì mai a risolvere completamente. Ciò è dato dal
fatto che questo genere di problemi sfugge le soluzioni analitiche.
Il problema è il seguente: otto regine devono essere poste su una scacchiera
inizialmente vuota, in modo che nessuna di esse possa essere mangiata (o
possa mangiare le altre).
Pseudo-codice (scritto da Niklaus Wirth [autore del Pascal, linguaggio che
odio con tutto il cuore]):
PROCEDURE tenta(i: integer);
BEGIN
    inizializza la scelta delle posizioni dell'i-esima regina;
    REPEAT fai la scelta successiva;
        IF non è sotto scacco THEN
        BEGIN muovi la regina;
            IF i < 8 THEN
            BEGIN tenta(i+1);
                IF l'esito è negativo THEN togli la regina
            END
        END
    UNTIL la soluzione è raggiunta O non ci sono più posizioni
END
Tutto chiaro?
Qualcuno di voi potrebbe iniziare a pensare che BT (BackTracking) e
RICORSIONE siano equivalenti.
Sbagliato! Il BT usa la ricorsione, ma non s'identifica con essa.
Per esempio, il problema de "La torre di Hanoi" si risolve ricorsivamente e
non mediante il BT.
Il BT fa parte dei metodi che risolvono i problemi per "tentativi" e quindi,
come dice il nome (BT), è costretto a fare "marcia indietro" e provare
un'altra strada finchè non trova quella "giusta" (se la trova).
Il brutto è che questi problemi non possono essere scomposti in
sotto-problemi per il semplice fatto che non abbiamo la certezza di essere
sulla strada giusta finchè non vediamo l'uscita (ripensando al labirinto).
Questo metodo è esaustivo in quando esamina ogni possibilità. Il caso
peggiore si ha quando si percorre l'intero albero prima di trovare l'uscita.
Se l'uscita non esiste (o non è raggiungibile), si ha sempre il caso
peggiore.
Talvolta è possibile introdurre qualche criterio euristico, che dovrebbe
significare "basato sull'esperienza", cioè su dati aggiuntivi di cui
disponiamo.
Per esempio, se tempo fa, con la mappa, siamo usciti dal labirinto in 3
giorni di cammino, è inutile che ora controlliamo anche i bivi più distanti
di 3 giorni di cammino dall'entrata.
Questo ci fa risparmiare tempo, comunque è meglio avere la mappa :-)
INTARSI
Intarsi (crasi dei termini "Intelligent" o "Intuitive" e "Parser"->Parsy) è
un parser ispirato da ECC-Eliza, programma che "dialoga" con l'utente.
Analizzando il file .dat di Eliza, sono rimasto molto deluso: conteneva solo
domande e risposte; niente di più :-(
Allora mi sono chiesto: "Se la sua struttura è così semplice e dà già dei
"buoni" risultati, che cosa succederebbe qualora la complicassimo?"
La seconda cosa che ho notato è che l'uomo (inteso come "essere umano")
raramente usa espressioni che non ha mai sentito: di solito unisce vari
costrutti semplici, in modo da formare un costrutto complesso.
Questo mi ha suggerito di utilizzare una grammatica ricorsiva (e però tale
ricorsività interferisce con il BT).
Facciamo subito degli esempi pratici.
Defininiamo qualche cosa tipo:
[sostantivo]
{
    "automobile"
    "penna"
    "matita"
    "plettro"                    ; ho iniziato a suonare la chitarra
    "pianoforte"                ; lo suono da una vita...
    "chitarra"                    ; non vorrei ripetermi :-)
    "orecchioni"
    "rosolia"                    ; non sono pazzo, voglio dimostrarvi la
potenza di Intarsi :-)
}
[art]
{
    "il"
    "lo"
    "la"
    ; ecc...
}
ora aggiungiamo anche:
[prep]
{
    "di"
    ; ecc...ho fretta
}
[verbo]
{
    [prendi]
    {
        "prendi"
        "raccogli"
        "agguanta"
        "serviti "<prep>
        "afferra"
    }
    [guida]
    {
        "guida"
    }
    [contrai]
    {
        "prendi"
        "ammalati di"
    }
}
e infine:
-[azione]-
{
    [prendi oggetto]
    {
        <prendi>" "(<art>(" "))<oggetto>
    }
}
Piccola Legenda:
[nome] definisce la sezione nome,
<nome> si riferisce alla sezione nome,
"testo" è del semplice testo,
-[nome]- significa che nome è una sezione di "partenza",
( ) - indicano parti opzionali (per esempio gli articoli sono quasi sempre
opzionali: "prendi sasso")
Se ora scrivessimo la seguente frase:
"Afferra chitarra"
Intarsi partirebbe da -[azione]-, l'unica sezione iniziale che abbiamo
specificato finora e inizierebbe a scandire la frase:
dunque, azione, giusto?
sezione "prendi oggetto", cosa abbiamo qui?
<verbo>" "(<art>(" "))<oggetto>
saltiamo alla sezione "verbo"....abbiamo "prendi"
Iniziamo dall'inizio....
"prendi" == "afferra"?
NO, non va bene
"raccogli" == "afferra"?
NO
"agguanta"? NO!
"serviti " ? NO, quindi è inutile stare a controllare anche <prep> :-)
"afferra"? SIIIII, ECCOLO QUA. BENE!
Allora ci rimane: " chitarra" e siamo ritornati alla sezione "prendi
oggetto" e ci manca:
" "(<art>(" "))<oggetto>
" " == " "? Sì, bene.
Adesso ci manca "chitarra" e
(<art>(" "))<oggetto>
Questa parta è opzionale, occhio!
saltiamo a "art":
"il" == "ch"            ; inizio di "chitarra"!
NO!
"lo" == "ch"? NO!
"la" == "ch"? NO!
Torniamo, un po' amareggiati, alla sezione "prendi oggetto" ben consci che
la nostra ricerca può comunque continuare in quanto si trattava solamente di
una parte opzionale :-)
Ci resta "chitarra" e <oggetto>.
E' inutile dire che analizzando la sezione oggetto troveremo "chitarra"!
Intarsi in pratica confronta la frase con la grammatica.
Prende la frase da una parte e la grammatica dall'altra.
No, no semplifichiamo!
Diciamo che la ricorsività serve a ridurne la ridondanza! Ho peggiorato le
cose?
No, intendevo dire che scrivere:
(segue una versione più semplice)
[oggetto]
{
    "monitor"
    "tastiera"
}
[art]
{
    "il"
    "la"
}
[verbo]
{
    [prendi]
    {
        "prendi"
        "afferra"
    }
}
-[azione]-
{
    [prendi oggetto]
    {
        <prendi>" "(<art>(" "))<oggetto>
    }
}
equivale a scrivere (si parte dalla sezione -[ ]-, ricordatevelo sempre!):
-[azione]-
{
    [prendi oggetto]
    {
        "prendi il monitor"
        "prendi la monitor"            ; si proprio così....tra un po' vi
spiego :-)
        "prendi ilmonitor"              ; anche questo!
        "prendi lamonitor"             ; idem!
        "prendi monitor"
        "prendi il tastiera"
        "prendi la tastiera"
        "prendi iltastiera"
        "prendi latastiera"
        "prendi tastiera"
        ; ecc...forse ne ho dimenticato qualcuno
    }
}
Così non è più (nel senso di maggiormente) ridondante? Chi avrebbe mai detto
che la ricorsione servisse anche a comprimere i dati!
Allora, torniamo a noi: "prendi la monitor" non vi piace, vero?
Nessuno vi vieta di suddividere i sostantivi in singolari/plurali e
femminili/maschili.
Es (senza completare le sezioni):
[sostantivi]
{
    [s.singolari]
    {
        [s.s.maschili]
        {
            "monitor"
        }
        [s.s.femminili]
        {
            "tastiera"
        }
    }
    [s.plurali]
    {
        [s.p.maschili]
        {
            "monitor"
        }
        [s.p.femminili]
        {
            "tastiere"
        }
    }
}
[art]
{
    [a.singolari]
    .
    .
    .
    .....come per i sostantivi
}
[art+sost]
{
    (<a.s.maschili>" ")<s.s.maschili>
    (<a.s.femminili>" ")<s.s.femminili>
    ecc.......
}
In seguito ci riferiremo sempre a [art+sost] anzichè direttamente a
[sostantivi] o a [art]. Chiaro?
Qualsiasi cosa schifosa abbiate visto in precedenza, può essere risolta
modificando la grammatica.
Vi mostrerò anche come la grammatica possa essere "contesto-sensitiva".
Vi riporto alcune sezioni:
[sostantivo]
{
    "automobile"
    "penna"
    "matita"
    "plettro"                    ; ho iniziato a suonare la chitarra
    "pianoforte"                ; lo suono da una vita...
    "chitarra"                    ; non vorrei ripetermi :-)
    "orecchioni"
    "rosolia"                    ; non sono pazzo, voglio dimostrarvi la
potenza di Intarsi :-)
}
[verbo]
{
    [prendi]
    {
        "prendi"
        "raccogli"
        "agguanta"
        "serviti "<prep>
        "afferra"
    }
    [guida]
    {
        "guida"
    }
    [contrai]
    {
        "prendi"
        "ammalati di"
    }
}
L'ultima la voglio modificare:
-[azione]-
{
    [prendi oggetto]
    {
        <prendi>" "(<art>(" "))<oggetto>
    }
    [contrai oggetto]                ; non siate pignoli
    {
        <contrai>" "(<art>(" "))<oggetto>
    }
}
Notate l'ambiguità che può crearsi se scrivo:
"Prendi la rosolia"                        ; lurido bastardo!
Intarsi partirà da -[azione]-, quindi attraverserà [prendi oggetto],
[prendi], ecc...giungendo alla conclusione che ciò che l'utente ha voluto
dire è che l'alter-ego "deve prendere la rosolia".
Ma noi volevamo che Intarsi capisse "Contrai la rosolia" e attraversasse la
sezione [contrai oggetto] e così via!
Il fatto è che Intarsi torna sui propri passi SOLO quando vede che la strada
finisce in un vicolo cieco (per esempio si aspetta un articolo e invece si
trova qualcosa che articolo non è).
Se la sezione [contrai oggetto] si fosse trovata prima, Intarsi avrebbe
scelto quella.
La soluzione sta nel complicare la grammatica distinguendo i sostantivi in
"contraibili" e "non contraibili"!        (si dice "contraibile"? Boh....)
L'ultima sezione cambierebbe in:
-[azione]-
{
    [prendi oggetto]
    {
        <prendi>" "(<art>(" "))<oggetto_non_contraibile>
    }
    [contrai oggetto]                ; non siate pignoli
    {
        <contrai>" "(<art>(" "))<oggetto_contraibile>
    }
}
Intarsi, percorrendo la sezione [prendi oggetto], si ritroverebbe davanti a
[oggetto_non_contraibile] e tornerebbe sui suoi passi "conscio" dell'errore
commesso. A questo punto tenterebbe con [contrai oggetto] e finalmente
troverebbe l'uscita (vi ricordate l'esempio del labirinto)?
Certo è difficile fare classi di oggetti "contraebili e non qualcos'altro",
"non contraibili e ciaffabili(?)", ecc...Qui potrebbe aiutare l'utilizzo
della forma:
{ n1 | n2 | n3 }  che significa: n1, n2 ed n3 possono apparire in qualsiasi
ordine purchè appaiano.
Aggiungendo qualche parentesi, poi...... {(n1) | (n2) | (n3)} comunque la
cosa si fa tosta!!!!
Non ho proprio pensato ad aggiungere un operatore OR, comunque nessuno ha
mai detto che gli operatori fossero definitivi. Se volete, potete aggiungere
quello che vi pare, ovviamente stavolta occorre modificare il codice...
INTARSI - PROBLEMATICHE - SOLO PER I CORAGGIOSI
Intarsi presenta un problema piuttosto singolare.
Stiamo cercando di applicare il Back Tracking, metodo ricorsivo, alla
scansione di una frase la cui rappresentazione è anch'essa ricorsiva. Ops!
Riuscite a intuire il problema?
Il Back Tracking impone che si vada sempre avanti, cioè che si scenda sempre
più in profondità tutte le volte che si avanza nell'analisi e che
s'indietreggi SOLO in caso di errore, cioè di tentativo fallito, di vicolo
cieco, insomma.
Una frase ricorsiva invece, ci costringe a percorre l'albero della
grammatica in modo del tutto diverso. Quando s'incontra un riferimento
(indicato con < >) si salta da un nodo all'altro in modo assolutamente
repentino e già il BT inizia a urlarci frasi oscene; quando poi percorriamo
l'albero della grammatica a ritroso senza aver incontrato vicoli ciechi, il
BT ci manda letteralmente a f.......
Quando si iniziano a esaminare i membri di una sezione, si scende in
profondità nell'albero e fin qui, nessun problema. Se tale membro ha
soddisfatto completamente le nostre richieste, Intarsi tirerà dritto e
ritornerà al chiamante (risalendo a livelli più superficiali) che a questo
punto continuerà l'analisi da dove l'aveva lasciata (per esempio, dopo
<verbo>, inizierà l'analisi di <art>). Se ora Intarsi trova un vicolo cieco,
che cosa fa?
Ma è ovvio: ritorna al chiamante e gli dice che la strada non è corretta! Ma
questo E' SBAGLIATO!!! Forse il membro che abbiamo percorso in precedenza
non era l'unico corretto! Forse se ne avessimo scelto un altro, a questo
punto non avremmo incontrato il vicolo cieco e saremmo ritornati al
chiamante con una buona notizia :-(
Il problema è che la grammatica è rappresentata da un albero che viene
percorso continuamente in entrambe le direzione (verso le foglie e verso la
radice) quindi non "ricorda" la nostra posizione. Quando abbiamo finito di
esaminare il membro di cui parlavamo prima, siamo ritornati e abbiamo detto
che andava tutto bene (gli altri 80 membri non li abbiamo neanche guardati).
Ritornando, abbiamo cancellato dalla stack il nostro percorso. A questo
punto se più avanti ci accorgiamo che era necessario controllare altri
membri, come facciamo a riteletrasportarci nell'esatta situazione nella
quale ci trovavamo in quel preciso momento?
Bisogna duplicare lo stack!!!
Se duplichiamo lo stack, Intarsi percorrerà tutta la grammatica e facendo
questo eseguirà vari pop dallo stack. Se giunto alla fine la strada è un
vicolo cieco, nessuna paura, abbiamo lo stack duplicato pronto per
ripercorrere un'altra volta l'intera strada, questa volta scegliendo un
altro membro :-)))))
Avete capito che scegliere un membro anzichè un altro cambia anche le
interpretazioni future per il fatto che avendo lunghezze diverse incrementa
il puntatore cur_str a valori diversi?
Facciamo finta che la frase sia:
"coccodrillo per"
e i membri abbiano il seguente ordine:
"cocco"
"coccodrillo"
Verrà scelto "cocco" in quanto "cocco" è uguale a "cocco"(drillo), però in
seguito "drillo" non potrà più essere interpretato correttamente perchè la
grammatica si aspetterà "per"!!!
Il problemone è che il metodo della duplicazione dello stack è inattuabile
perchè ad ogni passo lo stack raddoppierebbe letteralmente.
Sapete quanto vale 2^50? Dopo 16 passi lo stack sarebbe lungo 2^16 cioè
65536 DWORDs (65536*4 bytes), dopo 24, 16777216, ecc.....
Come ho risolto il problema?
Ma con l'euristica ovviamente :-)
Ho pensato che il caso più probabile nel quale possa verificarsi tale
"ambiguità" si ha quando due membri iniziano con le stesse sub-stringhe.
(proprio il caso di "cocco" e "coccodrillo") La prima soluzione alla quale
ho pensato è stata quella di ordinare i membri lessicograficamente
(alfabeticamente), ma ho desistito (troppo limitativo e noioso).
Allora ho pensato di esaminare TUTTI i membri e di scegliere quello che ci
porta più lontano, cioè che incrementa di più il puntatore cur_str. (tenete
presente che i membri possono contenere anche riferimenti ad altre sezioni,
ecc...quindi il discorso è più complicato di come sembra, comunque questo
metodo sembra funzionare).
In pratica avremmo scelto "coccodrillo" perchè è più lungo di "cocco".
La complessità di Intarsi senza euristica? Avete mai visto un albero di
alberi?
Siete ancora vivi?
In quest'ultima parte non sono stato molto chiaro, ma avrei dovuto scrivere
un libro solo su questo argomento :-)
P.S. Mi ricordo di aver fatto un errore (niente di grave comunque) da
qualche parte in questo messaggio, ma adesso non lo trovo più e sono stanco
morto (ore 1:50 di notte).
Kiuhnm

 (alfabeticamente), ma ho desistito (troppo limitativo e noioso).
L'ordine deve essere lessicografico (alfabetico), ma inverso in modo che
"coccodrillo" preceda "cocco".