The Minimum Strategy and the Strongest Strategy of the Number Guessing Game MOO

MOO is a popular number-guessing game that has been called by various names such as Hit & Blow, Cow & Bull. The rules of the game are as follows.

• Two players write on a piece of paper a four-digit number (hereafter called a MOO number) consisting of numbers different from each other and keep it out of sight of both players. The first digit may be a zero, as in 0586.
• Each player takes turns asking a MOO number to guess the number of MOOs written by the opponent. The opponent responds with the number of bulls, whose locations and numbers are the same, and cows, whose numbers are the same but their locations are different, from the hidden MOO numbers written. Calculating the number of bulls and cows from two MOO numbers is called the MOO product below. If you guess the MOO number written by your opponent, you will get four bulls.
• The player who gets four bulls with fewer guesses wins. If the number of guesses is equal, the game is a tie.

To calculate those strategies, we used the following techniques.

• Data representation for faster execution
• Elimination of Equivalent guesses
• Pruning

The search program for estimating the lower bound of the total number of questions for a given set of MOO numbers is divided into estimate.c (when 10 different numbers appear in the set) and estimate_n.c (when there are 10 different numbers in the set) and estimate_n.c (in other cases).

The program to find the minimum question strategy is find_sol.c . The total number of questions (for all 5040 inputs) with the minimum question strategy is 26274, so the average number of questions is 5.213. Although this is a small improvement over the best strategy reported before this study, with a total number of 26347 questions (average number of questions 5.226), it is significant that it proves that there is no strategy with a smaller number of questions.

The program to find the fixed strategy that maximizes the win rate for the minimum question strategy is find_sol_next.c. The resulting strategy is different from the minimum-question strategy, but it is the strongest strategy among the fixed strategies (no strategy has a winning ratio greater than 0.5 against this strategy). This strongest strategy is n-answer.all.

find_sol.c and find_sol_next.c" use the common header file hit.h.

References

• Tetsuro Tanaka, An optimal MOO strategy, Proceedings of the 3rd Game Programming Workshop (1996) 202-209 (Original Paper(In Japanese), English version(arxiv.org))