Potatura alfa-beta

La potatura alfa-beta accelera la ricerca eseguita da un motore scacchistico, un programma che confronta mosse e risposte. La ricerca può essere immaginata come un albero: ogni nodo è una posizione e ogni ramo una mossa legale. Senza potatura, il programma esaminerebbe molte continuazioni che alla fine si rivelerebbero irrilevanti.

Il metodo mantiene due limiti durante la ricerca. Alfa rappresenta il miglior risultato che una parte può già garantire lungo il percorso corrente. Beta è un limite creato da un’alternativa già disponibile all’avversario. Quando una continuazione è così sfavorevole che un giocatore razionale non la sceglierebbe mai, approfondirla non può più cambiare la decisione nel nodo superiore.

Il ramo viene interrotto per effetto di un limite logico nell’albero, non soltanto perché una mossa sembra poco attraente. Alla stessa profondità e con le stesse valutazioni al limite della ricerca, alfa-beta restituisce la stessa scelta di una ricerca completa che presume le migliori risposte di entrambe le parti.

Il risparmio dipende molto dall’ordine delle mosse. Provare per prime le mosse forti stabilisce prima limiti utili e permette di interrompere più rami senza esaminarli in profondità. Una funzione di valutazione, che assegna una stima numerica a una posizione, fornisce i valori nei punti in cui termina la ricerca finita.