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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
Last revision Both sides next revision
courses:b3b33alp:cviceni:t10 [2019/09/21 11:41]
stepan removed 		courses:b3b33alp:cviceni:t10 [2019/12/12 15:27]
herinjan [Quick test 1]
Line 1: Line 1:
-====== Cvičení 10: semestrální práce ​======+====== Cvičení 10, Fronta, Stavový automat ​======
  
-  * Úkolem je naprogramovat hráče pro deskovou hru Blokus. +===== náplň cvičení ​=====
-  * Vaše kódy budou hrát "proti sobě" (na serveru BRUTE).  +
-  * Pravidla naší hry se od klasického Blokus 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. +
-  * Aktuální verze {{courses:​b3b33alp:​cviceni::​sem.zip|základního hráče}}. 4.12.2018+
  
 +==== Quick test 1 ====
 +{{ :​courses:​b3b33alp:​cviceni:​alp19_qt1_zadani.pdf | Zadání Quick-testu }}
 +==== Úloha 1 Fronta ====
  
-===== Historie: =====+  * Přeměňte řešení úlohy 3 Flood fill z cvičení 8 na frontu. 
 +  * Postupnou animací zjistěte jak se změnilo vyplňování prostoru 
 +  * Zjistěte, zda potřebuje více paměti zásobník, nebo fronta
  
-  * 2.12.2018, zveřejnění zadání +==== Úloha ​2 Komentáře - rozšíření ====
-  * 4.12.2018, opravena chyba v konstruktoru BasePlayer base.py, nova verze ZIPu +
-  * 24.12.2018, průběžné výsledky turnaje jsou {{ http://​mrs.felk.cvut.cz/​~vonasvoj/​blokus/​main.html|zde }}. Turnaj se budeme snažit spouštět alespoň jednou denně (hry běží mimo Brute). +
-===== Pravidla hry: ===== +
- +
-  * Hra se hraje na 2D poli o velikosti $n_x$, $n_y$ +
-  * Hra je pro dva hráče (dále budou označení Player1 a Player2) +
-  * Každý hráč má k dispozici vlastní sadu kamenů (ve stylu Tetris). Každý kámen se skládá z jedné a více kostiček/​buněk. Kameny jsou nedělitelné. Kameny hráčů se liší barvou (červené a zelené kameny). +
-  * **Začátek hry:** +
-    * Hráč 1 začíná na levém dolním rohu, hráč ​2 začíná na pravém horním rohu. +
-    * Na začátku hry je hrací deska prázdná. +
-  * **Tahy:** +
-    * V každém tahu umístí hráč jeden ze svých dosud nepoužitých kamenů na hrací desku.  +
-    * Nově umístěný kámen se musí dotýkat kamenů stejné barvy pouze v rozích (není možné dotyk přes stěnu).  +
-    * Kamen nesmí vyčnívat mimo hrací desku. +
-    * Je nutné se dotknout alespoň jednoho rohu stejné barvy.  +
-    * Kostiček jiné barvy (tj. kostiček protihráče) se může dotýkat i hranou. +
-    * Při prvním tahu je nutné umístit tvar tak, aby startovní buňka daného hráče byla obsazena (tj., hráč 1 musí při prvním tahu umístit jeden ze svých tvaru do levého dolního rohu, obdobně hráč 2 umisťuje do pravého horního rohu). +
-    * Hráč **musí** umístit nějaký kámen, pokud je to možné. +
-  * Každý kámen lze použít jen jednou. +
-  * Kameny je možno rotovat, není však dovoleno je překlápět vodorovně ani svisle. +
-  * **Hra končí pokud:** +
-    * jeden z hráčů již umístil všechny své tvary.  +
-    * nebo pokud ani jeden z hráčů nemůže táhnout. +
-  * **Výhra:​** +
-    * hráč, který umístí všechny své tvary, dostává +20 bodů. +
-    * Pokud ani jeden hráč nemůže dál táhnout, sečtou se počty kostiček/​buněk (nikoliv tvarů!), které hrář neumístil a tyto se odečtou od jeho dosavadního skóre. +
- +
-**Příkad:​**  +
-   * nechť jsou dány tyto kameny:  +
-{{:​courses:​b3b33alp:​cviceni:​piece_0-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_1-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_2-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_3-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_4-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_5-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_6-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_7-0.png?​100|}} +
-{{:​courses:​b3b33alp:​cviceni:​piece_8-0.png?​100|}} +
- +
- +
-  * příklad hry. Po 16 tazích nemůže ani jeden hráč hrát. Zelený hráč nemůže umístit svuj nejdelší kámen (I 4x1 ), naopak červený hráč nemůže umístit svůj I (3x1). V tomto případě vyhrává červený hráč, neboť jemu zbývá umístit 3 buňky, zatímco zelenému hráčovi zbývá umístit 4 buňky. +
- +
-{{:​courses:​b3b33alp:​cviceni:​step_00.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_01.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_02.png?​100|}}{{:​courses:​b3b33alp:​cviceni:​step_03.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_04.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_05.png?​100|}}  +
- +
-{{:​courses:​b3b33alp:​cviceni:​step_06.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_07.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_08.png?​100|}}{{:​courses:​b3b33alp:​cviceni:​step_09.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_10.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_11.png?​100|}}  +
- +
-{{:​courses:​b3b33alp:​cviceni:​step_12.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_13.png?​100|}} ​  ​{{:​courses:​b3b33alp:​cviceni:​step_14.png?​100|}}{{:​courses:​b3b33alp:​cviceni:​step_15.png?​100|}} +
- +
- +
- +
- +
-===== Implementace:​ ===== +
-  * Stáhněte si {{courses:​b3b33alp:​cviceni::​sem.zip| ZIP soubor}}. +
-  * Svého hráče implementujte do třídy Player (soubor ''​player.py''​) která je odvozena od BasePlayer.  +
-  * Veškerou implementaci směřujte do třídy Player (případně dalších modulů).  +
-  * Neměňte BasePlayer!  +
-  * Třída BasePlayer obsahuje: +
-    * ''​self.board'':​ 2D pole velikosti self.rows x self.cols, pokud je self.board[r][c]=0,​ pak buňka na řádku r a sloupci c je neobsazená. +
-    * ''​self.name'':​ string, ve které, Brute vyplní vaše jméno +
-    * ''​self.text'':​ string, do kterého si zapište jméno vašeho programu (podle této proměnné poznáte, jakou verzi vašeho hráče jsme testovali) +
-    * ''​self.which'':​ proměnná typu int. Pokud je 1, pak hrajete jako hráč 1, pokud je -1, hrajete jako hráč 2.  +
-      * Podle hodnoty ''​self.which''​ poznáte, kde na hrací desce začínáte +
-      * Pokud do hrací desky umístíte kámen, vyplníte příslušné pozice v ''​self.board''​ hodnotou ''​self.which''​ +
-      * Naopak, buňky v ''​self.board'',​ které mají hodnotu ''​-self.which''​ patří protihráči. +
-    * ''​self.stones'',​ což je pole kamenů, každý kamen je dále tvořen polem buňek (viz dále). Toto pole bude hráčovi předáno v konstruktoru. +
-   * ''​print()''​ metoda, která vytiskne stav hrací desky (včetně souřadnic). +
-   * ''​getScore(which)''​ +
-     * spočítá score pro zadaného hráče (which=1, pak je to hráč 1, -1 pro hráče 2). +
-     * Score je: počet buněk dosud neumístěných kamenů zadaného hráče. +
-  +
-  * Hráči mezi sebou komunikují pouze dvěma metodami: +
-    * ''​player.move()''​ +
-      *  vrací pole souřadnic, na které hráč zapisuje svůj kámen +
-      * tuto metodu implementujete ve své tříde ''​Player''​ +
-    * ''​player.update( other )''​ +
-      * vezme buňky obsazené druhým hráčem (pole ''​other''​) a zapíše jej do proměnné ''​self.board''​. +
-      * tato metoda je již definována v ''​BasePlayer''​. +
-    * celkový timeout na výpočet ''​update()''​ a ''​move()''​ jsou 2 sec!  +
-  +
-==== Definice hracích kamenů ==== +
- +
-  * Kámen je popsán 2D polem, kde každé políčko reprezentuje (x,y) pozici vnitřní buňky kamene, x,y jsou celá čísla. +
-  * Například buňky t-kamene na následujícím obrázku jsou: (0,0), (1,0), (2,0) a (1,1). +
-  * Tento kámen bude v Pythonu reprezentován takto: ''​[ [0,0], [1,0], [2,0], [1,1] ]''​. +
-  * Na pořadí buňek v kameni nezáleží,​ takže stejný kamen může být reprezentován i polem: ''​[ [2,0], [1,1], [0,0], [1,0] ]''​. +
-  * Soubory se základními kameny najdete v {{courses:​b3b33alp:​cviceni::​sem.zip|ZIP souboru}}. +
-  * Kameny můžete nahrát funkcí ''​loadStones(filename''​),​ která je v souboru ''​base.py''​. +
-  * Takto načtené kameny lze předat hráči v konstruktoru (poslední proměnná). +
-  * <fc #​ff1000>​Vnitřní buňky kamenů mohou být na libovolných souřadnicích (tj. i záporných). Poté, co hráč obdrží seznam kamenů, je nutné si souřadnice kamenů/​buněk tzv. vycentrovat například tak, aby minimální x a y souřadnice buňek byla 0.</​fc>​ +
- +
-{{:​courses:​b3b33alp:​cviceni:​blokus1.eps.png?​200|}} +
- +
- +
-==== Jak si vyzkoušet hru ==== +
- +
-  * Následující kód je též v zipu (''​example.py''​)+
  
 +  * Upravte program na odstraňování komentářů z přednášky tak:
 +    * aby program bral v úvahu řetězce začínající a končící znakem '
 +    * aby správně interpretoval znaky \' a \"
 +    * aby pokud řádka končí znakem \ dovedl řetězec prodloužit přes více řádek
 +  * Program otestujte na následujících datech
 <​code>​ <​code>​
-import base +a='b \' c#d' #e 
-import player as P +i="j \" k'​l#​m"​ #n 
-stones ​= base.loadStones("stones9.txt")+</​code>​ 
 +  * Program z přednášky:​ 
 +<code python>​ 
 +def preskoc_komentare(line):​ 
 +  # vytiskne obsah souboru '​f'​ s vynechanymi komentari 
 +  stav=0          # počáteční stav automatu 
 +  for c in line:  # přečti jeden znak 
 +    if stav==0: ​  # počáteční stav 
 +      if c=="#": ​ # začátek komentáře 
 +        stav=1 
 +        continue ​        
 +      elif c=='​\"':​ 
 +        stav=2 ​   # začátek řetězce 
 +    elif stav==1: # 1="​komentar"​ 
 +      continue 
 +    elif stav==2: 
 +      if c=='​\"':​ 
 +        stav=0 
 +    print(c,end=""​) ​# vytiskni znak
  
-size = 10; +i=input() 
- +preskoc_komentare(i)  # nacti radku a preskakuj 
-#create two players ​(here as two instances of Player class defined in player.py) +</​code>​ 
-p1 = P.Player("​DogFishDead",​size,​ size, 1, stones); #1 means player 1 +==== Úloha 3 Kontrola reálného čísla ​====
-p2 = P.Player("​FatTire",​size,​ size, -1, stones); #-1 is for player 2 +
- +
-while(True):​ +
-    p1.print(); +
-    ​r1 ​= p1.move();​ +
-         +
-    p2.update(r1);​ +
-    r2 = p2.move();​ +
- +
-    p1.update(r2);​ +
-    p2.print();​ +
- +
-    s1 =  ​p1.getScore(1);​ +
-    s2 =  ​p1.getScore(-1);​ +
-    if (len(r1) ​== 0 and len(r2) ​== 0): +
-        print("​No answer, end, r1=",​r1,​ "​r2=",​r2);​ +
-        break; +
-     +
-s1 =  p1.getScore(1);​ +
-s2 =  p1.getScore(-1);​ +
-if (s1 < s2): +
-    print("​Player 1 wins (", s1, s2,"​)"​);​ +
-elif (s1 > s2): +
-    print("​Player 2 wins (", s1, s2,"​)"​);​ +
-else: +
-    print("​No winner, draw! ", s1,s2); +
- +
-     +
-print("​End of game"​);​+
  
 +  * Reálné číslo v pythonu je zadána touto BNF gramatikou:
 +<code BNF>
 +floatnumber ​  ::​= ​ pointfloat | exponentfloat
 +pointfloat ​   ::=  [intpart] fraction | intpart "​."​
 +exponentfloat ::=  (intpart | pointfloat) exponent
 +intpart ​      ::​= ​ digit+
 +fraction ​     ::=  "​."​ digit+
 +exponent ​     ::=  ("​e"​ | "​E"​) ["​+"​ | "​-"​] digit+
 +digit         ::​= ​ "​0"​..."​9"​
 </​code>​ </​code>​
 +  * Vymyslete a naprogramujte stavový automat, který bude zjišťovat,​ zda je řetězec na řádce reálným číslem.
 +  * 
 +==== Úloha 4 Obsahy závorek ====
 +  * Uvažujme řetězec obsahující závorky () a [].
 +  * Napište program, který bude testovat, zda je výraz správně uzávorkován a zjistí text uvnitř závorek
 +  * Závorky mohou být do sebe vnořeny a pak text patří do poslední úrovně závorek
 +  * Program tedy text:
 +<​code>​
 +aa[bb(cc)dd(ee)fff[gggg]]hhh
 +</​code>​
 +  * převede na výstup:
 +<​code>​
 +()cc
 +()ee
 +[]gggg
 +[]bbddfff
 +</​code>​
 +  * písmena '​aa'​ a '​hhh'​ se zahodí, nejsou uvnitř žádných závorek
  
-  ​* Podobný kód bude spuštěn i na Brutovi s tím rozdílem, že +   
-    * jako ''​p2''​ bude náš hráč +===== Domácí práce ​=====
-    * dále budeme kontrolovat validitu vašich tahů, tedy že: +
-      * umisťujete pouze zadané kameny a každý maximálně jednou +
-      * že jsou kameny umístěny na volná místa, že nejsou mimo hrací desku a že správně navazují +
-      * rychlost výpočtu metody move() +
-      * že metoda move() vrací [] pouze tehdy, pokud opravdu nemůžete žádný kámen umístit. +
- +
-===== Nápověda ===== +
- +
-   * Hraní vyžaduje několik dovedností,​ které budou detailně probrány na cvičení. +
-     * je třeba umět detekovat místa, kam lze kameny umístit - tzv. rohy v hrací desce. +
-     * je třeba umět rotovat kameny. Kolik rotací může kamen nabývat? +
-     * pro každou rotaci kamene je třeba zjistit, jestli jej můžete umístit na rohy v hrací desce.  +
-     * každý kamen lze umístit jen jednou, doporučujeme používat pole ''​self.isUsed'',​ tj. pokud se použije kámen i, označte si ''​self.isUsed[i]=1''​ +
-     * doporuručujeme,​ abyste si při každém volání move() vypočítali všechny možné umístění všech kamenů (tzv. expanze stavu). Z takového seznamu pak stačí vybrat jeden kamen . +
-     * nejprve implementuje hráče, který umisťuje kameny buď náhodně nebo popořadě (tj. se seznamu, který je výsledkem expanze stavu se vybere první, nebo náhodný prvek). +
-     * hrací strategii laďte teprve poté, co tento základní hráč správně funguje. Cílem hrací strategie je umístit takový kámen, který buď nejvíce pomůže vašemu hráču (např. nejvíce minimalizuje plochu dosud neobsazených kamenů), nebo naopak nejvíce ublíží protihráči. To vyžaduje opět udělat expanzi stavu a každé možné umístění kamene ohodnotit. +
-     * Pro implementaci strategie je možné využít algoritmus [[https://​en.wikipedia.org/​wiki/​Minimax|Minimax]] +
- +
- +
-===== Odevzdání na Brute, bodování a turnaj ​=====+
  
-   * Úlohu odevzejte do {{https://​cw.felk.cvut.cz/​brute|Brute}}, úkol SEM buď jako jeden ''​player.py''​ soubor, nebo jako ZIP archiv. +Tentokráte bez domácího cvičení, poslední domácí cvičení ​bude zadané ​příští týden.
-   * Pokud odevzdáváte ZIP archiv, je nutné, aby zazipované soubory byly v kořeni archivu. +
-   * Pokud si vytváříte své pomocné třídy/​moduly,​ pojmenujte je ve stylu vaslogin_modul.py (např. "​fantom4m_strategie.py"​). +
-   * Do odevzávaného ZIP souboru můžete nahrát jakékoliv svoje .py programy, které používáte na testování. Brute je bude ignorovat, bude používat pouze soubor ''​player.py''​ (případně moduly, které ''​player.py''​ importuje). +
-   * Po odevzdání na Brute bude váš hráč hrát proti našemu hráči v několika desítkách her (evaluace bude trva řádově minuty). +
-   * Pokud během techto her neudělá váš hráč chybu (tj. bude korektně vracet tahy), dostanete 2 body. +
-   * Hráči, kteří dostanou 2 body, budou dále posunuti do turnaje, kde bude hrát každý s každým. +
-   * Výsledné bodování (bude provedeno poslední výukový den semestru):​ +
-     * hráči, kteří se umístí v top 10%, + 3body +
-     * hráči, kteří se umístí v top 20%, + 2body +
-     * hráči, kteří se umístí v top 40%, + 1body+
courses/b3b33alp/cviceni/t10.txt · Last modified: 2019/12/12 15:30 by herinjan