Effetto orizzonte
L'effetto orizzonte (in inglese Horizon Effect) è un problema che si crea con gli algoritmi di ricerca in profondità con interruzione programmata.[1]
Problema
[modifica | modifica wikitesto]Un algoritmo di ricerca in profondità viene generalmente implementato su una struttura di dati come il grafo. Il suo scopo è effettuare la ricerca usando comunemente la tecnica della ricorsione, cercando tutte le possibili soluzioni.[2] Questi algoritmi vengono implementati anche nei programmi di scacchi, ma essendoci negli scacchi una grandissima varietà di soluzioni possibili, ed avendo a disposizione dei computer con memoria limitata, viene adottato un algoritmo di ricerca in profondità con interruzione, cioè viene inserito un numero oltre al quale la ricerca non prosegue. Questo numero corrisponde alla massima profondità a cui la ricorsione potrà arrivare; aumentando tale numero, aumenta la profondità della ricorsione.[3]
Il problema che così si crea è l'effetto orizzonte: non potendo esaminare tutte le soluzioni si rimane all'oscuro di un numero di casi che potrebbero essere favorevoli alla soluzione del nostro problema. Per esempio, si ipotizzi che un computer programmato per giocare a scacchi effettui una ricerca in profondità. All'inizio della partita il bianco ha la possibilità di effettuare 16 mosse di pedone e 4 mosse di cavallo per un totale di 20 mosse. Uguale situazione ha il nero. Considerando una profondità d'analisi 2 all'inizio della partita si ottengono ben 400 mosse possibili (20 del bianco per 20 del nero); più aumenta la profondità più aumenta il tempo di elaborazione. Però meno analisi in profondità equivale ad avere una visuale più ristretta delle mosse possibili, perdendo quindi delle soluzioni che potrebbero portare ad una vittoria, o che magari eviterebbero una sconfitta (effetto orizzonte).[4]
Nell'immagine qui rappresentata si può osservare una struttura ad albero su cui è possibile che si verifichi l'effetto orizzonte. Un algoritmo generico di ricerca in profondità con taglio (interruzione) dopo due ricorsioni; ignorerà la soluzione più ottimale corrispondente al nodo etichettato "A", in quanto non è in grado di vederla, essa è al di là del suo orizzonte massimo.
Soluzioni
[modifica | modifica wikitesto]Per ovviare al problema dell'effetto orizzonte vengono adottate diverse soluzioni che variano a seconda dell'applicativo su cui viene implementato l'algoritmo. Qui vengono illustrate alcune soluzioni, adottate prevalentemente nei programmi di scacchi.
Aumento della profondità
[modifica | modifica wikitesto]Si sceglie di impiegare più tempo e più risorse per ottenere un risultato soddisfacente, incrementando il numero di profondità massima, la quale comunque per ragioni fisiche non potrà essere infinita.[1]
Ricerca quiescente
[modifica | modifica wikitesto]La ricerca quiescente o metodo selettivo è un sistema di ricerca che esclude dalla ricerca approfondita le soluzioni non affini alla soluzione finale, definite scartabili. Includendo solamente quelle più probabili e/o di maggior successo si riducono i tempi di elaborazione.[1][4]
Database
[modifica | modifica wikitesto]Alcune delle soluzioni più plausibili e adottabili in un determinato stato della ricerca sono archiviate in un database e possono essere riutilizzate per ridurre i tempi di ricerca.[1][4]
Estensione singola
[modifica | modifica wikitesto]Le soluzioni chiaramente migliori vengono salvate durante la ricerca (ma non analizzate), per essere esaminate in un secondo momento oltre il limite massimo di profondità. Nel caso la soluzione non risulti valida una volta superato l’orizzonte cioè il numero massimo di profondità, si adotta un'altra soluzione (seguendo l’algoritmo in uso) magari inizialmente svantaggiosa ma che potrebbe portare ad una situazione migliore, anche se non è possibile saperlo, perché non viene effettuata nuovamente una ricerca approfondita. L'estensione singola è simile a una ricerca quiescente: le soluzioni sicuramente non ottimali vengono scartate, le soluzioni che potrebbero essere ottimali vengono analizzate, le soluzioni che risultano subito ottimali vengono salvate per essere esaminate oltre il limite di profondità al termine della ricerca e di conseguenza viene verificato che siano realmente ottimali.[5]
Note
[modifica | modifica wikitesto]- ^ a b c d Effetto orizzonte, su okpedia.it, 15 novembre 2014. URL consultato il 24 maggio 2016.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi, Jackson Libri, 2003, ISBN 88-256-1421-7.
- ^ Russell-Norvig, pp. 616,617.
- ^ a b c Andreas Vogt, I limiti del computer, su Scacchi!, 1998. URL consultato il 24 maggio 2016 (archiviato dall'url originale il 10 aprile 2016).
- ^ Russell-Norvig, pp. 174,175.
Bibliografia
[modifica | modifica wikitesto]- (EN) Stuart Russell e Peter Norvig, "Artificial Intelligence A Modern Approach" Second Edition (PDF), Hoboken, Prentice Hall, 2003 (archiviato dall'url originale il 14 maggio 2016).
