Giochi "finiti e senza ciclo" con sfumature.

Messaggioda Martino » 17/05/2008, 19:53

Salve a tutti. :D

Inauguro la mia presenza in questa sezione con un dubbio che da un po' mi disturba. Premetto che so poco-niente di teoria dei giochi.

Sto leggendo il libro "L'assassino degli scacchi e altri misteri matematici" di Bernoît Rittaud, che concilia guardacaso le mie due passioni - matematica e scacchi. Dopo il racconto "l'assassino degli scacchi" l'autore nell'appendice, volendo fornire un'argomentazione a favore del fatto che il gioco degli scacchi è "determinato", fornisce un semplice esempio di un gioco per cui esiste una strategia vincente per uno dei giocatori. Il gioco è il seguente (cito):

Bernoît Rittaud ha scritto:Un sacchetto contiene cinque biglie, ogni giocatore ne prende a turno una o due. Il giocatore A inizia e il vincitore è colui che prende la (o le) ultima/e biglia/e. Si tratta del cosiddetto gioco di Nim.


Viene costruito un grafo che illustra tutte le possibilità, quindi viene ridotto in virtù dell'esistenza di strategie vincenti, fino a designare A vincitore. Si tratta di un abbozzo della dimostrazione del più generale teorema di Zermelo e Von Neumann (stando a quanto leggo). L'autore poi riguardo tale teorema (che non conosco ma di cui posso ragionevolmente dedurre grosso modo l'enunciato a meno di terminologia) dice:

Bernoît Rittaud ha scritto:[...]la riduzione progressiva delle dimensioni del grafo funziona in realtà per qualsiasi gioco (sempre a patto che sia finito e senza ciclo). Tralasciamo la dimostrazione del caso generale, un po' tecnico, ma che non differisce, in sostanza, dal procedimento utilizzato nel nostro esempio. Per tutti i giochi, è possibile ridurre il grafo corrispondente a un solo vertice che designa un "vincitore obiettivo", cioè colui che è sicuro di vincere purché non commetta errori (nel nostro esempio si tratta del giocatore A, per altri giochi sarà il giocatore B). Non è molto difficile affinare lo studio per tenere conto della possibilità di partite che finiscono in parità.


e poi ancora:

Bernoît Rittaud ha scritto:Il gioco degli scacchi è un gioco finito e senza ciclo, con qualche sfumatura che ha dato adito a polemiche di secondaria importanza. Per questo gioco, quindi, esiste sia un "vincitore obiettivo" (i Bianchi o i Neri), sia un "risultato di parità obiettivo".


Le parti sottolineate sono quelle che mi disturbano (non si tratta di una coincidenza, le sottolineature sono mie :lol: ). Il procedimento di riduzione del grafo è bello e molto interessante e utile, non ci piove, ma l'esistenza del pareggio non complica le cose? Cosa si intende esattamente con "risultato di parità obiettivo"?
Se ho capito bene l'esistenza di un tale grafo per ogni gioco "finito e senza ciclo" (tra parentesi conoscete per caso le "sfumature" a cui la terza citazione fa riferimento?) assicura la presenza di una strategia ottimale per uno dei due giocatori, e quindi l'esistenza (mi azzardo a dirlo) di una "partita perfetta", ma non dice nulla riguardo al risultato di una tale partita.
Sempre riguardo la terza citazione, come fanno un vincitore obiettivo e un risultato di parità obiettivo a coesistere? Sono un po' confuso.
Inoltre, dove posso approfondire il concetto di "gioco finito e senza ciclo"?

Grazie a chi vorrà illuminarmi (o anche solo darmi un'idea) :)
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 1159 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Re: Giochi "finiti e senza ciclo" con sfumature.

Messaggioda Fioravante Patrone » 17/05/2008, 20:43

Martino ha scritto:Salve a tutti. :D

Benvenuto. Srotoliamo il tappeto rosso.


Ti rispondo, cercando di andare al sodo. Semmai, se restano zone grigie (o nere...), non scappo. Magari usa le cose del "mini-corso" (gioco in forma strategica ed equilibrio di Nash).

Allora, un gioco può essere rappresentato mediante la "forma estesa". Che è un albero (grafo senza cicli, ecco perché Rittaud parla di cicli), con un po' di etichette varie assegnate ai nodi e ai lati.
Se vuoi usare il metodo di induzione a ritroso (backward induction) per trovare un equilibrio per il gioco, sarà comodo supporre che l'albero sia finito (ecco l'altra parolina magica usata da Rittaud). Le sfumature (citate da Rittaud...) forse si riferiscono (provo a immaginare) al fatto che una partita di scacchi potrebbe durare teoricamente infinite mosse (dopo tre configurazioni identiche sulla scacchiera, un giocatore può chiedere la patta, a quel che mi risulta. Non deve).
Allora, con un gioco in forma estesa, finito e a informazione perfetta (fai conto che non abbia detto niente: i giochi citati sono tutti così. Volendo approfondire,vedi i link citati sotto) si può applicare l'induzione a ritroso. Che fornisce un equilibrio del gioco grazie al teorema di Zermelo- Kuhn (von Neumann non c'entra: c'è un risultato di Zermelo del 1913 sul gioco degli scacchi ed uno generale di Kuhn nel 1953).

Se il gioco è a somma zero, ovvero per ogni esito la somma dei payoff dei giocatori fa zero, allora l'equilibrio (di Nash) del gioco gode di proprietà interessanti.
La strategia del primo giocatore è una strategia di maxmin. E quella del secondo giocatore è di maxmin.
Cosa vuol dire?
Supponiamo che $\bar x$ e $\bar y$ siano strategie d'equilibrio dei due giocatori(*). Si ha:

$f(\bar x, \bar y) \ge f(x, \bar y)$ per ogni $x$
$g(\bar x, \bar y) \ge g(\bar x, y)$ per ogni $y$

(è la def di equilibrio di Nash)

Ovvero (il gioco è a somma zero, e quindi $g = -f$):
$f(\bar x, y) \ge f(\bar x, \bar y) \ge f(x, \bar y)$ per ogni $x,y$

Supponiamo che $f$ possa assumere solo i valori $1$ (vince il giocatore $I$), $0$ (pareggio) e $-1$ (vince il giocatore $II$).
Allora, per quanto riguarda il valore che $f$ assume in un equilibrio, si possono dare solo tre casi(**):

1. $f(\bar x, \bar y) = 1$. Allora, essendo $f(\bar x, y) \ge f(\bar x, \bar y)$ (per ogni $y$), se il giocatore $I$ gioca $\bar x$, egli si garantisce la vittoria, qualunque scelta faccia $II$.

2. $f(\bar x, \bar y) = 0$. Allora, essendo $f(\bar x, y) \ge f(\bar x, \bar y)$ (per ogni $y$), se il giocatore $I$ gioca $\bar x$, egli si garantisce comunque almeno il pareggio, qualunque scelta faccia $II$. Se però $II$ fa una scelta sciocca, $I$ può vincere(***).

3. $f(\bar x, \bar y) = -1$. Beh, come nel caso 1. ma con ruoli rovesciati fra i giocatori.


Martino ha scritto:Inoltre, dove posso approfondire il concetto di "gioco finito e senza ciclo"?

Puoi guardare qui:
- un abbozzo veloce: http://www.diptem.unige.it/patrone/intro_TdG.pdf
- la descrizione dettagliata: http://www.diptem.unige.it/patrone/deci ... estesa.pdf
Naturalmente ci sarebbe un ottimo libro...


(*) Sto parlando di giochi a somma zero. E' per questo motivo che mi permetto di parlare di strategia di equilibrio per un giocatore. In un gioco a somma qualsiasi, non ha senso, in generale. Ma si hanno solo coppie di strategie di equilibrio.

(**) Di nuovo, è essenziale essere in un gioco a somma zero. Per i giochi a somma zero, il payoff per $I$ (e quindi per $II$) è lo stesso in ogni equilibrio.

(***) Prova a considerare il gioco del tris, e vedrai che la situazione è proprio come descritta. Sai che c'è una strategia ottimale per $I$. Che garantisce ad $I$ almeno il pareggio. Ma se $II$ sbaglia, $I$ può vincere.

s.e.o.
Avatar utente
Fioravante Patrone
Cannot live without
Cannot live without
 
Messaggio: 3288 di 10808
Iscritto il: 09/06/2006, 19:18
Località: Temporaneamente a Novi Ligure ;-)

Re: Giochi "finiti e senza ciclo" con sfumature.

Messaggioda Martino » 17/05/2008, 23:10

Orbenissimo, grazie Fioravante. Ho letto con molto interesse il pdf di introduzione.

Se non ricordo male un gioco ad "informazione completa" (è la stessa cosa di "informazione perfetta"?) è un gioco in cui in ogni momento entrambi i giocatori hanno tutte le informazioni sullo stato del gioco (giusto?). Tu affermi che:

Fioravante Patrone ha scritto:Allora, con un gioco in forma estesa, finito e a informazione perfetta (fai conto che non abbia detto niente: i giochi citati sono tutti così. Volendo approfondire,vedi i link citati sotto) si può applicare l'induzione a ritroso. Che fornisce un equilibrio del gioco grazie al teorema di Zermelo- Kuhn (von Neumann non c'entra: c'è un risultato di Zermelo del 1913 sul gioco degli scacchi ed uno generale di Kuhn nel 1953).


Quindi nel gioco degli scacchi esiste un equilibrio. Ma che tu sappia, ci sono teoremi sugli scacchi che assicurano la vittoria ad uno dei due giocatori in caso egli segua una strategia ottimale? Sarebbe, credo, ben diverso che assicurare l'esistenza di una strategia ottimale per entrambi (la cui esistenza è da me condivisa - anche a livello intuitivo) appunto per l'esistenza del pareggio. Se n'era parlato qui tempo fa.

Fioravante Patrone ha scritto:Le sfumature (citate da Rittaud...) forse si riferiscono (provo a immaginare) al fatto che una partita di scacchi potrebbe durare teoricamente infinite mosse (dopo tre configurazioni identiche sulla scacchiera, un giocatore può chiedere la patta, a quel che mi risulta. Non deve).


In effetti potresti avere ragione. Non ricordo il regolamento purtroppo. Ma se fosse come dici, non sarebbe compromessa la finitezza del gioco?
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 1160 di 13035
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Re: Giochi "finiti e senza ciclo" con sfumature.

Messaggioda Fioravante Patrone » 19/05/2008, 13:38

Martino ha scritto:Se non ricordo male un gioco ad "informazione completa" (è la stessa cosa di "informazione perfetta"?) è un gioco in cui in ogni momento entrambi i giocatori hanno tutte le informazioni sullo stato del gioco (giusto?).
No, sbagliato.
Preferisco dirlo con parole mie.
Un gioco in forma estesa si dice a informazione perfetta se in ogni nodo in cui tocca scegliere ad un giocatore, egli è a conoscenza della intera storia pregressa che ha portato a quel nodo.
Informazione completa è un'altra cosa (e si può riferire anche ad un gioco in forma strategica).

Martino ha scritto:Quindi nel gioco degli scacchi esiste un equilibrio. Ma che tu sappia, ci sono teoremi sugli scacchi che assicurano la vittoria ad uno dei due giocatori in caso egli segua una strategia ottimale?
No, non ce ne sono teoremi di questo tipo.
Cose di questo genere sono note per "hex", ad esempio. Per questo gioco è noto che il primo giocatore ha una strategia vincente. Ma come sia fatta, lo si sa solo per scacchiere di lato max 9 x 9 (o giù di lì, è quanto mi risulta).

Martino ha scritto:
Fioravante Patrone ha scritto:Le sfumature (citate da Rittaud...) forse si riferiscono (provo a immaginare) al fatto che una partita di scacchi potrebbe durare teoricamente infinite mosse (dopo tre configurazioni identiche sulla scacchiera, un giocatore può chiedere la patta, a quel che mi risulta. Non deve).

In effetti potresti avere ragione. Non ricordo il regolamento purtroppo. Ma se fosse come dici, non sarebbe compromessa la finitezza del gioco?
Certo.

Aggiungo che ho controllato:
http://www.fide.com/info/handbook?id=32&view=category
e mi ricordavo bene. Un giocatore può chiedere la patta. Vedi art. 5.2.4
Però a questo punto subentra la regola delle 50 mosse.
Ma anche qui, un giocatore può chiedere la patta. Vedi art. 5.2.5
Avatar utente
Fioravante Patrone
Cannot live without
Cannot live without
 
Messaggio: 3303 di 10808
Iscritto il: 09/06/2006, 19:18
Località: Temporaneamente a Novi Ligure ;-)


Torna a Matematica per l'Economia e per le Scienze Naturali

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite