Mandatory work first

Mandatory work first è un metodo che impiega un pool di processori in una ricerca parallela condotta in due fasi.

Nel primo stadio della ricerca è esplorata soltanto una porzione ben definita dell’albero di gioco: l’albero minimale. Nella seconda visita è esaminato il resto dell’albero di gioco usando i limiti α e β trovati durante la prima ricerca. Durante le due fasi della ricerca l’algoritmo gestisce una lista di sottoalberi da visitare stabilita da esplorazioni precedenti. I

processori prelevano un sottoalbero dalla lista, lo visitano, comunicano il risultato e talvolta aggiungono lavoro alla lista.

L’algoritmo opera una classificazione dei figli di ciascun nodo. Il primo figlio di un nodo è

chiamato figlio sinistro. Il sottoalbero

contenente questo figlio è detto sottoalbero sinistro ed è esplorato da un processo di tipo S. Tutti gli altri figli di un nodo sono chiamati figli destri e sono contenuti nei sottoalberi destri visitati da processi di tipo D.

Dato un nodo il sottoalbero sinistro viene esplorato da un processo S finché non è fatto risalire al nodo il valore del figlio sinistro. Per ottenere questo scopo il processo S genera processi (di tipo sia S che D) per esplorare tutti

i sottoalberi del figlio sinistro. Parallelamente, per ognuno dei figli destri è ricavato un valore temporaneo.

Questi valori sono confrontati con il valore finale del figlio sinistro per produrre eventuali tagli. Questo valore temporaneo è calcolato da un processo D, il quale genera processi S e D per valutare il sottoalbero sinistro del figlio destro cui è associato. Se non è generato un taglio la visita del sottoalbero destro continua generando un processo D per esplorare il secondo sottoalbero del figlio destro. Tale processo viene arrestato quando il sottoalbero destro è stato completamente esplorato o si ha un taglio.

L’algoritmo di Fig. 4.23 illustra questo evolversi di attivazione e terminazione di processi S e D.

/* l’algoritmo ricorda fra parentesi angolate (< e >) i punti dove inserire le attività per la gestione dei valori minimax intermedi e finali */

typedef tuple_name ...;

int mandatory_work_first(position *p,int depth) { tuple_name roothandled,lsondone; void handle(position *,int,int,int,tuple_name,tuple_name); handle(*p,depth,TRUE,FALSE,roothandled,lsondon e); in(roothandled);

<return minimax value>; }

void handle(position p,int depth,int left,int parentleft,

tuple_name done,tuple_name lsiblingdone) { tuple_name sondone,lsdone; position *successor; int nmoves,cutoff,i; if (depth==0) { < valuta posizione >; if (!left && parentleft)

in(lsiblingdone); } else { nmoves=genmoves(p,&successor); if (left) { for(i=1;i<=nmoves;i++,successor++) eval("split",handle(successor,depth-1,i==0,left,sondone,lsondone)); for (i=1;i<=nmoves;i++) in(sondone); }

cutoff=false;

for (i=1;i<=nmoves && !cutoff;i++,successor++) { handle(successor,i==1,left,sondone,lson done); in(lsiblingdone); out(lsiblingdone); cutoff=<il mio valore temporaneo è peggiore di quello di mio padre>;

} }

}

< modifica, se migliorato, il valore di mio padre >;

if (left && leftparent) out(lsiblingdone); out(done);

}

Fig. 4.23 Mandatory work first

Il vantaggio di questo algoritmo è la riduzione dell’overhead di ricerca in quanto è eseguito solo il lavoro che è stato dimostrato essere necessario.

Nonostante questo metodo proponga la possibilità di prestazioni ottime (in termini di complessità in tempo), il suo utilizzo reale è problematico a causa dell’enorme spazio di memoria necessario per memorizzare tutte le valutazioni parziali dei nodi dell’albero

[AkBaDo82].

4.2.5.5 PVSplit (Principal Variation

Splitting)

PVSplit è un algoritmo parallelo di ricerca αβ

molto efficiente nella visita di alberi di gioco fortemente ordinati [MarCam82;MarPop85]. Per comprendere l’idea del metodo è utile esaminare la natura dell’albero visitato da un algoritmo αβ in condizioni ottime di

ordinamento. Abbiamo già discusso della classificazione dei nodi di un albero di gioco in 3 tipi: PV, CUT e ALL.

L’efficacia della ricerca αβ deriva dal fatto che i nodi CUT possono essere tagliati prima che l’albero relativo sia completamente esplorato. Il massimo beneficio da questo taglio si ottiene quando il miglior valore per il parametro A è disponibile. L’idea del metodo è di cercare di trovare questo valore prima che inizi

p₀ p p p p mv mv mv mv 1 2 1 2 n-1 n-1 n-2 n-2

Questi sottoalberi sono suddivisi dinamicamente fra i processori ed esplorati in parallelo.

Le alternative alla variazione principale sono esplorate in parallelo quando il figlio sinistro e` stato valutato completamente.

Fig. 4.24 Albero di gioco in PVsplit Inizialmente tutti i processori sono impiegati nella ricerca del sottoalbero più a sinistra del nodo radice, dove si assume sia contenuta la principal variation. In questo modo la mossa più promettente è valutata molto velocemente e la successiva decomposizione della restante parte dell’albero di gioco vede i processori iniziare la loro visita con una buona finestra di ricerca. Ciò consente più tagli ed un minore overhead di ricerca rispetto all’algoritmo base di decomposizione. #define update_alpha(VALUE)\ {\ if (VALUE>alpha)\ alpha=VALUE;\ if (alpha>=beta)\ {\ terminate(); /* implementa la

terminazione di tutti i sottoprocessori */ \ return(alpha);\

}\ }\

int pvsplit (position *p,int alpha,int beta,int length) { position *successor; int nmoves,result,i; if (length==0) return (treesplit(*p,alpha,beta)); nmoves=genmoves(p,&successor); if (nmoves==0) return(evaluate(p));

if (alpha>=beta) return(alpha); for (ind=1,free=NSONS;i<nmoves;ind++) { eval ("pvsplit",treesplit(*(successor+ind),-beta,-alpha,length-1)); free--; if (!free) { in("pvsplit",?result); free++; update_alpha(-result); } } while (free<NSONS) { in ("pvsplit",?result); free++; update_alpha(-result); } return (alpha); } Fig. 4.25 PVSplit

Analizziamo questo algoritmo più in dettaglio. PVSplit esegue una sequenza di ricerche secondo l’euristica di approfondimento iterativo.

Sia mv1, ..., mvn-1 la continuazione principale trovata nella (n-1)_esima iterazione e siano p0, p1, ..., pn-1 i nodi corrispondenti, dove p0 è il nodo radice e pn-1 la posizione raggiunta al termine della sequenza (Fig. 4.24). Questi nodi sono chiamati nodi splitting.

Quando la n-esima iterazione ha inizio tutti i processori sono impiegati nella valutazione (secondo l’algoritmo di decomposizione di base) dell’albero avente come radice pn-1. Quando tale ricerca è completata il valore minimax di pn-1 risale fino a pn-2 e le rimanenti mosse legali in pn-2 sono suddivise

dinamicamente fra i processori ed esplorate in parallelo.

Terminata la valutazione di pn-2, il suo valore è fatto risalire fino a pn-3 e così via. Tale

processo è ripetuto per ogni nodo splitting fino a che le mosse nella radice sono finalmente suddivise fra i processori per produrre il valore minimax finale ed una nuova principal variation per la succesiva iterazione.

In Fig. 4.25 è presentata una versione C-Linda di PVSplit.