Showing posts with label random. Show all posts
Showing posts with label random. Show all posts

## 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.

## Sunday, November 24, 2013

My Alma Mater didn't have a football team, and I love this fact intensely.  While I was there, the most important sport was intramural Ultimate Frisbee.  It was serious business.  I don't really like Ultimate Frisbee, but I was okay with this.  It's a quirky kind of thing, and a fact that I'm proud of repeating.

Sadly, my Alma Mater doesn't give out PhDs, especially not in physics, and so I had to go elsewhere to finish my education.  Specifically, I had to go to a Research I university, because those are the sorts of schools that give out physics PhDs.

What is a Research I university, you might ask?  Well, in the simplest possible terms, it is a school that receives and spends more money on college athletic programs than it does on academics.  Or at least that's the definition I've arrived at from observation. Let's not forget that fresh scent of Porta-Jons
The school I attend now has a proud tradition of inviting alumni back every Saturday in the Fall to get drunk on the school lawn and listen to terrible music at obnoxious volume levels while throwing hackey sacks in to holes cut out of plywood boards while some young adults in college at a 5th-grade reading level throw a ball around and concuss each other in a nearby stadium.  They then leave their mountains of ill-smelling trash behind to soak in the streets until a garbage crew comes by to pick it up.  My university endures this because those same people are so attached to this tradition that they are willing to pay large amounts of money for the privilege of doing it, and really, it's money.

The physics building is right next to the stadium at my school.  This means that once a week I am incapable of entering my office, because it is surrounded by the hordes of barbecuing barbarians offering their drunken libations and burnt sacrifices to their pagan football deities, and if I try to go in then they will sneak in behind me and start a conga-line to the bathroom -- a situation that happened once before and resulted in me having to call campus security to get them evacuated from the building.

Maybe you can tell by my tone, but I don't really like football.  The actual game itself is kind of dumb, but you know what, whatever.  Have fun playing it, and have fun watching it.  A lot of people think fantasy novels are dumb, or math is dumb (or rather, too smart for them to be able to perform properly), or Christianity is dumb, or whatever.  People can like whatever stupid things they want to.  I certainly do.

What annoys me about football, though, is the ridiculous status granted to it by society.  If I'm at a restaurant trying to enjoy some food and conversation, woe to me if there's some game on somewhere, as now I must endure everyone in the bar feeling entirely justified in standing out of their seats and screaming at the top of their lungs every five minutes.  Normally, that's considered rude and discourteous.  But if you do it because of football?  Then it's perfectly fine, the team's doing good -- and who's that antisocial jerkwad over there in the corner scowling and not cheering them on?  (Fun fact: football players can hear the cheers of their fans all over the world when directed at their images on TV screens.  Kind of like how God hears prayer.) Um, excuse me?  My friend and are trying to enjoy a beer and discuss our lives.  Thanks.
Watching people feel entitled to act like overbearing jackasses because of something that is pretty boring and mediocre (He threw the ball.  He caught the ball.  He is running after having caught the ball.  His running was impeded before its completion. Yay.) is really annoying.  Having my daily routine impeded because of the moronic devotion of football fans (like when they all decide to leave the stadium at the exact same time and now I can't leave my house or go anywhere or even get something to eat for the next two hours) is too much.

So all of that ranting is sort of just background.  Point is, my school has a really big football team, and about all my school has is a big football team, and about all my school cares about is its big football team, and I hate it all with a passion.  Football itself isn't interesting or compelling enough to hate -- the extent to which people care about it, however, definitely is.

Recently, I was helping my dad with a fundraiser he was putting on, the proceeds of which go to helping endangered wildlife.  I was moving tables and selling raffle tickets.  Some people would ask me what I do.  I'd tell them, I'm working on my PhD in physics.

"Oh, that's nice," they'd say, "Where do you go?"

So I'd tell them the name of my school.

Do you know what they'd say to me next?

They'd start talking about how "my" team is getting its butt whooped by some other team.  Or did really well against some other team.  Or is going to the championships or whatever it is football has.

Which... is really depressing.

Those people are fine.  They donated a lot of money to help save endangered species and their habitats.  And they don't know any better than to ask me about football.  They were trying to be friendly and start small talk with one of the event volunteers.   What better thing to talk about than the All-American game that everyone loves all the time forever?  And I go to one of the biggest football name schools in the world, so of course I'm going to love hearing all about it.

But it's sad that that's all people know about my school.  And it's sad that for the rest of my life, this will be the flow of conversation.  I tell them where I got my PhD.  They ask if I saw the game last week.  I silently curse cruel fate under my breath, and ask what game they're talking about, because for all I care they mean the water polo tournament.

It's sad that my school is firstly a football name brand and marketing device, and secondly an academic institution.  And it's sad that I'll be reminded of this fact for as long as I live.

My question to the general, vague, swirling ether of the internet (to whomsoever might read this): is there some school I could go to instead where I won't be constantly reminded of the sophomoric displays of group-think and tribalism that prevented me from entering my office on Saturdays?

Am I just at the wrong institution, or is this going to happen no matter where I go?

Is it just a fact of life, established by the Providence of God to humble physicists at dinner parties by constantly reminding us that no one cares about our big-brain fancy learnin', it's all about how the team does?

Or is there a PhD-granting school which either does not have a football team, or has a team that no one cares about, at all (not even undergrads)?

Please say there is, or that's just too depressing to be real.

## Saturday, May 25, 2013

### Late Night Musings

The other night I was up late, working on a draft for a paper I hope to have submitted before the end of the summer.  I think it was around 4 or so.  After a while, I decided to take a break, and normally I suppose that a break at 4 AM would mean something like sleeping.  For some reason, I was so excited by the research paper that I just didn't want to sleep, and had been just gunning through it pretty much for the past three days straight.  So I didn't sleep, and started updating my paper journal.

I made a poor stroke with the pen, and wanted to amend it.  Reaching in to my desk drawer, I took out the bottle of whiteout that I only now realize I have owned since I was in 3rd grade.  I have only ever in my entire life owned one bottle of whiteout, and it is this one.  I think that's weird.  Anyway, I took out the bottle of whiteout and was shocked to find that all the correction paste had dried up sometime in the past twenty years and would no longer come out of the bottle.

My apartment is a simple affair, single bedroom, bathroom, a kitchen.  The building is also pretty simple; it's a single property with a single building on a pretty quiet street.  The building is brick, two stories, and has a total of eight apartments.  I live on the top floor, and a (married?) couple live below me.  Unfortunately, pretty much every time I put a foot down on my floor, they know about it, so sometimes they've had to come up at, say, four in the morning, and ask me to please stop moving all of my furniture around, because they're trying to sleep like normal people.

Anyway, as I was saying, the whiteout wouldn't come up, and I needed to fix the pen stroke I'd made, and I don't have any other whiteout because I've only ever owned one bottle in my entire life, so I decide, based on my practically non-existent knowledge of chemistry, that I'll just mix hot water in with the dried-up correction fluid and thereby get liquid correction fluid.

So I'm at my sink, and I have the tap water running.  Just a trickle, because I don't want to waste water.  It's running, and heating up, and I put some in... and the whiteout doesn't mix with it.  So I start shaking the bottle, and I just know that with each down-shake I'm reverberating the entire celing of my downstairs neighbors.  But I keep doing this, water's running, I put water in, shake it up some, pour the water out, put more in, shake it up.  Some little flakes are starting to come, and I think, this is good, soon the flakes will be smaller, and then the small flakes will mix with the water like a colloidal dispersion, and then I can use it to correct my mistake.  So I put some water in, shake it up, pour it out, put some more in, shale it up, pour it out.

I don't even know how long I was doing this.  Seriously, maybe like thirty minutes.  I may seriously have spent thirty minutes at 4 in the morning on a weekday trying to revitalize my 3rd grade bottle of correction fluid.

At some point, I hear movement downstairs, and I hear a door open.  The outside door.  Crap, I thought, I woke them up again.  I hate waking them up.  It's rude, really, and I don't like being rude.  So I tried to quiet it down and I got ready for when he'd knock and I'd go to the door to find him standing outside looking like a zombie raised from death not moments before asking me to please, please stop moving around, it's so early and people are trying to sleep, and it's pretty reasonable to ask you to keep it down, so please stop scurrying around doing whatever it is, and what are you even doing anyway?

And it was then that I realized, if they were to ask me what the heck I was doing up at 4 in the morning making all this noise, it would probably be impossible to convince them that I wasn't on drugs.