8. diel - Backtracking - Minimax - Úvod
V predchádzajúcom článku, Backtracking – Lúštič Sudoku – Dokončenie , sme dokončili náš lúštič Sudoku.
V dnešnom tutoriále o rekurzívnych algoritmoch si predstavíme algoritmus zvaný minimax. Ide o modifikáciu klasického prehľadávania do hĺbky (backtrackingu), s ktorým sme sa už dôkladne zoznámili v predchádzajúcich lekciách.
Účel algoritmu minimax
Algoritmus minimax nám umožní vytvoriť program, ktorý proti užívateľovi hrá napr. šach, dámu alebo piškvorky. Všeobecne je minimax vhodný pre všetky hry, v ktorých sú všetky informácie viditeľné na hracej ploche.
Počas hry sa dvaja hráči (čierny a biely) pravidelne striedajú v ťahoch. Algoritmus hrá napr. v pozícii bieleho. Jeho súperom je obvykle človek, ale môže to byť aj iný algoritmus. Účelom minimaxu je vždy v aktuálnej hernej pozícii vybrať najlepší možný ťah.
Strom hry
Predstavme si, že máme rozohranú hru a premýšľame ďalšie ťahy. Možné varianty ďalšieho vývoja hry si môžeme prehľadne znázorniť pomocou stromu. Každý uzol stromu predstavuje nejaký stav na hracej ploche. Strom bude mať nasledujúce charakteristiky:
- koreňom stromu je aktuálny stav,
- biele uzly – na ťahu je biely hráč,
- čierne uzly - na ťahu je čierny hráč,
- listy stromu predstavujú koniec hry (výhru jedného z hráčov alebo remízu).
...koniec náhľadu článku...
Pokračuj ďalej
Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.
Kúpiť tento kurz
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Neobmedzený a trvalý prístup k jednotlivým lekciím.
- Kvalitné znalosti v oblasti IT.
- Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.
Popis článku
Požadovaný článok má nasledujúci obsah:
V tutoriále o rekurzívnych algoritmoch si ukážeme, ako pomocou algoritmu minimax vyberieme z aktuálnej pozície najlepší ťah v nejakej hre.
Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.
