Differences

This shows you the differences between two versions of the page.

--- en:shannon:mrm [2024-03-24 11:36] – Link to Hargelbarger paper rainer
+++ en:shannon:mrm [2024-08-28 09:52] (current) – rainer
@@ Line 1: / Line 1: @@
-====== Shannon's Mind Reading Machine ======
+<nimla>
-An early attempt to create machines that can adapt to changing sitiations by predicting non-random sequennces, D.W. Hagelbarger built his SEER, the ''SEequence Extrapoloation Robot''. Claude E. Shannon seemed to discussed the matter intensively and made a similar machine, based on Hagelbargers copy, smaller and adopting quicker.
+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.
-====== References ======
+Shannon´s Theseus
+-----------------
-- D.W. Hagelbarger: "SEER, A SEquence Extrapolating Robot".
+In his mouse labyrinth "Theseus" [[Shannon1952]],
-IRE Transactions on Electronic Computers, March 1956, pp. 1-7 {{:shannon:hagelbarger1959_seer.pdf|}}
+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.
-- Claude E. Shannon: "A Mind-Reading (?) Machine". Bell Laboratories Memorandum, March 18, 1953.
+This machine finds a solution in a basically static environment
-Reprinted in "Collected Papers" by S. Wyner, pp.688-690. {{:shannon:shannon_mindreadingmachine_searchable.pdf|Searchable Copy}}
+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,
+.
+\::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>