Gioco del cento

Da Wikipedia, l'enciclopedia libera.

Il gioco del cento è un cosiddetto gioco matematico e può essere considerato un buon esempio di un gioco finito ad informazione perfetta (vedi gioco ad informazione perfetta), diverso dall'usuale tic tac toe.

Grazie al teorema di Zermelo sui giochi ad informazione perfetta si sa che ammette equilibrio e quindi è ragionevole, per un gioco così piccolo, cercarlo.

Durante questa trattazione, il gioco viene chiamato Cento, quale alias di "gioco del cento". Nel gioco originario, di origine popolare probabilmente, ognuno dei due contendenti dice a turno un numero che deve essere strettamente maggiore del precedente e può essere distante dal precedente al massimo 10.

Il primo a giocare, che è ovviamente un caso speciale della regola precedente, può dire un numero da 1 a 10. Il primo che dice 100 ha vinto.

[modifica] Cento generalizzato: Cento(s:f)

Formalizziamo il gioco generalizzandolo

Regole:

a) ci sono due giocatori
b) ad ogni turno $i$ i giocatori devono giocare un numero $P_i \in \mathbb{N}$ (vedi Numeri naturali)
c) il primo puo' giocare un numero da 1 a $s$ , con $s$ in N
d) ad ogni turno successivo al primo il giocatore puo' giocare un numero $P i + 1 = P i + d i$ tale che $P i + s > = P i + 1 > P i$

Ovvero può aumentare il numero precedente di una quantità $d_i \in [1,s]$

e) il primo che gioca $f$ ha vinto

[modifica] Calcolo Equilibrio

Definisco l'insieme E delle giocate vincenti

f in E
se $x \in E$ allora

Il primo vince se può dire come sua prima giocata un numero in E altrimenti vince il secondo

[modifica] Strategia Cento originale

Es. Applico la regola a Cento(10:100)

100 in E
100 in E quindi 100 - 10 - 1 == 89 in E

Ovvero: se dico cento ho vinto, ma anche se costringo a dire al mio avversario un numero che mi consenta di dire cento ho vinto. Dicendo 89, ovvero 100 meno undici, costringo il mio avversario a dire un numero da 90 a 99 consentendomi in ogni caso di dire cento. In generale se voglio assicurarmi di poter dire x mi è sufficiente dire x-11.

$89 \rightarrow 78$
...
$23 \rightarrow 12$
$12 \rightarrow 1$

1 (che il primo può giocare e che, quindi, ha una strategia vincente)

In altre parole il Cento originale, ovvero il gioco Cento(10:100), ha la strategia vincente (per chi parte)

1,12,23,34,45,56,67,78,89,100

Indipendentemente dalla giocata dell'avversario.

[modifica] Strategia generalizzata Cento(s:f)

Es. Applico la regola a Cento(10:99)

99 in E
quindi anche 88, 77, 66, 55, 44, 33, 22, 11

Il primo non può giocare 11 quindi vince il secondo

[modifica] Estensione di Cento: XCento(s:f:D)

Proviamo ora con un gioco un poco più complesso. Si deve, cioè, cercare la strategia vincente elencando la forma strategica estesa (strategia forma estesa)

[modifica] Regole.

a) ci sono due giocatori
b) ad ogni turno i giocatori devono giocare un numero $P i$
c) il primo può giocare un numero da 1 a $s$
d) ad ogni turno successivo al primo il giocatore può giocare un numero $P i + 1$ tale che

def: $d i = P i - P i - 1$ (ovvero $P i + 1 = P i + d i + 1)$

i $P i + 1 > P i$
ii-a $d i + 1 > 0$
ii-b $d_{i+1} \in [d_i - D, d_i + D]$

e) vince chi arriva esattamente a f [3]

[modifica] Strategia per XCento(2:7:1) (studio teoria)[2]

XCento è un gioco finito [1] a informazione perfetta tra due contendenti, quindi, per il teorema di Zermelo, deve avere una e una sola di queste proprietà

a) deve esistere una strategia vincente per il primo
b) deve esistere una strategia vincente per il secondo
c) entrambi possono forzare il pareggio.

Innanzitutto è da notare che (c) è vietata dalle regole.

definisco la mossa come (n,d), dove n è il numero giocato mentre d è la distanza tra questa giocata e la precedente, che limita le possibili giocate successive.

Es.

(10, 10)
(21, 11) poteva giocare (19,  9) (20, 10) (21, 11)
(33, 12) poteva giocare (31, 10) (32, 11) (33, 12)
...

Notare che la prima giocata è, a causa delle regole, sempre del tipo (k,k). con 1<= k <=10.

Cerco di definire E come nei precedenti giochi

a) $(100, d f)$ in E (con $d f > 0$ )
b) se $(P_i, d_i) \in E$ allora $(P_i - d_i, x) \in E$ dove $x \in (d_i -1, d_i , d_i + 1)$ tolti i valori negativi.

generalizzazione

a) $(f, d_f) \in E$ (con $d f > 0$ )
b) se $(P_i, d_i) \in E$ allora $(P_i - d_i, x) \in E$ dove $x \in (d_i - D, d_i + D)$ tolti i valori negativi

Notare che $d f$ è sicuramente limitato anche superiormente questo valore $d f m a x$ potrebbe essere calcolato.

[modifica] Strategia per XCento(2:7:1) (studio)[2]

Scrivo l'albero strategico completo.

Gioca   Gioca   Gioca   Gioca   Gioca   Gioca   Gioca
A       B       A       B       A       B       A

A(1,1)
        B(2,1)
                A(3,1)
                        B(4,1)
                                A(5,1)
                                        B(6,1)
                                                A(7,1)
                                                        
                                        B(7,2)
                                A(6,2)
                                        B(7,1)
                                        B(8,2)
                                        B(9,3)
                        B(5,2)
                                A(6,1)
                                        B(7,1)
                                        B(8,2)
                                A(7,2)
                A(4,2)
                        B(5,1)
                                A(6,1)
                                        B(7,1)
                                        B(8,2)
                                A(7,2)
                        B(6,2)
                                A(7,1)
                                A(8,2)
                        B(7,3)
        B(3,2)
                A(4,1)
                        B(5,1)
                                A(6,1)
                                        B(7,1)
                                        B(8,2)
                                A(7,2)
                        B(6,2)
                                A(7,1)
                                A(8,2)
                                A(9,3)
                A(5,2)
                        B(6,1)
                                A(7,1)
                                A(8,2)
                        B(7,2)
                        B(8,3)
                A(6,3)
                        B(8,2)
                        B(8,3)
                        B(10,4)


Gioca   Gioca   Gioca   Gioca   Gioca   Gioca   Gioca
A       B       A       B       A       B       A
A(2,2)
        B(3,1)
                A(4,1)
                        B(5,1)
                                A(6,1)
                                        B(7,1)
                                        B(8,2)
                                A(7,2)
                        B(6,2)
                                A(7,1)
                                A(8,2)
                                A(9,3)
                A(5,2)
                        B(6,1)
                                A(7,1)
                                A(8,2)
                        B(7,2)
                        B(8,3)
        B(4,2)
                A(5,1)
                        B(6,1)
                                A(7,1)
                                A(8,2)
                        B(7,2)
                A(6,2)
                        B(7,1)
                        B(8,2)
                        B(9,3)
                A(7,3)
        B(5,3)
                A(7,2)
                A(8,3)
                A(9,4)

Quelli segnalati con A sono vincenti per il primo quelli con B sono vincenti per il secondo.

Quindi il primo inizia con (2,2) e vince.

E = A(2,2), A(4,1), A(7,1), A(7,2), A(7,3)

^[1] NdR questo andrebbe dimostrato: la prova dovrebbe basarsi sul fatto che è un gioco "strettamente crescente " e che quindi sono vietati i loop.
^[2] Cfr. un qualsiasi manuale di teoria dei giochi o Roberto Lucchetti, Di duelli, scacchi e dilemmi. La teoria matematica dei giochi, Bruno Mondadori Editore
^[3] Un'ulteriore variante sarebbe consentire di vincere anche superando <f>

Estratto da "http://it.wikipedia.org../../../g/i/o/Gioco_del_cento.html"

Categorie: Giochi matematici | Giochi

We provide Linux to the World