Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Reversi

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

Formulace problému

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

Formulace úlohy

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

Cíle

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

Hodnocení

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 porovnají vaše hráče 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ší hráče, který si poradí s ostatními soupeři.

Odevzdání

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!

Další informace

  • v turnaji je limit 1 sekunda na 1 tah
  • hráči mají zakázáno používat další vlastní výpočetní vlákna

Instrukce pro úlohu Reversi

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

Na co si dát pozor

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

Odkazy

courses/b4b33rph/cviceni/reversi/start.txt · Last modified: 2019/09/18 23:21 by penicrob