{"nbformat":4,"nbformat_minor":0,"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.6.1"},"colab":{"name":"PB016_cvi5_G02.ipynb","provenance":[],"collapsed_sections":[]}},"cells":[{"cell_type":"markdown","metadata":{"id":"1cKYLTEE1xFO"},"source":["# PB016: Umělá inteligence I, cvičení 5 - Hry a herní strategie\n","\n","Dnešní téma jsou hry, herní strategie a základní algoritmy pro optimální řešení her pomocí UI. Soustředit se budeme zejména na:\n","1. __Algoritmus minimax__\n","2. __Alfa-beta prořezávání__"]},{"cell_type":"markdown","metadata":{"id":"vL-HOkJH1xFQ"},"source":["---\n","\n","## 1. Algoritmus [minimax](https://en.wikipedia.org/wiki/Minimax)\n","\n","__Základní fakta__\n","- Koncept původně vycházející z [teorie her](https://en.wikipedia.org/wiki/Game_theory).\n","- Navržen pro hry dvou a více střídajících se hráčů, z nichž každý disponuje množinou strategií pro každý jednotlivý tah ve hře.\n","- Koncové stavy hry jsou ohodnoceny valuační funkcí, která přiřazuje jejich hodnotu pro každého hráče.\n","- Algoritmus minimax rekurzivně minimalizuje možnou prohru hráče v nejhorším možném případě (tj. případě, že se protihráč v každém tahu snaží dosáhnout naší maximální prohry výběrem optimální strategie).\n","- V jednoduchých hrách je možné úplné vyhodnocení hry, ale pro složitější hry rychle dochází ke kombinatorické explozi a algoritmus tudíž prohledává jen několik málo úrovní stromu možných tahů.\n","\n","__Pro ilustraci__ - příklad obecného minimax stromu:\n","\n","![minimax strom](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/minimax.png)"]},{"cell_type":"markdown","metadata":{"id":"NqbAtjo-1xFR"},"source":["### Hra pro toto cvičení\n","- Piškvorky (viz. též [Tic Tac Toe](https://en.wikipedia.org/wiki/Tic-tac-toe)) na ploše 3x3.\n","\n","__Příklad__ neohodnoceného herního stromu pro piškvorky:\n","\n","![tictactoe strom](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/tictactoe.png)"]},{"cell_type":"markdown","metadata":{"id":"3nQ5z58-1xFS"},"source":["### Základní kód hry\n","- třída reprezentující hrací plochu s funkcemi pro:\n"," - inicializaci hrací plochy,\n"," - ověření, zda je aktuální stav hrací plochy koncový,\n"," - ověření přípustnosti tahu,\n"," - vykreslení hrací plochy."]},{"cell_type":"code","metadata":{"scrolled":true,"id":"5joYwEmv1xFT","executionInfo":{"status":"ok","timestamp":1604321202063,"user_tz":-60,"elapsed":1934,"user":{"displayName":"Vít Nováček","photoUrl":"","userId":"05686630748873346736"}}},"source":["# pro mereni casu nutneho pro vyhodnoceni hry pomoci minimaxu a alfa-beta prorezavani\n","import time\n","\n","# definice tridy pro reprezentaci hry\n","class Game:\n","    def __init__(self):\n","        self.initialize_game()\n","\n","    # funkce pouzitelna jak k inicializaci, tak i k resetu hry\n","    def initialize_game(self):\n","        self.current_state = [['.','.','.'],\n","                              ['.','.','.'],\n","                              ['.','.','.']]\n","        self.result = None\n","        # hrac X vzdy hraje prvni\n","        self.player_turn = 'X'\n","\n","    # test konce hry - pokud ano, vraci viteze ('X' nebo 'O'), pripadne '.', jde-li o remizu;\n","    #                  pokud ne, vraci None\n","    def is_end(self):\n","        # vertikalni vyhra\n","        for i in range(0, 3):\n","            if (self.current_state[0][i] != '.' and\n","                self.current_state[0][i] == self.current_state[1][i] and\n","                self.current_state[1][i] == self.current_state[2][i]):\n","                return self.current_state[0][i]\n","\n","        # horizontalni vyhra\n","        for i in range(0, 3):\n","            if (self.current_state[i] == ['X', 'X', 'X']):\n","                return 'X'\n","            elif (self.current_state[i] == ['O', 'O', 'O']):\n","                return 'O'\n","\n","        # vyhra na hlavni diagonale\n","        if (self.current_state[0][0] != '.' and\n","            self.current_state[0][0] == self.current_state[1][1] and\n","            self.current_state[0][0] == self.current_state[2][2]):\n","            return self.current_state[0][0]\n","\n","        # vyhra na vedlejsi diagonale\n","        if (self.current_state[0][2] != '.' and\n","            self.current_state[0][2] == self.current_state[1][1] and\n","            self.current_state[0][2] == self.current_state[2][0]):\n","            return self.current_state[0][2]\n","\n","        # test plnosti hraci plochy\n","        for i in range(0, 3):\n","            for j in range(0, 3):\n","                # neni plna, pokracujeme\n","                if (self.current_state[i][j] == '.'):\n","                    return None\n","\n","        # remiza\n","        return '.'\n","\n","    # test pripustnosti tahu\n","    def is_valid(self, px, py):\n","        if px < 0 or px > 2 or py < 0 or py > 2:\n","            return False\n","        elif self.current_state[px][py] != '.':\n","            return False\n","        else:\n","            return True\n","    \n","    # vypis hraci plochy\n","    def draw_board(self):\n","        for i in range(0, 3):\n","            print(' | '.join(self.current_state[i]))\n","        print()"],"execution_count":1,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"qDEXImrd1xFY"},"source":["### Funkce pro hraní hry\n","- Cyklus střídání tahů hráčů `'X'` a `'O'`, dokud jeden z nich nevyhraje, případně dokud nedojde k remíze."]},{"cell_type":"code","metadata":{"id":"teR0fhJg1xFZ","executionInfo":{"status":"ok","timestamp":1604321210357,"user_tz":-60,"elapsed":1490,"user":{"displayName":"Vít Nováček","photoUrl":"","userId":"05686630748873346736"}}},"source":["def play(game):\n","    while True:\n","        game.draw_board()\n","        game.result = game.is_end()\n","\n","        # vypis prislusne zpravy ke konci hry\n","        if game.result != None:\n","            if game.result == 'X':\n","                print('Vitezem je X!')\n","            elif game.result == 'O':\n","                print('Vitezem je O!')\n","            elif game.result == '.':\n","                print('Remiza!')\n","\n","            game.initialize_game()\n","            return\n","\n","        # tah hrace\n","        if game.player_turn == 'X':\n","\n","            while True:\n","\n","                # vypocet optimalniho doporuceneho tahu minimalizacnim krokem\n","                print('Pocitam doporuceny optimalni tah...')\n","                start = time.time()\n","                (m, qx, qy) = mini(game)\n","                end = time.time()\n","                print('Vypocet zabral %.4f ms' % (1000*(end - start),))\n","                print('Doporuceny tah: X = %d, Y = %d' % (qx, qy))\n","\n","                correct_format, px, py = False, -1, -1\n","                while not correct_format:\n","                    try:\n","                        px = int(input('Zadej souradnici X: '))\n","                        py = int(input('Zadej souradnici Y: '))\n","                        correct_format = True\n","                    except ValueError:\n","                        print('Neplatny format, prosim opakuj zadani.')\n","                        correct_format = False\n","\n","                if game.is_valid(px, py):\n","                    game.current_state[px][py] = 'X'\n","                    game.player_turn = 'O'\n","                    break\n","                else:\n","                    print('Neplatny tah, zkus to prosim znovu.')\n","\n","        # tah UI\n","        else:\n","            (m, px, py) = maxi(game)\n","            game.current_state[px][py] = 'O'\n","            game.player_turn = 'X'"],"execution_count":2,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"WhmPih6S1xFc"},"source":["### __Příklad 1.1: Výběr tahu pro UI__\n","- Implementujte funkci pro výběr optimálního tahu pro UI (tj. maximalizaci koncové hodnoty hry z aktuální pozice)."]},{"cell_type":"code","metadata":{"id":"4skua5Zf1xFd"},"source":["# hrac 'O' maximalizuje (v tomto pripade je to UI)\n","def maxi(game):\n","\n","    # mozne hodnoty pro maximum jsou:\n","    # -1 - prohra\n","    # 0  - remiza\n","    # 1  - vyhra\n","\n","    # pocatecni nastaveni maxima jako -2 (horsi nez nejhorsi pripad)\n","    maxv = -2\n","\n","    px = None\n","    py = None\n","\n","    # testovani konce hry\n","    result = game.is_end()\n","\n","    # pokud hra skonci, funkce musi vratit vyhodnoceni daneho stavu (-1 pro prohru, 0 pro remizu, 1 pro vyhru)\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # vyber souradnic pro 'O' postupnym testovanim optimality moznych tahu (tj. \"vymezenim se\" vuci vysledku volani funkce mini)\n","\n","    # TODO - DOPLNIT SAMI\n","    \n","    # vracime hodnotu a souradnice optimalniho tahu\n","    return (maxv, px, py)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"Zk7LjHUh1xFg"},"source":["#### __Možné řešení výběru tahu pro UI__"]},{"cell_type":"code","metadata":{"id":"zo7_aKxJ1xFh"},"source":["# hrac 'O' maximalizuje (v tomto pripade je to UI)\n","def maxi(game):\n","\n","    # mozne hodnoty pro maximum jsou:\n","    # -1 - prohra\n","    # 0  - remiza\n","    # 1  - vyhra\n","\n","    # pocatecni nastaveni maxima jako -2 (horsi nez nejhorsi pripad)\n","    maxv = -2\n","\n","    px = None\n","    py = None\n","\n","    # testovani konce hry\n","    result = game.is_end()\n","\n","    # pokud hra skonci, funkce musi vratit vyhodnoceni daneho stavu (-1 pro prohru, 0 pro remizu, 1 pro vyhru)\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # vyber souradnic pro 'O' postupnym testovanim optimality moznych tahu (tj. \"vymezenim se\" vuci vysledku volani funkce mini)\n","    for i in range(0, 3):\n","        for j in range(0, 3):\n","            # testujeme tah, pokud je pole prazdne\n","            if game.current_state[i][j] == '.':\n","                # zkousime umistit 'O' a testujeme, zda je dany tah lepsi nez aktualne optimalni\n","                game.current_state[i][j] = 'O'\n","                (m, min_i, min_j) = mini(game)\n","                # pripadna aktualizace optimalniho tahu a aktualniho maxima\n","                if m > maxv:\n","                    maxv = m\n","                    px = i\n","                    py = j\n","                # reset pole na prazdne\n","                game.current_state[i][j] = '.'\n","    \n","    # vracime hodnotu a souradnice optimalniho tahu\n","    return (maxv, px, py)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"2UKjevOT1xFk"},"source":["### __Příklad 1.2: Simulace výběru tahu člověka__\n","- Implementujte funkci pro výběr optimálního tahu pro člověka (tj. minimalizaci koncové hodnoty hry z aktuální pozice)."]},{"cell_type":"code","metadata":{"id":"qaaxf9Zq1xFl"},"source":["# hrac 'X' minimalizuje (v tomto pripade je to clovek)\n","def mini(game):\n","\n","    # mozne hodnoty pro minimum jsou:\n","    # -1 - vyhra\n","    # 0  - remiza\n","    # 1  - prohra\n","\n","    # pocatecni nastaveni minima jako 2 (horsi nez nejhorsi pripad)\n","    minv = 2\n","\n","    qx = None\n","    qy = None\n","\n","    # testovani konce hry\n","    result = game.is_end()\n","\n","    # pokud hra skonci, funkce musi vratit vyhodnoceni daneho stavu (-1 pro vyhru, 0 pro remizu, 1 pro prohru)\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # vyber souradnic pro 'X' postupnym testovanim optimality moznych tahu (tj. \"vymezenim se\" vuci vysledku volani funkce maxi)\n","\n","    # TODO - DOPLNIT SAMI\n","\n","    # vracime hodnotu a souradnice optimalniho tahu\n","    return (minv, qx, qy)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"R9qEXD5Y1xFp"},"source":["#### __Možné řešení výběru tahu pro člověka__"]},{"cell_type":"code","metadata":{"id":"dOjTKvpw1xFp"},"source":["# hrac 'X' minimalizuje (v tomto pripade je to clovek)\n","def mini(game):\n","\n","    # mozne hodnoty pro minimum jsou:\n","    # -1 - vyhra\n","    # 0  - remiza\n","    # 1  - prohra\n","\n","    # pocatecni nastaveni minima jako 2 (horsi nez nejhorsi pripad)\n","    minv = 2\n","\n","    qx = None\n","    qy = None\n","\n","    # testovani konce hry\n","    result = game.is_end()\n","\n","    # pokud hra skonci, funkce musi vratit vyhodnoceni daneho stavu (-1 pro vyhru, 0 pro remizu, 1 pro prohru)\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # vyber souradnic pro 'X' postupnym testovanim optimality moznych tahu (tj. \"vymezenim se\" vuci vysledku volani funkce maxi)\n","    for i in range(0, 3):\n","        for j in range(0, 3):\n","            # testujeme tah, pokud je pole prazdne\n","            if game.current_state[i][j] == '.':\n","                # zkousime umistit 'X' a testujeme, zda je dany tah lepsi nez aktualne optimalni\n","                game.current_state[i][j] = 'X'\n","                (m, max_i, max_j) = maxi(game)\n","                # pripadna aktualizace optimalniho tahu a aktualniho minima\n","                if m < minv:\n","                    minv = m\n","                    qx = i\n","                    qy = j\n","                game.current_state[i][j] = '.'\n","\n","    # vracime hodnotu a souradnice optimalniho tahu\n","    return (minv, qx, qy)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"qDLcXBvQ1xFs"},"source":["### __A hrajeme!__"]},{"cell_type":"code","metadata":{"scrolled":true,"id":"LtcvuAkJ1xFt"},"source":["g = Game()\n","play(g)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"f6j254Jh1xFx"},"source":["---\n","\n","## 2. [Alfa-beta prořezávání](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)\n","\n","__Základní fakta__\n","- Optimalizace algoritmu minimax díky určení uzlů (resp. tahů) v herním stromu, které není potřeba dále prohledávat.\n","- Algoritmus alfa-beta prořezávání uchovává dvě hodnoty, $\\alpha$ a $\\beta$, které reprezentují:\n"," - minimální skóre, které má zaručeno maximalizující hráč,\n"," - maximální skóre, které má zaručeno minimalizující hráč\n","- Na začátku hry platí $\\alpha = - \\infty, \\beta = \\infty$ (tj. oba hráči začínají s jejich nejhorším možným skóre). \n","- Kdykoli se maximální zaručené skóre minimalizujícího hráče (\"beta\") stane menší než minimální zaručené skóre maximalizujícího hráče (\"alfa\") (tj. $\\beta < \\alpha$), maximalizující hráč nemusí prozkoumávat tahy vycházející z aktuálního uzlu, jelikož ví, že nereprezentují optimální strategii a nebudou ve hře dosaženy.\n","\n","__Pro ilustraci__ - prořezaný minimax strom z předchozího příkladu:\n","\n","![alfa-beta strom](https://www.fi.muni.cz/~novacek/courses/pb016/labs/img/alphabeta.png)"]},{"cell_type":"markdown","metadata":{"id":"8m6HPk1R1xFx"},"source":["### Upravená funkce pro hraní hry\n","- Cyklus střídání tahů hráčů `'X'` a `'O'`, dokud jeden z nich nevyhraje, případně dokud nedojde k remíze.\n","- Postup stejný jak před tím, jen využívá `mini` a `maxi` funkce rozšířené pro alfa-beta prořezávání.\n","- Namísto počátečních nekonečných hodnot pro $\\alpha, \\beta$ používáme $-2, 2$ (pro takto definované piškvorky to znamená de facto to stejné)."]},{"cell_type":"code","metadata":{"id":"vAvdUS_j1xFy","executionInfo":{"status":"ok","timestamp":1604321221532,"user_tz":-60,"elapsed":1530,"user":{"displayName":"Vít Nováček","photoUrl":"","userId":"05686630748873346736"}}},"source":["def play_alpha_beta(game):\n","    while True:\n","        game.draw_board()\n","        game.result = game.is_end()\n","\n","        if game.result != None:\n","            if game.result == 'X':\n","                print('Vitezem je X!')\n","            elif game.result == 'O':\n","                print('Vitezem je O!')\n","            elif game.result == '.':\n","                print('Remiza!')\n","\n","\n","            game.initialize_game()\n","            return\n","\n","        if game.player_turn == 'X':\n","\n","            while True:\n","                print('Pocitam optimalni tah...')\n","                start = time.time()\n","                # upravena mini funkce s prorezavanim\n","                (m, qx, qy) = mini_alpha_beta(game,-2, 2)\n","                end = time.time()\n","                print('Vypocet zabral %.4f ms' % (1000*(end - start),))\n","                print('Doporuceny tah: X = %d, Y = %d' % (qx, qy))\n","\n","                correct_format, px, py = False, -1, -1\n","                while not correct_format:\n","                    try:\n","                        px = int(input('Zadej souradnici X: '))\n","                        py = int(input('Zadej souradnici Y: '))\n","                        correct_format = True\n","                    except ValueError:\n","                        print('Neplatny format, prosim opakuj zadani.')\n","                        correct_format = False\n","\n","                if game.is_valid(px, py):\n","                    game.current_state[px][py] = 'X'\n","                    game.player_turn = 'O'\n","                    break\n","                else:\n","                    print('Neplatny tah, zkus to prosim znovu.')\n","\n","        else:\n","            # upravena maxi funkce s prorezavanim\n","            (m, px, py) = maxi_alpha_beta(game,-2, 2)\n","            game.current_state[px][py] = 'O'\n","            game.player_turn = 'X'"],"execution_count":3,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"EYRwU5KV1xF1"},"source":["### __Příklad 2.1: Výběr tahu pro UI s prořezáváním__\n","- Implementujte funkci pro výběr optimálního tahu pro UI (tj. maximalizaci koncové hodnoty hry z aktuální pozice).\n","- Tentokrát ale s prořezáním stromu tahů."]},{"cell_type":"code","metadata":{"id":"uluGdHyv1xF1"},"source":["def maxi_alpha_beta(game, alpha, beta):\n","    maxv = -2\n","    px = None\n","    py = None\n","\n","    result = game.is_end()\n","\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # TODO - DOPLNIT SAMI (vyber optimalniho tahu s aktualizaci alpha a ignorovanim vetvi s prilis velkym maxv)\n","\n","    return (maxv, px, py)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"AebZBtRV1xF4"},"source":["#### __Možné řešení výběru tahu pro UI__"]},{"cell_type":"code","metadata":{"id":"UmSJXlfj1xF5","executionInfo":{"status":"ok","timestamp":1604321228221,"user_tz":-60,"elapsed":2146,"user":{"displayName":"Vít Nováček","photoUrl":"","userId":"05686630748873346736"}}},"source":["def maxi_alpha_beta(game, alpha, beta):\n","    maxv = -2\n","    px = None\n","    py = None\n","\n","    result = game.is_end()\n","\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    for i in range(0, 3):\n","        for j in range(0, 3):\n","            if game.current_state[i][j] == '.':\n","                game.current_state[i][j] = 'O'\n","                (m, min_i, min_j) = mini_alpha_beta(game, alpha, beta)\n","                if m > maxv:\n","                    maxv = m\n","                    px = i\n","                    py = j\n","                game.current_state[i][j] = '.'\n","\n","                # dalsi dve podminky realizuji prorezani stromu tahu (jediny rozdil oproti predchozi verzi)\n","                if alpha >= beta:\n","                    return (maxv, px, py)\n","\n","                if maxv > alpha:\n","                    alpha = maxv\n","\n","    return (maxv, px, py)"],"execution_count":4,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"N6-ns3ri1xF8"},"source":["### __Příklad 2.2: Simulace výběru tahu člověka s prořezáváním__\n","- Implementujte funkci pro výběr optimálního tahu pro člověka (tj. minimalizaci koncové hodnoty hry z aktuální pozice).\n","- Tentokrát ale s prořezáním stromu tahů."]},{"cell_type":"code","metadata":{"id":"nrVT4mEF1xF9"},"source":["def mini_alpha_beta(game, alpha, beta):\n","\n","    minv = 2\n","\n","    qx = None\n","    qy = None\n","\n","    result = game.is_end()\n","\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    # TODO - DOPLNIT SAMI (vyber optimalniho tahu s aktualizaci beta a ignorovanim vetvi s prilis malym minv)\n","\n","    return (minv, qx, qy)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"uGx3GMLR1xGA"},"source":["#### __Možné řešení výběru tahu pro člověka__"]},{"cell_type":"code","metadata":{"id":"w75mZALh1xGA","executionInfo":{"status":"ok","timestamp":1604321233705,"user_tz":-60,"elapsed":1833,"user":{"displayName":"Vít Nováček","photoUrl":"","userId":"05686630748873346736"}}},"source":["def mini_alpha_beta(game, alpha, beta):\n","\n","    minv = 2\n","\n","    qx = None\n","    qy = None\n","\n","    result = game.is_end()\n","\n","    if result == 'X':\n","        return (-1, None, None)\n","    elif result == 'O':\n","        return (1, None, None)\n","    elif result == '.':\n","        return (0, None, None)\n","\n","    for i in range(0, 3):\n","        for j in range(0, 3):\n","            if game.current_state[i][j] == '.':\n","                game.current_state[i][j] = 'X'\n","                (m, max_i, max_j) = maxi_alpha_beta(game, alpha, beta)\n","                if m < minv:\n","                    minv = m\n","                    qx = i\n","                    qy = j\n","                game.current_state[i][j] = '.'\n","\n","                # dalsi dve podminky realizuji prorezani stromu tahu (jediny rozdil oproti predchozi verzi)\n","                if beta <= alpha:\n","                    return (minv, qx, qy)\n","\n","                if minv < beta:\n","                    beta = minv\n","\n","    return (minv, qx, qy)"],"execution_count":5,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"BPSfloFq1xGE"},"source":["### __A hrajeme!__"]},{"cell_type":"code","metadata":{"scrolled":true,"id":"-Cb-6H8-1xGF"},"source":["g = Game()\n","play_alpha_beta(g)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"6MmpG84S1xGI"},"source":["### __K zamyšlení__\n","- Jak upravit kód cvičení pro větší hrací plochy, případně těžší podmínku výhry (tj. nutnost dosažení 4 a více polí v řadě)?\n","- Jakým způsobem tyto změny ovlivní rychlost prohledávání?"]},{"cell_type":"markdown","metadata":{"collapsed":true,"id":"d1nO-4gZ1xGI"},"source":["---\n","\n","#### _Poznámka na závěr_ - materiály použité v tomto notebooku jsou převzatá originální díla licencovaná původními autory následujícím způsobem:\n","- Příklady herních stromů a kódu:\n"," - Převzato z webu [Stack Abuse](https://stackabuse.com/)\n"," - Autor: [Mina Krivokuća](mina.krivokuca@gmail.com)\n"," - Licence: N/A (převzato pouze pro interní použití v PB016 na FI MU s laskavým povolením autorky a Davida Landupa, provozovatele StackAbuse)"]}]}