Updated 4 September 2023, this page is a work in progress. You can play the game, but it could be a week or two before I finish this explanation.
What is the best strategy? We can't guarantee a win all of the time because there is a chance factor in the game. Are we aiming at the shortest solution on average? Average is a very misleading idea here. Suppose our average number of guesses is 5. This could be the average of:
2, 2, 2, 2, 2, 20 or:
5, 5, 5, 5, 5, 5
But the player who achieved the first of these patterns would win five out of six games, the other would win only one.
A human player tries to construct a next guess which will yield some definite bit of information but the computer can use a simpler and more general rule. The key to understanding this lies in the ideas of
candidates and
profiles.
A
candidate is any number you have not yet eliminated. A
candidate list is a list of the
candidates and every time you make a guess and get a score, you can eliminate from the
candidate list any
candidate that would not get that score from that guess.
There are twenty possible scores from [0, 0] = no bulls or cows to [5, 0] five bulls. The score [4, 1] is obviously impossible and [5, 0] means the game is over. It is useful to imagine the remaining 19 possible scores sorting the
candidates into boxes each labelled with its score.
A
profile is a table showing how many candidates there are in each box. All numbers are equivalent for the first guess and the profile looks like this:
| Bulls | 0 | 1 | 2
| 3 | 4 |
| Cows |
| 0 |
120 |
600 |
600 |
200 |
25 |
| 1 |
2400 |
3600 |
1200 |
100 |
| 2 |
7800 |
4200 |
450 |
10 |
| 3 |
6400 |
1100 |
20 |
| 4 |
1325 |
45 |
| 5 |
44 |
After each guess, the score you get will determine the composition of your new candidate list. Suppose your first guess was 01234 and your score was [0, 2]. Then your candidate list will be reduced to 7800 possibles. At this point, different guesses will create different profiles:
Guess = 10567
| Bulls | 0 | 1 | 2
| 3 | 4 |
| Cows |
| 0 |
0 |
150 |
168 |
72 |
12 |
| 1 |
552 |
864 |
348 |
36 |
| 2 |
1776 |
1176 |
168 |
9 |
| 3 |
1680 |
348 |
14 |
| 4 |
372 |
30 |
| 5 |
24 |
Guess = 56789
| Bulls | 0 | 1 | 2
| 3 | 4 |
| Cows |
| 0 |
0 |
0 |
0 |
130 |
0 |
| 1 |
0 |
0 |
780 |
0 |
| 2 |
0 |
2730 |
0 |
0 |
| 3 |
4160 |
0 |
0 |
| 4 |
0 |
0 |
| 5 |
0 |
