Vianoce v ITnetwork sú tu! Dobí si teraz kredity a získaj až 80 % extra kreditov na e-learningové kurzy ZADARMO. Zisti viac.
Hľadáme nové posily do ITnetwork tímu. Pozri sa na voľné pozície a pridaj sa k najagilnejšej firme na trhu - Viac informácií.

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 korún

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

Kúpiť všetky aktuálne dostupné lekcie s funkciou odovzdávanie úloh iba za 200 kreditov
Aktuálny stav konta 0 kreditov
Kúpou tohoto balíčku získaš prístup ku všetkým 10 článkom (10 lekcií) tohoto kurzu.

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

Čo od nás v ďalších lekciách dostaneš?
  • 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ť.

Článok pre vás napísal Jan Hnilica
Avatar
Autor se věnuje hlavně programování v C a v Pythonu
Aktivity