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.

---

---