کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903067 | 1632401 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Query complexity of mastermind variants
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called codemaker constructs a hidden sequence H=(h1,h2,â¦,hn) of colors selected from an alphabet A={1,2,â¦,k} (i.e.,hiâA for all iâ{1,2,â¦,n}). The game then proceeds in turns, each of which consists of two parts: in turn t, the second player (the codebreaker) first submits a query sequence Qt=(q1,q2,â¦,qn) with qiâA for all i, and second receives feedback Î(Qt,H), where Î is some agreed-upon function of distance between two sequences with n components. The game terminates when the codebreaker has determined the value of 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,â¦,n}, we prove that f(n,n)â¥nâloglogn 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)=Ω(nlogk).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 665-671
Journal: Discrete Mathematics - Volume 341, Issue 3, March 2018, Pages 665-671
نویسندگان
Aaron Berger, Christopher Chute, Matthew Stone,