Formalizzazione e classificazione dei metodi di decomposizione

Non esiste un modo unico di "decomporre" la ricerca di un albero di gioco: la molteplicità di soluzioni possibili rende necessaria una loro classificazione tale da evidenziare le proprietà di approcci alla decomposizione omogenei. Si considerino a riguardo le definizioni formulate di seguito.

Def. (decomposizione):

Sia A un albero di gioco costituito dall’insieme N={N1,...,Nn} di nodi (interni e terminali); sia inoltre P={P1,...,Pm} un insieme di processori. Si definisce decomposizione di A in P una funzione D: N→P che associa ad ogni nodo di A uno dei processori in P.

Def. (processo esploratore e processo supervisore):

Sia D una decomposizione dell’albero di gioco A nell’insieme P di processori; sia N l’insieme di nodi in A con Ni∈N. Si definisce esploratore (o responsabile) di Ni (secondo D) il

processore D(Ni). Sia inoltre padre:N→N la funzione che associa ad un nodo il proprio predecessore (essa considera il nodo radice padre di se stesso); è definito supervisore di Ni (secondo D) il processore D(padre(Ni)).

Qual è il significato di queste definizioni? La definizione di decomposizione come funzione intende sottolineare che la

valutazione di ogni sottoalbero dell’albero di gioco è "affidata" ad un solo processore chiamato esploratore.

Sia ad esempio (Ni,Pj) una delle relazioni indotte dalla funzione di decomposizione D; si osservi che Ni identifica completamente il sottoalbero Si di cui è radice: il significato della relazione è dunque che il valore minimax (o una sua limitazione) del sottoalbero Si deve essere calcolato dal processore Pj. La valutazione di Si richiede la conoscenza dei valori minimax dei sottoalberi le cui radici sono i successori di Ni: la funzione D definisce un esploratore anche per ciascuno di questi sottoalberi. Sia Ns uno dei successori di Ni e Ps=D(Ns) il rispettivo esploratore: che legame esiste fra i processori Pi e Ps?

È stabilita una dipendenza di Ps nei confronti di Pi in quanto il valore del sottoalbero lui affidato è utilizzato solo da Pi ed è quindi a questo processore che deve rispondere del suo operato. In questo caso Pi viene definito supervisore di Ns ad evidenziare il ruolo che esso assume di gestore del risultato della valutazione di Ns.

La decomposizione di un albero di gioco induce, quindi, una relazione gerarchica fra i processori che può essere descritta da una struttura ad albero. Tale relazione varia dinamicamente (cioè durante la visita complessiva dell’albero) in funzione del rapporto di "parentela" esistente fra i sottoalberi visitati ad un dato istante dai processori. Può ad esempio accadere, infatti, che in una fase successiva della visita sia Pi a dover comunicare l’esito della sua ricerca a Ps

in quanto il sottoalbero da lui visitato è contenuto in quello di cui Ps è responsabile.

Root P4 N32 P3 N31 N41 N42 N35 N36 N21 N22 N23 P1 P4 P3 P2 P3 P1 P2 P2 N33 P1 N34 P2

Fig. 4.19a Decomposizione: associazione nodo-processore

P1: N33→N22→Root P2: N35→N41→N23→N34

P3: N32→N42→N36

P4: N31→N21

Fig. 4.19b Decomposizione: ordine di valutazione dei nodi da parte dei singoli processori

L’albero di gioco di Fig. 4.19a descrive un esempio di decomposizione. I nodi sono etichettati con il nome del processore

responsabile del sottoalbero di cui sono radice. Si osservi come alcuni processori siano

responsabili di più sottoalberi. Ad un dato istante della visita, tuttavia, essi saranno impegnati nella valutazione di al più un sottoalbero. La specifica di una istanza di decomposizione deve quindi essere

completata con l’ordine di valutazione, da parte di ciascun processore, dei sottoalberi di cui esso è responsabile. Tale informazione costituisce la componente "dinamica" del concetto di decomposizione; in Fig. 4.19b ne troviamo un esempio in relazione all’albero di Fig. 4.19a.

Non è in generale possibile stabilire staticamente l’ordine con cui sarà effettivamente completata la visita dei sottoalberi, in quanto legato alle velocità relative dei processori. Tuttavia si intuisce la presenza di punti di sincronizzazione che

scandiscono le fasi della visita: un processore non può completare la valutazione di un sottoalbero S fino a che non ha ricevuto la comunicazione del valore minimax di tutti i sottoalberi di S. Fig. 4.20 fornisce

un’istantanea di una visita dell’albero di

Fig. 4.19a consistente con la decomposizione specificata. P1: N33→N22→Root P2: N35→N41→N23→N34 P3: N32→N42→N36 P4: N31→N21 Root N41 N36 N22 N23 P1 P2 P3 P1 P2 N34 P2

Fig. 4.20 Istantanea a tempo di esecuzione di una decomposizione

Si osservi lo stato corrente dei processori: P4 è inoperoso in quanto ha completato la

sequenza di compiti lui assegnati; P1 è in attesa di ricevere da P2 la valutazione del nodo N34; analogamente P3 è sospeso sulla

ricezione da P2 del valore associato a N41. P2

è dunque l’unico processore correntemente attivo: è in corso la valutazione di N41. Si osservi la relazione gerarchica stabilita fra P3 e P2: essa sarà capovolta quando P3, finalmente completata la valutazione di N36, dovrà

rispondere a P2 del suo operato.

Dato il problema della ricerca di un albero di gioco con un metodo di decomposizione, quando è fissata l’associazione

sottoalberi-processori?

In generale non ha senso che essa sia stabilita prima dell’inizio della ricerca a causa dei

seguenti motivi:

• il principale problema per l’attuazione di questo approccio è che è richiesta la conoscenza della struttura dell’albero; tale

informazione è, per la maggior parte dei domini, molto costosa sia in tempo che in spazio;

• la proprietà dell’algoritmo αβ di tagliare la visita di certi sottoalberi rende inutile la ricerca di alcuni di essi. Non è possibile stabilire staticamente l’identità di questi sottoalberi e quindi fissare a priori una distribuzione uniforme del carico. Lo scenario atteso al tempo della visita sarebbe il seguente: alcuni processori più "fortunati" completeranno prima degli altri la visita dei sottoalberi di cui sono responsabili (grazie alla maggiore efficacia dei tagli da essi prodotti) e resteranno inoperosi fino al completamento della visita complessiva. Qualsiasi soluzione a questo problema deve essere di natura dinamica, cioè deve

prevedere meccanismi che durante la visita permettano di riassegnare a processori

inoperosi sottoalberi già associati a processori sovraccarichi.

Una classificazione dei metodi di

decomposizione in base al tempo in cui è fissata la decomposizione è dunque poco significativa in quanto l’unico approccio

plausibile è quello di tipo dinamico. Ha invece senso distinguere le diverse soluzioni in base al tempo in cui esse stabiliscono i nodi

dell’albero in cui deve avvenire una reale decomposizione.

Def. (nodo di decomposizione):

Sia D la decomposizione dell’albero A

nell’insieme P di processori e Ni un nodo di A; Ni è un nodo di decomposizione (secondo D)

⇔∃Nj: Ni=padre(Nj) e D(Nj)≠D(Ni).

Si definisce dunque di decomposizione un nodo in cui avviene una distribuzione della ricerca, cioè dove alcuni dei propri sottoalberi sono esplorati da processori diversi dal suo responsabile. In funzione di questa definizione può essere formulata la seguente

classificazione dei metodi di decomposizione in statici e dinamici:

• un algoritmo di decomposizione statica fissa a priori l’identità di tutti i nodi di

• in un algoritmo di decomposizione dinamica, invece, una parte dei nodi di decomposizione è designata durante la ricerca.

Le definizioni proposte saranno recuperate nel Capitolo 5 dove costituiranno strumenti

essenziali nella discussione degli algoritmi discussi in quella sede.

4.2.5.2 Motivi di degrado delle