Semestrální práce HIVE

Tématem semestrální práce je vytvoření hráče pro hru 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.

• 29.11.2023 Nová sekce FAQ
• 27.11.2023 Zveřejnění zadání, 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 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 Výpočet skóre v turnaji

• Hraje se na hexagonálním gridu o velikosti 13×13, používáme stejný souřadnicový systém jako v domácích úkolech s hex. gridem (např., 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

• 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ů (*)
    • Ani jeden z hráčů nemůže táhnout (*)

• 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

• 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

Možné posuny (zeleně) ze žluté pozice	Možné posuny ze žluté pozice. V tomto případě se nelze posunout nikam
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

• Příklady práce s figurkami
• Doporučujeme shlédnutí dostupných video návodů, například zde 00:13-04:12.

• 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ů, nainstalujte si ji . Návod na instalaci najdete zde.

• 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

• 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)

• 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.

• 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ů

• 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

• 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..

• 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 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

• 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.

• 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 tento model , scale: x=y=180%, z=50%
• Jaké jsou možnosti tahů brouků a včel v této konfiguraci?

• Všechny platné pohyby jsou:

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