Sunday, November 26, 2017

Thursday, November 23, 2017

Difficult Rolls

Here are the dice I keep behind the screen:

Making Do With a d20 and a d6

In a pinch I could get by with the two d20s and three d6s with pips. The d20s can be used for a percentile roll with the convention that pink is tens and white is ones.

The d20 can simulate a d4 by taking the result modulo 4, treating 0 as 4.

The d20 can simulate a d8 or a d12 with the help of a d6. Take the result of the d20 modulo 4, treating 0 as 4. Roll a d6 and add 4 if the result is 4, 5, or 6. Or add 4 if the result is 3, 4 and add 8 if the result is 5, 6.

This DM is a minimalist and only uses a single d6 and a d20 when running a game. Perhaps he uses the techniques above. Maybe he runs an old version of the game where everyone has d6 hit dice and does d6 damage. The DM could ask a player to make a roll.

Discrete Uniform Distributions

How many discrete uniform distribution are needed?

If we are using the above dice, it is sensible to stick to dice rolls in the ranges 1–4, 1–6, 1–8, 1–10, 1–12, 1–20, and 1–100. But if we could generate an integer randomly from any range, then any list could be used as a random generation table.

The Holmes rulebook lists 14 1st level magic-user spells, 18 2nd level magic-user spells, and 18 3rd level magic-user spells. What if we need to determine a spell randomly, say because a scroll is found or an NPC spell caster is encountered? Small wonder the spell lists were truncated to 12 per level in the Moldvay rulebook.

Integer Division and Round Up or Modular Arithmetic

Two techniques for getting a smaller roll from a larger roll

To get a d2 or a d3 we can use the d6 and apply integer division and rounding up. When rolling a d6 with pips I like to use ⌈d6/3⌉ or ⌈d6/2⌉.

For a d5, I use d20 % 5, replacing 0 with 5.

As discussed previously one could use modular arithmetic to get the d2 and d3 rolls. Why the inconsistency? I prefer modular arithmetic nowadays, but the group has a tradition going back to childhood for how a d2 or d3 is rolled.

d6 Helper

Getting a larger roll from two smaller rolls

Back when icosahedral dice were numbered 0 to 9 twice, grognards would roll them with a helper d6 to determine whether the result was in the range 1–10 or 11–20. Specifically the formula d10 × (d2 – 1) × 10 was used. The technique generalizes:

    d15: d5 + (d3 – 1) × 5
    d16: d8 + (d2 – 1) × 8
    d18: d6 × (d3 – 1) × 6
    d24: d12 × (d2 – 1) × 12
    d30: d10 × (d3 – 1) × 10
    d36: d12 × (d3 – 1) × 12
    d40: d20 × (d2 – 1) × 20
    d60: d20 × (d3 – 1) × 20

I use a d6 with pips as the helper. When rolling a d18 I combine it with the d6 with digits.

If High Then Low

Interpolating a roll in between a smaller and a larger roll

A truly uniform result for most of the other ranges is not possible, at least not with a single roll. We use the "if high, then low" technique to get a near uniform approximation. To get a d7, one rolls a d8 and a d6. If the d8 is too high the result on the d6 is used. In general we find the next higher and next lower ranges that we can roll exactly and use those.

To get a d17 a d16 and a d20 are rolled. I don't use a d16 and a d18 because both need a helper d6; there would be ambiguity if the dice are rolled at the same time.

Falling Distributions

Motiving the falling distribution

Gaming has gotten by with uniform (e.g. d20) and normal (e.g. 3d6) distributions. Both of these are symmetric distributions with expected values at the center of the distribution.

When world-building, an asymmetric distribution in which small values are more likely than large values is desirable. We should use a distribution whose probabilities fall in this way to determine the level of an NPC if we want low-level characters to be common and high-level characters to be rare. It could also be used to determine the number of humans in a settlement or the number of orcs in a war party, since populations tend to follow a Pareto distribution.

I know about exploding rolls and penetrating rolls,  but they are close to uniform in practice.

One gets a geometric distribution by rolling repeatedly until a certain value is obtained and counting the number of rolls that is needed. Although strictly decreasing, it is a slow method which requires a lot of re-rolling.

Update: I've found a better way.

Absolute Value of the Difference of Two Rolls

A linear falling distribution with a single roll of two dice—almost

This interview mentions a promising technique, which is to roll the same dice twice and apply the absolute value function to the difference:
Because of the zero value, this isn't a perfect falling distribution, but if one is willing to re-roll until the result is not zero a falling distribution is achieved.

Tables

Falling distributions and in general any distribution using percentiles

Here is code for generating a d100 table which approximates an arbitrary distribution. It was used to make this table:

d100      level
01-331
34-552
56-703
71-804
81-865
87-916
92-947
95-968
97
9
98
10
99
11
00
12

An exponential distribution was used with the parameter chosen so 12 is the highest possible value. The distribution looks like this:

Sunday, November 12, 2017

Giant Hit Points

To get the hit points of a monster with a lot of hit dice, you have to roll the d8—or d6 if playing the old way—repeatedly and add them up.

This is similar to rolling fireball damage. An earlier post shows how to approximate the results of fireball damage using just two d6 rolls. The goal in the earlier post was to reduce the amount of calculation while preserving the original distribution.

The same could be done for hit dice. But do we want to preserve the original distribution? As noted in the previous post the result will usually be within 5 hit points of the mean. If a more uniform distribution is desired, we could replace an nd8 roll with an (n-1)×d8 + d8 roll.

Here are the distributions for a hill giant using 8d8 and 7×d8+d8:

A few values: 15, 22, 29, 36, 43, 50, and 57, are twice as likely as the others. If we were using 8×d8+d8 to roll hit points for a stone giant the distribution would be perfectly uniform.

When n is greater than 9, some values have a probability of zero. We could use an (n–2)×d8+2d8 roll so that all values are still possible, at least as long as n isn't greater than 17. Here is a comparison of using 15d8 and 13×d8+2d8 for storm giant hit points:
You might ask how hit points are distributed in the old modules. Let's take a look at the adult male hill giants in the steading:

Also see an earlier post for the distribution of goblin hit points in Little Keep on the Borderlands.

Wednesday, November 8, 2017

Polyhedra

We make use of in-game puzzles. To prosper in the Athenopolis campaign, familiarity with a fair amount of polyhedra lore is necessary.

Platonic Solids


Polyhedral dice come in the shapes of the five Platonic solids:
  • tetrahedron or triangular pyramid
  • hexahedron or cube
  • octahedron
  • dodecahedron
  • icosahedron
In the original edition of the game the colors of the dice were yellow, orange, green, blue, and white respectively.

How many vertices does an icosahedron have? You can pull out a die and try to count them, but it is better to observe that there 20 faces, and each has 3 vertices, for a total of 60 (vertex, face) pairs. However, each vertex is shared by 5 faces, so the number of vertices is 60 / 5 = 12.

A similar line of reasoning can be used to show the number of edges is 30.

In the Timaeus (c. 360 BCE), Plato associates the tetrahedron, octahedron, icosahedron, and cube with classical elements fire, air, water, and earth respectively. The dodecahedron is said to be the shape of the universe. Aristotle later associates the dodecahedron with the element aether.

The Platonic solids are the only five convex regular polyhedra. Euclid seems to argue something to this effect in Book XIII, Proposition 18 of The Elements (c. 300 BCE).  One translation of his claim is:
No other figures, besides the five said figures, can be constructed which is contained by equilateral and equiangular figures equal to one another.

Face, Edge, and Vertex Transitive

Imagine we had a case for the model of a polyhedron that fit it snugly. The polyhedron is face-transitive if we can place any face of the polyhedron to any face of the case and it still fits. A consequence of being face transitive is that every face is the same shape and size.

The polyhedron is edge-transitive if we can place any edge of the polyhedron to any inside angle of the case and it still fits. A consequence of being edge transitive is that every edge is the same length.

The polyhedron is vertex-transitive if we can place any vertex of the polyhedron to any corner of the case and it still fits. A consequence of being vertex transitive is that every vertex touches the same number of faces and edges.

Alternative names for face-transitive, edge-transitive, and vertex-transitive are isohedral, isotoxsal, and isogonal, respectively.

A polyhedron which is face, edge, and vertex-transitive is called a regular polyhedron.

Alternating Groups and Symmetry Groups

Let's reserve the letters V, E, and F  for the number of vertices, edges, and faces of a polyhedron, respectively. The vector (V, E, F) is called the face counting vector or f-vector of a polyhedron. For example the f-vector of the cube is (8, 12, 6).

Returning to the model of a polyhedron and its case, each way we can put the polyhedron in its case represents an element of the alternating group of the polyhedron.

Since Platonic solids are vertex transitive there is at least one group element for each of the V vertices. Each vertex is connected to 2 × E / V edges, and if we assign one of the model edges to a case edge the positions of the rest of the vertices and edges is determined. Thus the size of the alternating group is V × (2 × E / V) = E × 2.

The symmetric group allows for reflections as well as rotations. If the mirror image of a polyhedron also fits in its case, its symmetric group is twice the size of its alternating group.

VEF|A||S|
tetrahedron4641224
cube81262448
octohedron61282448
dodecahedron20301260120
icosahedron12302060120

The symmetry groups of the cube and octohedron are the same size. They are in fact isomorphic. The same is true of the dodecahedron and the icosahedron.

Other Polyhedra

Let's show that the tetrahedron with an f-vector of (4, 6, 4) has the smallest possible number of vertices, edges, and faces for a polyhedron.

A polyhedron must have at least 4 vertices since any 3 points are contained in a plane.

We can rule out a polyhedron with 3 faces by noting that an edge must have exactly two faces. For the polyhedron to have a vertex on the edge, the third face must intersect the vertex but not the rest of the edge. It follows  the polyhedron doesn't have any additional vertices, but this contradicts the fact that a polyhedron must have at least 4 vertices.

Each edge belongs to exactly two faces, but each face has three or more edges. The constraint 2E ≥ 3F  follows, and because a polyhedron must have at least 4 faces it must also have at least 6 edges.

For every value of F ≥ 4 we can construct a polyhedron called a pyramid with F faces by starting with a (F – 1)-polygon and connecting each vertex with a point not in the plane of the polygon. The f-vector of the polyhedron is (F, 2F – 2, F). A tetrahedron is triangular pyramid and the Great Pyramid of Giza is a square pyramid. The formula for the f-vector shows that we have also constructed a polyhedron for every V ≥ 4.

A pyramid is right if the line connecting the center of the polygon to the off vertex is perpendicular to the plane of the polygon. Otherwise the pyramid is oblique.

Similarly a prism is a way of constructing a polyhedron for each F ≥ 5 with an f-vector of (2F – 4, 3F – 6, F). The cube is a square prism. Note that a decagon prism has an f-vector of (20, 30, 12) which is the same as the f-vector of a dodecahedron. The example shows that the f-vector of a polyhedron doesn't necessarily tell us the number of edges each face has.

A prism is right if the off-polygon faces are perpendicular to the polygon faces. Otherwise the prism is oblique.

Polyhedral Dice

If we want the die to be fair, then the die should be face transitive. The Platonic solids are face transitive, but pyramids and prisms in general are not. Recall that a triangular pyramid is a tetrahedron and a square prism can be a cube.

There is a type of polyhedron called a bipyramid which yields an infinite family of face transitive polyhedra. The vertices of a regular n-polygon is connected to two vertices off the plane of the polygon on opposite sides. For the polyhedron to be face transitive, the vertices must be equidistant from and perpendicular to the center of the n-polygon. The figure is (n + 2, 3n, 2n) for n ≥ 3. The octohedron is a bipyramid.

The pentagonal bipyramid gives us a way to construct a 10-sided die, but most 10-sided dice are a different polyhedron called the pentagonal trapezohedron. The faces are quadrilaterals and in particular kites. The f-vector is (2n + 2, 4n, 2n) for n ≥ 3. The triangular trapezohedron has a f-vector of (8, 12, 6) which is the same as the cube.

The trapezohedron shows that face transitive does not imply edge transitive or vertex transitive. Bipyramids other than the square bipyramid or octahedron also show this.

The tetrahedron notwithstanding, for a polyhedron to be useful as a die we want each face to be parallel to a face on the opposite side so that there is always a clear "up".  Insisting that a bipyramid or trapezohedron have parallel faces places a constraint on the distance of the off-polygon vertices from the polygon. Update: or so I thought, but in fact the trapezohedron or bipyramid can have parallel faces regardless of the ratio of off-polygon vertex distance to polygon side length. And it should be emphasized that for a bipyramid to have parallel faces the polygon must have an even number of sides. The trapezohedron does not have this limitation.

The Catalan solids are another set of 13 face transitive polyhedra. One of these, the rhombic triacontahedron is used for 30-sided dice.

Euler's Characteristic

For a convex polyhedron, the following formula for the number of vertices, edges, and faces holds:
V – E + F = 2

Polytope

A regular polygon is a two dimensional analog of a Platonic solid.

Polytopes generalize polygons (in two dimensions) and polyhedra (in three dimensions) to n-dimensions.

A 4-polytope has 0-dimensional vertices, 1-dimensional edges, 2-dimensional faces, and 3-dimensional cells. The number of each can be represented by a f-vector with four elements: (V, E, F, C).

An n-polytope has n – 1 dimensional facets, n – 2 dimensional ridges, n – 3 dimensional peaks.

Sub-polytopes of any dimension can be called faces. If necessary to indicate the dimension they are called j-faces.

The extended f-vector of a polytope includes extra values on either end. One value, for dimension –1, represents the empty set. The other value, for dimension n, represents the polytope itself. These values are always 1. The cube has extended f-vector (1, 8, 12, 6, 1).

The formula for Euler's characteristic extends to convex polytopes and motivates our use of extended f-vectors. If fi is the number of faces of dimension t, then

$$ \sum_{i=–1}^n (–1)^i f_i = 0$$

Lattices and Flags

When studying a polyhedron such as the cube above we can create a graph called the face lattice of the polyhedron which shows which edges belong to which faces and which vertices belong to which edges.


At the top of the graph we put the entire polyhedron and at the bottom we put the empty set. This makes the graph a mathematical lattice. Every two elements in the lattice have a unique least element which contains both of them and a unique greatest element contained by both of them. The extended f-vector is the number of elements in each row of the lattice from the bottom up.

Two polyhedra are combinatorially equivalent if their face lattices are isomorphic.  The cube and the triangular trapezohedron are examples of combinatorially equivalent polyhedra. The dodecagon prism and the dodecahedron are not combinatorially equivalent even though their f-vectors are the same.

A flag is a sequence of "faces" of an n-polytope of increasing dimension: F- 1, F0, F1, ..., Fn, where each face is contained in the face that follows it in the sequence. The F-1 face is the "empty face" and the Fn face is the entire n-polytype.

A regular polytope is one where the symmetry group of the polytope acts transitively on the flags. This implies that the polytope is face, edge, and vertex transitive.

Ways to Number a Platonic Solid

The number of ways we can put n different numbers on the n faces of a Platonic solid is n! divided by the size of the alternating group of the solid.

tetrahedron2
cube30
octohedron1680
dodecahedron7,983,360
icosahedron40,548,366,802,944,000

Six-sided dice are often numbered with the constraint that opposite sides must add to 7. With this constraint there are only two ways to number a six-sided die. If you hold a six-sided die so that the sides for 1, 2, and 3 are showing, if the numbers increase in a counter-clockwise direction the die is said to be right-handed, which is the way Western dice are numbered.

Net

A polyhedron net is a set of edge-connected polygons, which can be folded into a polyhedron. Polyhedra can be constructed by printing a net on paper, cutting it out, and then folding the edges to create the shape.

Assigned Reading

"Convex Polyhedra" by Alexandrov. The reader is allowed to consult an English translation.