Retro Computer Laboratory

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<nimla>

Shannon´s "Mind-Reading Machine"

Author: Rainer Glaschick, Paderborn (rainer@glaschick.de)
Date: 2024-08-26
Version: 0.1

Background
==========

Claude E. Shannon had built small adaptive demonstrator Machines
with relays in the 1950 decade.

Shannon´s Theseus
-----------------

In his mouse labyrinth "Theseus" [[Shannon1952]],
a mechanical mouse learns its way through a maze
and repeats this as long as the maze is unchanged;
even after a change, a new path is found.
The found path is not necessarily the shortest, but does not
use blind alleys.
Two replicas have recently been build by the Heinz Nixdorf MuseumsForum
(HNF) in Paderborn (Germany).
They are regularly demonstrated in the HNF and the MIT Museum (MITM)
in Boston (USA).
While the outer appearance is very close to the original,
the driving electronics uses modern technology.
Shannon explains his machine in a film,
which was used to verify that the replica has the same behaviour.

This machine finds a solution in a basically static environment
that does not depend on the moves of the machine.

The Mind Reading Machine or Penny Matching Game
---------

In the same decade, Claude E. Shannon and David W. Hagelbarger created --
still in relay technology -- machines that could adapt their behaviour
in a dynamic environment like a game, where two opponents
change their behaviour while playing.
Two articles are well known describing the machines;
a rather short report in 1953 by Shannon with the title
"A Mind Reading (?) Machine" [[Shannon1953]]
(also known as "Penny Matching Game"),
and a more detailed article in 1956 by David W. Hagelbarger
with the title "SEER, A SEquence Extrapolating Robot"  [[Hagelbarger1956]].
It refers to Shannnon´s machine as a simplified
version, while Shannon´s article has no hint to Hagelbarger´s.
Also, Hagelbarger writes that the two machines played
against each other by using a third "umpire" machine.
While this suggests that Hargelbarger was the original developer,
Shannon may have inspired his work and participated in the development.
Shannon and Hagelbarger have published in 1954 und 1955 articles
together, thus -- independent from the credits in Hagelbarger´s article --
a cooperation of both might be assumed so far.

Both articles include schematics for the machines,
thus creating replicas was considered feasible.
Shannon´s machine still exists in the MITM and seems to be
in a fairly good condition that might allow to take it into
operation.
Hagelbarger´s machine seems no longer to exist;
just a photo of unknown provenance has been found (in the Web) so far.

The replicas
============

Intermittently, I have studied in particular Shannon´s machine since 
the original came to the HNF on loan from the MITM
for the Exposition "Codes & Clowns" in 2009.
My intention was from the beginning 
to finally make a replica using relays as in the original.  

After a closer look at the schematics, one error was evident,
and another one fairly probable, both  typos in the contact
designations ('W2' instead of 'W1´' and '1´' instead of '1').

Thus, it was useful to simulate the circuit in software,
which was done by translating the relay circuit to
logical expressions in a programming language.
In addition to a command line version, the software was also
used in a small Arduino-based board,
that could be used stand-alone and with an interface to keys
and lamps as with the original.

To verify the behaviour further, another software simulator
was made from the description in Shannon´s (and
Hagelbarger´s) article.

Some other software emulators can be found on the web;
and many of these are considered  unsatisfactory.

In particular, Shannon has used a user interface
that reveals the machine choice before the human opponent enters his,
in order that the machine cannot cheat.
Some software implementations require to trust the code that only
reveals "win" or "loose", not the machine´s choice,
and may also use more resources than the original. 
Shannon´s not a gaming device for enjoyment, but a device to demonstrate
the credibility of machine learning (in is beginning).

Finally, I made two two replicas for the HNF close to the original,
except the counter, an optical sensor for the random device,
and LED lamps for the memory state.
The housing and the linear counter (using modern gear)
have been made by Volker Morawe.

These two replicas use Shannon´s schematics. 
Correcting the above two errors was necessary, 
but not sufficient for satisfactory operation.
Inserting a contact was the minimal change needed; see
next section and my report (on request).

It is assumed that the latter ommission had later been detected,
perhaps by using the umpire machine playing Shannon´s against
Hagelbarger´s machine.


Verification and Testing
-------------------------

To assure that the machine is performing satisfactory,
systematic testing is essential.
Just trying not to loose is not sufficient, as the three errors
do not clearly manifest this way,
because the player tries to enter unpredictable sequences,
that are essentially not reproducible.

Testing and Verification concerns in particular:
- The original machine is no longer available for comparison.
- The random number generator prevents deterministic tests.
- Shannon and Hagelbarger claim that to force the machine to loose
requires simulating its state and a response dependent on the history.

To supply random input (as claimed by [[Poundstone2014]] to "beat"
the machine by not loosing)
is evidently  futile.
If the input sequence is truly random, the result can only be 50% wins,
otherwise the machine could predict the claimed random sequence,
in whatever direction.

In any case, the basic testing must show that the machine reliably
wins for some defined input sequences, that are:
- 'S': play the same always (e.g. 'llll&hellip;', 'rrrr&hellip;')
- 'D': play different each time (e.g. 'lrlrlrl&hellip;')
- 'SD': play the same, then different (e.g. 'llrrllrrllrr&hellip;')
- 'SSD':  play the same twice, then different once (e.g. 'lllrrrlllrrr&hellip;') 
- 'SDD':  play the same once, then different twice (e.g. 'llrlllrlll&hellip;', 'rrlrrrlrrr&hellip;')

In the first three cases, the machine must win continuously ("track"),
and in the last two it should win twice as often as loose (2:1 ratio).

All these could only be achieved by applying the three changes to the
original schematics.

For the sequences 'SSSD' and 'SDDD', the corrected machine(s) did win
with a small margin;
and for 'SSDD', the result was at par.

Longer sequences were not evaluated extensively,
as they contain the above winning sequences and are thus bound to win.

Thus, the independent sequence 'SSDD' ('lllrlllrlllr&hellip;'
or 'rrrlrrrlrrrl&hellip;' )
is the only one to play at par.

The relay replicas use lamps (LEDs) to indicate the state of the memory
(not present in the original);
they showed that half of the memory was unused unless the circuit was
corrected (third error).

All tests were used to verify the final relay replicas,
the software simulation of the published schematics (with all
combinations of error corrections)
and finally the schematics independent software version
[[Glaschick2024a]].

 


Appendix
======


Literaturverweise
----------

\::Hagelbarger1956
     D. W. Hagelbarger: "SEER, A SEquence Extrapolating Robot".
     
     IRE Trans. on Electronic Computers, March 1956, pp. 1-7

\::Shannon1952
     Claude E. Shannon: "Presentation of a Maze-Solving Machine".
    
     Transactions 8th Cybernetics Conference, Josiah Macy Jr. Foundation,
     1952. 

\::Shannon1953
     Claude E. Shannon: "A Mind-Reading (?) Machine".
     
     Bell Laboratories Memorandum, March 18, 1953.
     Reprinted in "Collected Papers" by S. Wyner, pp.688-690.
     
     See also [https://this1that1whatever.com/miscellany/mind-reader/Shannon-Mind-Reading.pdf]

\::White1959
    Gerald M. White: "Penny Matching Machines".
    
    Information and Control 2, 349-363 (1959)

\::Breazu2020
    M. Breazu, D. Volovici, D. Morariu, R. G. Cretulescu:
    "On Hagelbarger’s and Shannon’s  matching pennies playing machines".

    DOI: 10.2478/ijasitels-2020-0003

    [https://intapi.sciendo.com/pdf/10.2478/ijasitels-2020-0003]

\::Poundstone2014
    Willian Poundstone: "How I Beat the Mind Reading Machine".
    [https://william-poundstone.com/blog/2015/7/30/how-i-beat-the-mind-reading-machine]

    Dated July 14, 2014, retrieved 2024-08-27

\::Glaschick2024a
    Rainer Glaschick: "Correcting The Schematics Of Shannon´s &quot;Mind-Reading Machine&quot;"

    [[MRM_Variants]]

    
        


\ASCIIMathML ./ASCIIMathML.js

\CSS print pre, blockquote {page-break-inside: avoid; } 
\CSS all pre, blockquote, code {font-family: "Liberation Mono", courier, monospace; } 
\CSS all pre {font-family: "Liberation Mono", courier, monospace; margin-left: 3em} 




</nimla>