Mind reading machine (AWK)

From LiteratePrograms

theory

Shannon's 1953 memo, A Mind-Reading(?) Machine, describes a machine built out of relays at Bell Labs.

This machine is a somewhat simplified model of a machine designed by D.W. Hagelbarger. It plays what is essentially the old game of matching pennies or "odds and evens". This game has been discussed from the game theoretic angle by von Neumann and Morgenstern, and from the psychological point of view by Edgar Allen Poe in "The Purloined Letter". Oddly enough, the machine is aimed more nearly at Poe's method of play than von Neumann's.

The machine took advantage of the difficulty of generating truly random behavior in wetware by using a small (8-state) markov model to predict its human opponents.

practice

We implement a 1970's version of this 1950's algorithm, using AWK instead of mechanical relays.

Our markov model is based on behavior over the last two rounds, with hpa and hpb recording the history of the player's plays, and hca and hcb recording the history of the computer's guesses. The possible cases are: the player won or lost two rounds ago, changed plays or stayed with the same play, and won or lost the last round, for a total of 2³ = 8 histories, with any bias towards changing or staying in the upcoming round kept in the tally array.

If the player has repeated their behavior for a given history at least twice, we guess according to their predicted behavior. After the first observation, we guess with a 75%/25%, split, weighted towards the bias. If the player hasn't shown any bias (or during the first two rounds of the game), we guess at hazard.

<<consult model>>=
BEGIN	{ t = 0 }
NR > 2	{
	case = (hpa!=hca)"/"(hpa!=hpb)"/"(hpb!=hcb)
	t = tally[case]
	}
t < -1	{ guess=!hpb }
t == -1 { guess=(int(rand()+.75)?!hpb:hpb) }
t == 0	{ guess=int(rand()+.5) }
t == 1  { guess=(int(rand()+.75)?hpb:!hpb) }
t > 1	{ guess= hpb }

After finishing a round, we update the history with the results, including updating tally according to the player's behavior. Again, we wait for two rounds before touching the tally counters, at which point the history will have been fully initialized.

<<update model>>=
NR > 2	{ tally[case] += (hpb == play ? 1 : -1) }
	{
	hpa = hpb; hpb = play
	hca = hcb; hcb = guess
	}

We also report the results of the round to the player (in case they wish to update their internal models). En passant, we update pw and cw, the number of player (resp. computer) wins.

<<report results>>=
	{
	printf "You played " (play?"heads":"tails")
	printf "; I guessed " (guess?"heads":"tails")
	printf ".  "(play==guess?"I":"You")" win. "
	print "("(pw+=(play!=guess))"-"(cw+=(play==guess))")"
	}

Processing the player's input is done rather simply:

<<get input>>=
/^[hH]/		{ play=1 }
/^[tT]/		{ play=0 }
/^[^hHtT]/	{ printf "heads or tails? "; next }

and at the end of each round, if we haven't met a victory condition, we prompt for the next round.

<<check for victory>>=
cw+pw==100	{ printf (cw>pw?"I":"You")" won the match "
		  print  "by "(cw>pw?cw-pw:pw-cw)" games."
		  exit }
pw-cw==20	{ print "You win -- up by 20"; exit }
cw-pw==20	{ print "I win -- up by 20"; exit }
		{ printf "? " }

wrapping up

Now (following good paper-tty style) we provide some help upon startup and a little epilog.

<<mindreader.awk>>=
BEGIN	{
	print "+--------------------------------------------------------------+"
	print "| An AWKward mind-reading machine                              |"
	print "|         (this retrogame inspired by the Bell Labs Memo:      |"
	print "|          Shannon, 1953, 'A Mind-Reading (?) Machine')        |"
	print "+--------------------------------------------------------------+"
	print "Shall we play a game?"
	print "Tell me either 'heads' or 'tails'."
	print "If I guess what you picked, I win.  Otherwise, you win."
	print "The match goes for 100 rounds, or until one player is up by 20."
	printf "your play? "
	}
set seed
consult model
get input
report results
update model
check for victory
END	{ 
	print " T H A N K   Y O U   F O R   P L A Y I N G "
	}

Finally, on POSIX systems, the following line should be uncommented to keep the machine from being overly deterministic. (Shannon and Hagelbargers' devices used rapidly rotating mechanical parts to provide their intial entropy pool)

<<set seed>>=
#BEGIN	{ "date +%s" | getline seed; srand(seed) }

Download code