Tetris és a matematikai bonyolultság
A legtöbb játék matematikai szemszögből is vizsgálható, de a Tetris különleges kapcsolatot ápol a bonyolultságelmélettel. Maga a játék célja – hogy úgy rendezzük el a leeső formákat, hogy kitöltsük a pályát – nagyon hasonlít a matematikában ismert burkolási problémákhoz. A kérdés tehát adott: ha ismert a következő elemek sorrendje, és véges számú darabot kapunk, megmondható-e, hogy teljesen üressé tehető-e a pálya? Ugyanakkor a válasz korántsem egyszerű: a Tetris ilyen elméleti keretek között az egyik legösszetettebb számítási problémává válik.
Mi jelent bonyolultságot a játéknak?
A bonyolultságelmélet szerint a matematikusok és informatikusok különböző osztályokba sorolják a problémákat, például P és NP kategóriákba. Egy P-típusú feladványt bármely számítógép könnyen megold, míg az NP-problémák megoldásának megtalálása bonyolult, de a helyes megoldást gyorsan lehet ellenőrizni. Következésképpen, ha egy algoritmust, amely az egyik problémára működik, át lehet ültetni egy másikra, eldönthető, melyik nehezebb: ez a probléma-redukció elve.
A kulcsfontosságú referencia az úgynevezett NP-teljes problémakör, amelyhez minden más NP-probléma visszavezethető. Az egyik legismertebb ezek közül a háromrészre osztási probléma (three-partition problem): adott egy egész számokból álló halmaz (például {1, 2, 5, 6, 7, 9}), vajon felosztható-e háromelemű részhalmazokra úgy, hogy minden részhalmaz összege megegyezzen? Esetünkben (1, 5, 9) és (2, 6, 7) egy-egy megoldás, mert mindkettő összege 15. Ez azonban egyáltalán nem minden halmaznál lehetséges, és megtalálni, hogy létezik-e ilyen felosztás, NP-teljes bonyolultságú.
Tetris és a matematikai lehetetlenség
2003-ban a MIT kutatói bizonyították, hogy a Tetris problémája visszavezethető a háromrészre osztási problémára (three-partition problem): ha a Tetris pályáján keletkező rések megfeleltethetők a részhalmazoknak, a leeső blokkok pedig a számoknak, akkor pontosan az a kérdés, hogy kiüríthető-e a pálya – ugyanúgy, ahogy létezik-e megfelelő felosztás a háromrészre osztási problémában. Ezért elmondható, hogy a Tetris optimális végigjátszása is NP-teljes probléma, vagyis már rövid, bonyolultabb játékmeneteket sem lehet hatékonyan megoldani számítógéppel.
Tetris a kiszámíthatóság határán
Ugyanakkor a Tetrisnek van egy még meghökkentőbb matematikai vonása is. 2004-ben bizonyították, hogy egy speciális, csak rúdalakú (I-alakú) blokkokkal játszott partiban, ha adott számú lépés után azt kérdezzük, üres lesz-e a tábla a lehetséges lerakási módok bármelyikétől, erre még végtelen számítási teljesítménnyel sem adható általános algoritmikus válasz. Azaz létezik olyan Tetris-szituáció, ahol egy matematikai tétel — Gödel híres befejezetlenségi tétele — miatt sosem tudhatjuk biztosan, hogy lehet-e nyerni vagy sem.
Az örök kedvenc evolúciója
Következésképpen a Tetris nemcsak szórakoztató, hanem az egyik legnagyobb matematikai rejtély is. S bár a mindennapi játékban ezek a problémák fel sem tűnnek, a játék igazi mélységét és időtálló varázsát jelzi, hogy 2023-ban egy 13 éves fiú, úgynevezett rolling technikával, már a 29. szint fölé jutott – a játék pedig összeomlott a rekorddöntés közben. Jelentős, hogy még 40 év után is újabb és újabb matematikai és játéktechnikai meglepetéseket tartogat a Tetris.
