Da allora ci sono stati continui miglioramenti, fino ad arrivare ai giorni nostri, in cui i programmi di gioco possono permettersi di competere con avversari umani molto forti, e anche di batterli. Questi sviluppi sono stati il risultato di un intenso studio e di un grande interesse, che possono essere motivati in vario modo.

Innanzi tutto, i giochi di questo tipo hanno impegnato le facoltà intellettuali degli esseri umani fin da quando è iniziata la civilizzazione; sono sempre stati considerati interessanti perché offrono una competizione astratta, un modo per confrontarsi con le proprie capacità. L'abilità nel giocare giochi come scacchi e GO è sempre stata considerata una prova di intelligenza umana. Questo è il motivo per cui i giochi sono considerati un obiettivo attraente di ricerca in Intelligenza Artificiale: un computer che gioca (bene) a scacchi è una prova dell'esistenza di una macchina che fa qualcosa che si ritiene intelligente.

Secondariamente, i giochi offrono un "laboratorio" perfetto per studiare metodologie di risoluzione di problemi anche complesse. Infatti, è semplice rappresentare lo stato di un gioco per farvi agire degli agenti, che in genere hanno la possibilità di compiere un numero abbastanza piccolo di azioni ben definite. Inoltre, la semplicità delle regole e il fatto che lo stato del mondo sia in genere completamente accessibile fanno sì che sia facile rappresentare il gioco con una ricerca attraverso uno spazio di posizioni di gioco possibili. Una volta rappresentato il gioco, dunque, ci si può concentrare sulla risoluzione dei problemi veri e propri, e sulla ricerca di soluzioni sempre migliori.

In terzo luogo, i giochi offrono la possibilità di valutare le performance di un programma tramite degli standard assoluti: o si vince, o si perde, o si pareggia; non ci sono vie di mezzo.

Da ultimo, ma non per importanza, i giochi sono divertenti; è piacevole studiarli, lavorarci, e spesso gli stessi esperti umani sono ben disposti ad adoperarsi per vedere la propria bravura e la propria esperienza emulate da una macchina.

Queste osservazioni non devono però trarre in inganno. Un gioco può essere molto divertente e avvincente, e magari rappresentarlo può essere anche relativamente semplice. Tuttavia, risolvere un gioco è tutta un'altra questione.

Risolvere un gioco è un problema per molti aspetti diverso dai problemi tradizionali dell'Intelligenza Artificiale.

Innanzi tutto, la presenza di un avversario introduce incertezza, poiché non si sa mai che cosa egli abbia intenzione di fare. Non si tratta, però, di incertezza che si possa simulare, ad esempio, con un lancio dei dadi, perché i dadi, che rappresentano il caso, si considerano essere imparziali ed indifferenti agli obiettivi dell'agente, mentre l'avversario, presumibilmente, cercherà sempre di fare la mossa meno favorevole per l'agente. Si tratta, dunque, di una specie di incertezza ostile.

Secondariamente, i giochi sono di solito molto più difficili da risolvere rispetto ai problemi tradizionali, a causa delle loro "dimensioni". Gli scacchi, per esempio, hanno un fattore di ramificazione medio pari a 35, e le partite spesso richiedono 50 mosse per ciascun giocatore, cosicché l'albero di ricerca viene a contenere circa 35¹⁰⁰ nodi. Questo fatto introduce un nuovo concetto di incertezza: incertezza non dovuta a informazioni mancanti, ma dovuta al fatto che non si possiede il tempo per calcolare le conseguenze esatte di qualunque mossa, cosicché una mossa deve essere scelta e compiuta prima di sapere se è effettivamente la migliore che si possa fare. Per questo la ricerca sui giochi si è concentrata su come utilizzare al meglio il tempo per raggiungere buone decisioni quando è impossibile raggiungere decisioni ottimali.

Sommario

Nel corso del nostro studio della Teoria dei Giochi, partiremo considerando il caso di decisioni perfette nei giochi a due persone. Sebbene tale situazione sia irrealizzabile nella pratica, è comunque un utile punto di partenza per comprendere come gli algoritmi di gioco vengono modificati e perfezionati. Passeremo poi ai giochi con decisioni imperfette, ossia al caso dei giochi reali quali scacchi, dama, ecc. 

Esamineremo le principali strategie di ricerca, tra cui Minimax, SOLVE, SSS* e la potatura Alfa-Beta, la strategia più utilizzata attualmente dai programmi di gioco, in quanto permette notevoli semplificazioni e permette di prevedere più mosse rispetto ad altre strategie più elementari quali Minimax.

Dopo aver visto come tali algoritmi agiscono, andremo a studiarne la complessità, relativamente alla loro ottimalità, al numero di nodi esplorati, ecc.

A questo punto apriremo una piccola parentesi su un particolare algoritmo di ricerca: AO*. Questo è un algoritmo di ricerca generico per grafi AND/OR, ma che può benissimo essere applicato anche in Teoria dei Giochi, visto che è possibile stabilire una corrispondenza tra alberi di gioco e grafi (in particolare alberi) AND/OR.

Introdurremo quindi un'ulteriore complicazione ai giochi che consideriamo: la fortuna. Vedremo, quindi, come si affronta la soluzione di giochi in cui intervengono eventi esterni a priori impredicibili, che condizionano le scelte e le possibilità dei giocatori. Con considerazioni probabilistiche vedremo come si può arrivare a soluzioni accettabili anche in questi casi, apparentemente impossibili da risolvere.

Il capitolo finale si occuperà dello stato attuale dell'arte: illustreremo i progressi fin qui fatti dall'Intelligenza Artificiale nell'ambito della Teoria dei Giochi.

Seguono due appendici: la prima illustra un algoritmo particolarmente efficiente per la risoluzione del gioco del Tic Tac Toe; la seconda illustra le regole fondamentali dei giochi con cui abbiamo avuto a che fare nel corso del nostro studio.