9. diel - Minimax – Piškvorky proti užívateľovi – Úvod

V predchádzajúcom lekcii, Backtracking - Minimax - Úvod , sme si popísali princíp algoritmu minimax.

V dnešnom tutoriále o rekurzívnych algoritmoch využijeme naše znalosti algoritmu Minimax z lekcie Minimax - Úvod. Začneme vyvíjať program hrajúci piškvorky proti užívateľovi.

Úvod do hry Piškvorky

Hru piškvorky asi nemusíme príliš predstavovať. Dvaja hráči striedavo umiestňujú svoje symboly (obvykle znaky x a o) do štvorcovej mriežky. Vyhráva ten, komu sa podarí vytvoriť neprerušenú sériu svojich symbolov (či už vodorovne, zvisle alebo diagonálne) o vopred danej dĺžke.

Stavový priestor hry Piškvorky

Klasické piškvorky sa hrajú na ploche 15 x 15 a hráči musia pre výhru vytvoriť sériu piatich symbolov. Pre algoritmus Minimax je ale toto usporiadanie príliš náročné. Uvedomme si, že v prvom ťahu je na výber 225 pozícií, v druhom 224 atď. Pre iba tri ťahy dopredu má strom stavového priestoru viac ako 11 miliónov listov! Stupeň vetvenia tu je jednoducho obrovský a algoritmus takto rozsiahly stavový priestor nedokáže prehľadať do dostatočnej hĺbky v prijateľnom čase.

Tic-tac-toe

Skromnejší variant hry sa hrá na ploche 3 x 3 a na výhru sú potrebné práve tri znaky v sérii:

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