Building a ship in a bottle

Leave a comment

Lately I’ve been having a lot of discussions with people about Computer Science education. Everyone I’ve spoken with is passionate and excited about broadening the reach of CS education, which is really exciting to me: it’s exactly what I want to help with. One thing I’ve been frustrated by, from time to time, is not having a common understanding of what Computer Science education is. I’m not going to say I have the one true definition, but I thought I’d document my thoughts on it so that folks know what my perspective is.

One boon for marketing CS education is that everyone has an amazing supercomputer in their pocket, which can (and often does) run amazing programs; immersive games, augmented reality planetariums, music instruments, social media, and on and on. Being able to say to someone “I can teach you how to make these things and more – only limited by your imagination” is a great lure. It’s also misleading, and here’s where my analogy comes in. I think a smartphone and all of its apps are a lot like a phenomenal Ship in a Bottle. Offering to teach someone how to make an App is a lot like teaching someone how to make a ship in a bottle, without teaching them how to make a ship outside of a bottle first. Sure it’s possible, but it’s missing out on a number of opportunities:

goodwin_blksquall-1-75tequilaFirst, you’ll never be able to make better looking ships in a bottle than you can outside of a bottle. If you want to innovate – make new, cool things that have never been seen before – you should experiment making those things outside of a bottle first, then once you’re happy with them, figure out how to get them assembled inside of a bottle.

Second, to have any chance of getting a novice shipbuilder to make anything they’ll consider acceptable inside of a bottle, you’ll have to give them a lot of parts pre-made, already in a form that can be put in a bottle. After your lesson, if they want to reproduce the experience at home, they’ll have to start with the same parts, which are essentially ship in a bottle kits. If those kits aren’t available, they’ll have to figure out how to back-fill the knowledge to construct them.

Third, and this is where the analogy stretches its limits, if bottle technology changes, the kits immediately become obsolete, and only folks who know how to build these things from scratch will have any chance of keeping up with technology.

For me, the notion of building a ship in a bottle is very much like getting a program to run on any computer, not just a smart phone. Taking a high-level idea of a game, an application, a musical instrument, and turning it into the 1’s and 0’s of the machine code for a specific computer, is a lot like building a ship in a bottle. Computers are crazy time-and-space dilating machines that require processes be expressed in very specific ways (the machine code), and when they are, those processes run at almost-unimaginable speed.

Teaching someone “game coding” using a high-level framework is akin to giving them a Ship in a Bottle Kit, and maybe even a bottle with a hinged bottom. After the class, if you give them a real bottle and raw materials, (no framework), they won’t be able to reproduce that experience.

I’m not saying these experiences are bad at all. In fact, I think they’re great for giving students a sense of “here’s where we’re headed,” and “cool stuff is possible.” But if the only focus is on using kits, students will be fundamentally unprepared for the world where computers, operating systems and languages change with a 3-5 year cycle.

So, what am I advocating?

Teaching someone how to build a ship outside of a bottle includes:

  • Teaching them about how all computers work, all the way from gates, through logic and memory, up to machine code,
  • teaching them about decomposing big problems into smaller steps, and assembling those steps into solutions, and doing so in the context of actually solving problems,
  • teaching them about algorithms: use, implementation, analysis (Big Oh)
  • teaching them about abstraction: using and creating your own,
  • … and more. I think this is very much aligned with the current notions of computational thinking, and the recent AP CS principles curriculum.

An example I particularly like is Google’s CS Unplugged, which is an extreme example of learning about computer science concepts outside of the bottle of computers. Their activity with a Binary Sorting Network can be done on a playground with chalk, and blows kids’ minds when they come out sorted, regardless of what order they start with.

Systems like MIT’s Scratch might seem too much like a ship in a bottle kit in my analogy, but in my (admittedly limited) experience, once a student gets Scratch, they understand programming in a fundamental way. Scratch turns syntax – the icky, in-the-way stuff about programming – into a puzzle-assembly problem, so the students can focus on what they want to express. Later, when they are ready for textual-based programming, the syntax of those languages, when laid out with discipline, actually looks a lot like the similar Scratch program. Brilliant design on their part. The key to making this work is to keep the students exploring, make sure they keep learning from cool projects they like on the website, until they can pretty much create anything they want.

right20tool20for20the20jobWhen teaching programming, I wholeheartedly recommend (when possible) teaching more than one language in a short duration. When I took Intro to CS at UC Berkeley (in 1984!), they taught us Scheme and C in the same year. Looking back on the experience, I think it was really clever: I learned the things that are fundamentally the same between the two, and also the things that are way better in one than the other. Choice of language is a choice of tool, and Mr. Natural’s “get the right tool for the job” was drilled in to me by my hippie dad from an early age.

While it’s totally okay to teach “writing Apps”, or “coding webpages”, it’s important to realize and advertise the limitations (and strengths) of these approaches. Knowing how to “code a webpage” was a lucrative skill in 1999, but quickly became irrelevant as Web technologies advanced. Similarly, we’re way past the time when simply writing an App and uploading it to Apple or Google is the road to a career. The role of teaching these things is to give an early glimpse at what’s at the end of the journey of a CS education. The peril of only using those approaches is that you’re on a never-ending treadmill of needing to take the next class when a new framework or web technology takes over, making your previous skills irrelevant. To stand the test of time, classes like this should include  fundamentals of usability and visual design, not just HTML, CSS and Javascript. On the games side, spend some time investigating what makes an activity fun, not just how to animate sprites using frameworks. Bonus points, on the games side, would be to include learning principles of physics, using a physics simulation framework.

One quote that resonates with me, often misattributed to Edsger Dijkstra, is “computer science is no more about computers than astronomy is about telescopes.” I think this quote may have been mis-used to try to push CS into Math departments, and is at odds with the accurate observation that the pre-eminent professional society dedicated to CS is named The Association for Computing Machinery. I think it’s safe to say that CS is something new: we spend too much time arguing about whether it’s a science, a branch of mathematics, an engineering discipline, or a vocational discipline – it’s all of those things. If you leave any aspect out, you’re missing out on something. Combining them isn’t easy, but if we manage to do it, we’ll be totally surprised at the kinds of things future generations will be building in these amazing bottles.

I’ve got a lot more to say on the subject of CS education, and even about the analogy (compilers are like CNC machines-in-a-bottle), but I’ll stop here for now.

Addenda: less than a week after writing this, I received the latest issue of CACM, and in it was a nice piece titled “Misconceptions About Computer Science.” I think there’s a lot of overlap in philosophy, and I’ve also got some stuff to learn from the authors who have been thinking about these issues for longer than I have, but I was encouraged.


Pokemon Go and graph theory

Leave a comment

Lately I’ve been focusing my efforts on teaching. One thing I’m working on is writing a book about cryptography, math and programming that is targeted at high school-aged students. One of my motivators is equity, so I’m licensing it under a creative commons license, and the source code to the book is here, on github.

Another motivator is enthusiasm – I like to convey my enthusiasm for the material to the students I’m working with. One way to do that is to tap into things they’re already enthusiastic about. For the book, it’s the innate fascination we all have about secret codes.

For this blog post, I’ve got a tidbit about graph theory that is motivated by many folks’ fascination with Pokemon Go. Pokemon Go players do a few different things: they walk around their town collecting items at Pokestops, which are associated with landmarks in the real world:

(image credit: Business Insider)

Some of those items are Pokeballs, which are used to capture the Pokemon creatures that also wander around town. You can evolve and power up the Pokemon you catch to make them more powerful. The reason you care about your Pokemon’s power is that in addition to Pokemon and Pokestops, there are Gymnasiums, which are also associated with real-world landmarks, but instead of having items, they’re places where Pokemon can battle each other. I’ll skip past the part about teams because that’s not relevant, but the part that is relevant is that a Gymnasium can have up to ten different Pokemon in it, and when you battle, you can choose six of your Pokemon collection to fight against the ones in the Gymnasium. The question is: “how do you choose which Pokemon to battle?”

It’s a good question because the designers of the game created complex varieties of Pokemon (e.g., Fire, Grass, Electric, Poison, etc), and a complex hierarchy of strengths and weaknesses among them. So, for example, it’s easy to remember that if you’re going up against a Fire-type Pokemon, that a Water-type Pokemon has a strong advantage. On the other hand, Fire has an advantage against Grass and Ice. It’s a lot like rock-paper-scissors, but with over a dozen types instead of just three. Even more complex than the Big Bang Theory’s rock-paper-scissors-lizard-Spock.

Now we’re up to where Graph Theory can help. Just as this link shows the interactions between rocks, paper, scissors, lizards and Spockrpssl

In computer science, the above diagram is called a graph. It’s not the same as the graphs we draw of functions, so it’s kind of a confusing name, but you get used to it. These kinds of graphs have nodes and edges. If the edges have arrows, it’s called a directional graph (digraph for short). What this graph tells us is that an arrow from one node to another means that the node “beats” the one it points to.

We’d like a similar diagram for Pokemon Go. It’s subtly different: instead of a simple “Fire beats grass” relationship, we have “Fire is unusually strong against grass”. Even so, this is important information. With a simple cheatsheet like this, we could go up to any Gymnasium with a decent collection of Pokemon, and do serious damage. Also, we could learn which Pokemon we should add to a Gymnasium to make it stronger. So, how to do this?

I started by Googling for “Pokemon Go rock paper scissors” to get a list of the strengths and weaknesses of Pokemon creature types. This list seemed good for my purposes. I don’t know how accurate or authoritative it is, but that’s not as important as what I did with the information. What I could have done is use an art program to draw the graph. The drawback of this approach is that it is very “brittle”, meaning if I want a different layout I have a lot of work to do, or if the data is wrong, I have do a tedious search through the diagram.

What I did instead is use a tool that is designed to take a definition of a graph as its input, and to create pretty drawings of them. The tool I used is called graphviz, and it’s quite powerful and configurable.

The input to graphviz is called a “dot” file (the filenames end in .dot). Here’s my conversion of the above Pokemon database into a dot file:

digraph Battles {
 node [margin=0 fontsize=24 shape=plaintext ]
 # layout=circo
 Fire -> Steel
 Fire -> Bug
 Fire -> Ice
 Fire -> Grass
 Water -> Fire
 Water -> Ground
 Water -> Rock
 Grass -> Water
 Grass -> Ground
 Grass -> Rock
 Electric -> Water
 Electric -> Flying
 Ground -> Fire
 Ground -> Electric
 Ground -> Poison
 Ground -> Rock
 Ground -> Steel
 Rock -> Fire
 Rock -> Ice
 Rock -> Flying
 Rock -> Bug
 Fighting -> Normal
 Fighting -> Ice
 Fighting -> Rock
 Fighting -> Dark
 Fighting -> Steel
 Flying -> Bug
 Flying -> Fighting
 Flying -> Grass
 Ice -> Grass
 Ice -> Ground
 Ice -> Flying
 Ice -> Dragon
 Poison -> Grass
 Poison -> Fairy
 Psychic -> Fighting
 Psychic -> Poison
 Steel -> Fairy
 Steel -> Ice
 Steel -> Rock
 Bug -> Grass
 Bug -> Psychic
 Bug -> Dark
 Dragon -> Dragon
 Fairy -> Fighting
 Fairy -> Dragon
 Fairy -> Dark
 Ghost -> Psychic
 Ghost -> Ghost
 Dark -> Psychic
 Dark -> Ghost

It’s really simple: to say that Dark Pokemon are strong against Ghost Pokemon I wrote “Dark -> Ghost” and so on. Then I loaded this file into graphviz (with and without the “#” in front of layout), I got these two images:


If you look closely you’ll see they have the same set of relationships, they only differ in how they’re laid out. Pretty cool, huh? So if you encounter a Gymnasium that has a Nidoking (ground/poison), Rapidash (fire), Snorlax (normal) and Gyrados (flying/water) you can use this chart, and know that you could choose a Water, Water, Fighting and Electric Pokemon to defeat them. Note that some Pokemon, like Nidoking, have two types, so you want to choose an opponent that is strong against one or both types, but is not weak against either. In this case, water fills the bill. Water works against fire, then you see that the only thing good against normal is Fighting, and finally electric against flying/water.

A nice follow-on activity, now that we have this graph, is to optimize sequences of Pokemon in Gyms so that it’s as hard as possible to defeat them. You’ll note that our above example had two water-type weaknesses in a row – you’d want to avoid that. After that, you’d like to find, given a set of Pokemon, which ones you can safely trade away, because their strengths are subsumed (dominated in CS-speak) by other Pokemon. And so on — there’s a lot of meat in this graph!

Installing MITE (minecraft is too easy) mod on MacOS

Leave a comment

Thanks to a pointer from our neighbor (hi, Sten!), I decided to try to install MITE on my Mac.

It turns out the very good instructions in the MITE zipfile are very much Windows-specific. If you try to follow them as best you can on a mac, it’s probably not going to work.

Here are the Windows instructions: (interspersed with my MacOS translations)

Step 1 = Paste this folder into .minecraft versions folder if you have not already done so =

open Terminal and type

cd ~/Library/Application\ Support/minecraft

Step 2 = Copy 1.6.4.jar to this folder =

cd 1.6.4-MITE
cp ../1.6.4/1.6.4.jar

Step 3 = Rename it to 1.6.4-MITE.jar =

skip this step

Step 4 = Open 1.6.4-MITE.jar using WinZip or 7Zip =

First, in terminal type “open .” to fire up the Finder in this folder
In Finder, double-click on “” – it will create a folder called “original”

Step 5 = Delete META_INF folder inside =

In Finder, open your “original” folder, and delete the META_INF folder in there

Step 6 = Copy contents of class Files folder into 1.6.4-MITE.jar =

This is the key place where Windows and the Mac differ. If you drag the contents of “class Files” to the “original” folder, it will clobber important files. Instead, open the “class Files” folder in Finder, select all of its contents (first click on a.class, then press Cmd-a to select all), then drag those files to the “original” folder. It will ask if you want to keep or replace. IMPORTANT: hold down the Option key, and the “Skip” button turns into “Keep Both”. Select that.

This procedure does the important interleaving, then create the new, modified jar file with these commands (you have to have the “JDK” installed):

cd ../original
jar cf ../1.6.4-MITE.jar .

Step 7 = Move MITE Resource Pack to the resourcepacks folder in .minecraft =

this is right, except drag it to “~/Library/Application Support/minecraft/resourcepacks”

Step 8 = Run the Minecraft launcher and edit your profile to use 1.6.4-MITE version =

Step 9 = Play Minecraft and select the MITE Resource Pack =

Yay – it should work!

The error message I kept getting when I followed the windows instructions was:

java.lang.NoClassDefFoundError: net/minecraft/client/main/Main

It was that error that lead me down the path of the solution. I checked the contents of my improperly-created jar file with the command

jar tf 1.6.4-MITE.jar

and saw that indeed there was no “net/minecraft/client/main/Main” entry. From there, I saw that the directory path in the “original” directory was deleted with the drag-and drop operation, and remembered the “tar” command solution to interleaving-copies (and then, thanks to Google, found the way to do this in Finder).

I hope this helps someone else install (the excellent-but-very difficult) MITE mod to minecraft. Apologies for the built-in dependencies on knowledge of “Terminal”, and assuming you’ve installed the JDK. It’s very possible you could avoid those dependencies, but this was my way of fixing the problem.

First shot at a family role-playing game

1 Comment

Back when I was kid, Dungeons and Dragons appealed to me very much, but I think I was intimidated and/or too isolated to actually join a gaming group and play.  I made quite a few very detailed maps of underground caverns, but never did anything with them.

Many of my friends (hi Isaac, Andy & Martin!) enjoyed and still enjoy RPG’s, but I am still too intimidated at the level of commitment joining a serious group would entail. A couple months ago, I saw an inspirational impromptu RPG-like exchange between two anonymous users of “Omegle”. The story matter and level of violence were too intense for my taste (in terms of anything I’d do), but the lightness of touch and free flowing nature of this inspired me. “I could do that!”

So, I thought I’d try my family out on the activity.  I read up on how to run a “rules-light” RPG, and was inspired very much by the FUDGE and FATE folks, and especially by Robin’s Laws of Good Game Mastering.  Finally, this week, I decided to take the plunge…so I drew an outline of a map of an island on parchment paper, and just left it out overnight for the kids to see. 

Sure enough, the next morning morning they asked questions (I’d planted the seeds of doing a “do-it-ourselves game” earlier), and when I came home that night, Audra really wanted to work on the map and the game.

Here’s what we did:

Audra and I added rivers, mountains, cities, lakes (there’s a robber’s forest, too! and a mountain with a dragon inside). Then we drew another map of the main city that surrounds a castle.  Here we started adding details like a “market circle”, the castle inside, blacksmith, a magician’s hall, etc.

At this point, Colin joined, and he wanted to draw on the map at the same time.  Since Audra and I were still drawing, we let Colin add a lake outside the town, but then he got some paper from upstairs and had me draw a big circle, and then drew the entire planet.  He asked me to draw a small version of our island on the map, and then surrounded it with many, many other islands.

At this point, Audra wanted to “start playing”!  I pointed out that we _were_ kind of playing, and she said “you know, I want to do stuff!”  So we decided to choose our characters.

Audra’s character is named Arrowbird.  She’s 21 years old, 6 feet tall, is 3/4’th Elf and 1/4th human. Her human ancestors were warriors, and the elven ones were magicians. Her character is very familiar with Greek mythology, speaks Greek well, and is good with animals.  She lands on our island from overseas (Greece?) with a backpack, dagger and 500 gold pieces.

Colin’s character is named Moje.  He’s 14 years old, and a Dwarven Mage.  He’s really good at spells (for a 14-year old), especially spells that move stuff.  I’ll roll the characters specific attributes at some point, but I thought I’d hold off a bit.

Arrowbird wanted to own a horse.  I mentioned to her that horses are expensive to feed.  She asked how much — I said about 5 gold pieces a week. (I guess this was an Audra->GM meta-discussion)  She did some calculating, then asked how much a big dog would take to feed.  I tried to say almost that much, but she bargained me down, clever thing.

In parallel with that discussion, we said that Moje was dropped off in town by his parents to apprentice as a magician, also with a leather backpack, the family wand and 500 gold pieces.

Arrowbird decided her first task was to buy a big happy dog (like our neighbor’s Burmese Mountain dog, I suspect).  Moje decided he wanted a small, warrior dog.  Colin went back to drawing his globe.  Arrowbird went to the market and asked the woman how much a dog was. The woman told her 100 gold pieces. Arrowbird balked, and said “what would it take for the price to be 25?”  I rolled our dice, and the answer came out slightly negative, so I said “it would take about 75 gold pieces for the price to be another 25”.  She asked if there was anything she could do for the woman.  The woman replied that there was a wolf nearby her farm that occasionally kills dogs, and that if Arrowbird could take care of that problem, it would be worth 75 gold to her.

At this point, it was time to go to bed, but Audra’s wheels were churning.  By the time she was climbing in to bed, she was going to attempt to tame the wolf to get a pet for free and earn 75 gold.  I told her “that’s interesting, but don’t count on that working — only the dice will tell for sure!”  She said “okaaay dad…but I want you playing tomorrow — that way it’s not just dice I’m working with…”

Oh boy, I think we’ve created a monster (or four).  All of this was about 2 hours from start to finish.

Read and post comments | Send to a friend