Presenter: Gerold Jäger, Umeå University

Title: Optimal strategies and bounds for several variants of Black-Peg Static Mastermind and Black-Peg Static AB Game

Abstract:

Mastermind is a famous two-player game which has attracted much attention in the literature in recent years. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the codemaker  has to choose a secret by assigning  colors to the pegs, i.e., the secret is a p-tuple of colors. In the static variant the codebreaker asks a number of questions, all of them at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors.  The codemaker then answers all of those questions by telling the  codebreaker  an information how close each single questions is to the secret. In the  black-peg variant this information is exactly the number of pegs which  are correctly colored. The goal of the game is to minimize the number of questions.

A further well-known variant is the AB Game, which distinguishes  from Mastermind only by the rule that both in the questions and in the secret the colors must be pairwise distinct. Clearly, for this variant it holds  that p?c.

We present feasible and optimal strategies for the case of p=2 pegs and arbitrarily many colors c, and the case of p=3 pegs and arbitrarily many colors c for both, Static Black-Peg Mastermind and Static Black-Beg AB Game, but also  for some pairs special (p,c), where p and c are small numbers. Interestingly, all results about Static Black-Peg Mastermind can be  reformulated in terms of metric dimension of the graph (Z_c)^p.

Finally, we consider the most interesting case of Static Black-Peg AB Game, where the number of pegs p and the number of colors c equals, i.e., all questions and the secret are permutations.  We give a lower and an upper bound for the number of questions of an optimal strategy for this case.

Host: Marcel Turkensteen

Organizer: Steen Nielsen