Teoria dei giochi combinatoriali

La teoria dei giochi combinatoriali, nota anche come CGT, è una branca della matematica applicata e dell'informatica teorica che studia i giochi combinatoriali, e si distingue dalla teoria dei giochi "tradizionale" o "economica". La CGT è nata in relazione alla teoria dei giochi imparziali, il gioco a due giocatori di Nim in particolare, con un'enfasi sulla "soluzione" di alcuni tipi di giochi combinatoriali.

Un gioco deve soddisfare diverse condizioni per essere un gioco combinatorio. Queste sono:

Il gioco deve avere almeno due giocatori.
Il gioco deve essere sequenziale (cioè i giocatori alternano i turni).
Il gioco deve avere informazioni perfette (cioè nessuna informazione è nascosta, come nel Poker).
Il gioco deve essere deterministico (cioè non casuale). La fortuna non fa parte del gioco.
Il gioco deve avere un numero definito di mosse possibili.
Il gioco deve finire.
Il gioco deve finire quando un giocatore non può più muoversi.

La teoria del gioco combinatorio è in gran parte limitata allo studio di un sottoinsieme di giochi combinatoriali che sono a due giocatori, finiti, e hanno un vincitore e un perdente (cioè non finiscono in pareggi).

Questi giochi combinatoriali possono essere rappresentati da alberi, ogni vertice dei quali è il gioco risultante da una particolare mossa del gioco direttamente sotto di esso sull'albero. A questi giochi possono essere assegnati valori di gioco. Trovare questi valori di gioco è di grande interesse per i teorici del CG, così come il concetto teorico di aggiunta di gioco. La somma di due giochi è il gioco in cui ogni giocatore, al suo turno, deve muoversi in uno solo dei due giochi, lasciando l'altro così com'era.

Elwyn Berlekamp, John Conway e Richard Guy sono i fondatori della teoria. Hanno lavorato insieme negli anni Sessanta. Il loro lavoro pubblicato si chiamava Winning Ways for Your Mathematical Plays.

Definizioni

In teoria, ci sono due giocatori chiamati a sinistra e a destra. Un gioco è qualcosa che permette a destra e a sinistra di fare mosse verso altri giochi. Per esempio, nel gioco degli scacchi, c'è un'usuale impostazione di partenza. Si potrebbe però anche pensare ad una partita a scacchi dopo la prima mossa come ad una partita diversa, con una diversa impostazione. Quindi ogni posizione viene anche chiamata partita.

I giochi hanno la notazione {L|R}. L {\\fscx130\fscy130\frx40} $L$ sono i giochi in cui il giocatore sinistro può muoversi. R {\\displaystyle R} $R$ sono i giochi in cui il giocatore destro può muoversi. Se conosci la notazione scacchistica, allora la configurazione scacchistica abituale è la partita

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 6 , c 5 , N c 6 , ... | a 6 , a 5 , N a 6 , b 5 , c 6 , c 5 , N c 6 , ... }. {\\a3,a4,Na3,b3,b3,b4,c3,c4,Nc3,\a6,a5,Na6,b6,b6,b5,c6,c5,Nc6,\a6,\a6,a5,Na6,b6,b5,c6,\a6,\a6,\a6,\a6,\a6,\a6,\a6,\a6,\a6 $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

I punti "..." significano che ci sono molte mosse, quindi non tutte vengono mostrate.

Gli scacchi sono molto complessi. È meglio pensare a giochi più facili. Nim, per esempio, è molto più semplice da pensare. Nim si gioca così:

Ci sono zero o più pile di contatori.
In un turno, un giocatore può prendere tutti i segnalini che vuole da un mucchio.
Il giocatore che non può fare una mossa perde.

Il gioco più semplice di Nim inizia senza contatori! In questo caso, nessuno dei due giocatori può muoversi. Questo viene mostrato come {|}. Entrambi i lati sono vuoti, perché nessuno dei due giocatori può muoversi. Il primo giocatore ad andare non può muoversi, e quindi perderà. Nella CGT, le persone spesso scrivono {|} come simbolo 0 (zero).

Il gioco successivo ha un solo mucchio, con un solo contatore. Se il giocatore di sinistra va per primo, deve prendere il segnalino, lasciando a destra senza mosse ({|}, o 0). Se invece il destro va per primo, non ci saranno più mosse per il sinistro. Quindi sia il sinistro che il destro possono fare una mossa a 0. Questo viene mostrato come {{|}|{{|}}, o {0|0}. Il primo giocatore che si muove per primo vincerà. Giochi uguali a {0|0} sono molto importanti. Sono scritti con il simbolo, * (stella).

Domande e risposte

D: Cos'è la Teoria dei Giochi Combinatoriali?

R: La Teoria dei Giochi Combinatoriali (CGT) è una branca della matematica applicata e dell'informatica teorica che studia i giochi combinatoriali e si distingue dalla teoria dei giochi "tradizionale" o "economica".

D: Quali condizioni deve soddisfare un gioco per essere considerato un gioco combinatorio?

R: Affinché un gioco sia considerato un gioco combinatorio, deve avere almeno due giocatori, deve essere sequenziale (cioè i giocatori si alternano a turno), deve avere un'informazione perfetta (cioè nessuna informazione è nascosta), deve essere deterministico (cioè non casuale), la fortuna non può far parte del gioco, ci deve essere una quantità definita di mosse possibili, il gioco deve finire e il gioco deve finire quando uno dei giocatori non può più muoversi.

D: Su quali tipi di giochi si concentra la Teoria dei Giochi Combinatoriali?

R: La Teoria combinatoria dei giochi si concentra in gran parte sui giochi finiti a due giocatori che hanno vincitori e vinti (cioè, non finiscono in pareggi).

D: Come vengono rappresentati questi tipi di giochi?

R: Questi tipi di giochi possono essere rappresentati da alberi, con ogni vertice che rappresenta il gioco risultante da una particolare mossa del vertice direttamente sottostante sull'albero.

D: Quali sono gli obiettivi dei teorici della computer grafica?

R: Alcuni obiettivi dei teorici della CG includono la ricerca di valori per questi tipi di giochi, nonché la comprensione del concetto di "aggiunta di gioco", che prevede che ogni giocatore faccia una sola mossa in due giochi diversi, lasciando l'altro invariato durante il proprio turno.

D: Chi ha fondato la CGT?

R: Elwyn Berlekamp, John Conway e Richard Guy sono accreditati come fondatori della CGT nel loro lavoro pubblicato negli anni '60, intitolato Winning Ways for Your Mathematical Plays.