What is the most optimal algorithm for playing a popular guessing game?

[martix]

I need to come up with an optimal algorithm for playing a popular guessing game which you might know by a handful of names like Bulls and Cows, Codebreaker, Guess-the-number, Mastermind(without repeating digits though).
Here's the general definitions from the wiki page:

On a sheet of paper, the players each write a 4-digit secret number. The digits must be all different. Then, in turn, the players try to guess their opponent's number who gives the number of matches. If the matching digits are on their right positions, they are "bulls", if on different positions, they are "cows".

I have thought about it and I do have a certain strategy I play with, but I kinda fail to condense it into something specific and I don't think it works always and I also doubt its the most optimal.
Any tips, resources would be helpful.

 

[csprof2000]

Are you trying to optimize it with respect to the number of guesses you have to make, or for time (as in, does performing what may be a computationally large amount of logic not affect the algorithm's optimality)?

If it's the guessing thing, then perhaps a scheme like this...

List the 10 P 4 = 5040 possibilities.

Inquire as to the first one in the list... say, 0123.

Then,...

if B=4, you've won the game.

if B=3, eliminate this password only.

if B=2, eliminate from your list all passwords that have at least 3 ordered digits in common with the password you guessed.

if B=1, eliminate from your list all passwords that have at least 2 ordered digits in common with the password you guessed.

if B=0, eliminate from your list all passwords that have at least 1 ordered digit in common with the password you guessed.

Then guess the next remaining number in the list.

For instance, let's have the list ordered like: 0123, 0124, 0125, ..., etc. Say your secret password is 7628.

I guess 0123. B=1, so I eliminate anything looking like 01xx, 0x2x, 0xx3, x12x, x1x3, xx23. This is 270 numbers off the list.

I then guess 0213. B=0, so I eliminate anything looking like 0xxx, x2xx, xx1x, xxx3. This will be reduce the list further, by something between 0 and 360 elements (my guess is somewhere in the neighborhood of 300).

I then guess 1032. B=0, so I eliminate anything looking like 1xxx, x0xx, xx3x, xxx2.

I then guess 2103. B=0, so I eliminate anything looking like 2xxx, x1xx, xx0x, xxx3.

I then guess 3410. B=0, so I eliminate anything looking like 3xxx, x4xx, xx1x, xxx0.

I then guess 4321. B=1, so I eliminate anything looking like 43xx, 4x2x, 4xx1, x32x, x3x1, xx21.

etc. you get the idea. It's hard to do in my head, but once you get a program down for it it can run through this algorithm like a champ.

Notice that I don't even make reference to the C's. Can the idea be improved using the C's? Or must an entirely different method be adopted if one is to use the C's (and is the other method more efficient?) Thought experiment...

Is this in the ballpark of what you thought might be interesting?

I believe the algorithm is correct, in that in principle you check all numbers (either ask about them or eliminate them if they are impossible) and you can't eliminate a possible number. It always halts for finite input and the only way it can return is if B=4... and since the list will contain all possibilities, this should be alright.

Thoughts?

 

[martix]

The beauty of the game is that everything carries some information (which most of the time isn't that obvious too) - including C's and stuff. Obviously the more information there is, the better.
Well since its a game I am trying to optimize for number of guesses.

I usually guess the number in 7 or less turns(if I don't make a mistake that is). General strategy is going through all the numbers first.
Ex:
Num = 2407
Guesses:
1. 1234 - 2C
2. 5678 - 1C //By now I know that either 9 or 0 is also present.
3. 5690 - 1C //Now I know it isn't 5 or 6
4. 1596 - X //Eliminate those, so we now know that there is a 0 and it isn't last !(xxx0)
...and so forth...

However you do give me an idea here - while its kinda difficult for humans to brute-force, computers can do that in a snap. But is brute-forcing ever a good strategy?
One option is enumerating all permutations and eliminating the ones not possible.
Thought I'd rather not resort to brute-forcing...

And then there's also the challenge of coming up with next number or series of numbers that give you the most information, given what you have so far.

Also it has to be general, working not just for decimal with 4 numbers to guess.

 

[csprof2000]

Actually, my method generalizes to 10 numbers... and it's not complete in the sense that the information about Cs can be incorporated into the algorithm to make it converge faster.

Also, what I have down can be improved considerably as-is.

It's "brute force" only in the sense that you do a lot of work in between asking...the asking part isn't really so very brute force. A "brute force" algorithm with respect to what you're optimizing would be to just ask random numbers from the list, removing them if they're wrong. Then you could expect to ask [(10 C r) / 2] times on the average and (10 C r) times in the worst case, where r is the password length.

A nice thing about the general strategy - making a list, iterating through the list and removing impossibilities - is that it is clearly and provably correct. And if you use every bit of information to its fullest extent, you can do a lot better than what's above.

Also, you mention what the next best guess is. If you have some way of determining that, well, you can further improve it by sorting the numbers in the list based on how much information they may possibly add. The algorithm given already partially does that, and depending on how you put in the C handling logic, it may not even be necessary.

The above is just the idea, not the final algorithm.
Think about it... it needs some more work, but the idea is sound.

Does this answer your questions? I didn't just want to do your work for you.

 

[csprof2000]

Basically, to be both correct AND optimal, you will have to prove that you consider the possibility of each number, and you do so a minimal number of times. The list elimination method is nice in that respect since you can remove impossible passwords (and show your algorithm only removes those which are impossible), that the algorithm must produce the correct answer (because it checks all possible passwords until it finds the correct one), and that it's optimal (because a faster method would somehow know it was one of several possible solutions... without asking).

 

[csprof2000]

A more crystalized version of the algorithm...

	generate list of all passwords.

	while(passwords left in the list)
	do:

	   set p = the first password in the list.

	   get B, C for attempted password p


	   if B = 4, then...

	      return p

	   else...

	      eliminate all those which:

	         do not match exactly B ordered digits

	         do not match exactly B+C unordered digits

	      eliminate p

	   end if.

	loop.

 

[martix]

I see your point. It seems to me that humans go about solving this in a different way, not so methodical, hence the feeling that this is still a bit brute-force. However it may be just that we are better at picking up on complex patterns than computers are :P

But what we have here is pretty good. I'll test this method now, then I'll do some tech work on a program(interface and stuff), and then I'll think about implementing the algorithm.
I am still wondering how to come up with the best guess(or for the purposes of different difficulty settings - differently informative ones).

 

[CRGreathouse]

I'm not satisfied. The method in post #2 is clearly nonoptimal, and I expect that the method in post #6 is also suboptimal. Either would take too long on large instances of the problem: the space needed for the game with 10 letters or digits would be ~115 TB.

The problem seems structured enough to admit a better solution.

 

[CRGreathouse]

Consider a generalization of the C&B game where the first player can give hints ("It's not 1234"). This allows the list to be in any state at a given point. Suppose it has:
1234
4567
4568

Algorithm #6 takes two guesses in the worst case, but an optimal algorithm can determine the answer in one guess.

Showing that #6 is suboptimal in the (non-generalized) C&B game could presumably be done by finding a way to reach a state like this with actual guesses.

 

[martix]

What? 115TB?
Er... I do need it to be computationally efficient too! Enough so I can also keep history of guesses too because humans are prone to errors and I need to be able to go back and correct them.
It also needs to scale well only to a maximum of 16 P 6.

 

[CRGreathouse]

Er... I do need it to be computationally efficient too! Enough so I can also keep history of guesses too because humans are prone to errors and I need to be able to go back and correct them.
It also needs to scale well only to a maximum of 16 P 6.

If you have an alphabet of 16 characters and select 6, there are 5,765,760 entries for the list, so it takes up 5,765,760 bits (about 700 kB). That's not too bad, but it's not good either.

And I still think that a better algorithm exists by altering the order of guesses.

 

[AUMathTutor]

Hey guys, I'm new here... but I like this problem.

I agree that the algorithm in post #6 isn't optimal... or at least it seems like it could be better.

But it looks promising... could the basic structure not be improved upon by reordering the list, or if space is a consideration, by generating a "rule" set and generating new passwords on the fly, and checking them against the rules? Then all entries wouldn't have to be kept in storage at the same time. Also, this would make it easier to come up with the next "best guess"...

Where did you hear about this problem?

 

[bpet]

Ok what about a minimax approach to minimize the number of guesses required.

Maintain a list of possibilities and eliminate all that are inconsistent with the clues so far. At each step you choose the guess that would maximize the worst case number of possibilities that would be eliminated, i.e. let n(X,Y) be the number of possibilities that would be eliminated if X is guessed and Y is the answer; let n(X) be the minimum of n(X,Y) over all possibilities Y and choose as your next guess an X that maximizes n(X).

Obviously different Y's will yield the same clue and thus the same n(X,Y) so we can determine n(X) from all possible distinct clues.

I wonder, is there ever a situation where an optimal guess comes from outside the list of possibilities?

 

[martix]

Somehow I get the feeling that we shouldn't talk about "the guess with the highest chance of getting the most information". I don't want a probabilistic approach, even if its statistically better between games. I think randomness should only help, not harm the algo's efforts.

The idea came about as a side project to a programing task. I used to play that game a lot in class and I find it interesting. So in the light of a programing task we were given which seemed relatively easy and useless by itself I thought, what if along with the required technical part I also do this which puts the task to practical use and isn't so useless(might even be publicly releasable; Hell, some people would even charge money for something like this).

In that regard we are mixing up the practical and theoretical domain of the problem. I'll be worrying about doing the programing. Considering the maximum is 16 P 6 with a careful choice of service code algorithms I believe the program will be snappy enough.

Here we need to come up with the best theoretic deterministic algorithm math allows.

 

[CRGreathouse]

I wonder, is there ever a situation where an optimal guess comes from outside the list of possibilities?

I hadn't even considered that! It does seem possible, though, especially in the generalized version.

 

[AUMathTutor]

It seems like, in any event, there needs to be a way to find the "value" of a guess in terms of how much information it will give in the best case, the worst case, or on average.

The naive method - assuming every possible response in terms of B and C and then calculating the eliminated possibilities for each password seems unwieldy.

 

[martix]

I hadn't even considered that! It does seem possible, though, especially in the generalized version.

Actually that is a pretty valid issue. I often use numbers that I know not to be present to clarify information about other numbers.
Say you have
1234 - 1C
5678 - 2C
1290 - 2C
1394 - X - intentionally using the clearly not present 3/4 to determine the presence of other numbers.

 

[AUMathTutor]

It could just be, though, that this is just the most straightforward to get information, not the "best". Again, I think there needs to be a way to characterize a guess in terms of how much information it will give for a certain list of possible passwords.

 

[CRGreathouse]

It could just be, though, that this is just the most straightforward to get information, not the "best". Again, I think there needs to be a way to characterize a guess in terms of how much information it will give for a certain list of possible passwords.

Information is easy to characterize: the base-two logarithm of the number of remaining states is called "bits", which is a familiar unit. But just knowing which guess will maximize information is not enough, since perhaps one state will give more information but further guesses from that position will yield less, with a worse worst-case scenario.

 

[martix]

Sadly I haven't really had time to busy myself a lot with that issue in the past few days and it does not seem likely I will be able to in the near future too.

However from the recent replies here an unsuspecting viewer might easily decide we are talking about chess or a chess-like game here.
So maybe there are some techniques we can borrow from chess that apply here. Any resources you can think of maybe?

 

[AUMathTutor]

I just implemented csprof2000's algorithm for kicks, and it doesn't do too bad. I did make a look-up table instead of having the whole list in memory, but other than that...

It makes a very small number of guesses, though it doesn't run "fast", per se. I tried it for inputs of length 10 with up to 10 different digits and it always gave the right answer... it took under 5 minutes or so, and about 6 or 7 guesses. The time between guesses varied wildly, from under a second to several minutes.

Maybe there's a clever way to skip a bunch rather than checking them all.

 

[martix]

It should definitely run faster than that. Since the first 2 guesses are always obvious, you can calculate the reduced list after these are done and put that in memory and work from there.
I haven't had time to test anything, but I am sure I can eventually do better. :)

 

[AUMathTutor]

The thing is, csprof2000's algorithm must check each password at least once, whether it is to ask it OR to cross it off the list... so his way won't ever get any faster than that. The number of guesses is impressive, however. Looking back, he did say that he was optimizing for number of guesses, not time... but it does take a while, and would only be worse with length=16 passwords.

My code just generates all possible passwords in order and either eliminates them OR asks about them. I think the most obvious way to speed up my code isn't to look for a new algorithm, but to somehow "skip" large chunks of passwords that can't be part of it instead of just going through the list 1 by 1. For instance, consider passwords of length 2 from a pool of 5 numbers...

Secret: 32

01 10 20 30 40
02 12 21 31 41
03 13 23 32 42
04 14 24 34 43

Guess 01. B = 0 and C = 0. So we have (01, 0, 0) = (p, B, C). We add this to the table.
Check 02. Comparing to "01", we get B = 1, C = 1. Since B isn't 0 and C isn't 0, we skip "02".
Check 03. Comparing to "01" we get B = 1, C = 1. Skip it since B =/= 0.
Check 04. etc.
Check 10. Comarping to "01" we get B = 0 and C = 1. Skip it since C =/= 0.
Check 12. C = 1, so we skip.
Check 13. etc.
...
Check 23. It has B=0 and C=0 with "01", so we ask about it. We get (p, B, C) = ("23, 0, 2). Add to the table.
...
verify that the next one to be checked is "32", which passes. We ask about it, get B=2, and return.

All the time is lost in checking each of the numbers starting with 0, then starting with 2. If the algorithm could somehow "skip" the rest of these... this would take some logic... then you'd essentially only even be checking plausible ones. So we need to go from:

Keep a table of past guesses, iterate through new potential guesses, and ask about possibilities.

to

Keep a table of past guesses, and use the table of past guesses to generate the next potential guess in near-constant (or linear in the number of past guesses) time.

So the new algorithm would see that "23" is the next possible guess after "01" without checking all the intermediate values. If you could figure out how to do this, the algorithm would be a lot faster...

Please let me know if you come up with anything better... I'd love to know about it.

 

[martix]

Yup that'd be LINKED LISTS. :P
As I said before - it seemed an awful lot like brute forcing it. Your experience and code proves it.
I have already begun writing the program with the technical parts. The idea I have formulated is a not generating every possible password every time. Rather its working with single digits and positions as separate elements.
And any impossibilities just get POPed out. That seems the most natural way to me.

So rather than

Secret: 32

01 10 20 30 40
02 12 21 31 41
03 13 23 32 42
04 14 24 34 43

We do:

Secret: 32
Positions  [u]1   2[/u]
Possibles  0   0
           1   1
           2   2
           3   3
           4   4

That way we can avoid a couple of typical characteristics of computers like the brute-forcing you are doing and getting the exact same result from the same output. Lists can be randomized and superimposed for a number of purposes as required.
In other words it can be made to look more human-like.
So I'm thinking about a password building list with the whole codeset, a possibility list for every position. So when making a guess we build the password based on the possibility lists. And when we get the result we eliminate the appropriate numbers.

 

[CRGreathouse]

I have already begun writing the program with the technical parts. The idea I have formulated is a not generating every possible password every time. Rather its working with single digits and positions as separate elements.

I'm not sure how this works. It doesn't seem to store enough information to get optimal results. If your starting state is

Positions  1   2   3
Possibles  0   0   0
           1   1   1
           2   2   2
           3   3   3
           4   4   4

what do you transition to if the guess "012" has one right? Each value is possible at all positions.

 

[AUMathTutor]

I'm not sure how martix would prove that his way is optimal... it seems like CRGreathouse is correct.

I have a strong suspicion that a method similar to csprof2000's is optimal in the number of guesses, however. And I'm sure it's technically correct... he seemed to demonstrate that well enough. It will be interesting to test martix's code out on a problem suite and test what I have for csprof2000's and see if they give the same result. I guess we should just wait until then...

I don't really understand why martix seems so hung up on whether something is "brute force" or not. There have been several (good) suggestions for making the "obvious" algorithm take less space (this has already been proven to work... I only store guesses and get the right answer, and the number of guesses has always been small) ... and less time (I think that to avoid huge chunks of numbers, one needs only to look at prefix strings of the last guess(es) and iterate the higher-order positions rather than the low-order ones in order to make it compatible with the list of past guesses... it appears that this would reduce the search space by incredible amounts.)

I guess we'll just have to wait and see what martix gets, and compare. He probably doesn't even really need the "optimal" algorithm in either sense of the word, since I think he said he's just making a game.

 

[csprof2000]

Huh. I thought my algorithm would do better than that. I'll have to code it up and try it out.

In any event, the observation that my algorithm will look at d C r things is correct, and this must be why it's so slow for large inputs. I think there's definitely some merit in the idea to skip ranges of passwords... but I honestly don't want to get into it. Who knows if my algorithm is even optimal in the number of guesses...

Well, if AUMathTutor has a program that implements my algorithm, and since martix has an algorithm he says he uses to guess, why don't you both try guessing with:

digits = 0 to 9, inclusive.
length = 6
password = 2 4 1 7 3 8
password = 8 3 4 5 9 0
password = 2 4 6 8 3 5

And say what the guesses were (along with how many guesses were made). Then we can see very quickly whether or not martix's way or my way is better... it won't show either is optimal, but it it may very well show that one, the other, or neither are.

"Yup that'd be LINKED LISTS. :P"
I'm trying to figure out how you got that from AUMathTutor's post. It seems like either you have a fundamental misunderstanding of the problem he/she's talking about, or you don't know what linked lists are.