Magic: The Gathering ir oficiāli pasaulē sarežģītākā spēle

Spēles kāršu Magic: The Gathering pakotņu attēls Neitans Rūperts

Magic: The Gathering ir kāršu spēle, kurā burvji burst, izsauc radības un izmanto burvju objektus, lai uzvarētu savus pretiniekus.

Spēlē divi vai vairāki spēlētāji katrs savāc 60 kāršu kavu ar dažādām spējām. Viņi izvēlas šos klājus no aptuveni 20 000 kāršu kopas, kas tika izveidotas spēles attīstības laikā. Lai gan tas ir līdzīgs lomu spēlēm fantāzijas spēlēm, piemēram, Dungeons un Dragons, tajā ir ievērojami vairāk kāršu un sarežģītāki noteikumi nekā citās kāršu spēlēs.

Un tas rada interesantu jautājumu: kur starp reālajām spēlēm (tās, kuras cilvēki faktiski spēlē, atšķirībā no hipotētiskajām, ko parasti uzskata spēļu teorētiķi), kur Magic ir sarežģītāks?

Šodien mēs saņemam atbildi, pateicoties Aleksa Čērčila, neatkarīga pētnieka un galda spēļu dizainera darbam Kembridžā, Apvienotajā Karalistē; Stella Bīdermane Džordžijas Tehnoloģiju institūtā; un Ostins Heriks Pensilvānijas Universitātē.

Viņa komanda pirmo reizi ir izmērījusi spēles skaitļošanas sarežģītību, iekodējot to tādā veidā, ko var spēlēt dators vai Tjūringa mašīna. Šī konstrukcija to nosaka Maģija: pulcēšanās Viņi saka, ka tā ir skaitļošanas ziņā sarežģītākā literatūrā zināmā reālās pasaules spēle.

Pirmkārt, nedaudz fona. Datorzinātnē svarīgs uzdevums ir noteikt, vai problēmu var atrisināt principā. Piemēram, izlemt, vai divi skaitļi ir relatīvi pirmskaitļi (citiem vārdiem sakot, vai to lielākais kopīgais dalītājs ir lielāks par 1), ir uzdevums, ko var veikt ierobežotā skaitā labi definētu soļu, un tāpēc tas ir aprēķināms.

Parastā šaha spēlē arī izlemt, vai baltajam ir uzvaras stratēģija, var aprēķināt. Process ietver visu iespējamo gājienu secības pārbaudi, lai noskaidrotu, vai baltā krāsa var piespiest uzvarēt.

Bet, lai gan abas šīs problēmas ir aprēķināmas, to risināšanai nepieciešamie resursi ir ļoti atšķirīgi.

Šeit parādās skaitļošanas sarežģītības jēdziens. Šis ir rangs, kura pamatā ir problēmu risināšanai nepieciešamie resursi.

Šajā gadījumā lēmumu, vai divi skaitļi ir relatīvi pirmskaitļi, var atrisināt vairākos soļos, kas ir proporcionāli ievadīto skaitļu polinoma funkcijai. Ja ievade ir x , vissvarīgākais termins polinoma funkcijā ir forma Cxn , kur C un n ir konstantes. Tas ietilpst klasē, kas pazīstams kā P , kur P apzīmē polinoma laiku.

Turpretim šaha problēma ir jāatrisina ar brutālu spēku, un soļu skaits palielinās proporcionāli ievades eksponenciālajai funkcijai. Ja ievade ir x , vissvarīgākais eksponenciālās funkcijas termins ir forma Cnx , kur C un n ir konstantes. Un kā x palielinās, tas kļūst lielāks daudz ātrāk nekā Cxn . Tātad tas ietilpst lielākas sarežģītības kategorijā, ko sauc par EXP vai eksponenciālo laiku.

Papildus tam ir dažādas citas dažādas sarežģītības kategorijas un pat problēmas, kuru risināšanai nav algoritmu. Tos sauc par neaprēķināmiem.

Noskaidrot, kurā sarežģītības klases spēlēs ietilpst, ir grūts bizness. Lielākajai daļai reālās pasaules spēļu ir noteikti sarežģītības ierobežojumi, piemēram, spēļu dēļa izmērs. Un tas daudzus no tiem padara triviālus no sarežģītības viedokļa. Lielākā daļa pētījumu par reālās pasaules spēļu algoritmisko spēļu teoriju galvenokārt ir aplūkoti parasti spēlēto spēļu vispārinājumi, nevis spēļu reālās pasaules versijas, saka Čērčils un citi.

Tātad ir zināms, ka tikai dažām reālajām spēlēm ir nenozīmīga sarežģītība. Tie ietver Dots-and-Boxes, Jenga un Tetris. Mēs uzskatām, ka nav zināms, ka neviena reāla spēle būtu grūtāka par NP pirms šī darba, saka Čērčils un citi.

Jaunais darbs parāda, ka Magic: the Gathering ir ievērojami sarežģītāks. Metode principā ir vienkārša. Čērčils un kolēģi vispirms pārvērš katras kartītes spēkus un īpašības soļu komplektā, ko var iekodēt.

Pēc tam viņi izspēlē spēli starp diviem spēlētājiem, kurā spēle izvēršas Tjūringa mašīnā. Un visbeidzot viņi parāda, ka noteikšana, vai vienam spēlētājam ir uzvaras stratēģija, ir līdzvērtīga slavenajai datorzinātņu apturēšanas problēmai.

Šī ir problēma, lai izlemtu, vai datorprogramma ar noteiktu ievadi beigs darboties vai turpināsies mūžīgi. 1936. gadā Alans Tjūrings pierādīja, ka neviens algoritms nevar noteikt atbildi. Citiem vārdiem sakot, problēma nav aprēķināma.

Tātad Čērčila un līdzbiedru galvenais rezultāts ir tāds, ka Magic spēles iznākuma noteikšana nav aprēķināma. Viņi saka, ka šis ir pirmais rezultāts, kas parāda, ka pastāv reāla spēle, kurai uzvaras stratēģijas noteikšana nav aprēķināma.

Tas ir interesants darbs, kas izvirza svarīgus spēles teorijas pamatjautājumus. Piemēram, Čērčils un kolēģi apgalvo, ka vadošā formālā spēļu teorija pieņem, ka jebkurai spēlei ir jābūt aprēķināmai. Maģija: pulcēšanās viņi saka, ka tas neatbilst pieņēmumiem, ko parasti izdara datorzinātnieki, modelējot spēles.

Tas liek domāt, ka datorzinātniekiem ir jāpārdomā savas idejas par spēlēm, it īpaši, ja viņi cer izveidot vienotu spēļu skaitļošanas teoriju. Skaidrs, ka Magic šajā ziņā ir muša apburtajā ziedē.

Atsauce: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete

paslēpties