Differenza tra gioco a informazione perfetta, somma-zero, sequenziale, deterministico e non cooperativo

Cosa sono i giochi?

I giochi sono uno dei passatempi preferiti di tante persone; alcuni però, richiedono più impegno rispetto ad altri. La ragione di questo, risiede nella necessità di pensare intensamente alle mosse durante lo svolgimento del gioco per poter avere una buona prestazione e raggiungere l’obbiettivo preposto, e in alcuni casi la presenza di uno o più avversari rende questo compito ancora più difficile. Il gioco degli scacchi per esempio, richiede l’applicazione di principi generali, di giudizio e di predizione da parte del giocatore in ogni momento.

Da molti anni ormai, studiosi in tutto il mondo lavorano per riuscire ad emulare l’intelligenza umana dando vita alla disciplina dell’Intelligenza Artificiale (IA).

Uno dei primi domini sfruttati dagli scienziati per la ricerca è proprio quello dei giochi, che nonostante la semplicità delle regole e degli obbiettivi, offre uno spazio complesso la cui navigazione sembra un’esclusiva dell’intelligenza umana. Si è pensato quindi che il riuscire a costruire una macchina in grado di giocare a scacchi, o a qualsiasi altro gioco altrettanto o più complesso, come o meglio di un essere umano, potesse avvicinare l’umanità alla creazione di un’IA in grado di risolvere qualsiasi tipo di problema le si presenti.

I metodi usati per il raggiungimento dell’arduo obbiettivo sono gli algoritmi, formalizzati dal matematico Alan Turing, considerato il padre dell’informatica e dell’IA.

Tipologie di giochi

Il numero dei giochi esistenti è elevato ma si possono dividere in diverse categorie in base alle loro proprietà. Nel campo dell’IA vengono studiati principalmente giochi che hanno le caratteristiche degli scacchi: informazione perfetta, somma-zero, sequenziale, deterministico e non cooperativo.

Informazione perfetta e imperfetta

Nei giochi a informazione perfetta i giocatori sono a conoscenza di tutte le informazioni sullo stato presente e passato del gioco e sulle sue possibili continuazioni. Negli scacchi, che appertongono a questa categoria, le informazioni necessarie sono la posizione dei pezzi sulla scacchiera, le regole ufficiali e lo storico dello spostamento dei pezzi sulla scacchiera dall’inizio del gioco. Con queste informazioni si possono fare tutte le deduzioni necessarie per giocare. Il poker invece è un gioco a informazione imperfetta poiché ogni giocatore, nel poker tradizionale, è a conoscenza solo delle proprie 5 carte che gli vengono date e non conosce quelle in mano ai propri avversari.

In entrambe le situazioni i giocatori usano delle strategie per decidere cosa fare. Una strategia definisce le azioni che verranno effettuate durante la partita per ogni situazione possibile in cui ci si possa trovare. I giochi a informazione perfetta usano una strategia pura dato che conoscono tutte le informazioni necessarie. Quelli a informazione imperfetta invece dovranno usare una strategia mista per un gioco ottimale, ovvero dovranno generare più strategie e dare ad ognuna di esse una valore di probabilità. La strategia pura può anche essere vista come facente parte di un insieme di strategia mista nel quale ha probabilità 1 e tutte le altre hanno probabilità 0.

Somma zero e non somma zero

Nei giochi a somma zero a due persone se un giocatore vince significa che l’altro ha necessariamente perso. Se dovessimo usare la matematica per descrivere questo fenomeno, potremmo dare il valore 1 alla vittoria, 0 al pareggio e -1 alla sconfitta. Con queste premesse, la somma dei valori dell’esito della partita per i due giocatori deve sempre risultare 0. Quindi se per esempio negli scacchi il giocatore con i bianchi vince, viene valutato con 1 e poiché la somma deve essere 0, come abbiamo stabilito sopra, possiamo dedurre che l’altro giocatore ha ottenuto una valutazione di -1 e quindi ha perso. Possiamo estendere il concetto anche a piu di due giocatori e dare una definizione in termini economici dicendo che i giocatori si pagano l’un l’altro e non c’è produzione o distruzione di beni. Nel caso invece che che la somma dei valori dati alla fine della partita ai giocatori sia minore o maggiore di 0, ovvero diversa da 0, allora si parla di giochi a non-somma-zero. I giochi di intrattenimento sono generalmente del primo tipo.

Cooperativi e non cooperativi

La differenza tra giochi cooperativi e non cooperativi sta nella possibilità dei giocatori di poter effettuare accordi vincolanti sulle strategie da usare e/o la distribuzione della vincita, anche se questa opzione non fosse specificata nelle regole del gioco [6]. Quindi se ci si ritrova con un obbiettivo comune, due o più giocatori possono mettersi d’accordo e formare un’alleanza cooperando per raggiungere l’obbiettivo, questi sono i giochi cooperativi. I giochi non-cooperativi, che sono anche quelli più studiati, si fondano sull’indipendenza dei giocatori, che non comunicano e non collaborano tra di loro e perseguono in solitaria il proprio obbiettivo il cui raggiungimento va quasi sempre a discapito di tutti gli altri giocatori poiché ogni giocatore cerca di massimizzare il proprio guadagno, minimizzando di conseguenza quello degli altri. In queste circostanze, se il cambio di strategia di un giocatore (conoscendo le strategie degli altri e non potendole cambiare) non porta a un miglioramento della vincita, e questo è vero per tutti i giocatori, si è raggiunto l’equilibrio di Nash.

Deterministici e stocastici

I giochi deterministici possono essere risolti finitamente usando i valori dei parametri disponibili e le condizioni iniziali. Significa che siamo in grado, conoscendo lo stato presente e un’azione legale su tale stato, di determinare con certezza lo stato del gioco conseguente l’azione, e questo è vero per qualsiasi azione legale su ogni stato possibile dall’inizio alla fine del gioco. I giochi a informazione perfetta sono deterministici come gli Scacchi e Go.

I giochi stocastici possiedono caratteristiche di casualità che possono portare a risultati diversi date le stesse condizioni inziali e gli stessi valori dei parametri. In questa situazione non siamo in grado di prevedere l’esito di una nostra azione legale sulla posizione corrente durante un gioco, quindi è possibile che la stessa azione eseguita sulla stessa posizione in tempi diversi dia esiti diversi. I giochi a informazione imperfetta sono stocastici come Backgammon e Poker.

Sequenziale e simultaneo

Nei giochi con azioni simultanee non si sa che cosa farà l’altro giocatore finché non si è compiuta la propria scelta, non bisogna neccessariamente agire nello stesso momento, ma anche agire in tempi diversi non potendo sapere cosa farà l’altro è come se fosse simultaneo poichè la risoluzione del gioco avviene solo quando entrambi hanno effettuato la loro scelta e nessuno dei due può conoscere quella dell’altro prima di rilevare la propria. Questi tipi di giochi vengono rappresentati usando una matrice che contiene i valori relativi al risultato per ogni combinazione delle possibili azioni dei giocatori. Tipici giochi con azioni simultanee sono sasso-carta-forbici e il dilemma dei prigionieri. A differenza dei giochi con azioni simultanee dove il valore del risultato è conosciuto per ogni singola azione, nei giochi sequenziali il valore del risultato finale dipende da una sequenza di decisioni. Questo influisce sulle scelte poiché si è a conoscenza del comportamento precedente. Per trovare l’equilibrio di Nash nei giochi sequenziali, i giocatori devono identificare il giocatore con la strategia migliore e iterativamente dedurre la risposta migliore degli altri giocatori. Tra i giochi sequenziali ci sono gli scacchi e il poker.

Complessità

“La proprietà complessità in relazione ai giochi, viene utilizzata per indicare due diverse misure, che chiamiamo la complessità dello spazio degli stati e la complessità dell’albero di gioco.”

Lo spazio degli stati è il numero delle posizioni legali che si possono raggiungere dallo stato iniziale mentre la complessità dell’albero di gioco è il numero di foglie nell’albero di ricerca delle posizioni iniziali. In una partita di scacchi di 40 mosse ci sono 10¹²⁰ numeri di foglie e 10⁴³ posizioni legali