JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 3 ]    NEXT >
Re: Post your approach (response to post by Rustyoldman) | Reply
Ofcourse, but that wasn't the kind property I was looking for.
Re: Post your approach (response to post by dskloet) | Reply
A few seconds with google will usually tell you if a problem is NP-complete. With this problem, about ten seconds.
Re: Post your approach (response to post by venco) | Reply
In the worst case, My method takes
(k/2 * L) + k - 1
guesses.

that is, k - 1 initial guesses;
for each position, issue a guess with two candidate colors,
one as background color.
for example,
X Y X X
after this, we can know whether this position is color X or color Y
or neither.

This brings me 85 scores. I didn't make full use of the 20 secs.
in fact, for most cases it finishes in 1 sec...

If i make use of previous guesses by introducing a formula like yours,
the result may turn out better.
Re: Post your approach (response to post by gsais) | Reply
Thank you very much Mr gsais for this perfect explanation.
Re: Post your approach (response to post by venco) | Reply
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 did not participate in this match, but I thought of the first phase of finding the counts of colors:
First try k-1 guesses with 2 colors in each guess (half of one color, half of other, randomy sorted).

let`s call the numbers of pegs in each color A,B,C,D. Then (for 6 pegs) You have:
guess: ababba, result:1 miss,1 hit, equation: C+D=6-2
guess: ccacaa, result:1 miss,0 hit, equation: B+D=6-1
etc..
and last equation: A+B+C+D=6

Assuming that no peg color constitutes more than a half of the key, this will give the number of pegs and some information about placement in k guesses. But I guess the further part of telling which peg goes where was the difficult one :)
Re: Post your approach (response to post by gsais) | Reply
Actually, my taking the second spot is rather due to some inline assembly (SSE2) code and not only the "smart" discovery phase. SSE2 allowed the checking of about 6-7 times more random candidates than a C-only version. My best standard C code scored around 112-114.
Re: Post your approach (response to post by venco) | Reply
Yes, I've understood that part and already edited my post so that the cost formula would read "hits + hints". I've previously misread your approach description and that's why I thought that the 10000 factor was giving more weight to hits (perhaps because I tried that in my entry -giving more weight to hits- before I gave up and switched to discovering the color frequencies the "easy" way...)

By the way, I think your idea of giving more weight to hits+hints is brilliant (sure, I wish I'd had come up with it myself :-)
Re: Post your approach (response to post by gsais) | Reply

hits = feedback[0] = pegs with correct color and correct position; hints = feedback[1] = pegs with correct color but incorrect position

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.
Re: Post your approach (response to post by venco) | Reply
venco: Thanks for clarifying that! Now I can start to understand how you managed to skip the single-color guesses discovery phase.
Re: Post your approach (response to post by gsais) | Reply

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.

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.
Re: Post your approach (response to post by gsais) | Reply
I've got to say, this was a great summary post of what the leaders did (I haven't had a ton of time to skim through this thread). Nicely done.
Re: Post your approach (response to post by aminallam) | Reply
I did not get the method of guessing based on previous guesses. Can you please explain what is:
Sum(Abs(Expected matched - Actual matches)), and how the new guess is selected?

The method is very simple (in theory): always return a guess that is completely consistent with all the previous feedbacks. It goes like this:

a) A code is somehow choosed and postulated to be the secret key
b) The postulated code is used as the key to score each of the previous guesses and the resulting scores are compared against the codemaker's feedbacks for those previous guesses
c) If any of the comparisions fails (ie. we calculated a score of [3,5] but the codemaker's feedback was [4,5] for that guess) then it's said that the postulated code is "inconsistent" with the feedbacks (thus it can't possibly be the secret key) - another code must be choosed (repeat from step a)
d) Otherwise, if all the comparisions are successful, then it's said that the postulated code is "consistent" with the feedbacks (thus it can possibly be the secret key) - the postulated code is returned as the next guess

There are two important observations to make about this method:

1) All of the returned guesses have a greater than zero probability of being the secret key
2) The total number of consistent codes always decreases with each guess made - therefore the probability of finding the secret key always increases with each successive guess

It's because of these two features that the method is tipically called "stepwise optimal strategy" and it has been already found to be near-optimal on average (of course, optimal in this sense means relative to other algorithms - not to the ultimate optimal of always finding the answer in the first guess using shamanic powers). Strategies that are not stepwise optimal include "human" approaches (ie. slowly changing the guess to arrive at the answer by reasoning), and all the approaches that use a "background" color (ie. a color which is known to not occur in the answer or else that it's known where it's located within the answer).

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.

It's interesting to notice that the first and second places used a stepwise strategy consistently during the whole game (ie. a wrong move was never knowingly played); what it's more interesting to notice is that the third place (flagitious) and probably the fourth place too (cae) used the almost exact opposite strategy: playing knowingly wrong positions throughout most of the game! I believe that each of these two strategies have strengths and weaknesses in different areas so none can be considered better "overall" than the other. In particular, I believe that flagitious's approach has a bigger potential to be much more scalable than any stepwise approach, but I don't want to speculate too much before the final results are published and we can see the results...

Edit - Fixed venco's cost formula
Re: Post your approach (response to post by cae) | Reply
One more thing:
http://www.mathworks.com/contest/mastermind.cgi/home.html
Re: Post your approach (response to post by vdave) | Reply
This is provably true! With K-1 guess it is almost always possible
to split the code in two equally sized parts and know the color distribution in both parts. That's how my solution basically works.

It continues to split each part in two until each part has less than
about 1Million permutions and bute forces these. Additionally there
are a few special cases for small lenghts. This gave me ~110 points so
it can't be too bad.
Re: Post your approach (response to post by vdave) | Reply
I did not get the method of guessing based on previous guesses. Can you please explain what is:
Sum(Abs(Expected matched - Actual matches)), and how the new guess is selected?
[ 1 2 3 ]    NEXT >

RSS