Intelligenza artificiale e giochi: l'algoritmo MINMAX

MINMAX è un algoritmo impiegato in diverse discipline, tra cui: teoria dei giochi, teoria delle decisioni e IA. Viene usato per la ricerca delle azioni migliori assumendo scelte ottimali da parte degli agenti coinvolti e sfrutta una struttura ad albero ed una funzione euristica per cercare una soluzione in un contesto di conflitto tra più parti. Costruisce l'albero fino a una profondità prefissata, identificata dal numero di azioni alternate che si sceglie come limite di ricerca e usa la funzione euristica per valutare gli stati all'ultimo stadio della ricerca, valori che propaga poi fino allo stato iniziale, confrontandoli con quelli degli altri stati, finché non ha valutato tutti gli stati adeguati disponibili, trovando cosi il percorso migliore. Il potenziamento principale a questo algoritmo è realizzato tramite la potatura Alfa-Beta che sfrutta due variabili chiamate appunto Alfa e Beta, che creano un finestra di valori minimi e massimi ammissibili oltre i quali le posizioni non vengono considerate, riducendo la dimensione dell'albero e permettendo così una ricerca più profonda.