An Optimal Strategy for Static Black-Peg Mastermind with Two Pegs

摘要

Mastermind is a famous two-player game which has attracted much attention in literature within the last years. In this work we investigate the static (also called non-adaptive) variant of Mastermind. The principal rule is that the codemaker has to choose a secret consisting of p pegs and c colors for each peg and the codebreaker may give a number of guesses at once, where for each guess he receives information from the codemaker. Using this information he has a final guess for the correct secret. The aim of the game is to minimize the number of guesses. Whereas Goddard has investigated the static version of original Mastermind in 2003, we do such an investigation of its black-peg variant, where the received information consists only of a number of black pegs which corresponds to the number of pegs matching in the corresponding question and the secret. As main result we present a strategy for this game for p = 2 pegs and arbitrarily many colors c ≥ 3 colors and prove its feasibility and optimality. Furthermore, by computer search we found optimal strategies for 9 other pairs (p,c).