“Art Heist”: Error-Correcting Codes Made Accessible

Information Theory (Winter 2020)

Diwakar Ganesan, Madison Hurr, Colleen Dai and Alexandre Bucquet

 

This quarter, we set out to build a game to engage middle schoolers with the concept of error-correcting codes. We believe that this is an interesting project because error-correcting codes are central mechanisms in any transmission system, from communication through the Internet to deep space transmission. We hope to teach students with our interactive and memorable game such that they can have fun playing and learn more about error correcting codes while doing so.

In order to design our game, we studied some guiding principles of early secondary education. The first important conclusion that we drew is the importance of multiple teaching mediums. Students in diverse classrooms learn in different ways. Some are effective visual learners, others are effective auditory learners, and still others learn best by doing. We tried to incorporate all these styles of learning into our game design, using a concrete storyline, colorful pieces, a walkthrough video, and a guided worksheet

Other education researchers have recently commented on the effectiveness of student participation. A great way to introduce a new topic is to have students research it superficially on their own and present their findings to their peers. Such a tactic works best when the new material is sufficiently motivated by the teacher, so the students understand why they should care about the subject. This motivated our decision to build a game for students to play. In our design process, we made sure to motivate the use of error correcting codes using a small introductory segment. We kept it short and to the point as to not lose the attention of our students. In the worksheet, we made sure to guide students through the different rounds of our game while still giving them enough room to work things out on their own. While we had a solution prepared for the game, we don’t explain it immediately on the worksheet, but we challenge the students to think critically about how to find a solution to the puzzle that we give them. Structuring our game like this enhances the learning experience and encourages creative thought.

Our game is titled “Art Heist”. It involves three primary characters: the “genius” artist, the infamous art thief, and a renowned art historian. The artist paints a beautiful picture utilizing the squares colored red, blue, and yellow in the artist’s set, and the thief replaces one of the squares with another color (red, blue, or yellow). The art historian’s goal is to recover the original painting. The artist and art historian win if they are able to recover the original painting, and the thief wins if the artist and art historian are unable to do so. This game’s objectives are as follows:

  1. General understanding of error correcting codes — what does this field consist of? 
  2. An understanding of effectiveness of a code: what are the benefits of each code proposed, and what are the weaknesses?
  3. An overall intuition of “parity” — xoring two numbers, or in this case, mixing two colors. 

We created a game board and game pieces for Art Heist, and we also crafted a worksheet that will allow instructors to smoothly administer the game. We would love students to think about more schemes that can result in recovered art, along with how to correct for multiple changes and possible removal of squares by the thief. The game is loosely based on the notion of parity checks, and if the students are interested in real-world schemes, the administrator can explain the basics of Hamming Codes. Overall, we believe the game is an effective way to increase interest in error correcting codes and help students obtain a basic intuition as to why error correcting codes are both interesting and important. 

This slideshow requires JavaScript.

There were several other games we designed for the outreach event. The first was a Group Testing game with water and vinegar. Students are given 8 cups of water (labeled “A”-“H”), one of which has vinegar mixed in. They are also given 3 empty cups they can use for mixing. The point of the game is to figure out which cup has the vinegar, by only tasting 3 cups. We would help brainstorm ideas with the students until they came up with the optimal strategy: for example, mix “A”-”D” and “E”-”H” into separate cups. Whichever cup tastes vaguely vinegar-like is the group that has the vinegar. Then, you could mix half the cups in that group into separate cups, and test again. This way, in just 3 tastes, you can narrow down to the cup that has the vinegar in it. 

Another game we crafted would model communication channels that had the possibility of adversarial errors. In this game, there would be three players: Alice and Bob, who want to communicate with each other, and an adversary Eve who wants to eavesdrop on Alice and Bob. In this game, Alice will think of a word she wants to say to Bob, but instead of saying the word itself, she will give Bob a hint as to what the word is. If Bob knows the answer, they will shout “1, 2, 3!” and then shout the answer they are thinking of. However, Eve is also listening to what Alice is communicating, so Alice must give a hint that only Bob knows the answer to. For instance, if the word was “birthday”, and Bob knows that Alice’s birthday is on January 1st but Eve does not, Alice can yell “January 1st!”, and Bob could shout “1,2,3, birthday!”. If Eve can guess the word that Alice is thinking of, then Eve wins, However, if Bob and Alice can communicate without Eve successfully guessing the message, then Bob and Alice win. 

This game provides basic intuition into adversarial errors, and also the usage of cryptosystems in cryptographic schemes that are based on error-correcting codes (for example, the McEliece cryptosystem). 

Want to play the game for yourself? Click here to download our worksheet!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Game Set:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.