====== 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 {{ https://cw.felk.cvut.cz/forum/forum-1584.html | 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 {{courses:b3b33alp:cviceni:scrabble-v2.zip|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 [[https://cw.felk.cvut.cz/forum/thread-4638-post-17292.html#pid17292 | fóru. ]] * Update 13.12.2019: * [[http://mrs.felk.cvut.cz/~vonasvoj/scrabble/main.html|Turnaj je spusten!]] * Do sekce 'Jak postupovat' byla přidána podmínka, že **pokud žádáte o výměnu písmen, musí být příslušný řetězec nenulové délky.** * [[https://cw.felk.cvut.cz/forum/thread-4638.html| Další informace o turnaji ]] * Balíček se nemění * 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 15x15 * 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 {{https://www.w3schools.com/python/python_dictionaries.asp|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 ")