Chomp

Se siete due golosi e non avete paura di impiastricciarvi le mani, potete provare questo gioco. Prendete una tavoletta di cioccolato di quelle formate da tanti quadretti, e alternatevi nello staccarne via un pezzo per mangiarvelo. L’unica regola da seguire è che ciascun giocatore sceglie un quadretto e se lo mangia, insieme a tutti quelli rimasti al di sopra e alla destra. Attenzione, però! Sul quadretto in basso a sinistra è stato messo abbastanza Guttalax da far trascorrere un pomeriggio intero a dover scaricare l’intestino: colui al quale tocca prendere quel quadretto ha dunque perso la partita. Visto che un disegno vale più di mille parole, dopo lo stacco c’è un esempio pratico di partita, in cui il giocatore A, quello che inizia, perde la partita. Preferite giocare per primi o per secondi?

Il gioco in questione si chiama Chomp, ed è stato chiamato così da David Gale, che l’ha (ri)scoperto nei primi anni ’70; ma già nel 1952 Fred Schuh aveva proposto un gioco simile, con l’unica differenza che invece di quadretti di cioccolato venivano usati i divisori di un numero… roba molto meno dolce, insomma. Il gioco è imparziale, vale a dire che data una configurazione, ciascun giocatore – se tocca a lui giocare – ha a disposizione esattamente le stesse mosse (a differenza per esempio degli scacchi, in cui chi ha i pezzi bianchi non può muovere quelli neri), e a informazione perfetta, nel senso che ciascun giocatore sa esattamente cosa ha fatto l’avversario (a differenza per esempio del poker, in cui le carte dell’avversario sono ignote). Infine il gioco termina in un numero finito di mosse, e uno dei due giocatori deve per forza vincere: il pareggio non è ammesso.

Se si escludono i casi banali di tavolette lineari 1xn – il primo giocatore mangia tutti i quadretti tranne uno – e forse di quelle 2xn, non si conosce nessuna strategia esplicita che uno dei giocatori può seguire per essere certo di giungere alla vittoria; il sistema più semplice è dare in pasto a un computer la posizione iniziale e fargli macinare un po’ i dati, per tirare fuori il manuale di istruzioni con la mossa giusta a seconda della configurazione. Il gioco sembrerebbe insomma non dico equo ma giocabile, e in effetti in pratica è così. Ma i matematici sono degli esseri spregevoli che amano rovinare le sorprese, e hanno dimostrato che per una qualunque tavoletta con almeno due quadratini di cioccolato il primo giocatore ha la garanzia di poter sempre vincere!

Il modo per provare tale risultato è tipico della categoria dei matematici: una dimostrazione per assurdo, che non dice nulla di positivo ma si limita a tarpare le ali ai tentativi di trovare una risposta differente. In questo caso forse la cosa è addirittura peggiore: vediamolo subito. Supponiamo infatti che il secondo giocatore abbia una strategia vincente; essa deve per definizione valere per qualunque mossa iniziale del primo giocatore, compresa quella minimale che consiste nel mangiarsi solo il quadretto in alto a destra. Se però ci pensate su un attimo, qualunque sia la risposta ottimale a quella mossa il primo giocatore avrebbe potuto farla subito lui: togliere quel singolo quadretto è infatti una mossa neutra, nel senso che tutte le altre mosse lo tolgono. Insomma, il primo giocatore vince con la tecnica del furto di strategia (“strategy stealing” in inglese). Cosa esattamente rubi non si sa, ma sicuramente ruba.

Sono parecchi i giochi a cui si può applicare il furto della strategia: esempi classici sono quelli (imparziali e a informazione perfetta) in cui occorre completare una configurazione data prima dell’avversario, come il tris e il cinque-in-fila (su un foglio quadrettato occorre mettere cinque simboli in fila orizzonatale, verticale o diagonale). In questo caso si ragiona così: se il secondo giocatore avesse una strategia vincente, basta fare una prima mossa qualunque – che male non fa – e far finta di essere il secondo giocatore. Se mai nel corso della partita toccasse fare la mossa iniziale, basterebbe farne un’altra volta una a caso. In questi casi non è garantita la vittoria, ma la patta almeno sì, come nel caso del tris: meglio che nulla. E non venitemi a chiedere “ma se anche il secondo giocatore fa una mossa a caso, per tornare ad essere il secondo?” Il punto è proprio la strategia cercata non può esserci!

Termino lasciandovi con un giochino, “L’uovo di Colombo”. Immaginate di avere un tavolino rettangolare e un certo numero di uova, tutte uguali nella forma. Ogni giocatore posa un uovo sul tavolo, senza toccarne o spostarne nessun altro; il primo che non ha più spazio per aggiungere un nuovo uovo ha perso. C’è uno dei giocatori che ha a disposizione una strategia vincente? E se sì, è anche possibile descriverla?