September 20

Ken Thompson Played Moo

I stumbled across the following in an article by Dennis Ritchie about some of the things that Ken Thompson did.

An investigation of a strategy for Moo (Aleph-null, 1971; Grochow, 1972), the game we learned about from Cambridge University. It was also called Bulls and Cows: dealer picks a number of 4 different decimal digits, player guesses the number, dealer tells player the number of Bulls (Cows), correct digits in the right (wrong) place. Ken’s result was a large notebook with a complete strategy. Its first page said “guess 1234”. Depending on the number of bulls and cows, it sent you to other pages, with a new suggested guess–a complete game tree. It was not precisely optimal; it didn’t evaluate probabilities as such, but instead min-maxed on the number of possible responses locally in the game tree.

Faithful readers of this blog will probably recognize Moo as the ultimate ancestor of Mark4.

posted @ 07:43 PM EDT