A chi non è mai capitato di essere stato battuto dal proprio computer in un gioco e ci siamo chiesti come fa una macchina a prendere delle decisioni al punto da batterci nelle sfide umano contro computer. In questo articolo vedremo la teoria delle tecniche utilizzate, quella chiamata min-max, dai programmatori di giochi per far prendere delle decisioni intelligenti ad un computer.
La programmazione basata sull’intelligenza artificiale nasce da schemi differenti rispetto a quella tradizionale procedurale in cui si compiono passo dopo passo le operazioni, infatti viene seguita una logica di pattner-directed. Tale logica consente, in base ad una situazione ed a regole conosciute di generare situazioni nuove finché non viene raggiunta la condizione di terminazione. Un sistema pattner-directed è formato da:
- una serie di moduli chiamati pdm che possono essere attivati dai pattner
- lo stato attuale del sistema chiamato database globale
- l’algoritmo di controllo che gestisce l’attivazione e selezione dei pdm
L’operazione fondamentale per la risoluzione di un problema di intelligenza artificiale è il pattner matching che restituisce una risposta booleana se la situazione data fa parte della classe di situazione rappresentata dal pattner ed una serie di sostituzioni da fare sul pattner per renderlo uguale alla situazione data.
Nei giochi a due avversari che utilizzano sistemi pattner-directed, la strategia di controllo principale utilizzata è chiamata min-max. Questo tipo di strategia fa uso del concetto di funzione euristica, ossia una funzione con argomento lo stato del sistema e che restituisce un valore numerico indicante la bontà dello stato relativa al giocatore. Tanto più questo valore è grande, più la situazione è vantaggiosa per il max, ossia il computer, mentre se questo valore è piccolo avremo il vantaggio su min, ossia l’umano. Nel caso la funzione restituisse una situazione vincente per max avremmo “+infinito”, mentre per min “-infinito”. Lo scopo dell’algoritmo min-max è quello di trovare la migliore mossa successiva in base alla situazione di gioco. In questo algoritmo abbiamo tutti i concetti espressi finora: il database globale, le regole e la funzione euristica. La strategia min-max parte da uno stato iniziale ed attiva tutte le regole per creare nuovi stati figli, che a loro volta formeranno nuovi stati in un processo ricorsivo che formerà una struttura ad albero. La profondità degli stati nell’albero è detta depth bound e non deve essere esasperata per non incorrere in problemi di velocità computazionale. Ai livelli pari dell’albero avremo le mosse per max, mentre in quelli dispari per min. La migliore mossa viene scelta in questo modo: se il nodo esaminato è foglia viene assegnato un valore pari alla funzione euristica, altrimenti se il nodo esaminato è max gli viene assegnato il valore massimo tra quelli assegnati ai suoi figli e lo stesso vale per min, tutto questo va ripetuto ricorsivamente finché non viene assegnato un valore alla radice e la migliore prima mossa è lo stato che ha propagato il suo valore fino alla radice stessa.
Questa tecnica ha però delle limitazioni, come per esempio per il gioco degli scacchi nel quale si avrebbero troppe possibilità di gioco, quindi viene operata una potatura euristica dell’albero, come nel caso dell’alpha-beta potato.
