Ultima edizione | Archivio giornali | Archivio tematico | Archivio video

CNR: Alamanacco della Scienza

N. 2 - 8 feb 2017
ISSN 2037-4801

Focus - Il gioco  

Informatica

Cubo o Tetris, è sempre matematica

È considerato il gioco più venduto al mondo ed è addirittura divenuto oggetto di studio. È il cubo di Rubik, il celebre rompicapo inventato nel 1974 dal professore di architettura ungherese Erno Rubik per insegnare ai suoi allievi lo studio degli oggetti in 3D. Il 'cubo magico', come si chiamava originariamente, presenta 9 quadrati che differiscono tra loro per il colore su ognuna delle sue 6 facce. Quando il gioco è risolto, ogni faccia assume un unico colore. “Il cubo di Rubik rappresenta, mediante un oggetto fisico, concetti dell'algebra astratta come la 'teoria dei gruppi'. I gruppi sono alla base della teoria delle simmetrie ed entrano, per questo motivo, in tante applicazioni, dalla chimica alla fisica teorica”, spiega Roberto Natalini, direttore dell'Istituto di applicazioni del calcolo 'Mauro Picone' (Iac) del Cnr. Ma perché è così difficile da risolvere? “Applicando il calcolo combinatorio ai modi di ruotare spigoli e vertici si arriva all'enorme valore di circa 43 miliardi di miliardi di possibili configurazioni. Una serie di algoritmi mnemonici, ottenuti sempre grazie alla teoria dei gruppi, sono stati ideati e studiati da ricercatori delle università e accademie di tutto il mondo. Il primo è stato scoperto nel 1979 dal matematico David Breyer dell'Università di Berkley. Ma per la risoluzione del Cubo ci sono molti sistemi, il più usato è il cosiddetto 'metodo a strati' che consiste nel risolvere in successione lo strato inferiore, superiore e intermedio”.

Il matematico Tomas Rokicki dell'Università di Stanford, invece, ha elaborato uno studio in cui dimostra che per risolvere il gioco non servono più di 20 mosse. “Trovarle a occhio è praticamente impossibile”, prosegue Natalini. “E' possibile risolvere il cubo in circa 100 mosse, con i metodi più semplici e più lenti, o in circa 50 con i metodi da 'speed-cubing'. Ad oggi il record è di Feliks Zemdegs con soli 4,73 secondi”.

Non meno famoso è Tetris, da oltre 30 anni nelle classifiche dei migliori videogiochi mai realizzati, progettato nella prima metà degli anni Ottanta dal matematico Alexey Leonidovich Pajitnov per il Centro informatico Dorodnicyn dell'Accademia delle scienze russa. Prende il nome dalle figure geometriche 'tetramini' protagonisti del gioco e continua a essere prodotto in infinite varianti, un successo dovuto alle sue semplici regole: le forme geometriche che cadono dall'alto vanno incastrate per costruire un muro che si distrugge da solo a ogni linea completata; i pezzi vengono giù sempre più velocemente.

Le prime teorie al riguardo risalgono al 1996, secondo le quali ci sarà sempre un tetramino che non si riesce a incastrare. “Lo spazio di gioco è largo 10 quadratini, mentre i 7 pezzi che cadono in sequenza, se perfettamente incastrati, occupano al massimo una larghezza di 8. Ci sarà quindi sempre uno spazio di almeno 2 quadratini di larghezza fuori dal controllo. Ed è lì che inizia il vero rompicapo”, conclude il ricercatore. “Tetris è quello che in matematica chiamiamo un problema NP-completo. Questo non vuol dire che non esiste un algoritmo per risolverlo ma che, al crescere dei pezzi, il costo computazionale diventa eccessivo. In altre parole, non c'è un modo semplice di giocare a Tetris ottenendo il massimo numero di pezzi disposti correttamente, pur conoscendo in anticipo i pezzi successivi”.

Antonella Guidi

Fonte: Roberto Natalini, Istituto per le applicazioni del calcolo "Mauro Picone", Roma, tel. 06/49270961 , email roberto.natalini@cnr.it -