Playing out under a press: the safest route isn't the shortest

The football question

The opposition presses high. The keeper has the ball and the aim is simple: get it to the striker. He can go long, one pass that's often lost, or play out through the defenders, more passes but each one safer. Which route gives the best chance of getting the ball there?

The concept

A team in possession can be drawn as a network (mathematicians say a graph): the players are points and the passing lanes are links between them. Linear Algebra #10 counted how often the ball travelled along each link. Here each link carries something else: the chance a pass along it gets through the press.

A route is a chain of links from the keeper to the striker, and the ball only arrives if every pass on it is completed. Finding the best route through a network is a shortest path problem. "Shortest" here doesn't mean fewest passes: it means the route with the best value, here the highest chance of arriving.

A football example

Take the same made-up five-a-side team as Linear Algebra #10: keeper, defender, a left-sided and a right-sided player, and a striker. Against a high press, each pass gets through with a made-up chance: the keeper's short ball to the defender 90% of the time, his long ball to the striker only 30%.

A route's chance is every pass's chance multiplied together:

$$\text{chance of arriving} = p_1 \times p_2 \times \dots \times p_n$$

Shortest isn't safest

There are 16 routes from the keeper to the striker that don't involve the same player twice. The best five, and the long ball:

The long ball is the fewest passes and the worst of these. Playing out through the defender and the right-sided player takes three passes and gets through 49.7% of the time: 0.90 × 0.85 × 0.65. The two-pass routes lose out because the keeper's passes out wide are riskier than his short ball to the defender.

Dijkstra's method

Listing every route works for five players. For eleven, with a lane between every pair, there are 986,410 routes from keeper to striker, and real networks with more points have far more. The standard method is Dijkstra's, designed by the Dutch computer scientist Edsger Dijkstra in 1956, in his own account "in about twenty minutes" at a café in Amsterdam, and published in 1959.

It needs adding, not multiplying, so each pass gets a cost of minus its logarithm:

$$\text{cost of a pass} = -\log p$$

Then Dijkstra's method works outwards from the keeper, always settling the player who can be reached most cheaply so far, and never needing to look back at a player once he's settled. When it settles the striker, the route it used is the best one. It finds the same route as the full list: keeper, defender, right, striker, 49.7%.

Where the press should aim

A pressing coach is asking the opposite question: which lane, if we shut it, hurts them most? Shut each lane of the safest route in turn and find the next best:

Shutting the keeper's pass to the defender costs the most, 7.5 percentage points, because it's the first link of both of the two best routes. That's the network's way of saying what pressing coaches know already: stop the first pass and the whole build-up has to change. For the team playing out, it says where an extra short option, a midfielder dropping in, would be worth most.

Why it matters

Networks are everywhere in football: passes between players, scouts' journeys, travel between away games. Asking for the best route, and for the link whose loss hurts most, turns a picture of the team into decisions: how to play out, where to press, where to add an option. And the lesson of the long ball carries over: fewer steps isn't the same as better odds. Part 9 turns to scheduling: rotating a squad through a run of fixtures.

Limitations

• The chances are made up. Real completion rates under a press come from event or tracking data, which ours doesn't have.
• Passes aren't independent. One good pass can leave the next player more space, so multiplying chances is an approximation.
• The press moves. Opponents shift as the ball moves, so a lane's chance changes during the move. A fixed network is a snapshot.
• Arriving isn't scoring. The best route to the striker isn't necessarily the best route to a goal; that would need values for what happens when the ball arrives.

Try it yourself

The pressing team pushes its striker onto the keeper, and his short pass to the defender drops from 90% to 70%. Before running the code, guess: is playing out still better than going long, and which route is safest now?

Reproduce the analysis

Plain Python, nothing to install or download. It lists every route, runs Dijkstra's method, and shuts each lane of the best route in turn. All the numbers are made up.

import heapq
from math import exp, log

# Made up: the chance each pass is completed against a high press, for the five-a-side team of Linear Algebra #10.
# K keeper, D defender, L left, R right, S striker.
lanes = {("K", "D"): 0.90, ("K", "L"): 0.70, ("K", "R"): 0.65, ("K", "S"): 0.30,
         ("D", "K"): 0.95, ("D", "L"): 0.80, ("D", "R"): 0.85, ("D", "S"): 0.35,
         ("L", "D"): 0.85, ("L", "R"): 0.70, ("L", "S"): 0.60,
         ("R", "D"): 0.85, ("R", "L"): 0.70, ("R", "S"): 0.65}


def chance(route, lanes):
    """The chance every pass on a route is completed: multiply them."""
    p = 1.0
    for a, b in zip(route, route[1:]):
        p *= lanes[a, b]
    return p


def every_route(lanes, start="K", end="S"):
    """List every route that doesn't visit a player twice."""
    found, stack = [], [[start]]
    while stack:
        route = stack.pop()
        if route[-1] == end:
            found.append(route)
            continue
        stack += [route + [b] for (a, b) in lanes if a == route[-1] and b not in route]
    return found


def dijkstra(lanes, start="K", end="S"):
    """Safest route. A pass completed with chance p costs -log(p): multiplying chances becomes adding costs, and the
    cheapest route is the safest. Dijkstra's method settles the nearest player first and never looks back."""
    best, queue = {start: 0.0}, [(0.0, [start])]
    while queue:
        cost, route = heapq.heappop(queue)
        here = route[-1]
        if here == end:
            return route, exp(-cost)
        if cost > best.get(here, float("inf")):
            continue
        for (a, b), p in lanes.items():
            if a == here and cost - log(p) < best.get(b, float("inf")):
                best[b] = cost - log(p)
                heapq.heappush(queue, (best[b], route + [b]))
    return None, 0.0


routes = every_route(lanes)
print(f"{len(routes)} routes from keeper to striker; the five safest:")
for r in sorted(routes, key=lambda r: -chance(r, lanes))[:5]:
    print(f"  {'-'.join(r):<10} {len(r) - 1} passes, {chance(r, lanes):.1%}")
print(f"  Direct, K-S: 1 pass, {lanes['K', 'S']:.1%}")
route, p = dijkstra(lanes)
print(f"Dijkstra's method: {'-'.join(route)}, {p:.1%}")

print("\nIf the press shuts one lane of that route:")
for a, b in zip(route, route[1:]):
    open_lanes = {k: v for k, v in lanes.items() if k != (a, b)}
    r2, p2 = dijkstra(open_lanes)
    print(f"  {a}-{b} shut: best is {'-'.join(r2)}, {p2:.1%} ({(p2 - p) * 100:+.1f} percentage points)")

It prints:

16 routes from keeper to striker; the five safest:
  K-D-R-S    3 passes, 49.7%
  K-D-L-S    3 passes, 43.2%
  K-R-S      2 passes, 42.3%
  K-L-S      2 passes, 42.0%
  K-L-D-R-S  4 passes, 32.9%
  Direct, K-S: 1 pass, 30.0%
Dijkstra's method: K-D-R-S, 49.7%

If the press shuts one lane of that route:
  K-D shut: best is K-R-S, 42.3% (-7.5 percentage points)
  D-R shut: best is K-D-L-S, 43.2% (-6.5 percentage points)
  R-S shut: best is K-D-L-S, 43.2% (-6.5 percentage points)

The logarithm trick is why the snippet uses exp at the end: it turns Dijkstra's lowest total cost back into a chance.

Further reading

• Dijkstra's algorithm, Wikipedia. The method, its history and Dijkstra's own account.
• Shortest path problem, Wikipedia. The problem in general and the other methods for it.