Hrvatski matematički elektronski časopis math.e

http://www.math.hr/~mathe/

Kombinatorne igre

Matko Botinčan

Sadržaj:

1. Uvod
2. Reprezentacija igara pomoću grafa, odnosno stabla
3. Ukratko o klasifikaciji igara
4. Formalna definicija igara
5. Operacije na igrama
6. Igre stupnja dva
7. Pojednostavljivanje igara
8. Imparcijalne igre
9. Još malo o Nimu i imparcijalnim igrama
Literatura

1. Uvod

U intrigantnom igranom filmu L’Année dernière à Marienbad (“Prošle godine u Marienbadu”) [1] osoba M nagovara osobu X da odigraju jednu jednostavnu igru. Osoba M posloži karte na stol na sljedeći način:

PIC

Igrači naizmjence uzimaju koliko žele karata iz jednog retka te se igra ponavlja sve dok jedan od igrača ne uzme posljednju kartu i time gubi igru. U navedenom filmu osoba M velikodušno prepušta osobi X da odigra prvi potez. Na žalost, osoba X će uvijek izgubiti igru, kako god igrala.

Igra koju u filmu igraju osobe M i X poznata je pod imenom Nim (dolazi od njemačke riječi nehmen) te je jedna od najstarijih i najpoznatijih matematičkih igara za dva igrača. Samo ime igre pod kojim je ona danas poznata kao i njezina precizna matematička teorija nastali su još početkom prošlog stoljeća pionirskim radom C. L. Boutona [2].

Općenito se igra, dakako, može igrati predmetima bilo koje vrste (sigurno ste barem jednom imali priliku susresti varijantu s npr. šibicama, kamenčićima, novčićima i sl.), a pravila za određivanje pobjednika znaju varirati. Naime, u standardnoj varijanti igre pobjeđuje igrač koji uzima posljednji predmet, a u tzv. mizernoj varijanti igrač koji odigra posljednji potez gubi. Igrači iz filma [1] igraju, dakle, mizernu varijantu Nima.

Neki od čitatelja sigurno već znaju zašto osoba X u opisanoj situaciji gubi igru. Naime, Nim je primjer igre koja ima svojstvo da sa svake njezine pozicije uvijek točno jedan igrač ima pobjedničku strategiju (za takve igre kažemo da su determinirane), a pripadna je strategija praktički jednostavno provedljiva. Pogledajmo ukratko o čemu je riječ (pretpostavivši pri tome da igramo standardnu varijantu Nima). Uvedimo pojam korektne pozicije u igri na sljedeći način. Izrazimo broj predmeta na svakoj hrpi u binarnom sustavu te dobivene brojeve potpišimo jedan ispod drugoga (kao kad npr. zbrajamo brojeve na papiru). Reći ćemo da je dana pozicija Nima korektna ako je zbroj brojeva u svakom od stupaca paran. U protivnom govorimo o inkorektnoj poziciji. Indukcijom nije teško pokazati da tada vrijedi:

Teorem 1: S dane pozicije u Nimu igru dobiva drugi igrač (onaj koji drugi vuče potez) ako i samo ako je pozicija korektna.

Zadatak 1: Provedite induktivni dokaz ove tvrdnje.
Uputa: Uočite kako svaki potez odigran s korektne pozicije nužno rezultira inkorektnom pozicijom, a sa svake inkorektne pozicije moguće je odigrati potez na korektnu poziciju.

Odatle zaključujemo:

Zadatak 2: I za mizernu varijantu Nima postoji slična karakterizacija koja određuje s kojih pozicija pobjeđuje prvi, a s kojih drugi igrač. Pronađite tu karakterizaciju te odredite kako u tom slučaju izgledaju pobjedničke strategije za igrače.

Opisana karakterizacija u potpunosti rješava pitanje pobjednika u igri Nim te pobjedničkom igraču nalaže kako treba optimalno igrati da bi dobio igru. Pitanja o nalaženju pobjednika i pobjedničkih strategija prirodno se nameću praktički kod svih tipova igara, no također je interesantno zapitati se u kojim bismo sve igrama mogli upotrijebiti pobjedničku strategiju analognu onoj iz igre Nim. Osnovni cilj ovog teksta jest prezentirati jedan od temeljnih odgovora na ovo drugo pitanje. Također, namjera nam je pri tome upoznati čitatelja i s osnovnim konceptima koji figuriraju u kombinatornoj teoriji igara te posebno mlađim čitateljima dočarati na koji način u ovom konkretnom slučaju snaga i elegancija matematičke apstrakcije dolaze do izražaja.

2. Reprezentacija igara pomoću grafa, odnosno stabla

Način na koji se odvija igra često je korisno prikazati pomoću usmjerenog grafa, u kojem njegovi vrhovi predstavljaju moguće pozicije u igri, a bridovi moguće opcije svakog od igrača. Primjerice, igra Nim s jednom hrpom od jednog i još jednom hrpom od triju predmeta reprezentirana usmjerenim grafom izgledala bi ovako:

PIC

Igrači naizmjence vuku poteze odabirući jedan od bridova koji im je dostupan u pojedinom vrhu grafa. Igra završava u trenutku kada se stigne do terminalne pozicije u kojoj igrač koji je na potezu nema više što odigrati. U slučaju igre Nim to je pozicija u kojoj nijedna hrpa više ne sadrži predmet(e). Ishod igre u takvom slučaju ovisi o pravilima igre — vidjeli smo da je kod Nima moguće da takva pozicija bude bilo pobjednička, bilo gubitnička, ovisno o tome igramo li normalnu ili mizernu varijantu igre. Ipak, u općenitom slučaju normalna i mizerna varijanta igre nisu simetrične (mizerne varijante daleko je teže analizirati) pa ćemo se u ovom tekstu opredijeliti za normalnu varijantu igara u kojima je pobjednik onaj igrač koji je napravio posljednji potez. Dakle, igru gubi igrač koji u nekom trenutku ostane bez poteza, tj. nađe se na terminalnoj poziciji u pripadnom grafu igre.

Primijetimo: da bismo uopće mogli primijeniti opisani kriterij određivanja pobjednika u igri, moramo biti sigurni da igra završava nakon konačnog broja koraka, tj. da nijednim izborom poteza ne može nastati beskonačni niz pozicija (uočite kako će to biti slučaj ako u pripadnom grafu igre ne postoji beskonačno dugački put). Tipične matematičke igre poput Nima imaju to svojstvo, no to ne mora uvijek biti tako — uzmite za primjer igru šah (prisjetite se na koji se način u šahu rješavaju takve situacije u igri; naime, nijedna stvarna partija šaha ipak ne traje beskonačno dugo). Tretiranje beskonačnih tijekova igre općenito nije jednostavno i takvim se igrama nećemo baviti u ovom tekstu.

Često je zgodno prikazati sve moguće tijekove igre (sve različite puteve u reprezentaciji igre usmjerenim grafom) pomoću stabla. Kako bi to izgledalo za prethodni primjer igre Nim s hrpama od jednog i triju predmeta, možete vidjeti na idućoj slici:

PIC

Uočite kako u svakoj poziciji igre Nim lijevom i desnom igraču stoji na raspolaganju jednak skup opcija (kažemo da je Nim imparcijalna igra). To ne mora uvijek biti slučaj pa općenito moramo zasebno promatrati opcije lijevog, odnosno desnog igrača.

Na kraju ove točke istaknimo još jednom ključne pojmove koji će nam biti važni u daljnjem tekstu:

3. Ukratko o klasifikaciji igara

Čitatelji hrvatskog matematičkog elektronskog časopisa math.e sigurno se sjećaju članka Vedrana Krčadinca iz trećeg broja časopisa, koji je govorio o teoriji igara i matematičkom modeliranju konfliktnih situacija [3]. Igra Nim, kao i one koje ćemo razmatrati dalje u ovom tekstu, drugačije su od igara opisanih u navedenom članku. Kako bismo raščistili eventualno moguću zabunu o korištenoj terminologiji, napravit ćemo kratku digresiju o općenitoj klasifikaciji igara u teoriji igara.

Teorija igara velika je znanstvena disciplina koja svoje korijene vuče ponajviše iz matematike i ekonomije. U najširem smislu podijeljena je u dvije grane:

Igre kojima ćemo se baviti u ovom tekstu spadaju, dakako, u nekooperativnu teoriju igara. Iako one, zbog svoje nekooperativnosti, predstavljaju već znatnu simplifikaciju realnih situacija, vidjet ćemo da su još uvijek sve prije negoli jednostavne. Općenito, igre takvog tipa ne završavaju nužno samo pobjedom ili porazom, već uključuju niz mogućih ishoda zajedno s pripadnim preferencijama svakog od igrača. Pri tome očekivani dobitak u igri utječe na ponašanje igrača. Osnovni cilj jest predvidjeti racionalno ponašanje igrača u raznim konfliktnim situacijama te objasniti pod kojim uvjetima dolazi do “stabiliziranja”.

Da bismo jasnije odredili kakvi nas to točno tipovi nekooperativnih igara zanimaju, moramo napraviti određenu distinkciju među njima. Uzmimo kao primjer igru Nim i neku tipičnu kartašku igru, npr. Briškulu. Ako malo razmislimo, uočit ćemo da postoje dvije ključne razlike između igara poput Nima i igara poput Briškule:

  1. U igri Nim, trenutno stanje igre uvijek je vidljivo obojici igrača; kažemo da igrači imaju potpunu informaciju. Jedina nepoznanica u igri su potezi koji će biti odigrani u budućnosti. U Briškuli, s druge strane, igrači imaju nepotpunu informaciju, odnosno imaju samo parcijalni uvid u stanje igre (svaki igrač vidi samo svoje karte).
  2. Nim je igra bez elemenata slučajnosti (svi elementi igre deterministički su određeni), a kod Briškule to nije tako (ne znamo unaprijed koje ćemo karte dobiti prilikom dijeljenja). Za Briškulu kažemo da je igra s elementima slučajnosti.

Uočimo kako u igrama nepotpune informacije postoji neizvjesnost o trenutnom stanju igre (odnosno, o sadašnjosti). S druge pak strane, igre s elementima slučajnosti uključuju samo neizvjesnost o budućnosti (pri tome neizvjesnost budućeg poteza nestaje čim taj potez bude odigran).

Dakle, sve skupa zaključujemo kako nekooperativne igre ima smisla podijeliti na one potpune, odnosno nepotpune informacije, te na one sa, odnosno bez elemenata slučajnosti. Na taj je način svaku nekooperativnu igru moguće svrstati u jednu od četiriju dobivenih skupina. Klasifikacija nekolicine popularnih igara prikazana je u sljedećoj tablici:

igre potpune informacije igre nepotpune informacije
bez elemenata slučajnosti Nim, Šah, Go Potapanje brodova
s elementima slučajnosti Monopoly, “Čovječe ne ljuti se” Briškula, Bela, Poker

Teorija igara u ekonomiji fokusirana je na donošenje odluka pod utjecajem neizvjesnosti, dakle, bilo na igre nepotpune informacije, bilo na one s elementima slučajnosti. Kada se u užem smislu govori o teoriji igara, misli se upravo na takve igre. Sada je sigurno već jasno da nam je Vedran Krčadinac u članku [3] pisao upravo o takvim tipovima igara.

S druge strane, mi se u ovom tekstu bavimo igrama koje se nalaze u onoj “preostaloj” kategoriji, tj. (ne-kooperativnim) igrama potpune informacije bez elemenata slučajnosti. Takve su igre prvenstveno od matematičkog interesa (makar to ne znači da nemaju primjenu i u drugim područjima; sjetite se, primjerice, uvodnog dijela ovog teksta), a kako tipično imaju dodirnih točaka s kombinatorikom i teorijom grafova, teorija koja se oko njih razvila naziva se kombinatornom teorijom igara. Ovime smo također dali i svojevrsno opravdanje zašto smo u naslovu upotrijebili termin kombinatorne igre.

4. Formalna definicija igara

Igre potpune informacije bez elemenata slučajnosti, koje krećemo analizirati igraju samo dva igrača. Radi jednostavnosti igrače kratko nazivamo lijevim (L), odnosno desnim (D) (namjerno ne koristimo nazive “prvi”, odnosno “drugi” igrač, kako ne bi došlo do zabune kad budemo govorili o igraču koji je prvi, odnosno drugi na potezu). Dakle, budući da za svaku poziciju u igri pravila igre jednoznačno određuju dva skupa opcija koje su dostupne pojedinom igraču, igru možemo (naizgled možda jako jednostavno) definirati kao uređeni par skupova igara. Ako igru označimo s G, tada definicija kaže da je

{{ } { }} G = GL1, GL2,... | GD1,GD2, ... ,

pri čemu su { L1 L2 } G ,G ,..., odnosno { D1 D2 } G ,G ,..., skupovi opcija lijevog, odnosno desnog igrača. Bazu ove induktivne definicije predstavlja igra u kojoj nijedan od igrača nema što odigrati, tj. igra oblika:

{Ø |Ø}= { |}.

Ovakvu igru kratko ćemo označivati s 0 (nula). Također, igru G obično ćemo kompaktnije zapisivati kao G = { L D} G |G, pri čemu onda GL, odnosno GD, predstavljaju skupove opcija igrača L, odnosno D.

Napomenimo i to da igru { |} nismo slučajno označili s 0. Od ovog trenutka nadalje pojedine igre svjesno ćemo označivati simbolima za brojeve jer ćemo takvim igrama moći manipulirati na način sličan onom kojim manipuliramo brojevima u standardnoj aritmetici. Da bismo tu ideju razjasnili i preciznije opisali, promotrimo prethodno nekoliko jednostavnih primjera.

Svakoj igri korisno je dodijeliti stupanj koji opisuje njezinu jednostavnost. Nakon svakog odigranog poteza igra postaje jednostavnija u smislu da stižemo u poziciju igre manjeg stupnja. Najjednostavnija igra (i jedina stupnja 0) jest igra {| } s praznim skupom opcija za lijevog i desnog igrača. U idućem koraku kao opcije imamo na raspolaganju Ø i 0 = {| } pa tako igara stupnja 1 ima ukupno četiri (= 2 . 2) i to su: 0, 1 = {0 |}, -1 = {|0}, te * = {0 |0}. Pripadajuća stabla ovih igara prikazana su na sljedećoj slici (pri tome opcije igrača L bojimo plavom bojom, a opcije igrača D crvenom):

PIC PICPICPIC
0 = {|} 1 = {0 |} -1 = {|0} * = {0 |0}

Prikazane igre predstavljaju prototipove igara s obzirom na koje ćemo klasificirati sve složenije igre. One imaju sljedeća ključna svojstva:

Dakle, svaku igru možemo prema ishodu svrstati u jednu od navedenih četiriju klasa, kako je to sistematizirano sljedećom tablicom:

počinje D i
Ako u igri G
L ima pobjedničku D ima pobjedničku
strategiju strategiju
počinje L i
D ima pobjedničku G = 0 G < 0
strategiju (drugi pobjeđuje) (D pobjeđuje)
L ima pobjedničku G > 0 G || 0
strategiju (L pobjeđuje) (prvi pobjeđuje)

Uočimo i to kako relacija G = 0 u ovoj tablici ne govori da je sama igra G jednaka igri 0 (nula), već da je riječ o igri kojoj je vrijednost jednaka 0, tj. da igra G pripada klasi igara u kojoj drugi igrač ima pobjedničku strategiju. Isto tako, relacija G || 0 označuje da je igra G neusporediva s igrom 0, tj. da je riječ o igri u kojoj pobjedničku strategiju ima prvi igrač.

5. Operacije na igrama

Zamislite da ste u situaciji u kojoj igrate vašu omiljenu igru protiv izvrsnog protivnika, kojeg nikako ne uspijevate pobijediti. Sigurno biste u takvoj situaciji voljeli imati mogućnost da, nakon što jednom ustanovite kako je vaša šansa za pobjedu u igri postala gotovo zanemariva, prepustite svoje mjesto vašem protivniku, a vi preuzmete njegovu ulogu. Iako ovakav tip operacije nije baš uobičajen u igrama iz svakodnevnog života, on je ipak poželjan i koristan u matematičkim igrama. Operacija koja igru G zamjenjuje njoj suprotnom igrom -G definirana je induktivno ovako:

{ D L} - G = -G |-G .

Sjetite se pri tome da primjerice -GD zapravo označuje skup opcija {-GD1, -GD2,...}, gdje svaka pojedina opcija predstavlja igru jednostavniju od -G.

Nadalje, na igrama možemo definirati i operaciju sume. Naprimjer, svaka igra Nim suma je određenog broja igara Nim s jednom hrpom. U danoj sumi igrač koji je na potezu bira jednu od komponenata sume te u njoj odigrava jedan od mogućih poteza. Stoga definicija sume igara G i H izgleda ovako:

G + H = {GL + H, G+ HL |GD + H, G+ HD} .

Ovo opet predstavlja induktivnu definiciju: GL + H, primjerice, predstavlja skup opcija { } GL1 + H, GL2 + H, ..., svaka od kojih je igra jednostavnija od G + H.

Nije teško provjeriti da na ovaj način definirana suma ima svojstvo komutativnosti (G + H = H + G) i asocijativnosti (F + (G + H) = (F + G) + H) te da vrijedi G + 0 = G i G + (-G) = 0 (drugim riječima, igre sa sumom kao binarnom operacijom uvjetno rečeno čine grupu). Pri tome treba biti malo oprezan s čitanjem posljednjih dviju relacija jer je simbol 0 u njima upotrijebljen u dva bitno različita smisla. U relaciji G + 0 = G simbol 0 predstavlja igru nula, odnosno {|}. S druge strane, relacija G + (-G) = 0 govori da je igra G + (-G) igra vrijednosti 0, odnosno da pripada klasi igara u kojoj drugi igrač ima pobjedničku strategiju.

Zadatak 3: Provjerite da vrijede sljedeće jednakosti:

  1. 1 + (-1) = 0 (u igri 1 + (-1) pobjeđuje drugi igrač);
  2. * + * = 0 ( u igri * + * pobjeđuje drugi igrač).

Sada možemo definirati relaciju ekvivalencije na igrama na način da za igre G i H kažemo da su ekvivalentne, u oznaci G = H, ako u igri G + (-H) pobjeđuje drugi igrač, odnosno vrijedi G + (-H) = 0. Štoviše, na igrama možemo definirati i parcijalni uređaj >, pri čemu G > H označuje da je G + (-H) > 0, tj. u igri G + (-H) uvijek pobjeđuje igrač L, neovisno o tome koji igrač započinje igru.

Zadatak 4: Pokušajte dokazati sljedeće tvrdnje:

  1. Ako je G ≥ 0 i H ≥ 0, tada je i G + H ≥ 0. (Napomena: G ≥ 0 označuje G = 0 ili G > 0)
  2. Ako je H = 0, tada igra G + H ima isti ishod kao i igra G.

6. Igre stupnja dva

Vidjeli smo da igara stupnja jedan imamo ukupno četiri pa iz njih dobivamo ukupno 24 = 16 mogućih opcija za svakog od igrača L i D, što sve skupa daje 256 igara stupnja dva. Ipak, efektivni broj različitih igara stupnja dva možemo bitno reducirati ako uočimo da neke opcije igrači očito preferiraju u odnosu na druge. Naime, četiri igre stupnja jedan nalaze se u odnosu koji možemo ilustrirati ovakvim dijagramom:

PIC

Na dijagramu preferencije igrača L rastu prema gore, a preferencije igrača D rastu prema dolje. Primjerice, u skupu opcija {0,-1} igrač L očito će preferirati 0, a u skupu {1,*,- 1} igrač D preferirat će opciju -1. Jedini skup opcija u kojem nije a priori jasno što bi bila najbolja opcija za pojedinog igrača jest skup {0,*}. Stoga je za opcije igrača u igrama stupnja dva potrebno uzeti u obzir jedino sljedeće skupove: Ø, -1, *, 0, {0,*} i 1. Između 62 = 36 rezultantnih igara stupnja dva samo su 22 međusobno neekvivalentne (pri tome su četiri od njih ekvivalentne već poznatim igrama stupnja jedan). Pripadna stabla tih igara prikazuje sljedeća slika.

PIC PIC PIC PIC PIC
0 1 -1 2 -2
     
PIC PIC PIC PICPIC
* 12 -12 {1 |0} {0|- 1}
     
PIC PIC PICPICPIC
|^ |, {1 |-1} = ±1 1* -1*
     
PICPIC PIC PIC
{1|*} {* |-1} |^ * |, *
     
PICPICPIC
{0,*|- 1} {1 |0,*} *2

Kao što smo vidjeli u uvodnom dijelu ovog teksta na primjeru igre Nim, svaku igru možemo prikazati bilo kao stablo, bilo kompaktnije u obliku usmjerenog grafa. Stabla prvih 5 igara s prethodne slike predstavljaju istovremeno i njihove grafove pa stoga na sljedećoj slici dajemo ilustraciju grafova za preostalih 17 igara. Opcije igrača L, odnosno D, i dalje su obojene plavo, odnosno crveno, dok su zajedničke opcije obaju igrača obojene zelenom bojom.

PIC PIC PIC PICPIC
* 1 2 -1 2 {1 |0} {0 |-1}
     
PIC PIC PIC PIC PIC
|^ |, ±1 1* -1*
     
PICPIC PIC PIC
{1|*} {*|- 1} |^ * |, *
     
PICPICPIC
{0,*|- 1} {1|0,*} *2

Među dane 22 igre imamo jednu igru vrijednosti nula, šest negativnih, šest pozitivnih, te devet neizrazitih igara. Vrijednosti ishoda svih igara sistematizirane su u sljedećoj tablici. Pri tome igra vrijednosti nula nalazi se u gornjem lijevom, negativne igre u gornjem desnom, pozitivne u donjem lijevom, a neizrazite u donjem desnom kvadrantu.

Ø 1 * 0 {0,*} -1
Ø
-1
 -2
-1
0
-1 2
 -1*
*
|,
{* |-1}
0
1
1 2
|^
* |, * {0 |-1}
{0,*} |^ * *2 {0,* |-1}
1 21*{1|*}{1 |0}{1|0,*} ±1

Zadatak 5: Dokažite da vrijede sljedeće tvrdnje:

  1. 1 + 1 = 2;
  2. 1 2 + 1 2 = 1;
  3. |^ = {0 |*} = {0,* |*} ≥ 0;
  4. |^ * = {0,* |0} = |^ + *;
  5. 0 ||* 2 = {0,* |0,*};
  6. 1* = {1|1} = 1 + *;
  7. {1 |0} > *;
  8. |, * = {0 |0,*} || 0;
  9. {1 |0} > |^ *, {1|0} > *2, {1|0} > |, = *| 0, {1| 0} > |, *, {1 |0} > ±1 = {1 |-1}, {1|0} || 0, {1|0} || |^ ;
  10. {1 |*} > 0, {1|*} > |^ , {1|*} || |^ *;
  11. {1 |0,*} > |, , {1 |0,*} || |^ .

7. Pojednostavljivanje igara

Prisjetimo se da smo prilikom nalaženja svih međusobno neekvivalentnih igara stupnja dva zbog očitih preferencija pojedinih opcija naspram drugih smjeli izbaciti one manje “poželjne” opcije pojedinog igrača. Općenito, ako u igri G = { } GL1,GL2,GL3,...|GD1, GD2,GD3,... vrijedi GL2 ≥ GL1, kažemo da GL2 dominira GL1 te u tom slučaju smijemo izbaciti opciju GL1 (pod uvjetom da GL2 bude zadržana). Kod desnog igrača situacija je suprotna — kažemo da GD2 dominira GD1 ako vrijedi GD2 ≤ GD1 te opet smijemo izbaciti opciju GD1 (ako zadržimo GD2). Brisanje dominiranih opcija jedan je način za pojednostavljivanje igara.

Drugi, nešto suptilniji način, sastoji se od zamjene tzv. reverzibilnih opcija. Opciju desnog igrača X nazivamo reverzibilnom ako lijevi igrač ima odgovor XL, koji je za njega barem jednako toliko dobar koliko i dana igra G, tj. ako vrijedi XL ≥ G. U tom slučaju X smijemo zamijeniti nizom svih desnih opcija XLD = { } XLD1,XLD2, ... od XL. Slično, opcija lijevog igrača Y je reverzibilna ako desni igrač ima odgovor YD, koji je za njega barem jednako toliko dobar koliko i sama igra G, tj. ako je YD ≤ G te tada Y smije biti zamijenjen nizom svih lijevih opcija YDL od YD.

Primjerice, u igri G = {0,*|*} nijedna opcija lijevog igrača ne dominira nad onom drugom budući da je 0 ||*, ali je zato njegova opcija * reverzibilna, budući da je pripadni odgovor desnog igrača *R = 0, a za igru G vrijedi G ≥ 0 (uvjerite se da je to doista tako!). To znači da opciju lijevog igrača * možemo zamijeniti svim opcijama lijevog igrača od *R = 0 = { |}, tj. možemo je zamijeniti svim opcijama praznog skupa, dakle, možemo je obrisati. Na taj se način polazna igra G pojednostavljuje u igru {0 |*} = |^ .

Zadatak 6: Analizirajte reverzibilne opcije u igri { |^ | | ^ }, te je pojednostavite.

8. Imparcijalne igre

Imparcijalnom igrom nazivamo onu igru kod koje je skup opcija lijevog igrača jednak skupu opcija desnog igrača. Imparcijalne igre koje smo susreli u prethodnim točkama bile su { |} = *0 = 0, {0|0} = *1 = *, te {0,*|0,*} = *2. Ovu konstrukciju nije teško generalizirati pa na taj način kao igru stupnja n dobivamo igru sljedećeg oblika:

*n = {*0,*1,*2,...,*(n- 1)|*0,*1,*2,...,*(n- 1)}.

Ovakve igre, budući da su od posebne važnosti, imaju i posebno ime — nazivaju se nimberima. Ime potječe, naravno, od igre Nim — svaki nimber *n odgovara igri Nim koja se sastoji od jedne hrpe s n objekata. S obzirom da su u nimberima opcije lijevog i desnog igrača jednake, dovoljno je pisati samo jedan skup opcija pa ćemo u daljnjem tekstu nimber *n pisati kao *n = {0,*,*2,...,*(n -1)}.

Zadatak 7: Zapišite pomoću nimbera općenitu igru Nim kod koje se u prvoj hrpi nalazi n1 predmeta, u drugoj hrpi n2 predmeta ..., te u k-toj hrpi nk predmeta.

Nadalje, uloga nimbera postaje još važnija ako uvidimo da vrijedi sljedeća tvrdnja: svaka igra oblika

{*a,*b,*c,...|*a,*b,*c,...}

ekvivalentna je igri *m, gdje je m najmanji nenegativan cijeli broj koji se ne nalazi u skupu {a,b,c,...}. Da bismo to uvidjeli, potrebno je samo uočiti kako je svaka opcija *n za n > m reverzibilna — naime, opcija *m od *n ima svojstvo da je ≥ *m — pa stoga *n možemo zamijeniti opcijama od *m, odnosno s 0, *, *2, ..., *(m - 1).

Dana argumentacija zapravo predstavlja induktivni korak dokaza činjenice da je svaka imparcijalna igra ekvivalentna nekom nimberu. Ova tvrdnja, koju su po prvi puta dokazali Sprague (1935.-36.) i Grundy (1939.), jedna je od prvih i temeljnih rezultata kombinatorne teorije igara.

Teorem 2 (Sprague-Grundy): Za svaku imparcijalnu igru G postoji m takav da vrijedi G = *m.

Zadatak 8: Napravite za vježbu kompletni induktivni dokaz Sprague-Grundyjevog teorema (bazu, pretpostavku, te korak indukcije).

9. Još malo o Nimu i imparcijalnim igrama

Postavlja se još pitanje kako odrediti pobjednika u danoj imparcijalnoj igri. Zbog Sprague-Grundyjevog teorema to je sada moguće (barem u teoriji) jer znamo odrediti pobjednika u svakoj instanci igre Nim. Ipak, igra je tipično predstavljena u obliku sume nimbera, pa bi bilo korisno znati kako se nimberi mogu efektivno sumirati.

Znamo da vrijedi *n + 0 = *n, a nije teško pokazati da vrijedi i *n + *n = 0 (naime, opcije lijevog i desnog igrača su jednake). Krenimo izračunati koliko je *2 + *:

*2 + *= {0,*}+ {0}= {0+ *,*+ *,*2+ 0}= {*,0,*2}= *3.

Ako sada svakoj strani jednakosti dodamo *, odnosno *2, dobivamo da vrijedi *2 = *3 + *, odnosno * = *3 + *2. Na isti način induktivno dobivamo da vrijedi:

*a+ *b = {0,*,*2,...,*(a- 1)}+ {0,*,*2,...,*(b- 1)} = {0+ *b,*+ *b,...,*(a- 1)+ *b,*a+ 0,*a+ *,...,*a + *(b - 1)}.

Pomoću ove jednakosti sada možemo izgraditi tablicu zbrajanja nimbera koja bi za prvih 16 nimbera izgledala ovako (elementima u tablici su radi lakše čitljivosti ispuštene zvjezdice, tj. elementi predstavljaju tzv. nim-vrijednosti nimbera):

0 1 2 3 4 5 6 7 8 9 101112131415
0 0 1 2 3 4 5 6 7 8 9 101112131415
1 1 0 3 2 5 4 7 6 9 8 111013121514
2 2 3 0 1 6 7 4 5 1011 8 9 14151213
3 3 2 1 0 7 6 5 4 1110 9 8 15141312
4 4 5 6 7 0 1 2 3 12131415 8 9 1011
5 5 4 7 6 1 0 3 2 13121514 9 8 1110
6 6 7 4 5 2 3 0 1 141512131011 8 9
7 7 6 5 4 3 2 1 0 151413121110 9 8
8 8 9 101112131415 0 1 2 3 4 5 6 7
9 9 8 111013121514 1 0 3 2 5 4 7 6
101011 8 9 14151213 2 3 0 1 6 7 4 5
111110 9 8 15141312 3 2 1 0 7 6 5 4
1212131415 8 9 1011 4 5 6 7 0 1 2 3
1313121514 9 8 1110 5 4 7 6 1 0 3 2
14141512131011 8 9 6 7 4 5 2 3 0 1
15151413121110 9 8 7 6 5 4 3 2 1 0

Opcije pojedinog elementa u tablici čine sve ranije vrijednosti u istom retku i istom stupcu. Uočimo kako je svaki element tablice najmanji nenegativan cijeli broj koji se ne pojavljuje ranije u istom retku ili stupcu. Primjerice, *5 + *6 = *3 jer je 3 prvi broj koji se ne nalazi u skupu {5,4,7,6,1,0,6,7,4,5,2}, odnosno među prvih šest zapisa u petom retku i prvih pet zapisa u šestom stupcu tablice.

Ako malo bolje promotrimo relaciju *5 + *6 = *3, uvidjet ćemo da je nim-vrijednost 3 dobivena zbrajanjem bez prijenosa u bazi 2, odnosno logičkom operacijom eksluzivno ili (XOR) nim-vrijednosti 5 i 6. Ako tu operaciju nazovemo nim-sumiranjem, dobivamo:

Korolar 1: Nim-vrijednost sume dviju imparcijalnih igrara je nim-suma njihovih nim-vrijednosti.

Sada, dakle, imamo efektivan način za određivanje vrijednosti imparcijalnih igara.

Na kraju, zaključimo što možemo reći o ishodima u imparcijalnim igrama.

Korolar 2: Svaka pozicija u imparcijalnoj igri je:

Ovakva karakterizacija, iskazana doduše nešto drugačijim riječima, bila je navedena za igru Nim još na samom početku ovog teksta. No, sada vidimo kako ista karakterizacija vrijedi i u znatno općenitijem kontekstu — sve imparcijalne igre imaju takvo svojstvo. To nam zapravo govori kako igra Nim upravo predstavlja prototip svih imparcijalnih igara pa je stoga njezina matematička, a i ona nematematička popularnost doista i teorijski opravdana. Ne znamo da li je te činjenice bio svjestan Alain Resnais, redatelj filma [1], no, očito, opredijelivši se u svom filmu za igru Nim, nije pogriješio.

Literatura

[1]   A. Resnais. L’Année dernière à Marienbad. http://www.imdb.com/title/tt0054632/

[2]   C. L. Bouton. Nim, a game with a complete mathematical theory. Annals of Mathematics 3 (1901-02), 35–39.

[3]   V. Krčadinac. Teorija igara - matematičko modeliranje konfliktnih situacija. Math.e 3. http://www.math.hr/~mathe/teorijaigara/index.html

[4]   E. R. Berlekamp, J. H. Conway and R. Guy. Winning ways for your Mathematical Plays. Academic Press, 1982.

[5]   J. H. Conway. On Numbers and Games. Academic Press, 1976.

[6]   R. Guy. Combinatorial Games. In Handbook of Combinatorics, R. Graham, M. Grotschel and L. Lovasz (Eds.), Vol. II, North-Holland, Amsterdam, 1996, 2117–2162.

1. Uvod
2. Reprezentacija igara pomoću grafa, odnosno stabla
3. Ukratko o klasifikaciji igara
4. Formalna definicija igara
5. Operacije na igrama
6. Igre stupnja dva
7. Pojednostavljivanje igara
8. Imparcijalne igre
9. Još malo o Nimu i imparcijalnim igrama
Literatura