Kombinatoriskā spēļu teorija — definīcija, noteikumi un spēļu vērtības

Kombinatoriskā spēļu teorija (CGT) ir matemātikas un teorētiskās datorzinātnes nozare, kas pēta tā dēvētās kombinatoriskās spēles — deterministiskas, perfektas informācijas, secīgas spēles bez izredzēm. Tā atšķiras no "tradicionālās" jeb "ekonomiskās" spēļu teorijas, jo CGT galvenokārt koncentrējas uz to, kā noskaidrot, kurš spēlētājs ar perfektu spēli uzvarēs, un kā raksturot spēļu struktūru un to summas. Vēsturiski CGT izauga, pētot divu spēlētāju spēles, it īpaši slaveno Nim, un attīstījās apkārt idejai par kombinatorisku spēļu "risināšanu" ar precīzām matemātiskām vērtībām.

Pamattermiņi un kritēriji

Lai spēle tiktu uzskatīta par kombinatorisku spēli, parasti jāizpildās noteiktiem nosacījumiem:

Spēlē ir vismaz divi spēlētāji (parasti divi).
Spēle ir secīga — spēlētāji maiņās izpilda gājienus.
Ir ideāla informācija — visas pozīcijas un iespējamie gājieni ir zināmi abiem spēlētājiem (nav slēptas informācijas kā pokerā).
Spēle ir deterministiska — tajā nav izredžu vai nejaušības elementu. Veiksme nav spēles sastāvdaļa.
Spēlei ir ierobežots iespējamību skaits — katrā pozīcijā ir tikai galīgs skaits iespējamo gājienu.
Spēlei ir jābūt galīgai — pastāv galīgs gājienu skaits, un process beidzas.
Spēle beidzas tad, kad viens no spēlētājiem vairs nevar pārvietoties.

CGT bieži ierobežo pētījumu uz spēļu apakškopu, kuras beidzas ar uzvarētāju un zaudētāju (t.i., bez neizšķirtiem). Tomēr dažas paplašinātas pieejas paņem vērā arī misère noteikumus (kur pēdējais gājiens zaudē), izmaiņas partizānu spēlēs u.c.

Spēļu klasifikācija

Galvenās kategorijas:

Impartiālās spēles — abi spēlētāji var izmantot vienus un tos pašus gājienus no jebkuras pozīcijas (piemērs: Nim). Šīm spēlēm piemērojama Sprague–Grundy teorija.
Partizānas spēles — katram spēlētājam var būt atšķirīgas iespējas (piemērs: Hackenbush, Domineering). Šajās spēlēs parādās plašāks vērtību klāsts, tostarp realie skaitļi, infinitesimāli un "fuzzy" vērtības.
Normal play — standarta noteikums: spēlētājs, kurš nevar gājienu izdarīt, zaudē. Ir arī misère varianti, kuros pēdējais gājiens noved pie zaudējuma.

Spēļu attēlojums un risināšana

Kombinatoriskās spēles parasti attēlo kā koku (pozīciju grafu), kur katra virsotne atbilst kādai pozīcijai un katra mala — iespējamiem gājieniem uz bērnpozīcijām. Lai noteiktu, kurš spēlētājs ir uzvarētājs, izmanto atpakaļejošu indukciju no galīgajām pozīcijām.

Impartiālajās spēlēs būtiska ir Sprague–Grundy teorema: katrai pozīcijai var piešķirt skaitli (Grundy vērtību jeb nimber), kas ir pozīciju ekvivalents kādam Nim kaudam. Divu pozīciju disjunkcija (sumsumēšana) darbojas ar bitu ekskluzīvo vai (XOR) nimberu līmenī — šo īpašību izmanto, lai ātri atrastu uzvarētāju Nim tipa situācijās.

Piemērs: vienam Nim kaudam ar k akmeņu Grundy vērtība ir k; diviem kaudiem ar izmēriem a un b uzvarētājs ir tas, kurš var izveidot pozīciju ar nim sum = a XOR b = 0 (tas nozīmē P-klasi).

Spēļu vērtības un teorētiskie konstrukti

Partizānu spēlēs matemātiķi (īpaši Dž. Konvejs) izstrādāja plašu vērtību sistēmu: surreal skaitļi (Conway skaitļi), infinitesimāli, un īpašas objekta vērtības kā * (tā dēvētais "star", kas norāda uz pozīciju, kas uzvar nākošajam spēlētājam, bet nav vienkāršs reāls skaitlis). Šīs vērtības ļauj salīdzināt pozīcijas, meklēt kanoniskas formas un saprast, kā spēles uzvedas to summā.

Vēl viens svarīgs jēdziens ir spēļu temperatūra un entropija — daļēji apzīmē, cik steidzami ir gājieni pozīcijā (karstas spēles prasa tūlītēju rīcību), un nosaka, kā rīkoties, spēļu summā salīdzinot "karstumu".

Summa un spēļu kombinācijas

Divu spēļu summa (disjunktīvā summa) ir jauna spēle, kurā katrā gājienā spēlētājam jāizdara gājiens tieši vienā no komponentēm, otra paliek nemainīta. Šī struktūra ir centrāla CGT, jo sarežģītas pozīcijas bieži sadala vienkāršākās daļās, kuru vērtības pēc tam “saskaita” ar atbilstošām kombinācijas likmēm (nimberiem vai surreāliem skaitļiem).

Praktiskā nozīmē tas nozīmē: ja pozīciju var sadalīt neatkarīgās daļās, tās rezultātu var iegūt, analizējot katru daļu atsevišķi un pēc tam piemērojot atbilstošas kombinācijas noteikumus (piem., XOR nimberiem impartiālajās spēlēs).

Rezultātu klasifikācija

Pozīcijas bieži klasificē pēc iznākuma ar perfektiem gājieniem:

N (Next) — nākošajam spēlētājam ir uzvaras stratēģija;
P (Previous) — iepriekšējam (t.i., otram) spēlētājam ir uzvaras stratēģija;
L un R — atsevišķi nosacījumi partizānām spēlēm, kur gana spēcīgas pozīcijas var nodrošināt vienam vai otram spēlētājam uzvaru neatkarīgi no secības.

Piemēri un klasiskas spēles

Tipiski CGT piemēri: Nim, Kayles, take-and-break spēles, Hackenbush, Domineering un daudzas abstraktas kombinatoriskas spēles. Nim ir pamata paradigmas piemērs impartiālajām spēlēm un demonstrē Sprague–Grundy pieeju.

Vēsture un galvenie devēji

CGT modernā forma veidojās 20. gadsimta vidū. Galvenie pamatlicēji ir Elvins Berlekamps, Džons Konvejs un Ričards Gajs, kas 20. gadsimta 60. gados sadarbojās un vēlāk publicēja monumentālu darbu Winning Ways for Your Mathematical Plays (Uzvaras ceļi matemātiskajām spēlēm) — grāmatu, kas ieviesa daudzus jēdzienus, terminoloģiju un plašu piemēru klāstu.

Praktiskās piezīmes

Kombinatoriskā spēļu teorija saplūst ar algoritmu analīzi un sarežģītības teoriju — daudzus jautājumus par optimālu spēli vai spriedumu iegūšanu var klasificēt kā grūti aprēķināmus (bieži PSPACE-grūtus vai NP-grūtus konkrētās klases variācijās). Tomēr CGT sniedz spēcīgus rīkus un strukturālas metodes, lai analizētu plašu spēļu klāstu un pateiktu, kurš spēlētājs ar perfektu spēli uzvarēs, kā arī kādas ir optimālās stratēģijas vai vērtības.

Ja vēlaties, varu pievienot īsus matemātiskus piemērus — Sprague–Grundy mex aprēķinu, kā arī īsu demonstrāciju Nim summas izmantošanai vai parādīt, kā veidojas dažu partizānu spēļu surreālās vērtības.

Definīcijas

Teorijā ir divi spēlētāji - kreisais un labais. Spēle ir kaut kas tāds, kas ļauj kreisajam un labajam izdarīt gājienus uz citām spēlēm. Piemēram, šaha spēlē ir ierasts sākuma izkārtojums. Tomēr par šaha spēli pēc pirmā gājiena var domāt arī kā par citu spēli ar citu uzstādījumu. Tāpēc katru pozīciju arī sauc par spēli.

Spēles apzīmē ar {L|R}. L {\displaystyle L} $L$ ir spēles, uz kurām var pāriet kreisais spēlētājs. R {\displaystyle R} $R$ ir spēles, kurās var pārvietoties labējais spēlētājs. Ja jūs zināt šaha notāciju, tad parastā šaha izkārtojuma shēma ir partija

{ 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 \}$

Punktu "..." nozīmē, ka ir daudz gājienu, tāpēc nav parādīti visi gājieni.

Šahs ir ļoti sarežģīts. Labāk ir domāt par vieglākām spēlēm. Piemēram, par Nim ir daudz vienkāršāk domāt. Nim spēlē šādi:

Ir nulle vai vairāk skaitītāju kaudzīšu.
Gājiena laikā spēlētājs var paņemt no vienas kaudzes tik žetonu, cik vien vēlas.
Spēlētājs, kurš nevar izdarīt gājienu, zaudē.

Vienkāršākā Nim spēle sākas bez skaitītājiem! Šādā gadījumā neviens no spēlētājiem nevar pārvietoties. Tas ir attēlots kā {|}. Abas puses ir tukšas, jo neviens no spēlētājiem nevar pārvietoties. Pirmais spēlētājs nevar pārvietoties, tāpēc viņš zaudēs. CGT spēlē {|} bieži raksta kā simbolu 0 (nulle).

Nākamajā vienkāršākajā spēlē ir tikai viena kaudzīte ar vienu skaitītāju. Ja pirmais dodas kreisais spēlētājs, viņam ir jāņem skaitītājs, bet labajam spēlētājam nav gājienu ({|} vai 0). Ja tā vietā pirmais gājienu izdara labējais, kreisajam vairs nebūs gājienu. Tātad gan kreisais, gan labais var izdarīt gājienu uz 0. Tas tiek attēlots kā {{|}|{|}} jeb {0|0}. Uzvar spēlētājs, kurš pirmais izdarīs gājienu. Spēles, kas vienādas ar {0|0}, ir ļoti svarīgas. Tās tiek rakstītas ar simbolu * (zvaigzne).

Jautājumi un atbildes

J: Kas ir kombinatorisko spēļu teorija?

A: Kombinatorisko spēļu teorija (CGT) ir lietišķās matemātikas un teorētiskās datorzinātnes nozare, kas pēta kombinatoriskās spēles un atšķiras no "tradicionālās" vai "ekonomiskās" spēļu teorijas.

J: Kādiem nosacījumiem jāatbilst spēlei, lai to varētu uzskatīt par kombinatorisku spēli?

A: Lai spēli varētu uzskatīt par kombinatorisko spēli, tajā jābūt vismaz diviem spēlētājiem, tai jābūt secīgai (t. i., spēlētāji pārmaiņus veic gājienus), tai jābūt ar perfektu informāciju (t. i., nekāda informācija netiek slēpta), tai jābūt deterministiskai (t. i., tā nedrīkst būt nejaušība), spēlē nedrīkst būt iesaistīta veiksme, tai jābūt noteiktam iespējamo gājienu skaitam, spēlei galu galā ir jābeidzas un spēlei ir jābeidzas, kad viens spēlētājs vairs nevar izdarīt gājienu.

J: Uz kāda veida spēlēm koncentrējas kombinatorisko spēļu teorija?

A: Kombinatoriskā spēļu teorija galvenokārt koncentrējas uz divu spēlētāju galīgām spēlēm, kurās ir uzvarētāji un zaudētāji (t. i., kuras nebeidzas neizšķirti).

J: Kā tiek attēlotas šāda veida spēles?

A.: Šāda veida spēles var attēlot ar kokiem, kur katra virsotne attēlo spēles rezultātu, ko iegūst, veicot noteiktu gājienu tieši zem tās esošajā kokā.

J: Kādi ir daži CG teorētiķu mērķi?

A.: Daži CG teorētiķu mērķi ir atrast vērtības šāda veida spēlēm, kā arī izprast jēdzienu "spēles papildinājums", kas nozīmē, ka katrs spēlētājs veic tikai vienu gājienu divās dažādās spēlēs, atstājot otru gājienu nemainīgu savā gājienā.

J: Kas izveidoja CGT?

A: Par CGT dibinātājiem tiek uzskatīti Elvins Berlekamps, Džons Konvejs un Ričards Gajs (Richard Guy), kuri 1960. gados publicēja darbu "Uzvaras veidi matemātiskajām spēlēm".