Strongly Connected Components

The game of eight-ball is popular amongst amateur pool players (aka local bangers) here in the US. I end up playing a lot of eight-ball (likely because my office is next door to a bar with pool tables), and find myself looking at it from a theoretical, computer-sciency viewpoint. FSMs, optimality, minimax, variance, etc. Needless to say, this doesn’t hook a lot of listeners at the pool hall, so I’ve learned to keep my mouth shut. Instead, I thought I’d write down some of my ideas here.

The general goal for each turn in eight-ball is to hit the cue ball so that it knocks an object ball into a pocket (if that didn’t make sense, read the rules.) Each shot is quite different, and the optimal shot depends on many factors, the most important of which is the shape of the table, or how the balls are arranged. It’s not always a clear-cut matter of making the next shot — sometimes we don’t want the object ball to go in the pocket, or sometimes we want two object balls to go in pockets.

There are two components of pool that are equally important:

1. Knowing what shot to take next
2. Executing that shot

The second component can’t be learned without a lot of practice, but the first can be learned without even picking up a pool cue, and that’s the part I find fascinating.

From one perspective, we can look at a turn as a dual-stated affair; the state (shape) of the table before our shot, and the state of the table after our shot. An optimal shot would involve sinking all our balls, with the 8 ball landing next to a pocket, and the cue ball nearby (so we can make the 8 ball on the next shot).

Usually, though, the state of the table after a shot is similar to its prior state, although the cue ball has moved, and perhaps another ball has gone in a pocket. There are many possible states, mainly limited by how hard we can hit the cue ball, the spin we can put on it, the speed of the table, and the laws of physics.

But how do we choose one of these states to aim for?

Generally, a turn is simplified into two immediate objectives:

1. Make one of our balls
2. Leave the cue ball in a good spot to make the next ball

For example, if we are solids in the image below, we’d like to pocket the 5 (orange) ball, and leave ourselves a shot on the 2 (blue) ball. A word of warning to pool players about these diagrams: they’re simplified — I just whipped them up to illustrate some ideas.

A good spot to leave the cue ball can be many places on the table (some subset thereof), and is possibly a large area of the table we can aim for. Often there are multiple such zones, some larger than others, and some more difficult to aim at. We can actually visualize these areas in three dimensions, like this:

The three-dimensional terrain illustrates possible locations of the cue ball after our shot, and its height represents our preference for that location. The steeper peak in the illustration may make the next shot simple, but is difficult to aim at. The wider, rolling hill doesn’t make for such an easy next shot, but is much easier to aim for.

This is where the decision gets more difficult. The terrain we generated is simplified; its only input is our preference for the final location of the cue ball. Other factors, such as shot difficulty, should be included in the computation of the terrain, which may alter our final shot decision.

Next time: Humility and our opponent (i.e. variance and terrain composition)