Zoltán
10 °C
21 °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.