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

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 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
Tah 5, Hraje 1 Tah 6, Hraje 2 Tah 7, Hraje 1 Tah 8, Hraje 2
Tah 9, Hraje 1 Tah 10, Hraje 2 Tah 11, Hraje 1 Tah 12, Hraje 2
Tah 13, Hraje 1 Tah 14, Hraje 2 Tah 15, Hraje 1 Tah 16, Hraje 2

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í, 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 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ě 6×6 a maximálně 20×20
  • 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ů — 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 (2×2) 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 2×2 (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

  • Nevalidní tahy, které vytvářejí zcela zaplněné oblasti 2×2

  • Validní tahy:

  • Nevalidní tahy (protože se kameny nedotýkají hranou):

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 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 10×10)

    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 10×10 a také pole marks se značkami hráčů:

   board, marks = base.makeBoard10()

Jak probíhá hra / jak hrát doma

  1. Brute vytvoří oba hráče, předá jim hrací desku a seznam kamenů (hráči sdíli stejnou skupinu kamenů)
  2. Pokud je hráč na tahu, volá se jeho metoda move()
  3. Následuje kontrola validnosti tahu (jestli je kamen volný, jestli je uvnitř desky, jestli se nepřekrývá atd.. dle pravidel)
  4. 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 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 6×6, 7×7, .. 15×15. 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 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: 10×10 a 15×15, 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 Minimax a jeho rychlejší varianta 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
courses/b3b33alp/cviceni/t09.txt · Last modified: 2022/01/04 19:38 by vonasvoj