Todd W. Schneider

How Many Paths are Possible in an 18 Hole Round of Match Play Golf?

And a practical investigation of real-life USGA match play data

In honor of the Ryder Cup, here’s a fun puzzle for the mathematically inclined golfer to consider: how many different paths are possible in an 18 hole round of match play golf?

If you’d rather not wade through the math then you can skip ahead to the “practical exploration” section of this post to see some actual match play data, but if you like puzzles then let’s assume the following match play rules, adapted and condensed via the USGA:

  • A match consists of one side (individual or team) playing against another over a round of 18 holes
  • A hole is won by the side that holes its ball in the fewer strokes
  • A hole is halved if each side holes out in the same number of strokes
  • A match is won when one side leads by a number of holes greater than the number remaining to be played
  • If the match is tied after 18 holes, it ends as a tie

We can depict the set of all possible match play paths as a tree that looks like this:

tree

This tree shows all possible paths in an 18 hole round of match play. The number of holes played is on the x-axis, and the score of the match is on the y-axis. Every match starts at (0, 0), and moves from left to right. The match ends after 18 holes have been played, or one player’s lead is greater than the number of holes remaining. The black dots represent nodes at which the match continues, and the red dots represent nodes at which the match is over

How many paths are there across this tree?

Let’s say that Adam and Bubba are playing a match, and we’ll arbitrarily score it from A’s perspective, so that a positive score means that A is winning and a negative score means that B is winning. Every match starts at the leftmost point of the tree: 0 holes played, 0 score (“all square”). The match progresses hole by hole, and moves from left to right across the tree. There are 3 possible outcomes on each hole: A wins the hole, B wins the hole, or the hole is halved. We can denote A winning a hole with an up arrow (↑), B winning a hole with a down arrow (↓), and a halve with a right arrow (→).

Any path can then be written as a sequence of arrows. For example, one path is where the two players halve each hole for 18 consecutive holes, resulting in a tied match:

→ → → → → → → → → → → → → → → → → →

Another path would be if A won the first 10 holes. In that scenario, A would be up by 10 holes with 8 to play, and so the match would be over:

↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑

From basic combinatorics, we know there are 318 = 387,420,489 sequences that are 18 characters long and contain only the ↑, →, and ↓ characters. However, many of those sequences are not valid match play paths, because the match ends when one player’s lead is greater than the number of holes to play. For example, the sequence of 18 consecutive ↑ characters is invalid because the match would end after 10 holes. It’s worth noting though that 318 serves as an upper bound on the final answer.

If we wanted to follow this combinatoric approach to the problem, we could do it, but it would be pretty tedious and annoying. We could phrase a series of questions like, “how many character sequences are there that contain only ↑, →, and ↓, are 12 characters long, end with ↑ or →, and contain exactly 7 more ↑ characters than ↓ characters?” That’s an answerable question (3,157), but it only tells us one small piece of the puzzle: the number of possible paths in a match that ends with a score of +7 after 12 holes played, or “7 & 6” in golf terminology (“7 up with 6 to play”). We could answer a question like the one above for every possible terminal node, then sum the results, but maybe there’s a (slightly) more elegant way to do this?

Work backward!

Backward induction provides a much-needed respite from the complication of combinations and permutations. Instead of trying to construct sequences of arrows subject to multiple constraints, we can work across the tree backward, i.e., from right to left, defining the number of paths to a node in terms of the number of paths to the nodes before it.

Let’s simplify the problem a bit by looking at the tree for a 3 hole match:

3 hole match tree

Take a look at the node in the tree at (2, 0): that’s 2 holes played, 0 score. How could we have gotten to that point? Well, we can look at all the line segments coming into the node and see that there were 3 possible previous states: (1, 1), (1, 0), and (1, -1), so the number of paths to (2, 0) is equal to the sum of the number of paths to each of (1, 1), (1, 0), and (1, -1).

Now look at the node at (3, 1): there are only 2 possible previous nodes, (2, 1) and (2, 0). A 3 hole match could not have been at (2, 2) before coming to (3, 1) because (2, 2) is a terminal node so the match would have ended there. Other nodes, for example (1, 1), have only 1 possible previous node.

So every node after (0, 0) has exactly 3, 2, or 1 possible previous nodes, and we can define the number of paths to a given node as the sum of the number of paths to its possible previous nodes. (0, 0) is a special base case because every match starts there, so we can say that there is exactly 1 path that gets a match to (0, 0). Let p(h, s) equal the number of paths to the node at h holes played, and score s. Then our full induction specification looks like this:

equation

Where v(h, s) is a boolean function whose value is 1 if (h, s) is a valid node where the match continues, and 0 otherwise:

equation

For example, v(10, 10) = 0 because the match does not continue if the score is +10 after 10 holes, v(0, 1) = 0 because a score of +1 after 0 holes is not a valid score, and v(1, 1) = 1 because +1 after 1 hole is a valid node and the match continues.

With the above induction specification, the final step is to evaluate p(h, s) for every possible terminal node in the 18 hole tree (i.e. all the red nodes), then take the sum to calculate the total number of possible paths. I wrote an R script to do this, which you can see on GitHub. The output gives a final answer of 169,688,089 total possible paths. This is less than half of the 318 number we hypothesized earlier as an upper bound. 132,458,427 of the valid paths are 18 characters long, which means that 34.2% of all 18 character sequences of ↑, →, and ↓ characters are valid paths. As a sanity check I also did the backward induction in a Google spreadsheet, which got the same answer and makes for a nice visual aid.

A practical exploration of actual USGA match play data

Now that we know there are roughly 170 million possible match play paths, we can turn to actual data to see what the real-life distribution of paths looks like. The Ryder Cup, USGA amateur tournaments, and WGC-Accenture Match Play Championship all use a match play format. The USGA data was the most accessible so I wrote a quick Ruby script to scrape hole-by-hole scores from every USGA amateur match from 2010 through 2014—a total of 50,773 holes played over 3,112 matches—and dump the results into a .csv file.

Intuitively we shouldn’t expect every path to occur with equal probability. The paths would have equal probability if every hole were an independent event with 1/3 probability for each of ↑, →, and ↓, but the holes are not independent, and the probabilities are not all 1/3. In fact of all the holes played in the dataset, 42% resulted in a halve, with the other 58% won by one of the players. Since a halve occurs more than 1/3 of the time, that will tend to put more weight on the paths that stay closer to 0 score as opposed to larger magnitude scores.

On the other hand, each hole is not an independent event. Even though USGA championships are selected to include only highly skilled players, there will inevitably be some matches where one player is better than the other, and these matches will tend to have larger margins of victory. It would seem particularly unlikely, for example, to see a path where A wins each of the first 9 holes then B wins each of the second 9 holes, resulting in a tie. If A won 9 consecutive holes, it’d be a pretty safe bet that A is the better player than B, and very unlikely that B would win 9 consecutive holes against the superior player.

Of the 3,112 USGA matches that I scraped, there are 3,110 unique paths. There are two paths that appear twice each, one that finishes 8 & 7, the other 4 & 3. The overall distribution of final scores from the USGA matches is wider and flatter than the distribution would be if we picked paths randomly from a uniform distribution:

distribution

This shouldn’t be too surprising, because as mentioned earlier the theoretical uniform distribution would come true if every hole were an independent event with equal probabilities for ↑, →, and ↓, and we don’t believe that to be the case. The wider actual distribution might suggest that many matches are between players of unequal ability: if some players are better than others then we would expect the flatter distribution with more large margins of victory.

We can also investigate whether the likelihood of winning the next hole is a function of the current score: all things held constant, we should probably expect the currently leading player to be the better player, and therefore more likely to win the next hole. I took all back-9 holes and aggregated the probabilities for winning, losing, and halving the next hole given the current match score, and sure enough the probability of a player winning a hole increases as a function of that player’s lead:

image

It’s a bit strange that the seemingly arbitrary “player 1” seems to win more than average, but I think it’s probably because USGA tournaments are seeded based on qualifying stroke play scores, and “player 1” as I’ve defined it is the stronger seed, at least in the early rounds. “Player 1” won 60.3% of the 3,112 matches, which would be an extremely unlikely result if each match were independent with 50/50 odds, so that might suggest the ordering of player names on the USGA’s website is somehow related to skill level.

Another potentially interesting phenomenon is the relative paucity of matches that end with a score of ±1 as opposed to 0 or ±2. I have no supporting data, but I’d hypothesize that players who are down 1 on the final hole tend to play more aggressively, which makes them more likely to either win or lose the hole, and less likely to halve it—imagine an aggressive birdie putt, which maybe goes in, or maybe goes 6 feet past the hole and leads to a bogey. It’s also possible that the effect is just noise and I’m making up a story about it, which is always an important caveat!

Kind of like that Facebook map

Finally, I thought it’d be fun to build something like the Facebook friendship map, except with the match play tree. The brightness and thickness of each segment represents the number of USGA matches that passed through that segment, so for example the segment from (0, 0) to (1, 0) is the brightest because that’s the most common path: every match starts at (0, 0), and more of them move to (1, 0) than any other node.

match play tree

Data and code on GitHub

The USGA hole-by-hole data is available as a .csv at https://github.com/toddwschneider/matchplay, along with R code to calculate the number of paths, draw match play trees, and do some data analysis, plus Ruby code to scrape the data. There’s also a Google spreadsheet with the number of paths calculation.

The Traveling Salesman with Simulated Annealing, R, and Shiny

I built an interactive Shiny application that uses simulated annealing to solve the famous traveling salesman problem. You can play around with it to create and solve your own tours at the bottom of this post, and the code is available on GitHub.

Here’s an animation of the annealing process finding the shortest path through the 48 state capitals of the contiguous United States:

state capitals tsp

How does the simulated annealing process work?

We start by picking an arbitrary initial tour from the set of all valid tours. From that initial tour we “move around” and check random neighboring tours to see how good they are. There are so many valid tours—(47! / 2), to be exact—that we won’t be able to test every possible solution. But a well-designed annealing process eventually reaches a solution that, if it is not the global optimum, is at least good enough. Here’s a step-by-step guide:

  1. Start with a random tour through the selected cities. Note that it’s probably a very inefficient tour!
  2. Pick a new candidate tour at random from all neighbors of the existing tour. Via Professor Joe Chang, one way to pick a neighboring tour “is to choose two cities on the tour randomly, and then reverse the portion of the tour that lies between them.” This candidate tour might be better or worse compared to the existing tour, i.e. shorter or longer.
  3. If the candidate tour is better than the existing tour, accept it as the new tour.
  4. If the candidate tour is worse than the existing tour, still maybe accept it, according to some probability. The probability of accepting an inferior tour is a function of how much longer the candidate is compared to the current tour, and the temperature of the annealing process. A higher temperature makes you more likely to accept an inferior tour.
  5. Go back to step 2 and repeat many times, lowering the temperature a bit at each iteration, until you get to a low temperature and arrive at your (hopefully global, possibly local) minimum. If you’re not sufficiently satisfied with the result, try the process again, perhaps with a different temperature cooling schedule.

The key to the simulated annealing method is in step 4: even if we’re considering a tour that is worse than the tour we already have, we still sometimes accept the worse tour temporarily, because it might be the stepping stone that gets us out of a local minimum and ultimately closer to the global minimum. The temperature is usually pretty high at the beginning of the annealing process, so that initially we’ll accept more tours, even the bad ones. Over time, though, we lower the temperature until we’re only accepting new tours that improve upon our solution.

If you look at the bottom 2 graphs of the earlier USA animation, you can see that at the beginning the “Current Tour Distance” jumps all over the place while the temperature is high. As we turn the temperature down, we accept fewer longer tours and eventually we converge on the globally optimal tour.

What’s the point?

That’s all well and good, but why do we need the annealing step at all? Why not do the same process with 0 temperature, i.e. accept the new tour if and only if it’s better than the existing tour? It turns out if we follow this naive “hill climbing” strategy, we’re far more likely to get stuck in a local minimum. Histograms of the results for 1,000 trials of the traveling salesman through the state capitals show that simulated annealing fares significantly better than hill climbing:

tsp vs hill climbing

Simulated annealing doesn’t guarantee that we’ll reach the global optimum every time, but it does produce significantly better solutions than the naive hill climbing method. The results via simulated annealing have a mean of 10,690 miles with standard deviation of 60 miles, whereas the naive method has mean 11,200 miles and standard deviation 240 miles.

And so, while you might not think that Nikolay Chernyshevsky or Chief Wiggum would be the best people to offer an intuition behind simulated annealing, it turns out that they, along with cliche-spewers everywhere, understand the simple truth behind simulated annealing: sometimes things really do have to get worse before they can get better.

Make your own tour with the interactive Shiny app

Here’s the Shiny app that lets you pick up to 30 cities on the map, set some parameters of the annealing schedule, then run the actual simulated annealing process (or just click ‘solve’ if you’re lazy). Give it a shot below! Bonus points if you recognize where the default list of cities comes from…

The app is hosted at ShinyApps.io, but if you want to run the app on your local machine, it’s very easy, all you need to do is paste the following into your R console:

1
2
3
install.packages(c("shiny", "maps", "geosphere"), repos="https://cran.rstudio.com/")
library(shiny)
runGitHub("shiny-salesman", "toddwschneider")

Code on GitHub

The full code is available on GitHub

Around the World in 80,000 Miles

Here’s another animated gif using a bunch of world capitals. The “solution” here is almost certainly not the global optimum, but it’s still fun to watch!

world tour

Do you work for AN investment bank, or THE investment bank?

Matt Levine had a good idea on Twitter:

This is amusing of course because in the world of prestige-obsessed New York Times wedding announcements, the definite article “the” is far more prestigious than the indefinite article “a” – you want to work at the place everyone knows as the consulting firm, not a consulting firm!

I crawled through the Wedding Crunchers database of NYT wedding announcements to look for mentions of investment banks and consulting firms immediately preceded by “the” or “a”, then compiled the results into the spreadsheet at the bottom of this page. Caveats apply: some firms (JPMorgan, for example) tend not to be explicitly referred to as banks or consultancies, so we cannot measure where they fall on this particular New York Times Weddings & Celebrations prestige scale.

The results are pretty much what you’d expect: the usual suspects of Goldman Sachs, Morgan Stanley, and McKinsey are almost exclusively referred to as “the” investment bank or consulting firm. Jefferies & Company receives the most mentions as “an” investment bank. While this puts Jefferies toward the bottom of the prestige scale, that might actually be a good omen: Lehman Brothers, Salomon Brothers, and Bear Stearns all rank highly in prestige, and we’ve seen how that worked out for them…