====== Cvičení 9: Semestrální práce - LITS ====== Semestrální práce spočívá ve vytvoření funkčního hráče (programu) pro hru inspirovanou [[ https://www.youtube.com/watch?v=2eJCyScfHHw | Battle of LITS ]]. LITS je desková hra pro dva hráče, ve které se hraje s kameny různých tvarů a barev. Na hrací desce jsou značky pro oba hráče ("x" a "o"), cílem hráče je nechat co nejvíce svých značek nepokrytých a naopak pokrýt co nejvíce značek patřících protihráči. Obtížnost hry spočívá v pravidlech pro umisťování kamenů (viz dále). Naše hra pro předmět ALP se mírně liší od oficiálnách pravidel LITSu. **Platná jsou pouze pravidla uvedená na této stránce.** ===== Ukázka hry ===== | Tah 1, Hraje 1 | Tah 2, Hraje 2 | Tah 3, Hraje 1 | Tah 4, Hraje 2 | |{{:courses:b3b33alp:cviceni:lits-example-move-00a.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-00b.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-01a.png?direct&150|}}| {{:courses:b3b33alp:cviceni:lits-example-move-01b.png?direct&150|}}| | Tah 5, Hraje 1 | Tah 6, Hraje 2 | Tah 7, Hraje 1 | Tah 8, Hraje 2 | |{{:courses:b3b33alp:cviceni:lits-example-move-02a.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-02b.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-03a.png?direct&150|}}| {{:courses:b3b33alp:cviceni:lits-example-move-03b.png?direct&150|}}| | Tah 9, Hraje 1 | Tah 10, Hraje 2 | Tah 11, Hraje 1 | Tah 12, Hraje 2 | |{{:courses:b3b33alp:cviceni:lits-example-move-04a.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-04b.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-05a.png?direct&150|}}| {{:courses:b3b33alp:cviceni:lits-example-move-05b.png?direct&150|}}| | Tah 13, Hraje 1 | Tah 14, Hraje 2 | Tah 15, Hraje 1 | Tah 16, Hraje 2 | |{{:courses:b3b33alp:cviceni:lits-example-move-06a.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-06b.png?direct&150|}}|{{:courses:b3b33alp:cviceni:lits-example-move-07a.png?direct&150|}}| {{:courses:b3b33alp:cviceni:lits-example-move-07b.png?direct&150|}}| Finalní skóre je 7 vs. 3 (7 koleček nepokrytých, 3 křížky nepokryté). Vyhrává hráč 1, který hraje "za kolečka". } ===== Historie a balíček ===== Balíček obsahuje třídy pro vyzkoušení hry na vašem počítači: * **base.py** --- základní třída, hráči jsou potomky této třídy.** Tento soubor neměňte!** * **player.py** --- hrací algoritmus. **Vaši implementaci pište pouze do tohoto souboru** * **draw.py** --- třída pro kreslení hrací desky do PNG * **stones.txt** - příklad hracích kamenů V případě, že nastanou změny v zadání nebo bude např. upraveno/rozšířeno herní rozhraní, budou změny uvedeny v této sekci. * 15.11.2021 zveřejnění zadání, {{:courses:b3b33alp:cviceni:balicek-lits.zip|balíček se soubory}} * 22.11.2021 otevření úlohy SEM na Brutovi * 23.11.2021 časový limit 1s platí i pro konstruktor (Player.__init__()) * 9.12.2021 [[ http://mrs.felk.cvut.cz/~vonasvoj/lits/main.html | Turnaj zahájen ]]. Turnaj bude spouštěn alespoň jednou denně. Nezapomeňte vyplnit ''self.algorithm'' (podle toho poznáte, kterou verzi vašeho hráče jsme natáhli do turnaje). Proměnná ''self.tournament'' je v turnaji nastavena na True. * 21.12.2021 Brute update, nyní je možné používat numpy (i v turnaji) * 4.1.2022 timeout na move() byl zvýšen na 1.8s ===== Pravidla ===== * Hraje se na čtvercové hrací desce o rozměrech minimálně 6x6 a maximálně 20x20 * Na desce jsou umístěny značky 'o' a 'x' * Hrají dva hráči * jeden hraje za 'kolečka' - snaží se je co nejvíc uchránit, naopak se snaží pokrýt soupeřovy značky * druhý hraje za 'křížky' - snaží se o jejich ochranu, naopak se snaží pokrýt kolečka * Začínat může kterýkoliv hráč, hráči se ve hře střídají * Oba hráči dostanou společný balík hracích kamenů --- [[ https://en.wikipedia.org/wiki/Polyomino | polyomin ]] (znáte je z HW08) * Hrací kameny se liší tvarem a barvou. Mohou existovat kameny stejného tvaru, ale různé barvy. Velikost kamenů (počet jejich buňek) bude max 10. Počet barev bude <20. Celkový počet všech kamenů bude <40. * Hra probíhá takto: * První tah: začne jeden z hráčů (který to bude, určí Brute), vybere si jeden z dostupných kamenů a položí jej libovolně na hrací desku (celý kamen musí ležet na desce) * Další tahy: hráč na tahu si vybere jeden z dostupných kamenů a umístí jej na hrací desku za splnění těchto podmínek: * nově položený kamen se musí dotýkat alespoň jednou hranou některého z již položených kamenů * kameny stejné barvy se nikdy nesmějí dotýkat hranou (kameny různých barev se mohou dotýkat) * žádná čtveřice sousední políček (2x2) nesmí být zcela pokryta (viz dále) * kameny nesmí přečnívat z desky, nebo zakrývat (ani částečně) již položené kameny * s již položenými kameny na hrací desce se nemanipuluje * Oba hráči volí kameny ze společné (sdílené) množiny kamenů, tj. pokud je již nějaký kamen na desce, další hráč jej nesmí znovu použít. * Hráč musí položit nějaký kámen, pokud je to možné * Kameny je možné rotovat, je ale zakázáno jejich zrcadlení * Pokud hráč nemůže táhnout (např. protože už jsou použity všechny kameny) nebo sice zbývají kameny, ale nelze je umístit na desku, hráč nehraje * Jeden tah hráče musí proběhnout během max 1s. * Jeden tah hráče musí proběhnout během max 1.8s. * Pokud oba hráči po sobě nemohou táhnout, hra končí. * Vyhrává ten hráč, který má více svých značek nepokrytých (otevřených) ==== Pravidlo 2x2 ==== * Žádný čtverec 2x2 (kdekoliv na hrací desce) nesmí být úplně pokryt kameny, tj. alespoň jedna z jeho buněk musí být volná. * Příklad - uvažujme tuto hrací desku s dvěma položenými kameny (žlutá) a fialový kámen {{:courses:b3b33alp:cviceni:lits-rule2x2.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-stone.xcf.png?direct&100|}} * Nevalidní tahy, které vytvářejí zcela zaplněné oblasti 2x2 {{:courses:b3b33alp:cviceni:lits-rule2x2-invalid.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-invalid2.xcf.png?direct&100|}} * Validní tahy: {{:courses:b3b33alp:cviceni:lits-rule2x2-valid1.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-valid3.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-valid6.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-valid4.xcf.png?direct&100|}} * Nevalidní tahy (protože se kameny nedotýkají hranou): {{:courses:b3b33alp:cviceni:lits-rule2x2-valid2.xcf.png?direct&100|}} {{:courses:b3b33alp:cviceni:lits-rule2x2-valid5.xcf.png?direct&100|}} ===== Co je v balíčku ===== * Balíček obsahuje base.py, draw.py (pro kreslení hrací desky do png souborů), prázného hráče player.py a příklady kamenů (stones.txt) * Stáhněte si balíček (viz sekce [[#historie_a_balicek|Balíček]] ), nastavte si vaše vývojové prostředí tak, aby pracovalo uvnitř adresáře, kde máte soubory z balíčku (např. VSCODE: File -> Open folder ) * Veškerou implementaci provádějte v souboru player.py import sys import random import copy import base from draw import Drawer class Player(base.BasePlayer): def __init__(self, name, board, marks, stones, player): """ constructor of Player. Place you variables here with prefix 'self' -> e.g. 'self.myVariable' """ base.BasePlayer.__init__(self, name, board, marks, stones, player) #do not change this line!! self.algorithm = "my great method" #name of your method. Will be used in tournament mode def move(self): """ return [ stoneIdx, [ stonePosition] ] stoneIdx .. integer .. index of stone to self.freeStones [stonePosition] = [ [row1,col1] ... [rown, coln] ] .. position into board where stone is placed if no stone can be placed: return [] """ return [ ] if __name__ == "__main__": #load stones from file stones = base.loadStones("stones.txt") print("stones are", stones) #prepare board and marks board, marks = base.makeBoard10(); #create both players p1 = Player("pepa", board, marks, stones, 1) p2 = Player("franta", board, marks, stones, -1) #not necessary, only if you want to draw board to png files d = Drawer() d.draw(p1.board, p1.marks, "init.png"); moveidx = 0 while True: p1play = True p2play = True m = p1.move() #first player, we assume that a corrent output is returned #the following if/else is simplified. On Brute, we will check if return value #from move() is valid ... if len(m) == 0: p1play = False else: stoneIdx, stone = m stoneColor = stones[stoneIdx][0] base.writeBoard(p1.board, stone, stoneColor) #write stone to player1's board base.writeBoard(p2.board, stone, stoneColor) #write stone to player2's board p1.freeStones[ stoneIdx ] = False #tell player1 which stone is used p2.freeStones[ stoneIdx ] = False #tell player2 which stone is used d.draw(p2.board, p2.marks, "move-{:02d}a.png".format(moveidx)) #draw to png #now we call player2 and update boards/freeStones of both players m = p2.move() if len(m) == 0: p2play = False else: stoneIdx, stone = m stoneColor = stones[stoneIdx][0] base.writeBoard(p1.board, stone, stoneColor) base.writeBoard(p2.board, stone, stoneColor) p1.freeStones[ stoneIdx ] = False p2.freeStones[ stoneIdx ] = False d.draw(p1.board, p1.marks, "move-{:02d}b.png".format(moveidx)) #if both players return [] from move, the game ends if p1play == False and p2play == False: print("end of game") break moveidx+=1 print(" -- end of move ", moveidx, " score is ", p1.score(p1.player), p1.score(-p1.player) ) ==== Význam proměnných ve třídě Player ==== * ''__init__()'' je konstruktor třídy Player, v něm si definujte svoje proměnné (referencujte je přes ''self'') * V konstruktoru není vhodné provádět složité předvýpočty (např. dopředu napočítat všechny možné herní strategie apod.) - proto pro konstruktor platí stejný časový limit jako pro metodu move, tj. 1s. * ''self.player'' je buď 1 (v tom případě hraje hráč za kolečka), nebo -1 (hraje za křížky) * ''self.board'' je hrací deska. Je to 2D pole, přistupujeme do něj ''self.board[row][col]'' (tj. nejdřív řádek, pak sloupec). * pokud je ''self.board[row][col] == 0'', tak buňka row,col je prázdná * nenulová hodnota ''self.board[row][col]'' označuje, která barva je na této pozici umístěna * pozn. je zaručeno, že barvy kamenů jsou celá čísla větší než 0 * ''self.marks'' je 2D pole značek, má stejné rozměry jako ''self.board''. Slouží k výpočtu skóre. * pokud ''self.marks[row][col] == 0'', tak na pozici row, col není žádná značka * pokud ''self.marks[row][col] == self.player'', je na pozici row,col umístěna značka hráče * tj. hráč se snaží tyto pozice nepokrývat (nechat otevřené) * pokud ''self.marks[row][col] == -self.player'', je na pozici row,col umístěna značka soupeře * tj. hráč se snaží tyto buňky zakrýt * ''self.stones'' je pole kamenů, jeho formát je stejný jako v HW08: * ''self.stones[i]'' je i-tý kamen * ''self.stones[i][0]'' je barva i-tého kamene: * ''self.stones[i][1]'' je pole souřadnic i-tého kamene [[row1,col1], ... [rown],[coln]] * ''self.freeStones'' je 1D pole hodnot True/False. * pokud je ''self.freeStones[i] == True'', pak kamen s indexem ''i'' je volný a lze jej (pokud je to možné) umístit na desku * Pole ''self.stones'' a ''self.freeStones'' jsou úzce svázané: * i-tý kámen je ''self.stones[i]'' * je tento i-tý kamen volný? - tj. může ho hráč dát na hrací desku? - to určuje proměnná ''self.freeStones[i]'' * Do proměnných ''self.board'' a ''self.freeStones'' bude Brute/Turnaj zapisovat aktuální stav hrací desky po každém provedeném tahu. Je tedy nutné: * neměnit typ/rozměry těchto proměnných * neměnit pořadí kamenů (tj. neprovádět řazení pole self.stones), protože pak nebude synchronizováno s pořadím v ''self.freeStones'' ==== metoda move() ==== * Nejdůležitější je metoda třídy Player je ''move()''. Ta vrací buď prázné pole (pokud nelze táhnout), nebo index kamene a jeho pozici na hrací desce * Příklad 1. Chceme umístit kamen číslo 2. Předpokládejme, že tento kamen je tvaru vodorovné "I" o třech kostičkách. Umístíme jej na první řádek počínaje druhým sloupcem: def move(self): return [ 2, [ [0,1],[0,2],[0,3] ] ] * Příklad 2. Umístíme stejný kamen jako v předchozím příkladu, ale svisle, například do posledního sloupce a počínaje prvním řádkem (pro desku o rozměrech 10x10) def move(self): return [ 2, [ [0,9],[1,9],[2,9] ] ] * V poli self.freeStones je údaj o tom, které kameny jsou ještě volné, např. pokud chceme umístit kamen s indexem 3: def move(self): if self.freeStones[3] == True: #kamen 3 je volny, muzeme ho zkusit dat na hraci desku * Zjištění dostupných kamenů def move(self): for i in range(len(self.freeStones))): if self.freeStones[i] == True: #kamen i je volny else: #kamen i neni volny, nema smysl pokouset se umistit jej ==== další pomocné metody a proměnné ==== * ''self.inBoard(row,col)'' vrací True, pokud je souřadnice row,col uvnitř hrací desky: if self.inBoard(row, col) and self.board[row][col] == 0: #bunka row,col je prazda a uvnitr hraci desky * ''self.isEmpty()'' vrací True, pokud je hrací deska prázdná if self.isEmpty(): #deska je prazdna, tj. jedna se o prvni tah, lze umistit jakykoliv kamen na jakekoliv misto * ''self.score(player)'' vypočítá skóre pro hráče player: myScore = self.score(self.player) opponentScore = self.score(-self.player) * ''self.algorithm'' zde si napište jméno algoritmu/programu/strategie, kterou testujete * doporučujeme nastavit v konstruktoru třídy Player * pod tímto jménem uvidíte programy v turnaji * ''self.tournament'' je True, pokud je hráč puštěn v turnajovém módu. Lze využít např, tak, že na Brutovi se provede pouze základní (jednoduchý a rychlý) hráč, zatímco v turnaji se zapne např. lepší strategie apod..: if self.tournament: #zapni chytrou herni strategie.. hraju proti ostatnim studentum else: #hraju proti Brutovi, pohoda .. neni treba vyhrat * ''base.loadStones(filename)'' slouží k načtení kamenů stones = base.loadStones("stones.txt") * ''base.makeBoard10()'' vytvoří testovací hrací desku o velikosti 10x10 a také pole marks se značkami hráčů: board, marks = base.makeBoard10() ==== Jak probíhá hra / jak hrát doma ==== - Brute vytvoří oba hráče, předá jim hrací desku a seznam kamenů (hráči sdíli stejnou skupinu kamenů) - Pokud je hráč na tahu, volá se jeho metoda move() - Následuje kontrola validnosti tahu (jestli je kamen volný, jestli je uvnitř desky, jestli se nepřekrývá atd.. dle pravidel) - Pokud je kontrola v pořádku, Brute zapíše tah do hracích desek (''self.board'') obou hráčů a aktualizuje jejich ''self.freeStones'' * tj. při dalším volání ''move()'' se hráč rozhoduje na základě aktuálního stavu hrací desky a vybírá z aktuálně dostupných kamenů * Program v sekci ''if __name__ == "__main__":'' v souboru ''player.py'' realizuje jednoduchou hru hráče sám proti sobě. Předpokládáme, že hráč hraje správně, tj. vrací validní pozici kamenu (uvnitř hrací desky, kameny se nepřekrývají atd..), jejich validní index.. nicméně tyto věci nejsou v souboru player.py kontrolovány a budou kontrolovány až na Brutovi. * Pokud chcete otestovat vašeho hráče (tak, aby hrál sám proti sobě), stačí spustit program player.py: python3 player.py * soubor player.py využívá kreslení hrací desky do png souborů, to je realizováno v draw.py, a k tomu je potřeba knihovna [[https://pillow.readthedocs.io/en/stable/ | PIL ]]. ===== Jak odevzdat hráče ===== * Semestrální práce odevzdávejte do úlohy SEM na Brutovi * **Odevzdává se pouze soubor player.py** --- tj. do něj implementujte všechny svoje algoritmy * Odevzdání jiných souborů není možné (důvod je zabránění kolizím jmen souborů/balíčků v turnaji) * Pokud potřebujete více tříd, udějete to v souboru player.py * Testování na Brutovi bude probíhat takto: * Testy na hracích deskách 6x6, 7x7, .. 15x15. Začínat se bude z prázdné hrací desky. Na každé konfiguraci hrací desky se bude hrát cca 20x. V polovině případů budete hrát 'za kolečka', v ostatních případech 'za křížky'. V polovině případů bude začínat Brute, jinak váš hráč. * Testy na předvyplněných hracích deskách - obdobně jako v předchozím bodě s tím, že na začátku hry bude deska již částečně zaplněna kameny. * Pokud ve všech testech neudělá váš hráč ani jednu chybu, obdržíte 2 body. Jinak 0 bodů. * Není nutné Bruta porazit, pouze je třeba hrát správně dle pravidel * Z důvodu omezené kapacity výstupu, který Brute umí zobrazit, bude zobrazen buď jen souhrn her (v případě, že nenastala chyba), nebo bude detailně zobrazena první hra, ve které nastala chyba. * Brute hráč je naprogramován tak, aby hrál korektní tahy, není na něm implementována žádná chytrá strategie ===== Turnaj ===== * Všechny programy odevzdané na Bruta půjdou automaticky do [[ http://mrs.felk.cvut.cz/~vonasvoj/lits/main.html | Turnaje ]] * V turnaji poběží zápasy mezi všemi dvojicemi hráčů, každá dvojice bude hrát 10 her tak, že jeden z hráčů bude hrát za kolečka a ve stejném počtu běhů (tj. 10) i za křížky, zároveň bude každý hráč mít možnost prvního tahu. * Velikost hracích desek pro turnaj je: 10x10 a 15x15, počet kamenů bude max. 30. * Hráči, kteří v turnaji udělají alespoň jednu chybu, budou z turnaje vyloučeni * hráčům vyloučeným z turnaje nicméně zůstávají body v Brutovi * Sestavíme pořadí zbylých hráčů podle sestupného skóre nasbíraného během všech her * Prvních 10% hráčů dostane +3 body * Dalších 20% hráčů dostane +2 body * Dalších 20% hráčů dostane +1 bod * Turnaj bude spuštěn alespoň jednou denně * Finální turnaj bude cca týden před první zkouškou, jeho termín bude dopředu oznámen * Body budou studentům připsány na základě pořadí ve finálním turnaji * Turnaj je vhodným místem pro ladění herních strategií. Strategie určuje, jaký kamen umístit na aktuální hrací desku. * Základními algoritmy pro hraní her jsou [[ https://en.wikipedia.org/wiki/Minimax | Minimax ]] a jeho rychlejší varianta [[ https://en.wikipedia.org/wiki/Alpha–beta_pruning | Minimax s alpha-beta prořezáváním ]]. * Pro úspěšné hraní LITSu však nejsou algoritmy typu Minimax nezbytně nutné, jsou dokonce dost pomalé. * Pokud chcete "lépe" hrát, tj. neumisťovat kameny náhodně ale tak, abyste si zlepšovali skóre, zde jsou drobé tipy: * Je lepší nejdříve hrát s velkými, nebo malými kameny? * Je lepší první kamen umístit spíše do středu nebo spíše ke krajům hrací desky? * Při rozhodování, který kamen umístit si počítejte nové skóre, nebo aspon spočítejte (nebo odhadněte) kolik vlastních či soupeřových značek obsadíte