Kombinatorinė žaidimų teorija

Kombinatorinė žaidimų teorija, dar vadinama CGT, yra taikomosios matematikos ir teorinės informatikos šaka, tirianti kombinatorinius žaidimus ir besiskirianti nuo "tradicinės" arba "ekonominės" žaidimų teorijos. CGT atsirado dėl nešališkų žaidimų teorijos, ypač dviejų žaidėjų žaidimo Nim, akcentuojant tam tikrų kombinatorinių žaidimų tipų "sprendimą".

Kad žaidimas būtų kombinatorinis, jis turi atitikti kelias sąlygas. Tai yra:

Žaidime turi būti bent du žaidėjai.
Žaidimas turi būti nuoseklus (t. y. žaidėjai keičiasi vietomis).
Žaidimas turi būti visiškai informatyvus (t. y. jokia informacija nėra paslėpta, kaip pokeryje).
Žaidimas turi būti deterministinis (t. y. neatsitiktinis). Sėkmė nėra žaidimo dalis.
Žaidime turi būti nustatytas galimų ėjimų skaičius.
Galiausiai žaidimas turi baigtis.
Žaidimas turi baigtis, kai vienas iš žaidėjų nebegali judėti.

Kombinatorinė žaidimų teorija daugiausia skirta kombinatorinių žaidimų, kuriuose dalyvauja du žaidėjai, kurie yra baigtiniai ir turi nugalėtoją bei pralaimėtoją (t. y. nesibaigia lygiosiomis), poaibiui nagrinėti.

Šiuos kombinacinius žaidimus galima pavaizduoti medžiais, kurių kiekviena viršūnė yra žaidimas, atsirandantis atlikus tam tikrą ėjimą iš žaidimo, esančio medyje tiesiai po ja. Šiems žaidimams galima priskirti žaidimo vertes. Šių žaidimų verčių paieška labai domina CG teoretikus, kaip ir teorinė žaidimų papildymo sąvoka. Dviejų žaidimų suma yra žaidimas, kuriame kiekvienas žaidėjas savo ėjimo metu turi atlikti ėjimą tik viename iš dviejų žaidimų, kitą palikdamas tokį, koks jis buvo.

Šios teorijos kūrėjai yra Elwyn Berlekamp, John Conway ir Richard Guy. Jie kartu dirbo septintajame dešimtmetyje. Jų išleistas darbas vadinosi "Laimėjimo būdai jūsų matematiniams žaidimams".

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