A prima vista, Tetris sembra un passatempo semplice: blocchi che cadono, linee da completare, punteggi da superare. Eppure, dietro la sua essenzialità grafica e la meccanica intuitiva, si nasconde una struttura logica talmente intricata da porre sfide significative persino ai migliori algoritmi informatici. Non solo: il nostro cervello viene influenzato da un effetto che prende il suo nome.
Quel vecchio Tetris sul Game Boy? È più difficile di quanto immaginate
Il gioco, ideato nel 1984 dal programmatore russo Alexey Pajitnov, ha attraversato decenni, piattaforme come il Game Boy e generazioni. Milioni di persone, sin dagli anni ’90, hanno passato ore cercando di incastrare al meglio i celebri tetramini. Tuttavia, la domanda che ha incuriosito informatici e matematici non riguarda tanto la bravura del giocatore, ma piuttosto un interrogativo molto più ambizioso.
Tetris può essere davvero “risolto”?
Per rispondere, bisogna spostarsi nell’ambito della teoria della complessità computazionale, una disciplina che studia quanto sia difficile risolvere un determinato problema utilizzando un algoritmo (qui per saperne di più: https://it.wikipedia.org/wiki/Teoria_della_complessit%C3%A0_computazionale). Alcuni problemi sono classificati come “P”, cioè risolvibili in modo efficiente da un computer.
Altri, detti “NP”, non sono facilmente risolvibili, ma possono essere verificati rapidamente se si ha già una soluzione. Un Sudoku, ad esempio, può richiedere ore per essere completato, ma pochi secondi per verificarne la correttezza.
Tetris, sorprendentemente, rientra in una categoria ancora più insidiosa: gli NP-completi. Questa classe comprende problemi per i quali ogni altro problema NP può essere ricondotto, e Tetris ne è un rappresentante inaspettato. Ma cosa significa?
Nel 2003, un gruppo di ricercatori del MIT ha stabilito un collegamento tra Tetris e un noto problema matematico: la three-partition problem. Questo enigma chiede se un insieme di numeri interi possa essere diviso in sottogruppi da tre elementi con la stessa somma. Non sempre è possibile farlo, e determinare se esiste una suddivisione corretta è tutt’altro che semplice.
I ricercatori hanno mostrato che, sotto certe condizioni (ad esempio conoscendo in anticipo l’ordine dei pezzi), una partita di Tetris può essere matematicamente assimilata a questo problema. I blocchi corrispondono ai numeri, mentre le “lacune” nella griglia rappresentano i sottogruppi da riempire.
Se i numeri possono essere suddivisi correttamente, allora è possibile svuotare il campo da gioco. Il che significa che stabilire la risolvibilità di Tetris equivale, per difficoltà, a risolvere un problema NP-completo.
Questo risultato ha implicazioni rilevanti: non esiste un algoritmo efficiente che possa sempre dire se una determinata sequenza di blocchi porterà alla vittoria. Più la sequenza si allunga, più la complessità cresce in modo esponenziale.
A ciò si aggiunge un ulteriore livello di difficoltà svelato nel 2004 dai ricercatori Hoogeboom e Kosters: persino con un solo tipo di pezzo (il celebre “mattoncino I”) la domanda se sia possibile svuotare il campo non può essere deciso.
Nemmeno una potenza di calcolo infinita sarebbe in grado di dare una risposta certa, poiché la questione si collega ai teoremi di incompletezza di Gödel (qui un approfondimento: https://it.wikipedia.org/wiki/Teoremi_di_incompletezza_di_G%C3%B6del).
Eppure, tutto questo non impedisce ai giocatori di cercare nuovi limiti da superare. Nel 2023, un tredicenne è riuscito ad arrivare al livello 157 grazie a una tecnica avanzata chiamata “rolling”, mandando in crash il gioco stesso.
