uvod.tex

\chapter*{Úvod}
\addcontentsline{toc}{chapter}{Úvod}

Logik, anglicky Mastermind, je hra, která byla roku $1970$ vynalezena Mordecaiem Meirowitzem \cite{Nelson-history}. Mastermind je určen pro dva hráče. První hráč zadá čtyřmístný tajný kód složený z nějaké kombinace šesti barev. Druhý hráč se tento kód snaží nalézt na co nejmenší počet pokusů tak, že vždy vytvoří nějaký pokus, který je následně ohodnocen podle toho, jak se podobá tajnému kódu. Hra se dočkala veliké popularity a vznikaly další varianty s různým počtem pozic a barev. 

Mnoho matematiků zkoumalo různé algoritmy, které základní hru o čtyř pozicích a šesti barvách řeší. Jedním z prvních byl Donald Knuth, který v roce $1977$ navrhl algoritmus zaručující nalezení tajného kódu na pět tahů\cite{donald_e__knuth_1977}. Ukázalo se, že nelze zaručit nalezení tajného kódu na čtyři tahy \cite{koyama}. Knuthův algoritmus je tedy optimální z hlediska maximálního počtu tahů. Déle však trvalo nalézt optimální strategii z hlediska průměrného počtu tahů k nalezení tajného kódu. 

K hledání optimální strategie přispěl Robert Irving, který v roce $1978$ publikoval strategii s průměrným počtem pokusů $4.394$. 

Optimální strategie z hlediska průměrného počtu pokusů byla nalezena v roce $1993$ Kenji Koyamou a Tony W. Laiem. Vytvořili ji pomocí prohledávání stavového prostoru hry. 

Tato práce zobecňuje skupinu algoritmů, který Mastermind řeší. Kapitola $1$ zavádí základní terminologii a definice potřebné pro přesný popis hry. V kapitole $2$ je vytvořen obecný algoritmus, pomocí kterého popíšeme chod tří algoritmů popisovaných v kapitole $3$. Konkrétně jde o Knuthův algoritmus, Irvingův a algoritmus vytvořený Barteldem Kooi. V kapitole $4$ jsou popsány výsledky těchto algoritmů které byly nalezeny pomocí programu vytvořeného pro tuto práci. Zkoumáme maximální a průměrné počty pokusů a také volbu prvního tahu. Diskutujeme tam také o možných nedostatcích a případných zlepšení algoritmů.