Synposis
gawk -f readminds.awk
(then type "h" or "t").
Download
Download from
LAWKER.
Description
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 games 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.
Code
Begin
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 someone gets 20."
printf "your play? "
}
set seed
BEGIN { "date +%s" | getline seed; srand(seed) }
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 }
get input
/^[hH]/ { play=1 }
/^[tT]/ { play=0 }
/^[^hHtT]/ { printf "heads or tails? "; next }
report results
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.
{
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))")"
}
update model
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.
NR > 2 { tally[case] += (hpb == play ? 1 : -1) }
{
hpa = hpb; hpb = play
hca = hcb; hcb = guess
}
check for victory
At the end of each round, if we haven't met a victory
condition, we prompt for the next round.
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 "? " }
end
END {
print " T H A N K Y O U F O R P L A Y I N G "
}
Copyright
Copyright (c) 2009 the authors listed at the following URL, and/or
the authors of referenced articles or incorporated external code:
http://en.literateprograms.org/Mind_reading_machine_(AWK)?action=history&offset=20070207160312
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
