Magic: The Gathering oficialiai yra sudėtingiausias žaidimas pasaulyje

Žaidimo kortų „Magic: The Gathering“ paketų vaizdas Natanas Rupertas

Magic: The Gathering yra kortų žaidimas, kuriame burtininkai buria, išsikviečia būtybes ir išnaudoja magiškus objektus, kad nugalėtų savo priešininkus.

Žaidime du ar daugiau žaidėjų surenka po 60 skirtingų galių kortų kaladę. Jie pasirenka šias kaladės iš maždaug 20 000 kortelių, sukurtų žaidimui tobulėjant. Nors ir panašus į vaidmeninius fantastinius žaidimus, tokius kaip Dungeons and Dragons, jame yra daug daugiau kortelių ir sudėtingesnių taisyklių nei kituose kortų žaidimuose.

Ir tai kelia įdomų klausimą: kur tarp realaus pasaulio žaidimų (tų, kuriuos žmonės iš tikrųjų žaidžia, o ne hipotetinių žaidimų teoretikai paprastai laiko), kur magija yra sudėtingesnė?

Šiandien mes gauname atsakymą dėl Alexo Churchillio, nepriklausomo tyrinėtojo ir stalo žaidimų dizainerio Kembridže, JK, darbo; Stella Biderman Džordžijos technologijos institute; ir Austinas Herrickas Pensilvanijos universitete.

Jo komanda pirmą kartą išmatavo žaidimo skaičiavimo sudėtingumą, užkoduodama jį tokiu būdu, kurį galėtų žaisti kompiuteris ar Turingo mašina. Ši konstrukcija tai patvirtina Magija: susibūrimas Jie sako, kad tai sudėtingiausias literatūroje žinomas realaus pasaulio žaidimas.

Pirma, šiek tiek fono. Svarbus informatikos uždavinys – nustatyti, ar problemą galima išspręsti iš esmės. Pavyzdžiui, nuspręsti, ar du skaičiai yra santykinai pirminiai (kitaip tariant, ar jų didžiausias bendras daliklis yra didesnis nei 1), yra užduotis, kurią galima atlikti atliekant ribotą tiksliai apibrėžtų žingsnių skaičių, todėl ją galima apskaičiuoti.

Įprastame šachmatų žaidime taip pat galima apskaičiuoti, ar balta spalva turi laimėjimo strategiją. Procesas apima visų įmanomų ėjimų sekos testavimą, kad sužinotumėte, ar balta spalva gali priversti laimėti.

Tačiau nors abi šios problemos yra apskaičiuojamos, joms išspręsti reikalingi ištekliai labai skiriasi.

Čia atsiranda skaičiavimo sudėtingumo sąvoka. Tai reitingas, pagrįstas problemoms išspręsti reikalingais ištekliais.

Šiuo atveju nuspręsti, ar du skaičiai yra santykinai pirminiai, galima išspręsti keliais žingsniais, kurie yra proporcingi įvestų skaičių daugianario funkcijai. Jei įvestis yra x , svarbiausias daugianario funkcijos terminas yra formos Cxn , kur C ir n yra konstantos. Tai patenka į klasę, žinomą kaip P , kur P reiškia daugianarį laiką.

Priešingai, šachmatų problema turi būti išspręsta brutalia jėga, o žingsnių skaičius didėja proporcingai eksponentinei įvesties funkcijai. Jei įvestis yra x , svarbiausias eksponentinės funkcijos terminas yra formos Cnx , kur C ir n yra konstantos. Ir kaip x padidėja, šis tampa didesnis daug greičiau nei Cxn . Taigi tai patenka į sudėtingesnės kategorijos EXP arba eksponentinį laiką.

Be to, yra įvairių kitų įvairaus sudėtingumo kategorijų ir netgi problemų, kurioms išspręsti nėra algoritmų. Jie vadinami neapskaičiuojamais.

Išsiaiškinti, į kurią sudėtingumo klasę patenka žaidimai, yra sudėtingas reikalas. Dauguma realaus pasaulio žaidimų turi ribotas sudėtingumo ribas, pvz., žaidimų lentos dydį. Dėl to daugelis jų yra nereikšmingi sudėtingumo požiūriu. Dauguma realaus pasaulio žaidimų algoritminių žaidimų teorijos tyrimų pirmiausia buvo nagrinėti dažniausiai žaidžiamų žaidimų apibendrinimais, o ne realiomis žaidimų versijomis, sako Churchillis ir kt.

Taigi žinoma, kad tik keli realaus pasaulio žaidimai yra nereikšmingi. Tai apima „Dots-and-Boxes“, „Jenga“ ir „Tetris“. Manome, kad nėra žinoma, kad joks realaus pasaulio žaidimas būtų sunkesnis už NP prieš šį darbą, sako Churchillis ir kt.

Naujasis darbas rodo, kad „Magic: the Gathering“ yra daug sudėtingesnis. Metodas iš principo yra paprastas. Churchillis ir bendradarbiai pradeda versdami kiekvienos kortelės galias ir savybes į žingsnių rinkinį, kurį galima užkoduoti.

Tada jie žaidžia žaidimą tarp dviejų žaidėjų, kuriame žaidimas vystosi Turingo mašinoje. Ir galiausiai jie parodo, kad nustatyti, ar vienas žaidėjas turi laimėjimo strategiją, prilygsta garsiajai kompiuterių mokslo sustabdymo problemai.

Tai yra problema, kai reikia nuspręsti, ar kompiuterio programa su konkrečia įvestimi baigs veikti, ar tęsis amžinai. 1936 metais Alanas Turingas įrodė, kad joks algoritmas negali nustatyti atsakymo. Kitaip tariant, problema yra neapskaičiuojama.

Taigi pagrindinis Churchillio ir bendradarbių rezultatas yra tas, kad magijos žaidimo rezultato nustatymas yra neapskaičiuojamas. Tai pirmasis rezultatas, parodantis, kad egzistuoja realaus pasaulio žaidimas, kurio laimėjimo strategija neapskaičiuojama, sako jie.

Tai įdomus darbas, keliantis svarbius pagrindinius žaidimų teorijos klausimus. Pavyzdžiui, Churchillis ir bendradarbiai teigia, kad pagrindinė formalioji žaidimų teorija daro prielaidą, kad bet koks žaidimas turi būti apskaičiuojamas. Magija: susibūrimas Jie sako, kad tai neatitinka prielaidų, kurias dažniausiai daro kompiuterių mokslininkai modeliuodami žaidimus.

Tai rodo, kad kompiuterių mokslininkai turi persvarstyti savo idėjas apie žaidimus, ypač jei jie tikisi sukurti vieningą skaičiavimo žaidimų teoriją. Akivaizdu, kad magija yra musė užkerėtame tepe, kiek tai susiję.

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

paslėpti