|
LaMoSca v0.09Ordinamento con History Heuristic |
ObiettivoIn questa versione del programma viene introdotto l'ordinamento dei nodi interni dell'albero di ricerca, per migliorare le prestazioni dell'Alpha-Beta pruning. L'ordinamentoLa capacità di ridurre rami dell'albero di ricerca da parte dell'AlphaBeta dipende da quando la scansione effettuata durante la ricerca incontra le mosse che causano i tagli. Le prestazioni migliorerebbero se i nodi intermedi dell'albero fossero ordinati per ciascun livello, presentando per prime le mosse che portano a posizioni con valutazioni migliori nella speranza che possano causare dei tagli. La chiamata alla funzione che esegue l'ordinamento viene fatta per ciascuna mossa prima di eseguire la mossa stessa e chiamare l'AlphaBeta per proseguire la ricerca. Nell'ordinamento non è necessario ordinare completamente il livello corrente, ma è sufficiente portare in prima posizione la mossa a valore maggiore, nella speranza che le mosse rimanenti non vengano analizzate a causa di un taglio. Se questo non succede, la mossa di valore immediatamente inferiore sarà portata in prima posizione all'iterazione successiva. L'ordinamento dei nodi intermedi richiede di assegnare loro dei valori, assegnazione che può essere fatta essenzialmente secondo tre principi:
E' importante sottolineare che le valutazioni dei nodi intermedi possono essere non rigorosissime, perché non determinano la scelta della mossa da eseguire, fatta sempre sulla base delle valutazioni dei nodi foglia. MVV/LVA"MVV/LVA", acronimo di "Most Valuable Victim/Least Valuable Attacker", è una tecnica statica di ordinamento che pesa le mosse al momento della loro generazione in funzione di eventuali catture. Il valore assegnato è ottenuto come differenza tra il valore del pezzo catturato (eventualmente corretto da un fattore moltiplicativo) ed il valore del pezzo che muove. L'idea è quella di favorire mosse che permettono di catturare i pezzi più pesanti, cercando di muovere i pezzi più leggeri. Nonostante l'evidente approssimazione della valutazione, riconducibile al solo bilancio del materiale, l'implementazione del MVV/LVA è a costo molto ridotto, per cui è molto diffusa in combinazione con altre tecniche. History HeuristicL'History Heuristic è una tecnica di pesatura dinamica che pesa le mosse dei nodi interni dell'albero di ricerca in funzione dei tagli da loro causati. L'idea alla base di questa tecnica è che se una mossa ha causato un taglio, es.: la cattura di un pezzo, è probabile che rimanga ancora valida in varianti differenti se si dovesse presentare una posizione analoga. Per salvare le informazioni sui tagli viene usata una matrice 64x64, alla quale si accede usando come indici le case sorgente e destinazione della mossa. Ad ogni taglio nell'AlphaBeta da parte di una mossa si incrementa il valore del corrispondente elemento della matrice. L'incremento è pesato dando un valore maggiore all'aumentare del livello, in modo da far perdere influenza alle mosse più lontane. Killer MovesL'History Heuristic è una generalizzazione di un'altra tecnica abbastanza nota, che è quella delle "Killer Moves". Con questa tecnica si tiene memoria solamente di una o più mosse che hanno causato un taglio allo stesso livello dell'albero, nella speranza che siano ancora valide in altri rami. Il codiceIl programma utilizza l'ordinamento tramite MVV/LVA e History Heuristic. L'esecuzione del programmaEseguendo il programma e guardando il file di log è possibile avere traccia degli scambi effettuati nell'ordinamento. Ad esempio a fronte di un'apertura "d2d4" la ricerca su 4 livelli porta al primo scambio (con conseguente taglio AlphaBeta) come Scambia d5d6=0 con c1h6=8 // Cut |
DownloadDa completare
Da fare
|
Link |
| Indietro | Indice | Avanti |