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…', 'rrrr…') - 'D': play different each time (e.g. 'lrlrlrl…') - 'SD': play the same, then different (e.g. 'llrrllrrllrr…') - 'SSD': play the same twice, then different once (e.g. 'lllrrrlllrrr…') - 'SDD': play the same once, then different twice (e.g. 'llrlllrlll…', 'rrlrrrlrrr…') 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…' or 'rrrlrrrlrrrl…' ) 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 "Mind-Reading Machine"" [[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}