====== Semestrální práce HIVE ====== Tématem semestrální práce je vytvoření hráče pro hru [[ https://boardgamegeek.com/boardgame/2655/hive | HIVE ]]. Hive se hraje na hexagonálním gridu, kde hráči postupně pokládají (nebo posouvají) hrací kameny představující 5 různých druhů zvířat: včela, brouk, pavouk, kobylka, mravenec. Úkolem je obklopit protihráčovu včelu ze všech stran. Složitost HIVE spočívá v pravidlech pro pohyb jednotlivých figurek (každý druh má svoje vlastní pravidla). **Naše pravidla se mírně liší od oficiálních pravidel HIVE, pro semestrální práci jsou závazná pravidla uvedena na této stránce.** Odevzdané programy budou hrát nejprve proti Brutovi a následně budou automaticky převedeny do turnaje, kde budou hrát všichni proti všem. Cílem hry proti Brutovi je hrát podle pravidel (není třeba vyhrát), avšak v turnaji bude důležitá i strategie hry. {{ courses:b3b33alp:cviceni:hive-final1.png?500 |}} ===== Historie a balíček ===== * 29.11.2023 Nová sekce {{ https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/semestralnipracehive#faq | FAQ }} * 27.11.2023 Zveřejnění zadání, {{ courses:b3b33alp:cviceni:balicekhive.zip | aktuální balíček s programy}} * 4.12.2024 otevření Bruta - podle rychlosti vašeho programu trvá vyhodnocení i několik minut! * 15.12.2024 **Pokud chcete používat nějaké knihovny, které nejsou standardní součástí Pythonu, prosím kontaktujte V. Vonáska, aby ověřil, že budou k dispozici na strojích, kde poběží turnaj** * 7.1.2024 deadline semestrální úlohy * 10.1.2024 předpokládaný hlavní turnaj (body z něj se započítají k bodům ze cvičení) * 20.12.2024 [[ http://pilgrim.felk.cvut.cz/index | Spuštění turnaje ]]. Turnaj bude spuštěň cca 1-2x denně. Použijte ''self.algorithmName'' pro rozlišení jména vašeho algoritmu, použijte ''self.tournament'' pro zapnutí strategie (viz dále). * 20.12.2024 [[ https://cw.fel.cvut.cz/wiki/courses/b3b33alp/cviceni/semestralnipracehive#vypocet_skore_v_turnaji | Výpočet skóre v turnaji ]] ===== Pravidla ===== * Hraje se na hexagonálním gridu o velikosti 13x13, používáme stejný souřadnicový systém jako v domácích úkolech s hex. gridem (např., [[https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/t08#lehka_varianta|HW08]]) * Hrají dva hráči (liší se barvou figurek), hráči se střídají * Každý hráč má k dispozici stejnou sadu figurek (včela - Q/q, brouk - B/b, pavouk - S/s, kobylka - G/g, mravenec - A/a). Včela je vždy jedna, ostatních figurek může být i více {{ :courses:b3b33alp:cviceni:hivehr.png?300 |}} * Jeden hráč hraje za figurky označené velkým písmenem 'QBSGA' (v našich visualizacích je to fialový hráč), druhý hráč hraje s figurkami 'qbsga' (žlutý hráč) * Oba hráči mají vždy všechny informace o hře (umístění figurek na desce, seznam dosud neumístěných figurek svých i protihráče) * Figurky se buď na hrací desku **pokládají (umisťují)**, nebo se **posouvají**. Není možné figurky odebírat. * Hráči se střídají, označme 'n' jako n-tý tah hráče, který zrovna hraje (tahy jsou číslovány od nuly): * Tah 0: * pokud je hrací deska prázdná, musí hráč **položit** figurku (jakoukoliv) doprostřed hrací desky (souřadnice p=3, q=6) * pokud je na hrací desce již soupeřova figurka, musí hráč **položit** nějakou (jakoukoliv) svou figurku vedle ní (musí se dotýkat hranou). V tomto jediném případě se mohou dotýkat dvě figurky různé barvy, protože není jiná možnost. * Tah 1-3: * Hráč na tahu **položí** novou figurku na hrací desku (na prázdnou buňku) tak, aby se nedotýkala hranou kamene protihráče a zároveň se alespoň jednou hranou dotýkala své již položené figurky (viz pravidla pokládání) * Nejpozději v tahu č. 3 musí hráč položit včelu * Tahy 4+: * Hráč na tahu buď **položí** novou figurku (pokud ještě má nějaké k dispozici), nebo **posune** svojí, již položenou, figurku na nové místo (viz pravidla posouvání) * Hráč musí táhnout pokud může (nelze tedy vynechat tah a nechat hrát protihráče) * Hra končí, pokud je splněna některé z podmínek konce hry: * Jedna (nebo obě) včely jsou plně obklopeny kameny (bez ohledu na jejich barvu) * Počet sousedů včely (6) se rovná počtu obsazených sousedů včely * Pokud je včela na kraji hrací desky, stačí k jejímu obklopení méně kamenů * Pokud počet tahů každého hráče překročí 80 tahů [[https://cw.fel.cvut.cz/wiki/courses/b3b33alp/internal/cviceni/hive#bodovani_turnaje_draft|(*)]] * Ani jeden z hráčů nemůže táhnout [[https://cw.fel.cvut.cz/wiki/courses/b3b33alp/internal/cviceni/hive#bodovani_turnaje_draft|(*)]] ===== Pravidla položení figurek ===== * Do hrací desky lze umístit (položit) pouze figurku, která je k dispozici * Figurku lze položit pouze na prázdnou buňku * Při položení se figurka nesmí dotýkat hranou soupeřovi figurky, a musí se dotýkat hranou aspoň jedné figurky vlastní barvy (toto pravidlo neplatí při prvním tahu druhého hráče (viz výše)) * Brouka nelze položit na obsazenou buňku ===== Pravidla posouvání figurek ===== * Pro všechny kameny platí tato pravidla: * Při změně polohy figurky (posunem) nesmí dojít k rozpojení hnízda (tj. všechny umístěné figurky (bez ohledu na barvu) tvoři jednu komponentu souvislosti) * Figurky A/a, Q/q, S/s se po hrací desce pohybují "posunem", tj. na prázdnou pozici se mohou dostat pouze tehdy, pokud aktuální pozice a nová pozice sdílejí ještě jednu prázdou buňku * Posun figurek je omezen na kraji hrací desky (viz obrázek) * Posun je možný tehdy, pokud by se figurka fyzicky dala posunout mezi dvěma buňkami * Figurku lze posunout pouze na neobsazenou buňku (kromě figurky B - brouk, který může lézt po ostatních) * Žádná figurka nesmí opustit hrací plochu | {{:courses:b3b33alp:cviceni:hive-posun1.png?300|}} | {{:courses:b3b33alp:cviceni:hive-posun2.png?300|}} | | Možné posuny (zeleně) ze žluté pozice | Možné posuny ze žluté pozice. V tomto případě se nelze posunout nikam | | {{:courses:b3b33alp:cviceni:hive-posun3.png?300|}} | {{:courses:b3b33alp:cviceni:hive-posun4.png?300|}} | | Možné posuny (zeleně) ze žluté pozice | Možné posuny (zeleně) ze žluté pozice. Do buňky 10,0 se nelze posunout kvůli okraji hrací desky | * Pohyb figurek se dále liší podle toho, jaké zvíře představují * **Mravenec** (v programu označen "A" nebo "a" (ant) ) * V jednom tahu se může posunout o libovolný počet pozic, přičemž celá cesta mravence musí navazovat na hnízdo (každé pole z cesty sousedí s hnízdem) a mravenec se nesmí po cestě vracet * **Brouk** (v programu označen "B" nebo "b" (beetle) ): * V jednom tahu může navštívit všechny své sousedy * Brouk může vlézt na obsazenou pozici. V tom případě se barva této pozice mění na barvu brouka * Figurky, které jsou pod broukem, se nemohou hýbat * Brouk může vlézt na jiného brouka (opět může dojít ke změně barvy --- výsledná barva je vždy barva brouka, který je úplně nahoře) * Při umísťování brouka (první vložení brouka na hrací desku) musí být brouk umístěn na prázdnou buňku * Tím, že brouk může navštívit svého libovolného souseda, může se dostat do míst, která jsou jiným figurkám nepřístupná * **Pavouk** (v programu označen "S" nebo "s" (spider) ): * Pavouk se posunuje po prázdných buňkách vždy přesně o tři buňky, přičemž na své cestě se nesmí vracet * Při každém svém kroku se pavouk musí pohybovat kolem figurek, se kterými je v přímém kontaku * **Včela** (v programu označena "Q" nebo "q" (queen) ) * Včela se posunuje do jedné ze svých sousedních prázdných buněk * **Kobylka** (v programu označena "G" nebo "g" (grasshopper)): * Kobylka skáče ve všech šesti směrech na první volnou pozici * Mezi aktuální pozicí a novou pozicí kobylky musí být alespoň jedna obsazená figurka * Kobylka se může dostat do míst, kam ostatní figurky nemohou kvůli pravidlům posunu * {{ courses:b3b33alp:cviceni:hive.pdf | Příklady práce s figurkami }} * Doporučujeme shlédnutí dostupných video návodů, například [[https://youtu.be/3dGd9dpOerc?t=13|zde 00:13-04:12]]. ===== Implementace ====== * K dispozici je šablona (Python script) s třídou Player (soubor player.py), šablonu najdete v balíčku * Player obsahuje proměnné, na základě kterých hráč rozhodne, jak bude táhnout * Student vše implementuje do souboru player.py (viz dále) * Úkolem je naimplementovat pohyby/pokládání figurek na základě aktuálního stavu hrací desky a čísla tahu, tj. implementovat výše popsaná pravidla * Stav hry **jednoznačně** popisují tyto proměnné: * ''self.board'' (co je na hrací desce) * ''self.myMove'' (číslo tahu) * ''self.myPieces'' (kolik figurek a kterého typu mám ještě nepoložené) * ''self.rivalPieces'' (kolik figurek a kterého typu má ještě soupeř nevyložené) * Programy používají knihovnu PIL pro tvorbu png obrázků, [[ https://pypi.org/project/Pillow/ | nainstalujte si ji ]]. Návod na instalaci najdete [[https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/faq/vscode|zde]]. ===== Proměnné ===== * ''self.board'': * je dictionary představující hrací desku * klíče jsou dvě celá čísla (integers): (p,q) * hodnota je string představující figurky, které jsou na pozici (p,q) umístěny * ''self.board[p][q] = ""'' (prázdná buňka) * ''self.board[p][q] = "a"'' (na pozici (p,q) je umístěn mravenec) * ''self.board[p][q] = "aBb"'' (na pozici (p,q) je umístěn mravenec, na něm brouk a na něm ještě jeden brouk. Barva této pozice je dána posledním broukem (tj. b) * ''self.board'' je pouze pro čtení, hráč by neměl do této proměnné zapisovat * ''self.myMove'' je integer udávající číslo tahu (začíná se od nuly) * ''self.myPieces'' * dictionary, klíč je jméno hráčovy figurky a hodnota je počet ještě nepoložených figurek daného typu * ''self.myPieces["a"] = 3'' - hráč má k dispozici 3 mravence, kteří ještě nejsou na hrací desce (hráč hrající s malými písmeny) * ''self.myPieces["Q"] = 0'' - hráč má k dispozici 0 včel (tj. již včelu položil) (pro hráče hrající s velými písmeny) * ''self.rivalPieces'': * to samé jako ''self.myPieces'', ale pro protihráče * Klíče (jména figurek) jsou case-sensitive. Pokud hráč hraje s malými písmeny (qbsga), budou malá písmena v ''self.myPieces'', ale velká písmena v ''self.rivalPieces'', a naopak * ''self.myColorIsUpper'' je True, pokud hráč hraje s figurkami začínajícími velkými písmeny * ''self.algorithmName'' - řetězec, kterým hráč indikuje jméno svého programu (pro turnaj) * ''self.playerName'' - řetězec se jménem studenta (vyplňuje Brute) * ''self.tournament'' - je True, pokud je hráč spuštěn v turnajovém módu ===== Metody ===== * ''self.move()'' * Tato metoda je jako jediná volána Brutem * Pokud hráč přesouvá již položenou figurku, je návratová hodnota ''[fig, oldP, oldQ, newP, newQ]'' * ''fig'' je jméno figurky (jedno písmeno, buď velké nebo malé podle typu hráče), tj. string * ''oldP'', ''oldQ'' je souřadnice buňky, ze které se má přesunout figurka ''fig'' * ''newP'', ''newQ'' je souřadnice buňky na kterou se má přesun provést * V tomto případě jsou oldP, oldQ, newP a newQ typu integer * Příklad: přesuň fialového brouka z pozice (2,1) na pozici (2,2): ''return ["B", 2, 1, 2, 2]'' * Pokud se jedná o položení nové figurky na hrací desku, je návratová hodnota: ''[fig, None, None, newP, newQ]'', kde newP a newQ jsou souřadnice buňky, na kterou se má umístit figurka * Příklad: umísti žlutou včelu na pozici (3,6): ''return ["q", None, None, 3, 6]'' * Pokud nelze táhnout, je výsledkem prázdné pole, tj. ''return []'' * Implementace hráče může být samozřejme rozdělena (a je to silně doporučeno) do více metod, které si uživatel volá z metody ''self.move()'' * ''self.inBoard(p,q)'' * vrací True, pokud je buňka na pozici p,q součástí hrací desky * ''seld.isEmpty(p,q)'' * vrací True, pokud je buňka na pozici p,q volná (není tam žádná figurka) * ''self.saveImage(filename)'' * uloží aktuální stav hrací desky do png souboru (filename musí obsahovat příponu png) ===== Časové omezení ===== * Konstruktor hráče může trvat max. 1s * Metody ''self.move()'' může trvat max. 1s * Při překročení těchto limitů bude hráč ukončen. V případě hry proti Brutovi bude výsledek 0 bodů, v případě turnaje bude vyřazen ze všech her. ===== Hrací smyčka ===== * Brute vytvoří oba hráče (označme je player1 a player2), naplní jejich proměnné ''self.board'', ''self.myPieces'', ''self.rivalPieces'', ''self.myMove'' a ''self.playerName'' * Následně probíhá hra takto: * Brute zavolá ''player1.move()'' * Proběhne kontrola správnosti tahu a zapsání tahu do hracích desek, tj. dojde k přepsání ''self.board'', ''self.myPieces'', ''self.rivalPieces'' obou hráčů * Pokud je splněna podmínka konce hry, hra končí * Brute zavolá ''player2.move()'' * Proběhne kontrola správnosti tahu a zapsání tahu do hracích desek, tj. dojde k přepsání ''self.board'', ''self.myPieces'', ''self.rivalPieces'' obou hráčů * Pokud je splněna podmínka konce hry, hra končí * Jinak je zvýšena hodnota ''self.myMove'' (u ubou hráčů) o jedna, a hra pokračuje * Zjednodušená hrací smyčky (chybí v ní kontrola správnosti tahů) je implementována v souboru player.py, takže uživatel může hrát sám se sebou a ladit si tak svého hráče, sledovat průběh hry, vykreslovat (do png) apod. Tato hra je ukončena po 50 tazích. * Pro test vašeho hráče na vašem PC použijte: python3 player.py * Tento příkaz musí být spuštěn ve stejném adresáři, do kterého jste si stáhli balíček * Výsledkem je záznam hry ve formě PNG souborů ===== Jak odevzdávat ===== * Stáhněte si balíček se šablonou hráče * **Veškeré implementace provádějte pouze v souboru player.py** * **Na Bruta se odevzdává pouze soubor player.py** (Brute zbývající soubory (base.py) doplní a zajistí, že všichni hráči používají stejné výchozí datové struktury) * Odevzdává se do úlohy SEM ===== Jak na implementaci hry ===== * Nejdříve se seznamte s principem hry, doporučujeme si hru několikrát zahrát s kamarády. Případně je hra volně dostupná online zde [[https://boardgamearena.com/gamepanel?game=hive]] (obsahuje **interaktivní tutoriál**, doporučujeme!) * Po pochopení práce s hrací deskou a předávání výsledků Brutovi doporučujeme následující cvičení: * Implementujte metodu ''self.move()'' tak, aby v každém tahu umístila jednu z volných figurek na libovolnou volnou pozici na desce * Upravte tento program tak, aby hráči postupně zaplňovali hrací desku figurkami zleva doprava, shora dolů * Upravte tento program tak, abyste umístili svoji figurku pouze vedle své, již položené, figurky * Upravte program tak, abyste přesunuli libovolnou figurku na libovolnou pozici * Pro realizaci pohybu jednotlivých figurek je dobré si uvědomit, že jejich pohyby mají společné rysy. Pro každý z těchto rysů (podmínek) je dobré implementovat jednu krátkou funkci * Implementujte metodu pro detekci volných pozic v hrací desce * Implementujte metodu pro detekci volných pozic, které sousedí s alespoň jednou vaší figurkou * Implementujte metodu pro detekci volných pozic, které sousedí s libovolnou figurkou * Implementujte metodu, která vrátí ''True'', pokud je možné přesunou figurku z jedné pozice do druhé * atd.. ===== Bodování ====== * Rozlišujeme body z Bruta a body z Turnaje * Bodování v Brute: * Brute spustí vašeho hráče v mnoha (cca stovkách) tahů a kontroluje, jestli jsou tahy validní * Při testování na Bruta bude hra začínat i z neprázdné hrací desky (aby se simulovalo hraní v pokročilém stadiu hry), hodnoty proměnných ''self.board'', ''self.myPieces'', ''self.rivalPieces'' a ''self.myMove'' budou nastaveny správně * Pokud hráč neudělá ani jednu chybu, bude ohodnocen 5 body, jinak bude bodové ohodnocení 0 bodů. * Při hře proti Brutovi není nutné vyhrát, stačí táhnout náhodně (ale dle pravidel). Pokud máte program, který obsahuje jak jednoduchou strategii, a zároveň strategii pro turnaj, lze je rozlišit takto: def move(self): if self.tournament: #program se strategii pro turnaj else: #jednodussi program pro hru na Brutovi * Další body je možné získat za hru v turnaji, viz dále. ===== Turnaj ====== * Turnaj bude zahájen cca 3. týden prosince (podle počtu odevzdaných programů) * Turnaj proběhne cca jednou denně (výpočet trvá několik hodin, proto nelze turnaj spouštět častěji) * Výsledky turnaje budou aktualizovány na stránce turnaje (odkaz bude zveřejněn po zahájení turnaje) * Je možné odevzávat nové verze programů, postupně je ladit a zlepšovat * Finální turnaj proběhne několik dní před první zkouškou (předpoklad je 2. týden v lednu), datum bude včas oznámeno * Body z finálního turnaje se budou přičítat k hodnocení semestrální práce takto dle výsledného pořadí: * Prvních 10% hráčů dostane + 5 bodů * Dalších 20% hráčů dostane + 4 body * Dalších 20% hráčů dostane + 3 body * Bodování v turnaji bude zveřejněno při zahájení turnaje ===== Výpočet skóre v turnaji ====== * Pokud je protivníkova včela obklopena ze všech možných stran N, dostane hráč 15 bodů. * Pokud je včela uvnitř hrací desky, je N=6. * Na okrajích hrací desky může být včela plně obklopena z méně než šesti stran, pak je N méně než 6. * Pokud je protivníkova včela (včela je uvnitř desky) obklopena jen částečně, dostane hráč tolik bodů, kolik je počet bezprostředních sousedů včely -1 * Pokud je protivníkova včela na okraji hrací desky a není zcela obklopena, dostane hráč 2*(počet sousedů -1). * **Příklad:** Modrá včela je zcela obklopena, žlutý hráč dostane 15 bodů. Žlutá včela je obklopena ze tří stran, modrý hráč dostane 2 body. {{ :courses:b3b33alp:cviceni:hivepoints.png?400 |}} ===== FAQ ====== * [[https://cw.fel.cvut.cz/b231/courses/b3b33alp/cviceni/faq/vscode|Návod na instalaci knihovny PIL/PILLOW ]]. * 3D modely pro tisk, např. [[ https://www.stlfinder.com/3dmodels/hive-board-game/ ]], nebo [[ https://www.printables.com/model/190494-hive-game-board ]]. Na cvičeních jsme používali {{courses:b3b33alp:cviceni:hive_board_game_with_box_3591971.zip | tento model }}, scale: x=y=180%, z=50% * Jaké jsou možnosti tahů brouků a včel v této konfiguraci? {{ :courses:b3b33alp:cviceni:hive-faq1-scene.png?400 |}} * Všechny platné pohyby jsou: {{ :courses:b3b33alp:cviceni:hive-faq1.png?800 |}} * Brouk se nepohybuje posunem, ale leze přes ostatní, proto není jeho pohyb omezen na kraji hraci desky - z pozice (5,0). * Brouk na pozici (4,2) se nemůže nikam pohnout, neboť při přesunu by došlo k rozpojení hnízda. Toto platí i pro přesun brouka z pozice (4,2) do pozice (5,2) (i při tomto přesunu dojde k rozpojení hnízda).