Saturday, June 4, 2016

Claude Shannon Centenary and the 1-bit Maze (A-Maze-ing Dash Challenge)


The Claude Shannon Centenary 2016 in Hong Kong is a series of events held in Hong Kong to mark the life and legacy of Claude Shannon, an American mathematician and engineer, who was a visionary pioneer in the fields of computing, communications and artificial intelligence.  I chaired a seminar on quantum information theory given by the 2016 Shannon Award Lecturer Alexander Holevo on May 6th.  A Claude Shannon Centenary workshop was also organised on May 19th by Professor Raymond Yeung at the CUHK Institute of Network Coding, where I gave a talk titled "To prove or to disprove: information inequalities and sparse optimization". 

I also delivered this as an invited talk at Tsinghua University in Beijing on May 14th ("纪念Shannon诞辰一百周年学术论坛"). My talk was on the automated generation of mathematical proof to Shannon-type inequalities in information theory using linear programming and cloud computing.  Fancy that! A topic that would be impossible without Shannon's Master thesis that engendered the birth of digital logic in 1938 and his seminal work on information theory in 1948, and these two seemingly-disparate subjects converge!




A local outreach activity Computer Science Challenge was held on 21 May at the City University of Hong Kong for 180 middle school children (62 upper primary and 118 secondary school students) who formed teams to compete in three digital game challenges. The CS Challenge is part of the Claude Shannon Centenary, 2016 Hong KongDuring the CS Challenge, educational exhibits of Claude Shannon and replicates of his fun and thought-provoking robotic machines Rubik-cube manipulators using Lego — were also on display



One of the CS Challenge's tasks was to program a robot to solve a maze. This was inspired by Shannon's Maze-solving Theseus Mouse, which was the world's first digitally-programmed maze-solver in 1951. Shannon's Theseus Mouse ushered in the age of machine intelligence when a computer (using telephone relays) is capable of searching for a solution by trial and error and then remembering the solution. It was also Shannon's Theseus Mouse that inspired Paul Baran, the Internet pioneer to come up with the packet switching principle and dynamic routing underlying our Internet technologies.

The maze in the CS Challenge for secondary school students was designed with Shannon's entropy  a coin flip decides one of two possible maze entrances, i.e., the robot starts from the left entrance with a Head or otherwise from the right entrance with a Tail. The left and right entrances entail a left and right corner respectively, and the two passages meet at the intersection of a corridor to the exit. Now, a fair coin flip generates one bit of informationIn this way, as the coin is flipped only after the robot has been programmed, this 1-bit uncertainty prevents the participants from hard-coding the robot's movement (i.e., no dead reckoning); The robot has to hit an obstacle (i.e., the corner wall) and navigate its way by trial and error. We hope that students know about Claude Shannon and his marvellous creations as they bravely enter the Maze as Theseus did. Check out more pictures and the video below on the 1-bit maze. What a memorable and a-maze-ingly fun 2016 CS Challenge we had!