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.

  1. Žaidime turi būti bent du žaidėjai.
  2. Žaidimas turi būti nuoseklus (t. y. žaidėjai keičiasi ėjimais).
  3. Žaidimas turi būti visiškai informatyvus (t. y. nėra paslėptos informacijos, skirtingai nei, pavyzdžiui, pokeryje).
  4. Žaidimas turi būti deterministinis (t. y. neturėti atsitiktinių elementų). Sėkmė nėra žaidimo dalis.
  5. Žaidime turi būti ribotas galimų ėjimų skaičius (finitumas arba bent jau tokia struktūra, kad analizuojamas medžio ilgis yra baigtinis).
  6. Žaidimas turi baigtis (negali tęstis be galo).
  7. Ž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.