Differences

This shows you the differences between two versions of the page.

--- courses:a4b36acm1:kombinatoricke_hry [2018/10/03 03:51]
+++ courses:a4b36acm1:kombinatoricke_hry [2018/10/03 03:51] (current)
@@ Line 1: / Line 1: @@
+===== Kombinatorické hry =====
+**Definice:** Kombinatorickou hrou budeme rozumět libovolnou hru splǔjící následující pravidla:
+  - Hru hrají dva hráči, kteří se střídají v tazích.
+  - Počet stavů, ve kterých se hra může nacházet, je vždy konečný.
+  - Pravidla hry stanovují pro každého hráče v libovolném stavu hry jaké další tahy může zahrát.
+  - Hra končí vítězně pro hráče, který zahrál naposledy, tedy prohrává ten hráč, který na začátku svého tahu nemá žádný platný tah.
+  - Hraje se s úplnou informací a bez náhody.
+<note>Pokud narazíme na hru, která nesplňuje výše uvedená pravidla, tak se nelekněte. Tato definice strikně vymezuje typy her, jež jsou naším primárním cílem se naučit řešit (hrát optimálně).</note>
+<note tip> V některých níže uvedených hrách naschvál uvádím něco na způsob: //Zjistěte, pro které N, byste chtěli začínat.//. Tím bych chtěl trochu napovědět, že pokud hráči hrájí optimálně, stavy hry se budou dělit na (V)yhrávající a (P)rohrávající z pohledu začínajícího hráče. Zkuste při řešení nalézt pravidlo, podle kterého se jednotlivé stavy hry dělí na V a P a tím se nakonec dopracovat k odpovědi.
+</note>
+==== Hra #1: Odečítání dělitelů ====
+Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst jeho libovolný //vlastní// dělitel. Zjistěte, pro která N byste chtěli hrát jako první.
+==== Hra #2: Lámání čokolády I ====
+Hra se točí okolo lámání čokolády o rozměrech MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte). Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.
+==== Hra #3: Přičítání dělitelů ====
+V této hře je počáteční číslo pevně dáno a je rovné 2. Hráči se střídají a při svém tahu mohou k aktuální hodnotě N přičíst jeho libovolný //vlastní// dělitel. Hráč, po jehož tahu hodnota N překročí 2016, vítězí. Dokážete říci, zda existuje vyhrávající strategie pro začínajícího hráče?
+==== Hra #4: Čísla v lahvi ====
+V láhvi jsou lístečky s čísly od 1 do 16. Hráč, který je na tahu, vyndá z lahve nějaké číslo a všechny jeho dělitele. Prohrává hráč, nemůže táhnout. Může si začínající hráč vynutit výhru?
+==== Hra #5: Lámání čokolády II ====
+Hra se točí okolo lámání čokolády o rozměrech 2MxN kostiček. Při svém tahu smí hráč rozlomit libovolný dílek čokolády podél vyznačených linií (však to znáte), ALE nikdy nesmí vzniknout dílek o velikosti 1x1. Prohrává ten hráč, který nemůže žádný dílek rozlomit. Zjistěte, při jakých velikostech čokolády byste chtěli začínat.
+==== Hra #6: Odečítání prvočísel ====
+Hráči si zvolí přirozené číslo N. Ve hře se střídají a při svém tahu hráč může od aktuální hodnoty N odečíst libovolné prvočíslo (včetně 1) menší než N. Zjistěte, pro která N byste chtěli hrát jako první.
+==== Hra #7: Lámání čokolády III (Chomp) ====
+Opět se hra točí kolem lámání čokolády, ale v tomto případě jde o život! Tabulka čokolády leží na stole, rozlámaná na jednotlivé kostičky. Hráč si při svém tahu zvolí libovolný dílek čokolády a zbaští všechny dílky, které se od dané kostičky vyskytují nahoru a napravo (odebraný kus čokolády vždy tvoří obdélník o jednom či více dílků). Problém je, že dílek úplně vlevo dole je otrávený. Zkuste zjistit, zdali se jako začínající hráč můžete vyhnout otravě, pokud má tabulka čokolády tvar A) čtverce či B) obdélníku.
+==== Hra #8: Odebírání sirek ====
+Na stole leží N sirek. Hrači se postupně střídají v odebírání sirek, přičemž mohou při svém tahu odebrat 1, 2, nebo 3 sirky. Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.
+<note important>Následující 2 hry jsou zde uvedeny pro zajímavost, proto se je prosím nesnažte řešit, pokud neznáte odpovědi pro všechny hry uvedené výše.</note>
+==== Hra #9: Odebírání sirek II ====
+Na stole leží N sirek. Hrači se postupně střídají v jejich odebírání, přičemž hráč při svém tahu nesmí odebrat více sirek než kolik bylo odebráno v předchozím tahu. Začínající hráč musí odebrat alespoň jednu sirku, ale nesmí odebrat všechny (jinak by to byla pěkně nudná hra). Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.
+==== Hra #10: Odebírání sirek III (Fibonacci Nim) ====
+Na stole leží N sirek. Hrači se postupně střídají v jejich odebírání, přičemž hráč při svém tahu nesmí odebrat více sirek než kolik bylo odebráno v předchozím tahu. Začínající hráč musí odebrat alespoň jednu sirku, ale nesmí odebrat všechny (jinak by to byla pěkně nudná hra). Vyhrává ten hráč, po jehož tahu na stole nezbude žádná sirka.
+==== Hra #11: Odebírání z hromádek ====
+Na stole leží 3 hromádky se 4, 2 a 1 kamenem. Hráč při svém tahu může odebrat 1 nebo 2 kameny. Hráč, který zvedne poslední kámen vyhrává.
+==== Hra #12: Klasický NIM ====
+Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů (klidně odebere celou hromádku). Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.
+==== Hra #13: Upravený NIM ====
+Na stole leží M hromádek s kameny. i-tá hromádka obsahuje N[i] kamenů. Hráč si při svém tahu vybere hromádku a odebere z ní libovolný počet kamenů, ale vždy alespoň jeden. Vyhrává ten, který ze stolu zvedne poslední kámen. Určete v závislosti na počtu hromádek a kamenů v nich, zdali začínající hráč vyhraje, bude-li hrát optimálně.
+==== Hra #14: Otáčení mincí ====
+Je dána řada N mincí, kde některé jsou pannou a jiné orlem vzhůru. Hráč si při svém tahu může zvolit libovolnou minci, která je pannou vzhůru, a otočit ji. Navíc, si může zvolit libovolnou minci nalevo od té první a otočit ji (ať byla orientovaná jakkoliv). Ukažte, že tato hra je ekvivalentní s předchozí hrou NIM (klasický).
+==== Hra #15: Krájení koláče ====
+Hrači stojí nad koláčem, který má na svém okraji N zářezů. Hráč, který je na tahu, si zvolí dvojici zářezů na libovolném kusu koláče a jedním tahem ho napříč těmito zářezy rozřízne. Hráč, který nemůže provést žádný řez, prohrává.
+==== Hra #16: Odebírání sirek IV ====
+Na stole leží N hromádek sirek. i-tá hromádka obsahuje N[i] sirek. Hráč na tahu si zvolí libovolnou hromádku a odebere z ní 1, 2, nebo 3 sirky. Hráč, který odebere poslední sirku, vyhrává.
+==== Zdroje ====
+  * [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]]
+  * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]]
+  * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]]
+  * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]]
+  * Kombinatorické hry - krátká ilustrace ({{:courses:a4b36acm:combigames.pdf| pdf}}, {{:courses:a4b36acm:combigames.ppt| ppt}})
+  * Nimbers (Sprague-Grundyho čísla) - ukázková úloha  ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{:courses:a4b36acm:pizza.pdf| s řešením}})
+  * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]]