Kombinatorická teória hier: definícia, pravidlá a príklady
Objavte kombinatorickú teóriu hier (CGT): definície, pravidlá, príklady, riešenia pre Nim, súčty hier a história Conwaya, Berlekampa a Guya pre pochopenie rozhodovacích stratégií.
Kombinatorická teória hier (CGT) je odvetvie matematiky a teoretickej informatiky, ktoré sa zaoberá analýzou deterministických, postupných a informovaných hier bez náhody. Odlišuje sa od "tradičnej" alebo "ekonomickej" teórie hier tým, že sa sústreďuje na štruktúru a riešenie konkrétnych diskretných hier (často abstraktných), nie na stratégie v prostredí s neistotou alebo zmiešanými stratégiami. CGT historicky vznikla zo štúdií nestranných hier, najmä klasyckej úlohy Nim, a kladie dôraz na klasifikáciu hier, výpočet ich hodnôt a operáciu sčítania hier.
Podmienky, ktoré definujú kombinatorickú hru
Aby sa nejaká hra považovala za kombinatorickú podľa bežných formalizácií, musí spĺňať niektoré základné podmienky. Sú to (v skrátenej podobe):
- V hre musia byť aspoň dvaja hráči (zvyčajne práve dvaja).
- Hra je postupná – hráči sa striedajú v ťahoch.
- Hra má dokonalé informácie: všetky súčasné informácie o pozícii sú k dispozícii obom hráčom (na rozdiel od pokru a pod.). V texte pôvodne odkazované ako podmienok.
- Hra je deterministická – Šťastie alebo náhodné udalosti nie sú súčasťou pravidiel.
- Počet možných ťahov v každom momente aj celkový stavový priestor sú (zvyčajne) konečné.
- Hra sa nakoniec musí skončiť (nie sú povolené nekonečné sekvencie ťahov bez ukončenia).
- Hra končí, keď hráč nemôže vykonať žiadny platný ťah – v klasických modeloch to vedie k víťazovi a porazenému (bez remízy), hoci existujú aj varianty so remízami.
Základné pojmy a klasifikácia
V CGT sa rozlišujú dve dôležité kategórie hier:
- Nestranné (impartial) hry: dostupné ťahy závisia iba od pozície a nie od toho, kto je na tahu. Nim je typickým príkladom.
- Partizánske (partizan) hry: obidvaja hráči majú často rozdielne množiny dostupných ťahov z rovnakej pozície (príklady: Hackenbush, rôzne verzie šachových úloh).
Existujú tiež dve bežné konvencie ukončenia hry:
- Normálna hra – ten, kto nemá ťah, prehráva.
- Misère hra – ten, kto nemá ťah, vyhráva (takéto pravidlo mení analýzu a často komplikuje riešenie).
Reprezentácia hier a riešenie
Kombinatorické hry sa zvyčajne reprezentujú ako strom rozhodnutí (herný strom), kde každý vrchol reprezentuje pozíciu a hrany predstavujú ťahy k novým pozíciám. Analytici CGT hľadajú pre každú pozíciu tzv. hernú hodnotu alebo inú kanonickú reprezentáciu, ktorá umožňuje určiť, či je pozícia výherná alebo prehry pre hráča na ťahu a ako kombinačne reagujú dve alebo viac súbežných hier.
Pri nestranných hrách hrá kľúčovú úlohu Sprague–Grundyova veta, ktorá priradí každej pozícii tzv. nimové číslo (nimber). Nimbery sa kombinujú pomocou bitového XOR pri súčte nezávislých nestranných hier – ak je celkový XOR nulový, pozícia je P-pozícia (predvídateľná pre prehru hráča na ťahu), inak N-pozícia (výherná).
Sčítanie hier a hodnoty hier
Typická operácia v CGT je sčítanie dvoch (alebo viacerých) hier: súčet hier G + H je hra, v ktorej v každom ťahu hráč vykoná ťah v jednej z komponentných hier a ostatné komponenty zostanú nezmenené. Táto operácia je základom pre štúdium kombinácií nezávislých subhier a vedie k algebraickým štruktúram hodnôt hier.
Pre partizánske hry John Conway vyvinul rozsiahlu teóriu hodnôt hier vrátane pojmu surreal numbers (surreálne čísla) a širšej triedy herných hodnôt, ktoré môžu byť nie len číslami, ale aj komplexnejšími objektmi (tzv. games). Tieto hodnoty sa dajú sčítavať a porovnávať a pomáhajú rozhodovať optimálne ťahy, najmä pri kombináciách rôznych typov pozícií.
Príklady a ilustrácie
Najznámejším príkladom je Nim, kde sa hrá s niekoľkými kopami predmetov a v každom ťahu hráč odoberie ľubovoľný počet predmetov z jednej kopy. Sprague–Grundyova analýza ukazuje, že pozícia je výherná práve vtedy, ak XOR veľkostí všetkých kôp je nerovný nule. Pre demonštráciu: pozícia s kôpami (3, 4, 5) má XOR = 3 XOR 4 XOR 5 = 2, teda je výherná pre hráča na ťahu.
Ďalšie bežné príklady: Kayles, posúvanie kameňov na grafe, Hackenbush (majúci partizánske prvky), a množstvo puzzle-hier, ktoré sa dajú analyzovať pomocou CGT techník.
Zložitosť a výpočtové aspekty
Mnohé otázky v CGT sú algoritmicky náročné: rozhodovanie, či daná pozícia má výhernú stratégiu, môže byť ťažké. Pre všeobecné pravidlá hier podobných šachu a mnohým iným kombinatorickým hrám sú rozhodovacie problémy často PSPACE-úplné. Napriek tomu existujú silné štrukturálne výsledky (napr. Sprague–Grundyova veta pre nestranné hry), ktoré poskytujú efektívne metódy riešenia pre širokú triedu hier.
Význam a aplikácie
CGT má viacero teoretických i praktických aplikácií: v teórii algoritmov (analýza herných stromov), pri návrhu silných heuristík pre počítačové programy v hrách, v kombinatorike a pri tvorbe matematických hádaniek. Okrem toho CGT rozvíja elegantné matematické objekty (nimbery, súčty hier, surreálne čísla), ktoré majú zaujímavé spojenia s inými oblasťami matematiky.
Krátka história a literatúra
Rozvoj modernej kombinatorickej teórie hier je pripisovaný najmä pracám Elwyn Berlekamp, John Conway a Richard Guy, ktorí v 60. rokoch 20. storočia významne rozšírili oblasť a neskôr spolu zverejnili rozsiahlu prácu nazvanú Víťazné spôsoby pre vaše matematické hry (Winning Ways for your Mathematical Plays). Táto kniha spolu so základnými článkami Conwaya položila základy modernej algebraickej a kombinatorickej analýzy hier.
Pre ďalšie štúdium odporúčam vyhľadať literatúru venovanú Sprague–Grundyovej teórii, partizánskym hrám, surreálnym číslam a špecializovaným monografiám o jednotlivých hrách (Nim, Hackenbush, Kayles a pod.).
Definície
V teórii sú dvaja hráči nazývaní ľavá a pravá strana. Hra je niečo, čo umožňuje ľavici a pravici vykonávať ťahy do iných hier. Napríklad v šachovej hre existuje zvyčajné východiskové rozostavenie. O šachovej hre by sa však dalo uvažovať aj po prvom ťahu ako o inej hre s iným nastavením. Každá pozícia sa teda tiež nazýva hra.
Hry majú zápis {L|R}. L {\displaystyle L}
sú hry, do ktorých sa môže ľavý hráč presunúť. R {\displaystyle R}
sú hry, do ktorých sa môže presunúť pravý hráč. Ak poznáte šachovú notáciu, potom je obvyklým šachovým usporiadaním hra
| { 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 \}} |
Bodky "..." znamenajú, že je veľa ťahov, preto nie sú zobrazené všetky.
Šach je veľmi zložitý. Je lepšie myslieť na jednoduchšie hry. Napríklad Nim je oveľa jednoduchší. Nim sa hrá takto:
- Existuje nula alebo viac hromádok počítadiel.
- V jednom ťahu si hráč môže vziať z jednej hromádky toľko žetónov, koľko chce.
- Hráč, ktorý nemôže vykonať ťah, prehráva.
Najjednoduchšia hra Nim začína bez počítadiel! V takom prípade sa ani jeden z hráčov nemôže pohnúť. To je znázornené ako {|}. Obe strany sú prázdne, pretože ani jeden z hráčov sa nemôže pohnúť. Prvý hráč, ktorý sa pohne, sa nemôže pohnúť, a preto prehrá. V CGT sa často píše {|} ako symbol 0 (nula).
Ďalšia najjednoduchšia hra má len jednu hromádku s jedným počítadlom. Ak ide ľavý hráč ako prvý, musí si vziať počítadlo, pričom pravý hráč nemá žiadny ťah ({|} alebo 0). Ak namiesto toho pravý ťahá ako prvý, ľavý už nebude mať žiadne ťahy. Ľavý aj pravý hráč teda môžu urobiť ťah na 0. Ten sa zobrazí ako {{|}|{|}}, alebo {0|0}. Hráč, ktorý sa pohne ako prvý, vyhrá. Hry rovné {0|0} sú veľmi dôležité. Sú zapísané symbolom * (hviezdička).
Otázky a odpovede
Otázka: Čo je kombinatorická teória hier?
Odpoveď: Teória kombinatorických hier (CGT) je odvetvie aplikovanej matematiky a teoretickej informatiky, ktoré skúma kombinatorické hry a líši sa od "tradičnej" alebo "ekonomickej" teórie hier.
Otázka: Aké podmienky musí hra spĺňať, aby sa považovala za kombinatorickú hru?
Odpoveď: Aby sa hra považovala za kombinatorickú hru, musí mať aspoň dvoch hráčov, musí byť sekvenčná (t. j. hráči sa striedajú v ťahoch), musí mať dokonalé informácie (t. j. žiadne informácie nie sú skryté), musí byť deterministická (t. j. bez náhody), šťastie nemôže byť súčasťou hry, musí existovať definovaný počet možných ťahov, hra musí nakoniec skončiť a hra musí skončiť, keď jeden z hráčov už nemôže ťahať.
Otázka: Na aký typ hier sa zameriava kombinatorická teória hier?
Odpoveď: Teória kombinatorických hier sa zameriava najmä na konečné hry pre dvoch hráčov, ktoré majú víťazov a porazených (t. j. nekončia remízou).
Otázka: Ako sú tieto typy hier reprezentované?
Odpoveď: Tieto typy hier sa dajú reprezentovať stromami, pričom každý vrchol predstavuje výslednú hru z určitého ťahu priamo pod ním na strome.
Otázka: Aké sú ciele teoretikov CG?
A: Medzi ciele teoretikov CG patrí nájdenie hodnôt pre tieto typy hier, ako aj pochopenie konceptu "sčítania hier", ktorý zahŕňa, že každý hráč urobí iba jeden ťah v dvoch rôznych hrách, pričom ostatné hry sa počas jeho ťahu nezmenia.
Otázka: Kto založil CGT?
Odpoveď: Elwyn Berlekamp, John Conway a Richard Guy sa zaslúžili o založenie CGT vo svojej publikovanej práci s názvom Winning Ways for Your Mathematical Plays v 60. rokoch 20. storočia.
Prehľadať