Hry a strategick´e myˇslen´ı V´aclav Vopravil Kombinatorick´ymi hrami budeme rozumˇet hry dvou hr´aˇc˚ u (hr´aˇci se tradiˇcnˇe oznaˇcuj´ı Lev´y a pRav´y, b´ıL´y a ˇceRn´y,. . . , struˇcnˇe L a R hr´aˇc), kter´e splˇ nuj´ı n´asleduj´ıc´ı neform´aln´ı poˇzadavky: (a) Hra m´a nˇekolik (zpravidla koneˇcn´y) poˇcet pozic. Jedna z tˇechto pozic se naz´yv´a poˇc´ateˇcn´ı. (b) Pravidly jsou stanoveny vˇsechny povolen´e tahy. Tahem je m´ınˇena zmˇena ze souˇcasn´e pozice do nov´e pozice. Vˇsechny nov´e pozice se naz´yvaj´ı moˇznostmi. Oba hr´aˇci maj´ı stejnou informaci o hˇre. (c) Hr´aˇci se v taz´ıch stˇr´ıdaj´ı dokud nedos´ahnou koncov´e pozice. (d) Hr´aˇc na tahu m´a k dispozici veˇsker´e informace o hˇre; vˇsechny moˇzn´e budouc´ı moˇzn´e tahy, a je-li to nezbytn´e, tak´e pˇredch´azej´ıc´ı moˇzn´e tahy. (e) Ve hˇre nehraje ˇz´adnou roli n´ahoda, ˇstˇest´ı, blufov´an´ı,. . . (f) Hr´aˇc na tahu, kter´y nem˚ uˇze t´ahnout, prohr´al a jeho soupeˇr vyhr´al (norm´aln´ı varianta hry). Jistˇe m´a smysl se pt´at, kter´e hry jsou kombinatorick´e, jak´y maj´ı hry v´ysledek? Skonˇcit hry mohou v´ıtˇezstv´ım jednoho z hr´aˇc˚ u (a tedy prohrou protihr´aˇce) nebo patem (rem´ızou). Vˇzdy budeme pˇredpokl´adat, ˇze oba hr´aˇci nebudou dˇelat chyby a budou hr´at hru optim´alnˇe. Racion´aln´ı tah znamen´a nejv´yhodnˇejˇs´ı tah. Hr´aˇc na tahu, pokud nem˚ uˇze jiˇz d´ale t´ahnout, prohr´al (a druh´y vyhr´al). Jin´ymi slovy hry skonˇc´ı patem, pokud oba hr´aˇci hraj´ı racion´alnˇe a pravidla hry umoˇzn ˇ uj´ı neprohr´at (ale pro protihr´aˇce tak´e nevyhr´at). Pˇrijmeme jeˇstˇe nˇekolik omezuj´ıc´ıch podm´ınek na vyˇsetˇrovan´ı hry. Jednou z nich je pravidlo (g) Hra skonˇc´ı po koneˇcnˇe mnoha taz´ıch (s v´ysledkem v´yhry jednoho z hr´aˇc˚ u, nebo patem). Budeme poˇzadovat, aby hra byla zcela determinov´ana, tj. v´ysledkem hry bude pr´avˇe jedna z tˇechto moˇznost´ı: 1. Lev´y hr´aˇc vyhraje a nez´aleˇz´ı na taz´ıch prav´eho, 2. prav´y hr´aˇc vyhraje a pˇritom nez´aleˇz´ı na taz´ıch lev´eho hr´aˇce, 3. oba hr´aˇci mohou dos´ahnout patu (maj´ı neprohr´avaj´ıc´ı strategii), bez ohledu na tahy protihr´aˇce (aniˇz by se domlouvali). Poˇzadavek (g) zes´ıl´ıme a budeme poˇzadovat, aby pravidly hry bylo vˇzdy zaruˇceno, aby hra skonˇcila (hr´aˇc, kter´y nem˚ uˇze t´ahnout, prohr´al) (podm´ınka konce hry). Kl´ıˇcovou ot´azkou ve hr´ach je nalezen´ı, kter´y z hr´aˇc˚ u m´a vyhr´avaj´ıc´ı strategii. Strategie 1
hr´aˇce urˇcuje jak hr´aˇc bude postupovat (t´ahnout) v jednotliv´ych pozic´ıch. Vyhr´avaj´ıc´ı strategie hr´aˇci zabezpeˇc´ı v´yhru bez ohledu na moˇzn´e tahy protihr´aˇce. Struktur´arn´ı indukc´ı je moˇzn´e jednoduˇse dok´azat, ˇze kaˇzd´a kombinatorick´a hra dvou hr´aˇc˚ usu ´ plnou informac´ı m´a vyhr´avaj´ıc´ı strategii pro jednoho z hr´aˇc˚ u.
Dawsonovy ˇ sachy Hru Dawsonovy ˇ sachy1 hraj´ı dva hr´aˇci. Hr´aˇci se v taz´ıch stˇr´ıdaj´ı, a pokraˇcuj´ı podle pravidel hry, dokud hra neskonˇc´ı (hr´aˇc na tahu nem˚ uˇze t´ahnout). Tradiˇcnˇe se hr´aˇci naz´yvaj´ı b´ıL´y a ˇceRn´y. Hraje se na ˇsachovnici, ale pouze na prvn´ıch tˇrech ˇr´adc´ıch. Na poˇc´atku hry jsou b´ıl´e kameny v prvn´ı ˇradˇe a ˇcern´e v horn´ı ˇradˇe. C´ılem hry je znemoˇznit hr´aˇci prov´est tah (norm´aln´ı varianta hry), tj. zv´ıtˇez´ı hr´aˇc, kter´y udˇel´a posledn´ı tah. Ve hˇre zaˇc´ın´a hr´aˇc s b´ıl´ymi kameny. Kameny se pˇresouvaj´ı jako ˇsachov´y pˇeˇsci - o jedno pole pˇr´ımo vpˇred (pokud je pole voln´e) nebo, kdyˇz stoj´ı na sousedn´ım poli v diagon´aln´ım smˇeru soupeˇr˚ uv k´amen, o jedno pole ˇsikmo vpˇred. Stoj´ı-li dva pˇeˇsci proti sobˇe (soused´ı spolu ve stejn´em sloupci), nemohou se br´at (neplat´ı ˇsachov´e pravidlo en passant). Kdyˇz pˇeˇsec postoup´ı ˇsikmo vpˇred na pole, kde leˇz´ı soupeˇr˚ uv k´amen, je soupeˇr˚ uv k´amen odebr´an. Bran´ı kamen˚ u je povinn´e. S pˇeˇscem, kter´y doˇsel na protˇejˇs´ı konec desky, uˇz nen´ı moˇzn´e d´al hr´at. ´ Uloha: Nejprve si zahrajte nˇekolik parti´ı. Rozmyslete si, ˇze Dawsonovy ˇsachy jsou kombinatorickou hrou. Zahrajte si tak´e variantu, ve kter´e bran´ı kamen˚ u nen´ı povinn´e. Kdo vyhraje, pokud v kaˇzd´em tahu si vybere sv˚ uj nejlepˇs´ı tah ve hr´ach 3 × 3, 4 × 3, resp. 5 × 3. B´ıl´y nebo ˇcern´y hr´aˇc? Jak´y bude prvn´ı tah v´ıtˇeze? ´ Ulohy: B´ıl´y a ˇcern´y hr´aˇc hraj´ı Dawsonovy ˇsachy: . . . . . . . . . . . . . . .| . . .{z. . . } 7×3
. . . . . . . . . . . . . . . . .| . . . {z . . . .} Dawsonova u ´loha
. . . . . . . . . . . . . . . . . . .| . . . .{z. . . . }
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9×3
8×3
1. Budeme pˇredpokl´adat, ˇze na tahu je b´ıl´y hr´aˇc v poˇc´ateˇcn´ı pozici jako je na prvn´ım obr´azku (ˇsachovnice 7 × 3). M˚ uˇze si hr´aˇc sv´ym tahem zabezpeˇcit v´ıtˇezstv´ı? Pokud ano, jak? 2. V pozici jako je na druh´em obr´azku ˇcern´y hr´aˇc nab´ıdne, aby b´ıl´y hr´aˇc zaˇc´ınal. Pˇrijme b´ıl´y hr´aˇc tuto nab´ıdku? Pokud ji odm´ıtne, proˇc? 3. B´ıl´y hr´aˇc navrhne zahr´at si na ˇsachovnici 9×3 jako na tˇret´ım obr´azku, nebo nˇejakou ˇ y hr´aˇc jeho jinou hru na ˇsachovnici (2n − 1) × 3, kde n je kladn´e cel´e ˇc´ıslo. Cern´ nab´ıdku neakceptuje, ledaˇze by ve hˇre zaˇc´ınal. Proˇc? 4. Hra se dostala do pozice jako je na posledn´ım obr´azku. B´ıl´y hr´aˇc je na tahu. M˚ uˇze vyhr´at? A proˇc? N´apovˇeda: Pˇri anal´yze vyuˇzijeme jednak vynucen´e tahy a rozdˇelen´ı hry na disjunktn´ı ˇc´asti. Nejdˇr´ıve pˇredpokl´adejme, ˇze m´ame dostateˇcn´e dlouhou ˇsachovnici a prvn´ı tah 1
Thomas Rayner Dawson (1889 – 1951), ˇsachov´ y teoretik, u ´lohu formuloval v jej´ı betlov´e variantˇe r. 1935.
2
ˇ y je donucen br´at a b´ıl´y hr´aˇc dokonˇc´ı. V´ysledn´a b´ıl´eho bude posledn´ım kamenem. Cern´ ˇsachovnice bude o dva sloupce menˇs´ı. D´ale pˇredpokl´adejme, ˇze b´ıl´y zah´aj´ı tahem pˇredposledn´ım kamenem. Vynucen´ymi tahy se ˇsachovnice zmenˇs´ı o tˇri sloupce. Tyto tahy pˇripom´ınaj´ı odeb´ır´an´ı kamen˚ u ve hˇre Nim[2, 3; n]. Zaˇcne-li b´ıl´y nˇekde ne na kraji“, po ” vynucen´ych taz´ıch se odeberou tˇri sloupce a ˇsachovnice se rozpadne na dvˇe ˇc´asti. M´a-li ˇsachovnice pouze jeden sloupec, prvn´ı tah zablokuje soupeˇre. Tato anal´yza n´am dovoluje probl´emy Dawsonov´ych ˇsach˚ u pˇrev´est na u ´ lohu typu Nim. Na poˇc´atku hry je na stole hrom´adka n kamen˚ u. Dovolen´ymi tahy jsou (a) odebr´an´ı jednoho kamene v pˇr´ıpadˇe, ˇze hrom´adka obsahuje pouze jeden k´amen, (b) odebr´an´ı dvou kamen˚ u, (c) odebr´an´ı tˇr´ı kamen˚ u a pˇr´ıpadn´e rozdˇelen´ı hrom´adky na dvˇe. . . . Napˇr´ıklad b´ıl´y hr´aˇc z pozice . . . m´a na v´ybˇer dva r˚ uzn´e tahy (symetrick´e pozice vy. . . . . . . . . nech´ame): . . . (ˇspatn´y tah) a . . . . Druh´y tah je pro b´ıl´eho optim´aln´ı, protoˇze b´ıl´y po . . . . . . . . . vynucen´ych taz´ıch dokonˇc´ı do pozice . . . . Podobnou u ´ vahou z´ısk´ame, ˇze prvn´ı hr´aˇc m´a . . . vyhr´avaj´ıc´ı strategii na ˇsachovnic´ıch (2n + 3) × 3 (optim´aln´ı tah je t´ahnout prostˇredn´ım kamenem a kop´ırovat tahy). Analyzujte tak´e pozice pro n = 4, 5, . . . a urˇcete prvn´ı optim´aln´ı tah pro ˇsachovnici 10 × 3. Pozn´amka: Sprague-Grundyova posloupnost G Dawsonov´ych ˇsach˚ u zaˇc´ın´a: 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3, 0, 1, 1, 3, 0, 2, 1, 1, 0, 4, 5,. . . Posloupnost G(n) je periodick´a s periodou 34, ale se sedmi v´yjimkami (posledn´ı je n = 51). Napˇr´ıklad pro . . n = 2 je . . = {2 | 2 } = ∗ = •1. . .
Hry s odeb´ır´ an´ım pˇ redmˇ et˚ u Neform´aln´ı pravidla tˇechto her jsou tato: 1. Dva hr´aˇci, tradiˇcnˇe Lev´y a Prav´y hr´aˇc, L a R, stˇr´ıdavˇe odeb´ıraj´ı kameny z jedn´e (nebo v´ıce) hrom´adek. 2. Pravidly hry je urˇceno kolik lze v jednom tahu odeb´ırat kamen˚ u. Tato ˇc´ısla jsou kladn´a, pro oba hr´aˇce stejn´a (a nemˇenn´a). Obecnˇe takov´a mnoˇzina S m˚ uˇze b´yt nekoneˇcn´a, ale my se zamˇeˇr´ıme pouze na koneˇcn´e mnoˇziny S. 3. Kaˇzd´e odebr´an´ı kamen˚ u se naz´yv´a tahem. 4. Hr´aˇc, kter´y ve hˇre zahraje posledn´ı pravidly povolen´y tah, vyhr´al. Posledn´ı hr´aˇc odebere posledn´ı k´amen a n´asleduj´ıc´ı hr´aˇc jiˇz ˇz´adn´y pravidly povolen´ymi tahy, nem˚ uˇze kameny odeb´ırat. (Jinak by poruˇsil pravidla.) 5. Ve hˇre je vˇzdy jeden z hr´aˇc˚ u v´ıtˇezem. (Ve hˇre nem˚ uˇze nastat patov´a nebo rem´ızov´a situace). Z´apisem Subst[s1 , s2 , . . . ; n] budeme rozumˇet hru na jedn´e hrom´adce o n kamenech a v kaˇzd´em tahu je moˇzn´e odebrat pouze s1 , s2 , . . . kamen˚ u. Oznaˇc´ıme S mnoˇzinu {s1 , s2 , . . .}. Poˇcet n je poˇc´ateˇcn´ı pozice hry, jinou moˇznou pozic´ı je Subst[s1 , s2 , . . . ; n − s1 ]. Tak jako v pˇr´ıkladu Dawsonov´ych ˇsach˚ u, m˚ uˇzeme vˇsechny pozice hry zn´azornit koneˇcn´ym obyˇcejn´ym orientovan´ym grafem bez kruˇznic (DAG). Pozice ve hˇre zn´azorn´ıme uzly grafu 3
a jednotliv´e moˇzn´e tahy orientovan´ymi hranami. Napˇr´ıklad z pozice Subst[1, 3; 9] vedou dvˇe ˇsipky do pozic Subst[1, 3; 9 − 1], Subst[1, 3; 9 − 3], tj. Subst[1, 3; 8] a Subst[1, 3; 6], atd. Protoˇze hra nem˚ uˇze b´yt patov´a, m˚ uˇzeme jednotliv´e pozice oznaˇcovat takto: (a) koncovou pozici oznaˇc´ıme P. (b) Pozice, ze kter´ych vede alespoˇ n jedna ˇsipka (tah) do pozice P, oznaˇc´ıme N pozic´ı, (c) pozice, ze kter´ych vede tah pouze do N oznaˇcujeme tak´e P. V pozic´ıch P existuje vyhr´avaj´ıc´ı strategie pro II. hr´ aˇce a naz´yvaj´ı se nulov´e. Pozice N se naz´yvaj´ı nenulov´ymi a oznaˇcuj´ı situaci, kdy ve hˇre existuje vyhr´avaj´ıc´ı strategie pro I. hr´aˇce (ten, kter´y ve hˇre zaˇc´ın´a). Pozice P znamen´a, ˇze pˇredch´azej´ıc´ı hr´aˇc zahr´al v´ıtˇezn´y tah, pozice N n´asleduj´ıc´ı, a nez´aleˇz´ı na tom, jak bude protihr´aˇc hr´at. Naj´ıt takov´e tahy a takov´e pozice, kter´a hr´aˇci zaruˇc´ı v´yhru je pˇredmˇetem strategie ve hˇre. Vyhr´avaj´ıc´ıch tah˚ u v dan´e hˇre m˚ uˇze b´yt i v´ıce, ale ne vˇsechny tahy z vyhr´avaj´ıc´ı pozice jsou vˇzdy vyhr´avaj´ıc´ımi tahy. Pˇr´ıklad: (1) znaˇckovac´ım algoritmem z´ısk´ame, ˇze Subst[1, 3; 9] je N pozice a (2) G(Subst[1, 3; 9]) = 1. Hra se naz´yv´a N hra, pokud je v poˇc´ateˇcn´ı pozici N . Hra se naz´yv´ a P hra, pokud je v poˇc´ateˇcn´ı pozici P. Oba hr´aˇci hraj´ı racion´alnˇe a nedˇelaj´ı z´amˇernˇe chyby. Bude-li hr´aˇc v pozici N , budeme tak´e ˇr´ıkat, ˇze hr´aˇc vyhraje (existuje vyhr´avaj´ıc´ı strategie pro I. hr´aˇce). Z P pozice nem˚ uˇze v´est nˇejak´y vyhr´avaj´ıc´ı tah. Takˇze: v kombinatorick´ych hr´ach a t´ım i ve hr´ach s odeb´ır´an´ım kamen˚ u, jsou z jist´eho hlediska d˚ uleˇzit´e P pozice. Pokud naraz´ıme na nˇejakou N pozici, z t´eto pozice m˚ uˇze v´est i nˇekolik tah˚ u, ale vˇzdy alespoˇ n jeden tah do P pozice. Tento tah je tahem v´ıtˇezn´ym (spr´avn´ym tahem). Takov´y tah dostane protihr´aˇce do P pozice (pˇredch´azej´ıc´ı hr´aˇc m´a vyhr´avaj´ıc´ı strategii), ve kter´e bud’ jiˇz nen´ı ˇz´adn´y tah (koncov´a pozice) nebo vˇsechny tahy vedou pouze do N pozic, ve kter´y opˇet hr´aˇc uplatˇ nuje tuto strategii (n´asleduj´ıc´ı hr´aˇc m´a vyhr´avaj´ıc´ı strategii). Pˇr´ıklad: Hra Subst[1, 3; 9] je N hra, pozice Subst[1, 3; 6] je P pozice, protoˇze hr´aˇc m˚ uˇze zahr´at do pozic Subst[1, 3; 5], resp. Subst[1, 3; 3]. Obˇe dvˇe jsou N pozice. Napˇr´ıklad z druh´e pozice se m˚ uˇzeme dostat do nulov´e pozice Subst[1, 3; 3 − 3] odebr´an´ım tˇr´ı kamen˚ u. Pokud analyzujeme hru, obvykle se odvol´av´ame na prvn´ıho hr´aˇce (hr´aˇce, kter´y ve hˇre zaˇc´ın´a, otev´ır´a hru). Tak´e ho oznaˇcujeme jako hr´aˇce na tahu (n´asleduj´ıc´ı hr´aˇc). Jeho protihr´aˇc se naz´yv´a pˇredch´azej´ıc´ım hr´aˇcem. Tuto terminologii zav´ad´ıme z d˚ uvodu, ˇze nˇejak´a pozice ve hˇre mohla vzniknout pomoc´ı pˇredch´azej´ıc´ıch tah˚ u. Jedna poˇc´ateˇcn´ı pozice mohla vzniknout z nˇejak´e sloˇzitˇejˇs´ı hry jako moˇznost nˇejak´eho tahu. Napˇr´ıklad hra Subst[1, 3; 9] je moˇznost´ı ze hry Subst[1, 3; 9 + 1] po tahu – odebr´an´ı jednoho kamene. Hry s odeb´ır´an´ım pˇredmˇet˚ u m˚ uˇzeme studovat (ˇreˇsit) anal´yzou stromu hry. Ovˇsem tato metoda selh´av´a pro bohat´e stromy hry. Napˇr. hra Subst[1, 3; 39] je N hra, ale strom hry je pˇr´ıliˇs koˇsat´y.
4
Soustˇred’me se nyn´ı na vˇsechny hry s odeb´ır´an´ım pˇredmˇet˚ u. M˚ uˇzeme odeb´ırat s1 , s2 , . . . , sn kamen˚ u a budeme pˇredpokl´adat, ˇze 0 < s1 < s2 < · · · < sn . Oznaˇcen´ı pozic: Subst[S; 0], Subst[S; 1], Subst[S; 2], . . . potenci´alnˇe nekoneˇcn´e posloupnosti her. Pro kaˇzdou poˇc´ateˇcn´ı pozici 0, 1, 2, . . . stanov´ıme, zda se jedn´a o N nebo o P. Zaˇcneme od 0. Koncov´a pozice je vˇzdy P pozice. V kaˇzd´em kroku okamˇzitˇe oznaˇc´ıme pozice Subst[S; s1 ], Subst[S; s2 ],. . . ,Subst[S; sn ] jako N pozice, protoˇze jedn´ım tahem se dostaneme do pozice P. Vezme nyn´ı nejmenˇs´ı index i a uvaˇzujme neoznaˇcenou pozici Subst[S; i]. Tato pozice m˚ uˇze b´yt koncov´a (a je tedy P pozic´ı). Nebo z t´eto pozice vede tah, ale pouze do N pozice. Proto tuto pozici nazveme P pozic´ı. Odtud ale z´ısk´ame, ˇze vˇsechny pozice Subst[S; i + s1 ], Subst[S; i + s2 ], . . . , Subst[S; i + sn ] jsou tak´e N . (Jedn´ım tahem se dostaneme do P pozice). Metoda n´apadnˇe pˇripom´ın´a Eratosthenovo s´ıto. Zastavme se na chv´ıli: hled´ame-li okol´ı pozice, jedn´a se o koneˇcnou topologickou vlastnost. Hled´ame vlastnˇe bezprostˇredn´ıho n´asledovn´ıka, resp. pˇredch˚ udce (tj. dost´av´ame svaz). Vyˇsetˇrujeme-li koncovou pozici, pomoc´ı n´ı z´ısk´av´ame informace o vˇetˇs´ı a vˇetˇs´ı mnoˇzinˇe z´akladn´ıch postaven´ı, a to rekurzivnˇe. Hra Subst[S; k] je N hrou, pokud alespoˇ n jeden tah (odebr´an´ı kamen˚ u) k − s1 ,k − s2 ,. . . ,k − sj ,. . . ,k − sn je P pozice. Pozice Subst[S; k] je P, pokud k < s1 (koncov´a pozice, z hrom´adky nelze odebrat k´amen), nebo vˇsechny pozice Subst[S; k − s1 ], Subst[S; k − s2 ],. . . , Subst[S; k − sj ],. . . ,Subst[S; k − sn ] jsou N pozicemi. Pˇr´ıklad: Analyzujme hru Subst[3, 4; k]. Je-li k = 0, jedn´a se o koncovou pozici a ta je P pozic´ı. Potom pozice Subst[3, 4; 3] a Subst[3, 4; 4] jsou N pozicemi. Vezmˇeme k = 1. Pozice Subst[3, 4; 1] je P pozice, protoˇze z hrom´adky s jedn´ım kamenem nem˚ uˇzeme odebrat stanoven´y poˇcet kamen˚ u. Tak´e pro k = 2 dost´av´ame P pozici. Dalˇs´ı ˇc´ıslo je k = 5. tato pozice je N , protoˇze mj. staˇc´ı odebrat 4 kameny. Z pozice Subst[3, 4; 5] nen´ı tah do P pozice. Pozice Subst[3, 4; 6] je tak´e N pozic´ı. Pˇr´ıklad: Analyzujme hru Subst[1, 3, 4; k]: k P/N
0 P
1 N
2 P
3 N
4 N
5 N
... ...
Pozice Subst[1, 3, 4; 0] je P pozice (nulov´a), z pozice Subst[1, 3, 4; 1] jedn´ım tahem se dostaneme do P pozice a tedy tato pozice je N . Z pozice Subst[1, 3, 4; 2] se jedn´ım tahem m˚ uˇzeme dostat pouze do N pozice a proto je tato pozice P. Oznaˇcme koncovou pozici znakem 0. N´asleduj´ıc´ı pozice budeme oznaˇcovat kladn´ym ˇc´ıslem, kter´e je nejmenˇs´ı z ˇc´ısel, kam se jiˇz jedn´ım tahem nedostaneme. Konkr´etnˇe hodnota k = 1 bude jedna, protoˇze se muˇzeme jedn´ım tahem dostat do 0. Hodnota pro k = 2 je ale opˇet nulovou, protoˇze se m˚ uˇzeme dostat pouze do pozice 1. Pozice k = 3 m´a hodnotu 1, ale pozice k = 4 m´a hodnotu 2, protoˇze jedn´ım tahem se dostaneme do pozic, kter´e jsou oznaˇceny 0, 1. k P/N
0 P
mex
0
1 N 0 1
2 P 1 0
3 4 N N 0,0 1,0 1 2 5
5 6 7 ... N N P 2,0,1 3,1,0 2,2,1 3 2 0 ...
Nech´a se oˇcek´avat, ˇze posloupnost N a P bude periodick´a, resp. lze vyslovit hypot´ezu, ˇze posloupnost pozic hry {0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, . . .} je periodick´a a hypot´ezu dok´azat matematickou indukc´ı. Tato vlastnost je spoleˇcn´a vˇsech hr´am s odeb´ır´an´ım pˇredmˇet˚ us koneˇcnou mnoˇzinou {s1 , s2 , . . . , sn }. Pˇr´ıklad: Vrat’me se k anal´yze hry Subst[3, 4; k]. Stejn´ym zp˚ usobem pomoc´ı nejbliˇzˇs´ıho ” okol´ı“ pozice z´ısk´ame tabulku:
k=
P P P N N 0 1 2 3 4 7 8 9 10 11 14 15 16 17 18 21 22 23 24 25
N 5 12 19 25
N 6 13 20 27
Kaˇzd´e pozici ve hˇre s odeb´ır´an´ım pˇredmˇet˚ u m˚ uˇzeme pˇriˇradit ˇc´ıslo, kter´e budeme naz´yvat Grundyovou hodnotou. Oznaˇcme N = {0, 1, 2, . . .} a Z = {. . . , −2, −1, 0, 1, 2, . . .}. Uvaˇzujme hru s odeb´ır´an´ım kamen˚ u Subst[s1 , s2 , . . . , sn ; k]. Oznaˇcme S = {s1 , s2 , . . . , sn }. Oznaˇc´ıme G(0) = 0 a G(k) = −1 pro z´aporn´a cel´a ˇc´ısla k. Potom pro kaˇzd´e kladn´e ˇc´ıslo m oznaˇc´ıme Sk = {u ∈ N; u = G(k − sj ), pro vˇsechnaj = 1, 2, . . . , n}. Mnoˇzina Sk je mnoˇzinou nez´aporn´ych ˇc´ısel. G(k − s1 ), G(k − s2 ), . . . , G(k − sn ). Definujeme G(k) = min(N \ Sk ). G je posloupnost G : N → N, takov´a, ˇze G(k) je nez´aporn´e pro nez´aporn´e k. Tato posloupnost se naz´yv´a Grundyova posloupnost. Pˇr´ıklad: Vrat’me se k anal´yze hry Subst[3, 4; k] a spoˇc´ıtejme hodnoty posloupnosti G(k). k G(k − 3) G(k − 4) Sk N − Sk G(k)
0 −1 −1 ∅ N 0
1 −1 −1 ∅ N 0
2 −1 −1 ∅ N 0
3 0 −1 {0} {1, 2, . . .} 1
4 5 0 0 {0} {1, 2, . . .} 0 ...
Obecnˇe dostaneme: G(7k) = G(7k + 1) = G(7k + 2) = 0, G(7k + 3) = G(7k + 4) = G(7k + 5) = 1, G(7k + 6) = 2.
NIM Hru Nim hraj´ı dva hr´aˇci (L a R, resp. I. a II. hr´aˇc), stˇr´ıdavˇe odeb´ıraj´ı kameny z nˇekolika hrom´adek. Ve sv´em tahu mus´ı vˇzdy odebrat nejm´enˇe jeden k´amen, ale vˇzdy pouze z jedn´e hrom´adky. Hr´aˇc, kter´y udˇelal posledn´ı pravidly povolen´y tah, vyhr´al, protoˇze hr´aˇc na tahu jiˇz nem˚ uˇze t´ahnout (na hrom´adce nejsou kameny). ´ ch ˇ ´ n´ım pr ˇ edmˇ Tak jako v pˇr´ıpadˇe Dawsonovy sach˚ u a nebo Her s odeb´ıra et˚ u, hra Nim m´a n´asleduj´ıc´ı vlastnosti: 6
1. 2. 3. 4. 5.
hru hraj´ı dva hr´aˇci. ve hˇre je nˇekolik (zpravidla koneˇcn´y) poˇcet pozic a jedna pozice poˇc´ateˇcn´ı, hr´aˇci se v taz´ıch stˇr´ıdaj´ı, dokud nedos´ahnou koncov´e pozice, v norm´aln´ı variantˇe hry, hr´aˇc, kter´y udˇel´a posledn´ı tah, vyhr´al. Pravidly hry je zaruˇceno, ˇze vˇzdy po koneˇcnˇe mnoha taz´ıch dojde ke koncov´e situaci, pravidla nepˇripouˇst´ı pat a ani rem´ızu (opakov´an´ı tah˚ u a pod.). 6. Oba hr´aˇci vˇzdy znaj´ı vˇsechny moˇzn´e tahy a pozice, ˇz´adnou roli zde nehraje n´ahoda. ´ n´ım pr ˇ edmˇ Dawsonovy ˇ sachy, Hry s odeb´ıra et˚ u a hry Nim splˇ nuj´ı n´asleduj´ıc´ı podm´ınku: 7. Pravidla hry nerozliˇsuj´ı mezi hr´aˇci. To znamen´a tah z dan´e pozice, kter´y m˚ uˇze udˇelat jeden z hr´aˇc˚ u, m˚ uˇze tak´e udˇelat druh´y hr´aˇc. Z´aleˇz´ı jen na tom, kter´y z hr´aˇc˚ u je pr´avˇe na tahu. Takov´e kombinatorick´e hry se naz´yvaj´ı nestrann´e. Pozici s n hrom´adkami a s poˇctem kamen˚ u p1 , p2 , . . . , pn oznaˇc´ıme Nim[p1 , p2 , . . . , pn ]. Na poˇrad´ı p1 , p2 , . . . , pn nez´aleˇz´ı. Takˇze napˇr´ıklad pozice Nim[p1 , p2 , p3 , . . . , pn ] je stejn´a, jako pozice Nim[p2 , p1 , p3 , . . . , pn ]. Obvykle budeme pˇredpokl´adat, ˇze na kaˇzd´e hrom´adce v poˇc´ateˇcn´ı pozici je alespoˇ n jeden k´amen. Takˇze napˇr´ıklad pozice Nim[n, 0] je stejn´a jako pozice Nim[n]. Pozice, na kter´e nen´ı jiˇz ˇz´adn´a hrom´adka, se oznaˇcuje 0. Budeme tedy pˇredpokl´adat, ˇze hra zaˇc´ın´a z nˇejak´e pozice Nim[p1 , p2 , p3 , . . . , pn ]. Pˇr´ıklad: Uvaˇzujme tˇreba pozici Nim[2, 2]. Prvn´ım tahem s hr´aˇc m˚ uˇze dostat do pozice Nim[2, 1] nebo Nim[2, 0]. Z pozice Nim[2, 1] se hr´aˇc m˚ uˇze dostat do pozice Nim[2, 0], Nim[1, 1] nebo Nim[0, 1]. Z pozice Nim[2, 0], tj. Nim[2] se hr´aˇc m˚ uˇze dostat do pozic Nim[1] nebo Nim[0]=0, atd. Pozice Nim[2, 2] je P pozice. Protoˇze at’ zahraje I. hr´aˇc jakkoliv, II. hr´aˇc ve druh´e hrom´adce m˚ uˇze vˇzdy zahr´at stejn´y tah. Pozice Nim[3, 2] je naopak jistˇe N pozic´ı, protoˇze alespoˇ n jeden prvn´ı tah vede do P pozice (a t´ım je pr´avˇe pozice Nim[2, 2]). Hru Nim m˚ uˇzeme analyzovat stejn´ymi prostˇredky jako hry Dawsonovy ˇ sachy, nebo ´ ´ ´ ˚ Hry s odebıranım kamenu. Podotknˇeme, ˇze opˇet sestrojen´ı stromu hry m˚ uˇze b´yt nˇekdy komplikovan´e. ´ Uloha: Uvaˇzujme n´asleduj´ı pozice ve hˇre Nim. 1. Nim[2, 3, 7, 5, 6] 2. Nim[23, 7, 56] 3. Nim[1, 2, 4, 8, 16] Zjistˇete, zda pozice hry je N . Pokud dan´a pozice je N , urˇcete vˇsechny vyhr´avaj´ıc´ı tahy! ´ Uloha: Uvaˇzujme n´asleduj´ıc´ı hry Nim na jedn´e hrom´adce se 14 kameny s omezen´ım moˇzn´ych tah˚ u. 1. Nim[1, 4, 7; 14] 2. Nim[1, 2, 3, 4, 7; 14] 3. Nim[3, 4, 6; 14]
7
Pro kaˇzdou hru urˇcete (a) N a P pozice. Pokud je hra v N pozici, (b) popiˇste vyhr´avaj´ıc´ı strategii. Urˇcete tak´e (c) Grundyovy hodnoty vˇsech pozic. Boutonova metoda (1902): Na t´eto metodˇe si uk´aˇzeme, proˇc nen´ı v´yhodn´e studovat nestrann´e hry pomoc´ı strom˚ u (pˇr´ıliˇs mnoho moˇznost´ı, strom je nepˇrehledn´y). Pˇr´ıklad: Zkuste si nˇekolik poˇc´ateˇcn´ıch pozic ve hˇre Nim[1, 3, 5, 6, 45] a pod.
´n´ı Hry Cram a Dominova Obˇe hry maj´ı podobn´a pravidla. Dva hr´aˇci stˇr´ıdavˇe pokl´adaj´ı kostky domina 2 × 1 a 1 × 2 na pol´ıˇcka ˇsachovnice m × n. Kostky se nesmˇej´ı pˇrekr´yvat. Hr´aˇc, kter´y poloˇzil posledn´ı kostku, vyhr´al (hr´aˇc, kter´y jiˇz nem˚ uˇze poloˇzit kostku, prohr´al). Pokud nen´ı ˇz´adn´e omezen´ı na orientaci kostek, hra se naz´yv´a Cram. Pokud lev´y hr´aˇc m˚ uˇze pokl´adat pouze kostky ´ n´ı. vertik´alnˇe a prav´y hr´aˇc horizont´alnˇe, hra se naz´yv´a Dominova Pˇr´ıklad: Moˇzn´a partie m˚ uˇze vypadat tˇreba takto:
,
,
, atd.
´ n´ım kamen˚ Tak jako ve hr´ach Dawsonovy ˇ sachy, Hry s odeb´ıra u a hry Nim, 1. 2. 3. 4. 5.
hru hraj´ı dva hr´aˇci, ve hˇre je nˇekolik (zpravidla koneˇcn´y) poˇcet pozic a jedna pozice poˇc´ateˇcn´ı, hr´aˇci se v taz´ıch stˇr´ıdaj´ı, dokud nedos´ahnou koncov´e pozice, v norm´aln´ı variantˇe hry, hr´aˇc, kter´y udˇel´a posledn´ı tah, vyhr´al. Pravidly hry je zaruˇceno, ˇze vˇzdy po koneˇcnˇe mnoha taz´ıch dojde ke koncov´e situaci, pravidla nepˇripouˇst´ı pat a ani rem´ızu (opakov´an´ı tah˚ u a pod.). 6. Oba hr´aˇci vˇzdy znaj´ı vˇsechny moˇzn´e tahy a pozice, ˇz´adnou roli zde nehraje n´ahoda. ´ n´ım kamen˚ Tak jako Dawsonovy ˇ sachy, Hry s odeb´ıra u a hry Nim, i hra Cram je nestrann´a, tj. plat´ı 7. Pravidla hry nerozliˇsuj´ı tahy obou hr´aˇc˚ u. Z dan´e pozice vˇsechny dostupn´e tahy jednoho z hr´aˇc˚ u jsou i moˇznostmi druh´eho hr´aˇce, a to v kaˇzd´e pozici. Z´aleˇz´ı jen na tom, kter´y z hr´aˇc˚ u zaˇc´ın´a. ´ n´ı tuto posledn´ı podm´ınku nesplˇ Hra Dominova nuje, je pˇr´ıkladem tzv. partyz´ ansk´e hry. Budeme nejdˇr´ıve analyzovat hru Cram stejn´ymi prostˇredky, jako hry Dawsonovy ˇ ´ n´ım kamen˚ sachy, hry s odeb´ıra u a hry Nim. Kaˇzdou pozici ve hˇre budeme oznaˇcovat P nebo N pozic´ı. Pˇr´ıklad: Uvaˇzujme napˇr´ıklad hru Cram na ˇsachovnici 2 × 3 jako na obr´azku . V prvn´ım tahu je moˇzn´ych celkem sedm moˇzn´ych pozic. V druh´em tahu je celkem 22 moˇzn´ych pozic, a z tˇechto pozic je jeˇstˇe moˇzn´ych dalˇs´ıch 18 moˇznost´ı (sestrojte si strom hry). Protoˇze nˇekter´e pozice se opakuj´ı a jin´e jsou symetrick´e, budeme radˇeji kreslit reprezentanty zaj´ımav´ych postaven´ı, tj. v prvn´ım tahu tˇri moˇznosti , a , atd. Situaci si jeˇstˇe m˚ uˇzeme ulehˇcit, budeme-li zakreslovat pouze pole, kam jeˇstˇe m˚ uˇzeme pˇri tahu poloˇzit kostku domina, tj. z pozice prvn´ım tahem lze z´ıskat pouze pozice: ,
a
. Stejn´e pozice nebudeme kreslit v´ıcekr´at a tak postupnˇe z´ısk´ame graf
hry. 8
dostaneme, ˇze hra je N . Otoˇcen´a hra
Anal´yzou hry
tahem v t´eto hˇre je tah rozdˇelen´ı na
=
je naopak P hra. Vyhr´avaj´ıc´ım
.
´ Uloha: Zjistˇete u nˇejak´ych jednoduch´ych pozic, zda se jedna o P nebo N pozici. Napˇr. ,
,
napˇr.
,
,
,
,
nebo
,
,
. Vˇsechny pozice se 4 nebo 5 ˇctvereˇcky,
. Pokuste se vyslovit nˇejak´e obecnˇejˇs´ı vˇety pro pravo´ uheln´ıky.
Pozice N a P m˚ uˇzeme tak´e urˇcit pomoc´ı Grundyov´ych hodnot. Grundyova posloupnost hry Cram je rekurzivnˇe definov´ana jako GCram : C → N, kde mnoˇzina C je mnoˇzina vˇsech pozic ve hˇre Cram a mnoˇzina N je mnoˇzina vˇsech nez´aporn´ych cel´ych ˇc´ısel. GCram je definov´ana takto: GCram (·) = 0 (kdyˇz nejde poloˇzit kostku domina) a pro kaˇzdou pozici X ve hˇre Cram je: GCram (X) = min(N \ {GCram (Y1 ), GCram (Y2 ), . . . , GCram (Yk )}), kde Y1 , Y2 , . . . , Yk jsou vˇsechny moˇzn´e pozice, kter´e je moˇzn´e dos´ahnout jedn´ım tahem z pozice X. Pˇr´ıklad: GCram ( ) = 0; GCram (
) = GCram (
) = · · · = 0. GCram ( ) = 1 (jedn´ım
tahem se dostaneme do hry 0). GCram ( ) = 1, protoˇze jedn´ım tahem se dostaneme do pozice (hry)
, kter´a m´a GCram hodnotu 0.
her
, kter´e maj´ı hodnotu −1 a 0. I GCram hodnota hry
,a
= −2, prvn´ım tahem se dostaneme do
´ Uloha: Urˇcete GCram hodnoty tˇechto pozic ve hˇre Cram: ,
,
,
,
,
,
Jin´ym pˇr´ıkladem jsou pozice: GCram ( atd.
= 2. GCram ( ,
,
) = 0. ,
,
. ) = 0, GCram (
) = 1, GCram (
) = 1,
´ n´ı se liˇs´ı od hry Cram tak, ˇze nˇejak´e pozice mohou b´yt dostupn´e jednomu Hra Dominova z hr´aˇc˚ u, ale druh´emu ne. Napˇr´ıklad pozice pozice, pozice
a
a
, nebo pozice
a
jsou stejn´e
jsou r˚ uzn´e.
´ ´ n´ı v pozic´ıch Uloha: Hrajte hru Dominova
,
. Sestrojte grafy a proved’te anal´yzu.
Tak jako ale u pˇredch´azej´ıc´ı her, m˚ uˇzeme sestrojovat graf hry a strom hry pro oba hr´aˇce, vˇzdy ale s vyznaˇcen´ım pˇr´ısluˇsn´eho hr´aˇce (dostupn´e pozice pro lev´eho a prav´eho hr´aˇce ´ zvl´aˇst’). Umluvou je d´ano, ˇze lev´y hr´aˇc pokl´ad´a kostky domina vertik´alnˇe a prav´y hr´aˇc horizont´alnˇe. V grafech tahy lev´eho se vˇzdy kresl´ı modrou barvou (bLue) a tahy prav´eho ˇcervenou barvou (Red). V´ysledn´e tˇr´ıdy (v´ysledky) ve hr´ach (pozic´ıch) v partyz´ansk´ych her:
9
Fazy Nulov´e Kladn´a Z´aporn´a Napˇr´ıklad hra
N P L R
1 2 L R
je z´aporn´a.
Hry a ˇ c´ısla Tak jako v pˇr´ıpadˇe nestrann´ych her, m˚ uˇzeme pˇriˇrazovat hodnoty pozic´ım v partyz´ansk´ych hr´ach. Ohodnocen´ı pozic n´am pom˚ uˇze ve hˇre naj´ıt vyhr´avaj´ıc´ı strategii. Uk´aˇzeme, jak ´ n´ı, ale obecn´y princip je aplikovateln´y na ostatn´ı pˇriˇrazovat hodnoty ve hˇre Dominova hry. Nejdˇr´ıve nˇekter´e pozice ohodnot´ıme obvykl´ymi ˇc´ısly, pozdˇeji budeme potˇrebovat i jin´a ˇc´ısla. Nejdˇr´ıve vyˇsetˇr´ıme pozici, ve kter´e nen´ı moˇzn´y ˇz´adn´y tah. Takov´e (nulov´e) pozici pˇriˇrad´ıme symbol 0. Z t´eto pozice ˇz´adn´y prvn´ı hr´aˇc nem´a vyhr´avaj´ıc´ı strategii, naopak, v t´eto hˇre existuje vyhr´avaj´ıc´ı strategie pro II. hr´aˇce. Pozice, ve kter´ych existuje vyhr´avaj´ıc´ı stra´ n´ı jsou to pozice tegie pro druh´eho hr´aˇce budeme naz´yvat nulov´e hry. Ve hˇre Dominova napˇr´ıklad , nebo , atd. ´ n´ı v pozici Ve hˇre Dominova
m´a vyhr´avaj´ıc´ı strategii lev´y hr´aˇc. Lev´y hr´aˇc m´a jeden
prvn´ı tah do pozice (0, nulov´e). Prav´y hr´aˇc v t´eto hˇre nem´a pravidly povolen´y tah. Dohodneme se, ˇze takovou hru budeme oznaˇcovat {0 |}. V lev´e ˇc´asti p´ıˇseme moˇzn´e tahy lev´eho hr´aˇce, a do prav´e ˇc´asti zap´ıˇseme moˇzn´e tahy prav´eho hr´aˇce. Lev´y hr´aˇc m´a v t´eto pozici v´yhodu jednoho tahu a proto hodnotu hry {0 |} oznaˇc´ıme 1. Pozici oznaˇc´ıme −1. V t´eto pozici existuje vyhr´avaj´ıc´ı strategie pro prav´eho hr´aˇce, a nez´aleˇz´ı na tom, jak zahraje lev´y hr´aˇc. Hodnota t´eto hry je {| 0} = −1, protoˇze pouze prav´y hr´aˇc m˚ uˇze t´ahnout do hry o hodnotˇe 0. Pouˇzijeme-li stejn´e argumenty, ohodnot´ıme tak´e hry Analyzujme situaci zahr´at do hry
=1a
= −1.
a hledejme jej´ı hodnotu. Lev´y hr´aˇc m´a na v´ybˇer dva moˇzn´e tahy,
nebo do hry
. Hodnoty tˇechto her jsou 1 a 0. Hru
oznaˇc´ıme {0, 1 |},
resp. 2 (v´yhoda pro lev´eho dvou tah˚ u ). Prav´y hr´aˇc v t´eto hˇre nem´a pravidly povolen´y tah. Analogicky pozice = {| 0, −1} = −2 (prav´y hr´aˇc m´a v´yhodu dvou tah˚ u). Co m˚ uˇzeme ˇr´ıct o pozici
? V t´eto pozici prav´y hr´aˇc m´a tak´e v´yhodu dvou tah˚ u, lev´y
hr´aˇc nem˚ uˇze t´ahnout. Oznaˇc´ıme tuto hru {| −1, −1} = {| −1} = −2. Pouˇzijeme-li sˇc´ıt´an´ı her, dost´av´ame −1 + (−1) = −2. Podobnˇe pozice
10
m´a hodnotu {1, 1 |} = {1 |} = 2.
Hru zap´ıˇseme {−1 | 1}. Lev´y hr´aˇc m˚ uˇze zahr´at do hry o hodnotˇe −1 a prav´y hr´aˇc do 1. V t´eto hˇre existuje vyhr´avaj´ıc´ı strategie pro II. hr´aˇce a proto tuto hru oznaˇc´ıme tak´e 0. Prvn´ı hr´aˇc zahraje sv˚ uj tah a prohraje. Pod´ıv´ame-li se jeˇstˇe jednou na v´ychoz´ı pozici, m˚ uˇzeme ji tak´e oznaˇcit +1 + (−1) = 0, protoˇze pozice odpov´ıdaj´ı 1 a −1. Pozice
,
umoˇzn ˇ uj´ı lev´emu dostat se jedn´ım tahem do pozice
. Proto i tyto pozice
budeme znaˇcit {1 |} = 2. Podobnˇe pozice = −2. Uvˇedomte si, ˇze napˇr´ıklad pozice je pozice 2 + (−2) = 0 a v t´eto hˇre existuje vyhr´avaj´ıc´ı strategie pro II. hr´aˇce. Pro hru tedy dostaneme 2 = {1, 1 |} = {1, 0 |}. A podobnˇe −2 = {| −1, −1} = {| −1, 0}. Hru zap´ıˇseme jako {| −2, −2, −1} a oznaˇc´ıme ji symbolem −3. Otoˇcenou hru oznaˇc´ıme {2, 2, 1 |} = 3. Vyˇsetˇr´ıme jeˇstˇe pozici
. Moˇznosti tah˚ u hr´aˇc˚ u jsou {−1, 0 | 1}. Ot´azkou je, jak´e ˇc´ıslo
pˇriˇrad´ıme t´eto hˇre. Jistˇe je v t´eto hˇre lev´y ve v´yhodˇe (hra bude kladn´a). Vyˇsetˇr´ıme-li hru ˇce). Proto hˇre
, zjist´ıme, ˇze hra je nulov´a (existuje vyhr´avaj´ıc´ı strategie pro II. hr´apˇriˇrad´ıme hodnotu 1/2. (Protoˇze 1/2 + 1/2 + (−1) = 0.) Hodnotu
hry m˚ uˇzeme tak´e zapsat 1/2 = {−1, 0 | 1}. Podobnˇe hodnota hry {1 | 0, −1} a pˇriˇrad´ıme ji hodnotu −1/2.
zap´ıˇseme jako
Obecnˇe: Budeme-li v pozici G a moˇzn´e tahy lev´eho jsou do her H1 , H2 , . . . , Hm , moˇznosti tah˚ u prav´eho budou tˇreba K1 , K2 , . . . , Kn a vˇsechny hodnoty H1 , H2 , . . . , Hm ,K1 , K2 , . . . , Kn jsou ˇc´ısla (hodnoty pozic), budeme ps´at G = {H1 , H2 , . . . , Hm | K1 , K2 , . . . , Kn }. M˚ uˇze se ′ st´at, ˇze tak´e nˇejak´a jin´a hra G m´a stejnou hodnotu {H1 , H2 , . . . , Hm | K1 , K2 , . . . , Kn }. 1. Kaˇzdou P pozici oznaˇc´ıme znakem 0. 2. Kaˇzdou L pozici oznaˇc´ıme kladn´ym ˇc´ıslem, pokud hodnota hry bude ˇc´ıslo. 3. Kaˇzdou R pozici pˇriˇrad´ıme z´aporn´e ˇc´ıslo, pokud je hˇre pˇriˇrazeno ˇc´ıslo. Obecnˇe L a R pozice nemus´ı nutnˇe pˇriˇrazovat hˇre ˇc´ısla, ale informuje n´as o tom, kdo ve hˇre vyhraje a zda je hra kladn´a, resp. z´aporn´a. 4. Pokud dvˇe pozice jsou opaˇcn´e, jejich hodnota bude tak´e opaˇcn´a a jejich souˇctem vˇzdy bude 0 (P pozice, existuje vyhr´avaj´ıc´ı strategie pro II. hr´aˇce). Uvaˇzujme pozici . Tato pozice je N pozice, existuje vyhr´avaj´ıc´ı strategie pro I. hr´aˇce. Pokud prvn´ı hr´aˇc v t´eto hˇre zahraje, dostane se do hry , jej´ıˇz hodnota je 0 (nulov´a hra). Tedy hru zap´ıˇseme jako {0 | 0} a pˇriˇrad´ıme ji (nadre´alnou) hodnotu ∗. T´eto hˇre nem˚ uˇzeme pˇriˇradit hodnotu 0, protoˇze ve hˇre ∗ existuje vyhr´avaj´ıc´ı strategie pro I. hr´aˇce. Struˇcnˇe budeme ˇr´ıkat, ˇze hra {0 | 0} m´a hodnotu ∗ (star, hvˇezdiˇcka). Pozice + je N pozice, tedy ∗ + ∗ = 0. Budeme jeˇstˇe analyzovat pozici (hru) {0, ∗ | ∗} a hru oznaˇc´ıme ↑. Hra
. Tato hra je L. Moˇznosti tah˚ u zap´ıˇseme jako m´a hodnotu ↑. Opaˇcn´a hra
11
m´a hodnotu
{∗ | 0, ∗}. Tuto hodnotu budeme oznaˇcovat ↓, a plat´ı ↑ + ↓ = 0. Obecnˇe hr´am typu N , P , R , L pˇriˇrazujeme jejich (nadre´alnou) hodnotu tvaru {H1 , H2 , . . . , Hm | K1 , K2 , . . . , Kn }, kde Hi a Ki maj´ı vˇsechny tak´e (nadre´alnou) hodnotu. Nadre´aln´a hodnota nemus´ı b´yt obvykl´e ˇc´ıslo. Pozice mohou b´yt kladn´e, nebo z´aporn´e. Napˇr´ıklad ve hˇre oznaˇcen´e ∗ existuje vyhr´avaj´ıc´ı strategie pro I. hr´aˇce. Hra m˚ uˇze b´yt kladn´a (napˇr. ↑), z´aporn´a (napˇr. ↓). R˚ uzn´e hry mohou m´ıt stejnou (nadre´alnou) hodnotu. ˇ ste hru Dominova ´ ´ n´ı na ˇsachovnic´ıch 3 × 3, 4 × 4, 6 × 4 nebo 6 × 6. Uloha: Reˇ ————————
[2hs03RMF actual 0ugb.tex, 08/01/14, 16:18]
12
