Thursday, February 20, 2014

Opposed Checks in D&D are the Same as Coin Flips

This is a lesson in statistics and probability, as applied to the popular Dungeons and Dragons role playing game.  I'm having trouble lately with the LaTeX embedder: if you see a lot of dollar signs and slashes, then check your plugins and permissions on your browser and allow MathJax to work, so you can see the equations better.

At least since version 3.0, the Dungeons and Dragons rule book has featured a rule of opposed checks.  These are supposed to represent, using dice, the opposition of two separate skills: so, your ability to Hide versus the orc's ability to Spot; your ability to tie a rope versus the orc's ability to escape from bonds.  You roll your skill, the orc rolls his skill, you apply modifiers, and the higher outcome wins.

Even before this, rolling dice was a common way to set the difficulty of something in old versions and in other non-d20 games.  How hard is the door to force?  You didn't think of it, now you're on the spot, so you roll a die to figure out how hard it is.  Then you tell the PCs to beat that number on their own roll.  Makes sense.

Doing checks this way is, from a probabilistic point of view, about as good as flipping a coin. The probability of the PC winning is slightly more than 50-50.  In terms of DCs, an opposed check (before modifiers) is equivalent to a DC of 10.5.

I'll prove it.

When you roll a die, a number comes up.  A random number, hopefully.  If the dice has $n$ sides, then this number is between $1$ and $n$.  It is customary to denote a random number with a capital letter: in this case, I'm going to call $X$ the result of rolling the die; $X=1, 2, 3,\ldots, n$, depending on what we roll.

If we consider some number between $1$ and $n$, say 6, then the probability that $X=6$ is, as we all know, $1/n.$  It is common to write this as $\Pr(X=6) = \frac{1}{n}.$  And, of course, it isn't just for $X=6$ that this is the case, but for any number $x$ between $1$ and $n$.  More generally, for any such $x$, we write $\Pr(X=x) = \frac{1}{n}.$

In our case, we are going to roll the same die twice.  This gives us two random numbers (the results of the two dice), which we will call $X_1$ and $X_2.$  For concreteness, suppose this is an opposed strength check between the PC and an Orc.  We'll say that $X_1$ is the die we (the GM) roll for the Orc, and $X_2$ is the die that the PC rolls.  We want to know $\Pr(X_2 \geq X_1)$, that is, the probability that the second result is higher than the first or in game terms, the probability that the PC wins his contest against the Orc.

This could go a number of ways.  The GM might roll a 1, in which case the PC is guaranteed to win, or the GM might roll a $n$, in which case the PC has to also roll $n$ or lose, with other possibilities in between.  But we don't want to consider the probability of the PC winning given some particular roll from the GM, because that's trivial.  So what we want to do instead is consider all of these possibilities.

We look at
$$\Pr(X_2\geq X_1) = \sum_{x=1}^n \Pr(X_2 \geq x) \cdot \Pr(X_1=x),$$
which means that we consider the probability of the GM rolling some number $X_1=x$, then multiply by the probability of the PC winning given this roll, then consider this for all the possible $x$ the GM might roll and add these together.  That gives us the probability of the PC winning his roll, regardless of what the GM rolls.

Breaking this down, we find
$$\Pr(X_2\geq X_1) = \sum_{x=1}^n \sum_{y=x}^n \frac{1}{n} \frac{1}{n} = \frac{1}{n^2}\sum_{x=1}^n\sum_{y=x}^n 1 = \frac{1}{n^2}\sum_{x=1}^n (n-x+1).$$
Stopping for a second, for people less familiar with this stuff, the $\sum_{y=x}^n$ term means that we add up every value of $X_2$, starting at $x$, and ending at $n$.  Concretely, if we're rolling a d20, and the Orc's roll is $X_1=15$, then we add up contributions from $y=15,16,17,18,19,20,$; that's $6 = 20-15+1$ terms we consider.  More generally, it is $n-x+1$ terms, which is why we wrote $(n-x+1)$ there.  Moving on,
$$\Pr(X_2\geq X_1) = \frac{1}{n^2} \left(\sum_{x=1}^n n - \sum_{x=1}^n x + \sum_{x=1}^n 1\right) = \frac{1}{n^2}\left(n^2 - \sum_{x=1}^n x + n\right).$$
The term $\sum_{x=1}^n x$ means the sum of the first $n$ numbers.  So,
$$\sum_{x=1}^n = 1 + 2 + 3 + 4 + 5 + \cdots + n.$$
Those who've had Calculus will be familiar with this, but other people maybe no so much.  There's a beautiful formula due to Gauss, arguably the first person to discover it, whose proof is even more beautiful.  Consider the following image:

This shows a bunch of stacks of squares, increasing from 1 to 2 to 3, on up to $n$.  The area of these squares is $\sum_{x=1}^n x.$  Now consider a second one of exactly the same size: the two interlock, forming a rectangle:

The width of the rectangle is $n$ and the height is $n+1$, so its areas is $n(n+1)$.  But the area of the rectangle is equal to twice the area of the stacked squares!  Therefore,
$$\sum_{x=1}^n x = \frac{n(n+1)}{2}.$$

So then, carrying on with our equation, we now have
$$\Pr(X_2 \geq X_1) = \frac{1}{n^2}\left(n^2 - \frac{n(n+1)}{2} + n\right) = 1 - \frac{n+1}{2n} + \frac{1}{n} = \frac{2n - n - 1 + 2}{2n} = \frac{n+1}{2n},$$
which, as I said, is slightly better than 50% probability.

For a 6-sided die, it is $\frac{7}{12}.$  For a 20-sided die, it is $\frac{21}{40}$, which is a 52.5% chance of success, which corresponds to a DC of 10.5.  A flat DC 10 is a 55% chance of success.  So rolling an opposed roll for the Orc is the same as considering the Orc's passive check.

That is without modifiers.  To include modifiers, start at flat DC 10, and modify as
$$DC = 10 + (\text{Orc's mod}) - (\text{PC's mod}).$$
For an Orc with +3 and a PC with -1, the check would be at
$$DC = 10 + 3 - (-1) = 14.$$
This will be (mostly) statistically equivalent to a modified opposed check ($\pm$ a 2.5% sliver of probability)

I did this all for dice, which are what is relevant to RPG players.  For dice, the result is not quite $1/2$ because the rolls can only equal certain specific results (like 1, or 7) and a tie goes to the player, but in a general case, it is actually true that the probability of a second random number being larger than the first random number is exactly $1/2$: that is, $\Pr(X_2>X_1) = \frac{1}{2}.$  I'll prove it.

So, consider  $X_1, X_2$, which are still random numbers, but not necessarily from a die.  For instance, we might push blocks on ice, and $X_2$ and $X_1$ gives the distance the blocks travel before coming to rest.  Or throw darts at a wall and $X_2,X_1$ are the distances from a bullseye.  Or something.  It's also not necessarily that case that every possible value is equally likely.  For a fair die, every number has probability $1/n$ or coming up; for throwing darts at a bullseye, if we're any good, then we will be more likely to be near the bullseye.  Let $\Pr(X=x) = p(x)$, where $p(x)$ is just some function: give it a value $x$ and it gives you a probability $p$.  Here $p(x)$ is called the "probability distribution function".  For simplicity, we also consider $\Pr(X\leq x) = F(x)$, called the "cumulative density function".  This is the probability of $X$ being less than some value $x$; as we'll see, a separate symbol for this is really useful.

As before, we have
$$\Pr(X_2\geq X_1) = \int \Pr (X_2\geq x)\cdot\Pr(X_1=x)dx = \int (1-F(x))p(x) dx = \int p(x)dx - \int F(x)p(x)dx.$$
You may be wondering what the weird S is, the $\int$ thing.  That's an integral sign, and it basically just means "add up all the possible values of $x$."  It's different from the $\sum$ symbol in that $\sum$ considers only discrete values while $\int$ considers continuous spectra of values.  We have used here the fact that $1 = Pr(X\leq x) + Pr(X\geq x) = F(x) + \Pr(X\geq x)$ to express this in terms of $F$.

If we add up all the probabilities of things happening, we should get 100%; that is, $\int p(x)dx = 1.$  This makes sense; the probability that we roll a 1 or a 2 or a 3, etc, is 1.  So
$$\Pr(X_2\geq X_1) = 1 - \int F(x)p(x)dx.$$
To fully evaluate this, we can write it another way.  Think what happens if, instead of rolling for the orc first then making the PC roll higher than that, we have the PC roll, then roll for the orc and make sure the orc rolls lower.  It's the same thing in the end, but can be written as:
$$\Pr(X_2\geq X_1) = \int \Pr(X_2 = x) \Pr(X_1 \leq x) = \int p(x) F(x) dx.$$
Comparing these two,
$$\int p(x) F(x)dx = \Pr(X_2\geq X_1) = 1 - \int p(x) F(x)x,$$
which must mean $\Pr(X_2 \geq X_1) = \int p(x)F(x)dx = 0.5.$

So, the long and short of it is, if we have two random numbers that we produce in the same way, one after the other, and we want to know the probability that the second is larger than the first, then this is 50%.  In terms of D&D, this means that if you generate the DC for a skill check by rolling a die, then have the PC roll to beat that die, then you may as well flip a coin to accomplish the same thing.  This also means you can fix the DC of the opposed rolls at 10, and just add the Orc's bonuses and subtract the PC's bonus to increase the DC; it achieves the exact same thing.

If this result is unsatisfying to you, consider using a different system of opposed rolls that changes the dice used by each party, for slightly swingier results.

Note: this was originally written on 2/20/2014, but was updated on 5/7/2018 to make the wording more clear.

Wednesday, January 29, 2014

Speculating on Blindsprings

I recently stumbled on to a web comic called Blindsprings, after seeing a banner ad for it.  Let me take this time to recommend it to you.

Blindsprings is a comic that just went online back in October.  If you go to the website, you can see that not much has happened yet.  As such, it's hard to gauge just what the story is or where it's going.  So far though, surmising from the information available, I think this has the potential to be something really, truly great.  What is also exciting is being able to see the story develop from the beginning.

Plus, the artwork is beautiful.

 this was the ad for it
Here's a non-spoilery description blurb of it:

The main heroine is a young girl named Tamaura.  She lives alone in the forest, where she attends to animals and plants trees and performs many other tasks for a shady group known as "the spirits".  It's a simple, idyllic kind of life.  One day she meets a young man named Harris, who has heard a fable of her and came to investigate the truth of it.  The two become friends, and after spending time with her, Harris decides to go off to a place called Kirkhall to study what is called Academic Magic.

The setting is not the standard "medieval" fantasy kind of setting, but something more like early Enlightenment era.  Really, not much of it has been revealed yet, so that's mostly a surmisation.  We are not even finished with the prologue.

After you've read it, come back here and let's talk about it.  There's not much of it (so far), so should be easy.

There are SPOILERS below.

Sunday, January 26, 2014

What is Spin? A Concrete Explanation.

To say that a particle has "spin 1/2" is to say that it must be rotated through 720 degrees before it can return to its original configuration.  This is not something normally witnessed in the world of classical mechanics, and so this aspect of quantum mechanics is often piled up with unhelpful metaphors and mysticism.

I wrote a post previously trying to point out that quantum mechanical spin is just a degree of freedom.  Spin tells you the components of a particle in a combination of two wave states with the same energy.  You can make pseudospins and isospins with any two such states, no matter what they are.  When you rotate the system, the components get mixed up -- just like angular momentum states.  You have to rotate the system by 720 degrees before the components get mixed up enough to be un-mixed up (i.e. back to there they were).  That's all it is.

What gives spin states this weird property is that the space of rotation is three dimensional, but the spin "vector" is only two-dimensional.  Rotations of typical vectors with three components (even if one of those components is zero) work just the way you'd think they should.  But, it's not completely surprising that 2D objects in 3D space don't rotate like 3D objects in 3D space.

To illustrate where spin comes from, and how it contrasts to orbital angular momentum, consider the case of rotation in 2 dimensions.  The best way to talk about rotations is to start at the unit circle.

Thursday, January 23, 2014

Everything Cool is Impossible

Physics has known for a long time how to build a time machine.  The possibility in a real spacetime geometry was first noted by Van Stockum, but this possibility was only really first analyzed by Frank Tipler in the 70's.  All you need is a massive rotating cylinder.  And also it has to be infinitely long.

 This illustrates how frame dragging can lead to time travel
Since then, at least a dozen other possibilities have been proposed for time travel to the past, and physicists have proven that these spacetime geometries result in what are called "Closed Timelike Curves" (CTCs), which are trajectories a massive object could follow to go back in to its own past.  We know that they would work within the theory of General Relativity.  But, they're all impossible.  They either require the universe to be rotating (it isn't), they require infinitely large systems (we can't make them), they require negative-mass matter (no such matter exists), or they require you perform your time travel within the interior event horizon of a Kerr black hole (which is fine, but then you can't leave).

This situation is worse than merely having a concept of physics that excludes time travel, or that merely says that time travel is impossible.  For if time travel was excluded by theory, then we could always say the theory was incomplete.  What we have instead is a system that fully allows time travel possibilities without prejudice, as long as we're able to break some other law of physics to get there.  It's not just the stubborn "no" of a parental figure; it's like having your parents describe step-by-step exactly what you can do to eat chocolate cake for breakfast, and one of those steps is "eat infinite broccoli".

Physics also knows how to effect FTL travel.  The speed of light puts a prohibitive barrier on
our ability to explore the stars, but a number of work-arounds have been proposed.  Technically, relativity only prohibits local FTL movement, but says nothing of global FTL travel.  So if you can distort space and time in just the right way, you can move however fast you want.  One of the more frequently explored proposals is wormhole travel.    Wormholes produce a kind of "short cut" in spacetime, and it is actually a Federal Law that when you want to discuss how wormholes work you must draw two dots on a sheet of paper, "A" and "B", draw the straight line connecting them, then fold your paper so "A" and "B" touch and jab a pencil through it.  While going along the line you draw may take billions of years, going through the wormhole may take minutes.
 My lawyers also recommend I show you this diagram

Sadly, you can't make a wormhole.  And even if you made a wormhole, the throat collapses when you try to travel inside of it, so you can't even use the wormhole for travel anyway.

Another proposal is the Alcubierre warpdrive.  This contracts spacetime in the front and expands it in the back, producing what some call a "wave" of spacetime contraction that "tips over" the light cones inside the warp bubble.  Locally, you're moving slower than light, but globally you may be moving, in theory anyway, as fast as you want.

But you can't make the Alcubierre warp drive either.  If you took the mass of the universe and made it negative, the Alcubierre warp drive requires ten times that number in negative-mass matter to move a standard-sized spaceship.   To clarify, we haven't even found one single particle of negative-mass matter.

Science knows how to make a Bag of Holding, and can even make a Bag of Holding that slows down time (see chapter 3 here).  You can store a lifetime supply of hot pies and ice cream in the same box, and whenever you take them out the pie is still oven-fresh and the ice cream still ice cold, and so even twenty years later you can serve yourself delicious pie a la mode.  But, like so many awesome things, it requires either negative mass or impossible mater distributions and can't be made.

I just made a post about how the Bag of Holding (aka, Van den Broeck Bubble) can be exploited to, potentially, travel to parallel worlds (if any even exist).  This one is a lot more speculative, requiring ideas way beyond established science, but is at least partially based in what we already know about general relativity and curved-space geometry.  It isn't really scientific, but if we wanted to know if there were other universes, this has potential to actually find them.  But it also requires not only negative mass, but infinitely much of it.  So we won't ever be able to try.

 Pictured: A guy wearing a green screen. Not Pictured: An invisibility cloak
Science has pretty recently discovered (less than ten years ago) how to make a literal cloak of invisibility.  It involves bending light in just the right way.  We know what that just-the-right-way way is, and we even know how to make materials that bend light in just that way.  Sadly, it only works for a single frequency (i.e. color) of light at a time.  There's no way to be completely invisible, because there don't exist materials with  the right optical properties naturally.  So you can be green-invisible, but you'll still be perfectly visible in red and blue.  I guess you'll just look slightly more purple?

I recently calculated (as part of my research) how to make a slightly different kind of cloak, namely a shadow cloak.  Also something you'd read about in fantasy books, the shadow cloak works on the same spacetime distortion principle as for a black hole, but now modified to work with optical materials (so not requiring it be made of actual black holes).  A perfect realization  would allow light to enter, but trap it there.  If you were wearing it, you would appear to be not just covered in a black garment, but actually swathed in shadows.  (Look at a black object, then look at an unlit hole; there's a big visual difference)  You'd also probably heat up a lot (since all the energy is trapped), which would make this kind of material perfect for solar panels, increasing their efficiency probably to near 100%.  But you can't make the shadow cloak, because it requires material parameters that are both infinite and negatively infinite.  Like with the invisibility cloak, you can only realize this (if at all) for a single color of light at a time.  Which vastly diminishes its coolness.

You can probably see where my knowledge tends to specialize, but physics knows a lot more cool things in the quantum domain, such as teleportation devices and solutions to the P=NP problem.  All of which, we know how it would work, and only minor technicalities render it impossible.  Things like wavefunction collapse, quantum decoherence, and the no-cloning theorem.

Any time there's something cool in physics, there's something else that renders it impossible.

Again, this isn't the situation of wanting to do something incredible and merely lacking a theoretical model to describe it.  Our formulations of physics account for it exactly.

It's just that all the cool stuff is impossible.

More and more, it just seems like the Universe comes equipped with fail-safes against our ever doing the cool things of science fiction.

Wednesday, January 22, 2014

What Do Wizards Even Do?

The Malfoys are very rich.  The Weasleys are very poor.  However, they are not nearly as poor as the inbred and horrible Gaunts.

Why?

This is again part of the same basic problem with the series: Rowling never bothered to figure out her universe from the perspective of the characters who live in it.

How do wizards generate wealth?

As revealed in the books, there are really only so many things a wizard or witch can do professionally.  You can make wands.  You can make magical pranks.  You can manufacture magical candy.  You can sell books or robes.  You can teach at Hogwarts (and there's only a dozen positions there).  You can work for a news publication.  Or you can work for the Ministry of Magic.  That is the entire wizarding economy.

For instance, when the students begin taking their OWLS and deciding their classes for future employment, almost every single job opportunity considered is at the Ministry of Magic.  Harry becomes an auror, but what else was he going to become?  An accountant?

Tuesday, January 14, 2014

Sailing Away to Narnia

I stumbled upon an article a few months ago that I've been meaning to blog for a while and never got around to.

The original article is by Chris van den Broeck, and deals with the subject of warp drives.

Yes, warp drives.  The Alcubierre warp drive engine is a device that stretches the spacetime around a spaceship, forming what is known in scientific literature as the "warp bubble" (really, that's what we call it).  Within the warp bubble, the ship is moving at "normal speeds", but outside of the bubble, the ship is moving faster than the speed of light.  The geometry for this is known and well understood, and the means of producing it are also fully understood.

You're probably wondering, if we know how to make a warp drive, why we haven't actually... you know... made a warp drive.  And that's a wonderful question.  We haven't made a warp drive because it requires a lot of stuff that probably doesn't exist, namely negative energy mass.  It requires a whole lot of it.  Like, ten times the positive mass of the entire universe in negative mass.

Van den Broeck proposed an idea to get around this, one elegant in both its simplicity and apparent absurdity.

Here's what you do: Take a bag.  Distort space, so that the inside of the bag is bigger than the outside of the bag.  The inside is big enough to hold a spaceship, and the outside if around the Planck length.  Now stick your spaceship inside of the bag, and then put a warp bubble around the bag.   It requires a lot less negative energy.  Voila!  Crisis averted.
 Schematic from original article. Region II is the bag. Region I is where the ship is. Region IV is the warp bubble
Now, warp drives are cool of themselves, but what I really want to talk about is the device that distorts space so the inside of the bag is bigger than the outside of the bag.  This is sometimes called a "van den Brocek bubble", or, somewhat more appropriately, a Bag of Holding.

We've gone from warp drives to the bag of holding, and we're not even done yet.  We're going all the way to Narnia.