Strategy for computer codebreaking
Ronald Retzel (2012)draft version
- Game theory
- Game analysis
- Basic Strategies
- Advanced Strategies
- Links
- Home
Fig.1 Vomlel (2004?) Bayesian networks in Mastermind
Game theory
Links
Fig.2 Diagram of rock, paper, scissors, lizard, Spock game play
Game analysis (Bulls and Cows / Mastermind )
Numeral system set:
Links
- List_of_numeral_systems
- http://en.wikipedia.org/wiki/Numeral_system
- http://en.wikipedia.org/wiki/Decimal_without_a_zero#The_bijective_base-10_system
Numeral systems have a base that rules the digits. Since the invention of zero, by convention any modern numeral system set starts with zero.
- base-10:{0,1,2,3,4,5,6,7,8,9} (decimal system set)
- base-6: {0,1,2,3,4,5} (senary system)
- base-2: {0,1} (binary system)
- base-26:{0,1,...26} (hexavigesimal system)
In this approach we use the base-6 set with k=6 elements.
Values can easily be converted from one to another numeral system. How to convert from/to decimal system: http://en.wikipedia.org/wiki/Hexadecimal#Division-remainder_in_source_base
Values can easily be converted from one to another numeral system. How to convert from/to decimal system: http://en.wikipedia.org/wiki/Hexadecimal#Division-remainder_in_source_base
Symbol set: The numeral set is here used to create an index for the symbol set only. No calculations are made. In this game numeral set and symbol set are paired bijectively (Bijection): for any numeral system exactly one element in either set represents exactly one element in the other set, any distinct objects can be symbols, e.g.:
- {0,1,2,3,4,5,6,7,8,9} (10 elements: paired with decimal system)
- {1,2,3,4,5,6,7,8,9,0} (10 elements: paired with decimal system)
- {head, tail} (2 elements: binary system)
- {red, yellow, green, blue, white, orange} (6 colors: senary system)
- {ant,bird,cat,dolphin,eagle,falcon} (6 symbols: senary system)
- {red ball, blue ball, red triangle, blue triangle, red square, blue square} (6 symbols: senary system)
- {a,b,c,...x,y,z} (26 character alphabet: hexavigesimal system)
In this approach (instead of colors) we use this symbol set: {1,2,3,4,5,6} paired with this numeral set: {0,1,2,3,4,5} where the 1st element of the numeral system set (zero) represents the 1st element of this symbol set (one) and so on. Note that it is not necessary to use another base-10 system, since we don't calculate with the code (cf. http://en.wikipedia.org/wiki/Decimal_without_a_zero#The_bijective_base-10_system); in this game ciphers are just symbols, like an index for a color.
Permutations set: http://en.wikipedia.org/wiki/Permutation
In this game the code is a sequence of elements where the order is taken into account (permutation, not a combination) and any duplicates are allowed. In this approach we use n=4 elements per sequence, e.g. "1233". This gives us a set with kn = 64 =1,296 different permutations, meaning distinct sequences of 4 elements of the symbol set: {"1111","1112",...,"6666"}. No blanks allowed (in some game setups a blank may be used in a guess as an additional symbol that we know of for sure that it is not in the code).
Countable set: http://en.wikipedia.org/wiki/Countable_set
In this approach we assume that the set of permutations is countable. Note that this is not a necessary requirement. In reality it depends on the capabilities of the computer (not to mention theoretical aspects). If countable then we can create an index (cf. http://en.wikipedia.org/wiki/Factorial_number_system): In this approach the index (position) in the numeral system set of each permutation is exactly represented by its value, no matter what numeral system is used, e.g.:
- decimal system: Position 3: Permutation: 0003, 4th position, since "0" is 1st position in numeral set
- binary system: Position 10 (bin.): Permutation: 0010, convert binary to decimal: 3 = 4th position
- hexadec.system: Position B (hex.): Permutation: 000B, convert hexadecimal to decimal: 0011 = 12th position
It might get handy to have an index number for each code and being able to calculate the code from an index rather than to examine the codes, e.g. when picking up a random code or cover scanned codes.
Comparing codes
Information we get from the other player comparing codes: quantity of direct "hits" (black pegs); quantity of correct elements at any position (black + white pegs), in this approach called "hints", e.g. if "1234" is the secret code then "1122" has 1 full hit and 1 other hit. In this approach hits=black pegs and hints=black+white pegs, therefore we get this result: (1.2) = (1 hit, 2 hints), in usual notation written (1,1) = (1 black peg, 1 white peg).
Consistency.
We don't know the secret code "1234", but we know that our guess "1122" compared with the real secret code gives (1.2) as a result. Any candidate for the secret code must have the same behavior, meaning if compared with the guess ("1122") this must result in (1.2) as well, e.g."1331" does and therefore it is a consistent candidate for the secret code. If it would have another behavior than the real secret code then it cannot be the secret code. We call a guess consistent with a previous guess if the comparison between these two guesses has the same result as the comparison between secret code and the previous guess had. In this game a guess is consistent if it is consistent with all previous guesses. If there is no consistent code within the rest of permutations, then an information given must be wrong. Note that the player is not forced to guess consistently.
Scoreboard.
a) Columns (categories)
Each code in the same column (category of codes) has the same quantity of duplicates and non-duplicates. For any n with k>=n given we know the complete set of categories of all permutations where: neither the order nor the symbol-index is taken into account.
b) Rows (scores)
Each code in the same row will give the same result when compared with the secret code. For any n given we know the complete set of all possible scores, noted as "(hits,hints)" where hits=black pegs and hints=black+white pegs: (0,0)..(n,n). In this approach (n=4, k>=n) these are: (0,0) (0,1) (0,2) (0,3) (0,4) (1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (4,4). Note that a score with n-1 black pegs and 1 white peg (n-1,n), e.g. (3,4) is not possible in this game. Quantity of possible patterns (with n>1, k>=n): (n+1)2 - (n+1)*n/2 -1 = 14. Our scoreboard now has 14 rows, 5 columns and looks like this (hints-sorted!):
Each code in the same column (category of codes) has the same quantity of duplicates and non-duplicates. For any n with k>=n given we know the complete set of categories of all permutations where: neither the order nor the symbol-index is taken into account.
n.k k>=n
1.1: 1-0
2.2: 2-0 1-1
3.3: 3-0 2-1 1-1-1
4.4: 4-0, 3-1, 2-2, 2-1-1, 1-1-1-1
5.5 :5-0, 4-1, 3-2-0, 3-1-1, 2-2-1, 2-1-1-1, 1-1-1-1-1
6.6: 6-0, 5-1, 4-2, 4-1-1, 3-3, 3-2-1, 3-1-1-1, 2-2-2, 2-2-1-1, 2-1-1-1-1, 1-1-1-1-1-1
In
this approach there are 5 categories: (4,0,0,0) (3,1,0,0) (2,2,0,0) (2,1,1,0)
(1,1,1,1), reading: 4 same elements, 3 same and 1 different element. and
so on, e.g.: "1111" "1112" "1122" "1123" "1234". "1122" scores same as
"1221" or "2233". Quantity of distinct patterns: formula missing.
b) Rows (scores)
Each code in the same row will give the same result when compared with the secret code. For any n given we know the complete set of all possible scores, noted as "(hits,hints)" where hits=black pegs and hints=black+white pegs: (0,0)..(n,n). In this approach (n=4, k>=n) these are: (0,0) (0,1) (0,2) (0,3) (0,4) (1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (4,4). Note that a score with n-1 black pegs and 1 white peg (n-1,n), e.g. (3,4) is not possible in this game. Quantity of possible patterns (with n>1, k>=n): (n+1)2 - (n+1)*n/2 -1 = 14. Our scoreboard now has 14 rows, 5 columns and looks like this (hints-sorted!):
| Scoreboard: counts of solutions for possible first guesses n=4 k=6 | |||||
| Scores\ cat. | (4) | (3-1) | (2-2) | (2-1-1) | (1-1-1-1) |
| e.g. | "1111" | "1112" | "1122" | "1123" | "1234" |
| (0.0) | 625 | 256 | 256 | 81 | 16 |
| (0.1) | - | 308 | 256 | 276 | 152 |
| (1.1) | 500 | 317 | 256 | 182 | 108 |
| (0.2) | - | 61 | 96 | 222 | 312 |
| (1.2) | - | 156 | 208 | 230 | 252 |
| (2.2) | 150 | 123 | 114 | 105 | 96 |
| (0.3) | - | - | 16 | 44 | 136 |
| (1.3) | - | 27 | 36 | 84 | 132 |
| (2.3) | - | 24 | 32 | 40 | 48 |
| (3.3) | 20 | 20 | 20 | 20 | 20 |
| (0.4) | - | - | 1 | 2 | 9 |
| (1.4) | - | - | - | 4 | 8 |
| (2.4) | - | 3 | 4 | 5 | 6 |
| (4.4) | 1 | 1 | 1 | 1 | 1 |
| Total | 1296 | 1296 | 1296 | 1296 | 1296 |
| worst case | 625 | 317 | 256 | 276 | 312 |
| total hint<2 | 1125 | 871 | 768 | 539 | 276 |
| Irving [Kooi] | 512 | 236 | 204.5 | 185.3 | 188.2 |
| Neuwirth [Kooi] | 1498 | 2693 | 2885 | 3044 | 3057 |
| Kooi | 5 | 11 | 13 | 14 | 14 |
Note that for the reason of better evaluation in this approach the scoreboard is hint-sorted, unlike in many notations where it is hit-sorted.
c) Interpretation for the first guess: If we guess "1111" and get (0.0) then there are 625 codes left to be the secret code, e.g. "2345", this tells us that the possibility that the code does not contain any "1" is 625/1,296. If we guess "1234" and get (0.0) then there are just 16 possible codes left, e.g. "5566", since the possibility that the code does not contain either 1, 2, 3, 4 (=does contain only 5 and/or 6) is 16/1,296.
d) Modification. At first stage we are not interested in lucky hits, since they are allways hints at the same time. We can now sum up the scores by looking at hints separately:
Interpretation: If the guess is of the kind (4-0) e.g. "1111" then we will know the exact quantity of color "1": 1, 2, 3 or 4 times, no other guess will give us that information. This can be a good objective for a human player (see there). On the other hand in worst case the possible codes are reduced just to 48% (625-1). And the chance to find 3 or 4 colors is very low at 2%. If the guess is of the kind (1-1-1-1) e.g. "1234" then we will know exactly how many of these 4 colors are in the code at least 1 time, no other guess will give us that information. If our objective would be to maximize the hints after the first guess this guess might be good: In worst case we will have still 660-1 codes left, but at least 2 colors (50% of the colors) found; and we have a chance of 27% to find 3 or 4 colors.
To evaluate an approach we need to look at the next turns.
Tree .
Attention: Obviously the table above is not finished. Sorry I had no time.
Interpretation:
(under construction)
| Scoreboard: Hints for possible first guesses n=4 k=6 | |||||
| Scores\ cat. | (4-0) | (3-1) | (2-2) | (2-1-1) | (1-1-1-1) |
| e.g. | "1111" | "1112" | "1122" | "1123" | "1234" |
| (x.0) | 625 | 256 | 256 | 81 | 16 |
| (x.1) | 500 | 625 | 512 | 458 | 260 |
| (x.2) | 150 | 340 | 418 | 557 | 660 |
| (x.3) | 20 | 71 | 104 | 158 | 336 |
| (x.4) | 1 | 4 | 6 | 12 | 24 |
| Total | 1296 | 1296 | 1296 | 1296 | 1296 |
| worst case | 625 | 625 | 512 | 557 | 660 |
| total hint<2 | 1125 | 871 | 768 | 539 | 276 |
Interpretation: If the guess is of the kind (4-0) e.g. "1111" then we will know the exact quantity of color "1": 1, 2, 3 or 4 times, no other guess will give us that information. This can be a good objective for a human player (see there). On the other hand in worst case the possible codes are reduced just to 48% (625-1). And the chance to find 3 or 4 colors is very low at 2%. If the guess is of the kind (1-1-1-1) e.g. "1234" then we will know exactly how many of these 4 colors are in the code at least 1 time, no other guess will give us that information. If our objective would be to maximize the hints after the first guess this guess might be good: In worst case we will have still 660-1 codes left, but at least 2 colors (50% of the colors) found; and we have a chance of 27% to find 3 or 4 colors.
To evaluate an approach we need to look at the next turns.
Tree .
| Scoreboard: Hints for possible second guesses first guess="5555": (x.1) | |||||
| Scores\ cat. | (4) | (3-1) | (2-2) | (2-1-1) | (1-1-1-1) |
| e.g. | "1111" | "1112" | "1122" | "1123" | "1234" |
| (x.0) | - | - | - | - | - |
| (x.1) | - | - | 512 | 458 | 260 |
| (x.2) | 15 | 340 | 418 | 557 | 660 |
| (x.3) | 5 | 71 | 104 | 158 | 336 |
| (x.4) | 0 | 4 | 6 | 12 | 24 |
| Total | 499 | 500 | 1296 | 1296 | 1296 |
| worst case | - | 625 | 512 | 557 | 660 |
| total hint<2 | - | 871 | 768 | 539 | 276 |
Attention: Obviously the table above is not finished. Sorry I had no time.
Interpretation:
(under construction)
Basic Strategies for computer programming
Also see: Strategies for real people
Basic strategies for computer assume complete information about all of the possible codes and to be able to count them. If the quantity of codes is more than the computer is able to calculate with in a given time then this kind of strategy fails. This highly depends on the game setup and the computer hardware being used.
Index.
- Basics
- Shapiro (1983) as discussed in: Kooi, Barteld (2005)
- Knuth, Donald (1976–1977)
- Irving, R. (1978-1979) as discussed in: Kooi, Barteld (2005)
- Neuwerth as discussed in: Kooi, Barteld (2005)
- Koyama, Kenji; Lai, Tony (1993)
- Kooi, Barteld (2005)
- Comparing the strategies
- Links
Non-strategies.
- Random guess each turn, guess without consistency check (at worst k^n = 6^4=1,296 guesses)
- Random guess, but chose a consistent code only (at worst ?? guesses).
- same, but variations like specified start guess, mix of scanning and random guesses
- Evaluation of all possible permutations using scoreboards
- Incomplete scan (not all permutations are evaluated)
Evaluating strategies
- Shapiro (1983) as discussed in: Kooi, Barteld (2005)
- Knuth, Donald (1976–1977)
- Irving, R. (1978-1979) as discussed in: Kooi, Barteld (2005)
- Neuwerth as discussed in: Kooi, Barteld (2005)
- Koyama, Kenji; Lai, Tony (1993)
- Merelo et al. (1999)
- Kooi, Barteld (2005)
- Venco (2006)
Shapiro (1983)back to index
"A Simple Strategy: The first strategy by Shapiro (Shapiro, 1983) (it is also published in (Sterling and Shapiro, 1994)). His algorithm does the following: the combinations are somehow ordered (usually alphabetically) and the first combination is asked. The answer is received. The next question is the first one in the ordering that is consistent with the answers given so far. And so on until the combination is cracked. A crucial drawback to this strategy, however, is that it looks at the informativity of questions very marginally. One can only be certain that one does not know the answer already, but that is all." Kooi (2005).--- not nec. consistent---
But brute force made it possible for some (as of now only simple) game sets to find questions that allways give the answer in not more than 7 turns. (Bogomolny, A, Greenwell, Don,(1999/2002))
Knuth, Donald (1976–1977)back to index
"using an algorithm that progressively reduced the number of possible patterns. The algorithm works as follows:
- The first guess is aabb.
- Calculate which possibilities (from the 1296) would give the same score of colored and white pegs if they were the answer. Remove all the others.
- For each possible guess (not necessarily one of the remaining possibilities) and for each possible colored/white score, calculate how many possibilities would be eliminated. The score of the guess is the least of such values. Play the guess with the highest score (minimax algorithm).
- Go back to step 2 until you have got it right."(Knuth, Donald (1976–1977)
See http://www.delphiforfun.org/Programs/MasterMind.htm, Nelson, Toby (1999) Investigations into the Master Mind Board Game. (html)
Neuwerthback to index
Kaymanback to index
Kooi, 2005back to index
Advanced Strategy for computer programming
Merelo et al. (1999-2012) back to index
https://springerlink3.metapress.com/content/n45l60j4803q7601/resource-secured/?target=fulltext.pdf&sid=wstdb0spla1licd2t3q4xii1&sh=www.springerlink.comhttp://geneura.wordpress.com/2011/05/08/going-a-bit-farther-and-a-bit-faster-solving-mastermind-using-evolutionary-algorithms/
http://geneura.wordpress.com/tag/games/
Improving and Scaling Evolutionary Approaches to the MasterMind Problem
Juan J. Merelo, Carlos Cotta and Antonio Mora
An experimental study of exhaustive solutions for the Mastermind puzzle
J. J. Merelo, Antonio M. Mora, Carlos Cotta, Thomas P. Runarsson
(Submitted on 5 Jul 2012)http://arxiv.org/abs/1207.1315
Venco, 2006back to index
http://apps.topcoder.com/forums/?module=Thread&threadID=511592&start=0&mc=41
My approach was simply to generate guesses compatible with results of previous guesses.
The problem is that I didn't find guarantied way to find this compatible
guess in time. So I was looking for guess with as small error as
possible.
The error I've used = sum(guesses, 10000*abs(guess.a -
current.a)+abs(guess.b - current.b)), where b is number of perfectly
matched pegs, and a is number of total matched colors
(results[0]+results[1] from nextGuess arguments).
Now, I generate each guess candidate by first generating compatible
color counts (first part of error sum), then generating most compatible
order.
In both of those steps I first quickly make some reasonable initial
state, then optimize it by some number of randomized changes, each
taking into account possible reduction of error. To speed up things a
lot I've maintained arrays of error changes for various modification of
the state, and look up for the best moves in this array. I have found
it's much more efficient to have this array maintained, than to
recalculate errors after each move.
I've managed to generate up to 50000000/(L*L*L) candidates per each
guess, using reasonable runtime - up to 15 seconds in worst case.
If any candidate has perfect match (zero error) I return the guess immediately.
Another part of my solution is the code for getting as much as possible
information from guesses analytically. The code estimates possible
minimum and maximum values for color counts, possible assignment bits of
colors in each place, etc. It allowed me to determine exact numbers of
each color in reasonably few guesses - about K.
Initially, I've tried to issue first K-1 unicolor guesses to determine
counts, but it turns out it wasn't necessary. This approach gets no
information about ordering from the first guesses, and I've got ~100
score from it (my second submission).
...
I thought about brute-force solution for small cases, but I've found
that my generic algorithm almost always finds compatible guess for
lengths up to 20, and larger cases are not brute-forceable anyway.
...
Several coders have mentioned random swaps as the way to find compatible guess.
My code does a bit more. It repeatedly removes 2-8 worst pegs, then adds
them back in the best places. In each step if there are several
possibilities with the same change in error, I pick one randomly.
Similar algorithm was used in the first stage when I don't know color counts yet for finding compatible set of counts.
...
"venco used the following cost formula (note: hits =
pegs with correct color and correct position; hints = pegs with correct
color but incorrect position):
cost = sum { 10000 * abs(hits - hits') + abs(hints - hints') }
The 10000 factor is used to give more weight to hits than to hints." (gsais)
Actually it's the other way around. I give more weight to hints to find correct color counts as quick as possible:
cost = sum { 10000 * abs(hints - hints') + abs(hits - hits') }
After all counts are found (it usually happens slightly later than after
K guesses) I start to use correct number of different colors, so the
first part of cost always yield zero, and algorithm concentrates on
ordering.
...
"hits = feedback[0] = pegs with correct color and
correct position; hints = feedback[1] = pegs with correct color but
incorrect position" (gsais)
Here is one more difference. I've used total number of matching colors
as value hints in cost formula, no matter if it's they are on correct
place or not.
It can be calculated as results[0]+results[1] from nextGuess argument.
This way hints is plain measure of how good is your guess in terms of
choosing various colors of pegs, and hits is the measure of order
quality.
.....
gsais, 2006
http://apps.topcoder.com/forums/?module=Thread&threadID=511592&start=15&mc=41
As good and simple as the stepwise strategy is, it has a very important
complication: altough finding a consistent code for small problems is
rather easy, for larger problems is extremely hard. In fact, it has been
already proved that just deciding if there exists a consistent code (a
subset of the problem of finding it) is a NP-complete problem; see
lbackstrom's post above. Even for not so large problems (~ K=10 L=15)
you can't actually hope to find a consistent code by simply generating
random codes, you really need to use some heuristic to guide the search.
However, even with good heuristics, for slightly larger problems it's
almost impossible to find a consistent code (unless you already have
enough hints), and for the very large problems the only thing that
becomes easy is understanding the true meaning of "finding the needle in
a haystack". This is where the "almost" stepwise strategies come, and
they come in basically two flavors:
* Divide-and-conquer: use a background color or an analytical method to
divide the problem in smaller problems and apply a stepwise approach for
the smallest problems; see the approaches of lyc1977 (background color;
discarding the impossible combinations is a way to find the consistent
codes) and OvejaCarnivora.
* Least inconsistent code: instead of finding a completely consistent
code with all the previous feedbacks, find the code that is the least
inconsistent (within a subset of the search space). Essentially, a cost
formula is used that measures how much inconsistent a code is, and any
optimizing algorithm is used to minimize the cost. venco used the
following cost formula (note: hits = feedback[0] = pegs with correct
color and correct position; hints = feedback[1] = pegs with correct
color but incorrect position):
cost = sum { abs(hits - hits') + 10000 * abs((hits + hints) - (hits' + hints')) }
The 10000 factor is used to give more weight in the first moves to the
total number of correct colors (hits + hints) than to the number of
correct positioned colors (later, once the color frequencies are
discovered the term becomes automatically zero). Now, since both vdave
and I started the search already knowing how many pegs of each color
were in the answer, the number of hints was completely irrelevant
(because hits + hints = L if the code is a permutation of the right
colors), thus the cost formula reduces to:
cost = sum { abs(hits - hits') }
Furthermore, knowing the frequency of each color greatly limited the
search space and also simplified the operation of finding the closest
neighbours of a code (ie. codes with an approximate cost) to swaps. But
these advantages didn't come without a price: as venco himself has
already stated, his 14+ points advantage over vdave (in the tests) are
very likely due to his algorithm skipping the color's frequencies
discovery phase - yet he doesn't say that achieving that was far away
from being an easy task at all (I can bet I wasn't the only one that
unsuccessfully attempted that, so I'm looking forward to read exactly
how he did it in the match editorial - right now I'm clueless edit: ok,
now I understand how he accomplished it: it's thanks to the brilliant
10000 * diff(hits + hints) term in the cost function). On the other
hand, vdave's "smart" discovery phase is rather intuitive (after one is
told about it, of course...), easy to understand and implement, and it's
also likely what allowed him to take the second spot in the tests.
http://www.mathworks.com/contest/binpack.cgi/analysis.html#Evolution
Strategies
Our contest problem is also known as the "knapsack" problem, a special
case of the bin-packing problem. Everybody knows how to write a brute
force search algorithm to find the best fit song list. However, since
brute force search is obviously slow and our scoring system punishes
algorithms with long CPU times, exhaustive search is ruled out. This
leaves us with two other choices: limited (heuristic) search and
multiple tries.
Limited search means using some heuristic judging criteria to check a
selected subset of all the combinations, and choose the ones that pass
the criteria to test.
Multiple tries means generating many random combination of the song
list, and then choosing the one with the best fit. This can also be
considered as a kind of limited search, except there is no heuristic
judging criteria. Simply choose the combination with the shortest gap
among all the selected combinations. This approach has a fancy technical
name, namely, the Monte-Carlo method.
Monte Carlo Method
Earlier entries mostly used the limited search approach. However, they
either had a large gap (due to limitations in their heuristics) or spent
too much CPU time. They were soon out run by entries using the
Monte-Carlo method. All of the top 100 entries used the Monte-Carlo
method.
The Monte-Carlo method for this problem can be summarized by the following three steps:
I. Generate some random permutations of the song list
II. Find the best packing among these permutations
III. Return the index corresponding to the best packing
Given these three steps, many strategies can be applied and many
parameters can be adjusted. As one of the MathWorkers here said, the
contest is like a genetic algorithm, except that it's the humans who are
doing the mixing and selection. There were many cases where someone
found a new strategy to apply to one of the steps, achieving a quantum
leap in the score, which was then followed by a series of marginal
improvements as other people tweaked (optimized) the strategy to its
full power. This tweaking continued until a new strategy was found and
another tuning war began.
4. EMPIRICAL RESULTS
The first table shows for each strategy for how many combinations the game is won in a particular round of
the game. Or put in other words: each strategy produces a game tree, the table shows for each depth of the
tree how many leafs (nodes without successors) there are.
Round number 1 2 3 4 5 6 7 8 9
Simple 1 4 25 108 305 602 196 49 6
Worst case 1 6 62 533 694 0 0 0 0
Expected size 1 10 54 645 583 3 0 0 0
Entropy 1 4 71 612 596 12 0 0 0
Most parts 1 12 72 635 569 7 0 0 0
[Kooi]
The third table shows how many questions are needed in total in the strategy (the sum of the lengths of all
the paths from the root of the tree to a leaf) and the expected number of questions needed (the expected
length of a path to a leaf). The numbers in the second column are rounded.
total number of questions expected number of questions
Simple 7471 5.765
Worst case 5801 4.476
Expected size 5696 4.395
Entropy 5722 4.415
Most parts 5668 4.373
The last four compare quite favourably to the Koyoma and Lai’s result of 4.340 (Koyoma and Lai,1993)
[kooi]
The following table shows the number of questions that
can be asked if the first answer is (1, 0).
question answer number of different questions
AAAA (1, 0) 12
AAAB (1, 0) 53
AABB (1, 0) 34
AABC (1, 0) 125
ABCD (1, 0) 52
Links:
Introduction:
mathworks.com
- CreativityGames.net. Mastermind - Strategy for Real People (html) - Review: Good Introduction
- Chow Ka Fat "TUTORIAL ON MASTERMIND CODEBREAKING STRATEGY (1)
(THE SIMPLEST GAME SETTING)" (html Part 1, 2, 3, 4, 5, 6, 7)
- CreativityGames.net.Mastermind - Strategy for Real People (html) - Review: Good Introduction
- Eric Rasmusen. (2000/2003/2005) An introduction to game theory (pdf)
- Mårdell, Jimmy. Optimal Mastermind Strategy html
- Nelson, Toby (1999) Investigations into the Master Mind Board Game. (html).- Review: Excellent overview
- Bogomolny, A; Greenwell, Don,(1999/2002) Cut the Knot. Invitation to MasterMind. (html/java) - Review: Excellent overview
- Fahrni, Reto (2009), "Mastermind. Perfekte Strategie dank Computer" (pdf)
- Francis, John (2010) Strategies for playing MOO, or Bulls and Cows. (pdf)
- Weisstein, Eric W. (no year) "Mastermind." From MathWorld--A Wolfram Web Resource
- mathworks.com (2001) http://www.mathworks.com/contest/mastermind.cgi/rules.html
http://www.mathworks.com/contest/mastermind.cgi/home.html
http://www.mathworks.com/contest/mastermind.cgi/analysis.html
mathworks.com- http://www.mathworks.com/contest/mastermind.cgi/winner.html
- http://www.mathworks.com/matlabcentral/fileexchange/Files.jsp?fileId=946
- lbackstrom; venco (TopCoder Members) (2006). Marathon Match 2 (html)
2 different strategies on 20 digits/15 colors game
- Knuth, Donald (1976–1977). The Computer as a Master Mind.(pdf) J. Recr. Math. (9): 1–6
- Irving, R. (1978-1979). Towards an Optimum Mastermind Strategy. Journal of Recreational Mathematics, Vol. 11, No. 2, pp. 81 – 87. (NO LINK FOUND) [discussed in: Kooi (2005), Fahrni (2009)]
- Neuwirth, E. (1982). Some Strategies for Mastermind. Zeitschrift f¨ur Operations Research, Vol. 26, pp.B257 –B278.(NO LINK FOUND)[discussed in: Kooi (2005)]
- Shapiro, E. (1983). Playing Mastermind Logically. SIGART Newsletter, Vol. 85, pp. 28 – 29.(NO LINK FOUND)[discussed in: Kooi (2005)]
- Koyama, Kenji; Lai, Tony (1993). "An Optimal Mastermind Strategy". Journal of Recreational Mathematics (25): 251–256 (NO LINK FOUND)[discussed in: Kooi (2005), Fahrni (2009)]
- Wiener, Michael (1995). Newsgroups: sci.math (txt)
- Merelo, J.J. ; J. Carpio; P. Castillo; V. M. Rivas; G. Romero (1999) "Finding a needle in a haystack using hints and evolutionary computation: the case of Genetic Mastermind" html(html)(html )
- Temporel, Alexandre ; Tim Kovacs (no year 2002?) "A heuristic hill climbing algorithm for Mastermind" (pdf/gz)
- Merelo-Guervos, J.J.; P. Castillo; V.M. Rivas (2003/2004) "Finding a needle in a haystack using hints and evolutionary computation: the case of evolutionary MasterMind" (pdf)
- Vomlel, Jiri (2004?) Bayesian networks in Mastermind (pdf)
- Vomlel, Jiri (2004) Bayesian networks in Mastermind, Proceeding of the 7th Czech-Japan Seminar, Awaji Island, Japan (pdf)
- De Bondt, Michiel C. (November 2004). NP-completeness of Master Mind and Minesweeper. Radboud University Nijmegen (ps)
- Stuckman, Jeff; Zhang, Guo-Qiang (2005). Mastermind is NP-Complete (html)
- Kooi, Barteld (2005). "YET ANOTHER MASTERMIND STRATEGY" (pdf)
- Venco (2006) forums (Topcoder.com)
- Heeffer, Albrecht; Harold Heeffer (2007).NEAR-OPTIMAL STRATEGIES FOR THE GAME OF LOGIK (pdf)
- Slovesnov, Alexey (2008/2011) Search of optimal algorithms for bulls and cows game (pdf)
- Gerfertz, Torsten; Christian Pernegger und Thomas Seidl (2008). PostScript spielt Mastermind (html)
- (Unknown) (2008) html
- Jeff Rowberg (2010). Solving Mastermind Logically (html/pl)
- Doerr, Benjamin; Reto Spöhel, Henning Thomas, Carola Winzen (2012). Playing Mastermind with Many Colors (html)
- Merelo, J.J. et al. (2012) An experimental study of exhaustive solutions for the Mastermind puzzle (5 Jul 2012) (html)(pdf)
-
(no year)
- http://code.google.com/p/mastermind-strategy/source/browse/wiki/Overview.wiki?r=43
- http://www.docstoc.com/docs/14831880/Optimal-Mastermind-Strategy (paysite)
- http://www.delphiforfun.org/Programs/MasterMind.htm Program as "seeker"
-
Enlaces externos
- Mastermind flash Juega al mastermind en flash.
- Mastermind OnLine Juega al Mastermind en tiempo real usando Algoritmos Genéticos
- Gran Colección de juegos Mastermind en línea
Static Mastermind (variant), http://www.maa.org/editorial/knot/Mastermind.html
A naive (but logically consistent) strategy is 97% as good as the optimum strategy, http://www.csc.ncsu.edu/degrees/undergrad/Reports/rtrosu/intro.htm
For an approach using a genetic algorithm, http://kal-el.ugr.es/mastermind/docmm.html
Enigma Mastermind (variant), http://www.student.brad.ac.uk/nchilton/java/Enigma.html
For the rules of Master Mind, as supplied with the game, http://www.iserv.net/~central/GAMES/mastermind/mastermind.html
Permalink: http://codebreaker-mastermind-superhirn.blogspot.com/2012/08/mastermind-strategies.html
Citation: Retzel, Ronald (2012). "Strategy for computer codebreaking". http://codebreaker-mastermind-superhirn.blogspot.com/2012/08/mastermind-strategies.html
Disclaimer: All of my blogs and posts are my private and personal online notebooks and my private opinion. Posts are allways draft versions that might get published to be reviewed by and to be discussed with my friends only. No information is meant for the public and I do not take any liability at all at any time for any content, code, link etc. for any reason. Warning: many links here are "clickable" and your software might usually direct you to and display content other than mine without warning.
color (etc.) in code, in correct position (black peg/ bull)
color (etc.) in code, but in wrong position (white peg/ cow)
