A Candy Crush nem videojáték, hanem matematikai probléma
További Tech cikkek
-
Olyat hibát produkál a Windows, hogy garantáltan mindenki kiugrik a székéből - Könnyen megeshet, hogy a Google kénytelen lesz eladni a Chrome-ot
- A Huawei hivatalosan is bejelentette, előrendelhető a Mate 70
- Lesöpörheti Elon Musk X-ét a Bluesky, már a Google is relevánsabbnak találja
- Ezek a leggyakrabban használt jelszavak – érdemes változtatni, ha ön is használja valamelyiket
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övesse az Indexet Facebookon is!
Követem!
