Regarding the problem Randil brought up, maximum likelihood seems to work the best (although I can't prove it).
Basically, at each step we guess the four-digit code that is most likely to yield the evidence given so far.
I will use the following notation:
● p
r to denote Prob(green|right),
● p
w to denote Prob(green|wrong),
● q
r = 1-p
r,
● q
w = 1-p
w,
I will also assume that 0 < p
w < p
r < 1.
The probability that a four-digit code (that is not already guessed) yields the evidence so far is
p
rA q
rB p
wC q
wD,
where A is # of greens for correctly guessed digits (over all the evidence so far), B is # of reds for correctly guessed digits, C is # of greens for incorrectly guessed digits, and D is # of reds for incorrectly guessed digits.
Note that A+C is the total number of greens and B+D is the total number of reds. So then divide probability by p
wA+C q
wB+D, which is constant over all four-digit codes, and this gives
(p
r/p
w)
A (q
r/q
w)
B,
and the log of this is
A log (p
r/p
w) + B log (q
r/q
w).
So we just choose the four-digit code that maximizes the above quantity.
I wrote C++ code (C++11 standard) to simulate this. Various values of p
r and p
w are selected. For each set of values, it runs the guessing game 5000 times using the above strategy and takes the average number of tries. Except for the first guess which is completely random, if two or more values are tied for the maximum, this code chooses the first instance, which is the smallest 4-digit code/number. (Note that in the code, "TRIES" is number of times to run the game; the number of tries/guesses for each game is called "count".)
Here are the results. The resulting averages tend to be better than the averages Randil posted for his strategy (ex. for p
r=0.55 and p
w=0.45, the average with this strategy is 276.97, compared to 506). Also, I noticed that pairs of values with fixed p
r-p
w which are further away from the center (0.5) have a lower average number of guesses.
A few other things. I only did p
r > p
w but that's good enough since if p
r < p
w, just reverse the colors and switch p
r with q
r and p
w with q
w. The case p
r = p
w is obvious enough (it's equivalent to completely random guessing and the average number of tries for that is 5000.5). I didn't do p
w=0 or p
r=1 though since the code doesn't support it; you can try the code with something like p
w=0.0001 or p
r=0.9999 but I don't expect anything really special to come out of it.
The only other thing is that the case p
r=1 and p
w=0 can be done theoretically; the strategy is obviously to independently test each digit 0, 1, ... until you get the right digit, and the number of tries is always the largest digit plus one. The probability that the largest digit is k is ((k+1)
4-k
4)/10000, and when you work it out, the expected value for the number of tries is 8.4667.
