2025. 07. 31., 14:01

Az egyszerű Tetrisben rejtőző megoldhatatlan problémák

Az egyszerű Tetrisben rejtőző megoldhatatlan problémák
Az 1980-as évek közepén indult világhódító útjára a Tetris, amikor a szovjet programozó, Alekszej Pazsitnov megalkotta. A játék hamar kultikussá vált, mára több százmillió rajongót szerzett, és generációk nőttek fel azon, hogy Game Boy képernyőjén próbálják a legmegfelelőbb helyre illeszteni az egyre gyorsabban hulló blokkokat. Érdekes, hogy egy ilyen egyszerű, könnyen tanulható játék a legnagyobb matematikai kihívások közé tartozik, és még a legerősebb szuperszámítógépeket is próbára teszi.

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.

2025, adminboss, www.scientificamerican.com alapján

  • Te szerinted miért szeretnek az emberek ilyen bonyolult játékokat játszani?
  • Ha neked kellene egy ilyen nehéz problémát megoldani, inkább logikára vagy intuícióra hagyatkoznál?
  • Mit csinálnál, ha rájönnél, hogy bizonyos kérdésekre sosem lehet választ adni?


Legfrissebb posztok

MA 12:01

A Microsoft Entra Connect Health hibájával bérlői adatokat loptak

A Microsoft súlyos biztonsági problémával néz szembe: támadók kihasználták a Microsoft Entra Connect Health szolgáltatásában rejlő sebezhetőséget, így illetéktelenek férhettek hozzá rendszergazdai e-mail-címekhez és a bérlők konfigurációs adataihoz...

MA 11:31

Az energiában jöhet a kvantumszámítógép első nagy áttörése

Bár a kvantumszámítógépek legnagyobb áttörései még évekre, akár évtizedekre is lehetnek, a technológia már most komoly változásokat hozhat az energiaiparban...

MA 11:01

Az első észlelt csillagösszeolvadás: egy óriáscsillag felfalja társát

💫 Az Androméda-galaxisban lezajlott egy igazán ritka és látványos esemény: két csillag, egy szuperóriás és egy kisebb társa több ezer évnyi keringés után végül összeolvadt...

MA 10:36

Megéri otthon CO2‑csapdát építeni? Így működik

A Föld légköre még mindig döntően nitrogénből (78%) és oxigénből (21%) áll, szemben az aggasztó hírekkel, amelyek szerint már szinte csak szén-dioxidot lélegzünk be...

MA 10:25

A Merkúr újra látogatót kap: két űrszonda pályára állt

Nyolc év utazás után két űrszonda állt a Merkúr körüli pályára, hogy feltárja a Naphoz legközelebbi bolygó titkait...

MA 10:01

Az otthoni net rémálma: amikor túl sok eszköz csatlakozik

Elég néhány extra eszköz, és a legjobb otthoni internet is térdre kényszerül...

MA 09:36

Az AWS is leállt – mégsem vette észre senki

Napjaink digitális világában, amikor egy online szolgáltatás hibát jelez, pillanatok alatt elárasztják a közösségi médiát a panaszos bejegyzések, és összeomlik a netes ügyfélszolgálat is...

MA 09:13

A BADBOX botnet visszatért, rekorddöntő napi 40 milliárd hirdetéskéréssel

Több hónapos szünet után ismét felbukkant a BADBOX nevű botnet, amely folyamatos működésével napi 40 milliárd hamis hirdetési ajánlatkérést generál, zömmel Android-alapú eszközök segítségével...

MA 09:01

Az FBI-t újra meghackelték: országos rendőrségi adatbázis a célpont?

🕵 Felmerül a kérdés, hogy mennyire biztonságosak a rendvédelmi szervek adatbázisai, miután egy, az FBI-hoz köthető rendszert mindössze két hónapon belül másodszor is feltörtek...

MA 08:49

Az MI-vezér retteg, a Microsoft mégis MI-ügynököket tol a Windows 11-re

Egy lényeges szempont, hogy a mesterséges intelligencia (MI) fejlődése olyan tempót diktál, amely még a terület legnagyobb szereplőit is aggodalommal tölti el...

MA 08:36

A Toyota, a Nissan és a Honda szabványosítják az alkatrészeket költségcsökkentésért

A három legnagyobb japán autógyártó, a Toyota, a Nissan és a Honda mostantól közösen egységesítenek bizonyos alkatrészeket, hogy jelentősen csökkentsék a gyártási költségeket...

MA 08:13

A rejtélyesen gyorsuló űrszikla továbbra is zavarba hozza a csillagászokat

💨 Fontos kérdés, hogy miért mozog a 1998 KY26 nevű, sötét üstökös a Naprendszerben olyan módon, amit a kutatók mindmáig nem tudnak teljesen megmagyarázni...

MA 07:36

A Marson gondok: akadozik a NASA marsjárója és keringője

Az utóbbi hetekben nem volt kegyes a technika a Földön és azon túl sem, hiszen a NASA mind a Perseverance Mars-járóval, mind az Odyssey keringővel problémákat tapasztalt...

MA 07:24

Ismerd meg az iCloud+ újdonságait: Apple Intelligence és okosabb Siri

🌈 Az Apple következő szoftverfrissítései jelentős változásokat hoznak: már minden kompatibilis eszközön – a megfelelő nyelvre állítva – ingyenesen elérhetővé válnak az Apple Intelligence (MI) és a Siri új generációs képességei...

MA 07:13

Az MI mégsem úgy működik, mint az agy – meglepő felfedezés

Fontos kérdés, hogy a mesterséges intelligencia mennyire tudja valóban utánozni az emberi agyat...

APP
MA 07:11

APPok, Amik Ingyenesek MA, 11/22

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     Loan Calc-Lite (iPhone/iPad)A Loan Payment Calculator with PMI egy olyan alkalmazás, amely segít kiszámolni a havi hiteltörlesztő részleteket...

MA 06:36

Az idő sokkal furcsább, mint hinnénk – a tudósok próbára teszik

⏳ Az idő jelensége mindennapjaink része, mégis zavarba ejtő titkokat rejt. Bár óráink pontosan mérik a múlását, a tudósok még mindig nem értik annak legmélyebb természetét...

MA 06:24

Az okosszemüveg, amely tapintássá változtatja a látást

Kezdetben a tudósokat lenyűgözte az emberi agy képessége: bármilyen érzékelési élményt könnyedén át tud alakítani egy másik típusú információvá...

MA 06:05

Történelmi események a mai napon (November 22.)

Erős nap a történelemben: a kairói háborús csúcstalálkozótól a spanyol trónváltásig, a The Beatles ikonikus lemezétől a Toy Story (Toy Story – Játékháború) forradalmi bemutatójáig...

MA 06:01

A tudósok összecsapnak: kié a Riemann-sejtés bizonyítása?

A matematika világát most két egymással versengő bizonyítási állítás is felbolygatta, mindkettő azt állítja, hogy megoldotta a Riemann-sejtést, a leghíresebb nyitott problémát...

APP
szombat 07:11

APPok, Amik Ingyenesek MA, 11/21

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     Bank: The Dice Game (iPhone/iPad)A Bank egy lendületes és szórakoztató kockajáték, amelyben a stratégiai gondolkodás, a kockázatvállalás és a szerencse egyaránt próbára teszi a játékosokat...

szombat 06:06

Történelmi események a mai napon (November 21.)

Rövid utazás a mai nap történelmi mérföldkövei között: birodalomalapítástól és forradalmi tudományos áttöréstől a forró levegős ballon első szabad repüléséig és az ARPANET tartós kapcsolatának elindításáig...

APP
péntek 07:12

APPok, Amik Ingyenesek MA, 11/20

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     MSR Easy Connect: Read & Write (iPhone/iPad)Az MSR Easy Connect alkalmazás lehetővé teszi, hogy iPhone vagy iPad készülékeddel, Bluetooth Low Energy technológián keresztül, könnyedén olvass és írj adatokat MSR eszközödre...

péntek 06:05

Történelmi események a mai napon (November 20.)

Válogatás a történelem ezen napjának legemlékezetesebb pillanataiból: forradalom indul Mexikóban, Magyarország belép a tengelyhatalmak közé, királyi esküvő a Westminster apátságban, történelmi közel-keleti békekísérlet, és tűzvész pusztít a Windsor-kastélyban...

APP
csütörtök 07:11

APPok, Amik Ingyenesek MA, 11/19

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     Prowl: Easy Push Notifications (iPhone/iPad)A Prowl egy modern értesítési alkalmazás, amely lehetővé teszi, hogy bármilyen eszközödön vagy szolgáltatásodon keresztül gyorsan értesülj a fontos eseményekről – legyen szó e-mailről, alkalmazásról vagy egyedi integrációkról...

csütörtök 06:05

Történelmi események a mai napon (November 19.)

Viharos évszázadok eseményei sűrűsödnek ezen a napon: elhangzik a Gettysburgi beszéd, először találkozik Reagan és Gorbacsov, Kína fellövi első Shenzhou űrhajóját, miközben az Atlanti-óceánon a Prestige olajkatasztrófája okoz példátlan környezeti pusztítást...

APP
szerda 07:11

APPok, Amik Ingyenesek MA, 11/18

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     KORG iMS-20 (iPhone/iPad)Az iMS-20 egy fizikai modellezésen alapuló, analóg szintetizátor-alkalmazás, amely hűen idézi meg a legendás Korg MS-20 szintetizátort...

szerda 06:05

Történelmi események a mai napon (November 18.)

Ma keresztes hadjárat indulásától és gyarmati birodalmak alkujától grandiózus időzónareformon, forradalmi győzelmen és modern háborús fordulópontokon át a Vörös Bolygó felé tartó űrszonda indulásáig ível a nap krónikája...

APP
kedd 07:11

APPok, Amik Ingyenesek MA, 11/17

Fizetős iOS appok és játékok, amik ingyenesek a mai napon.     KORG iMS-20 (iPhone/iPad)Az iMS-20 egy korszerű digitális zeneszerkesztő, amely a legendás Korg MS-20 szintetizátort kelti életre...