Kombinatorična teorija iger

Kombinatorična teorija iger, znana tudi kot CGT, je veja uporabne matematike in teoretičnega računalništva, ki preučuje kombinatorične igre in se razlikuje od "tradicionalne" ali "ekonomske" teorije iger. CGT je nastala v zvezi s teorijo nepristranskih iger, zlasti igre Nim za dva igralca, s poudarkom na "reševanju" določenih vrst kombinatoričnih iger.

Da bi bila igra kombinatorična, mora izpolnjevati več pogojev. Ti so:

V igri morata sodelovati vsaj dva igralca.
Igra mora biti zaporedna (tj. igralci se izmenično menjavajo.)
Igra mora imeti popolne informacije (tj. nobena informacija ni skrita, kot v pokru).
Igra mora biti deterministična (tj. brez naključij). Sreča ni del igre.
Igra mora imeti določeno število možnih potez.
Igra se mora na koncu končati.
Igra se mora končati, ko se eden od igralcev ne more več premikati.

Teorija kombinatoričnih iger je večinoma omejena na preučevanje podskupine kombinatoričnih iger, ki jih igrata dva igralca, so končne ter imajo zmagovalca in poraženca (tj. ne končajo se z neodločenim izidom).

Te kombinatorične igre lahko predstavimo z drevesi, katerih vsak vrh je igra, ki nastane z določeno potezo iz igre, ki je na drevesu neposredno pod njim. Tem igram se lahko pripišejo vrednosti igre. Iskanje teh vrednosti iger je zelo zanimivo za teoretike CG, prav tako kot teoretični koncept dodajanja iger. Seštevek dveh iger je igra, v kateri se mora vsak igralec na svojem poteku premakniti le v eno od obeh iger, drugo pa pusti v nespremenjeni obliki.

Elwyn Berlekamp, John Conway in Richard Guy so utemeljitelji te teorije. Sodelovali so v šestdesetih letih prejšnjega stoletja. Njihovo objavljeno delo se je imenovalo Zmagovalni načini za vaše matematične igre.

Opredelitve

V teoriji sta dva igralca, levi in desni. Igra je nekaj, kar levi in desni strani omogoča, da naredita poteze v druge igre. Na primer, v šahovski igri je običajna začetna postavitev. Lahko pa bi si šahovsko igro po prvi potezi predstavljali tudi kot drugo igro z drugačno nastavitvijo. Zato se vsaka pozicija imenuje tudi igra.

Igre so zapisane z oznako {L|R}. L {\displaystyle L} $L$ so igre, v katere se lahko premakne levi igralec. R {\displaystyle R} $R$ so igre, v katere se lahko premakne desni igralec. Če poznate šahovsko notacijo, je običajna šahovska postavitev igra

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

Pike "..." pomenijo, da je veliko potez, zato niso prikazane vse.

Šah je zelo zapleten. Bolje je razmišljati o lažjih igrah. Nim, na primer, je veliko preprostejši. Nim se igra takole:

Na voljo je nič ali več kupčkov števcev.
Na potezi lahko igralec vzame toliko žetonov z enega kupčka, kolikor jih želi.
Igralec, ki ne more izvesti poteze, izgubi.

Najlažja igra Nim se začne brez števcev! V tem primeru se noben igralec ne more premakniti. To je prikazano kot {|}. Obe strani sta prazni, ker se nobeden od igralcev ne more premakniti. Igralec, ki je prvi na vrsti, se ne more premakniti, zato izgubi. V igri CGT ljudje pogosto zapišejo {|} kot simbol 0 (nič).

Naslednja najlažja igra ima samo en kupček z enim števcem. Če gre prvi levi igralec, mora vzeti števec, desni pa ostane brez potez ({|} ali 0). Če se namesto tega prva premakne desna stran, leva stran nima več potez. Tako lahko tako levi kot desni naredita potezo do 0. To je prikazano kot {{|}|{|}} ali {0|0}. Zmaga igralec, ki se prvi premakne. Igre, enake {0|0}, so zelo pomembne. Zapisane so s simbolom * (zvezda).

Vprašanja in odgovori

V: Kaj je kombinatorična teorija iger?

O: Teorija kombinatoričnih iger (CGT) je veja uporabne matematike in teoretičnega računalništva, ki preučuje kombinatorične igre in se razlikuje od "tradicionalne" ali "ekonomske" teorije iger.

V: Katere pogoje mora izpolnjevati igra, da se šteje za kombinatorično igro?

O: Da se igra šteje za kombinatorično igro, mora imeti vsaj dva igralca, biti mora zaporedna (tj. igralci se izmenično menjavajo), imeti mora popolne informacije (tj. nobena informacija ni skrita), biti mora deterministična (tj. brez naključij), sreča ne sme biti del igre, imeti mora določeno število možnih potez, igra se mora na koncu končati in igra se mora končati, ko se eden od igralcev ne more več premakniti.

V: Na katere vrste iger se osredotoča kombinatorična teorija iger?

O: Teorija kombinatoričnih iger se osredotoča predvsem na končne igre dveh igralcev, ki imajo zmagovalce in poražence (tj. ne končajo se z remijem).

V: Kako so predstavljene te vrste iger?

O: Te vrste iger lahko predstavimo z drevesi, pri čemer vsak vrh predstavlja igro, ki nastane zaradi določene poteze neposredno pod njim na drevesu.

V: Kakšni so cilji teoretikov računalniške teorije?

O: Nekateri cilji teoretikov CG vključujejo iskanje vrednosti za te vrste iger in razumevanje koncepta "dodajanja iger", ki vključuje, da vsak igralec naredi samo eno potezo v dveh različnih igrah, pri čemer druga ostane nespremenjena v njegovem poteku.

V: Kdo je ustanovil CGT?

O: Elwyn Berlekamp, John Conway in Richard Guy so zaslužni za ustanovitev CGT v svojem objavljenem delu z naslovom Winning Ways for Your Mathematical Plays v šestdesetih letih prejšnjega stoletja.