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).
Zobrazenie stromu je nasledujúce:

 

...koniec náhľadu článku...
Pokračuj ďalej

Vedomosti v hodnote stoviek tisíc získaš za pár eur

Došiel 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émiovej sekcie.

Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš s Prevádzkovými podmienkami.

Čo od nás v ďalších lekciách dostaneš?
  • Prístup k jednotlivým lekciám podľa spôsobu obstarania.
  • 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.
Článok pre vás napísal Jan Hnilica
Avatar
Autor se věnuje hlavně programování v C a v Pythonu
Aktivity