Mind reading machine (AWK) – LiteratePrograms

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 23 = 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) }


Source link