Bulls and Cows

Bulls and Cows is a two player game. First player thinks of a N digit secret number and second player guesses that number. This is done by second player making a guess and first player telling the number of bulls and cows in the guess. If the digits of guess matches secret and they are in right position, it's a bull, if they match but on different position, they are cows. For e.g. Let secret be 0123 and guess be 0012. The guess has 1 bull, 2 cows. The game continues, until second player gets a response of N bulls.

The problem is to write a computer solver for bulls and cows that would try to guess the secret making only a small number of attempts.

Solution: show

Let D be the unique digits that can be put in the secret. Let N be the length of the secret number. The total number of secrets is D^N.

A naive solution is to try all D^N guesses until N bulls is the response. This approach makes D^N attempts in worst case. Not good.

We can do better than this. Let us make a random first guess and we get a response r. We create a pruned set by selecting all numbers (from D^N possible) that have response r with the guess. Secret must be in the pruned set. We can pick a number from this set as our guess and repeat the logic until we hear N bulls.

There are three ways to pick the next number
a) Pick the first number from the pruned set
b) Pick the number randomly from the pruned set
c) Use a heuristic to pick a number (Note this number can be outside the pruned set).

Our experiments show that b) is better than a). For N = 4, D = 10 with distinct digits in secret (5040 possible secrets) and initial guess of 0123, the pick first strategy makes 6.0051 attempts on average and 9 attempts in a worst case. On the other hand, randomly picking from the pruned set makes 5.9136 attempts on average and 9 attempts in a worst case.

Note that optimal strategy for N=4, D=10 with distinct digits in secret (5040 possible secrets) takes an average of 5.2131 attempts with 7 attempts in the worst case (technical paper). It is also guaranteed that 6 attempts is the worst case lower bound for any algorithm. Since 5.2131 is theoretical best, 5.9136 achieved by random is not bad.

Let us now explore option c. There are (N+1)*(N+2)/2 - 1 response classes starting from (0 bulls, 0 cows) to (N bulls, 0 cows). Note the -1 is there because if the response is N-1 bulls then we cannot have 1 cow. The response to a guess, partitions the D^N numbers (as shown in Fig 1).

Fig 1. Response partition of 10^4 numbers for the secret 0123

Now we know that the secret lies in the pruned set. We need to pick our next guess that partitions the pruned set in the best possible manner. One way to judge the goodness of partition is by information gain [sum_i ni * log (ni)]. The issue now is that to compute information gain, we need to compute responses for D^N * length(pruned set) pairs.

Note that the best guess can be outside the pruned set, that is why we need to compute D^N * length(pruned set) responses and not length(pruned set)^2. To see this consider that pruned set is [089, 189, 289, 389, 489, 589, 689, 789]. If our secret is 789 we need 8 guesses but if we try 012 as guess 1 then we get pruned set [389, 489, 589, 689, 789], then we try 345 as our guess 2 to get a pruned set [689, 789] and now two more guesses are required. So we solved it in 4 attempts instead of 8.

But the bigger issues is that this technique can only be applied if length of pruned set is small, otherwise it can be computationally prohibitive and memory intensive. Our strategy is as follows:

step 1. Pick distinct digits to make first guess.
step 2. Select random guess from the pruned set.
step 3. Perform step 2, three or four times.
step 4. Pick guess using information gain measure.
step 5. Perform step 4, until game is solved.

For N = 4, D = 10, (5040 possible secrets), this strategy makes 5.7201 attempts on average with 8 attempts in a worst case. Summary of algorithms is as follows:

D=10, N=4, 5040 secrets
algo	average #attempts	worst #attempts
pick first	6.0051	9
pick random	5.9136	9
heuristic pick	5.7201	8
optimal	5.2131	7

D=10, N=4, 10000 secrets
algo	average #attempts	worst #attempts
pick first	8.0291	13
pick random	6.6323	11
heuristic pick	6.2001	8

Source code: bullscows.py

Technical resources: optimal strategy, bullscows.pdf