The game of MOO.
While glancing through the First Edition UNIX Programmer's Manual (1971) I was struck by the following page in Section VI (‘User-maintained programs’):
11/3/71 MOO (VI)
NAME moo -- a game
SYNOPSIS /usr/games/moo
DESCRIPTION moo is a guessing game imported from England.
FILES
SEE ALSO
DIAGNOSTICS
BUGS
OWNER ken
The programmer of this game, Ken Thompson, is also the author of the UNIX Operating System. He wrote several other games for UNIX version 1.0 (Blackjack, Chess, a 3D self-learning version of Tic-tac-toe), and they all have more extensive descriptions in the Manual. So I was intrigued by this game ‘moo’, which I had never heard of.
It became clear to me that Moo is also known as ‘Bulls and Cows’, and is the forerunner of Master Mind, which I did know. In a pencil-and-paper version Bulls and Cows has been played by schoolchildren in Britain for decades. The rules are simple:
- Guess the 4-digit code, of which all digits must be distinct.
- Bulls: the number of correct digits in the right place.
- Cows: the number of correct digits in the wrong place.
E.g. if 5046 is the secret code, then a guess of 3456 is one bull (the 6) and two cows (the 4 and 5). The purpose of the game is to get ‘four bulls’ (code correctly guessed) in as few tries as possible.
A simpler version with a 3-digit code is known as Pico Fermi Bagels (Bagels, Bagel Pico Fermi).
The first computer implementation of Bulls and Cows was the MOO program written in 1968 in machine-code by Dr. Frank King for TITAN, the Cambridge University Atlas 2 computer; this program kept a league table showing the performance of its human opponents, which made it very popular in the Computer Laboratory.
Around 1970 it was ‘imported from England’ into the USA when J.S. Felton wrote a version for the TSS/8 time sharing system of DEC's PDP-8, Jerrold Grochow did so in PL/1 for the Multics system at MIT, and Guy L. Steele wrote a BASIC program in DEC's DECUS Program Library for the PDP-10 and -11.
The game was introduced to a wider audience by ℵ0 (‘Aleph Null’) in the Computer Recreations column of the April-June 1971 issue of Software – Practice and Experience.
Moo / Bulls and Cows has attracted quite some attention from mathematicians and computer scientists. It has been shown that using an optimal strategy any Moo secret code can be found in at most seven guesses, and that the best average number of guesses is 5.21. The optimal playing strategy is discussed in several papers, e.g, John Francis and Alexey Slovesnov. Donald Knuth wrote an article about an algorithm for solving classic six color Master Mind.