HopScotching towards Quantum Computing

Tags

Computers, Hopscotch, Minecraft, Physics, Programming, Quantum mechanics

Leo’s FLG (Focused Learning Goal) for this year is to build a real quantum computing mod in MineCraft. (Note that the kids set these goals for themselves at the beginning of the year, and although I might have slightly influenced his choice of project, the “in MinceCraft” setting was all Leo!) This came from several sources, aside from just the obvious entanglement of his interest in quantum computers with MineCraft. The main one is that there are two quite cool MineCraft mods, one, called qCraft, that adds a sort of quasi-quantum mechanics, and another, called Mekanism, that adds all sorts of advanced devices, esp. lasers. The qCraft mod actually has quantum computer components, but they are not very elegantly done; We wanted to make it a little more like a real quantum computer by using the Mekanism lasers as the qubit sources, and then add optical components for the gates.

(If you don’t know what the heck I’m talking about, there are innumerable videos on quantum computation on youtube, but if you REALLY want to understand it, I strongly recommend this excellent set of short lectures by Michael Nielsen, which not only nicely demystifies quantum computers, but at the same time demystifies quantum mechanics!)

Anyway, so we needed to get our feet a tiny bit wet toward this pretty massively complex FLG. Unfortunately, direct MineCraft modding is done either in Java or Python. (There are a few little experiments in modding in scratch-like languages, but, much as they are nice tries, they have issues, so I decided not to bother with them, at least for the moment.)

To get our feet wet using a programming paradigm that Leo already knows, we chose HopScotch. Together we created a highly simplified quantum computer game in HopScotch. We only have one gate, a Hadamard gate, and the quantum state is highly simplified, having only the possibilities of being 1 or 0 or 50/50, no complex numbers nor normalizations.

But it’s kinda cool, none-the-less:

The circle represents a qubit that might be a photon, for example, and its color represents its quantum state: green is definite 1, and red is definite 0. It travels a continuous loop from left to right, and then re-appears on the left again, as though it’s on a quantum wire that’s looped around from the end to the start.

When the program starts, the photon’s quantum state is definite 1 (1.0|1>+0.0|0>), and so the photon is green. The M box on the right measures the quantum state, “collapsing” it to 1 or 0. If you just let the program run from the start without doing anything (as above), the measurement gate will just keep reading 1, and incrementing the 1 count. The photon will just stay green.

The hex is a Hadamard gate (H gate), which splits the quantum state in half: 0.5|1>+0.5|0>. (Remember that we’re simplifying here, so there are no complex values or normalizations, and I’m using probabilities instead of amplitudes; I did say “simplified” and “baby steps”, right?!) If you drag the hex into the photon’s path (pic below), the state becomes a mixture of 1 and 0, and the color becomes a (ugly) mixture of red and green:

When the qubit in this 50/50 state gets measured (that is, when it hits the M gate), there’s a 50/50 chance of “collapsing” into a 1 or a 0. It’ll change to either red or green, start again at the left, hit the H gate again, and so on. If you let it run like that for a while, the counts of 1 and 0 will come out the same, statistically speaking.

You can try it out yourself on HopScotch on your iPad. (I’m told that HopScotch now allows you to run code in your browser, so you don’t need to actually have HopScotch on an iPad, although I highly recommend HopScotch on an iPad!)

---

---

 

Livestock Crisis Algebra

Tags

Algebra, Math, Minecraft

Leo’s been reading an Algebra book, and giving me problems from it.

[Teaching principle [1]: Don’t give kids problems; Instead, let them give YOU problems, at least for a long time into a new subject. Pretend to struggle, and show your work in detail. Get things wrong occasionally. This models how to do the problem, correct mistakes, and shows that mistakes are no big deal. And if you make it look fun enough, you being an idiot will keep their attention for hours! Eventually you can expand the game to you asking THEM question!]

One of the problems had to do with farm animals. MineCraft has many funny creatures. Early on Leo’s exploration, he and I would play together in worlds he was creating [2]. In order to be maximally annoying, I would flood his creations with animals — pigs, mostly. Leo dubbed this a “Livestock Crisis”, and would get very upset at me; Success! 🙂

Anyway, this created an excellent opportunity to do some on-the-spot MineCraft Math!

We started with the problem of how many pigs you could fit into a pen of a particular size, like this one (note the curious chicken!):

This isn’t a completely trivial problem because you have to calculate the inner area, not the outer area, and then divide by the area taken up by a pig. Okay, it’s pretty trivial (but not for a 7 year old)!

In the example above, the outer area is 10×14 block, and the walls are 1 block thick. We assumed that a pig is 2×1 blocks. We calculated the area for this problem: (14-(2*1))x(10-2*1)) => 12*8 => 96sqbks (square blocks). So, you should be able to get 96/(2*1) => 48 pigs into that space.

Here’s 48 pigs:

Uh oh. That definitely doesn’t look right! Hmmm.

Before trying to fix it, let’s turn the whole thing into a formula: Let L and W be the length and width of the outer wall of the pen, and T be the wall thickness. And let A (or P for a pig) be the ground area of an animal. Taking our math above:

(14-(2*1))x(10-2*1)) => 12*8 => 96sqbks, and
96/(2*1) => 48

and just replacing the right symbol for each number:

1=>T
14=>L
10=>W
((L-(2*T))*(W-(2*T)))=>(14-2)*(10-2)=>12*8=96
2=>P
((L-2T)*(W-2T))=>(14-2)*(10-2)=>12*8=96
96/P=>96/2=>48 … Voila … well, sort of, but it didn’t work.

So, the only thing that we made a rough estimate of in the above was the ground area of a pig. We guessed 2×1 = 2sqblks. But in reality, a pig is 0.625 blocks wide and 1.25 blocks long, which is only 0.78sqblks!

Okay, so let’s use our formula to make a new estimate. Mostly things are the same:
T=1
L=14
W=10
((L-2T)*(W-2T))=>(14-2)*(10-2)=>12*8=96

But the pig (P) is WAY smaller:
P=0.78

So the result is WAY bigger!
96/0.78=123 pigs !!!

(It jut occurred to me that I should be teaching Leo dimensional (i.e., unit) analysis at the same time… Oh well, next time!)

Okay, so 123 pigs … well, here’s about 123 pigs.

We actually lost count a couple of time, so we don’t really know how many pigs are in this pic, but it’s definitely about 123, probably only +- 1 or 2. And yeah, that looks WAY better!

For the record, again not that you can read this, here’s the white board recording our process:

Notice our incorrect analysis of pig size at the top, and the 3D model of the pen at the bottom. (We very quickly realized that the height isn’t relevant, except that pens have to be 2 blocks high to keep the animals from escaping!) At one point I also tried to simplify the polynomial product by multiplying it out by FOIL. I was so pleased with myself demonstrating how to simplify the expression in this way that it was a bit of an embarrassing letdown, not to mention confusing to Leo, when I got to the end and the multiplied-out form was not nearly as nice as the factored form! I guess that trick is really only useful for complex moduli, as in quantum mechanics.

Down the left side is another problem we did once we had the formula, applying it to 3×2 cows in a 100×100 pen with 2 block thick walls. Ready? 644 cows!

Notes:

[1] I’ve just now raised this to the level of a “principle”, but don’t listen to me; I’m just making this up as I go along; What to I know about teaching!?

[2] One of the great things about MineCraft is that it’s designed for users to play collaboratively in the same world. (In the iOS version of MineCraft this is incredibly simple if you’re on the same LAN; When you create a world, it automatically starts it as a server, and opens a port to it, and anyone else on the same LAN can just connect directly to it. This is quite impressively well implemented!

---

---

 

MineCraft Seeds & Random Math

Tags

Algebra, Computers, Cryptography, Logic, Math, Minecraft, Philosophy, Probability, Programming, Quantum mechanics

[It slightly bothers me that the last few posts are mostly MineCraft-related. But as Leo has been getting more and more interested in nuances of MineCraft, I’m trying to guide this interest toward math instead of evil. (And “evil” in MineCraft is quite a lot less evil than with many other things he could be getting addicted to.) (Some day I’ll talk about MineCraft addiction management strategies … when I figure some out!)]

One of the (many) good things about MineCraft is its programmability, which I’ve mentioned before. But there’s even a simpler sense in which it’s sort of programmable, which is that you can set the randomization seed when you create a world. Leo got into this because one of the other good things about MineCraft is that there is a community, even at Leo’s age, of kids (of many ages!) who have explored a huge amount about the world, so he learns from his friends, and also from the web, about many cool worlds that have been discovered using various seeds. Here’s an example, but there are literally hundreds (maybe thousands!) of these!

Interestingly, in MineCraft, the term “seed” makes for a convenient pun; Leo understood perfectly that the “seed” is what the world is grown from. But in reality, of course, it comes from the concept of a random number seed, which is how the pseudo-random number generator creates the random stream that generates the world, and everything in it. This, of course, is how it’s possible to publish the seed, as in the web page above, so that others can get back to the same exact (initial) world.

So I turned this into a series of discussion about random numbers, pseudo-random numbers, determinism and non-determinism, and one of Leo’s favorite topics: Quantum Computing and cryptography.

Here are the blackboards that I used in these discussion, with some (too brief) commentary. I strongly recommend this video for a really well done explanation of the whole conceptual space (except for the quantum computers).

Let’s start with determinism v. non-determinism:

Leo got right away that 4+5 is deterministic, and if you were to print the result in a loop (bottom right scribble) you’d get 9 every time, but 4+Rand(10) would randomly give you a number between 5 and 14 (in 1-origin). Note, also at the bottom left the important observation that “All non-quantum computers are DETERMINISTIC.”

So, the mystery is:

To translate my scribbles:

• All (non-quantum) computers are deterministic.
• Rand(#) [which is a computer function] seems to be non-deterministic. (We tried this on the iPad in the BASIC interpreter.)
• The mystery (apparent paradox!) is: How does Rand work? (We had a brief passing philosophical discussion about paradox v. conundrum.)

The answer, of course, is:

PSEUDO-RANDOMIZATION – Ensued a long interesting discussion of possible pseudo-randomization algorithms, the meaning of “Mod” (the modulo wheel at the bottom center), and so forth. (This board had lots of erasures; You’re only seeing the end product!)

The key concept, which closes the loop on MineCraft seeds, is that the computer needs to have something external in order to seed the pseudo-randomization. That’s what the box around MineCraft is. We talked a lot about where the computer could get a seed. One place is obviously that you give it a specific seed. In that case what’s external is you! But what about when you don’t give it a seed? (Leo’s initial solution, of course, was to use Rand() … 🙂

After explaining why this wasn’t going to work (can you say: “infinite regress”?) And that quantum fluctuations were going to be hard to capture [see footnote 1 below], I posed the following problem: Suppose that you were locked in the kitchen with all the lights off at night (we actually did this exercise), and needed a pseudo-random seed…. It only took a few seconds to get the right answer to this one:

---

Footnote 1 (20181107): It turns out that early random seeds were, indeed, generated from macroscopic quantum fluctuations, and more recently, believe it or not, from cameras aimed at a bank of lava lamps! Here’s a terrific video on these.

---

 

 

Pooping Diamonds (Pythoncraft!)

Tags

Minecraft, Programming

In a previous post I described how Leo and I have been using redstone to create digital hardware in Minecraft — or at least to try. This approach to interesting Minecraft is like pulling teeth. (More precisely, it’s like building a computer out of sand…almost literally!)

There are also several ways to program the Minecraft world itself. One way involves command blocks which allow you to execute arbitrary sets of Minecraft commands. We haven’t really tried this yet, but it seems kind of painful. But you can do some pretty complex stuff done this way, like this amazing Turing machine, and this complete SPARC CPU!

A much more direct way to program the Minecraft world is to reach into the server itself through its API. There’s a very good intro to programming in Python, by Craig Richardson, that’s all set in the Minecraft world. Getting the software to actually work requires hacking through the usual morass of stack hassles, wrong program versions, broken paths, missing files, and blah blah blah, but once I got through all that, it actually worked! (I’m always amazed when something in the Unix world actually works, considering the utter mess that is the Unix software stack!)

Once I got this to work as advertised, Leo and I were able to actually program in Python and have it take effect in the Minecraft world!

Considering that this is the first time Leo has programmed in an actual text-based programming language, we started with something simple.

First Leo wanted to build huge buildings, so we wrote a triple-nested loop:

def maketower(x1, x2, y1, y2, z1, z2, blocktype):
  for x in range(x1,x2):
    for y in range(y1,y2):
      for z in range(z1,z2):
        mc.setBlock(x,y,z,blocktype)

It only took about an hour to get him to understood the nested loops.

Next he wanted to drop blocks near us, and I had to idea to make this happen continuously as we move around. Here’s that program (blocktype 57 are diamonds):

def poopie(blocktype=57,sleepsecs=1):
  while True:
    pos=mc.player.getPos()
    print(pos)
    time.sleep(sleepsecs)
    mc.setBlock(pos.x,pos.y,pos.z,blocktype)

If you call this with sleepsecs=0.1 or so, then it leaves a trail as you move …thus its name! 🙂

Here are a couple of view of what the world looked like after we had made a bunch of giant blocks of diamond and emerald using maketower, and we had also flown around for a while pooping diamonds:

The totally great thing about this is that I can use Leo’s natural attraction (one might say “addiction”!) to Minecraft as a way into Computer Science for real. Unfortunately, Python is a ridiculous programming language — sort of the modern version of BASIC, or possibly worse!

At some point I’ll port the interface to a Lisp; then we’ll actually be able to do some real computer science!

 

Minecraft (Redstone) Computing

Tags

Electronics, Logic, Minecraft, Programming, Redstone

Of course, the most interesting thing about Minecraft for us STEM Hacker parents is redstone. Redstone — more precisely redstone dust (but I’ll just say “redstone”) — is basically wiring, and combined with lights and levers and torches, and a few other do-dads, pretty much enables you to build any sort of digital computing device that you can figure out…although you’re almost literally building it from sand! Given the low-level-ness of the whole thing, and some other annoying problems — mainly that redstone (dust) is highly resistive as compared with real wires, and everything is physical, so you’re running highly resistive and self-interacting wires all over the place! — you really have to think like a VLSI engineer rather than like a computer scientist. Yet there are folks who build quite amazing computing machines — like complete huge Turing machines!, and other insanely complex devices (this one’s actually a playable Pong in redstone, and this one’s an utterly insane graphing calculator! — in Minecraft. But I’m guessing that those folks (a) aren’t trying to collaborate on the project with a 7-year-old, and (b) have WAY too much time on their hands.

(There are ways to think in Minecraft like a computer scientist — specifically, you can actually program the world in Python! But I’ll get to that another post.)

Anyway, so Leo and I set out to do something pretty modest, create a binary counter using adders. We had worked through how a redstone adder works based on this very good video. (I highly recommend watching that video to get a very good sense of how redstone works if you don’t already know.) So we designed a counter. The design is to use two adders linked in a ripple carry configuration, and a clock whose tick causes the adders to latch their output and  to pass the latched output back to their inputs, permanently adding 01 on each cycle.

Here are the two adders linked in a ripple carry configuration and with a manually-operated output latch — no clock or fed-back inputs yet:

There’s a lot to see here, and watching the video linked above about adders will help a lot to understand what’s going on here, if you care. But one thing to notice is the latch repeater (on the rightmost side). Notice that the redstone just ahead of the repeater is going dim. This is one of the really annoying things about redstone: the signal is both slow, and fades out after 15 blocks, so you need to add repeaters every once in a while. It’s also undependable in terms of timing, causing all sorts of noise in the signal. As a result, you need to annoyingly put repeaters and latches all over the place, just to get your signals from A to B reliably. But, the above manually-operated ripple-carry adder and latch circuit actually does work.

Okay, so now to the counter. All we should have to do is to add a clock and feed the outputs back into the inputs (and set 01 as a permanent input), right? Well, all that isn’t as easy as it sounds.

First to the clock. We did the clock by creating a railroad of a certain length, so that the car runs continuously, and each time around sends a signal to our counter. Here’s the railroad:

In the below you’ll see this in various configurations (and with various animals sitting the car — turns out that animals like to get into the railcars!) This worked pretty well. The repeater next to the left track picks up the signal when the car passes it and sends it to the latch, which stays on for a few seconds and then cycles off. This is our signal. We can make the clock-tick arbitrarily long by just making the track loop longer. (We had discovered this trick while trying to make a roller coaster.)

Okay, so now we have to get the latched outputs back to the input side of the adders. This wasn’t so easy, and we tried a couple of different configurations before settling on one that was not overly tortuous. Here’s an early one:

This is a little hard to parse visually, but what’s happening is that the return signals are climbing up to a pair of high-wires (literally!) that bridge them back over the adders and to then land them down a bunch of steps to the correct input. (Note that this pic is backwards v. the above pics; here the inputs are on the right. The clock is at the back, slightly hidden.) This required so many staircases and repeaters that it was too hard to debug, so we ended up with this simpler design:

(This one’s in the “normal” orientation that the first pics above were: Inputs on the left, outputs on the right.)

Here the return signal only has to bridge the ripple carries, rather than having to bridge the whole adder, which required a lot less stair-cases, and many fewer repeaters.  Note the pig wandering around on the input, and the sheep that is now riding around in the rail car!

This configuration actually sort of worked, and it’s fun to watch it run. Here’s another view of it at a different phase just so that you can see that the system is actually clocking:

Unfortunately, timing problems with redstone repeaters made it unreliable. It really needs to have another set of latches on the input side. That would be easy to wire up now that we have a reliable clock, but, to be honest, (a) I’m collaborating with a 7-year-old, and (b) NO, I do NOT have too much time on my hands!

 

History Craft: The American Revolution

Tags

History, Minecraft

I’m trying to use Minecraft for good, and not evil.

(Yes, we are doing redstone computing; it’s just that writing a post on it is taking me a while!)

So, I had the brilliant idea to build a Minecraft model of historical events, and then Leo suggested that you could actually make the timeline of the event — for example the timeline of a war — into a Minecraft obstacle course!

Our first foray into this is the Minecraft American Revolution:

We started out studying the timeline of major events in the revolution:

And Leo started building. He’s only got a little way so far, but here’s a bird’s eye view of the events from the end of the French-Indian war through the British sailing into Boston harbor:

The area on the left is the startpoint, and the blue building is the French-Indian war, which is full of minecraft zombies that you have to fight your way through.

If you make it through there, you are presented with these signs:

representing the taxes that were the linchpin events that ignited the war. You have to actually knock down these signs in order to get to the door behind, which opens onto Boston harbor full of British…er…zombies:

And that’s as far as we’ve got, but the concept seems to work well, esp. for wars. Leo’s trying to build one or two events in the timeline each day.

By the way, using Minecraft for historical events is not at all new. Here, for example, is an out-of-control re-enactment of a lot of the detail about the American Revolution, but as far as I know, representing the timeline as an obstacle course is a novel insight due to Leo.

(The coolest part is going to be when we get to the Declaration of Independence. We’re going to write the whole thing out — or the relevant bits anyway — in Minecraft signs, and then you’ll have to add a sign with your name to sign it yourself! 🙂 )

---

---

 

Minecraft Farlands and Computer Math

Tags

Computers, Math, Minecraft

Given Leo’s love of large numbers, it’ not surprising that he is fascinated by what’s called The Farlands, at the edges of the Minecraft world. Basically, The Farlands are some combination of (a) the limits of the internal Minecraft representation, (b) places where, presumably for the sake of speed, the engineers just populated the world with random numbers instead of bothering to create topography where most players will never see it, and (c) bugs. The bugs are likewise in places where most players will never get to, so who cares, right? Answer: Pretty much every young nerd like Leo cares!

So, per my usual theory of making everything a math or science lesson, we use the Farlands as a way into a lesson about computer math. Here’s our whiteboard:

Without trying to annotate everything on the board, we were calculating how many bits it would take to represent the XZ coordinate limits for Minecraft. (Minecraft uses Y for the vertical access, which seems slightly weird if you’re trying to navigate the map because you’re looking down on it, but it’s this is way that it’s usually done in physics.)

We imagined maps of various sizes, for example: 128×128 (on the left about the middle of the board), and then tried to figure out how many bits we’d need to represent these, which led to a short lesson in base 2 logarithms. The interesting thing that Leo noticed, and which was what initiated this lesson, was this seemingly weird factoid from the Farlands web page:

Leo thought that that number was really funny and weird, but I thought that I knew why that number was like it was — specifically, that’s 2^64th. So we talked about binary representation of number (which Leo already knew from long ago) and logarithms as a way to figure out what power of 2 you needed to make a given value, and did some examples, and then used Wolfram Alpha to test my hypothesis that 9,223,372,036,etc is 2^64th:

 

Um….oops! I forgot that that’s actually the positive limit, but the world is actually TWICE that, positive AND negative!

This led to more lesson on binary representation of positive and negative numbers, and how you could do it with a single sign bit, and the “correct” representation where (in three bits) -1 = 111, -2=110, and so on. This is the stuff on the upper left of the whiteboard. Leo himself noticed that it would wrap around at 4 = -4, and asked why Minecraft didn’t wrap around at 2^63+1…Good question. That would be cool!

---

---

 

MineCraft Math: Ender’s Game

Tags

Algebra, Computers, Games, Minecraft, Programming

I’ll eventually write a long series of posts on Minecraft, but for the moment, I’m going to start at the end, because, well, we got to the end game a little earlier than one normally would.

The reasons that we got to the End Game are that, first, ever since we’ve been doing Minecraft, which isn’t actually very long (although it’s a long story, for another time), Leo has been obsessively studying, and obsessively telling me all about, the End Game. In the Minecraft end game you: Discover a Stronghold, Find an End Portal, Get into the Ender World (or whatever it’s called), Kill the Ender Dragon, and Solve a slightly complex mechanical puzzle, all while trying not to die in various stupid ways that you can die in Minecraft. Once you’ve done all this you’ve basically won Minecraft, and are reworded with an actually quite moving and lovely (albeit long) poem. I was hoping that by going through this with Leo I would be rewarded by his no longer bothering me about all this…. (We’ll see!)

So, anyway, in keeping with my theory of math education, where everything fun is mathematical, and everything mathematical is fun, we turned the search for the Stronghold into a math problem, which is described by the scribbling on this whiteboard:

To make a long story short, the Strongholds are randomly located slightly underground along three axes 120 degrees apart at between 640 and 1550 (or so) blocks from the world center. In order to find them efficiently, you can thrown an “Eye of the Ender” up in the air, and it travels for a bit in the direction of one of the Strongholds.

Finding the stronghold along a given line is analogous to the children’s game where someone thinks of a number in a range, say 1-100, and then the magician asks if it’s say, 50, and if not, whether it’s higher or lower, at which point you go to 1/2 way between (25, for lower, for example).

In mathematics, this is approximately Newton’s Method — or at least I always think of Newton’s Method when I think of this game. In algorithms design it’s called binary search, and it’s easy to prove that it’s big-O log-base-2 in the size of the ordered list, so, in the case of 100, it’s O(Log2(100)) or about 6-7 tries, max.

Leo and I calculated all this, and figured out where the middle of the line connecting the center (where we started out) between 640 and 1550 was. (That’s what all the trig is in the picture above — the line wasn’t exactly along the X or Y axis, so there’s some complexity.)

And then we started to search for the Stronghold, and lo-and-behold, it worked! In about 5 tosses of the Eye of The Ender we hit pay-dirt (literally — well, digitally, anyway), and upon drilling into the ground where we ended up, found a stronghold, played the end game, and won!

Now that he’s won, let’s see if Leo will come down from his Minecraft addiction! I have low hopes; He’s already made a list of the numerous other Minecraft challenges he wants to solve.

---

---