forked from adrianN/adrianN.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmastermind.html
More file actions
75 lines (75 loc) · 19.7 KB
/
mastermind.html
File metadata and controls
75 lines (75 loc) · 19.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link href="https://adriann.github.io/feed.rss" rel="alternate" type="application/rss+xml" title="What's new on adriann.github.io" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Adrian Neumann (adrian_neumann@gmx.de)" />
<title>Mastermind</title>
<style type="text/css">
.displayequation{margin-left:auto;margin-right:auto;}
</style>
<style>
.caption{font-size:66%;text-align:right;}
.figure{float:right;padding-bottom:1em;padding-left:1em;}
.figure>img{display:block;margin:0 auto;}
.footnotes{font-size:80%;}
.block{border-left:1ex solid gray;padding-left:2em;}
li{padding:0.25em;}
a:hover{text-shadow: 0 0 5px;}
body{font-family:sans-serif;max-width:100ex;padding-left:3em;padding-right:2em;}
code{font-family:Consolas, Inconsolata, Monaco, monospace;}
p{text-align:justify;}
</style>
</head>
<body>
<div id="header">
<h1 class="title">Mastermind</h1>
</div>
<div class="figure">
<img src="pictures/mastermind_owlpacino_scaled.jpg" title="Picture BY-ND by Flickr user owlpacino" alt="The classic game" />
<p class="caption">The classic game</p>
</div>
<p>We already considered a <a href="guessing_games.html">guessing game</a> on this blog, in which Alice asks queries of the form “is the number in this set” and receives yes/no answers.</p>
<p>In this post, we will play a restricted version of the popular game Mastermind. In Mastermind Carole thinks of a secret string of four coloured pins. Alice can query strings and learns the number of matching pins (differentiated between the pins that are correct and in the correct position and the pins that are merely contained in the secret string).</p>
<p>Mastermind has been extensively studied in combinatorics. Already in ’77 Knuth showed that Alice can always win in at most 5 moves. Here we want to find asymptotics for the game when Carole chooses a string of length <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math>.</p>
<p>To make things easier for our calculation, we will restrict the game to binary strings. Also, Alice only learns the Hamming distance (that is the number of differences) between her string and Carole’s string. Alice is computationally unbounded, the only important metric is the number of queries she needs to guess Carole’s string.</p>
<p>The naive algorithm is testing each bit of Carole’s string sequentially, by querying strings of the form <code>0000</code>, <code>1000</code>, <code>0100</code>, etc. This takes <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> queries for bitstrings of length <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> – essentially we do a binary search for Carole’s string. However the algorithm doesn’t seem to be very efficient, it appears that Mastermind is easier than the yes/no game. After all we get much more information with each query.</p>
<p>Can we find Carole’s string with less than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> queries?</p>
<!-- more -->
<p>It turns out that it <em>is</em> possible to gather enough information quickly. Disappointingly the strategy is not very useful if we take the computation time into account that Alice needs to produce the secret string.</p>
<h2 id="a-randomized-strategy">A Randomized Strategy</h2>
<p>In Knuth’s algorithm, Alice always queries the string that eliminates the largest number of possible secret strings. This is straightforward to implement by using a brute force approach (we’re computationally unbounded), however the analysis becomes tricky.</p>
<p>Luckily Alice has a very simple randomized strategy that succeeds with high probability. Without thinking she queries random strings and stores the string and its Hamming distance to the secret string. Intuitively a random string is not much worse at eliminating possible solutions than the optimal string.</p>
<p>We have collected enough information when there is only one possible solution left. Let the the secret string be <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math>, and let the query string be <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math>. Let us try to find the probability that a fixed impostor-string <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>i</mi><annotation encoding="application/x-tex">i</annotation></semantics></math> is not excluded by querying <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math>, i. e. <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math> and <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>i</mi><annotation encoding="application/x-tex">i</annotation></semantics></math> have the same Hamming distance from <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math>.</p>
<div class="figure">
<img src="pictures/mastermind.png" alt="The same distance" />
<p class="caption">The same distance</p>
</div>
<p>Suppose <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math> and <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>i</mi><annotation encoding="application/x-tex">i</annotation></semantics></math> differ in <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>d</mi><annotation encoding="application/x-tex">d</annotation></semantics></math> positions. How many query strings are there that don’t discern between the two? For <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math> to have the same distance from both, only the positions matter where <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math> and <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>i</mi><annotation encoding="application/x-tex">i</annotation></semantics></math> disagree – where they agree the bits of <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math> contribute the same thing to the Hamming distance. So <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>−</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">n-d</annotation></semantics></math> positions of <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>q</mi><annotation encoding="application/x-tex">q</annotation></semantics></math> are completely arbitrary. In the remaining positions we need to make sure half the bits agree with <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math> and the other half agrees with <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>i</mi><annotation encoding="application/x-tex">i</annotation></semantics></math>. Clearly this is only possible if <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>d</mi><annotation encoding="application/x-tex">d</annotation></semantics></math> is even. Already after the first query we’ve excluded all impostors that have an odd distance from <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>s</mi><annotation encoding="application/x-tex">s</annotation></semantics></math>. Pretty neat.</p>
<p>For even <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>d</mi><annotation encoding="application/x-tex">d</annotation></semantics></math> we get <span class="math display">$$\mbox{Pr}[i \mbox{ survives}] = \frac{\left({{d}\atop{d/2}}\right) \cdot 2^{n-d}}{2^{n}} = \left({{d}\atop{d/2}}\right) \cdot 2^{-d}.$$</span> Using Stirling’s approximation on the factorials it is straightforward to show that this is essentially <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msqrt><mfrac><mn>2</mn><mrow><mi>π</mi><mi>d</mi></mrow></mfrac></msqrt><mi>.</mi></mrow><annotation encoding="application/x-tex">\sqrt{\frac{2}{\pi d}}.</annotation></semantics></math></p>
<p>We want to show that after a sufficiently large number of samples <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>t</mi><annotation encoding="application/x-tex">t</annotation></semantics></math>, the probability that there is an impostor string left tends to zero. By a simple union bound it suffices to show <span class="math display">$$ \sum_d \left({{n}\atop{d}}\right) \cdot \left(\frac{2}{\pi d}\right)^{t/2} \rightarrow 0.$$</span></p>
<p>Let’s try to bound the individual summands. We do a case distinction. First consider the case where <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>d</mi><mo>≤</mo><mi>n</mi><mi>/</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><msup><mo stretchy="false" form="postfix">)</mo><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">d \leq n/(\log n)^3</annotation></semantics></math>. By Stirling’s formula we can bound <span class="math display">$$\left({{n}\atop{d}}\right) \leq \left(\frac{en}{d}\right)^d,$$</span> and thus the summands are no larger than <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mrow><mi>t</mi><mi>/</mi><mn>2</mn><mo>⋅</mo><mo stretchy="false" form="prefix">(</mo><mn>2</mn><mi>d</mi><mi>/</mi><mi>t</mi><mo>⋅</mo><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>e</mi><mi>n</mi><mi>/</mi><mi>d</mi><mo stretchy="false" form="postfix">)</mo><mo>−</mo><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>π</mi><mi>d</mi><mi>/</mi><mn>2</mn><mo stretchy="false" form="postfix">)</mo><mo stretchy="false" form="postfix">)</mo></mrow></msup><mi>.</mi></mrow><annotation encoding="application/x-tex">2^{t/2\cdot (2d/t \cdot \log (en/d)- \log(\pi d/2))}.</annotation></semantics></math> By plugging in the extreme values, 2 and <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>/</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><msup><mo stretchy="false" form="postfix">)</mo><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">n/(\log n)^3</annotation></semantics></math>, for <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>d</mi><annotation encoding="application/x-tex">d</annotation></semantics></math> and setting <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mo>≥</mo><mn>4</mn><mi>n</mi><mi>/</mi><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">t\geq 4n/\log n</annotation></semantics></math> we get <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mi>d</mi><mi>/</mi><mi>t</mi><mo>⋅</mo><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>e</mi><mi>n</mi><mi>/</mi><mi>d</mi><mo stretchy="false" form="postfix">)</mo><mo>−</mo><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>π</mi><mi>d</mi><mi>/</mi><mn>2</mn><mo stretchy="false" form="postfix">)</mo><mo>≤</mo><mfrac><mn>1</mn><mrow><mn>2</mn><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><msup><mo stretchy="false" form="postfix">)</mo><mn>2</mn></msup></mrow></mfrac><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>e</mi><mi>n</mi><mi>/</mi><mn>2</mn><mo stretchy="false" form="postfix">)</mo><mo>−</mo><mo>log</mo><mi>π</mi><mo>≤</mo><mo>−</mo><mn>3</mn><mi>/</mi><mn>2</mn><mo>,</mo></mrow><annotation encoding="application/x-tex">2d/t\cdot \log (en/d) - \log (\pi d/2) \leq \frac{1}{2(\log n)^2} \log (en/2) - \log \pi \leq -3/2,</annotation></semantics></math> for sufficiently large <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> and thus the exponent can be bounded from above by <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>3</mn><mi>t</mi><mi>/</mi><mn>4</mn></mrow><annotation encoding="application/x-tex">-3t/4</annotation></semantics></math>.</p>
<p>Hopefully we can also derive such a bound in the case where <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>/</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><msup><mo stretchy="false" form="postfix">)</mo><mn>3</mn></msup><mo>≤</mo><mi>d</mi><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">n/(\log n)^3 \leq d \leq n</annotation></semantics></math>. In this case we bound the binomial coefficient rather crudely by <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msup><mn>2</mn><mi>n</mi></msup><annotation encoding="application/x-tex">2^n</annotation></semantics></math>. Then the summands are not larger than <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mrow><mi>t</mi><mi>/</mi><mn>2</mn><mo>⋅</mo><mo stretchy="false" form="prefix">(</mo><mn>2</mn><mi>n</mi><mi>/</mi><mi>t</mi><mo>−</mo><mo>log</mo><mo stretchy="false" form="prefix">(</mo><mi>π</mi><mi>d</mi><mi>/</mi><mn>2</mn><mo stretchy="false" form="postfix">)</mo><mo stretchy="false" form="postfix">)</mo></mrow></msup><mi>.</mi></mrow><annotation encoding="application/x-tex">2^{t/2\cdot (2n/t - \log (\pi d/2))}.</annotation></semantics></math> Bounding <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>π</mi><mi>d</mi><mi>/</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">\pi d/2</annotation></semantics></math> by <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>/</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><msup><mo stretchy="false" form="postfix">)</mo><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">n/(\log n)^3</annotation></semantics></math> and setting <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mo>≥</mo><mn>4</mn><mi>n</mi><mi>/</mi><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">t\geq 4n/\log n</annotation></semantics></math> we get <span class="math display">$$\frac{2n}{t} - \log {\pi d}{2} & \leq \frac{\log n}{2} - \log (n/(\log n)^3) \
= \frac{\log n}{2} - \log n + 3 \log \log n \
= 3 \log \log n - \frac{\log n}{2}.
$$</span> Again this is smaller than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>3</mn><mi>/</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">-3/2</annotation></semantics></math> for sufficiently large <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> and we can bound the summands by <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msup><mn>2</mn><mrow><mo>−</mo><mn>3</mn><mi>t</mi><mi>/</mi><mn>4</mn></mrow></msup><annotation encoding="application/x-tex">2^{-3t/4}</annotation></semantics></math> in this case too.</p>
<p>Now we can easily bound the whole sum for <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi><mo>≥</mo><mn>4</mn><mi>n</mi><mi>/</mi><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">t\geq 4n/\log n</annotation></semantics></math> <span class="math display">$$
\sum_{d} \left({{n}\atop{d}}\right) \cdot \left(\frac{2}{\pi d}\right)^{t/2} \leq \sum_d 2^{-3t/4} \
= n2^{-3t/4},\
$$</span> and this goes to zero rather quickly.</p>
<p>Hence a sublinear number of queries suffices to narrow down the solution space to a single candidate. An information theoretic argument shows that this is optimal. We get <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>log</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\log n</annotation></semantics></math> bits in every query and the secret string has <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> bits, proof by handwave.</p>
<h2 id="remarks">Remarks</h2>
<p>We’ve shown that after <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false" form="prefix">(</mo><mi>n</mi><mi>/</mi><mo>log</mo><mi>n</mi><mo stretchy="false" form="postfix">)</mo></mrow><annotation encoding="application/x-tex">O(n/\log n)</annotation></semantics></math> queries we’ve collected enough information to exclude all but one possible solutions. We can then find the remaining solution by brute force. Unfortunately we can’t improve much on that method: Checking whether there is a valid solution given <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>k</mi><annotation encoding="application/x-tex">k</annotation></semantics></math> queries and answers is <a href="http://arxiv.org/abs/cs.CC/0512049">NP-complete</a>.</p>
<p>Optimizing functions (like the Hamming distance from a fixed string) using only the answers from an oracle is studied under the name “Blackbox Complexity”. The applications are mainly in the analysis of evolutionary and genetic algorithms. In theory algorithms base their decisions solely on the evaluation of a problem specific fitness function. Blackbox complexity tries to prove lower and upper bounds or the running time of these algorithms for different function classes. Currently only very simple functions are tractable mathematically.</p>
<p>The analysis of Mastermind I presented here is from a <a href="http://arxiv.org/abs/1012.0952">FOGA ’11 paper by Doerr et al.</a> A slightly different take on the problem that some might find easier to follow can be found in Anil and Wiegand “Black-box Search by Elimination of Fitness Functions”.</p>
<hr/>
<div style="display:inline-flex;flex-wrap:wrap;justify-content:space-between;font-size:80%">
<p style="margin-right:2ex">CC-BY-SA <a href="mailto:adrian_neumann@gmx.de">Adrian Neumann</a> (PGP Key <a href="https://adriann.github.io/ressources/pub.asc">A0A8BC98</a>)</p>
<p style="margin-left:1ex;margin-right:1ex"><a href="http://adriann.github.io">adriann.github.io</a></p>
<p style="margin-left:2ex"><a href="https://adriann.github.io/feed.rss">RSS</a></p>
</div>
</body>
</html>