Kombinatorinen peliteoria

Kombinatorinen peliteoria, joka tunnetaan myös nimellä CGT, on soveltavan matematiikan ja teoreettisen tietojenkäsittelytieteen haara, joka tutkii kombinatorisia pelejä ja eroaa "perinteisestä" tai "taloudellisesta" peliteoriasta. CGT syntyi suhteessa puolueettomien pelien teoriaan, erityisesti kahden pelaajan Nim-peliin, ja siinä painotettiin tietyntyyppisten kombinatoristen pelien "ratkaisemista".

Pelin on täytettävä useita ehtoja ollakseen kombinatorinen peli. Nämä ovat:

Pelissä on oltava vähintään kaksi pelaajaa.
Pelin on oltava peräkkäinen (eli pelaajat vuorottelevat vuorotellen).
Pelissä on oltava täydellinen informaatio (eli mitään tietoa ei ole piilotettu, kuten pokerissa).
Pelin on oltava deterministinen (eli ei-sattumanvarainen). Onni ei kuulu peliin.
Pelissä on oltava tietty määrä mahdollisia siirtoja.
Pelin on lopulta loputtava.
Peli on lopetettava, kun yksi pelaaja ei voi enää liikkua.

Kombinatorinen peliteoria rajoittuu pitkälti sellaisten kombinatoristen pelien osajoukon tutkimiseen, jotka ovat kahden pelaajan pelejä, äärellisiä ja joilla on voittaja ja häviäjä (eli jotka eivät pääty tasapeleihin).

Nämä kombinatoriset pelit voidaan esittää puina, joiden jokainen huippu on peli, joka on seurausta tietystä siirrosta suoraan puun alapuolella olevasta pelistä. Näille peleille voidaan antaa peliarvoja. Näiden peliarvojen löytäminen kiinnostaa suuresti CG-teoreetikkoja, samoin kuin pelien yhteenlaskun teoreettinen käsite. Kahden pelin summa on peli, jossa kunkin pelaajan on vuorollaan siirryttävä vain toiseen näistä kahdesta pelistä ja jätettävä toinen peli ennalleen.

Elwyn Berlekamp, John Conway ja Richard Guy ovat teorian perustajia. He työskentelivät yhdessä 1960-luvulla. Heidän julkaisemansa teoksen nimi oli Winning Ways for Your Mathematical Plays.

Määritelmät

Teoriassa on kaksi pelaajaa, joita kutsutaan vasemmaksi ja oikeaksi. Peli on jotain, jonka avulla vasen ja oikea voivat tehdä siirtoja muihin peleihin. Esimerkiksi shakkipelissä on tavallinen alkuasetelma. Voidaan kuitenkin myös ajatella shakkipeliä ensimmäisen siirron jälkeen eri pelinä, jossa on eri asetelma. Jokaista asemaa kutsutaan siis myös peliksi.

Pelien merkintätapa on {L|R}. L {\displaystyle L} $L$ ovat pelejä, joihin vasen pelaaja voi siirtyä. R {\displaystyle R} $R$ ovat pelejä, joihin oikea pelaaja voi siirtyä. Jos tunnet shakin merkintätavan, tavallinen shakkiasetelma on peli seuraavasti

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

Pisteet "..." tarkoittavat, että siirtoja on monta, joten kaikkia ei näytetä.

Shakki on hyvin monimutkainen. On parempi miettiä helpompia pelejä. Esimerkiksi Nim on paljon yksinkertaisempi peli. Nimiä pelataan näin:

Laskuripinoja on nolla tai enemmän.
Vuorollaan pelaaja voi ottaa yhdestä pinosta niin monta pelinappulaa kuin haluaa.
Pelaaja, joka ei pysty tekemään siirtoa, häviää.

Nim-pelin helpoin peli alkaa ilman laskureita! Tällöin kumpikaan pelaaja ei voi liikkua. Tämä näkyy merkkinä {|}. Molemmat puolet ovat tyhjiä, koska kumpikaan pelaaja ei voi liikkua. Ensimmäisenä lähtevä pelaaja ei voi liikkua, joten hän häviää. CGT:ssä {|} kirjoitetaan usein symbolina 0 (nolla).

Seuraavaksi helpoimmassa pelissä on vain yksi kasa, jossa on vain yksi laskuri. Jos vasemmanpuoleinen pelaaja menee ensin, hänen on otettava laskuri, jolloin oikeanpuoleinen pelaaja ei saa tehdä siirtoja ({|} tai 0). Jos sen sijaan oikea siirtyy ensin, vasemmalla ei ole enää siirtoja. Sekä vasen että oikea voivat siis tehdä siirron 0:aan. Tämä näkyy muodossa {{|}|{|}} eli {0|0}. Pelaaja, joka siirtyy ensimmäisenä, voittaa. {0|0}:n kaltaiset pelit ovat hyvin tärkeitä. Ne merkitään symbolilla * (tähti).

Kysymyksiä ja vastauksia

K: Mitä on kombinatorinen peliteoria?

V: Kombinatorinen peliteoria (Combinatorial Game Theory, CGT) on soveltavan matematiikan ja teoreettisen tietojenkäsittelytieteen haara, joka tutkii kombinatorisia pelejä, ja se eroaa "perinteisestä" tai "taloudellisesta" peliteoriasta.

K: Mitkä ehdot pelin on täytettävä, jotta sitä voidaan pitää kombinatorisena pelinä?

V: Jotta peliä voidaan pitää kombinatorisena pelinä, siinä on oltava vähintään kaksi pelaajaa, sen on oltava peräkkäinen (eli pelaajat vuorottelevat vuorollaan), siinä on oltava täydellistä informaatiota (eli mitään tietoa ei ole piilotettu), sen on oltava deterministinen (eli se ei saa olla sattumanvarainen), tuuri ei voi olla osa peliä, siinä on oltava tietty määrä mahdollisia siirtoja, pelin on lopulta päätyttävä ja pelin on päätyttävä, kun toinen pelaaja ei voi enää siirtyä.

K: Minkä tyyppisiin peleihin yhdistelmäpeliteoria keskittyy?

V: Kombinatorinen peliteoria keskittyy pääasiassa kahden pelaajan äärellisiin peleihin, joissa on voittajat ja häviäjät (eli jotka eivät pääty tasapeleihin).

K: Miten tämäntyyppiset pelit esitetään?

V: Tämäntyyppiset pelit voidaan esittää puina, joissa kukin kärki edustaa peliä, joka on seurausta tietystä siirrosta suoraan puun alapuolella olevasta siirrosta.

K: Mitä tavoitteita CG-teoreetikoilla on?

V: CG-teoreetikoiden tavoitteisiin kuuluu muun muassa arvojen löytäminen tämäntyyppisille peleille sekä "pelin lisäämisen" käsitteen ymmärtäminen, jossa kukin pelaaja tekee vain yhden siirron kahdessa eri pelissä ja jättää toisen pelin ennalleen oman vuoronsa aikana.

K: Kuka perusti CGT:n?

V: Elwyn Berlekampin, John Conwayn ja Richard Guyn katsotaan perustaneen CGT:n 1960-luvulla julkaistussa teoksessaan Winning Ways for Your Mathematical Plays.