Kombinatorinė žaidimų teorija CGT apibrėžimas, savybės ir pavyzdžiai

Kombinatorinė žaidimų teorija, dažnai sutrumpinama CGT, yra taikomosios matematikos ir teorinės informatikos sritis, tirianti deterministinius, visiškai informatyvius, nuoseklius (turn-based) kombinatorinius žaidimus. Ji skiriasi nuo „tradicinės“ arba „ekonominės“ žaidimų teorijos, kuri dažniau nagrinėja strategijas ir sprendimus prielaidoje apie racionalius veikėjus, galinčius turėti tikimybių arba paslėptos informacijos elementų. CGT istorija glaudžiai susijusi su tolydine nešališkų žaidimų analize — ypač dviejų žaidėjų žaidimo Nim, — ir orientuojasi į tam tikrų kombinatorinių žaidimų „sprendimą“, t. y. kiekvieno žaidimoįvertinimą, lyginimą ir sujungimą su kitais žaidimais.

Kad žaidimas būtų laikomas kombinatoriniu, jis paprastai turi atitikti kelias pagrindines sąlygas. Autoriai ir vadovėliai tai aprašo įvairiai, bet dažniausiai pateikiama tokia sąlygų seka: sąlygas.

Žaidime turi būti bent du žaidėjai.
Žaidimas turi būti nuoseklus (t. y. žaidėjai keičiasi ėjimais).
Žaidimas turi būti visiškai informatyvus (t. y. nėra paslėptos informacijos, skirtingai nei, pavyzdžiui, pokeryje).
Žaidimas turi būti deterministinis (t. y. neturėti atsitiktinių elementų). Sėkmė nėra žaidimo dalis.
Žaidime turi būti ribotas galimų ėjimų skaičius (finitumas arba bent jau tokia struktūra, kad analizuojamas medžio ilgis yra baigtinis).
Žaidimas turi baigtis (negali tęstis be galo).
Žaidimas dažnai laikomas pasibaigusiu, kai vienas iš žaidėjų nebegali atlikti ėjimo (priklausomai nuo taisyklių — tai reiškia pralaimėjimą arba kitą išeitį).

Savybės ir pagrindinės sąvokos

CGT daugiausia nagrinėja dviejų žaidėjų žaidimus, kuriuose laimi vienas iš žaidėjų (normal play konvencija: paskutinį ėjimą padaręs žaidėjas laimi). Svarbiausios sąvokos ir savybės:

Žaidimo medis: kiekvieną žaidimo būseną (padėtį) galima pavaizduoti medžiu, kur iš viršūnės išeina tam tikros galimos parinktys (options). Kiekviena viršūnė yra naujas žaidimas arba padėtis, atsiradusi atlikus ėjimą.
Impartialūs ir partizaniniai žaidimai: impartialiuose žaidimuose abu žaidėjai turi tas pačias galimybes iš bet kurios padėties (pvz., Nim), o partizaniniuose galimybės gali skirtis priklausomai nuo žaidėjo (pvz., Hackenbush, Domineering).
Disjunktyvinė suma: dviejų žaidimų suma yra žaidimas, kuriame kiekvienas žaidėjas per savo ėjimą gali atlikti ėjimą tik viename iš sudedamųjų žaidimų, kitus palikdamas nepakitusius. Tai pagrindinė operacija CGT, leidžianti analizuoti sudėtinius žaidimus kaip komponentų suma.
Žaidimo vertė: CGT priskiria kiekvienai pozicijai tam tikrą verčių kategoriją ar skaičių (pvz., nimberiai, realios arba „surreal“ reikšmės), kurios leidžia prognozuoti, kuris žaidėjas turi pranašumą ir kaip žaidimai elgiasi sumose.
Kanoniškos formos ir lygybė: žaidimai gali būti sutraukti iki kanoniškos (supaprastintos) formos, o dvi padėtys laikomos lygiomis, jei jas galima pakeisti viena kita be poveikio bet kokiai sumai su bet kokiu trečiu žaidimu.
Išeitinės klasifikacijos: įprasta klasifikacija pagal rezultatus — P (Previous, pralaimintis žaidėjas, jei kitas ėjimas priklauso varžovui), N (Next — laiminti žaidėjas, jei ėjimą turi kitas) ir partizaniniuose žaidimuose papildomos klasės L ir R (laimi kairysis arba dešinysis žaidėjas).

Impartialių žaidimų teorija ir Sprague–Grundy

Impartialių žaidimų analizėje labai svarbi Sprague–Grundy teorija. Ji teigia, kad kiekviena impartiali pozicija atitinka vieną nimberį (Grundy skaičių), o žaidėjo strategija sumažinama iki Nim žaidimo analoogo. Grundy skaičius G pozicijai apskaičiuojamas kaip mex (minimum excludant) — mažiausias neigiamasis sveikas skaičius, nepriklausantis išvestinių pozicijų Grundy reikšmių. Dėl to disjunktyvinės sumos nimberis yra xor (bitinis išskirtinis ARV) visų komponentų nimberių. Tai leidžia spręsti sudėtingas sumas, pagrindžiant, kodėl Nim — kertinis pavyzdys CGT.

Partizaniniai žaidimai, „surreal“ skaičiai ir papildomos sąvokos

Conway ir jo bendradarbiai parodė, kad partizaninių žaidimų pasaulis yra daug turtingesnis: kai kurios pozicijos atitinka realius skaičius arba platesnę skaičių sistemą — surreal skaičius, kurias Conway vėliau suformulavo platesniame darbe. Taip pat egzistuoja tokios sąvokos kaip žaidimo temperatūra ar „karštumas“ (nurodanti pozicijos potencialų pranašumą, kurį verta „nusikeisti“ prieš žaidžiant kitur) ir infinitesimalai bei komponentų vertės, kurie padeda vertinti sudėtingas sumas ir optimalias strategijas partizaniniuose kontekstuose.

Pavyzdžiai

Nim — klasikinis impartialus žaidimas: yra kelios krūvos akmenų; žaidėjai paeiliui paima bet kokį skaičių akmenų iš vienos krūvos. Nim sprendžiamas naudojant xor operaciją tarp krūvų dydžių (nimberiai).
Kayles — impartialus žaidimas, kai žaidėjai nuima vieną arba dvi gretimas figūras iš eilės; jo Grundy seka galima apskaičiuoti rekursyviai.
Hackenbush — partizaninis žaidimas su spalvotomis brūkšniais ir „šaknimis“, suteikiantis pavyzdį, kaip žaidimų vertės gali tapti realiais arba surreal skaičiais.
Domineering — partizaninis žaidimas, kuriame vienas žaidėjas deda vertikalias domine figūras, kitas — horizontalias; demonstruoja strateginį skirtumą tarp žaidėjų galimybių.

Istorija ir pagrindiniai autoriai

Šios teorijos plėtojime didelį indėlį padarė Elwyn Berlekamp, John Conway ir Richard Guy. Jie pradėjo glaudžiai bendradarbiauti septintajame dešimtmetyje, vėliau išleidę platų darbą pavadinimu "Laimėjimo būdai jūsų matematiniams žaidimams", kuris tapo pagrindiniu CGT šaltiniu ir populiarinimo knyga. Conway taip pat sukūrė surreal skaičių teoriją, kuri glaudžiai susijusi su žaidimų verte ir struktūra.

Praktinis panaudojimas ir tolesni tyrimai

Kombinatorinė žaidimų teorija turi tiek grynai teorinį, tiek praktinį reikšmingumą: ji taikoma kompiuterinių žaidimų dirbtinio intelekto kūrime (analizė be atsitiktinumo), matematinių galvosūkių sprendime, optimalių strategijų konstravime ir net kai kuriose algoritminėse problemose bei formaliose sistemose. Tolimesni tyrimai apima misère žaidimų (kur taisyklės dėl paskutinio ėjimo laimėtojo keičiasi), ilgesnio periodo arba begalinių pozicijų analizę, kompleksinių temperatūrų ir infinitesimalų tyrimą bei sudėtingų žaidimų kanonizaciją.

Apibendrinant, CGT suteikia turtingą kalbą ir priemones, leidžiančias objektyviai aprašyti, suskirstyti ir spręsti įvairius kombinatorinius žaidimus — nuo paprastų Nim tipo uždavinių iki sudėtingų partizaninių konstruktų su netradicinėmis vertėmis.

Apibrėžtys

Teorijoje yra du žaidėjai, vadinami kairiuoju ir dešiniuoju. Žaidimas yra tai, kas leidžia kairiajam ir dešiniajam atlikti ėjimus į kitus žaidimus. Pavyzdžiui, šachmatų žaidime yra įprasta pradinė padėtis. Tačiau šachmatų partiją po pirmojo ėjimo taip pat galima laikyti kitu žaidimu su kitokia sąranga. Taigi kiekviena pozicija taip pat vadinama partija.

Žaidimai žymimi {L|R}. L {\displaystyle L} $L$ - tai žaidimai, į kuriuos gali pereiti kairysis žaidėjas. R {\displaystyle R} $R$ - tai žaidimai, į kuriuos gali pereiti dešinysis žaidėjas. Jei žinote šachmatų notaciją, tai įprasta šachmatų konfigūracija yra žaidimas

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Taškai "..." reiškia, kad yra daug ėjimų, todėl rodomi ne visi.

Šachmatai yra labai sudėtingi. Geriau galvoti apie lengvesnius žaidimus. Pavyzdžiui, apie Nim yra daug paprasčiau galvoti. Nim žaidžiama taip:

Yra nulis ar daugiau skaitiklių krūvelių.
Savo ėjimo metu žaidėjas gali paimti tiek žetonų iš vienos krūvelės, kiek nori.
Žaidėjas, kuris negali atlikti ėjimo, pralaimi.

Lengviausias "Nim" žaidimas prasideda be jokių skaitiklių! Tokiu atveju nė vienas žaidėjas negali judėti. Tai pavaizduota kaip {|}. Abi pusės yra tuščios, nes nė vienas žaidėjas negali judėti. Pirmasis žaidėjas negali judėti, todėl pralaimi. CGT žmonės dažnai rašo {|} kaip simbolį 0 (nulis).

Kitame lengviausiame žaidime yra tik viena krūvelė su vienu skaitikliu. Jei kairysis žaidėjas eina pirmas, jis turi pasiimti skaitiklį, o dešinysis neturi jokių ėjimų ({|} arba 0). Jei vietoj to dešinysis žengia pirmas, kairysis nebeturės jokių ėjimų. Taigi ir kairė, ir dešinė gali atlikti ėjimą į 0. Tai pavaizduota kaip {{|}|{|}}, arba {0|0}. Laimi tas žaidėjas, kuris pirmas atlieka ėjimą. Žaidimai, lygūs {0|0}, yra labai svarbūs. Jie rašomi su simboliu * (žvaigždute).

Klausimai ir atsakymai

K: Kas yra kombinacinė žaidimų teorija?

A: Kombinatorinė žaidimų teorija (CGT) - tai taikomosios matematikos ir teorinės informatikos šaka, tirianti kombinatorinius žaidimus ir besiskirianti nuo "tradicinės" arba "ekonominės" žaidimų teorijos.

K: Kokias sąlygas turi atitikti žaidimas, kad būtų laikomas kombinatoriniu žaidimu?

A: Kad žaidimas būtų laikomas kombinatoriniu žaidimu, jame turi būti bent du žaidėjai, jis turi būti nuoseklus (t. y. žaidėjai keičiasi ėjimais), jame turi būti tobula informacija (t. y. jokia informacija nėra paslėpta), jis turi būti deterministinis (t. y. neatsitiktinis), sėkmė negali būti žaidimo dalis, turi būti apibrėžtas galimų ėjimų skaičius, žaidimas turi galiausiai baigtis ir žaidimas turi baigtis, kai vienas iš žaidėjų nebegali judėti.

Klausimas: Kokio tipo žaidimams skirta kombinatorinė žaidimų teorija?

A: Kombinatorinė žaidimų teorija daugiausia dėmesio skiria dviejų žaidėjų baigtiniams žaidimams, kurie turi laimėtojus ir pralaimėtojus (t. y. nesibaigia lygiosiomis).

K: Kaip vaizduojami šių tipų žaidimai?

A.: Tokius žaidimus galima pavaizduoti medžiu, kurio kiekviena viršūnė vaizduoja žaidimo rezultatą, gautą atlikus tam tikrą ėjimą iš žemiau esančio medžio.

K: Kokie yra kai kurie CG teoretikų tikslai?

A: Kai kurie CG teoretikų tikslai yra rasti šių tipų žaidimų vertes ir suprasti "žaidimo papildymo" sąvoką, kai kiekvienas žaidėjas atlieka tik vieną ėjimą dviejuose skirtinguose žaidimuose, palikdamas kitą ėjimą nepakeistą savo ėjimo metu.

K: Kas įkūrė CGT?

A: Elwyn Berlekamp, John Conway ir Richard Guy yra laikomi CGT įkūrėjais. 1960 m. jie išleido darbą "Winning Ways for Your Mathematical Plays" ("Laimėjimo būdai jūsų matematiniams žaidimams").