Thursday, August 16, 2012

Mastermind Strategies

Strategy for computer codebreaking

Ronald Retzel (2012) 
draft version


Fig.1 Vomlel (2004?) Bayesian networks in Mastermind

  
Game theory


Links
  • Game theory wikipedia
  • Eric Rasmusen. An introduction to game theory (pdf)







Fig.2 Diagram of rock, paper, scissors, lizard, Spock game play

Game analysis (Bulls and Cows / Mastermind )


Game setup: see How to play. Here we play the color code game.

Numeral system set:
 
Links
Fig.3 Maya numbering 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


Decimal ValueBaseBase-x Value



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.

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).

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. 

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]14982693288530443057
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:

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.

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:
  1. The first guess is aabb.
  2. 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.
  3. 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).
  4. 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





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.com
http://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.


Comparing the strategies

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:

Basics:
Overviews:
 Contests
  •  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
Original research
  • 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. 
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)