# Programování II pro matematiky ## Teoretické cvičení 13 **26. 5. 2021** Martin Mareš a Tomáš Karella --- ## Plán cvičení - Opakování - Řešení domácích úkolů - On-line kvíz - Příklady --- ### Opakování - Minimax <img src="https://www.baeldung.com/wp-content/uploads/2017/07/minimax.png" style="width: 100%;"> --- ### Opakování - prořezávání <img src="https://upload.wikimedia.org/wikipedia/commons/9/91/AB_pruning.svg" style="width: 100%;"> --- ### Opakování - Dijkstrův algoritmus  --- ### Organizační záležitosti - Zbývá nám poslední cvičení - Dostanete dvě známky - Za teoretické cvičení - Za praktické cvičení - Výsledná známka bude jejich průměr (přihlédneme k aktivitě na cvičeních a k domácím úkolům) -- - Známka se spočítá do úlohy na **Heap** - **3** (65 %) - 14.3 bodů - **2** (75 %) - 16.5 bodů - **1** (85 %) - 18.7 bodů - **Na splnění požadavků pro získání zápočtu je ale pořád potřeba mít alespoň 26.6 bodů...** --- ### Kvíz ... --- ### Příklady - Navrhněte, jak budete řešit piškvorky pomocí algoritmu minimax. Pro minimax je potřeba vytvořit strom, kde každý vrchol znázorňuje jednu situaci po odehrání tahu. Jaké situaci budou odpovídat listy? Jak bude vypadat ohodnocení listů? - Jak bude vypadat stavový prostor u hry dáma? Jak bude vypadat ohodnocení listů? - Jak se úloha změní při hraní šachů? --- ### Řešení <img src="https://nestedsoftware.com/assets/images/2019-06-15-tic-tac-toe-with-the-minimax-algorithm-5988.123625/eo3qr44bp1w96a92t8s2.png" style="width: 100%;"> --- <img src="https://blog-c7ff.kxcdn.com/blog/wp-content/uploads/2017/03/ttt-minimax.jpg" style="width: 100%;"> --- <img src="https://d3i71xaburhd42.cloudfront.net/eeea111cd2561c950952c1d0215709a0f8dbba24/2-Figure2-1.png" style="width: 100%;"> --- <img src="https://cdn-media-1.freecodecamp.org/images/1*96QEzhnsOkNqz7swB0qx8w.jpeg" style="width: 100%;">