Složitost logických her

• Název práce v češtině: Složitost logických her
• Název v anglickém jazyce: Complexity of logic games
• Klíčová slova: Logik|Minesweeper|algoritmus|NP-úplnost
• Klíčová slova anglicky: Mastermind|Minesweeper|algorithm|NP-complete
• Akademický rok vypsání: 2023/2024
• Typ práce: diplomová práce
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. Mgr. Pavel Růžička, Ph.D.

Zásady pro vypracování

Cílem práce by mělo být studium složitosti problémů inspirovaných logickými hrami. Doporučenými příklady takových her jsou hry Logik a hra Minesweeper.

Seznam odborné literatury

1. Berghman, Lotte, "Efficient solutions for Mastermind using genetic algorithms" K.U.Leuven (1) (2008): 1–15.
2. de Bondt Michiel, NP-completeness of Master Mind and Minesweeper, Radboud University Nijmegen (2004).
3. Kaye Richard, Minesweeper is NP-complete. Mathematical Intelligencer, 22(2) (2000): 9–15.
4. Knuth, Donald, "The Computer as Master Mind" J. Recr. Math. (9) (1977): 1–6.
5. Koyama, Kenji; Lai, Tony, "An Optimal Mastermind Strategy". J. Recr. Math. (25) (1993): 230–256.
6. Stuckman Jeff A., Zhang Guo-Qiang, Mastermind is NP-Complete, arXiv (2005)

Předběžná náplň práce

V roce 1977 popsal D. Knuth [4] algoritmus, který potřebuje v nejhorším případě právě pět pokusů k řešení hry logik. V roce 1993 publikovali K. Koyama a T.W. Lai [3] publikovali algoritmus, který sice potřebuje v nejhorším případě šest pokusů, ale průměrně jich potřebuje přibližně 4,35. Odlišný (genetický) algoritmus představila v roce 2008 Lotte Berghman [1]. Michael de Bondt [2] studoval složitost různých verzí her logik a Minesweeper. Mimo jiné ukázal, že hra logik je NP-úplný problém vzhledem k počtu kolíčků, a že jsou NP-úplné také různé verze hry Minesweeper. Tím navázal na důkaz NP-úplnosti hry Minesweeper Richarda Kaye [3]. NP-úplnost problému zda je daná instance hry logik řešitelná , ukázali K. Koyama a T. Lai [5].

Předběžná náplň práce v anglickém jazyce

In 1977 D. Knuth [4] published an algorithm that needs, in the worst case, just five attempts to solve the Mastermind game. In 1993, K. Koyama and T.W. Lai's [3] wrote an algorithm that needs six attempts in the worst case, but needs about 4.35 attempts on average. A different (genetic) algorithm was introduced in 2008 by Lotte Berghman [1]. Michael de Bondt [2] studied complexity of different versions of the games Mastermind and Minesweeper. He showed that Mastermind is an NP-complete problem with respect to the number of pegs, and that different versions of Minesweeper are also NP-complete. So he extended Richard Kay's proof of NP-completeness of the Minesweeper game [3]. NP-completeness of the problem of whether a given instance of Mastermind is solvable was shown by K. Koyama and T. Lai [5].