Kombinatoriskā spēļu teorija

Kombinatoriskā spēļu teorija, pazīstama arī kā 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" jeb "ekonomiskās" spēļu teorijas. CGT radās saistībā ar taisnprātīgo spēļu teoriju, jo īpaši divu spēlētāju Nim spēli, uzsverot noteiktu veidu kombinatorisko spēļu "risināšanu".

Lai spēle būtu kombinatoriskā spēle, tai jāatbilst vairākiem nosacījumiem. Tie ir šādi:

Spēlē jābūt vismaz diviem spēlētājiem.
Spēlei ir jābūt secīgai (t. i., spēlētājiem ir jāmainās pēc kārtas).
Spēlē jābūt ideālai informācijai (t. i., informācija netiek slēpta, kā tas ir pokera spēlē).
Spēlei jābūt deterministiskai (t. i., bez izredzēm). Veiksme nav spēles sastāvdaļa.
Spēlei ir jābūt noteiktam iespējamu gājienu skaitam.
Galu galā spēlei ir jābeidzas.
Spēlei ir jābeidzas, kad viens no spēlētājiem vairs nevar pārvietoties.

Kombinatorisko spēļu teorija lielākoties aprobežojas ar tādu kombinatorisko spēļu apakškopas izpēti, kurās ir divi spēlētāji, kuras ir galīgas un kurās ir uzvarētājs un zaudētājs (t. i., kuras nebeidzas neizšķirti).

Šīs kombinatoriskās spēles var attēlot ar kokiem, kuru katra virsotne ir spēle, kas izriet no konkrēta gājiena no spēles, kura atrodas tieši zem tās kokā. Šīm spēlēm var piešķirt spēles vērtības. Šo spēļu vērtību atrašana ir ļoti interesanta CG teorētiķiem, tāpat kā teorētiskais jēdziens "spēļu papildinājums". Divu spēļu summa ir spēle, kurā katram spēlētājam savā gājienā jāveic gājiens tikai vienā no divām spēlēm, atstājot otru spēli tādu, kāda tā bija.

Šīs teorijas pamatlicēji ir Elvins Berlekamps, Džons Konvejs un Ričards Gajs. Viņi strādāja kopā 20. gadsimta 60. gados. Viņu publicētais darbs saucās "Uzvaras ceļi matemātiskajām spēlēm" (Winning Ways for Your Mathematical Plays).

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".