Pishquorky

Klasický souboj X a O mezi hráči, s počítačem, nebo jako simluace počítače proti počítači.

Jedná se o můj první zápočťák, takže implementace je nic moc. Navíc je to díky pythonu extrémně pomalé. Není příliš těžké můj algoristmus porazit, sami se o tom přesvědčte :).

DOWNLOAD GITHUB

Uživatelská dokumentace

Spuštění

Program se spustí z konzole příkazem: python pishquorky.py, nebo pomocí souboru LAUNCH.bat

Je zapotřebí mít nainstalovaný python

Pozn.: Program byl testován a odladěn pouze pro OS Windows.

Ovládání hry

Vždy začíná člověk, počítač hraje jako druhý. Když jste na tahu, tak můžete levým tlačítkem myši nakreslit svůj symbol do kteréhokli z prázdných políček.

Při zvolení módu simulace hry počítače s počítačem musíte pro spuštění simulace zvolit a zahrát první políčko.

Konec hry

Hra končí když X nebo O vytvoří řadu dlouhou nejméně 5 políček. V okně, které vyskočí si můžete zvolit hrát zvonu (Ano) nebo program ukončit. (Ne)

PRO VÝVOJÁŘE (TECHNICKÁ DOKUMENTACE)

Python soubory

Program obsahuje dva pythonovské soubory:

Výchozí soubor (pishquorky.py)
Soubor funkcí (pishquorkyFunctions.py)

Výchozí soubor

Pomocí balíčku TKinter se vytvoří okno s herními možnostmi. Hráč si může vybrat:

ze tří velikostí herní plochy (dále velikost herní plochy (počet políček) := n)
ze tří herních módů (Lokálně - člověk proti člověku, člověk proti počítači, simulace hry počítače s počítačem)
svůj startovní symbol (X | O)

Do patřičných proměnných se vybrané možnosti uloží funkcí submitButton, jež je svázaná s tlačítkem "Submit".

Po stisknutí talčítka "Submit" se vytvoří samotné čtvercové herní okno o rozměrech 32-násobku n políček pixelů. (32 := obrázek uvnitř tlačítka má 28px + 2px ze všech stran zabírá rámeček tlačítka) Po vytvoření tohoto tzv. kořenového okna se importuje druhý pythonovský soubor. Iniciuje se 2D seznam buttonGrid o rozměrech (n + 2) na ukazatele na tlačítka (instance class Button1 viz dále):

první a poslední sloupce a řádky budou obsahovat ukazatele na tlačítka-zarážky pro Index Out Of Range error. (zůstanou prázdná po celou hru)
na herním okně budou tedy zobrazená a interagovatelná pouze tlačítka "vnitřního čtverce" ze seznamu (indexy [1][1] až [n][n])

Do druhého souboru se pošlou pomocí funkce setButtonGrid():

ukazatel na seznam buttonGrid
rozměry hrací plochy
symbol vybraný hráčem
ukazatel na kořenové okno
zvolený herní mód

Soubor funkcí

Soubor obsahuje třídu Button1 a několik funkcí, které se starají o celý průběh hry.

Button1

Tato třída slouží jako malé rozšíření na TKinter Button. Každá instance má atributy:

ukazatel button na vlastní TKinter Button - tlačítko s textem nebo obrázkem zobrazitelné na okno, jeho atributem "command" je funkce symbol() (viz dále)
row, column s indexy v seznamu buttonGrid
symbol - údaj X | 0 | None (None := tlačítko je zatím prázdné)
isBlank - pomocný Boolean údaj - True := symbol = None, jinak False
isDummy - typ Boolean - True := při konstrukci nebyl zadán row, tento Button1 se automaticky označí za zarážku a nebude se metodou grid() zobrazovat na okně; jinak False

Nakonec se metodou grid() zobrazí patřičný TKinter Button na okno.

Ukazatele na instance této třídy najdeme v seznamu buttonGrid.

Globální proměnné

Obrázky TKinter typu PhotoImage:

blank - prázdné tlačítko
cross - obyčejný křížek
circle - obyčejné kolečko
last_cross - lehce zvýrazněný křížek (rozlišuje poslední tah)
last_circle - lehce zvýrazněné kolečko ——||——
winner_X_img - zvýrazněný křížek (ke zvýraznění výtězné řady)
winner_O_img - zvýrazněné kolečko ——||——

Po dobu hry se nemění:

chosen_symbol - symbol který bude první na tahu (symbol který si vybral hráč) (X | O)
window - ukazatel na hlavní herní TKinter okno
game_mode - (0 | 1 | 2) - 0 := člověk proti člověku, 1 := hráč proti počítači, 2 := simulation počítače proti počítači
height - výška hracího pole v počtu políček
width - sířka hracího pole v počtu políček
proximity - popisuje o jaké okolí nových symbolů se rozšiřuje algorithm_possible_moves

Jsou měněny funkcemi:

last_symbol - po každém tahu se mění, určuje který symbol je na tahu
ready_to_place - boolean, který zapíná/vypíná funkci symbol() (viz dále)
buttonGrid - 2d seznam všech tlačítek, atributy tlačítek jsou měněny během hry
last_button - ukazatel na poslední zahrané tlačítko, které je během hry zvýrazněné
algorithm_inteligence - hloubka prohledánání stromu hry v minimaxové funkci algorithmChooseNextTurn() (viz dále), aktuálně je z výpočetních důvodů nastavený na 3
algorithm_possible_moves - python set všech tlačítek, která jsou validní jako další tah. (prázdné, nejdou dummy, sousedí stranou nebo rohem s ostatními znaky)

setButtonGrid()

Tato funkce se volá z výchozího souboru před spuštěním hry. Nastaví výchozí hodnoty globálním proměným v tomto souboru podle zvolených možností ve výchozím souboru. (ukazatel na seznam buttonGrid, rozměry hrací plochy, symbol vybraný hráčemukazatel na kořenové okno, zvolený herní mód)

Nakonec nastaví hodnotu proměnné last_button na první dummy v seznamu buttonGrid (pro první tah nesmí být last_button None, protože funkce předpokládájí že je to ukazatel na instanci třídy Button1)

Funkce nakreslení symbolu

Funkce se volají navzájem v pořadí: symbol() -> updateGrid() -> checkForWinner() (pakliže byla vítězná řada nalezena, tak -> ) markWinner()

markWinner()

Jako parametry dostane: index jednoho tlačítek ve vítězné řadě a parametricky popsaný směr dvěma čísly z funkce checkForWinner(), např.: (-1,0): vertikální; (-1,1): rostoucí diáhovála ...

Projde všechna tlačítka se stejným symbolem v nepřerušené řadě okolo vstupních indexů v daném směru a nahradí jejich obrázky patřičnými vítěznými variantami. Vypíše vítěze do konzole.

Nakonec vytvoří vyskakovací okno s možností (ano/ne) hrát znovu. Když hráč zvolí ano, tak se všem tlačítkům v herním okně nastaví atributy na výchozí (prázdné) a všechny globální proměnné, které byli pozměněny během hry se také resetují do původních hodnot a vrátí True; Když hráč zvolí ne, tak se "zničí" herní okno, vrátí False a program skončí.

checkForWinner()

Jako parametry dostane indexy tlačítka v seznamu buttonGrid. Postupně bude hledat ve všech čtyřech směrech (vertikální, horizontální a obě diagonály) jestli ono tlačítko je součástí monotónní nepřerušené řady dlouhé alespoň 5. V každém směru počítá než narazí na jiný symbol nebo prázdné tlačítko v jedné polopřímce a pak pokračuje ve směru opačné polopřímky.

Jakmile napočítá dohromady 5, tak zavolá a vrází výsledek funkce markWinner() -> bool

Když nenapočítá 5 ani v jednom směru, tak funkce vrátí False.

updateGrid()

Jako parametry dostane indexy právě zahraného tlačítka v seznamu buttonGrid.

Do globální proměné algorithm_possible_moves přidá všechna tlačítka v jeho okolí, (popsané offesty indexů proximity = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]) která jsou validní jako tah (prázdná a nejdou dummy)

Také z proměnné algorithm_possible_moves odebere ono právě zahrané tlačítko.

Nakonec zavolá a vrátí hodnotu vrácenou funkcí checkForWinner() -> bool

symbol()

Tato funkce se zavolá pokaždé, když je stisknuto tlačítko na herním okně. Jako parametr dostane odkaz na ono tlačítko. (class Button1) (dále jen tlačítko)

Když talčítko není prázdné, nebo globální ready_to_place == false, tak neudělá nic. Jinak když je prázdné, tak:

Změní obrázek zvýrazněného symbolu v posledním zahraném tlačítku (last_button) na obyčejný obrázek (symbolu X|O). Ukazatel v proměnné last_button změní na nové tlačítko.

Nastaví atribut tlačítka symbol na hodnotu odpovídající globální proměnné last_symbol. (X|O) Dále tlačítko opatří patřičným obrázkem.

Zavolá funkci updateGrid(indexy tlačítka) a když ta vrátí False, tak změní last_symbol na opačný. (X -> O, nebo O -> X) (pakliže hráč vyhraje (updateGrid vrátí True, tak necheme aby se změnil startovní symbol))

Když uživatel vybral herní mód tzv. proti počítači a zároveň je na tahu symbol, který má počítač, tak se zavolá funkce algorithmChooseNextTurn(algorithm_inteligence) (viz dále)

Když uživatel vybral herní mód simulace hry počítače proti počítači, tak se pokaždé zavolá funkce algorithmChooseNextTurn(algorithm_inteligence) (viz dále)

Funkce minimaxového algoritmu

algorithmUpdateGrid()

Jako parametry dostane indexy právě zahraného tlačítka v seznamu buttonGrid a python set momentálních přípustných tahů. (current_possible_moves)

Vytvoří si interní kopii current_possible_moves, odebere právě zahrané tlačítko a přidá do ní všechna tlačítka v jeho okolí, (popsané offesty indexů proximity = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] od onoho právě zahraného tlačítka) která jsou validní jako tah (prázdná a nejdou dummy)

Nakonec vrátí tento nově vytvořený set validních tahů

Vytváří nové sety, aby se nemusel dělat příliš složitý backtracking během rekurze.

algorithmChooseNextTurn()

Na vstupu dostane depth_of_search: int, (momentálně nastavený na 3) který určuje, do jaké hloubky bude algoritmus Minimax prohledávat. (Hloubka 1 bere v úvahu pouze okamžité tahy, hloubka 2 zahrnuje i odpověď soupeře atd.)

Rekurzivně se volá pomocná funkce deepSearch, která vyhodnocuje možné tahy do zadané hloubky depth_of_search. Zvažuje postupně všechny validní tahy algorithm_possible_moves. Rekurze se nenoří hlouběji, když dorazí do zadané hloubky, nebo když ve vrcholu minimaxového stromu hra (hypoteticky) skončí hra (řada 5).

Poté rekurzivně vyhodnocuje stav hry po hypotetických tazích. Používá funkci evaluateState k ohodnocení koncových pozic. Střídá fáze maximalizace a minimalizace skóre (algoritmus Minimax), když ze všech koncových pozic počítá nejlepší. K tomu používá minimax_sgn, který alternuje mezi 1 a -1 skrze hladiny rekurze. Pokud depth == 0, rekurze se zastaví a vrátí ohodnocení stavu.

Sleduje nejlepší nalezený tah a ukládá ho do proměnné best_move. Během výběru nejlepšího tahu, když algoritmus narazí na dosavadní minimum/maximum podruhé, tak navíc preferuje tahy, které vedou k více možnostem (min./max. na konkrétní hladině se posílá do rodiče spolu s počtem jeho výskytů) na onu maximální řadu algoritmova symbolu (viz evaluateState()) nebo které vedou na méně možností na onu maximální řadu soupeře.

Po dokončení rekurzivního vyhledávání se vybere nejlepší tah.Tento tah se provede voláním symbol(best_move[0]), čímž si algoritmus umístí svůj symbol.

Pozn.: ve zdrojovém kódu jsou "zakomentované" pomocné výpisy do konzole označené debugging print:. V případě zájmu je možné je odkomentovat.

evaluateState()

Slouží jako ohodnocující funkce listů minimaxového stromu. Na vstupu dostane poslední dvě zahraná tlačítka a znaménko hladiny (minimax_sgn), na které se nacházíme. (tak funkce pozná které ze dvou tlačítek je kterého hráče) (nutné aby funkce fungovala obecně na různých hlubinách minimaxového stromu)

Funkce najde a spočte délku maximální uniformní řady obsahující poslední tlačítko a to samé pro předposlední tlačítko. (opponent_max ; this_max) Aby se řada počítala, tak musí splňovat jedno z následujících: (jinak není "hrozbou")

není blokovaná druhým symbolem ani z jedné strany
je dlouhá 4 a blokovaná pouze z jedné strany
je dlouhá 5

Nakonec funkce pomocí minimax_sgn vrátí patřičnou hodnotu 1 až 5 (nejdelší řady), pakliže je tento stav výhodný pro algoritmus na tahu, nebo hodnoty (-5 až -1) pakliže je výhodná naopak pro protihráče; nebo vrátí 0, když byli všechny řady blokované a zároveň kratší než 4.

pozn. výhodnost vychází přímo z ptavidel hry, kladné hodnoty vracíme jen když si algoritmus opravdu může dovolit útočit, záporné hodnoty znamenají, že algoritmus musí blokovat. (horší pro něj, nemůže postavit delší řadu)