Black Friday je tady! Roční předplatné se slevou 55 % s kódem ROCNI55. Více informací
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:

Lekce 9 - Minimax – Piškvorky proti uživateli – Úvod

V předchozí lekci, Minimax - Úvod, jsme si popsali princip algoritmu Minimax.

V dnešním tutoriálu o rekurzivních algoritmech využijeme naše znalosti algoritmu Minimax z lekce Minimax - Úvod. Začneme vyvíjet program hrající piškvorky proti uživateli.

Úvod do hry Piškvorky

Hru piškvorky asi nemusíme příliš představovat. Dva hráči střídavě umisťují své symboly (obvykle znaky x a o) do čtvercové mřížky. Vyhrává ten, komu se podaří vytvořit nepřerušenou sérii svých symbolů (ať už vodorovně, svisle nebo diagonálně) o předem dané délce.

Stavový prostor hry Piškvorky

Klasické piškvorky se hrají na ploše 15 x 15 a hráči musí pro výhru vytvořit sérii pěti symbolů. Pro algoritmus Minimax je ale toto uspořádání příliš náročné. Uvědomme si, že v prvním tahu je na výběr 225 pozic, ve druhém 224 atd. Pro pouhé tři tahy dopředu má strom stavového prostoru více než 11 miliónů listů! Stupeň větvení zde je prostě obrovský a algoritmus takto rozsáhlý stavový prostor nedokáže prohledat do dostatečné hloubky v přijatelném čase.

Tic-tac-toe

Skromnější varianta hry se hraje na ploše 3 x 3 a pro výhru jsou potřeba právě tři znaky v sérii:


 

...konec náhledu článku...
Pokračuj dál

Znalosti v hodnotě stovek tisíc získáš za pár korun

Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.

Před koupí tohoto článku je třeba koupit předchozí díl

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš s Provozními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • Přístup k jednotlivým lekcím dle způsobu pořízení.
  • Kvalitní znalosti v oblasti IT.
  • Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.

Popis článku

Požadovaný článek má následující obsah:

V tutoriálu o rekurzivních algoritmech využijeme znalosti algoritmu Minimax. Začneme programovat inteligentní piškvorky proti uživateli.
Článek pro vás napsal Jan Hnilica
Avatar
Autor se věnuje hlavně programování v C a v Pythonu
Aktivity