Pandora, Gabriella
-3 °C
3 °C

A Candy Crush nem videojáték, hanem matematikai probléma

2014.03.12. 10:20
A Candy Crush nehéz, de egy matematikus szerint a játék számítástudományi problémák egy speciális csoportjába tartozik. Ha elég sokáig játszunk vele, egy napon a játék segíthet ezeket megoldani.

Toby Walsh, a New South Wales egyetem kutatója a Candy Crush Saga egy speciális verzióját elemezve megállapította, hogy a játék tulajdonképpen az NP-nehéz matematikai problémák közé tartozik (lásd a keretest). Ezekre jellemzően nehéz megoldást találni.

Azoknak, akik egy kő alatt vagy internet nélkül töltötték az elmúlt éveket, elmondanánk: a 2012-ben debütált Candy Crush egy piszkosul addiktív logikai játék, amit világszerte 93 millióan játszanak pécén vagy okostelefonokon. A színkirakós-kombinálós játék menetét nehéz lenne szóban elmagyarázni, de videón már egyértelműek a játékszabályok:

Walsh tanulmányozta a Candy Crush Saga egy általános verzióját, ahol a pálya mérete korlátlan, majd feltette magának a kérdést: lehetséges olyan sorrendben végrehajtani a műveleteket, hogy az egy adott pontszámot eredményezzen?

Hogy a feladványból matematikai kérdést csináljon, olyan sorrendben rendezte el a cukorkákat, hogy az megfeleljen egy matematikai feladvány, a Boole-kielégíthetőség logikai állításainak. Ez azt vizsgálja, hogy egy sor logikai állítás egymást erősíti, vagy ellentmondanak egymásnak. Ennek az eldöntése viszont már NP-nehéz – és ez azt bizonyítja, hogy a Walsh által játszott Candy Crush-verzió is az.

Hasonló módszerekkel már Nintendo-játékokról – például a Super Mario Brosról, illetve a Legend of Zeldáról – is megállapították, hogy NP-nehezek. Sőt, másfél évtizede még az aknakeresővel szemléltették ugyanezt a jelenséget.

Most elmagyarázzuk, miről szól a P avagy NP probléma; ha Ön ezzel tisztában van, lapozzon a keretes rész végére az utolsó két mondatért. 

P avagy NP?

A P avagy NP probléma a matematikai feladatok megoldhatóságával kapcsolatos kérdés - egészen pontosan arról szól, hogy a kettő valójában különböző vagy ugyanaz. Az elvárt válasz: különbözők, de ezt eddig nem sikerült bebizonyítani. A "P avagy NP" probléma eldöntése a gyakorlatban azt jelenti, hogy egy feladatról megállapítható-e, hogy ésszerű időn belül megoldhatja-e mondjuk egy számítógép.

A non-P probléma alapvetően egy P-nél nehezebb probléma, aminek nincs adott időn belül tuti megoldása. A non-P probléma létezését az tudja bebizonyítani, aki nekiül és az összes lehetséges számítási módszert végigpróbálgatva állítja, hogy egyik sem polinomiális, és nem hullik el közben végelgyengülés miatt. Eddig senkinek sem sikerült.

A non-P gyanúsított problémák egy csoportját NP-nek nevezzük (nondeterminisztikus-P). Az NP olyan probléma, amelynél meg tudjuk állapítani, hogy megoldása P. Ezen belül van még egy kisebb csoport, amelyet NP-teljes problémáknak nevezünk - ezek olyanok, amelyekhez egyetlen polinomiális megoldás kulcs lenne minden NP-hez. Ha tehát egy NP-teljes problémának P megoldása akad, minden NP P-nek bizonyulna. A feltevés az, hogy mivel ilyen megoldás nincs, minde NP-teljes probléma non-P.

Walsh megállapította, hogy a Candy Crush Saga is NP-teljes játék. Ezek szerint világszerte 93 millióan foglalkoznak egy igen összetett matematikai problémával.

Köszönjük, hogy minket olvasol minden nap!

Ha szeretnél még sokáig sok ilyen, vagy még jobb cikket olvasni az Indexen, ha szeretnéd, ha még lenne független, nagy elérésű sajtó Magyarországon, amit vidéken és a határon túl is olvasnak, akkor támogasd az Indexet!

Tudj meg többet az Index támogatói kampányáról!

Milyen rendszerességgel szeretnél támogatni minket?

Mekkora összeget tudsz erre szánni?

Mekkora összeget tudsz erre szánni?