Gioco stocastico
Un gioco stocastico è una situazione caratterizzata dalla casualità, dall'incertezza e dall'imprevedibilità degli eventi. Nei giochi stocastici le azioni degli agenti e i payoff (guadagni) dipendono da una variabile casuale. Il gioco stocastico è un modello astratto utilizzato nella teoria dei giochi per analizzare le scelte e le strategie razionali degli agenti in condizioni di incertezza. A differenza dei giochi deterministici, nei giochi stocastici gli eventi sono totalmente o parzialmente indipendenti dalle scelte degli agenti. Un giocatore può prevedere le scelte più logiche e razionali dell'altro giocatore, può effettuare le scelte giuste per massimizzarela propria utilità ma non può conoscere con certezza gli aspetti casuali dell'ambiente operativo. Questa situazione può essere rappresentata in un albero di gioco tramite l'inserimento dei nodi di casualità.
I nodi di casualità ( nodi rossi ) non rappresentano delle decisioni dei giocatori bensì degli eventi casuali ( es. lancio di un dado, lancio di una moneta, condizioni meteo, ecc. ) che i giocatori subiscono. I nodi casuali influenzano la sequenza decisionale ( gioco ) degli agenti. A seconda del valore assunto dalla variabile stocastica, gli agenti si trovano su una ramificazione dell'albero di gioco piuttosto che su un'altra. Gli agenti non conoscono con certezza l'esito del nodo di casualità ( ramificazione ) e non sono in grado di influenzare l'esito con le proprie azioni. In tali situazioni gli agenti possono soltanto calcolare una stima della probabilità di ciascuno nodo-figlio del nodo di casualità e del relativo valore atteso medio.
Complessità algoritmo stocastico. I giochi stocastici sono caratterizzati da una ramificazione molto più ampia rispetto ai giochi deterministici. Per ogni nodo di casualità è necessario considerare ogni possibile valore che la variabile stocastica può assumere. È quindi molto complesso analizzare completamente un albero di gioco o un albero di ricerca. La ricerca può diventare molto complessa anche considerando poche mosse successive ossia anche limitando la profondità dell'albero di ricerca soltanto a pochi livelli.
