challenge

What's wrong with checking all 10000 combinations?

Bayesian inference.

That is all.

Quote:

Original post by ghostrider_ The challenge is... given a set of clues and results from the game "Mastermind", determine the answer, and whether or not there's many or no possible answers.

Quote:

Original post by InnocuousFox Bayesian inference. That is all.

Are you sure that's how you would do it? There is nothing probabilistic about the problem...

my fault... the number of the digits is given as an input N.. so imagine that if N=6 then i have 1.000.000 combinations.. furthermore i think that there is a better algorithm as far as complexicity is concerned..

Quote:

Original post by InnocuousFox Bayesian inference. That is all.

i dont get how to use it.... :s

let me give you an example..
if N=4 and the clues are:

9793 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0

Then the number 3411 is the only one that satisfies the rules.

Quote:

Original post by alvaro Quote: Original post by InnocuousFox Bayesian inference. Are you sure that's how you would do it? There is nothing probabilistic about the problem...

It's a decent way. Sure, on a small scale, the problem is tractable and you can just brute-force it as you suggested. However, that doesn't scale well.

Bottom line, you are dealing with uncertainty based on limited or slightly ambiguous information. By narrowing down the percentages of what is more likely to possibly be in any given slot, you can then take the best option that pops out and try that.

Quote:

Original post by ghostrider_ my fault... the number of the digits is given as an input N.. so imagine that if N=6 then i have 1.000.000 combinations.. furthermore i think that there is a better algorithm as far as complexicity is concerned..

Yep.

Quote:

Original post by ghostrider_ Quote: Original post by InnocuousFox Bayesian inference. That is all. i dont get how to use it.... :s

There's plenty of reading material available. In general, though, each slot has an equal chance of being each color. When you get clues back, you bias those percentages for or against colors. If you have a 0/1, you know that you can inch up the %s of all 4 colors in all 4 slots... just not much. If you get a 1/0, you can bump up the %s of all 4 slots with the colors currently in those slots. Eventually, by trying different combinations, the right answers will bubble to the top for each slot.

Incidentally, you can do this for games like Bridge, too, where you need to ferret out the locations of cards in other people's hands.

It's one way of doing things...

Quote:

Original post by InnocuousFox Quote: Original post by alvaro Quote: Original post by InnocuousFox Bayesian inference. Are you sure that's how you would do it? There is nothing probabilistic about the problem... It's a decent way. Sure, on a small scale, the problem is tractable and you can just brute-force it as you suggested. However, that doesn't scale well. Bottom line, you are dealing with uncertainty based on limited or slightly ambiguous information. By narrowing down the percentages of what is more likely to possibly be in any given slot, you can then take the best option that pops out and try that.

I really think you are thinking of the wrong problem here, and that's why I quoted what the original question was. The problem as described is not probabilistic at all.

EDIT: It looks like you did read the problem correctly. Then I'll just have to disagree with your approach. There is a set of possible hidden patterns, and each result you get restricts you to a subset of them. You need to find the intersection set. The Bayesian approach reduces to all probabilities being 0 or 1, which makes it not very interesting.

It's somewhat similar to the SAT problem, and I believe most non probabilistic algorithms for it are similar to this one: DPLL, which is really just backtracking, so I think something like this can be good choice.

You can try to do something like enumerating all the combinations using backtracking, and terminate as soon as you find that one of the results is inconsistent with the part of the combination you have built so far. But I doubt this will result in anything much better than brute-force enumeration.

If you are fed the results one by one, you can have a container with the surviving possibilities, and filtering from it will get faster and faster as its size is reduced.

Quote:

Original post by InnocuousFox It's a decent way. Sure, on a small scale, the problem is tractable and you can just brute-force it as you suggested. However, that doesn't scale well.

It's not so much "Bayesian vs. something else" as "how you represent your PDF" (e.g., as a Bayes net)... since representing the whole PDF without any assumptions has the same complexity as brute-forcing (and is in the 0-1 case entirely equivalent).

Quote:

Original post by alvaro If you are fed the results one by one, you can have a container with the surviving possibilities, and filtering from it will get faster and faster as its size is reduced.

...which is just a sparse representation of your Bayesian probability distribution...

Also: Doesn't Wikipedia give an algorithm?

Quote:

Original post by Emergent Also: Doesn't Wikipedia give an algorithm?

Amused Dave is amused.