NOVINKA: Kurz kybernetickej bezpečnosti teraz už od 0 €. Staň sa žiadaným profesionálom. Zisti viac:
NOVINKA: Staň sa dátovým analytikom od 0 € a získaj istotu práce, lepší plat a nové kariérne možnosti. 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 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émiové sekcie.

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š?
  • 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.

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