====== 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).