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

Cvičení 9 - Semestrální práce

Úvod

  • Tématem semestrální práce je vytvořit funkčního hráče pro hru Scrabble
  • Pravidla hry budou oproti klasickému Scrabble upravená, řiďte se tedy pouze pravidly uvedenými na této stránce
  • Hráč bude spoušťěn ve dvou módech: na Brutovi a v tzv. turnajovém módu
    • Na Brutovi se bude hrát proti jednoduchému (hloupému) protivníkovi
    • Cílem je zahrát několik (cca desítky) her přesně dle pravidel, není nutné Bruta porazit
    • Správně implementovaný hráč bude oceněn max. 2 body (nutná podmínka pro udělení zápočtu)
    • Další body (celkově až 5 bodů) bude možné získat v turnaji (každý hraje s každým) podle celkového pořadí
      • Prvních 10 procent hráčů (podle pořadí) získá +3 body
      • Dalších 20 procent hráčů získá + 2 body
      • Dalších 20 procent hráčů získá + 1 bod
    • Turnaj se budeme snažit pouštět každý den, vyhodnocení turnaje proběhne jeden až dva dny před první zkouškou.
    • První kolo turnaje proběhne až po odevzdání alespoň deseti hráčů (očekáváme v půlce prosince 2019).
  • Veškeré dotazy prosím směřujte na diskuzní fórum
  • Semestrální práce se odevzdává na Brute v jednom souboru player.py do úlohy SEM

Historie a balíček

  • Data plus základní třídy pro vašeho hráče jsou v tzv. Balíčku.
  • Pokud by nastaly změny v pravidlech nebo rozhraní tříd, budou vždy uvedeny v této sekci
  • Aktuální balíček (verze 2):
    • Balíček s šablonou hráče a slovníkem je ZDE
  • Update 24.12.2019:
    • Po diskuzi se studenty přidáváme možnost hrát v turnajovém módu více-písmennými tahy bez ohledu na existenci jednopísmenných, viz seznam pravidel.
    • Existující programy odevzdané na Bruta zůstávají v platnosti a za stejné body, nově však máte možnost vylepšít svého hráče pro turnajový mód
    • Do base.py je přidána proměnná self.tournament, kterou nastavuje náš program (hráč ji pouze čte) takto:
      • Pokud je False, znamená to, že váš program hraje na Brutovi
      • Pokud je True, váš program hraje v turnajovém módu
    • Viz též informace na fóru.
  • Update 13.12.2019:
  • Update 2.12.2019:
    • na tuto stránku byly přidány příklady pro výpočet skóre.
    • Byla opravena chyba v příkladu konstruktoru třídy Player (viz poslední příklad na této stránce),
    • Balíček se nemění.
  • Update: 1.12.2019:
    • semestrálka otevřena v Brute
  • Balíček:
    • Verze 2 (24.12.2019):
      • přidána proměnná self.tournament, která říká hráčovi, jestli se hraje na Brutovi (False) nebo v turnaji (True)
    • Verze 1 (26.11.2019):
      • změna v base.py a player.py: na žádost studentů přidána proměnná self.lettersInBag (zbývající počet písmen ve velkém zásobníku)
    • Verze 0 (25.11.2019):
      • zadání semestrálky

Pravidla (našeho) Scrabble

  • Hrací deska má rozměny 15×15
  • Budeme používat pouze velká písmena
  • Budeme používat notaci řádek-sloupec (tj. deska self.board[i][j] odkazuje na i-tý řádek a j-tý sloupec). Řádky i sloupce jsou číslovány od nuly. Pozice self.board[0][0] je horní levý roh. Pozice self.board[14][14] je pravý spodní roh.
  • Neobsazené políčko bude mít hodnotu “” (řetězec délky 0)
  • Pro validaci slov budeme používat slovník (obsahuje pouze slova psaný velkými písmeny). Délka slovníku je řádově desítky tisíc slov.
  • Slova se čtou/tvoří výhradně zhora dolů a zleva doprava a tyto směry jsou též použity pro validaci přes slovník
    • Slovník může být pro každou hru jiný, pro vývoj vašeho programu použijte slovník v balíčku (viz Historie)
  • Začátek hry:
    • Na začátku hry dostane hráč předvyplněnou hrací desku (všechna slova budou validní)
    • Vytvoří se seznam 100 písmen (četnosti písmen dle četností v anglické abecedě (ano, slovník počítá s angl. slovy)), ze kterého se bude dále losovat. Písmena jsou v tomto seznamu rozmístěna náhodně.
    • Z velkého seznamu se náhodně vylosuje 7 písmen pro každého hráče
  • Další tahy:
    • Hráči se střídají. Validní tahy jsou tyto:
      • Pass: hráč se vzdává tahu, score se nemění, hrací deska se nemění
      • Vyměň písmena: hráč požádá o výměnu jednoho nebo více svých písmen. Hrací deska se nemění, score se nemění.
        • Je nepřípustné žádat o výměnu více písmen než má hráč ve svém balíku.
        • Je nepřípustné žádat o výměnu písmen, která hráč nemá.
        • Je přípustné žádat o výměnu stejných písmen (např. chce hráč vyměnit všechny 'Q' - hádejte proč?)
      • Umísti písmeno (nebo více písmen) ze svého zásobníku na desku:
        • Nově umístěná písmena leží v jedné přímce a v této přímce musí buď vytvořit nové slovo nebo doplnit existující slovo
        • Nově vytvořené slovo se musí alespoň v jednom místě dotýkat (vlevo/vpravo/nahoře/dole) existujícího slova (tj. všechna slova na hrací desce tvoří tzv. souvislou komponentu grafu)
        • Všechny slova vzniklá křížením musí být také validní
        • V tomto typu tahu se mění deska i skóre
        • Písmena, která hráč položil na desku jsou automaticky nahrazena (je-li to možné) dalšími písmeny z velkého zásobníku
    • Pokud hráč může hrát tak, že umístěním jednoho písmena vznikne nové slovo (nebo je doplněno existující slovo) je povinnost tento tah udělat
      • Tedy: je-li možné hrát jedním písmenem, je nutné tento tah udělat, nelze dát Pass nebo žádat o výměnu písmen.
      • Pokud je naopak možné vytvořit nové slovo (nebo doplnit existujicí) s použitím minimálně dvou písmen, nemusí hráč tento tah udělat. V takovém případě buď dává Pass nebo požádá o výměnu písmen.
      • Validního hráče tedy není možné naprogramovat tak, že pouze žádá o Pass nebo o výměnu písmen!
      • Toto je hlavní změna oproti klasickému Scrabble.
      • Toto pravidlo je nutné dodržet při odevzdání do Bruta (pokud proměnná self.tournament je False)
    • V případě turnajového módu (pokud proměnná self.tournament je True) se předchozí pravidlo upravuje takto:
      • Pokud je možné hrát jednopísmenným tahem, tak není možné dát Pass nebo žádat o výměnu písmen, ale je nutné umístit buď jedno nebo více písmen
      • V turnajovém módu můžete tedy umísťovat í více písmen na jednou bez ohledu na existenci jednopísmenného tahu
    • Hra končí pokud:
      • je vyčerpán zásobník 100 písmen (je společný pro oba hráče)
      • 6krát za sebou se nezměnilo skóre (tj. tři tahy pro každého hráče)
  • Výpočet skóre:
    • Skóre se mění (navyšuje) po každém umístění písmen. Detekují se nově vzniklá/upravená slova a výsledek je váženým součtem hodnoty písmene a hodnoty políčka.
    • Totální skóre hráče (a protihráče) bude aktualizováno Brutem po každém tahu.
    • Algoritmus pro výpočet skóre si implementujte sami.
      • Hodnoty písmen a hodnoty políček lze získat z třídy BasePlayer - viz sekce Implementace.
  • Časové limity
    • Maximální čas pro jeden tah je 0.4 s (viz sekce Implementace)
    • Maximální čas pro inicializaci hráče je 0.4 s (viz sekce Implementace)

Příklad 1

  • Předpokládejme slovník: ABC, AB, CA, ABCA
  • Předpokládejme zásobník: A
  • Tečka '.' označuje prádné pole (zde pro zobrazení)

.......
..ABC..
.......

  • Možné jednopísmenné tahy:

...A...
..ABC..
.......

.......
..ABC..
....A..

.......
..ABCA.
.......

Příklad 2

  • Předpokládejme slovník: ABC, XABCY, XYABC, AX, CY, XYA
  • Předpokládejme zásobník: X,Y
  • Tečka '.' označuje prádné pole (zde pro zobrazení)

.......
..ABC..
.......

  • Možné dvoupísmenné tahy (doplnění existujícího slova z obou stran)

.......
.XABCY.
.......

  • Možné dvoupísmenné tahy (doplnění existujícího slova z jedné strany)

.......
XYABC..
.......

  • Možné dvoupísmenné tahy

..X....
..Y....
..ABC..
.......

  • Příklad nevalidních dvoupísmenných tahů (slova AX a CY jsou sice validní, ale rozšiřují existující slove ve dvou přímkách)

.......
..ABC..
..X.Y..

Příklad 3

  • Předpokládejme slovník: ABC,AX,BY,CZ,XYZ
  • Předpokládejme zásobník: X,Y,Z
  • Tečka '.' označuje prádné pole (zde pro zobrazení)

.......
..ABC..
.......

  • Příklad umístění nového slova vedle existujícího: je možné, neboť nově vzniklé 'AX', 'BY' i 'CZ' jsou ve slovníku a zároveň 'XYZ' je ve slovníku

.......
..ABC..
..XYZ..

  • Příklad nevalidního tahu: (slova se nedotýkají)

.......
..ABC..
.......
..XYZ..

Výpočet skóre

  • Předpokládejme, že hráč položí horizontálně N písmenek na desku na řádek r, např. [[r,c1,'B'],[r,c2,'Q'] ... [r,cn,'Z']]
  • Mezi těmito písmeny se najde to, které leží nejvíce vlevo (sloupec L) a další, které leží nejvíce v pravo (sloupec R)
  • Od sloupce L se najde písmeno LL v hrací desce, které leží na řádku r nejvíce vlevo od L tak, že mezi tímto písmenm a L není mezera.
  • Od sloupce R se najde písmeno RR v hrací desce, které leží na řádku r nejvíce vpravo od R tak, že mezi tímto písmenem a R není mezera.
  • Tím vznikne slovo od sloupce LL do sloupce RR.
  • Dále se detekují vertikálně všechna slova, který vzniknout na sloupcích c1, c2, … cn.
  • Výsledekem je seznam slov vzniklých horizontálně a vertikálně.
  • Každé slovo se ohodnotí jako vážených součet hodnot písmen a hodnot políček.
  • Skóre je pak součtem hodnot těchto slov.
  • Obdobně se postupuje v případě vertikálně položených písmen.
  • Příklad 1:

.......
..A.X..
...W...
..XYZ..

  • Příklad 1: umístění písmena R mezi A a X: vzniknou slova: ARX, RWY. Skóre je součtem hodnoty ARX a RWY

.......
..ARX..
...W...
..XYZ..

  • Příklad 2:

.X.X.XX.
.AAAAAA.
..B.B...

  • Příklad 2: umístění Q: hlavní slovo (horizontálně): XQXQXX, vedlejší slova: QAB, QAB

.XQXQXX.
.AAAAAA.
..B.B...

Implementace

  • Všechny potřebné třídy a příklady použití hráče jsou v Baličku
  • Hráč bude implementován ve třídě Player, která je potomkem třídy BasePlayer (soubor base.py)
  • BasePlayer obsahuje základní metody, NIKDY tuto třídu neměnte. Brute vždy nahrazuje soubor base.py defaultní verzí base.py, čili jakékoliv vaše změny v tomto souboru budou ignorovány.
  • BasePlayer (a následně též třída Player) mají tyto proměnné a metody:
  • Proměnné:
    • self.board - dvourozměrné pole (hrací deska), obsahuje buď “” (prázdný řetězec) nebo velké písmeno.
      • Pole self.board používejte libovolně, ale po každém volání self.move() bude toto aktualizováno Brutem
    • self.rows a self.cols - počet řádků a sloupců v self.board (integer)
    • self.weight - váhy jednotlivých buňek hrací desky (dvourozměrné pole, velikost shodná s self.board)
    • self.dictionary - seznam slov ve formátu python-dictionary
      • pro zjištění, jesli slovo v proměnné word je ve slovníku, použijte word in self.dictionary
    • self.bag - jednorozměrné pole písmen
    • self.myScore - absolutní skóre tohoto hráče (je nastaveno metodou update)
    • self.otherScore - absolutní skóre protihráče (je nastaveno metodou update)
    • self.lettersInBag - zbývající počet písmen ve velkém zásobníku
    • self.tournament - pokud True, hraje se v turnajovém módu, jinak se hraje na Brutovi. Tuto proměnnou nastavuje turnajový program, hráč by ji měl pouze číst
  • Metody
    • self.cellValue(row, col) - hodnota buňky
    • self.letterValue(letter) - hodnota písmenka (písmeno musí být velké), nebo 0
    • self.inBoard(row, col) - vrací True, pokud je souřadnice row,col v hrací desce
    • self.isEmpty(row, col) - vrací True, pokud je self.board[row][col] prázdné
    • self.print() - výpis hrací desky
    • self.move() - metoda, která bude volána Brutem (viz dále)
    • self.update() - update hráče po tahu protihráče
  • Vysvětlení tříd a význam self před názvy metod a proměnných bude probráno na cvičení

V souboru base.py jsou dále pomocné funkce:

  • base.readDictionary(soubor) - načte soubor se slovníkem, vrací jako typ Dictionary
  • base.createInitialBag() - vytvoří pole písmenek, ze kterého se dále losuje
  • base.createBoard(word) - vytvoří hrací desku a umístí doprostřed zadané slovo
  • Příklady použítí těchto metod jsou v player.py
  • Vysvětlení významu base bude provedeno na cvičení

Jak postupovat

  • Stáhněte si balíček s programy a slovníkem
  • Svého hráče implementujte do souboru player.py, do třídy Player (případně jako samostatné funkce v souboru player.py)
  • Nejdůležitější je metoda player.move(), která bude volána Brutem. Jejím výstupem je:
    • None, v případě, že hráč se chce zdržet hry
    • “slovo”, (tj. jeden řetezec) v případě, že hráč chce vyměnit písmena za nová (v tomto případě budou vyměněna písmena s,l,o,v,o.
      • k výměně písmen dojde v self.bag
      • Délka řetězce musí být větší než nula! tj. nelze žádat o výměnu např. return "" . Doplněno 13.12.2019
    • [[r1,c1,l1], ... [rn,cn,ln]] tj. seznam souřadnic a písmen, kam se mají zapsat (rn je n-tý řádek, cn je n-tý sloupec, ln je n-té písmeno)
      • Např. pokud chcete zapsat písmeno A na řádek 0 a sloupec 7: return [ [0,7,'A'] ]
      • Maximální počet písmen umístěných na desku je len(self.bag)
    • Váš hráč nemusí (ale může) zapsat umístěná písmena na self.board
    • Po skončení funkce self.move() bude hrací deska (self.board), písmena (self.bag) automaticky upravena Brutem
      • Změny, které si tedy uživatel do těchto proměnných provede, budou přepsány!
      • Je to proto, aby oba hráči měli pořád stejný obraz hrací desky
  • Čas výpočtu metody move() je maximálne 0.4s!
  • Čas inicializace hráče (konstruktor __init__) je maximálně 0.4s
  • Pokud bude překročen maximální čas výpočtu, bude hra ukončena

soubor player.py

  • V tomto souboru je šablona pro vašeho hráče (třída Player)
  • Zároveň je v tomto souboru ( v sekci if name == “main”: ) ukázka použití tříd/hráčů s spolu s while cyklem, ve kterém celá hra běží.
  • Pro testování svého hráče použijte příklad
  • Následující příklad je zjednodušením player.py
  • Funkce afterMove zde není pro přehlednost zobrazena (ale je v player.py)

import base
import random
import copy
 
 
 
class Player(base.BasePlayer):
    def __init__(self, name, dictionary, board, bag, bigBagSize):
        base.BasePlayer.__init__(self, name, dictionary, board, bag, bigBagSize) #always keep this line and DON't change it
        self.text = "myGreatPlayer" #fill the name of your awesome player!
 
        #bellow you can define your own variables. Don't forget to use 'self.' to adress them correctly
 
 
    def move(self):
        """
            the main function of your player. This function is called by the gaming server to obtain
            your move. 
            Possible moves are:   
              return None     - this means to 'pass' (score/board/bag are not changed)
              return "hello"  - string of letters that you want to replace. Letters can repeat. 
                                Only letters in 'self.bag' can be used here. Not more than 7 letters.
              return [ [r1,c1,L1], [ r2,c2,L2]  ... [rn,cn,Ln] ], where 'r_x' is row, 'c_x' is columns and 'Lx' is the letter
                                that you want to place to the board.
                                You don't have to place these letters to self.board, it will be done anyway by Brute
        """
        return None;
 
 
if __name__ == "__main__":
 
 
 
    words = base.readDictionary('dic.txt') #words is represented as python-dictionray 
 
    board = base.createBoard("ABACUS") #this word should be from the dictionray
    board = base.createBoard(random.choice(list(words))) #random word from the dictionray
 
    bag = base.createInitialBag()
 
    player1bag = bag[0:7]   #letters for the player1
    player2bag = bag[7:14]  #letters for the player2
    bag = bag[14:] #remove first 14 letters
 
 
    p1 = Player("player1", words, board, player1bag);
    p2 = Player("player2", words, board, player2bag);
    p1.print()
 
    noChangeMoves = 0;
    while noChangeMoves < 6:
 
        result = p1.move()   #first player plays
        s1 = afterMove(p1, result, p2, board)  #determine the type of move, update both player, return change of score
 
        p1.print()
 
        result = p2.move();  #second player plays
        s2 = afterMove(p2, result, p1, board)  #determine the type of move, update both player, return change of score
 
        p2.print()
 
        if s1 + s2 == 0:
            noChangeMoves+=1
        else:
            noChangeMoves = 0
 
 
    print("Game finished after " , noChangeMoves , " moves without change of score ")

courses/b3b33alp/cviceni/t09.txt · Last modified: 2019/12/25 02:24 by vonasvoj