Lekce 8 - Minimax - Úvod
V předchozím článku, Backtracking - Luštič Sudoku - Dokončení, jsme dokončili náš luštič Sudoku.
V dnešním tutoriálu o rekurzivních algoritmech si představíme algoritmus zvaný Minimax. Jedná se o modifikaci klasického prohledávání do hloubky (backtrackingu), se kterým jsme se již důkladně seznámili v předchozích lekcích.
Účel algoritmu Minimax
Algoritmus Minimax nám umožní vytvořit program, který proti uživateli hraje např. šachy, dámu nebo piškvorky. Obecně je Minimax vhodný pro všechny hry, ve kterých jsou veškeré informace viditelné na hrací ploše.
Během hry se dva hráči (černý a bílý) pravidelně střídají v tazích. Algoritmus hraje např. v pozici bílého. Jeho soupeřem je obvykle člověk, ale může to být i jiný algoritmus. Účelem Minimaxu je vždy v aktuální herní pozici vybrat nejlepší možný tah.
Strom hry
Představme si, že máme rozehranou hru a promýšlíme další tahy. Možné varianty dalšího vývoje hry si můžeme přehledně znázornit pomocí stromu. Každý uzel stromu představuje nějaký stav na hrací ploše. Strom bude mít následující charakteristiky:
- kořenem stromu je aktuální stav,
- bílé uzly – na tahu je bílý hráč,
- černé uzly – na tahu je černý hráč,
- listy stromu představují konec hry (výhru jednoho z hráčů nebo remízu).
Zobrazení stromu je následující:
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
V tutoriálu o rekurzivních algoritmech si představíme algoritmus Minimax, který se používá při vytváření programů hrajících deskové hry proti uživateli.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
