Warning
This page is located in archive.

Semestrální práce

  • Úkolem je naprogramovat hráče pro deskovou hru inspirovanou Quoridorem
  • Vaše kódy budou hrát “proti sobě” (na serveru BRUTE).
  • Pravidla naší hry se od klasického Quiridoru mírně liší. Řiďte se pouze pravidly uvedenými na této stránce.
  • Je možné, že během řešení semestrální práce narazíte (nebo tým učitelů) na nejasnosti a bude potřeba ujasnit pravidla nebo pozměnit rozhraní pythonovských skriptů. V takovém případě budeme všechny změny přehledně uvádět v sekci Historie.

Historie:

  • 4.12. zveřejnění zadání
  • 18.12. přidán příklad inicitalizace překážek na začátku hry. Překážky se přidávají v jednorozměrném poli. Délka tohoto pole musí být dělitelná 2 (to zajistí náš kód), neboť každá překážka je reprezentována dvěma objekty typu Obstacle.
  • 26.12. Aktuální výsledky turnaje. Do této tabulky se dostane pouze kód (hráč) odevzdaný do úlohy SemTour na Brutovi.
  • 31.12. Aktualizace třídy Obstacle, byla přídána metoda _ _eq_ _(), takže nyní můžete přímo porovnávat překážky operátorem '==' (např. if (o1==o2)). Pro zjištění, zdali-je proměnná None pouzijte operátor is, např. if (not obstacle is None) …
  • 31.12. Upozornění pro SemTour/SemBasic: v player.py nedefinujte svou vlastní třídu Obstacle, pouze ji importujte (from obstacle import *). Tento import je povolen. Pokud potřebujete svou vlastní implementaci překážek, vytvořte si vlastní třídu (třeba MyGreatObstacle) a tu používejte uvnitř svého hráče. Je však třeba zajistit, že překážky předané metodou make_move (a příjem překážek z opponent_move) musí probíhat přes naši třídu Obstacle. Pokud byste z make_move vrátili proměnnou jiného typu než Obstacle (zde myšlena třída Obstacle definovaná na této stránce), bude to vyhodnoceno jako nevalidní překážka a systém ukončí hru.
  • 02.01. Kromě modulů numpy, scipy, matplotlib, stat, statistics a pyclbr jsou všechny ostatní importy povoleny .

Pravidla hry:

  • Hra se hraje na 2D poli o velikosti $n_x$, $n_y$
  • Hra je pro dva hráče
  • Začátek hry:
    • Hráči jsou umístěni na prvním, resp. posledním řádku, a na jakémkoliv sloupci.
    • Je dán seznam $n$ překážek (může být prázdný)
  • Cílem hráče je dostat se do své cílové zóny.
  • Cílová zóna je:
    • poslední řádek (kterýkoliv sloupec) - pro hráče, který začína na prvním řádku
    • první řádek (kterýkoliv sloupec) - pro hráče, který začíná na posledním řádku
  • Hráči se pohybují vlevo, vpravo, nahoru, dolů - vždy o jedno políčko
  • Hráči se nemohou přeskakovat
  • Hráči nemohou opustit hrací desku
  • Hráči nemohou být na stejné pozici
  • Hráči nemohou přeskakovat překážky (ani svoje, ani protihráčovi, ani překážky zadané na začátku hry)
  • Překážky:
    • každý hráč má k dispozici $m$ překážek
    • překážka je dlouhá 2 buňky (viz obrázek) a je umístěna “mezi” buňkami
    • překážka může být umístěna pouze uvnitř hrací plochy (mimo hran hrací desky)
    • překážka nesmí zasahovat ven
    • překážka nesmí překrývat jinou překážku, ale může ji přetínat (viz obrázek)
    • překážka musí být umístěna tak, aby ani jednomu hraci nezablokovala cestu k cíli
    • překážky lze pouze přidávat, jednou přidané překážky se nesmí ani odebrat, ani posunout
    • maximální počet překážek, které se ve hře můžou najednou vyskytnout, je $2m + n$
  • Tah jednoho hráče je:
    • posun hráče o jedno políčko (překážky se nemění), nebo
    • přidání nové překážky (pozice hráče se nemění), nebo
    • beze změny, pokud nelze ani umístit překážku ani se pohnout.
  • Hra končí, když
    • jeden z hráčů dosáhl své cílové zóny
    • ani jeden z hráčů nemůže udělat tah. V takové situaci jsou oba hráči idioti a oba prohráli.
  • Souřadnicový systém je na následujícím obrázku.
  • Všechny souřadnice jsou typu integer.
Základní hrací ploha a její souřadnicový systém. Modrý hráč je na pozici (3,0), zelený na pozici ($n_x$-2, $n_y$-1).
Příklady validních překážek (černě) a nevalidních (červeně). Validní tahy.

Příklady umisťování překážek

Kdy nelze umístit překážku:

a b
  • a) Předpokládejme toto rozestavení na začátku hry. Ani jeden z hráčů nesmí umístit překážku do červeně vyznačené oblasti, protože by oběma hráčům blokovala přístupovou cestu k jejich cílové zóně.
  • b) Ani jeden z hráčů nesmí umístit do červeně vyznačené oblasti, jinak by blokovala zelenému hráči přístup k jeho cílové zóně. Existují i jiné konfigurace překážek, které v tomto případě nelze použít.

Kdy lze překážku umístit:

  • hráči se pohli ze své počáteční polohy (naznačeno šipkami). Zelený chce dosáhnout prvního řádku, modrý posledního. V tomto případě oba hráči mohou dosáhnout své cílové zóny a proto je možné umístit překážku

Implementace:

  • Semestrální práce bude realizována několika pythonovskými skripty:
    • player.py - v této třídě bude váš kód. Dostanete kostru třídy s návodem na implementaci. Tento soubor budete odevzávat na upload system.
    • manager.py - tento kód se stará o spouštění hry. Nemusíte implementovat, ale je dobré vědět, jak funguje. Můžete ho používat pro testování na vlastním PC.
    • obstacle.py - malinká třída pro reprezentaci překážek. Slouží k výměně překážek mezi hráči. Neměnte.

Překážky

  • budeme reprezentovat jako “zakázaný pohyb z buňky x1,y1 do buňky x2,y2.
  • Jelikož má každá překážka délku “dvě buňky”, bude jedna překážka reprezentována dvěma instancemi třídy Obstacle.
  • Je na vás zajistit, abyste vytvářeli validní překážky (rovné, délky dvě).
  • Třídu obstacle neměnte, pouze ji importujte do svého hráče.

class Obstacle:
    """ Simple class to represent one part of each obstacle. The obstacle is defined by coordinates of cells
        between which the player cannot move
    """
 
    def __init__(self,fromx, fromy,  tox, toy):
        self.fromx = fromx
        self.fromy = fromy
        self.tox = tox
        self.toy = toy
 
    def __str__(self):
        return "(" + str(self.fromx) + "," + str(self.fromy) + ")->(" + str(self.tox) + "," + str(self.toy) + ")"
 
    def can_player_move(self, fromx, fromy, tox, toy):
        """
            return True, if a player can move from [fromx,fromy] to [tox,toy]. This only checks if THIS obstacle 
            prevents the move or not. 
        """
        if (self.fromx == fromx and self.fromy == fromy and self.tox == tox and self.toy == toy) or \
    (self.fromx == tox and self.fromy == toy and self.tox == fromx and self.toy == fromy):
               return False
        return True
 
    def is_valid_obstacle(self, sizex, sizey):
        """ return True, if the given obstacle is valid (is inside the board). Size of the board is sizex, sizey
        """
        return (self.fromx >= 0 and self.fromx < sizex and \
                self.fromy >= 0 and self.fromy < sizey and \
                self.tox >= 0 and self.tox < sizex and \
                self.toy >=0 and self.toy < sizey)
 
    def __eq__(self, other):
        return type(self) == type(other) and  self.fromx == other.fromx and self.fromy == other.fromy and self.tox == other.tox and self.toy == other.toy;

Příklad vytvoření validní překážky z obrázku:

#horizontalni
p1 = Obstacle(5,0, 5,1)
p2 = Obstacle(6,0, 6,1)
 
#vertikalni
p3 = Obstacle(3,5, 4,5)
p4 = Obstacle(3,6, 4,6)

Takové překážky bude vracet metoda Player.makeMove a Player.expandObstacles jako pole, tedy:

#.. somewhere in player.expandObstacles()
pa = Obstacle(3,5, 4,5)
pb = Obstacle(3,6, 4,6)
myObstacles = []
myObstacles.append(pa)
myObstacles.append(pb)
return myObstacles

Player

  • Jádro vaší práce bude spočívat v implementaci třídy Player.
  • Tato třída bude volána herním managerem, proto je třeba dodržet předepsané rozhraní
  • Nutné metody, jejichž rozhraní neměňte (tj. neměňte počet/pořadí argumentů).
    • konstruktor musí mít právě jeden parametr (jméno studenta)
    • initialization - bude vysvětleno na cvičení
    • make_move - bude vystvětleno na cvičení
    • opponent_move - bude vysvětleno na cvičení
    • all_player_moves - bude vystvětleno na cvičení
    • all_obstacles - bude vystvětleno na cvičení
  • Vytvořte si další funkce nebo proměnné dle potřeby.

class Player:
    def __init__(self, name):
        self.name = name; #student's name, will be filled by BRUTE
        self.version = "version 3" #student' debug info, e.g. version, name of algorithm..
        self.myx = -1 #my position
        self.myy = -1
        self.opponentx = -1  #position of the oponent
        self.opponenty = -1
        self.sizex = -1  #size of the board. Will be filled using initialization
        self.sizey = -1
        self.obstacles = []  #I have no 
        self.max_obstacles = -1
        self.my_goal_row = -1  #index of row, where is my goal zone
        self.my_obstacles = 0 
 
    def initialization(self, sizex, sizey, myx, myy, opponentx, opponenty, max_obstacles, list_of_obstacles):
        """
            This method is called by the game Manager to tell the player where it is, where is the oponent, where are obstacles and how
            many obstacle the player can use.
 
            sizex, sizey - dimensions of the board
            startx, starty - my initial position at the board
            ostartx, ostarty - initial position of the oponent
            max_obstacles - how many obstacles I can use
            list_of_obstacles - array of initial obstacles (objects Obstacles).
        """
        self.sizex = sizex
        self.sizey = sizey
        self.myx = myx
        self.myy = myy
        self.opponentx = opponentx
        self.opponenty = opponenty
        self.max_obstacles = max_obstacles
        self.obstacles = list_of_obstacles
        self.my_obstacles = 0 #number of my obstacles
 
 
        if (self.myy == 0):
            self.my_goal_row = sizey -1
        else:
            self.my_goal_row = 0
 
    def is_in_board(self, x,y):
        """ return True if position (x,y) is in the board 
            TODO: implement in class
        """
        return True
 
    def can_player_move(self, x,y):
        """ return True, if this player can move from (self.myx, self.myx) to the cell (x, y)
            TODO: implement in class
        """        
        return True
 
 
 
    #this is called by the manager. this function should return either new position of this paper (0, (x,y)) or
    #position of new obstacles (1, x1,y1,x2,y2);
    def make_move(self):
        """ this function is called by the game Manager to get the move of this player. The move is
            either new position of the player or newly placed obstacle. 
            Return always TWO variables: the first is integer, the second is LIST
 
            if value is 1: the list is [x, y] - new position of the player
            if value is 2: the list is [o1, o2] - list of two Obstacles - this means that the player placed new obstacle
            if value is None: the list is ignored - this means that player cannot move
 
            TODO: implement by yourself
 
            #the following code is just example to show how to return new postion, new obstacle or None.
 
            #example of returning a position, try first go to down, then left, then right, then up
            #return 1, [self.myx, self.myy]; #move up toward the goal zone
 
            o1 = Obstacle(x1,y1, x2, y2);
            o2 = Obstacle(xx1,yy1, xx2, yy2);
            if (o1.is_valid_obstacle(self.sizex, self.sizey) and o2.is_valid_obstacle(self.sizex, self.sizey)):
               self.obstacles.append(o1)
               self.obstacles.append(o2)
               self.my_obstacles+=1
               return 2, [ o1, o2 ]
            """
        return None
 
 
 
 
    def opponent_move(self, moveType, result):
        """ this is called by the Manager to pass result of oponent's move. moveType and result has the same
            meaning as in the self.move method
        """
        if (moveType == 1):
            #the other player moved itself, let's update its position
            self.opponentx = result[0]
            self.opponenty = result[1]
        elif (moveType == 2):
            #the other player placed a new obstacle.
            if (len(result) == 2):
                self.obstacles.append(result[0])
                self.obstacles.append(result[1])
            else:
                #this shouldn't happen, it will be checked by the manager
                print("Error, oponent returned wrong move!!")
        else:
            print("Oponent return None")
 
 
    def expand_player(self):
        """ returns LIST of [x,y] positions where this player can move. It can be empty.
            TODO: implement by yourself
        """
        my_moves = []
        return my_moves
 
    def expand_obstacles(self):
       """ return LIST of [o1,o2] of all possible pairs of obstacles. can be empty if the player cannot
          place any obstacle anymore
            TODO: implement by yourself
       """
       my_obstacles = []
       return my_obstacles 

Příklad práce s hráčem (doporučujeme začínat takto):

p = Player("pepa")
p.initialization(10,10, 0,0 9,9, 5, []); #board 10x10, first player at (0,0), second at (9,9), max 5 obstacles, empty list of obstacles 
 
my_moves = p.expand_player()
 
#or 
my_obstacles = p.expand_obstacles()

Manager

  • V turnaji bude spouštěna tzv. managerem.
  • Ten se postará o vytvoření hráčů, předá jim informace o velikosti hrací plochy, rozmístí hráče (a případně výchozí překážky).
  • V každém kole Manager zavolá oba hráče metodou Player.make_move(), která vrátí buď novou pozici hráče, nebo seznam nových překážek (seznam musí mít délku 2).
  • Pokud jeden z hráčů dosáhne svého cílového stavu, hra končí.
  • Zde je uvedena minimalistická verze třídy Manager, která stačí pro vaše testování. Na upload systému máme rafinovanější verzi, která kontroluje validnost tahů, počty překážek atd..

from obstacle import *
 
class Manager:    
    """
        Example of game Manager. This class is responsible to call methods of both players. This is simple version
        of the manager (e.g., we do not control validiy of obstacles returned by players etc..).
    """
 
    def __init__(self, p1, p2, sizex, sizey):
        """ p1,p2 are objects of class Player
            sizex,sizey is dimension of the board
        """
        self.p1 = p1
        self.p2 = p2
        self.sizex = sizex
        self.sizey = sizey
 
 
    def init(self):
        """
            Example of game initialization. We create positions of both players (x1,y1) and (x2,y2) and 
            call initialization on each player. 
        """
        self.x1 = self.sizex//2; 
        self.y1 = 0;
 
        self.x2 = self.sizex//2;
        self.y2 = self.sizey -1;
 
        #create an initial obstacle. As each obstacle has to have length 2, we have to create TWO objects 
        obstacles = []
        obstacles.append( Obstacle(2,self.sizex//2,2,self.sizey//2 + 1) ) #horizontal obstacle at column 1
        obstacles.append( Obstacle(3,self.sizex//2,3,self.sizey//2 + 1) ) #horizontal obstacle at column 2
 
        self.p1.initialization(self.sizex, self.sizey, self.x1, self.y1, self.x2, self.y2, 4, obstacles)
        self.p2.initialization(self.sizex, self.sizey, self.x2, self.y2, self.x1, self.y1, 4, obstacles)
 
    def check_result(self, player, moveType, result):
        """ return True, of result of player.move is valid
        """
        if (moveType == 1 and len(result) == 2):
            if (player == 1):
                self.x1,self.y1 = result[0], result[1]
            else:
                self.x2,self.y2 = result[0], result[1]
            return True;
        if (moveType == 2 and len(result) == 2 and type(result[0]) == Obstacle and type(result[1]) == Obstacle):
            obstacles.append(result[0])
            obstacles.append(result[1])
            return True;
        if (moveType == None):
            return True;
 
        print("Upps, player1 returned invalid output from move()");
        quit()
 
    def is_winner(self):
        """ return true if one of player is at goal zone 
        """
        return self.y1 == self.sizey-1 or self.y2 == 0
 
 
    def game(self):
        """ Example how the game will be handled during the tournament. The player p1 will always start first.
            The game is organized this way:
            1. tell p1 where is p2 (p1.oppositeMove())
            2. ask p1 to move (i.e., to move itself or place new obstacles)
            3. tell p2 what move p1 did
            4. ask p2 to move
        """
 
        moveType2 = 1;
        result2 = [ self.x2, self.y2 ]
 
        cnt = 0;
 
        while(True):
            self.p1.opponent_move( moveType2, result2 )
            moveType1, result1 = self.p1.make_move()
            print("p1 returned: ", moveType1, result1[0], result1[1]);
 
            self.check_result(1, moveType1, result1)
 
            if (self.is_winner()):
                print("P1 wins");
                return
 
            self.p2.opponent_move(moveType1, result1)
 
            moveType2, result2 = self.p2.make_move()
            print("p2 returned: ", moveType2, result2[0], result2[1]);
            self.check_result(2, moveType2, result2)
            if (self.is_winner()):
                print("p2 wins!");
                return;
            print("p1=(",self.x1, self.y1,"), p2=(",self.x2,self.y2,")")
        print("end of the game");

Příklad hry

  • Předpoklad: player.py, manager.py a obstacle.py jsou ve stejném adresáři

from manager import *
from player import *
p1 = Player("pepa")
p2 = Player("franta")
 
m = Manager(p1,p2, 15, 15);
m.init()
m.game()

Jak hrát

  • Správně naprogramovaný hráč může hrát proti sobě (stačí vytvořit dvě instance třídy Player, manager se postará o to, že startují z různých pozic.
  • Pokud byste si chteli vytvořit např. náhodného hráče, udělejte si kopii třídy Player (třeba do souboru randomPlayer.py) a toho si naimportujte:

from manger import 
impor randomPlayer as RP
import player as P
 
p1 = P.Player("pepa")
p2 = RP.Player("franta")
#zbytek je stejný jako výše.

  • Pro testování asi budete potřebovat měnit manager.py (např. aby umisťoval hráče do vámi zvolených pozic, aby dával hodně překážek na začátek hry atd.
  • V managerovi dělejte jen takové změny, které nemění rozhraní volání (aby se nestalo, že váš player počítá s jinými argumenty, než výše uvedený manager)

Jak bude hodnoceno a jak odevzávat

  • Odevzdávejte player.py (nebo player.zip)
    • Pokud odevzdáte zip, musí být všechny souboru v kořenovém adresáři zipu
  • Hodnocení na upload systému je rozděleno do dvou fází SEMBasic a SEMTour
  • SemBasic, zde budeme kontrolovat (v tomto pořadí):
    • jestli váš kód splňuje zadané rozhraní (za správnost 0 bodů)
    • platnost tahů z funkce expandPlayer (za správnost 1 bod)
    • platnost překážek z funkce expandObstacles (za správnost 1 bod)
    • Z této části musíte získat 2 body, jinak nebude semestrální práce uznána.
  • SemTour
  • zde bude váš kód spuštěn v turnajovém módu. Budete hrát každý s každým
  • v tomto případě bude Manager volat metodu makeMove()
  • pokud váš kód během turnaje vrátí neplatný výsledek (např. se hráč posune a více než jedno políčko, nebo umístíte do hry více než jednu překážku najednou atd.), budete z turnaje vyloučeni (samozřejmě je možné kód upravit a odevzdat znova) *
  • bodování:
    • váš hráč je mezi 10% nejlepšími (3 body)
    • váš hráč je mezi 20% nejlepšími (2 body)
    • váš hráč je mezi 40% nejlepšími (1 bod)
    • procenta se počítají z počtu hráčů, kteří se úspěšně účastní turnaje (tj. nejsou vyřazeni)
    • finální bodování bude spočítáno na začátku 15 týdne semestru (po zápočtech).
  • minimálně je nutný zisk 0 bodů.

.

Příklad expanze překážek

Výchozí stav:

Vytvoření hry. Hráči v 0. sloupci. Jedna dvou-buňková překážka na začátku

p = Player("pepa")
o1 = Obstacle(0,1, 0,2) #horizontal obstacle (black in the following images)
o1 = Obstacle(1,1, 1,2)
p.initialization(4,4, 0,0 0,3, 5, [o1, o2]);
 
ob = p.expand_obstacles()
 
#in this case, the list 'ob' should have 11 items. The order of the returned obstacles does not matter

Validní tahy:

Situaci vlevo-nahoře odpovídá tento fragment kódu:

def expand_player(self):
   my_moves = []
   o1 = Obstacle(0,0,  0,1)
   o1 = Obstacle(1,0,  1,1)
   my_moves.append( [ o1, o2 ] );
   ... code for other obstacles ...
   return my_moves

Příklad inicializace hry s překážkami

  • Překážky na začátku hry jsou předány jako pole objektů Obstacle - poslední parametr metody Player.initialization
  • Toto pole je jednorozměrné

Příklad předání 2 překážek.

  • Je třeba si uvědomit, že každá překážka je reprezentována dvěma objekty Obstacle.
  • Musíme tedy předat pole 4 objektů

#vertical obstacle
o1 = Obstacle(0,0, 1, 0;
o2 = Obstacle(0,1, 1, 1;
 
#horizontal one
o3 = Obstacle(1,1,1,2);
o4 = Obstacle(2,1,2,2);
 
player.initialization(5,5, 0,0, 4,4, [ o1, o2, o3, o4 ] );

  • metoda player.initialization je volána naším programem a JE zajištěno, že délka tohoto pole je dělitelná dvěma (nebo je předáno prázdné pole).
  • v metodě player.initialization je toto pole uloženo do self.my_obstacles
  • Pokud tedy chcete pracovat s první překážkou, používejte self.my_obstacles[0] a self.my_obstacles[1].
  • Postupujte od jednodušších problémů ke složitějším
  • Pro úspěšné testování si do třídy Player napište funkci, která “graficky” vypisuje stav hry
  • Třídu Player laďte bez managera (ten se hodí až na turnajový mód):
  • Nejprve implementujte expand_player() a odevzdejte na BRUTE. Teprve poté, co dostanete plný počet za tuto část, postupujte dále
  • Realizujte výpočet umístění všech překážek (expand_obstacles()). Toto je nejtěžší část semestrální práce.
  • Pro splnění SEMBasic není třeba mít “inteligentního” hráče, stačí hráče, “který ví, jak táhnout”.
  • až budete mít splněnou SEMBasic, začněte implementovat 'inteligenci'.
    • např. metodou Minimax.
    • v této metodě se vám budou hodit funkce expand_player a expand_obstacles
courses/b3b33alp/cviceni/semestralni_prace.txt · Last modified: 2018/01/07 15:46 by vonasvoj