i
i
“Gravner-strategije” — 2010/5/12 — 13:16 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 13 (1985/1986)
Številka 4
Strani 194–203
Janko Gravner:
STRATEGIJE
Ključne besede: matematika, teorija iger.
Elektronska verzija: http://www.presek.si/13/790-Gravner.pdf
c© 1986 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
/iJ" -'-''''' -'I/"",1C"" I"",
STRATEGIJE
1. Osnovni pojmi
Bralci Preseka so gotovo že zdavnaj sami opazili, da lahko igre med dvema igral-
cema v grobem razdelimo v dve skupini : igre, pri katerih je treba "samo misli-
ti", in take, kjer igra določeno vlogo tudi sreča. Tukaj se bomo ukvarjali s
prvim tipom, bolj natančno, vse igre, ki jih bomo srečali, bodo
(a) končne, to je , igralec, ki je na potezi, ima vedno na izbiro le končno
mnogo potez in igra se vedno konča,
(b) spopolno informacijo, to pomeni, da igralec pred vsako svojo potezo
pozna tako pozicijo kot tudi ves dotedanji potek partije in
(c) med dvema igralcema.
Končnim igram s popolno informacijo med dvema igralcema bomo odslej rekli
kar na kratko igre, saj nas drugačne tu ne bodo zanimale .
Žal so resnično zanimive igre, kot so šah, go, dama, mlin in podobne, pre-
več zapletene, da bi nam tu služile kot primer, zato najprej opišimo nekaj takih
iger (ali bolje iqric] , ki imajo enostavnejša pravila , a so še vedno dovolj zanimi-
ve, da bodo marsikoga tako prevzele, da bo ob igranju s sošolcem preslišal
marsikatero šolsko uro . Da poenostavimo izražanje, bomo imenovali igralca, ki
je prvi na potezi, beli, njegovega nasprotnika pa črni.
1. Igra križci-krogci. V kvadratke pravokotne končne mreže (kot je na primer
list z nizkim karam) beli vpisuje križce, črni pa krogce. Zmaga tisti, ki prvi
uspe postaviti v neprekinjeno vodoravno ali navpično ali diagonalno vrsto n
svojih znakov . Če igralca zapolnita mrežo, ne da bi komu uspelo zmagati, je
igra neodločena. Običajno je n = 5, ker je za manjše n beli v tako očitni pred-
nosti, da igra ni zanimiva, za višje n pa je zmagati na manjših mrežah že zelo
težko . Za n = 3 lahko na primer beli zmaga že kar v treh potezah. Oglejmo si
o
)(
o O
)(
)(
O O
)(
)(
)(
Slika 1
194
primer na sliki 1, ki jasno pokaže, ka ko mora beli v tem primeru igrati, da bo
zmagal (to seveda gre le v primeru, da je mreža dovolj velika).
Naloga 1. Kako velika mora biti mreža za n = 3, da beli lahko zmaga? Na dovolj
veliki mreži opiši pot belega do zmage v primeru n =4 .
Za n = 5 pa , kolikor je avtorju znano , še ni dokazano , da beli sploh lahko zma-
ga, če seveda črni igra optimalno .
II. Razne variante igre nim
11.1. Nim 1. Na mizi je n dinarjev . Igralec, ki je na potezi, lahko vzame 1,2
ali 3 dinarje. Tisti, ki pobere zadnji dinar, zmaga in pospravi ves kupček .
Naloga 2. V katerem primeru beli lahko zmaga in kako mora za to igrati? Kaj
pa , če tisti, ki pobere zadnji dinar, izgubi? Kaj pa , če lahko igralec na potezi
vzame poljubno število dinarjev med 1 in k (k < n j?
11.2. Nim 2. Na mizi je n kupčkov SPI, " " Pn dinarji. Igralec, ki je na po-
tezi, lahko vzame poljubno število dinarjev iz enega izmed kupčkov (ven-
dar mora vzeti vsaj en dinar). Tisti , k i pobere zadnji dinar, zmaga. Na pri -
mer, če so trije kupčki z 1,3 in 5 dinarji, lahko igra poteka tako: B( 1,3 ,5).
Č( 1,3 ,0). B( 1,1,0), Č( 1,0 ,0 ) (Č( 1,3,0) pomeni , da je črni na potezi in da
ima pred sabo kupčke z 1, 3 in O dinarji) in črni zmaga. Pozneje bomo vi-
deli, da v tej igri beli "skoraj vedno" lahko zmaga .
11.3. Drevesni nim. Kaj je graf in kakšne vrste grafi so drevesa, bralci Pre -
seka že vedo (glej tudi sliko 2). Igralca imata na začetku pred sabo drevo z
vrhom V, ki ima še to lastnost, da iz to č ke V vodi le ena povezava. Igrata
tako , da izmenično počrnjujeta toč ke in povezave drevesa. Igralec, ki je na
potezi , mora počrniti neko (povezano) pot med neko nepočrnjeno in neko
že počrnjeno točko. Na začetku je ed ina črna točka vrh V. Pri počrnitvi
poti pa se poč rnijo tudi vse točke na njej. Zm agovalec je tisti , ki počrni
zadnjo povezavo (ali, ka r je isto, zadnjo točko ) . Igra lahko poteka na
primer tako , kot je prikazano na sliki 2 .
Slika 2
Tukaj je zmagal črni .
195
11.4. Zastrupljena čokolada. Igralca imata pred sabo tablico čokolade ve-
likosti mx n . Igralec, k i je na potezi , si izbere košček in ga odgr izne, hkrati
z njim pa tudi vse, kar je desno in pod tem koščkom (torej ves desni
spodnji vogal glede na izbrani košček) . Košček levo zgoraj je zastrupljen,
zato tisti, ki ga mora pojesti, izgubi. Oglejmo si primer na sliki 3 (m = 3,
n = 4). S križcem je označen izbrani košček.
Z I I
)(
čn-4
Z
)(
B
B
Z I )( I
č
Z I
)(
B č
Slika 3
Pri tem beli seveda zmaga.
Naloga 3. Kako mora beli igrati v primeru m = 2 (ali n = 2), da bo gotovo zma-
gal?
III. Bridget. Igralca imata pred sabo kvadratno mrežo belih in črnih točk, zn
točkami v vsaki od št irih stranic (v narisanem primeru na sliki 4 je n = 3, obi-
čajno je večji) . Beli z rdečim svinčnikom povezuje bele točke , v vsaki potezi z
Oo
• •
O O
• •
O O
• •
O O
O
• •
O
• •
O
• •
O
O O
O
•
•
•
196 Slika 4 Slika 5
v o d ~ r v r ~  li  mien^ Erbo pr, em pwtdk,CrM pa o Crnim rwidnikorn p w a  
Aljs Crne tdh. Nabga m a  19 pmasti mko mkko v q d n j l  wbi a rseko 
tdb r ~wrnl l .  &#!la pa, m i  nr!m mEk4 v Levem f io lwr neka m e h  
v d-m. M a  ~8rdda ih E m  EaSs r u  mwIo $ekM. Zmgawalni polo24 
[ belfqa Je RB p r h r  t w n  kot na gki 5. 
IV. Hex. To @o I$ Web* hrBti m mrds asthlnikw. Mr& Im ohllko romba 
ve1i-i k x k. Obibjna j b A =  11, rw diki 8 ps 1s k = 4. I & a  IzmcnEna. 
pawlfata hmenEb nr PI&. Brli 
I $!mh t brlirni karrranEk1 pwmstl 
I (to v n i  -wid wwzm mrbj  
dve mprgtni strMl, s h h i  z 8, 
&nl pa rrwotmr. s Crnimi karnmnkki 
mmi, o r n h i  s Em 4 maw- 
valnih pwti b w q a  )e am&w nn 
tliki. h t a b  kot Y puBjlnJm mi- 
mew ss dr videti, & * Ma morn 
kanEafi z m h q a  nekagrt 
To, kar W Wd WIh, bo r n m u m e t ~ ~  m r @  r pram1 %Istam pamenu te b+ 
W e  WmllkQJVBf h n w  &WII, cts mW &st4rr nit1 4-w~  nemb pa 
rr#n PT doh1 m lmb dali, kaka bi thm Wl dobill. Ci wvredmstl teklh &b 
bi s& @wda ds16 rwprwgmt1, mhmjala eab t w t m a t l k  %bk I " i n l k n i r t i " l ,  
ki jih a prbd Qdkh44o. Vs.4 e- w lim v6Cinom ne g n  wrakmti ,  pa 
#dl dobdcm uporhnactl, & r ~ m  ht j  ah-aktctnar ne 4lsb. Pogwmcr rl 
na]pwl pqm* prlmar tam m m B l M a .  Vemo,da imam dm dru2ini skcpaji 
d a m  m k .  K d k  bi dokmli, d l  imm wj ana d d i n e  Wrl M w h ?  Rb- 
pmm* &a W wka W n m  I m l a  @u& ul, bl Iih o h  skw inell @wE 
W, kar Se r W u  r m - m l m b .  Tmkmu d ~ k m u  rsdemo Wwlm *d 
rbwdurn" IpnYrdh do pmthhwjd In Je E l m  m h m k t i m .  m 
p w  d i m ,  I katerh bi ugo&vlll, kWn bd drufin j l  tiaa r w m  W r l d  
ggpki. J m ,  4 immm pmrnuto padstkow H kd w k ~ .  
vmrm so 4 4  k d k n  m. Drfidrdmc, $1 mrel nelfd pdmw, PrviE, 
wkurnu m S n m u  b k u  iw rmEmmo BH4 Prl MU so TW p r i m  W ~ M  irldk: 
zmaga belega , zmaga črnega in remi. Imamo tudi igre, kjer je možnih več izi-'
dov , med našimi primeri pa takih ni. Seveda so zanimive samo igre, kjer sta vsaj
dva možna izida.
Najvažnejši pojem pri igrah pa je strategija. To je natančen predpis, kako
naj v vsaki potezi in v vsaki poziciji določeni igralec igra oziroma strategija je
popoln (in vnaprej dan) opis, kako naj igralec odgovarja na poteze nasprotnika,
in ne vključuje nobene bistrosti. Mislimo si lahko, da igro igra računalnik, ki
mo ra v poljubn i poziciji potegniti potezo, katero, pa določa program (seveda
brez generatorja slučajnih števil) . V igri nim 1 je ena od strategij belega taka:
v vsaki potezi vzame en dinar. V igri nim 2 pa lahko igramo po tejle strategiji :
vedno vzamemo vse dinarje z najmanjšega kupa. Pri čokoladi pa lahko črni
igra po tejle strategiji : pogleda , kateri kos je odgrizn il v svoji potezi beli, si izbe-
re košček, ki se le z eno točko do tika tega kosa (ta je nujno en sam). ga odg riz-
ne in z njim vse koščke desno in pod njim .
Seveda nobena od naštetih strategij ni kaj prida. Za vsako od njih bo na-
sprotnik , ko enkrat ve zanjo, zlahka igral tako, da bo zmagal. Kakšne strategije
pa sploh so dobre? Najbolj ugodne so gotovo take, ki omogočajo zmago ne
glede na to, kaj igra nasprotnik. Takim st rategijam rečemo zmagovalne strate-
gije. Tako bi na primer nalogo 1 lahko povedali tudi tako: poišči zmagovalno
strategijo za belega v igri nim 1.
Če v neki poziciji obstaja zmagovalna st rategija na primer za belega, potem
ji rečemo zmagovalna pozicija za belega. Igra torej postane nezanimiva , čim be -
li najde zase zmagovalno strategijo, saj jo lahko brez razmišljanja uporab lja in
črni je obsojen na poraz, pa če se še tako trudi.
Vzemimo , da sta v neki igri le dva možna izida: zmaga belega ali zmaga
črnega. Videli bomo, da potem obstaja bodisi zmagovalna strategija za belega
bodisi za črnega. To je najbrž bil prvi "resni " rezultat teorije iger, dokazal ga je
leta 1921 nemški matematik Ernst Zermelo. Če sledimo njegov i ideji , predpo-
stavimo najprej, da je naša trd itev napačna. To pomeni, da - po kakršnikol i že
strategiji beli igra - vedno lahko črni s primerno izbiro potez zmaga in narobe ,
za vsako strategijo črnega lahko beli igra tako, da bo zmagal. Iz tega sledita dve
posledici .
(1) ~ :aterokoli prvo potezo bo bel i odigral, bo nastala pozicija, ki zanj ne bo
zmagovalna. Seveda, saj če bi obstajala taka p rva poteza belega, ki bi ga prive-
dla v zmagova lno pozicijo , bi bila zanj že začetna pozicija zmagovalna.
(2) Obstaja vsaj ena začetna poteza belega, ki privede do pozicije, ki za č rne ­
ga ni zmagovalna. V nasprotnem primeru bi bila namreč začetna pozicija zma -
govalna za črnega .
Ko enkrat to vemo, smo skoraj opravili. Iz (1) in (2) sledi, da obstaja taka za-
četna poteza belega, da pozicija, ki nastane, ne bo zmagovalna za nobenega od
obeh igralcev . Imenujmo to pozicijo YI . S popolnoma istim sklepom lahko
pokažemo, da obstaja taka poteza črnega v poziciji YI, da bo nastala pozicija
Y 2, ki ne bo zmagovalna nit i za belega niti za črnega. Potem lahko, spet na
198
enak način. dobimo pozicije Y3, Y4 • •••• ki niso zmagovalne za nikogar. Torej
se taka igra ne bo nikoli končala. saj če bi se, bi bila končna pozicija zmago-
valna za nekoga (predpostavili smo, da sta le dva mogoča izida). Dobili smo to-
rej neskončno zaporedje potez. kar nasprotuje naši predpostavki o končnosti
igre.
Naloga 6. Vzem imo, da imamo igro s tremi izidi : zmago belega. zmago črnega
in remijem. Potem bodisi obstaja zmagovalna strategija za belega. bodisi taka
strategija belega . s katero lahko beli iztrži vsaj remi. bodisi zmagovalna strate-
gija za črnega.
Torej za šah lahko rečemo tole: bodisi obstaja zmagovalna strategija za be-
lega. bodisi zmagovalna strategija za črnega. bodisi se ob pametni igri obeh
igralcev vsaka pa rtija mora izteči v remi. Opomba: nobena od teh strateg ij
danes še ni znana (in tudi gotovo ne bo tako kmalu), ker je šah igra. ki ima
ogromno število mož nih pozicij.
Naloga 7. Predpostavi. da imaš na voljo računalnik z neskončnim spominom,
ki dela zelo hitro. Premisli. kakšen bi bil program, ki bi ugotovil , katera od
treh zgo raj navedenih možnosti pri šahu dejansko nastopi.
Vrnimo se sedaj k našim primerom. Dokažimo najprej tole. Pri igri križci-
krogci ne obstaja zmagovalna strategija za črnega (torej obstaja taka strateg ija
za belega, s katero lahko vsaj remizira). Pa predpostavimo nasprotno, da zma-
govalna strategija za črnega obstaja. V tem primeru beli lahko igra takole. V
svoji prvi potezi nekje naredi križec (kjerkoli). Nato počaka, da svojo potezo
odigra črni. Potem se beli lahko brani tako, da igra zmagovalno strategijo črne­
ga, dela se, da je črni z dodatnim križcem. Če zmagovalna strategija (za črnega)
od njega zahteva, da igra tisto potezo, ki jo je že naredil. zariše križec na po-
ljubnem praznem polju . Na ta način igra zmagovalna strategijo z dodatno pote-
zo. Toda ta dodatna poteza ga pri zmagovalni strategiji ne moti, saj je dodatni
križec vedno lahko le v korist in nikoli v škodo . Potemtakem beli na ta nač i n
lahko zmaga . Prišli smo torej v nasprotje s predpostavke, da črni lahko zmaga.
S tem smo to trditev ovrgli. Morda se je pri tem dokazu komu zdelo čudno, da
predpostavljamo, da beli ve za hipotetično zmagovalno strategijo črnega. To
smo v resnici prisiljeni storiti . saj za zmagovalno strategijo zahtevamo. da vodi
do zmage, kakorkoli že nasprotnik igra. Smo torej kar se da pesimistični, pred -
postavimo, da nasprotnik v vsaki potezi ve za svojo najboljšo potezo in jo brez
usmiljenja igra.
Naloga 8. Pokaži, da pri igrah bridget in hex obstaja zmagovalna strategija za
belega.
Naslednja je na vrsti igra zastrupljena čokolada. Uženemo jo s podobnim
199
razmislekom, kot je bil zgornji . Denimo, da je vsaj eno od števil m, n večje od 1
(če je m = n = 1, je beli, jasno, izgubljen) . V tem primeru obstaja zmagovalna
strategija za belega. Naj temu ne bo tako, naj torej obstaja zmagovalna strate-
gija za črnega . Potem v prvi potezi beli odgrizne samo košček na poziciji (m,n) .
Katerokoli potezo nato igra črni, prvo potezo belega zabriše in beli se brez te-
žav lahko drži zmagovalne strateg ije črnega in zmaga . Predpostavka, da lahko
zmaga črni, je torej ovržena in črni je tisti , ki je zapisan pogubi .
Tudi v igri drevesni nim obstaja zmagovalna strategija za belega. Da bra lca
ne bi utrujati z rigoroznostjo, bomo dokaz za to trd itev razložili kar na prime-
ru. Vzemimo tile dve drevesi s slike 7:
Slika 7
Drugo drevo dobimo iz prvega tako, da mu "odrežemo deblo" oziroma vrh pre-
maknemo v točko V l. Tudi na tako dobljenem drevesu lahko igramo drevesni
nim po istim pravilih. Recimo tej igri nim«. V tej igri obstaja bodis i zmagovalna
strategija za belega bodisi za črnega. Če nastopi prvi primer in je prva poteza v
zmagovalni strategiji za belega na primer počrnitev poti od Ta do V 1 , potem v
prvi potezi originalne igre beli počrni pot od Ta do V, nato pa igra zmagovalno
strategijo belega v igri nim«. Če pa v igri nim« obstaja zmagovalna strategija za
črnega, beli v prvi potezi preprosto počrni povezavo od Vdo V 1, nato pa spet
brezskrbno igra zmagovalno strategijo za črnega v igri nim« in seveda spet
zmaga.
Vse doslej so bile zmagovalne strategije "v oblakih". Vemo, da obstajajo,
a jih ne poznamo. Za dve od naštetih iger bomo bolj konkretni in bomo zmago-
valni strategiji opisali.
2. Zmagovalna strategija za igro nim 2
V tej zmagovalni strategiji je skrito kar precej matematike. Kdor želi
uspešno igrati po njej. se mora najp rej dobro naučiti pretvarjati dvojiški zapis
števil v desetiškega in obratno. Pa preidimo k stvari. Najp rej bomo naredili ko -
rak , ki je v matematiki precej pogost, namreč, definirali bomo nekaj. kar na
prvi pogled ne bo imelo niti najmanjše zveze z našo igro. Vzemimo dve nene-
200
gat ivn i celi števili a in b in i z rač u naj mo "nekaj podobnega kot vsoto". a tfJb . na
t ak način : zap išemo a in b v dvojiškem sistemu eno nad d rugo. t ak o da so eni ce
nad enicami itd. Nato posamezne številke seštejemo po modulu 2. pri č emer pa
seštevek v nekem stolpcu n ič ne vpliva na vsoto v naslednjem. Najbolj se to vidi
na pr imeru :
1011
11 Gl 23 = 10111 =28
11100
To torej ni običajna vsota števil. Ta operacija ima .nasled nje lastnosti. ki jih je
zelo lahko preveriti. zato jih bomo le navedli.
a tfJ (b Ef) c) = (a tfJ b) Ef) c
atfJb=btfJa
atfJO=a
atfJa =O
(asociativnost) •
(komutativnost) r
in
za poljubna ce la števi la e, b , c > O. Bralca. ki obvlada algebraične strukture,
opozorirno , da je množ ica (N U {O} • tfJ) Abelova grupa (kar za običajno
seštevanje ne velja).
Predpostavimo sedaj, da imamo pri igri nim 1 n kupčkov s PI • .. .. Pn dinar-
ji . Najprej izračunamo tako imenovano vsoto pozicije s = PI Ef) oo ' tfJ Pn . Za
igro s št irimi kupčk i s 3 . 5 . 7 in 11 dinarji je vsota na primer
3
5
7
11
10
11
101
111
1011
1010
enaka 10. Videli bomo . da igralec na potezi lahko zmaga vedno, ko je vsota
različna od O (v nasprotnem p rime ru pa seveda lahko zmaga drugi igralec).
Igrati je treba tako . da bo po naši potezi vsota pozicije vedno enaka O. če
je to le mogoče (v zgornjem primeru je: v največjem kupu je t reba pustiti le 1
dinar). Pa vzemimo . da je vsota začetne pozicije različna od O. in pokažimo , d a
lahko beli odigra t ako potezo . ki bo črnega postavila pred pozicijo zničelno
vsoto . Izračunajmo števila SI = S tfJ P I • ...• Sn = S tfJ Pn . Da se dokazati. da
obstaja tak i. 1 ~ i ~ n , da je Si < Pi . Beli sedaj igra tako. da vi-tem kupčku
pusti Si kovancev . Kakšna je po tej potezi pozicija? Spremen il se je le i-ti kup-
ček. vsota nove pozicije s' . je torej enaka :
201
S'=Pl EB ... EBpj _l EBSjEE>Pj+l EB EBPn =
=Pl EB ... (f)Pj_l EBPj@S ~Pj+l EE> EBPn =
= (PI EB ... (f)pn ) EBS=S~S=O
Kaj pa zdaj lahko igra črni? Karkoli bo revež igral, bo vsaj venem kupčku
spremenil (v dvojiškem zapisu) vsaj eno številko, s čimer bo povzročil ,da vso-
ta pozicije ne bo več nič . S tem bo belemu omogočil potezo, ki spe t vodi v
pozicijo z ničelno vsoto. In tako dalje do konca igre, ki je seveda tak, d a so vsi
kupčki prazni. Vsota take pozicije je seveda enaka O, kar pomeni , da je zadnjo
potezo odigral beli.
Vse je torej odvisno od vsote začetne pozicije . Če je enaka O, lahko zmaga
črni, v vseh ostalih primerih pa beli.
Naloga 9. Ali je poteza, ki jo beli v primeru, da je vsota pozicije različna od O,
mora igrati, do bo gotovo zmagal, vedno ena sama?
Naloga 10. Spremenimo pravila tako, da izgubi tisti , ki mora pobrat i zadnji d i-
na r. Kdaj v taki igri lahko beli zmaga? Opiši tudi zmagovalno strategijo.
3. Zmagovalna strategija za igro bridget /
O O lj
/
Najprej zmagovalna strategijo za • • • •/ /belega opi šimo, pozneje jo bomo ute- /
meljili. Beli naj v mislih potegne diago- O /0 O, /
nalo kot na sliki 8, nato pa igra potezo • /. • •/
P1. //e/r-O O• •Slika 8 O O
Nato naj igra po naslednjem algoritmu:
(1) Če črni poveže neko točko na diagonali s horizontalno črto, potem naj bo
odgovor tak, kot na sliki 9 .
1
///
( 1. 1) • •
/
/
/
/ Slika 9
(2) Če črni poveže točki s črto pod diagonalo kakorkoli drugače, potem naj
odgovori tako, kot kaže slika 10.
202