Logik - algoritmy a strategie
| Thesis title in Czech: | Logik - algoritmy a strategie |
|---|---|
| Thesis title in English: | Mastermind - algorithms and strategies |
| Key words: | Logik|algoritmus|genetický algoritmus |
| English key words: | Mastermind|algorithm|genetic algorithm |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Pavel Růžička, Ph.D. |
| Author: |
| Guidelines |
| Cílem práce by měl být popis algoritmů souvisejících s hrou logik, jejich rozbor a případná implementace. |
| References |
| 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. |
| Preliminary scope of work |
| 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]. |
| Preliminary scope of work in English |
| 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].
|