Warning
This page is located in archive.

2. Reversi

Vaším cílem bude naprogramovat hráče hry Reversi.

Hru si můžete ozkoušet např. zde.

Problém

Reversi je hra na čtvercových hracích polích s hrací deskou o rozměru $n\times n$. Každý hráč má sadu hracích kamenů jedné barvy. Na počátku hry jsou ve středu umístěny dva kameny každé barvy umístěné do plochy 2 x 2 diagonálně. Hráč ve svém tahu umístí jeden kámen na prázdné pole, aby uzavřel souvislou (i jednoprvkovou) řadu kamenů soupeře mezi své kameny. Každá tahem uzavřená řada změní svou barvu. Uzavřít řadu lze ve všech osmi sousedních směrech. Pokud hráč nemůže umístit kámen, kterým by uzavřel nějakou soupeřovu řadu, je na tahu soupeř. Hra končí v okamžiku, kdy je celá hrací plocha zaplněna kameny nebo když žádný hráč nemůže položit kámen uzavírající soupeřovu řadu. Vítězí hráč s nejvíce kameny na hrací ploše.

Cíle

Touto úlohou se blíže seznámíte s:

  • Prohledáváním stavového prostoru s oponentem
    • Problém kombinatorické exploze
    • Zohlednění efektivity prohledávacích algoritmů

Řešení této úlohy lze zobecnit na mnohé podobné klasické hry, i když v některých případech (např. Go) může být nedostačující na porážku dostatečně dobrého lidského soupeře.

Úkol: Turnajový hráč

Pokusíte se napsat hráče, který se utká s hráči vašich spolužáků. Viz specifikace a hodnocení.

Termín odevzdání úlohy je v BRUTE.

Základní informace o turnaji:

  • hraje se systémem každý s každým na hracím poli o velikosti $n\times n$, $n \in \{6,8,10\}$
  • zápas se skládá ze dvou setů - v prvním začíná hráč “A”, v druhém začíná hráč “B”
  • za vítězství v zápase 2 body, remíza 1 bod, prohra 0 bodů
  • limit 60s na konstruktor
  • limit 5s na 1 tah (metoda move)
  • zahrání neplatného tahu znamená ztrátu zápasu
  • překročení časového limitu znamená ztrátu zápasu

Odkazy

courses/b3b33kui/semestralni_ulohy/2_reversi/start.txt · Last modified: 2024/03/06 11:16 by xposik