Reversi

Ve druhé úloze bude Vaším úkolem naprogramovat hráče (původně deskové) dvouhráčové hry Reversi.

Mějme čtvercovou hrací plochu 8 x 8 čtvercových políček. Hrací plocha je ohraničená a hrany hrací plochy spolu nesousedí. Máme hrací kameny dvou barev. Na začátku hry máme ve středu hrací plochy umístěny dva kameny od každé barvy. Hráč, který je na tahu položí na hrací plochu kámen své barvy tak, aby uzavřel alespoň jednu souvislou řadu soupeřových kamenů zakončenou vlastním kamenem. Všechny soupeřovy kameny v souvislých řadách od místa položení do místa vašeho kamene se potom stanou kameny hráče na tahu. Je tedy možné uzavřít více než jednu řadu. Toto je možné provádět vodorovně, svisle a šikmo. Pokud hráč nemůže umístit kámen tak, aby soupeři zabral alespoň jeden kámen, hraje automaticky soupeř. Hra končí v okamžiku, kdy je celá hrací plocha zaplněna kameny nebo pokud žádný hráč nemůže položit svůj kámen. Vítězem hry je hráč mající na hrací ploše více kamenů než soupeř.

Naprogramujte hráče, který bude hrát korektně a lépe než hráči všech ostatních.

Na úloze si ukážeme následující vlastnosti této skupiny problémů:

• Objevení základních úskalí prohledávání v prostoru s oponentem, v dynamickém prostředí
  • Problém prohledávání jako kombinatorická exploze
  • Efektivita prohlédávacích algoritmů
• Zobecnění tohoto problému na celou třídu úloh, které lze řešit stejným či obdobným přístupem

Stejně jako v celém předmětu RPH se cení především vaše snaha. Pak se nemusíte bát, že byste kvůli této úloze předmět neukončili. Nicméně v průběhu práce na úloze budou definované kontrolní body, kdy budete muset odevzdat implementaci jisté části úlohy. Na závěr se porovná váš hráč s ostatními a pokusíte se umístit v této minisoutěži co nejlépe.

• Měli byste úloze porozumět a naimplementovat jednoduchého hráče.
• Měli byste navrhnout sofistikovanějšího hráče, který si poradí s ostatními soupeři.

Odevzdání se dělí na dvě části:

1. Odevzdání jednoduchého hráče, který umí hrát korektní tahy.
2. Odevzdání sofistikovaného hráče pro turnaj.

• Odevzdávat budete ZIP archív s vaším modulem player.py a případně se všemi moduly, které tento modul importuje. Tyto soubory musí být v kořeni archívu, archív nesmí obsahovat žádné adresáře! Max. velikost nahrávaného ZIPu je 1 MB.

• v turnaji je limit 1 sekunda na 1 tah
• hráči mají zakázáno používat další vlastní výpočetní vlákna
• implementace pro turnaj musí být v jazyce Python

1. Vytvořte si ve vašem oblíbeném IDE projekt Reversi a v něm soubor player.py s hráčem podle specifikace.
2. Pro testování korektnosti tahů před prvním odevzdáním využijte testovací skript s datasetem reversi_dataset_testing.zip.
   1. Zip soubor rozbalte do složky, ve které se nachází váš hráč.
   2. Spuštěním test_on_datasets.py můžete ověřit korektnost tahů vašeho hráče.
3. Po úspěšném prvním odevzdání bude poskytnut herní skript s možností hry dvou hráčů proti sobě.

• Při testování na datasetu se pro každý tah vytváří nový hráč. Při klasické hře (turnaji) objekt hráče přežívá po celou dobu jedné hry s protivníkem. Dávejte tedy pozor na to, co si váš hráč pamatuje.
• Testovací dataset kontroluje pouze omezenou sadu tahů, při reálné hře nastává mnohem více herních situací. Kód hráče si důkladně sami zkontrolujte a nespoléhejte pouze na průchod testem na datasetu.

• Zahrajte si proti počítači (pozor, hra nemusí mít stejná pravidla jako ta specifikovaná ve formulaci problému)
• Zahrajte si reversi proti jiným hráčům