Teoria dei giochi (introduzione)

Durante uno dei miei corsi universitari, mi sono trovato a dover studiare un argomento che col tempo ho apprezzato  molto e secondo me è molto interessate: La teoria dei giochi.

Per “Gioco” intendiamo una serie di regole che definiscono le mosse lecite, alternate tra due (o più) giocatori. In genere si rappresenta l’insieme delle possibili istanze di un gioco con un grafo orientato, dove ogni vertice corrisponde ad una configurazione ed ogni arco ad una mossa.  I giochi si dividono in

  • Deterministici
  • Non deterministici
  • Ad informazione perfetta
  • Ad informazione imperfetta

Untitled

 

Cerchiamo di dare una prima definizione di “teoria dei giochi”: è una scienza matematica che ha come scopo lo studio delle situazioni in cui diversi giocatori interagiscono tra loro,  cooperando oppure giocando uno contro l’altro. L’incertezza è dovuta al fatto, quindi, che ci sono più giocatori, avversari  o compagni, che non  conoscono le mosse degli altri giocatori. L’incertezza non è però aleatoria, il problema  è dovuto alle numerose possibili combinazioni, basti pensare che, ad esempio, negli scacchi la dimensione dell’albero delle decisioni  è approssimativamente di 10123 .   Si intuisce subito quindi quale sia il problema fondamentale, ovvero l’impossibilità di esaminare tutto l’albero. Questo ci porta quindi a porci una domanda fondamentale: come usare al meglio il tempo a disposizione quando non è possibile prendere decisioni ottime?
Nel corso degli anni sono stati proposti diversi algoritmi di ricerca, sempre più efficienti, per riuscire ad esplorare l’albero decisionale in tempi sempre più brevi, tra i più famosi c’è l’algoritmo MiniMax per decisioni perfette (e imperfette), che però non è il più efficiente, in quanto è una semplice ricerca in ampiezza della soluzione.

Algoritmo MINMAX

Lo scopo di questo algoritmo è trovare la mossa teoricamente migliore ovvero massimizzare la funzione utilità, senza considerare limitazioni dovute al tempo, caso che però difficilmente si riscontra nella realtà in quanto il tempo gioca un ruolo fondamentale.  Supponiamo di avere due giocatori: MIN e MAX (che muove per primo), ogni mossa di uno di due giocatori deve tenere conto della contromossa dell’altro. Come intuirete dal nome il giocatore MAX vuole massimizzare la sua funzione utilità, mentre MIN la vuole minimizzare. Vediamo i punti chiavi dell’algoritmo

  • Genero tutto l’albero decisionale
  • Arrivo fino alle foglie e applico la funzione di utilità
  • A questo punto propago il valore trovato ai genitori: il valore di un nodo MIN è il minimo tra i valori dei figli, il valore di un nodo MAX è il massimo tra i valori dei figli.
  • Come anticipato poco fa, MAX è il primo giocatore per cui la radice corrisponde ad un turno di MAX, che sceglie la mossa che porta alla mossa con il valore più alto.

E’ riportato qui l’algoritmo in pseudocodice.

 

function MINIMAX-DECISION(state) returns an action 

inputs: state, current state in game
v <– MAX-VALUE(state)
return the action in Successor(state) with value v

 

function MAX-VALUE(state) returns a utlity value

if CUTOFF-TEST(state, depth) then return EVAL(state)
v<–   -∞
for a, s in successor (state) do
v <– MAX(v, MIN-VALUE(s))
return v

 

function MIN-VALUE(state) returns a utlity value

if CUTOFF-TEST(state, depth) then return EVAL(state)
v<–   +∞
for a, s in successor (state) do
v <– MIN(v, MAX-VALUE(s))
return v

The following two tabs change content below.
Hello! I am Davide, nice to meet you! Lover of everything related to technology, science, music. I live between Rome, where i study, and Pescara, the place where I grew up. Cheeseburger eater.

Ultimi post di Dvidì (vedi tutti)

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.