Dave Computes How to Draw Penrose Tiles on a Grid

In this post, I'll explore several aperiodic tile sets created by Roger Penrose, and how I devised ways of drawing these tilings on graph paper (or some such grid). All these drawings will be distorted to varying degrees, but they'll retain the core properties of Penrose's tilings.


Pentagonal Penrose Tiling (P1)

This tiling involves drawing pentagons with line segments oriented in one of only 5 possible directions. The smallest pentagons that look decent have line segments with slopes 0/2, 1/2, 2/1, -2/1, and -1/2. The pentagons are oriented either right-side-up (with flat edge on bottom) or upside-down (with flat edge on top).

Neighboring pentagons that share a side are always in opposite orientations.

Gaps occur between neighboring pentagons that touch at only one point and are in the same orientation.

Pentagon tiling is based on the idea that 6 pentagons can be assembled to nearly fill a larger pentagon. (Note that the edges of smaller regular pentagons would align perfectly with a larger regular pentagon. The imperfect alignment is due to the distortion created by drawing less-than-perfect pentagons on a grid.)

We can tile 6 of these larger pentagons to form an even larger pentagon.

Notice that each of the internal pentagons shares a side with 2, 3, or 5 other pentagons.

If we continue the tiling pattern, we'll see that the gaps between pentagons also come in three shapes: 2-pointed diamonds, 3-pointed boats, and 5-pointed stars.

Now let's talk about the matching rules. First, a 2-pentagon can never share a side with another 2-pentagon, a 3 cannot share with another 3, and a 5 cannot share with another 5. Thus, 2s are allowed to touch only 3s and 5s. We can prove that 3s must always sit on 5s and have a pair of 2s on their heads, pointing toward each other.

5s are always surrounded by 2s and 3s, with 2s always appearing in pairs, pointing away from each other.

Diamonds always connect a pair of 5-pentagons. They're always formed by a pair of 2s (pointing away from each other) and a pair of 3s. Notice that diamonds may appear symmetrical, but they have a kind of north and south pole.

Boats are always surrounded by the following pentagons.

Stars are always surrounded by five 2-pentagons. The five points of the star point to a mix of 3-pentagons and 5-pentagons.

The patterns repeat themselves on larger scales. So, just as a 3-pentagon always sits on a 5-pentagon and has two 2-pentagons on its head, a boat always sits on a star and has two diamonds on its head. You can see these relationships in this larger tiling.

Notice all the decagons that appear, each containing a boat and 2 diamonds. Every star is surrounded by 5 such decagons.

The key to drawing any large tiling is to only draw the parts you know for certain, until you prove you're absolutely stuck. At that point, you make a single binary choice, and draw everything that results from that choice until you're stuck again. Each choice reveals more than the previous choice did. If you reach a contradiction, then you made a choice that was inconsistent with the tiling you had so far. In that case, you'll need to study those situations more carefully and identify the patterns you missed.

I enjoy coloring in the gaps and 2-pentagons. The remaining 3- and 5- pentagons themselves form structures with 2, 3, or 5 points, and follow the same matching rules.

Pentagons within Pentagons

Penrose tilings have a fractal nature. They are self-similar at different scales. We can see that by drawing one line in each 2-pentagon and two lines in each 3-pentagon like this.

Confusingly, 5-pentagons sometimes require 0, 1, or 2 lines. Happily, if you draw lines in all 2- and 3-pentagons first, the missing lines in 5-pentagons are easy to figure out.

Notice that the new lines form bigger 2-, 3-, and 5-pentagons, and that each large pentagon of a certain type has the same pattern inside it produced by the smaller pentagons. Also notice that big 2-pentagons contain 2-pointed diamonds, large 3-pentagons contain 3-pointed boats, and large 5-pentagons contain 5-pointed stars.

We can therefore start with a pattern of pentagons of any size and subdivide them into a pattern of smaller pentagons, or build up patterns of bigger pentagons.

Notice the Fibonacci numbers in the lengths and slopes of the sides in the pentagons we can generate in this manner.

Bottom Length  Shallow Slopes  Steep Slopes
  2 = 2 × 1        ± 1/2          ± 2/1
  2 = 2 × 1        ± 2/3          ± 3/1

  4 = 2 × 2        ± 3/5          ± 5/2

  6 = 2 × 3        ± 5/8          ± 8/3

 10 = 2 × 5        ± 8/13        ± 13/8

Notice that, the larger the pentagon is, the better the lines of an inscribed star coincide with the lines of smaller pentagons.

By the way, we can make Penrose tilings with the smallest pentagons, but the result isn't particularly attractive. And it's rather difficult to draw, in part because some pentagons are separated by infinitely thin gaps.

From Pentagons (P1) to Darts and Kites (P2)

If we fill our pentagons as follows, then Penrose's darts and kites (P2) will emerge.

(I think of these as a hoof, spiderman, and dodge.)

Notice that I doubled the length of each line in the pentagons so that the new markings will align with the grid. The gray parts will turn into darts, and the white parts into kites. It takes two gray triangular parts to form a dart, separated by a gap in the pentagons. Notice that there are two kinds of white parts--wider parts and narrower triangular parts. It takes one of each part to form a kite. Knowing that the markings should form darts and kites helps guide drawing the pentagons.

Here you can see both a pentagon (P1) tiling and the corresponding darts and kites tiling (P2). Technically, the kites should extend just slightly into the gaps between pentagons, and the rest of the gaps should be filled by darts. It's easy to extend the darts and kites into the gaps, but it means going off the grid.

One of my favorite tilings is produced by marking the pentagons as follows.

The resulting pattern consists of larger darts and kites, but still retains the diamonds, boats, and stars of the P1 tiling. The darts and kites almost appear curved. I think the result reminds me of flowers and is quite beautiful. I haven't seen this pattern anywhere else.

Here it is again without the pentagons.

Darts and Kites (P2)

We can draw darts and kites without any pentagons. The key is to use two different sets of line segments--a shorter set and a longer set. Notice that these are the same lengths that appeared in the pentagons.

Below you can see how the same longer segments (thick) are used to form both darts (left) and kites (right). In the darts, the shorter segments (thin) point inward. In the kites, the shorter segments point outward. The decagon formed by the kites can serve as a useful guide.

Below we can see all 7 vertices that darts and kites can form. Notice that darts always eat a pair of kites.

Here's a pattern of darts and kites.

Larger darts and kites are found by cutting each dart in half along its line of symmetry, as shown below.

Likewise, we can draw even smaller dart and kite tiles (based on a pseudo-star and pseudo-decagon). Notice that the smallest dart and kite are identical, so shading the darts is helpful.

The advantage of using these very distorted and difficult-to-draw darts and kites is that many can be squeezed into a small drawing.

Penrose's darts and kites (P2) can be used to draw rhombi tilings (P3) by marking the dart and kite tiles as follows. Notice that each marking is taken from the set of shorter line segments.

When we put them together, some of the rhombi (shown in gray) are thinner and entirely contained in kites. Other fatter rhombi are formed when two P2 tiles meet.

Disappearing Pentagons

At some point I tried shrinking the pentagons (P1) into points. Each point still behaves like a 2-, 3-, or 5-pentagon, connecting to the correct number of points.

The diamonds, boats, and gaps between pentagons now take on interesting shapes. Here's the diamond.

And the boat.

And the star.

We can now forget about pentagons altogether and treat these distorted diamonds, boats, and stars as a new set of 3 tiles.

These fit together just as before. Boats still sit on stars. Boats still have two diamonds on their heads. A boat and two diamonds still form a decagon. Stars are still surrounded by 5 decagons. Just as each end of a diamond used to point to a 5-pentagon, now each end of a diamond is a point with 5 connections.

In drawing these, it's helpful to be aware of the three possible shapes that emerge between stars. These act like super-diamonds, super-boats, and super-stars.

Shading the diamonds results in the following fascinating pattern. Notice the white regions formed by stars and boats now act like larger diamonds, boats, and stars.

The prevalence of decagons in these patterns made me realize that I could make the tiles even smaller to form pseudo-decagons. Here are my smaller tiles.

With smaller tiles, we can make a more detailed tiling in the same size grid. The best thing about these tiles is they're the only ones I've found that use exclusively horizontal, vertical, and 45-degree diagonal segments to generate reasonably attractive pictures. Therefore, if you wanted to tile a your floor based on Penrose, I'd choose this tile set.

Here's a nicer coloring of the same picture.

Rhombi (P3)

Starting with distorted diamonds, boats, and stars, we can inscribe rhombi to produce Penrose's rhombi tilings (P3). Thinner rhombi have been shaded in.

The matching rule requires that any socket (like the two sockets in a boat or the five sockets in a star) must be filled by a thin (shaded) rhombus. Below you can see a Penrose rhombus tiling (P3) and the distorted diamonds, boats, and stars (with thick outlines) used to create it.

Happy tile drawing!

Dave Computes Trouble Strategy

Let's get into Trouble--a simple board game with a lot of luck and just enough strategy to make things interesting. We'll focus on the two-player variant. All data is based on trials with 1 million games, unless otherwise noted. I'll be referring to some simpler strategies by name, including:

Random = chooses a valid move at random
Capture = captures when possible, but otherwise plays at random
Capture+Start = captures when possible, otherwise starts a new peg, otherwise random


Statistics

With purely random play, player 1 has a slight advantage, winning 51% of games. Here are some additional stats. The Capture+Start column (for example) represents games in which both players use the Capture+Start strategy described above.

Statistic          Random  Capture  Capture+Start
Turns per game     55      58       62
Captures per game  1.1     1.4      2.7
Starts per game    4.7     5.0      6.3
Passes per game    15      16       14
Choices per game   16      16       26
No-Choice games    1.9%    2.2%     2.7%

On a given turn, a player may be forced to pass. This occurs about 25% of the time. Alternatively, a player might be forced to make a particular move, because only one of its pegs can move the number of spaces rolled (or start when a 6 is rolled). On other turns, a player might have a choice of which peg to move in response to a roll of the die. These choices occur on roughly 30 - 40% of turns. Astonishingly, note that about 2% of the time a player will not be given any choice in the course of an entire game (nearly always resulting in a loss).


Simple Strategies

I simulated various strategies playing against a purely random strategy ("Random"), and here are the win rates I found.

Strategy                   Win Rate against Random
Behind                     44%
Ahead                      46%
Random                     50%
Capture                    55%
Capture+Start              62%
Capture+Start+Ahead        64%
Capture+Start+SafestAhead  68%

The Ahead strategy always moves the peg that's furthest ahead (closest to the finish, or perhaps already in it), while the Behind strategy always moves the peg that is furthest behind (closest to the start, or perhaps starting a new peg). Surprisingly, note that both of these strategies are defeated by Random (which explains why my 4-year-old kept beating me).

The Capture strategy takes us to a 55% win rate. (Note that Capture outperforms Start, which starts a new peg whenever possible.)

We obtain a 62% win rate with Capture+Start. We get to 64% by playing Capture+Start+Ahead, which always moves the peg that's furthest ahead when it can't capture or start a new peg.

Any further improvement defies simple rules, and generally involves choosing to move pegs to escape threats and to threaten opponents. The Capture+Start+SafestAhead strategy listed above moves pegs to minimize the number of threats (in which an opponent's peg could capture the player's peg with a single roll of the die, including rolling a 6 to capture a peg at the opponent's entrance). If two moves lead to the same number of threats, the further ahead peg is moved. An even better strategy would also choose to threaten opponent pegs. It's a good bet that even optimal play can still expect to lose to Random about 30% of the time.


Elements of an Optimal Strategy

Initially, I was unable to write a program to find the optimal Trouble strategy. I therefore began by writing a program to approximate optimal play. (I'll come back to optimal play later in this post.) Each time my program is faced with a choice of which move to make, it tries each possible move and simulates a thousand games from that point. In those simulations, it plays the Capture+Start strategy for both sides, which can be computed quickly and is a good (but imperfect) approximation of optimal play. Here are the rules I extracted from my program's results:


Rule #1:  Capture

Always capture an opponent's peg when you can. There are exceptions to this rule, but they are extremely rare. In the game below, the blue player has a roughly 68% chance of winning if it moves the peg at the bottom right, which would escape a pursuer and get the peg to the finish. Nonetheless, the correct move is to capture with the peg at the top left, resulting in a 74% chance of victory.

Rule #2:  Start New Pegs

Prefer to start a new peg when you can. This rule and the ones that follow are really guidelines. They are usually correct, but exceptions are common.

In the game below, the blue player has rolled a 6, and has a 46% chance of winning by starting a new peg. This is a significant advantage over the 39% chance of winning by moving the peg already on the board--even though that move would escape a pursuer.

Rule #3:  Move the Furthest Ahead

In general, move whichever peg is closest to the finish. In the game below, the blue player should move the peg marked 39 because it is closer to the finish, even though moving the peg marked 34 would escape a pursuer and open up the possibility of starting a new peg.

Rule #4:  Avoid Danger

Most exceptions to the Furthest Ahead rule come down to avoiding danger. A dangerous space is one that could lead to a capture on the opponent's next roll. That means anywhere 1-to-6 spaces ahead of an opponent. It also means the opponent's start space (if the opponent has any pegs left to start).

In the game below, we've rolled a 4. Moving the further ahead peg (marked 47) would place it in danger, so it's significantly better to move the peg marked 51, placing that peg in danger instead.

In the game below, we've rolled a 5. If we move the top-left peg, it will land on the opponent's start space, leaving it vulnerable to being captured on the next turn. Therefore, we should move the peg marked 47 instead.

Note that it's ok to land on the opponent's start space if the opponent has no more pegs to start. It's also ok to land on the opponent's start with a 6, since we'll be able to roll again to get off that space before our opponent has a chance to roll.

Note that it's often helpful to forget about getting the further behind pegs to the finish. Instead, think of those pegs as ones you can move any time a roll would place the further-ahead peg in danger. In general, of all those pegs that can be moved without entering danger, move the one that's furthest ahead.

Rule #5: Play Dead

You've got two pegs on the board, and the one that's further ahead finds itself in danger. In this situation, it's often best to move the peg that's behind. The peg that's furthest ahead "plays dead" until it's safe to move again, either because the threat has leapt over us, or because a subsequent roll lets us move to safety.

In the game below, the further ahead peg is threatened and we've rolled a 2. Moving that peg 2 spaces still leaves it vulnerable to capture on the opponent's next roll. (We would need to have rolled at least a 3 to move our peg beyond our opponent's reach.) Therefore, we'll have it play dead, and we'll choose to move peg 39 instead.

There are multiple rationales for this choice. Advancing the further ahead peg often increases the number of opportunities for an opponent to capture it. In this situation, our opponent has only one active peg. If peg 36 plays dead, it's likely our opponent will be forced to step over our peg on the next couple of turns. Moving peg 39 also increases the chance that it will go on to catch up to and capture the opponent. Finally, it's possible that peg 36 is doomed no matter what. In that case, we're better off giving up on it and using our rolls to benefit peg 39. Of course, we'll re-examine the situation on our next roll.


Rule #6:  Desperate Times

Desperate times call for desperate measures. Often, when our opponent has 3 pegs in the finish, we need to stop whatever we're doing to make sure that last peg doesn't reach the finish. If it's unlikely we'll have time to get our remaining pegs to the finish, we're going to have to devote all our energy to capturing our opponent's last peg. That means starting as many pegs as we can and assembling an army to attack it.

In the game below, we should leave peg 11 to threaten our opponent. That's true even if we only rolled a 1. This peg is close enough to attack already. Now let's send in the reinforcements by advancing peg 22. (If we had more pegs left to start, then it'd be even more critical to free up our start space.) As desperate as our situation is, notice that we'll still pull off a win 22% of the time.

Steps Toward a Truly Optimal Strategy

It eventually occurred to me that my program to approximate optimal strategy suffered from a critical weakness. It assumed that I would play randomly in all future moves. That meant that a correct move now might be made incorrect by random play in the future, while an incorrect move now might prove safer in the face of random play. Specifically, I began to notice that the computer rarely suggested I chase my opponent, presumably because I might randomly pass it and get captured.

I therefore set out to write a program to solve for the true optimal strategy. What makes Trouble so tricky is that's its "game tree" is really a "game graph." Due to a capture, an earlier game state can be reached again later in a game, resulting in a cyclic game graph. Attempts to find an algorithm for solving such cyclic games were unsuccessful, so I invented my own algorithm. My idea was inspired by Google's PageRank algorithm. First, I identified all game states, where a state consists of whose turn it is and how the board is arranged. (I did not include the roll of the die.) I associated each game state with a number, indicating the probability that player 1 would win. I initialized all probabilities to 0.5. Then I visited each state exactly once, in no meaningful order, updating each state's probability, according to the following rules.

if player 1 won, record 1.0 and return
if player 2 won, record 0.0 and return
total = 0.0
for each roll 1 to 6:
  if no valid moves:
    if roll is 6: total += prob(this state)
    otherwise: total += 1.0 - prob(other player + this board)
  otherwise:
    bestValue = -1.0
    for each valid move:
      nextBoard = board after move is executed
      if roll is 6: moveValue = prob(this player + nextBoard)
      otherwise: moveValue = 1.0 - prob(other player + nextBoard)
      if moveValue > bestValue: bestValue = moveValue
    total += bestValue
record total / 6.0

Note that these rules are not recursive. In computing any one state's probability, it assumes all other states are already associated with correct probabilities. I updated each state's probability, and then I repeated the process again and again. The resulting probabilities converge surprisingly quickly to the limits of decimal precision.

Unfortunately, there are an awful lot of possible states in a game of trouble. Each peg can occupy one of roughly 30 possible locations. Let's consider a game where each player already has 3 pegs in the finish, and one peg yet to start. I call this a 1-1-game, since each player has one free peg. There are roughly 2 × 30 × 30 = 1,800 possible states in such a game--2 possible players whose turn it could be, roughly 30 possible locations for the first player's peg, and roughly 30 locations for the second player's peg. If each player has 2 finished pegs and 2 yet to start (a 2-2-game), there are now 2 × 30 × 30 × 30 × 30 = 1,620,000 possible states. The situation is actually a bit better than this. My program computes 381,936 such states. This proved to be highly manageable, and so my program had no trouble solving the 2-2-game for the optimal solution. In fact, it was able to solve m-n-games where m + n ≤ 5. But a full game would require roughly a million times more states than a 2-2-game. The rest of this post describes my understanding of the correct strategy, as gleaned from observing optimal 2-2-games.


More Elements of Optimal Play


All the elements I shared earlier remain true for optimal play. Here are a few more.

• Once a peg is within a single roll of any open places in finish, and that peg is unthreatened, then you should usually wait for a roll that can enter finish, instead of just moving closer to finish.

• Generally avoid moving a peg that has already finished, unless it would be detrimental to move other pegs.

• Generally move a lagging peg off of your opponent's start when your leading peg is safe.

• Here's how to play when no opponent pegs are on the board (all are in start or finish). If you have any pegs beyond your opponent's start, get them to finish. If all of your pegs are before your opponent's start, you should often set up a situation where the leading peg can leap clear across the opponent's start (with a roll of 5 or 6, from just before the opponent's start). Alternatively, set up an ambush, by getting a peg into the space just before your opponent's start, and then leaving it there, allowing your next peg to step over and proceed to finish. Generally abandon any such leap/ambush plans once your opponent starts a new peg.

• A trailing peg can often chase an opponent peg (that is closer to its finish than the trailing peg is) when the leading peg is likely to remain unthreatened.

Whenever you are faced with a decision, consider each possible move separately and identify what type of move it is. Most moves fall into the following categories, sorted by strength of move.

1.  Capture your opponent's peg.

2.  Start a new peg.

3.  Chase your opponent's last peg.

4.  Strong moves:  enter finish; escape a threat with leading peg (so that no longer a single roll from capture); chase an opponent's peg (that is closer to its finish than the chasing peg is to your finish). I could identify no clear rule for situations when you are faced with a decision between two strong moves. There's probably no more critical decision than determining whether to chase an opponent.

5. Set up a leap over start or ambush if the only pegs on board are yours, and they haven't reached your opponent's start yet.

5.  Move unthreatened leading peg until it could enter any open position in finish with a single roll.

6.  Move a trailing peg.

7.  Move closer to finish with a peg that is already a single roll from any open position in finish.

8.  Move within threat instead of playing dead, if the threatening peg is not likely to follow (because it's not your opponent's leader).

9.  Move finished peg within finish. This is a neutral move generally made to avoid making a detrimental move.

10.  Any other move, other than the following.

11.  Move into a threat with your leading peg.

12.  Allow opponent's last peg to pass your last defender.