Natália
-3 °C
8 °C

A matematikusok szerint nehéz a tetris

2002.10.28. 13:48
Az MIT kutatói bebizonyították, hogy a tetris bonyolult játék, matematikailag ugyanis az igen nehezen megoldható NP-teljes problémák közé sorolható. Ezentúl tehát a munka helyett tetrisezők azzal a megnyugtató tudattal játszhatnak, hogy nemhogy nem lazsálnak, hanem az elméleti matematika egyik legnagyobb kihívásával küzdenek éppen.
Tizenhét évvel azután, hogy az orosz Alekszej Pajtinov megalkotta a tetrist, a Massachusetts Institute of Technology (MIT) kutatói végre bebizonyították, hogy a játék nehéz. A tetris azután vált igen népszerűvé, hogy a Nintendo is megjelentette, azóta is ez a legnagyobb példányszámban eladott játék a világon.

Erik Demaine és kutatótársai szerint a tetris a legbonyolultabb matematikai problémák csoportjába, az NP-teljes problémák közé tartozik, írta a Nature magazin. Ezek közül talán a legismertebb az utazó ügynök probléma, melyben az ügynöknek n számú városba kell eljutnia, mindegyikbe pontosan egyszer, a lehető legkisebb költséggel, azaz a legrövidebb útvonalon.

Demaine szerint emiatt szinte lehetetlen olyan algoritmust írni, ami képes gyorsan és hatékonyan játszani a játékot.

Hogy világos legyen

A matematikai problémák egy csoportját P-vel jelölik, mivel ezek megoldására létezik polinomiális algoritmus. Ezek megoldása egy adott számítási módszerrel mindig ugyanannyi időt vesz igénybe - egy adatbázisban például tízszer annyi tétel szortírozása tízszer annyi időbe kerül. Felteszik, hogy léteznek non-P problémák is, ezeknek nincs adott időn belül biztos megoldása. A non-P probléma létezésének bizonyításához az összes lehetséges számítási módszerről be kellene látni, hogy nem polinomiális. Ez eddig senkinek sem sikerült.

A non-P gyanúsított problémák egy csoportját NP-nek (nondeterminisztikus P) nevezzük. Az NP olyan probléma, amelynél meg lehet állapítani, hogy megoldása P. Ezen belül van még egy kisebb csoport, amelyet NP-teljes problémáknak neveznek - ezek olyanok, amelyekhez egyetlen polinomiális megoldás kulcs lenne minden NP-hez. Amennyiben tehát egy NP-teljes problémának P megoldása akad, minden NP P-nek bizonyulna. A sejtés az, hogy az NP problémákra nem létezik polinomiális megoldó algoritmus.

Ilyen nagy dolog tehát a tetris.

Addiktív

Az a tény tehát, hogy a tetris NP-teljes probléma, azt jelenti, hogy az egyes elemek legmegfelelőbb helyének megtalálására - akár időkorlátozás nélkül is - az egyetlen módszer minden egyes lehetőség végigpróbálgatása. Demaine szerint a tetrisre éppen a hatalmas intellektuális kihívás miatt lehet olyan könnyen rászokni.

A kétszemélyes játékok azonban még komplikáltabbak: a sakk például EXPTIME-teljes, azaz exponenciális időbonyolultságú probléma: a megoldáshoz szükséges idő exponenciálisan növekszik a tábla méretének növelésekor. A japán go az ilyen típusú játékok közül talán a legösszetettebb.

Felfedeznéd Portugáliát?

Itt a remek alkalom, hogy megismerd. Beszámolók, fotók - böngéssz!

Oszd meg élményeidet!

Oszd meg nyári élményeidet más utazókkal is, tölts fel beszámolót, fotókat!