Sunday, October 4, 2015

Encodings for Tic-Tac-Toe

Peter hurried back to the Library of Alexandria, the message clutched tightly in his fist. He resisted the urge to study the parchment, reading it again wouldn’t help. The message was obviously some form of code, and he had memorized the whole thing in his first glance. The entire message read “23G.” Although he didn’t know what those few characters meant, Peter was certain they were important.

“You received a message,” he called out the moment he entered the library. Half a dozen startled patrons glared at him from their tables. Flushing with embarrassment at his outburst, Peter quietly strode to the main circulation desk.

“You have a message,” he whispered to the head librarian, holding out the parchment.

The elder librarian took the message and read it carefully. After a moment he nodded a few times, saying only, “Interesting.”

“What is it? It is it important?” Peter asked impatiently.

The librarian looked surprised. “What gave you that impression?”

“It’s a code, isn’t it?” answered Peter. “And it came through the wizard’s telegraph office, which must mean it’s important.”

The librarian chuckled softly before explaining, “It’s a move in a game called Tic-Tac-Toe. I’ve been playing with the librarian from G’Raph. She’s quite skilled at strategy.”

“What?”

“Tic-Tac-Toe. It’s a simple game, but most enjoyable,” started the librarian. “It’s a two player game that is played on a three by three grid, where—”

“I know what Tic-Tac-Toe is,” cut in Peter. “But how does ‘23G’ represent a move in Tic-Tac-Toe?”

“Ah. I see where you’re confused. We had to invent an encoding scheme that allows us to play over pigeon message or magical telegraph. It’s really quite a simple scheme. The first number represents the row, the second number represents the column, and the last letter indicates who made the move. We need that last one so we can play different games against other librarians. I’m currently winning two of my three games.” As he spoke, he pulled a few pieces of parchment from under the desk. On the one labeled G’Raph, he carefully marked an X in the third column of the second row.

“But why three letters? Why not just draw out the whole board and pass that back and forth?”

The librarian smiled. “Our encoding makes for a convenient abstraction. We can send those letters by pigeon message, magical telegraph, or even by magical mirrors without needing to change the encoding. Each of those communication mediums uses its own underlying encoding to transmit letters. Pigeon messages rely on written letters, which are really just lines of ink on parchment. The magical telegraph uses a new form of dots and dashes to encode each letter. I have no idea what encoding the magical mirrors use. I think it has something to do with pastel colors. But it doesn’t matter. Regardless of the underlying encoding used to store and transmit the message, we only need to worry about encoding it as letters.”

“You go through all of that for a game of tic-tac-toe?” asked Peter.

“Tic-Tac-Toe is more than just a game,” said the librarian. “It is the ultimate test of strategy. It is a window into a person’s inner-most thinking.”

Peter stared at him in disbelief.

“Now if you’ll excuse me,” continued the librarian, “I have to plan my next move.”

Three days later Peter stumbled into the library, looking as though he hadn’t slept in about three days. He walked up to the main counter and stood there silently, beaming at the librarian.

“Are you okay?” asked the librarian.

“I did it!” Peter practically shouted with glee.

“Did what?” asked the librarian, now thoroughly worried.

Peter’s smile grew even wider. “I created a new encoding for the library!” He waited for the librarian’s gasp of excitement. When the librarian’s face remained blank, Peter added, “An encoding… like for your game of tic-tac-toe.”

“I see. And what’s it for?” asked the librarian.

“Books and scrolls!” Peter opened his arms expansively to indicate the contents of the library.

The librarian considered this for a moment. Carefully he said, “We have an encoding system for books and scrolls. It’s called letters. You use them to form words and… you know, encode knowledge.”

“No. I don’t mean for the content of the scrolls. I mean for the topics,” Peter explained. “I have developed a new system that gives each subject a unique code of three numbers in the range 0 to 255 that represent the category, subcategory, and specialization. So we can encode the contents of any scroll, book, or loose parchment with a three number code.”

“Consider this scroll,” Peter continued, picking a scroll from the return bin. “The subject code is 192.168.1, which translates to the communication category (192), the networking subcategory (168), and the specialization of pigeon networks (1).

“And, like your Tic-Tac-Toe encoding, the subject encoding can be transmitted easily. We can share the encoding with other libraries and use it to request resources. If I wanted a book on ancient history (category 0), of the kingdom (subcategory 0), and the development of new eating utensils (specialty 10), I could send a pigeon message to a library in G’Raph simply stating ‘Request: 0.0.10. Alexandria.’ You see?”

The librarian thought about the scheme for a minute. “I suppose it could work,” he admitted. “But it’s no where near as exciting as exchanging moves in a game like Tic-Tac-Toe. Leave it to you to make encodings so… practical.”

--------------------------

Thank you to Caroline Meeks for suggesting the topic of encodings.

Interested in lower level codings? Learn about binary with Unhappy Flowers and Binary or Using Binary to Warn of Snow Beasts.