Query Complexity of Mastermind Variants

Abstract

We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called \textit{codemaker} constructs a hidden sequence $H=(h_1,h_2,\dots ,h_n)$ of colors selected from an alphabet $\mathcal{A}=\{1,2,\dots ,k\}$ (\textit{i.e.,} $h_i\in \mathcal{A}$ for all $i\in \{1,2,\dots ,n\}$). The game then proceeds in turns, each of which consists of two parts: in turn $t$, the second player (the \textit{codebreaker}) first submits a query sequence $Q_t=(q_1,q_2,\dots ,q_n)$ with $q_i\in \mathcal{A}$ for all $i$, and second receives feedback $\hat{I}”(Q_t,H)$, where $\hat{I}”$ is some agreed-upon function of distance between two sequences with $n$ components. The game terminates when $Q_t=H$, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let $f(n,k)$ denote the smallest integer such that the codebreaker can determine any $H$ in $f(n,k)$ turns. We prove three main results: First, when $H$ is known to be a permutation of $\{1,2,\dots ,n\}$, we prove that $f(n,n)\ge n-\log \log n$ for all sufficiently large $n$. Second, we show that Knuth's Minimax algorithm identifies any $H$ in at most $nk$ queries. Third, when feedback is not received until all queries have been submitted, we show that $f(n,k)=\hat{I}\text{c◯}(n\log k)$.

Revised and trimmed- 17 pages