Logik - algoritmy a strategie
Název práce v češtině: | Logik - algoritmy a strategie |
---|---|
Název v anglickém jazyce: | Mastermind - algorithms and strategies |
Klíčová slova: | Logik|algoritmus|genetický algoritmus |
Klíčová slova anglicky: | Mastermind|algorithm|genetic algorithm |
Akademický rok vypsání: | 2023/2024 |
Typ práce: | bakalářská práce |
Jazyk práce: | |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | doc. Mgr. Pavel Růžička, Ph.D. |
Řešitel: |
Zásady pro vypracování |
Cílem práce by měl být popis algoritmů souvisejících s hrou logik, jejich rozbor a případná implementace. |
Seznam odborné literatury |
1. Berghman, Lotte, "Efficient solutions for Mastermind using genetic algorithms", K.U.Leuven (1) (2008): 1–15.
2. Knuth, Donald, "The Computer as Master Mind", J. Recr. Math. (9) (1977): 1–6. 3. Koyama, Kenji; Lai, Tony, "An Optimal Mastermind Strategy". J. Recr. Math. (25) (1993): 230–256. |
Předběžná náplň práce |
Hra logik pochází od Mordecaje Meirowitze ze 70tých let dvacátého století. Logik navazuje na hru zvanou „Bulls and cows". Komerčně ji začala vyrábět firma Invicta Plastics, která později
prodala práva firmám Hasbro, Pressman Toys (USA) a Orda Industries (Izrael). Jde o rozšířenou hru jejíž pravidla jsou všeobecně známa. Na základě vlastní zkušenosti soudím, že k nalezení správné barevné kombinace postačí pět pokusů. To bylo potvrzeno D. Knuthem [2], který popsal algoritmus, který potřebuje v nejhorším případě právě pět pokusů. V roce 1993 publikovali K. Koyama a T.W. Lai [3] algoritmus, který sice potřebuje v nejhorším případě šest pokusů, ale průměrně přibližně jen 4,35. Odlišný (genetický) algoritmus představila v roce 2008 Lotte Berghman [1]. |
Předběžná náplň práce v anglickém jazyce |
The game of Mastermind was invented by Mordecai Meirowitz in the 70s. The idea of the game is based on the earlier game called Bulls and cows. It was commercially produced by the company Invicta Plastics, which later sold the rights to Hasbro, Pressman Toys (USA) and Orda Industries (Israel). The game became quickly popular worldwide. Based on my own experience, five attempts should suffice to find the correct color combination. This was confirmed by D. Knuth [2], who published an algorithm that needs five attempts in the worst case. In 1993, K. Koyama and T.W.Lai’s [3] presented an algorithm that needs six attempts in the worst case, but about 4.35 on average. A different (genetic) algorithm was published in 2008 by Lotte Berghman [1].
|