| 1. |
|
|
| 2. |
- Jäger, Gerold, et al.
(författare)
-
Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory
- 2015
-
Ingår i: Combinatorial Algorithms. - Cham : Springer Berlin/Heidelberg. - 9783319193144 - 9783319193151 ; , s. 188-199
-
Konferensbidrag (refereegranskat)abstract
- We investigate a version of the Mastermind game, where the codebreaker may only store a constant number of questions and answers, called Constant-Size Memory Mastermind, which was recently introduced by Doerr and Winzen. We concentrate on the most difficult case, where the codebreaker may store only one question and one answer, called Size-One Memory Mastermind. We consider two variants of the game: the original one, where the answer is coded with white and black pegs, and the simplified one, where only black pegs are used in the answer. We show that for two pegs and an arbitrary number of colors, the number of questions needed by the codebreaker in an optimal strategy in the worst case for these games is equal to the corresponding number of questions in the games without a memory restriction. In other words, for these cases restricting the memory size does not make the game harder for the codebreaker. This is a continuation of a result of Doerr and Winzen, who showed that this holds asymptotically for a fixed number of colors and an arbitrary number of pegs. Furthermore, by computer search we determine additional pairs (p, c), where again the numbers of questions in an optimal strategy in the worst case for Size-One Memory Mastermind and original Mastermind are equal.
|
|
| 3. |
- Jäger, Gerold, et al.
(författare)
-
The number of pessimistic guesses in Generalized Black-peg Mastermind
- 2011
-
Ingår i: Information Processing Letters. - : Elsevier. - 0020-0190 .- 1872-6119. ; 111:19, s. 933-940
-
Tidskriftsartikel (refereegranskat)abstract
- Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p; c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p; c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2; c), b(3; c) and b(4; c) and give upper and lower bounds for b(5; c) and a lower bound for b(6; c). Furthermore, for arbitrary p, we present upper bounds for b(p; 2), b(p; 3) and b(p; 4). Finally, we give bounds for the general case b(p; c). In particular, we improve an upper bound recently proved by Goodrich.
|
|
| 4. |
- Jäger, Gerold, et al.
(författare)
-
The number of pessimistic guesses in Generalized Mastermind
- 2009
-
Ingår i: Information Processing Letters. - : Elsevier. - 0020-0190 .- 1872-6119. ; 109:12, s. 635-641
-
Tidskriftsartikel (refereegranskat)abstract
- Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. The code consists of 4 pegs, each of which is one of 6 colors. In Generalized Mastermind a general number p of pegs and a general number c of colors is considered. Let f(p; c) be the pessimistic number of questions for the generalization of Mastermind with an arbitrary number p of pegs and c of colors. By a computer program we compute ten new values of f(p; c). Combining this program with theoretical methods, we compute all values f(3; c) and a tight lower and upper bound for f(4; c). For f(p; 2) we give an upper bound and a lower bound. Finally, combining results for fixed p and c, we give bounds for the general case f(p; c).
|
|
| 5. |
- Jäger, Gerold, et al.
(författare)
-
The worst case number of questions in Generalized AB game with and without white-peg answers
- 2015
-
Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 184, s. 20-31
-
Tidskriftsartikel (refereegranskat)abstract
- The AB game is a two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. It is a variant of the famous Mastermind game, with the only difference that all pegs in both, the secret and the questions must have distinct colors. In this work, we consider the Generalized AB game, where for given arbitrary numbers p, c with p <= c the secret code consists of p pegs each having one of c colors and the answer consists of a number of black and white pegs. There the number of black pegs equals the number of pegs matching in the corresponding question and the secret in position and color, and the number of white pegs equals the additional number of pegs matching in the corresponding question and the secret only in color. We consider also a variant of the Generalized AB game, where the information of white pegs is omitted. This variant is called Generalized Black-peg AB game. Let ab(p, c) and abb(p, c) be the number of questions in the worst case needed by the codebreaker to guess the secret for Generalized AB game and Generalized Black-peg AB game, respectively. Combining a computer program with theoretical considerations, we confirm known exact values of ab(2, c) and ab(3, c) and prove tight bounds for ab(4, c). Furthermore, we present exact values for abb(2, c) and abb(3, c) and tight bounds for abb(4, c)
|
|
