| Dvije igre i njihova generalizacija |  |  |
|
Sadržaj: 1. Igra NimIgra Nim opisana je na početku članka Kombinatorne igre Matka Botinčana, objavljenog u šestom broju math.e [MB]. Ponovimo ukratko osnovno o toj igri.
Na stolu se nalazi 16 šibica poslaganih u četiri reda. U prvom redu je jedna šibica, u drugom su tri šibice, u trećem pet, a u četvrtom sedam. Igrači naizmjence biraju redak i uzimaju iz njega jednu ili više od preostalih šibica. Pobjednik je igrač koji uzme zadnju šibicu. Nekoliko varijanti igre Nim možete igrati online na sljedećim adresama:
Zanimljivo je da u varijanti igre koju smo opisali igrač koji je prvi na potezu gubi ako drugi igrač ne napravi pogrešku, tj. drugi igrač ima pobjedničku strategiju. Ilustrirajmo to situacijom u kojoj su ostala dva retka s po dvije šibice u svakom.
Ako prvi igrač uzme dvije šibice iz prvog ili drugog retka, drugi će moći uzeti obje preostale šibice, dakle i zadnju. Ako pak prvi igrač uzme samo jednu šibicu, drugi će uzeti jednu iz retka s dvije šibice i dovesti igru u položaj s po jednom šibicom u dva retka. Prvi igrač uzima jednu od njih, a zadnja ponovno pripada drugom igraču. Kažemo da je stanje igre s dva retka od po dvije šibice P-pozicija, jer prethodni igrač (eng. previous player) može pobijediti, bez obzira kako igra njegov protivnik. Stanja igre koja nemaju to svojstvo nazivamo N-pozicijama, jer sljedeći igrač (eng. next player) može jednim potezom dovesti igru u P-poziciju i tako pobijediti. P-pozicije zovemo još i sigurnim, pobjedničkim ili korektnim, a N-pozicije nesigurnim, gubitničkim ili inkorektnim. Vidimo da igra Nim ne može završiti neodlučeno, tj. svako stanje igre je P-pozicija ili N-pozicija. To svojstvo imaju i sve ostale igre kojima ćemo se baviti u ovom članku. Možemo zaključiti da se pobjednička strategija sastoji u tome da se N-pozicija koja nam je ostavljena promijeni u P-poziciju. Pobjednička pozicija postaje gubitničkom bilo kojim potezom, dok gubitnička pozicija postaje pobjedničkom ispravnim potezom (koji ne mora biti jedinstven). Evo još nekoliko P-pozicija igre Nim.
Da bismo pobjeđivali u igri Nim, trebamo znati prepoznati P-pozicije. U članku [MB] opisana je jednostavna karakterizacija P-pozicija koja je stara više od 100 godina i potječe od C.L. Boutona [CB]. Broj šibica u svakom retku zapišimo u binarnom sustavu i poravnajmo znamenke na desno:
Pobjedničke pozicije prepoznajemo po tome što u stupcima imaju paran broj jedinica. U Matkovom članku [MB] proučava se široka klasa igara u kojima postoji slična karakterizacija P-pozicija, tzv. imparcijalne (nepristrane) igre. Varijanta igre Nim koju smo opisali naziva se standardnom jer pobjeđuje igrač koji odigra zadnji potez. Ako se igra po pravilu da je zadnji potez gubitnički, govorimo o misère varijanti igre. Možemo li u tom slučaju jednostavno karakterizirati pobjedničke pozicije? Ovo je Boutonov opis pobjedničke strategije za misère Nim. Igramo kao što bismo igrali standardnu varijantu Nima, sve dok postoje barem dva retka s više od jedne šibice. Kada naš protivnik odigra tako da ostane samo jedan takav redak, smanjimo ga na jednu ili nijednu šibicu ovisno o tome koja od te dvije mogućnosti ostavlja neparan broj redaka s jednom šibicom. Tada će zadnju šibicu uzeti naš protivnik. Bitno je primijetiti da uvijek možemo zadati P-poziciju standardnog Nima u kojoj dva ili više retka sadrže više od jedne šibice. Naš će protivnik prvi morati smanjiti broj takvih redaka na jedan. U idućem poglavlju promatramo igru sličnu misère Nimu za koju nije poznat jednostavan opis pobjedničke strategije. 2. Igra ChompIgru Chomp izmislio je David Gale [DG], a ime joj je dao Martin Gardner [MG]. Igra se na pravokutnoj ploči čokolade podijeljenoj na kvadratiće, dimenzija m × n. Igrači naizmjence biraju jedan kvadratić čokolade te pojedu izabrani kvadratić i sve kvadratiće koji se nalaze iznad ili desno od njega. Kvadratić na donjem lijevom rubu ploče je otrovan - igrač koji ga pojede je izgubio.  Chomp možete igrati online na sljedećim adresama:
Vidimo da je Chomp misère igra, tj. zadnji potez je gubitnički. Kad bismo igrali tako da pobjeđuje igrač koji pojede donji lijevi kvadratić čokolade, igra bi bila sasvim nezanimljiva jer se to može napraviti odmah u prvom potezu. U misère varijanti prvi igrač također može pobijediti ako igra ispravno. Teorem. U igri Chomp prvi igrač ima pobjedničku strategiju. Dokaz. Prvi igrač može pojesti kvadratić čokolade u gornjem desnom kutu ploče. Ako tako dolazi u P-poziciju, onda do kraja igre može zadavati P-pozicije i pobijediti drugog igrača. Ako je pak ploča bez gornjeg desnog kuta N-pozicija, drugi igrač je u jednom potezu može dovesti do P-pozicije. No onda je prvi igrač mogao odmah odigrati taj isti potez, jer bilo koji potez na samom početku igre sigurno eliminira gornji desni kut ploče. ■ Nažalost, iz dokaza teorema ne možemo zaključiti što je pobjednička strategija prvog igrača, nego samo da ona postoji. Ne možemo čak ni zaključiti koji potez treba odigrati na početku - možda treba izabrati gornji desni kut ploče, a možda i ne. Do danas nije otkrivena jednostavna karakterizacija P-pozicija u igri Chomp. Ipak, u nekim specijalnim slučajevima poznato je kako treba igrati prvi igrač da bi pobjeđivao. Jedan takav slučaj je kvadratna ploča čokolade, tj. slučaj kada je m = n. Prvi igrač počinje s kvadratićem koji se nalazi jedno mjesto desno i iznad otrovanog kvadratića te ostavlja položaj u obliku slova L s "krakovima" jednake duljine. Jasno je da je to P-pozicija; na bilo koji potez drugog igrača može se odgovoriti simetrično i ponovno izjednačiti duljinu krakova, sve dok ga se ne prisili da uzme otrovani kvadratić. Drugi slučaj u kojemu je poznata pobjednička strategija prvog igrača je ploča dimenzija 2 × n. Prvi igrač počinje s gornjim desnim kutom ploče. Nakon toga na bilo koji potez drugog igrača odgovara tako da gornji red bude za jedan kvadratić kraći od donjeg. Jasno je da su dva reda čokolade duljine k i k + 1 P-pozicija igre Chomp. Što god napravio igrač koji je na potezu, njegov će protivnik moći igru ponovno dovesti do položaja tog oblika. Na kraju će igraču koji je na potezu ostati samo otrovani kvadratić. Već je Chomp na ploči čokolade dimenzija 3 × n znatno kompliciranija igra i ne možemo tako jednostavno karakterizirati P-pozicije. Možemo ih opisati beskonačno mnogo, ali pritom će ostati beskonačno mnogo P-pozicija koje nismo opisali. Stanje ploče zadajemo uređenom trojkom brojeva (a, b, c). Broj a nam govori koliko ima kvadratića čokolade u prvom redu ploče, b u drugom redu, a c u trećem. Očito je a ≤ b ≤ c. Najjednostavniji slučaj je a = 0, u kojem imamo dva reda čokolade. Znamo da su tada pobjedničke pozicije one sa c = b + 1. U idućem slučaju, a = 1, imamo samo dvije P-pozicije: (1, 1, 3) i (1, 2, 2). 
Prva od njih je pobjednička jer možemo igrati simetrično i prisiliti protivnika da pojede otrovani kvadratić. Za drugu se također lako provjeri da igrač koji je na potezu gubi. Sva ostala stanja ploče s a = 1 su N-pozicije, jer ih jednim potezom možemo svesti na neku od opisanih P-pozicija. Ako je b ≥ 2, pojedemo kvadratić u trećem retku i trećem stupcu i zadamo poziciju (1, 2, 2), a za b = 1, c ≥ 4 zadamo (1, 1, 3). Ako je a = 2, ponovno imamo beskonačno mnogo P-pozicija. To su pozicije za koje je c = b + 2. 
Dok protivnik uzima kvadratiće iz drugog ili trećeg reda, zadajemo kraće položaje istog tog oblika sve dok ne dođemo do P-pozicije (2, 2, 4). Ako uzme jedan ili oba kvadratića iz prvog reda, odgovorimo tako da ostane (1, 2, 2), odnosno P-pozicija oblika (0, b, b + 1). Za a = 3 i a = 4 imamo konačno mnogo P-pozicija: (3, 3, 6), (3, 4, 7), (3, 5, 5), (4, 4, 8), (4, 5, 9), (4, 6, 10) i (4, 7, 7). Primijetimo da će P-pozicija s čvrstim a uvijek biti konačno mnogo ako se među njima pojavi neka s b = c. Za a = 5 pobjedničke pozicije su (5, 5, 10), (5, 6, 9) i (5, k +7, k +11), k ≥ 0. Doron Zeilberger [Z1] uspio je pomoću računala odrediti P-pozicije za a ≤ 115. Kasnije je Andries Brouwer [AB] proširio taj račun sve do a = 90000, ali opća karakterizacija P-pozicija u igri Chomp s tri retka ne čini se izglednom. 3. Igre na parcijalno uređenim skupovimaOpisat ćemo jednu općenitu klasu igara u koje spadaju Nim i Chomp.
Primjeri parcijalno uređenih skupova su prirodni, cijeli, racionalni i realni brojevi s uobičajenom relacijom "manje ili jednako", ali ti primjeri imaju jedno dodatno svojstvo. Svaka dva broja a i b su usporediva, što znači da vrijedi bar jedna od tvrdnji a ≤ b ili b ≤ a. Takvi se uređeni skupovi nazivaju totalno ili linearno uređenima. Pravi primjer parcijalno uređenog skupa čine podskupovi zadanog skupa S i relacija "biti podskup" ⊆. Na primjer, {1, 2} i {2, 3} su podskupovi od {1, 2, 3} koji nisu međusobno usporedivi. Opišimo sad kako se na parcijalno uređenom skupu (P, ≤) može igrati igra slična Nimu i Chompu. Prvi igrač izabire element a ∈ P i briše sve elemente x od kojih je a manji ili jednak. Tako dolazimo do manjeg parcijalno uređenog skupa (P', ≤') na kojem drugi igrač nastavlja igru. U standardnoj varijanti igrač koji ne može nastaviti (jer je P' prazan skup) gubi, a u misère varijanti pobjeđuje. Nim i Chomp su zaista specijalni slučajevi ove općenite klase igara. Da bismo Nim shvatili kao igru na parcijalno uređenom skupu, trebamo definirati parcijalni uređaj na skupu šibica s kojima igramo. Šibica a je u relaciji sa šibicom b, u oznaci a ≤ b, ako se podudaraju ili se b nalazi u istom retku i desno od a. Šibice koje se nalaze u različitim recima nisu usporedive. Lako se provjeri da je definirana relacija refleksivna, antisimetrična i tranzitivna, a Nim odgovara igri na opisanom parcijalno uređenom skupu. Chomp također možemo opisati zadajući parcijalni uređaj na kvadratićima čokolade. Ako je ploča dimenzija m × n, kvadratiće koordinatiziramo uređenim parovima { (i, j) | i = 1,…,m, j = 1,…,n }. Donji lijevi kut ploče ima koordinate (1, 1), a gornji desni (m, n). Kvadratić s koordinatama (i1, j1) je manji ili jednak kvadratiću s koordinatama (i2, j2) ako vrijedi i1 ≤ i2 i j1 ≤ j2. S obzirom da je već 3 × n Chomp komplicirana igra, možemo li išta reći o igri na parcijalno uređenom skupu? Neki od zaključaka lako se generaliziraju, a u općenitoj situaciji bolje prepoznajemo prave razloge zbog kojih vrijede. Na primjer, standardna varijanta Chompa je trivijalna zato što odgovarajući parcijalno uređen skup ima najmanji element (1, 1). U parcijalno uređenom skupu (P, ≤) treba razlikovati najmanji element od minimalnih elemenata. Najmanji element je n ∈ P sa svojstvom n ≤ x, za svaki x ∈ P (tj. element koji je manji od svih ostalih elemenata iz P). Minimalni element je svaki m ∈ P za koji iz x ≤ m slijedi x = m (tj. element od kojeg niti jedan drugi element iz P nije manji). Ako postoji, najmanji element je minimalan i jedinstven. S druge strane, u parcijalno uređenom skupu bez najmanjeg elementa može postojati više različitih minimalnih elemenata. Primjer su prve (najljevije) šibice u svakom od redaka igre Nim. U totalno uređenim skupovima pojmovi najmanji element i minimalni element se podudaraju. Analogno definiramo najveći element i maksimalne elemente parcijalno uređenog skupa. Ako postoji najveći element, možemo generalizirati zaključak da prvi igrač ima pobjedničku strategiju. Kao i u igri Chomp, prvi igrač može izabrati najveći element n i dovesti igru u poziciju koja je možda pobjednička. Ako nije, onda je to N-pozicija i drugi igrač ima izbor elementa x koji je pretvara u P-poziciju. Međutim, onda je prvi igrač na početku mogao izabrati x i dovesti igru u istu poziciju, jer vrijedi x ≤ n. Za igre na parcijalno uređenim skupovima nedavno je dokazan jedan dublji rezultat, takozvani teorem o periodičnosti. Dokazao ga je Steve Byrnes 2003. godine [SB], u doba kad je bio u završnom razredu srednje škole. Kao rezultat Steve je dobio stipendiju od 100000 dolara pomoću koje si plaća školarinu na Harvardu. Ranije verzije članka objavio je na simpatičnoj web stranici http://www.geocities.com/sbyrnes321/ (ako postane nedostupna, ovdje možete pogledati kopiju). Ilustrirat ćemo teorem o periodičnosti na primjeru igre Chomp s tri retka. Student Dorona Zeilbergera, Xinyu Sun [XS], na tom je primjeru postavio sljedeću hipotezu. Pretpostavimo da je za čvrsti a skup svih P-pozicija (a, b, c) beskonačan. Tada niz razlika c − b za dovoljno velike vrijednosti od b postaje periodičan. Na primjer, spomenuli smo da su za a = 5 pobjedničke pozicije (5, 5, 10), (5, 6, 9) i (5, k +7, k +11), za sve k ≥ 0. Niz c − b u ovom slučaju je 5, 3, 4, 4, 4, 4,… Dakle, nakon dva člana niz postaje periodičan s periodom 1. Za a = 120 dobivamo prvi niz s periodom većim od 1. Tada su P-pozicije (120, b, c), za c = b + 71 + (-1)b i b ≥ 170 (period je 2). Za veće a-ove javljaju se dulji periodi, npr. za a = 6541 niz nakon 9249 "kaotična" člana postaje periodičan s periodom 9. Hipoteza o periodičnosti igre Chomp s tri retka provjerena je uz pomoć računala za vrijednosti a do 90000, prije nego što je postala korolarom općeg Byrnesovog teorema o periodičnosti igara na parcijalno uređenim skupovima. Literatura
1. Igra Nim |
