Alternative Star Trek Warp Speed Scale and Related Equations

Alternative Warp Speed Scale

At the risk–hopefully not too great–of offending Star Trek enthusiasts and traditionalists, it seems that a simple update to the Warp speed definitions would allow for more realistic exploration of space without departing unduly from the original concept.

The update would use a simple base-10 log scale. Log scales are often used in science and technology with Decibel and Richter scales being common examples.

Under this revision, a Starship’s speed or velocity (v) would be defined as:

v = 10w-1c …(1)
where:
v = velocity (speed)
w = Warp speed
c = speed of light

Equation 1 above uses w-1 (rather than just w) as the exponent to preserve Warp 1 as the speed of light (c), since 100 = 1, which is in keeping with existing scales and the general understanding of Warp speeds. Warp 2 becomes 10 times the speed of light, Warp 3 is 100 times, etc.

Table 1 is a comparison with existing Warp speed factors (multiples of the speed of light):

Warp TOS (w3) TNG/DS9/VOY Proposed (10w-1)
1 1 1 1
2 8 10 10
3 27 39 100
4 64 102 1000
5 125 214 10,000
6 216 392 100,000
7 343 656 1M
8 512 1024 10M
9 729 1516 100M
9.9 3053 794M
9.99 7912 977M
10 Not possible Not possible 1000M (see below)

Table 1 Comparison of Traditional and Proposed Warp Speed Factors

Series abbreviations:

  • TOS = The Original Series
  • TNG = The Next Generation
  • DS9 = Deep Space Nine
  • VOY = Voyager

The main advantages of the proposed approach are that it:

  • aligns reasonably well, and in some cases better, with time/distance in the TV/film series
  • makes the galaxy more navigable in human time frames
  • makes intergalactic travel plausible
  • would relax the somewhat artificial and tortured Warp 10 limit, however, this can be restored in a more mathematically rigorous way (see below)

While the proposed speeds are significantly greater than the standard scales, at least for higher Warp values, they fit more comfortably with the vast distances found in our Universe. For example, using the old scale (TNG say), to travel from Earth to the centre of our galaxy, about 25,000 light years, it would take over 16 years at Warp 9 and over 3 years at Warp 9.99.

Going to another (close) galaxy is simply implausible, taking 300 or more years at Warp 9.99. Given there are hundreds of billions of galaxies out there, it seems a bit limiting to restrict exploration to such a tiny fraction of the known universe.

By contrast, Table 2 below shows a distance and travel time chart for the proposed new scale.

Warp Local Planets Nearby stars Visible stars Federation Centre of galaxy Cross galaxy Nearby galaxies
(0.0005 ly) (50 ly) (500 ly) (5,000 ly) (25,000 ly) (100,000 ly) (5 Million ly)
1 4.4 hr 50.0 yr 500 yr 5,000 yr 25,000 yr 100,000 yr 5,000,000 yr
2 26.3 min 5.0 yr 50.0 yr 500 yr 2,500 yr 10,000 yr 500,000 yr
3 2.6 min 6.0 mth 5.0 yr 50.0 yr 250 yr 1,000 yr 50,000 yr
4 15.8 sec 2.6 wk 6.0 mth 5.0 yr 25.0 yr 100 yr 5,000 yr
5 1.6 sec 1.8 day 2.6 wk 6.0 mth 2.5 yr 10.0 yr 500 yr
6 0.16 sec 4.4 hr 1.8 day 2.6 wk 3.0 mth 1.0 yr 50.0 yr
7 16 msec 26.3 min 4.4 hr 1.8 day 1.3 wk 1.2 mth 5.0 yr
8 1.6 msec 2.6 min 26.3 min 4.4 hr 21.9 hr 3.6 day 6.0 mth
9 0.16 msec 15.8 sec 2.6 min 26.3 min 2.2 hr 8.8 hr 2.6 wk
10 0.016 msec 1.6 sec 15.8 sec 2.6 min 13.1 min 52.6 min 1.8 day

Table 2 Distance and Travel Times for the Proposed New Warp Speeds

Remembering that a scale is just that, a scale. It doesn’t mean that starships can reach these speeds or sustain them for extended periods. Indeed, standard cruising speed may be significantly less than full speed because of engine stress and energy efficiency.

The next section builds on these ideas by placing limits on Warp speed based on various criteria.

Warp Speed Constraints

To provide limits on the speed of Warp capable ships, and to stay faithful to the idea of a universal maximum Warp speed, for example Warp 10, we can introduce some constraints. One approach is a blend of relativistic and newtonian mechanics.

First, let’s assume that:

  1. The force required to move a ship though the Warp field is proportional to the square of its Warp speed, and,
  2. There is an universal maximum Warp speed (μ) similar to the speed of light in standard physics

Based on these two assumptions, the force (F) required to “push” through the Warp field can be written mathematically as:

F = aw2 / √(μ2-w2) …(2)
where:
F = force
a = constant
w = warp speed
μ = universal maximum warp speed

The numerator is the Warp squared factor from the first assumption above. The denominator is analogous to the Lorentz factor of special relativity which is usually written 1/√(c2-v2). It means the required force increases as the speed approaches the universal maximum Warp speed and becoming infinite at that maximum Warp speed. This meets the second assumption above and provides a robust mathematical underpinning of the limit.

Using the force definition from Equation 2 and the velocity from Equation 1, we can calculate the Power (P) required by a Warp engine to maintain a constant velocity using the standard relation:

  • Power (P) = Force (F) by velocity (v)

This gives:

P = Fv = acw210w-1 / √(μ2-w2) …(3)
where:
P = power
F = force
v = velocity (speed)
a = constant
c = speed of light
w = warp speed
μ = universal maximum warp speed

From Equation 3 the energy needed to travel a particular distance can be derived using the standard definitions:

  • distance (d) = velocity (v) by time (t)
  • Energy (E) = Power (P) by time (t)

This leads to the following energy equation:

d = vt
E = Pt = (Fv)t = F(vt) = Fd = adw2 / √(μ2-w2) …(4)
where:
E = energy
P = power
F = force
v = velocity (speed)
t = time
d = distance
a = constant
w = warp speed
μ = universal maximum warp speed

In addition to power and energy calculations, we can derive an equation for efficient defined as the distance travelled per unit of energy consumed (similar to fuel efficiency for motor vehicles). The efficiency (eff) equation follows directly from Equation 4:

eff = d/E = √(μ2-w2) / aw2 …(5)

Setting a Universal Maximum Warp (μ)

We can choose any Warp speed as the universal maximum, but let’s stay with convention and make μ=10.

The constant a in the above equations depends on the “units” we use to measure the various quantities. For simplicity, let’s make P=1 when w=1. We can put these values into the Power equation (3) above and solve for a as follows:

1 = ac12101-1 / √(102-12)
1 = ac / √(102-12)
ac = √(102-12) = √99
a = √99 / c

Then substituting a back into Equations 3 gives:

Pμ=10 = √99w210w-1 / √(100-w2) …(6)

Using the same approach for the Energy and Efficiency equations, namely:

  • Energy = 1 per unit distance (say 1 lightyear) when w = 1
  • Efficiency = 1 (100%) when w = 1

We get:

Eμ=10 = √99w2 / √(100-w2) per unit distance …(7)
effμ=10 = √(100-w2) / √99w2 …(8)

Table 3 below shows comparative results for Power, Energy and Efficiency for various Warp speeds based on Equations 6, 7 and 8. It also includes the time it would take to travel one light year at the given Warp speed as a reference.

Warp Power Energy per ly Efficiency (%) Time to travel 1 ly
1 1 1.0 100.00 1.0 yr
2 41 4.1 24.62 1.2 mth
3 939 9.4 10.65 3.6 day
4 17,370 17.4 5.76 8.8 hr
5 287,228 28.7 3.48 52.6 min
6 4,477,443 44.8 2.23 5.3 min
7 68,269,794 68.3 1.46 31.5 sec
8 1,061,319,933 106.1 0.94 3.2 sec
9 18,489,527,619 184.9 0.54 0.32 sec

Table 3 Comparative Power, Energy and Efficiency for Various Warp Speeds (μ=10)

These results show that:

  • Power requirements rapidly (exponentially) increase as Warp speeds increase
  • Energy (fuel) requirements modestly increase as Warp speeds increase
  • Efficiency, which is essentially the inverse of energy consumption, reduces in line with energy increases

The massive power requirements speak to the difficulty of achieving higher Warp speeds. It confirms the understanding that significant technical advances are required to go just one step up the Warp speed ladder. It also supports the idea that even a fractional increase in Warp speed comes at a significant cost in terms of additional power requirements.

While the power demands are very high at higher Warp speeds, the energy consumption (i.e. fuel use) remains relatively modest (although increasing). This means the main technical challenge in Warp drive design is to convert the available energy at a high enough rate to provide the power demands needed to achieve a given Warp speed.

The energy efficiency figures can be interpreted, in starship terms, as light years per unit of fuel, for example antimatter. So you get, say, 100 light years per kilogram of antimatter at Warp 1, but only 24.6 at Warp 2, and this drops down to just over half a light year (0.54) at Warp 9, of course you cover that half light year in a fraction of a second!

Despite the rather hypothetical situation, the overall results are consistent with what we might expect from Starship pseudo physics or, perhaps, Warp drive mechanics.

Engine Power Levels

We can further expand on these results to show how the engine power output affects Warp speeds. Lets assume full speed – the rated top speed – is achieved when the engine is producing 100% of its rated power output. Table 4 below shows the corresponding Warp speeds associated with various percentages of this power output for different rated Warp speeds (leftmost column).

Rated Warp 20% 40% 60% 80% 100% 120% 140% 160% 180% 200%
2 1.5 1.7 1.8 1.9 2.0 2.1 2.1 2.1 2.2 2.2
3 2.5 2.7 2.8 2.9 3.0 3.1 3.1 3.2 3.2 3.2
4 3.4 3.7 3.8 3.9 4.0 4.1 4.1 4.2 4.2 4.2
5 4.4 4.7 4.8 4.9 5.0 5.1 5.1 5.2 5.2 5.3
6 5.4 5.7 5.8 5.9 6.0 6.1 6.1 6.2 6.2 6.3
7 6.4 6.7 6.8 6.9 7.0 7.1 7.1 7.2 7.2 7.3
8 7.4 7.7 7.8 7.9 8.0 8.1 8.1 8.2 8.2 8.2
9 8.4 8.7 8.8 8.9 9.0 9.1 9.1 9.2 9.2 9.2

Table 4 Warp Speeds for Various Engine Power Percentages (μ=10)

Table 4 shows that running on lower power settings doesn’t significantly reduce the Warp speed compared with its rated full speed (100% power). And conversely, running the engine above its rated power (i.e. overloading it) produces only marginal gains in Warp speed.

Based on this observation, let’s assume Starfleet defines the following Warp speed/power designations:

Designation Percentage of Rated Power Description
Reserve Warp 10% Energy conservation or damaged engine
Standard Warp 33% Standard cruising speed, default if no speed specified
Express Warp 67% Expedited speed
Full Warp 100% Rated full speed
Flank1 Warp 133% Flank speed (medium overload)
Maximum Warp 167% Maximum speed (maximum overload), emergency situations

Table 5 Starfleet Designations with Associated Rated Power Percentages

  1. Flank is a US nautical term used to denote speeds in excess of “full” speed.

Using these Starfleet designations, the corresponding Warp speeds, and the time to travel one lightyear (ly) at those speeds, for different Warp rated ships are shown in Table 6 below.

Rated Warp Designation Reserve Standard Express Full Flank Maximum
Power % 10% 33% 67% 100% 133% 167%
2 Warp 1.3 1.7 1.9 2.0 2.1 2.2
Time/ly 5.4 mth 2.5 mth 1.6 mth 1.2 mth 4.3 wk 3.6 wk
3 Warp 2.3 2.6 2.9 3.0 3.1 3.2
Time/ly 2.9 wk 1.2 wk 5.0 day 3.7 day 2.9 day 2.5 day
4 Warp 3.2 3.6 3.9 4.0 4.1 4.2
Time/ly 2.3 day 21.1 hr 12.1 hr 8.8 hr 6.9 hr 5.8 hr
5 Warp 4.2 4.6 4.9 5.0 5.1 5.2
Time/ly 5.8 hr 2.2 hr 1.2 hr 52.6 min 41.4 min 34.3 min
6 Warp 5.2 5.6 5.9 6.0 6.1 6.2
Time/ly 36.3 min 13.3 min 7.4 min 5.3 min 4.1 min 3.4 min
7 Warp 6.2 6.6 6.9 7.0 7.1 7.2
Time/ly 3.7 min 1.3 min 44.4 sec 31.5 sec 24.7 sec 20.5 sec
8 Warp 7.2 7.6 7.9 8.0 8.1 8.2
Time/ly 21.7 sec 7.9 sec 4.4 sec 3.2 sec 2.5 sec 2.1 sec
9 Warp 8.2 8.6 8.9 9.0 9.1 9.2
Time/ly 2.0 sec 0.75 sec 0.43 sec 0.32 sec 0.25 sec 0.21 sec

Table 6 Actual Warp Speed and Time to Travel 1 ly for Starfleet Designated Speeds (μ=10)

This means a starship that is rated as Warp 5, for instance, has a standard cruising speed of Warp 4.6 and maximum speed of Warp 5.2. However, there are two main reasons why ships cannot simply run at their maximum Warp speed:

  • Energy cost (fuel)
  • Engine endurance

We have already looked at energy consumption and seen that energy efficiency does reduce significantly at higher Warp speeds, but an even stronger reason to reduce Warp speed is engine endurance. This is explored in more detail in the next section.

Engine Endurance

Engine endurance is the length of time the engine can operate at a particular power output level before it requires maintenance. Typically Warp engines must be taken offline for a period to allow the maintenance to be performed.

Without maintenance, the risk of a major engine failure or even a catastrophic engine breach significantly increases.

I’m givin’ it all she’s got, Captain! If I push it any farther, the whole thing’ll blow!

– Montgomery ‘Scotty’ Scott

The higher the output power, and hence Warp speed, the shorter the operating time. Conversely, the lower the power output the longer the engine can run before requiring maintenance.

The engine endurance is a function of the ratio of actual engine power compared to the rated (100%) engine power (ρ = P / Pr). This ratio is one (1) when the actual power equals the rated power. Less than one when the actual power is lower than the rated power, such as cruising, and greater than one in overload situations.

There are various ways to formulate an endurance equation but let’s assume that Starfleet Warp drives have an endurance (ε) characterised by an inverted sigmoid function.

As a refresher, the following graphs show a “standard” sigmoid function and some progressive variations to transform it into something more suitable for use as an endurance function.

Standard Sigmoid
Inverted Sigmoid
Inverted Shifted Sigmoid
Inverted Shifted Scaled Sigmoid

These versions use the natural logarithm base (e), rather than 10, say, but as shown below the actual base value is irrelevant.

For those not interested in the mathematical details, please skip to the Summary Table at the end of the post where all the results are summarised in one combined table.

The general form of the endurance equation is:

ε(ρ) = a√(μ2-wr2) / (1 + bec(ρ-0.5)) …(9)
where:
ε = engine endurance
a, b and c = constants (‘c’ is not the speed of light here)
μ = universal maximum warp speed
wr = rated Warp speed of the ship/engine
ρ = p / pr
p = actual engine power
pr = rated engine full (100%) power

The Lorentzian term √(μ2-wr2) in the numerator is designed to limit the endurance as the rated Warp speed (wr) increases. This changes the endurance characteristics for different rated Warp speeds. It makes the endurance approach zero as the rated Warp speed approaches the universal maximum Warp limit (μ).

By setting the exponent to ρ-0.5, the endurance curve is symmetric about ρ=0.5.

The constant a, in conjunction with √(μ2-wr2), forms the upper limit (asymptote) of the sigmoid function and becomes a scaling factor that depends on the units used to measure endurance.

The constants b and c can be determined by making the following assumptions:

  1. Endurance at half power (ρ=0.5) is half the maximum endurance (i.e. ε(0.5) = a√(μ2-wr2)/2). This also makes the maths below simpler.
  2. A Starfleet regulation states that for a Starship to be rated at a particular Warp speed (wr), its engine must be able to sustain that Warp speed for a minimum period of time (εr).

For brevity, we will assign k = √(μ2-wr2) in the follows calculations. Note k is a constant for each rated Warp speed.

Substituting Assumption 1, ε(0.5)=a√(μ2-wr2)/2=ak/2, into Equation 9 allows the value of b to be determined as follows:

ε(0.5) = ak/(1 + bec(0.5-0.5)) = ak/(1 + be0) = ak/(1 + b) = ak/2
=> (1 + b) = 2
=> b = 1

Putting this value of b back into Equation 9 gives:

ε(ρ) = ak / (1 + ec(ρ-0.5)) …(10)

Substituting Assumption 2, ε(1) = εr, into Equation 10 allows the value of c to be determined as follows:

ε(1) = ak/(1 + ec(1-0.5)) = ak/(1 + ec/2) = εr
=> εr(1 + ec/2) = ak
=> εr + εrec/2 = ak
=> εrec/2 = ak – εr
=> ec/2 = (ak – εr)/εr = ak/εr – 1
=> c/2 = log(ak/εr – 1)
=> c = 2log(ak/εr – 1)

Putting this value of c back into Equation 10 above gives:

ε(ρ) = ak / (1 + e2log(ak/εr – 1)(ρ – 1/2))
= ak / (1 + e(2ρ – 1)log(ak/εr – 1))

Which, remembering, enlog(x) = xn, simplifies to:

ε(ρ) = ak / (1 + (ak/εr – 1)(2ρ-1)) …(11)
where:
ε = engine endurance
a = constant unit scaling factor
k = √(μ2-wr2)
wr = rated Warp speed of the ship
εr = endurance at full power (ρ=1)
ρ = p / pr
p = actual engine power
pr = rated engine full (100%) power

Finally, let’s provide some concrete values for μ, a and εr so we can calculate some actual results. We will stick with μ=10 for the universal Warp limit. Let’s use a (Earth) day as the endurance unit. Setting εr to 0.5 days (i.e. 12 hours) as the minimum period the engine must sustain the rated Warp speed.

Noting that k will range between 0 and 10 (mostly nearer 10), setting a to 10 will give a maximum endurance of 100 days. This seems about right. Substituting μ=10, a=10 and εr=0.5 into Equation 11 gives:

ε(ρ) = 10√(100-wr2) / (1 + (20√(100-wr2) – 1)(2ρ-1)) days …(12)
where:
wr = rated Warp speed of the ship
ρ = p / pr

A plot of endurance at different rated Warp speeds is shown below:

The following points can be drawn from this plot:

  • Overall engine endurance declines progressively as the rated Warp speeds increase. Put simply, high performance engines need more frequent maintenance.
  • All the individual lines meet at (ρ=1, ε=0.5), although it is hard to see in the plot.
  • For any given rated Warp speed, the endurance declines significantly as the power ratio (ρ) increases. In particular, running at standard (33%) power provides much better endurance than express (67%) or higher power ratios.

Table 7 below is a tabular version of the graph above. It shows engine endurance times for the designated power settings for different rated Warp speeds.

Rated Reserve Standard Express Full Flank Maximum
Warp (10%) (33%) (67%) (100%) (133%) (167%)
2 3.2 mth 2.7 mth 2.1 wk 12.0 hr 21.5 min 38.4 sec
3 3.1 mth 2.7 mth 2.0 wk 12.0 hr 21.9 min 39.8 sec
4 3.0 mth 2.6 mth 2.0 wk 12.0 hr 22.5 min 42.0 sec
5 2.8 mth 2.4 mth 1.9 wk 12.0 hr 23.4 min 45.3 sec
6 2.6 mth 2.2 mth 1.8 wk 12.0 hr 24.7 min 50.4 sec
7 2.3 mth 2.0 mth 1.6 wk 12.0 hr 26.6 min 58.8 sec
8 1.9 mth 1.6 mth 1.4 wk 12.0 hr 30.0 min 1.2 min
9 1.4 mth 1.2 mth 1.1 wk 12.0 hr 37.3 min 1.9 min

Table 7 Endurance Times for Different Rated Warp Speeds (μ=10)

Table 7 clearly shows that the endurance at full speed is the same (0.5 day = 12 hr) for each rated Warp speed in accordance with Assumption 2 above.

It also shows, which is not clear from the graph, that the engine endurance of overloaded power settings (i.e. flank and maximum) are dramatically less than full power, measured in only minutes or seconds. This plays into the idea that, in an emergency, it is possible to squeeze a bit more speed from the engine but only for comparatively short periods.

Summary

The various results above can be combined into a single summary table. Table 8 below shows the following information:

  • Warp speed (at the designated power setting)
  • Endurance (maximum time the engine can run before maintenance)
  • Maximum distance before maintenance (Warp speed x endurance time)
  • Time to travel 1 lightyear (at the specified Warp speed)
  • Energy (fuel) to travel 1 lightyear in an arbitrary unit. In this case we have used kilograms of antimatter

for ships of different rated Warp speeds running at Starfleet designated power settings. The data is based on the equations developed earlier.

Rated Warp Designation Reserve Standard Express Full Flank Maximum
Power % 10% 33% 67% 100% 133% 167%
2 Warp 1.3 1.7 1.9 2.0 2.1 2.2
Endurance 3.2 mth 2.7 mth 2.1 wk 12.0 hr 21.5 min 38.4 sec
Distance 0.59 ly 1.1 ly 0.30 ly 0.01 ly 0.00 ly 0.00 ly
Time/ly 5.4 mth 2.5 mth 1.6 mth 1.2 mth 4.3 wk 3.6 wk
Fuel/ly 0.2 kg 0.3 kg 0.4 kg 0.4 kg 0.4 kg 0.5 kg
3 Warp 2.3 2.6 2.9 3.0 3.1 3.2
Endurance 3.1 mth 2.7 mth 2.0 wk 12.0 hr 21.9 min 39.8 sec
Distance 4.6 ly 9.7 ly 2.8 ly 0.14 ly 0.01 ly 0.00 ly
Time/ly 2.9 wk 1.2 wk 5.0 day 3.7 day 2.9 day 2.5 day
Fuel/ly 0.5 kg 0.7 kg 0.9 kg 0.9 kg 1.0 kg 1.1 kg
4 Warp 3.2 3.6 3.9 4.0 4.1 4.2
Endurance 3.0 mth 2.6 mth 2.0 wk 12.0 hr 22.5 min 42.0 sec
Distance 40 ly 88 ly 27 ly 1.4 ly 0.05 ly 0.00 ly
Time/ly 2.3 day 21.1 hr 12.1 hr 8.8 hr 6.9 hr 5.8 hr
Fuel/ly 1.1 kg 1.4 kg 1.6 kg 1.7 kg 1.8 kg 1.9 kg
5 Warp 4.2 4.6 4.9 5.0 5.1 5.2
Endurance 2.8 mth 2.4 mth 1.9 wk 12.0 hr 23.4 min 45.3 sec
Distance 351 ly 809 ly 258 ly 14 ly 0.57 ly 0.02 ly
Time/ly 5.8 hr 2.2 hr 1.2 hr 52.6 min 41.4 min 34.3 min
Fuel/ly 1.9 kg 2.4 kg 2.7 kg 2.9 kg 3.0 kg 3.1 kg
6 Warp 5.2 5.6 5.9 6.0 6.1 6.2
Endurance 2.6 mth 2.2 mth 1.8 wk 12.0 hr 24.7 min 50.4 sec
Distance 3.1 kly 7.3 kly 2.4 kly 137 ly 6.0 ly 0.25 ly
Time/ly 36.3 min 13.3 min 7.4 min 5.3 min 4.1 min 3.4 min
Fuel/ly 3.1 kg 3.8 kg 4.2 kg 4.5 kg 4.7 kg 4.8 kg
7 Warp 6.2 6.6 6.9 7.0 7.1 7.2
Endurance 2.3 mth 2.0 mth 1.6 wk 12.0 hr 26.6 min 58.8 sec
Distance 27 kly 65 kly 22 kly 1.4 kly 65 ly 2.9 ly
Time/ly 3.7 min 1.3 min 44.4 sec 31.5 sec 24.7 sec 20.5 sec
Fuel/ly 4.8 kg 5.8 kg 6.4 kg 6.8 kg 7.1 kg 7.4 kg
8 Warp 7.2 7.6 7.9 8.0 8.1 8.2
Endurance 1.9 mth 1.6 mth 1.4 wk 12.0 hr 30.0 min 1.2 min
Distance 233 kly 546 kly 198 kly 14 kly 724 ly 36 ly
Time/ly 21.7 sec 7.9 sec 4.4 sec 3.2 sec 2.5 sec 2.1 sec
Fuel/ly 7.3 kg 8.8 kg 9.9 kg 10.6 kg 11.2 kg 11.6 kg
9 Warp 8.2 8.6 8.9 9.0 9.1 9.2
Endurance 1.4 mth 1.2 mth 1.1 wk 12.0 hr 37.3 min 1.9 min
Distance 1.8 Mly 4.1 Mly 1.6 Mly 137 kly 8.8 kly 535 ly
Time/ly 2.0 sec 0.75 sec 0.43 sec 0.32 sec 0.25 sec 0.21 sec
Fuel/ly 11.7 kg 14.6 kg 16.9 kg 18.5 kg 19.8 kg 20.9 kg
9.5 Warp 8.8 9.2 9.4 9.5 9.6 9.6
Endurance 4.3 wk 3.5 wk 6.3 day 12.0 hr 46.9 min 3.0 min
Distance 4.7 Mly 9.9 Mly 4.1 Mly 433 kly 34 kly 2.5 kly
Time/ly 0.55 sec 0.22 sec 0.13 sec 100 msec 83 msec 72 msec
Fuel/ly 15.8 kg 20.9 kg 25.3 kg 28.8 kg 31.9 kg 34.8 kg

Table 8 Rated Warp Summary Table

For example, consider a Warp 5 rated ship. At Standard Warp, it will travel at Warp 4.6 which it can sustain for 2.4 months, or just over 800 lightyears, before maintenance is required. At this speed, it will take 2.2 hours and use 2.4 kg of antimatter for each lightyear travelled.

In an emergency, it can travel at Warp 5.2 but only for 45 seconds.

It is also worth noting that Standard Warp provides the best total range for a given rated Warp (i.e. the maximum distance travelled before engine maintenance is required). This agrees with commonsense that there is a “sweet spot” that balances engine endurance and raw speed.

In this post we have:

  • Proposed an alternative log base-10 Warp scale that more realistically reflects the vastness of the Universe and makes it more navigable in human time frames
  • Developed Warp Power, Energy and Efficiency pseudo-equations by combining relativistic and classical mechanics which provides a robust mathematical underpinning of a universal Warp speed limit
  • Introduced the notion of engine endurance to restrict the distance Warp capable ships can travel at various Warp speeds before engine maintenance is required

STAR TREK and related marks are trademarks of CBS Studios Inc.

Bridge Partnership (Two Hands) Probability Analysis

Introduction

The previous Bridge post looked at various aspects of a single hand including suit distributions, High Card Points and honour holdings. This post will look at similar aspects but will focus on the combined holdings of two hands. We will only consider the situation immediately after the deal and before any cards are played.

Although there are four players (and four hands) in a Bridge deal, they form two partnerships comprising of the North-South and East-West hands. Therefore the combined holdings of the 26 cards held between these hands is a key element of the game.

A quick reminder of some terminology:

4-2-3-4 Specific suit distribution (i.e. 4♠︎, 2♥︎, 3♦︎ and 4♣︎).
4 4 3 2 Generic suit distribution (i.e. any hand with two 4-card, one 3-card and a 2-card suit).
C(n,k) Combination function (see comb below). Returns the number of ways to select ‘k’ items from a collection of ‘n’ objects where order is unimportant.

The same utility functions used in the previous post are used here. They are repeated below for convenience.

(defn fact
  "Return the factorial of integer n >= 0"
  [n]
  (apply *' (range 1 (inc n))))

(defn comb
  "Return the combination - ways of selecting k from n (k<=n)"
  [n k]
  (/ (fact n) (*' (fact k) (fact (- n k)))))

Suit Distribution of Two Hands

We can ask equivalent questions about the probability of specific suit distributions between two hands as we did for one in the previous post.

How many partnership combinations are there?

There are two ways to view this. One is to only consider the combined 26 card holding without regard to the holdings of the individual hands, in this case the answer is simply the number of ways you can select 26 cards from 52:

C(52,26) = 495,918,532,948,104

The other way to view it, is that the individual holdings of each hand are important. In this case, the answer is the number of ways 13 cards can be selected from 52, multiplied by the number of ways 13 cards can be selected from the remaining 39 cards:

C(52,13)C(39,13) = 5,157,850,293,780,050,462,400

Needless to say both numbers are sufficiently large that you and your partner will not be holding the same cards very often :). However, these values are important as they form the denominators for some of the probability equations developed later.

Suit Distribution of Combined Hands (26-cards analysis)

Taking the first view–combined 26-cards–we can answer questions like:

What is the probability of suit distributions of two combined hands?

As we did with one hand, we can look at the probability of the combined distribution of two hands by iterating over all possible distributions and calculating the probability based on 26 cards instead of 13 cards.

This produces the specific distribution with each suit treated uniquely. For example, there will be separate results for 8-6-6-6, 6-8-6-6, 6-6-8-6 and 6-6-6-8 (i.e. where the 8 cards are Spades, Hearts, Diamonds and Clubs respectively).

The Clojure code is shown below:

"Probability of specific suit distribution for
two combined hands (ie 26 cards)"
(def distr-combined-specific
  (let [c5226 (comb 52 26)]
    (for [s (range 14)
          h (range 14)
          d (range 14)
          c (range 14)
          :when (= 26 (+ s h d c))]
      (let [cs (* (comb 13 s)
                  (comb 13 h)
                  (comb 13 d)
                  (comb 13 c))
            pp (/ (* 100.0 cs) c5226)]
        [[s h d c] pp]))))

(sort-by last > distr-combined-specific)
;=> ([[6 6 7 7] 1.7484724571169408]
;    [[6 7 6 7] 1.7484724571169408]
;    [[6 7 7 6] 1.7484724571169408]
;    [[7 6 6 7] 1.7484724571169408]
;    [[7 6 7 6] 1.7484724571169408]
;    [[7 7 6 6] 1.7484724571169408]
;    [[5 7 7 7] 1.3113543428377057]
;    [[6 6 6 8] 1.3113543428377057]
;    ...

(apply + (map last distr-combined-specific))
;=> 100.0

(count distr-combined-specific)
;=> 1834

From these results, we can see there are 1834 specific combined distributions whose probabilities total to 100.0% (as expected). The most common specific distribution (or shape) has two 7-cards suits and two 6-cards suits (e.g. 7-7-6-6, 7-6-7-6, etc).

The generic distribution combines specific distributions of the same general shape, for example, the four specific distributions mentioned earlier would be grouped under the single generic distribution 8 6 6 6.

The following code performs this grouping and also counts the number of specific distributions associated with each generic distribution.

"Probability of generic suit distribution for two combined hands"
(def distr-combined-generic
  (reduce
    (fn [acc [d p]]
      (let [g-distr (vec (sort > d))
            acc (update-in acc [g-distr :prob] (fnil + 0.0) p)
            acc (update-in acc [g-distr :cnt] (fnil inc 0))]
        acc))
    (sorted-map)
    distr-combined-specific))

;=> {[7 7 6 6] {:prob 10.490834742701646, :cnt 6},
;    [7 7 7 5] {:prob 5.245417371350823, :cnt 4},
;    [8 6 6 6] {:prob 5.245417371350823, :cnt 4},
;    [8 7 6 5] {:prob 23.604378171078707, :cnt 24},
;    [8 7 7 4] {:prob 6.556771714188528, :cnt 12},
;    [8 8 5 5] {:prob 3.3193656803079423, :cnt 6},
;    [8 8 6 4] {:prob 4.917578785641396, :cnt 12},
;    ...

(apply + (map :prob (vals distr-combined-generic)))
;=> 99.99999999999996

(count distr-combined-generic)
;=> 104

As expected, the number of generic distributions is significantly less at 104. The most common one by far is 8 7 6 5 (23.6%). Note that this is different from the most common specific distribution because there are many more (24) specific distributions that make this generic distribution than there are for 7 7 6 6 which has only six.

The full results are shown in Table 1 below and are downloadable here as a csv file.

The “Specific count” column is the number for specific distributions that make up each generic distribution. So the columns are related as follows:

“Specific count” x “Specific Prob (%)” = “Generic Prob (%)”
Generic Distribution Specific Count Specific Prob (%) Generic Prob (%)
7 7 6 6 6 1.7485 10.4908
7 7 7 5 4 1.3114 5.2454
8 6 6 6 4 1.3114 5.2454
8 7 6 5 24 0.9835 23.6044
8 7 7 4 12 0.5464 6.5568
8 8 5 5 6 0.5532 3.3194
8 8 6 4 12 0.4098 4.9176
8 8 7 3 12 0.1639 1.9670
8 8 8 2 4 0.0335 0.1341
9 6 6 5 12 0.5464 6.5568
9 7 5 5 12 0.4098 4.9176
9 7 6 4 24 0.3036 7.2853
9 7 7 3 12 0.1214 1.4571
9 8 5 4 24 0.1707 4.0980
9 8 6 3 24 0.0911 2.1856
9 8 7 2 24 0.0248 0.5961
9 8 8 1 12 0.0031 0.0373
9 9 4 4 6 0.0527 0.3162
9 9 5 3 12 0.0379 0.4553
9 9 6 2 12 0.0138 0.1656
9 9 7 1 12 0.0023 0.0276
9 9 8 0 12 0.0001 0.0016
10 6 5 5 12 0.1639 1.9670
10 6 6 4 12 0.1214 1.4571
10 7 5 4 24 0.0911 2.1856
10 7 6 3 24 0.0486 1.1656
10 7 7 2 12 0.0132 0.1590
10 8 4 4 12 0.0379 0.4553
10 8 5 3 24 0.0273 0.6557
10 8 6 2 24 0.0099 0.2384
10 8 7 1 24 0.0017 0.0397
10 8 8 0 12 0.0001 0.0011
10 9 4 3 24 0.0084 0.2024
10 9 5 2 24 0.0041 0.0993
10 9 6 1 24 0.0009 0.0221
10 9 7 0 24 0.0001 0.0017
10 10 3 3 6 0.0013 0.0081
10 10 4 2 12 0.0009 0.0110
10 10 5 1 12 0.0003 0.0033
10 10 6 0 12 0.0000 0.0003
11 5 5 5 4 0.0335 0.1341
11 6 5 4 24 0.0248 0.5961
11 6 6 3 12 0.0132 0.1590
11 7 4 4 12 0.0138 0.1656
11 7 5 3 24 0.0099 0.2384
11 7 6 2 24 0.0036 0.0867
11 7 7 1 12 0.0006 0.0072
11 8 4 3 24 0.0041 0.0993
11 8 5 2 24 0.0020 0.0488
11 8 6 1 24 0.0005 0.0108
11 8 7 0 24 0.0000 0.0008
11 9 3 3 12 0.0009 0.0110
Generic Distribution Specific Count Specific Prob (%) Generic Prob (%)
11 9 4 2 24 0.0006 0.0151
11 9 5 1 24 0.0002 0.0045
11 9 6 0 24 0.0000 0.0005
11 10 3 2 24 0.0001 0.0024
11 10 4 1 24 0.0000 0.0010
11 10 5 0 24 0.0000 0.0001
11 11 2 2 6 0.0000 0.0000
11 11 3 1 12 0.0000 0.0001
11 11 4 0 12 0.0000 0.0000
12 5 5 4 12 0.0031 0.0373
12 6 4 4 12 0.0023 0.0276
12 6 5 3 24 0.0017 0.0397
12 6 6 2 12 0.0006 0.0072
12 7 4 3 24 0.0009 0.0221
12 7 5 2 24 0.0005 0.0108
12 7 6 1 24 0.0001 0.0024
12 7 7 0 12 0.0000 0.0001
12 8 3 3 12 0.0003 0.0033
12 8 4 2 24 0.0002 0.0045
12 8 5 1 24 0.0001 0.0014
12 8 6 0 24 0.0000 0.0001
12 9 3 2 24 0.0000 0.0010
12 9 4 1 24 0.0000 0.0004
12 9 5 0 24 0.0000 0.0001
12 10 2 2 12 0.0000 0.0001
12 10 3 1 24 0.0000 0.0001
12 10 4 0 24 0.0000 0.0000
12 11 2 1 24 0.0000 0.0000
12 11 3 0 24 0.0000 0.0000
12 12 1 1 6 0.0000 0.0000
12 12 2 0 12 0.0000 0.0000
13 5 4 4 12 0.0001 0.0016
13 5 5 3 12 0.0001 0.0011
13 6 4 3 24 0.0001 0.0017
13 6 5 2 24 0.0000 0.0008
13 6 6 1 12 0.0000 0.0001
13 7 3 3 12 0.0000 0.0003
13 7 4 2 24 0.0000 0.0005
13 7 5 1 24 0.0000 0.0001
13 7 6 0 24 0.0000 0.0000
13 8 3 2 24 0.0000 0.0001
13 8 4 1 24 0.0000 0.0001
13 8 5 0 24 0.0000 0.0000
13 9 2 2 12 0.0000 0.0000
13 9 3 1 24 0.0000 0.0000
13 9 4 0 24 0.0000 0.0000
13 10 2 1 24 0.0000 0.0000
13 10 3 0 24 0.0000 0.0000
13 11 1 1 12 0.0000 0.0000
13 11 2 0 24 0.0000 0.0000
13 12 1 0 24 0.0000 0.0000
13 13 0 0 6 0.0000 0.0000

Table 1 Percentage generic probability of combined hands

One immediate observation is that most distributions have at least one suit with eight or more cards. Only the first two distributions (7766 and 7775) don’t and these make up just 15.736% of all distributions.

In Bridge, the combined number of cards (or “fit”) in a suit (particularly a major suit) is important because it often determines whether the two hands should play in a suit contract or a No Trumps contract. With a combined suit holding of eight or more cards, the odds favour a suit contract over a No Trump contract. A fit in a second suit further favours a suit contract and often means a higher contract (or more tricks) is possible with less than the expected number of HCP. The hands are said to have a “good” fit.

We can summarise the results from Table 1 to show the likelihood of various primary and secondary suit fits as shown in Table 2 below.

P/S 5 6 7 8 9 10 11 12 13 Total N-or-less N-or-more
7 15.736 15.736 15.736 100.000
8 5.245 30.161 10.338 45.745 61.481 84.264
9 6.557 13.660 6.917 0.966 28.100 89.581 38.519
10 3.424 3.510 1.390 0.325 0.023 8.673 98.254 10.419
11 0.134 0.755 0.498 0.160 0.031 0.004 0.000 1.582 99.835 1.746
12 0.037 0.075 0.035 0.009 0.001 0.000 0.000 0.000 0.158 99.993 0.165
13 0.003 0.003 0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.007 100.000 0.007

Table 2 Percentage probability of primary (P) and secondary (S) suit ‘fits’ in combined hands

While this view of the combined 26-cards provides some useful insights it does not distinguish between the holdings in each hand separately. So an 8-card fit, for example, could be made up of any combination of 0-8, 1-7, 2-6, 3-5, 4-4, 5-3, 6-2, 7-1 or 8-0 between the two hands. In the next section we look at how the two hands separately contribute to the combined result.

Suit Distribution of Two Separate Hands (2 x 13-cards)

Using the second view–the distribution between two separate hands–provides a more comprehensive result. It captures the detail of the distribution associated with each hand but generates significantly more data that requires additional processing to exact useful information.

As we did previously, let’s consider an example, say one hand has the specific distribution 3-5-3-2 (i.e. 3♠︎, 5♥︎, 3♦︎ and 2♣︎) and the other has 2-3-4-4 (i.e. 2♠︎, 3♥︎, 4♦︎ and 4♣︎). We know the number of ways to select the first hand from the total ways for all hands is:

Ways to select: C(13,3)C(13,5)C(13,3)C(13,2)
Total ways: C(52,13)

The second hand must be selected from the remaining cards which means only 10 of the remaining Spades, 8 of the remaining Hearts, 10 of the remaining Diamonds and 11 of the remaining Clubs, and the total ways it can be selected must come for the remaining 39 cards as follows:

Ways to select: C(10,2)C(8,3)C(10,4)C(11,4)
Total ways: C(39,13)

The probability of these two specific distributions is the product of the ‘ways-to-select’ divided by the product of the ‘total-ways’:

C(13,3)C(13,5)C(13,3)C(13,2)C(10,2)C(8,3)C(10,4)C(11,4)
——————————————————————— = 0.02780163%
C(52,13)C(39,13)

Importantly, if we took the second hand first, and the first hand second, the numerator would be quite different. The new calculation would be:

C(13,2)C(13,3)C(13,4)C(13,4)C(11,3)C(10,5)C(9,3)C(9,2)
——————————————————————— = 0.02780163%
C(52,13)C(39,13)

Somewhat amazingly, although what we would expect intuitively, the result turns out to be the same. The mathematical magic behind this is that the factors for each suit are interchangeable:

C(13,a)C(13-a,b) = 13!/a!(13-a)! x (13-a)!/b!(13-a-b)!
= 13!/a!b!(13-a-b)!
= 13!/b!(13-b)! x (13-b)!/a!(13-b-a)!
= C(13,b)C(13-b,a)

This explains why the result is independent of the order of the hands.

This example can be easily generalised for two hands with specific distributions s1-h1-d1-c1 and s2-h2-d2-c2 as:

C(13,s1)C(13,h1)C(13,d1)C(13,c1)C(13-s1,s2)C(13-h1,h2)C(13-d1,d2)C(13-c1,c2)
———————————————————————
C(52,13)C(39,13)

The following Clojure code calculates the percentage probability of all possible specific two hand distributions. As each of the eight possible suit counts can range from 0 to 13 there are potentially 148 = 1,475,789,056 iterations. To reduce this somewhat epic number, the second suit upper range is limited to 13 less the first suit, which brings it down to 121,550,625 iterations. It is still a sizeable bit of number crunching which takes about 15 seconds on my MacBook Pro.

(def distr-two-hands-specific
  (let [c5213c3913 (* (comb 52 13) (comb 39 13))]
    (for [s1 (range 14) s2 (range (- 14 s1))
          h1 (range 14) h2 (range (- 14 h1))
          d1 (range 14) d2 (range (- 14 d1))
          c1 (range 14) c2 (range (- 14 c1))
          :when (and
                  (= 13 (+ s1 h1 d1 c1))
                  (= 13 (+ s2 h2 d2 c2)))]
      (let [cs (* (comb 13 s1) (comb (- 13 s1) s2)
                  (comb 13 h1) (comb (- 13 h1) h2)
                  (comb 13 d1) (comb (- 13 d1) d2)
                  (comb 13 c1) (comb (- 13 c1) c2))
            pp (/ (* 100.0 cs) c5213c3913)]
        [[s1 h1 d1 c1] [s2 h2 d2 c2] pp]))))

(sort-by last > distr-two-hands-specific)
;=> ([[3 3 3 4] [3 3 4 3] 0.08237519989109292]
;    [[3 3 4 3] [3 3 3 4] 0.08237519989109292]
;    [[3 3 3 4] [3 4 3 3] 0.08237519989109292]
;    [[3 3 4 3] [3 4 3 3] 0.08237519989109292]
;    [[3 4 3 3] [3 3 3 4] 0.08237519989109292]
;    [[3 4 3 3] [3 3 4 3] 0.08237519989109292]
;    [[3 3 3 4] [4 3 3 3] 0.08237519989109292]
;    [[3 3 4 3] [4 3 3 3] 0.08237519989109292]
;    [[3 4 3 3] [4 3 3 3] 0.08237519989109292]
;    [[4 3 3 3] [3 3 3 4] 0.08237519989109292]
;    [[4 3 3 3] [3 3 4 3] 0.08237519989109292]
;    [[4 3 3 3] [3 4 3 3] 0.08237519989109292]
;    [[3 3 3 4] [3 3 3 4] 0.07060731419236536]
;    [[3 3 4 3] [3 3 4 3] 0.07060731419236536]
;    [[3 4 3 3] [3 4 3 3] 0.07060731419236536]
;    [[4 3 3 3] [4 3 3 3] 0.07060731419236536]
;    [[2 3 4 4] [4 3 3 3] 0.0617813999183197]
;    [[2 4 3 4] [4 3 3 3] 0.0617813999183197]
;    [[2 4 4 3] [4 3 3 3] 0.0617813999183197]
;    [[3 2 4 4] [3 4 3 3] 0.0617813999183197]
;    ...)

(apply + (map last distr-two-hands-specific))
;=> 99.99999999998808

(count distr-two-hands-specific)
;=> 239344

The results show there are 239,344 specific two hand distributions whose total probability sums to 100% (as expected). This is a lot of data to digest but it allows us to answer a broad range of distributional questions like:

What is the probability of two hands having exactly the same shape?

The following code uses the result calculated above to sum the probabilities of each case where the two distributions are identical.

"Probability of identical distributions in each hand"
(reduce
  (fn [acc [d1 d2 p]]
    (if (= d1 d2)
      (update acc (vec (sort > d1)) (fnil + 0.0) p)
      acc))
  (sorted-map)
  distr-two-hands-specific)

;=> {[4 3 3 3] 0.28242925676946146,
;    [4 4 3 2] 0.27801629963243857,
;    [4 4 4 1] 0.008845973170123048,
;    [5 3 3 2] 0.08472877703083843,
;    [5 4 2 2] 0.027801629963243858,
;    [5 4 3 1] 0.016175493796796423,
;    ...}

The full result is shown in Table 3 below.

Distr. Absolute Prob (%) Relative Prob (%)
4333 0.28243 40.25368
4432 0.27802 39.62472
4441 0.00885 1.26079
5332 0.08473 12.07611
5422 0.02780 3.96247
5431 0.01618 2.30544
5440 0.00014 0.01940
5521 0.00081 0.11527
5530 0.00004 0.00591
6322 0.00177 0.25159
6331 0.00051 0.07319
6421 0.00034 0.04803
6430 0.00002 0.00246
6511 0.00000 0.00070
6520 0.00000 0.00025
6610 0.00000 0.00000
Total 0.70162 100.00

Table 3 Percentage probability of two hands with exactly the same shape

These hands can cause problems, particularly with a major suit fit, as they are often played in a suit contact where a No Trumps contract is frequently better because of the lack of ruffing opportunities.

The following sections take the above specific two hand distribution results and interpret them for:

  • Single suit
  • Two suits
  • Full distribution (all four suits)

Single Suit Analysis

This section focuses on the details of any given single suit to answer questions such as:

How is any one suit distributed between the two hands?

If we pick one suit, Spades say, what is the probability of holding X cards in one hand and Y cards in the other. We can process the results above with the following code to build a table of X-Y ‘fit’ probabilities.

"Probability of holding a particular X-Y fit in any one suit"
(def one-suit-fit
  (reduce
    (fn [acc [d1 d2 p]]
      (update acc [(d1 0) (d2 0)] (fnil + 0.0) p))
    (sorted-map)
    distr-two-hands-specific))

;=> {[0 0] 0.0016378547895184352,
;    [0 1] 0.019771247102043903,
;    [0 2] 0.09490198608981093,
;    [0 3] 0.23923208993472986,
;    [0 4] 0.3518118969628408,
;   ...

(apply + (map val one-suit-fit))
;=> 100.0

The full results are in Table 4 below.

X/Y 0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 0.0016 0.0198 0.0949 0.2392 0.3518 0.3166 0.1778 0.0622 0.0133 0.0017 0.0001 0.0000 0.0000 0.0000
1 0.0198 0.2056 0.8482 1.8294 2.2868 1.7331 0.8088 0.2311 0.0394 0.0038 0.0002 0.0000 0.0000
2 0.0949 0.8482 2.9936 5.4883 5.7771 3.6396 1.3865 0.3151 0.0411 0.0029 0.0001 0.0000
3 0.2392 1.8294 5.4883 8.4731 7.4140 3.8129 1.1554 0.2009 0.0188 0.0008 0.0000
4 0.3518 2.2868 5.7771 7.4140 5.2957 2.1664 0.5024 0.0628 0.0038 0.0001
5 0.3166 1.7331 3.6396 3.8129 2.1664 0.6782 0.1130 0.0090 0.0003
6 0.1778 0.8088 1.3865 1.1554 0.5024 0.1130 0.0121 0.0005
7 0.0622 0.2311 0.3151 0.2009 0.0628 0.0090 0.0005
8 0.0133 0.0394 0.0411 0.0188 0.0038 0.0003
9 0.0017 0.0038 0.0029 0.0008 0.0001
10 0.0001 0.0002 0.0001 0.0000
11 0.0000 0.0000 0.0000
12 0.0000 0.0000
13 0.0000

Table 4 Percentage Probability of X cards in one hand and Y cards in the other for a given suit

We can recast Table 4 data in various ways such as:

Given you have X cards in a suit what is the probability partner holds Y cards in the same suit?

In Table 5 below, each row in Table 4 has been ‘normalised’ by dividing by the row total so each row now sums to 100%. The number of cards held by you (X) is shown in the first column. The number held by partner (Y) is shown in the top row. The corresponding value is P(Y|X) or the probability of partner holding Y cards if you hold X card in a particular suit.

X/Y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Total
0 0.13 1.55 7.42 18.70 27.50 24.75 13.90 4.86 1.04 0.13 0.01 0.00 0.00 0.00 100.00
1 0.25 2.57 10.59 22.85 28.56 21.65 10.10 2.89 0.49 0.05 0.00 0.00 0.00 100.00
2 0.46 4.12 14.54 26.66 28.06 17.68 6.73 1.53 0.20 0.01 0.00 0.00 100.00
3 0.84 6.39 19.17 29.59 25.89 13.32 4.04 0.70 0.07 0.00 0.00 100.00
4 1.47 9.58 24.21 31.07 22.19 9.08 2.11 0.26 0.02 0.00 100.00
5 2.54 13.90 29.19 30.58 17.37 5.44 0.91 0.07 0.00 100.00
6 4.28 19.46 33.36 27.80 12.09 2.72 0.29 0.01 100.00
7 7.06 26.21 35.74 22.79 7.12 1.03 0.05 100.00
8 11.42 33.76 35.22 16.14 3.23 0.22 100.00
9 18.18 41.09 30.82 9.04 0.87 100.00
10 28.45 46.23 22.19 3.13 100.00
11 43.86 45.61 10.53 100.00
12 66.67 33.33 100.00
13 100.00 100.00

Table 5 Holding X cards in a suit (left column) the percentage probability of partner holding Y cards (top row) in the same suit

So if you hold four Spades there is a 22.19% chance that partner will also hold exactly 4 Spades, and a 9.08% chance of holding exactly five Spades. By accumulating these results we can find the likelihood of a fit of N or more cards.

Holding X cards in a suit what is the probability of a fit of N or more cards in that suit?

Table 6 is just the same data as Table 5 only showing the accumulated total from left to right.

0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 12+ 13+
0 100.00 99.87 98.33 90.91 72.20 44.70 19.94 6.05 1.18 0.14 0.01 0.00 0.00 0.00
1 100.00 99.75 97.18 86.59 63.74 35.18 13.53 3.43 0.54 0.05 0.00 0.00 0.00
2 100.00 99.54 95.42 80.88 54.22 26.16 8.48 1.74 0.21 0.01 0.00 0.00
3 100.00 99.16 92.78 73.61 44.02 18.12 4.81 0.77 0.07 0.00 0.00
4 100.00 98.53 88.94 64.73 33.66 11.46 2.38 0.28 0.02 0.00
5 100.00 97.46 83.56 54.37 23.79 6.42 0.98 0.07 0.00
6 100.00 95.72 76.26 42.91 15.11 3.02 0.30 0.01
7 100.00 92.94 66.73 30.99 8.20 1.08 0.05
8 100.00 88.58 54.82 19.60 3.45 0.22
9 100.00 81.82 40.73 9.91 0.87
10 100.00 71.55 25.32 3.13
11 100.00 56.14 10.53
12 100.00 33.33
13 100.00

Table 6 Holding X cards in a suit (left column) the percentage probability of an N+ card fit (top row) with partner

As eight or more cards in a suit is the standard for a trump fit we have highlighted the 8+ column. When holding four cards in a suit there is a 33.66% chance that partner will have four or more. With five cards, however, this chance increases to 54.37%. This, in part, explains the attraction of 5-card major openings as it is significantly more likely that an eight card fit exists.

Given the partnership holds a combined number of cards in a suit, what is the probability of the various divisions of those cards between the two hands?

This is usually asked when considering the likely holdings of the opponents. For example, we have eight cards in Hearts (say), what is the probability that the five remaining Hearts held by the opponents are divided 3-2, 4-1 or 5-0. Because the opponents’ hands also form a partnership of 26 cards, the same probabilities apply.

There are alternative ways to calculate these divisions which we will examine in a later post on suit holdings. They are included here for completeness and to show that the specific suit distribution data captures all the salient information about the distribution between two hands.

# X-Y Prob (%)
0 0-0 100.00
1 0-1 50.00
1-0 50.00
2 0-2 24.00
1-1 52.00
2-0 24.00
3 0-3 11.00
1-2 39.00
2-1 39.00
3-0 11.00
4 0-4 4.78
1-3 24.87
2-2 40.70
3-1 24.87
4-0 4.78
5 0-5 1.96
1-4 14.13
2-3 33.91
3-2 33.91
4-1 14.13
5-0 1.96
6 0-6 0.75
1-5 7.27
2-4 24.22
3-3 35.53
4-2 24.22
5-1 7.27
6-0 0.75
# X-Y Prob (%)
7 0-7 0.26
1-6 3.39
2-5 15.26
3-4 31.09
4-3 31.09
5-2 15.26
6-1 3.39
7-0 0.26
8 0-8 0.08
1-7 1.43
2-6 8.57
3-5 23.56
4-4 32.72
5-3 23.56
6-2 8.57
7-1 1.43
8-0 0.08
9 0-9 0.02
1-8 0.54
2-7 4.28
3-6 15.71
4-5 29.45
5-4 29.45
6-3 15.71
7-2 4.28
8-1 0.54
9-0 0.02
# X-Y Prob (%)
10 0-10 0.01
1-9 0.17
2-8 1.89
3-7 9.24
4-6 23.10
5-5 31.18
6-4 23.10
7-3 9.24
8-2 1.89
9-1 0.17
10-0 0.01
11 0-11 0.00
1-10 0.05
2-9 0.72
3-8 4.76
4-7 15.88
5-6 28.58
6-5 28.58
7-4 15.88
8-3 4.76
9-2 0.72
10-1 0.05
11-0 0.00
# X-Y Prob (%)
12 0-12 0.00
1-11 0.01
2-10 0.23
3-9 2.12
4-8 9.53
5-7 22.87
6-6 30.49
7-5 22.87
8-4 9.53
9-3 2.12
10-2 0.23
11-1 0.01
12-0 0.00
13 0-13 0.00
1-12 0.00
2-11 0.06
3-10 0.79
4-9 4.92
5-8 15.93
6-7 28.31
7-6 28.31
8-5 15.93
9-4 4.92
10-3 0.79
11-2 0.06
12-1 0.00
13-0 0.00

Table 7 Percentage probability of a suit dividing between two hands

So to answer the query above, the opponents five outstanding Hearts will split as follows:

  • 3-2: 67.82%
  • 4-1: 28.26%
  • 5-0: 3.92%

Two Suit Analysis

This section considers the distribution of any two specific suits.

What is the probability of a fit with partner in my two longest 4+ card suits?

This is of some interest when considering using bids that show two suited hands.

The code below uses several of Clojure’s more interesting features including the threading macro (->>), function argument destructuring and reduce-style iteration.

The specific distribution data structure is passed through several steps (functions) to transform it into the desired result. This style of programming is common in functional languages. The various data structure formats between steps are shown as comments.

(def two-suit-fits
  "What is the probability of a fit with partner in
  my two longest suits with 4 or more cards?"
  (->> distr-two-hands-specific
       ;
       ; ([[s1, h1 d1, c1] [s2, h2, d2, c2] prob], ...)
       ;
       (reduce
         (fn [{:keys [fits tots] :as acc} [d1 d2 prob]]
           (let [ds (sort #(compare %2 %1) (map vector d1 d2))
                 p1 (first ds)
                 p2 (second ds)
                 ps [(p1 0) (p2 0)]
                 max-fit (max (apply + p1) (apply + p2))]
             (if (< (first p2) 4)
               acc
               {:fits (update fits [ps max-fit] (fnil + 0.0) prob)
                :tots (update tots ps (fnil + 0.0) prob)})))
         {:fits {} :tots {}})
       ;
       ; {:fits {[[x1 x2] fit] prob, ...}
       ;  :tots {[[x1 x2] tot-prob], ...}}
       ;
       ((fn [{:keys [fits tots]}]
          (sort (for [[[ps fit] prob] fits]
                  [[ps fit] (* 100.0 (/ prob (tots ps)))]))))
       ;
       ; ([[[x1 x2] fit] relative-%prob], ...)
       ;
       (reduce
         (fn [{:keys [res lastps lastprob rtot]} [[ps fit] prob]]
           (if (= ps lastps)
             {:res (assoc res [ps fit] [prob (- rtot lastprob)])
              :lastps ps
              :lastprob prob
              :rtot (- rtot lastprob)}
             {:res (assoc res [ps fit] [prob 100.0])
              :lastps ps
              :lastprob prob
              :rtot 100.0}))
         {:res (sorted-map) :lastps [] :lastprob 0.0 :rtot 100.0})
       ;
       ; {:res {[[x1 x2] fit] [relative-%prob, reverse-accum-%prob], ...}
       ;  :lastps [x1 x2]
       ;  :lastprob <float>
       ;  :rtot <float>
       ;
       :res))

;=> {[[4 4] 4] [0.0021997634521034428 100.0],
;    [[4 4] 5] [0.3661172961162857 99.9978002365479],
;    [[4 4] 6] [6.949115984745576 99.63168294043162],
;    [[4 4] 7] [29.93204349541178 92.68256695568604],
;    [[4 4] 8] [38.821054462217894 62.750523460274266],
;    [[4 4] 9] [18.871677012414445 23.92946899805637],
;    [[4 4] 10] [4.465132976302236 5.057791985641927],
;    [[4 4] 11] [0.5584368534484566 0.5926590093396911],
;    [[4 4] 12] [0.033506211206907395 0.03422215589123445],
;    [[4 4] 13] [7.159446839082796E-4 7.159446843270564E-4],
;    [[5 4] 5] [0.07387275139205572 100.0],
;    ...

The results are show in Table 8 below. The numbers in brackets represent the
reverse accumulated totals so they are the probability of an N+ card fit in at least one of the two suits.

Suits 4 5 6 7 8 9 10 11 12 13
4-4 0.00 (100.00) 0.37 (100.00) 6.95 (99.63) 29.93 (92.68) 38.82 (62.75) 18.87 (23.93) 4.47 (5.06) 0.56 (0.59) 0.03 (0.03) 0.00 (0.00)
5-4 0.07 (100.00) 3.14 (99.93) 21.91 (96.79) 40.18 (74.87) 25.78 (34.69) 7.63 (8.91) 1.18 (1.27) 0.09 (0.09) 0.00 (0.00)
5-5 0.01 (100.00) 1.33 (99.99) 15.13 (98.65) 38.99 (83.52) 31.77 (44.54) 10.80 (12.76) 1.81 (1.96) 0.15 (0.15) 0.00 (0.00)
6-4 0.76 (100.00) 11.81 (99.24) 35.84 (87.42) 34.16 (51.58) 14.12 (17.42) 2.98 (3.30) 0.31 (0.32) 0.01 (0.01)
6-5 0.30 (100.00) 7.55 (99.70) 32.48 (92.16) 38.47 (59.68) 17.21 (21.21) 3.62 (4.00) 0.36 (0.38) 0.01 (0.01)
6-6 0.06 (100.00) 3.59 (99.94) 25.23 (96.35) 41.97 (71.12) 23.13 (29.16) 5.43 (6.03) 0.58 (0.60) 0.02 (0.02)
7-4 3.46 (100.00) 24.06 (96.54) 39.37 (72.47) 24.63 (33.10) 7.38 (8.48) 1.04 (1.09) 0.05 (0.05)
7-5 2.11 (100.00) 20.48 (97.89) 40.97 (77.40) 27.27 (36.43) 8.02 (9.17) 1.10 (1.15) 0.05 (0.05)
7-6 0.96 (100.00) 14.95 (99.04) 40.88 (84.09) 32.06 (43.22) 9.78 (11.16) 1.32 (1.38) 0.06 (0.06)
8-4 9.17 (100.00) 34.39 (90.83) 36.58 (56.44) 16.40 (19.86) 3.24 (3.47) 0.22 (0.22)
8-5 7.40 (100.00) 33.75 (92.60) 38.33 (58.84) 16.99 (20.52) 3.30 (3.53) 0.23 (0.23)
9-4 17.39 (100.00) 41.65 (82.61) 31.04 (40.96) 9.06 (9.93) 0.87 (0.87)

Table 8 Percentage probability of a fit with partner in your two longest 4+ card suits (N+ accumulated total in brackets)

Table 8 shows, for example, that with two 4-card suits there is almost a 63% chance that you will have an 8-card or greater fit with partner in one of those suits. This rises to 83.5% with two 5 cards suits.

Holding a hand with a 6-card and 4-card suit is it worth bidding the 4-card suit?

When holding a hand with 6-4 in the longest suits, there is often a debate about whether it is better to re-bid the 6-card suit (to show 6 cards), eschewing the 4-card suit, or whether it is better to introduce the 4-card suit at the cost of concealing the 6th card of the longer suit. Of course sometimes it is possible to show both but here we consider the case where it is not.

Assume we conceal the 4-card suits and show the 6-card suit. Table 6 above shows that we can expect to find an 8+ card fit in that suit 76.26% of the time. On the other hand if we show the 4-card suit which means we have shown 5-4 in two suits, Table 8 shows there is a 74.87% chance that we will have an 8+ card fit in at least one of the two suits.

This suggests that it is marginally better to stick with the 6-card suit. This is clearer when the 6-card suit is a major suit. However, when the 6-card suit is a minor and the 4-card suit is major there is a case to reveal the 4-card suit, especially with game values, as it is more likely to lead to a game contract.

Full Distribution Analysis

This section considers the full distribution of each hand.

What is partner’s most likely distribution given my distribution?

We know from the earlier post that there are 560 specific and 39 generic suit distributions for a single hand. So simplistically there are up to 39 x 560 = 21,840 ways to consider the distribution options for two hands. Clearly some are invalid. The function below returns the most likely distribution of partner’s hand and its probability given a particular distribution in your hand.

(defn partner-distr-prob
  "Return a list of partner's most likely suit distribution and
  their percentage probabilities given your distribution.
  Limit the response to 'n' distributions."
  [sd d n]
  (let [dall (filter #(= d (first %)) sd)
        totp (apply + (map last dall))
        ds (sort-by
             (fn [[d1 d2 prob]] [prob d2])
             #(compare %2 %1)
             dall)]
    (for [[d1 d2 prob] (take n ds)]
      [d2 (* 100.0 (/ prob totp))])))

(partner-distr-prob distr-two-hands-specific [4 4 3 2] 10)
;=> ([[3 3 3 4] 3.44007589760525]
;   [[3 3 4 3] 3.010066410404594]
;   [[4 3 3 3] 2.580056923203937]
;   [[3 4 3 3] 2.580056923203937]
;   [[3 2 4 4] 2.580056923203937]
;   [[2 3 4 4] 2.580056923203937]
;   [[4 2 3 4] 2.211477362746232]
;   [[2 4 3 4] 2.211477362746232]
;   [[3 2 3 5] 2.06404553856315]
;   [[2 3 3 5] 2.06404553856315])

Table 9 below shows some results for a few of the more common distributions.

4-4-3-2
Distr. Prob (%)
3-3-3-4 3.440
3-3-4-3 3.010
4-3-3-3 2.580
3-4-3-3 2.580
3-2-4-4 2.580
2-3-4-4 2.580
4-2-3-4 2.211
2-4-3-4 2.211
3-2-3-5 2.064
2-3-3-5 2.064
4-3-2-4 1.935
4-2-4-3 1.935
3-4-2-4 1.935
2-4-4-3 1.935
3-3-2-5 1.806
3-2-5-3 1.548
2-3-5-3 1.548
2-2-4-5 1.548
4-3-4-2 1.505
3-4-4-2 1.505
5-3-3-2
Distr. Prob (%)
3-3-3-4 3.276
3-4-3-3 2.867
3-3-4-3 2.867
2-4-3-4 2.867
2-3-4-4 2.867
2-4-4-3 2.508
2-3-3-5 2.293
3-4-2-4 2.150
3-2-4-4 2.150
4-3-3-3 2.048
3-3-2-5 1.720
3-2-3-5 1.720
2-5-3-3 1.720
2-3-5-3 1.720
3-4-4-2 1.672
4-3-2-4 1.536
4-2-3-4 1.536
2-4-2-5 1.505
2-2-4-5 1.505
1-4-4-4 1.433
5-4-3-1
Distr. Prob (%)
3-3-3-4 3.440
2-3-4-4 3.010
2-3-3-5 2.752
3-3-4-3 2.676
3-2-4-4 2.580
2-4-3-4 2.580
3-2-3-5 2.359
3-4-3-3 2.293
3-3-2-5 2.064
2-2-4-5 2.064
2-4-4-3 2.007
3-4-2-4 1.935
4-3-3-3 1.911
4-2-3-4 1.843
4-3-2-4 1.613
2-3-5-3 1.605
2-4-2-5 1.548
2-2-5-4 1.548
4-2-4-3 1.433
3-2-5-3 1.376
6-4-2-1
Distr. Prob (%)
2-3-4-4 3.548
3-3-3-4 2.956
2-3-3-5 2.838
2-4-3-4 2.661
3-3-4-3 2.628
3-2-4-4 2.534
2-2-4-5 2.433
2-4-4-3 2.365
2-3-5-3 2.207
2-2-5-4 2.129
3-2-3-5 2.027
3-4-3-3 1.971
1-3-4-5 1.892
1-4-4-4 1.774
1-3-5-4 1.656
3-3-2-5 1.577
3-2-5-3 1.577
3-4-2-4 1.478
2-4-2-5 1.419
2-2-3-6 1.419

Table 9 Some percentage probabilities of partner’s suit distribution given your distribution

All of these results have been derived from the specific suit distribution data generated at the beginning of this section. Many other results are possible. The examples above are a guide to anyone wanting to calculate their own specific two-hand distribution probabilities.

HCP Distribution

Let’s move from suit distributions to High Card Points (HCP). Recall from the first blog that HCP are assigned to honour cards as follows: A=4, K=3, Q=2 and J=1. The hand HCP are the sum of the HCP of each honour card in the hand, and is a measure of the ‘strength’ (trick taking potential) of the hand.

Like suit distributions, we can take two views of HCP holdings, either from the combined 26 cards that make up the two hands or from two separate 13-card hands.

HCP Holdings of Combined Hands (26-cards analysis)

Starting with the combined 26-card view, the HCP distribution can be computed using a simple modification to the single hand code. For two combined hands, the number of non-honour cards (Xs) is determined by subtracting the number of honour cards from 26, instead of 13, and the denominator is C(52,26) instead of C(52,13). This leads to the following formula:

C(4,a)C(4,k)C(4,q)C(4,j)C(36,(26-(a+k+q+j))) / C(52,26)
where a,k,q,j = number of A,K,Q and J honour cards held respecively.

Iterating through all the possible honour combinations allows the formula above to be used to calculate the probability for each case. Aggregating these by HCP, we can calculate the total probability of each HCP value as shown in the following code:

"Return a map of HCP percentage probabilities for two hands combined"
(def hcp-prob-combined
  (let [c5226 (comb 52 26)
        plst (for [a (range 5)
                   k (range 5)
                   q (range 5)
                   j (range 5)]
               (let [hcp (+ (* 4 a) (* 3 k) (* 2 q) (* 1 j))
                     xs (- 26 (+ a k q j))
                     cs (* (comb 4 a)
                           (comb 4 k)
                           (comb 4 q)
                           (comb 4 j)
                           (comb 36 xs))
                     prob (/ cs c5226)]
                 [hcp prob]))]
    (reduce
      (fn [acc [h p]]
        (update acc h (fnil + 0.0) (* 100.0 p)))
      (sorted-map)
      plst)))

;=> {0 5.125576866202734E-5,
;    1 4.8459999462280393E-4,
;    2 0.001998974977819066,
;    3 0.0063867794163108005,
;    4 0.017985893298594256,
;    ...

(apply + (map val hcp-prob-combined))
;=> 100.0

The full results are shown in Table 10 below and can be downloaded here in csv format.

HCP Exactly-N Prob (%) N-or-less Prob (%) N-or-more Prob (%)
0 0.00 0.00 100.00
1 0.00 0.00 100.00
2 0.00 0.00 100.00
3 0.01 0.01 100.00
4 0.02 0.03 99.99
5 0.04 0.07 99.97
6 0.09 0.16 99.93
7 0.19 0.35 99.84
8 0.34 0.69 99.65
9 0.59 1.28 99.31
10 0.95 2.23 98.72
11 1.46 3.69 97.77
12 2.12 5.82 96.31
13 2.94 8.76 94.18
14 3.88 12.65 91.24
15 4.89 17.54 87.35
16 5.91 23.44 82.46
17 6.83 30.28 76.56
18 7.57 37.84 69.72
19 8.05 45.89 62.16
20 8.22 54.11 54.11
21 8.05 62.16 45.89
22 7.57 69.72 37.84
23 6.83 76.56 30.28
24 5.91 82.46 23.44
25 4.89 87.35 17.54
26 3.88 91.24 12.65
27 2.94 94.18 8.76
28 2.12 96.31 5.82
29 1.46 97.77 3.69
30 0.95 98.72 2.23
31 0.59 99.31 1.28
32 0.34 99.65 0.69
33 0.19 99.84 0.35
34 0.09 99.93 0.16
35 0.04 99.97 0.07
36 0.02 99.99 0.03
37 0.01 100.00 0.01
38 0.00 100.00 0.00
39 0.00 100.00 0.00
40 0.00 100.00 0.00
Total 100.00

Table 10 HCP percentage probability of two combined hands

Unlike the single hand HCP table this table is symmetric about 20 HCP. This makes sense as you and your partner will split the points with the opponents. Any points you have the opponents won’t have and vice versa.

If we take a combined holding of 25 HCP as a requirement for ‘game’ then you and your partner can expect to hold a game hand about 17.5% of the time. Of course other factors need to be considered such as distribution, vulnerability, secondary fits and the opponents’ skill level.

Many players will bid game, especially vulnerable, on lighter values which increases the likelihood to nearer 25%, or, 50% if you count the opponents. So it is likely game contracts will be played about half of the time at competitive tables.

HCP Holding of Two Separate Hands (2 x 13-cards)

Taking the view of two separate 13-card hands, we can modify the above approach by considering each hand separately. The probability equation becomes:

C(4,a1)C(4,k1)C(4,q1)C(4,j1)C(36,x1)C(4-a1,a2)C(4-k1,k2)C(4-q1,q2)C(4-j1,j2)C(36-x1,x2)
————————————————————————–
C(52,13)C(39,13)
where x1 = 13-(a1+k1+q1+j1) when >= 0
and x2 = 13-(a2+k2+q2+j2) when >= 0

Iterating over each possible honour combination, noting the second hand can only select from the remaining honour cards, and aggregating the probability results by HCP values provides the result. This operation is performed by the following code.

"Calculate a map of HCP percentage probabilities for two separate hands"
(def hcp-prob-separate
  (let [c5213c3913 (* (comb 52 13) (comb 39 13))
        plst (for [a1 (range 5) a2 (range (- 5 a1))
                   k1 (range 5) k2 (range (- 5 k1))
                   q1 (range 5) q2 (range (- 5 q1))
                   j1 (range 5) j2 (range (- 5 j1))
                   :let [x1 (- 13 (+ a1 k1 q1 j1))
                         x2 (- 13 (+ a2 k2 q2 j2))]
                   :when (and
                           (not (neg? x1))
                           (not (neg? x2)))]
               (let [hcp1 (+ (* 4 a1) (* 3 k1) (* 2 q1) (* 1 j1))
                     hcp2 (+ (* 4 a2) (* 3 k2) (* 2 q2) (* 1 j2))
                     cs (* (comb 4 a1)
                           (comb 4 k1)
                           (comb 4 q1)
                           (comb 4 j1)
                           (comb 36 x1)
                           (comb (- 4 a1) a2)
                           (comb (- 4 k1) k2)
                           (comb (- 4 q1) q2)
                           (comb (- 4 j1) j2)
                           (comb (- 36 x1) x2))
                     prob (/ cs c5213c3913)]
                 [[hcp1 hcp2] prob]))]
    (reduce
      (fn [acc [h p]]
        (update acc h (fnil + 0.0) (* 100.0 p)))
      (sorted-map)
      plst)))

;=> {[0 0] 5.125576866202734E-5,
;    [0 1] 2.4229999731140202E-4,
;    [0 2] 6.05749993278505E-4,
;    [0 3] 0.0014165230612051191,
;    ...
;    [12 10] 0.7965990398621553,
;    [12 11] 0.7293034947719456,
;    [12 12] 0.6226706646156763,
;    [12 13] 0.505656851922869,
;    ...

(apply + (map val hcp-prob-separate))
;=> 100.00000000000006

(count hcp-prob-separate)
;=> 849

A portion of the result is show in Table 11 below. The full results are here in csv format.

X/Y 8 9 10 11 12 13 14 15 16 17 18
0 0.0166 0.0214 0.0262 0.0300 0.0325 0.0336 0.0329 0.0305 0.0271 0.0228 0.0183
1 0.0394 0.0498 0.0597 0.0667 0.0712 0.0722 0.0696 0.0634 0.0556 0.0461 0.0364
2 0.0740 0.0917 0.1073 0.1183 0.1237 0.1233 0.1169 0.1047 0.0902 0.0737 0.0573
3 0.1458 0.1766 0.2042 0.2212 0.2265 0.2220 0.2073 0.1819 0.1538 0.1236 0.0942
4 0.2451 0.2934 0.3328 0.3548 0.3576 0.3441 0.3148 0.2711 0.2247 0.1763 0.1314
5 0.3555 0.4165 0.4637 0.4871 0.4811 0.4542 0.4085 0.3458 0.2803 0.2159 0.1580
6 0.4801 0.5516 0.6040 0.6231 0.6035 0.5593 0.4943 0.4094 0.3255 0.2457 0.1758
7 0.6259 0.7079 0.7610 0.7704 0.7325 0.6662 0.5754 0.4669 0.3629 0.2671 0.1860
8 0.7354 0.8158 0.8602 0.8556 0.7982 0.7098 0.6009 0.4772 0.3619 0.2597 0.1765
9 0.8158 0.8871 0.9184 0.8969 0.8180 0.7131 0.5912 0.4583 0.3392 0.2377 0.1570
10 0.8602 0.9184 0.9330 0.8910 0.7966 0.6797 0.5498 0.4157 0.3003 0.2044 0.1307
11 0.8556 0.8969 0.8910 0.8335 0.7293 0.6069 0.4784 0.3526 0.2472 0.1627 0.1009
12 0.7982 0.8180 0.7966 0.7293 0.6227 0.5057 0.3889 0.2786 0.1892 0.1211 0.0722
13 0.7098 0.7131 0.6797 0.6069 0.5057 0.4006 0.2992 0.2075 0.1370 0.0843 0.0482
14 0.6009 0.5912 0.5498 0.4784 0.3889 0.2992 0.2163 0.1456 0.0924 0.0545 0.0298
15 0.4772 0.4583 0.4157 0.3526 0.2786 0.2075 0.1456 0.0942 0.0574 0.0324 0.0169
16 0.3619 0.3392 0.3003 0.2472 0.1892 0.1370 0.0924 0.0574 0.0335 0.0180 0.0088
17 0.2597 0.2377 0.2044 0.1627 0.1211 0.0843 0.0545 0.0324 0.0180 0.0090 0.0041
18 0.1765 0.1570 0.1307 0.1009 0.0722 0.0482 0.0298 0.0169 0.0088 0.0041 0.0017
19 0.1126 0.0971 0.0785 0.0583 0.0401 0.0257 0.0151 0.0080 0.0039 0.0017 0.0006
20 0.0684 0.0573 0.0446 0.0317 0.0209 0.0127 0.0070 0.0035 0.0016 0.0006 0.0002
21 0.0389 0.0314 0.0234 0.0159 0.0100 0.0057 0.0029 0.0013 0.0005 0.0002 0.0000
22 0.0206 0.0160 0.0114 0.0074 0.0043 0.0023 0.0011 0.0004 0.0002 0.0000 0.0000
23 0.0103 0.0076 0.0052 0.0031 0.0017 0.0008 0.0003 0.0001 0.0000 0.0000
24 0.0047 0.0033 0.0021 0.0012 0.0006 0.0003 0.0001 0.0000 0.0000

Table 11 Portion of HCP percentage probability for two separate hands

So, for example, the probably of holding exactly 13 HCP and partner holding exactly 10 HCP is 0.6797%.

Perhaps a more interesting way to represent this data is to pose the question:

Holding X HCP, what is the probability partner holds Y HCP?

We can answer this by simply normalising each row in the above table so that the total adds to 100% by dividing each value by the row sum. Table 12 below shows a portion of this result and includes ‘N-or-more’ in brackets as an accumulated value.

X/Y 8 9 10 11 12 13 14 15 16 17 18
0 4.55 (91.70) 5.88 (87.15) 7.19 (81.27) 8.24 (74.08) 8.94 (65.85) 9.23 (56.91) 9.04 (47.68) 8.39 (38.64) 7.44 (30.25) 6.28 (22.81) 5.02 (16.53)
1 4.99 (90.17) 6.32 (85.17) 7.57 (78.85) 8.46 (71.29) 9.03 (62.82) 9.16 (53.80) 8.83 (44.64) 8.04 (35.81) 7.05 (27.77) 5.85 (20.73) 4.62 (14.88)
2 5.45 (88.68) 6.76 (83.22) 7.91 (76.46) 8.73 (68.55) 9.12 (59.82) 9.09 (50.70) 8.62 (41.61) 7.72 (32.99) 6.65 (25.27) 5.43 (18.62) 4.23 (13.19)
3 5.92 (87.16) 7.17 (81.24) 8.29 (74.07) 8.98 (65.78) 9.20 (56.80) 9.02 (47.60) 8.42 (38.58) 7.39 (30.16) 6.24 (22.77) 5.02 (16.53) 3.82 (11.51)
4 6.37 (85.65) 7.63 (79.27) 8.66 (71.64) 9.23 (62.99) 9.30 (53.76) 8.95 (44.46) 8.19 (35.51) 7.05 (27.33) 5.84 (20.28) 4.58 (14.43) 3.42 (9.85)
5 6.86 (83.83) 8.03 (76.97) 8.94 (68.94) 9.39 (60.00) 9.28 (50.61) 8.76 (41.33) 7.88 (32.58) 6.67 (24.70) 5.40 (18.03) 4.16 (12.63) 3.05 (8.46)
6 7.32 (81.89) 8.42 (74.56) 9.22 (66.15) 9.51 (56.93) 9.21 (47.42) 8.53 (38.22) 7.54 (29.68) 6.25 (22.14) 4.97 (15.89) 3.75 (10.93) 2.68 (7.18)
7 7.80 (79.90) 8.82 (72.10) 9.48 (63.28) 9.60 (53.80) 9.12 (44.21) 8.30 (35.08) 7.17 (26.78) 5.82 (19.62) 4.52 (13.80) 3.33 (9.28) 2.32 (5.95)
8 8.27 (77.71) 9.17 (69.44) 9.67 (60.26) 9.62 (50.59) 8.98 (40.97) 7.98 (31.99) 6.76 (24.01) 5.37 (17.25) 4.07 (11.88) 2.92 (7.81) 1.98 (4.89)
9 8.72 (75.32) 9.48 (66.60) 9.82 (57.12) 9.59 (47.30) 8.74 (37.72) 7.62 (28.98) 6.32 (21.35) 4.90 (15.04) 3.63 (10.14) 2.54 (6.51) 1.68 (3.97)
10 9.15 (72.79) 9.77 (63.65) 9.92 (53.88) 9.47 (43.96) 8.47 (34.49) 7.23 (26.02) 5.85 (18.79) 4.42 (12.94) 3.19 (8.52) 2.17 (5.33) 1.39 (3.16)
11 9.57 (70.13) 10.03 (60.57) 9.96 (50.54) 9.32 (40.58) 8.15 (31.26) 6.78 (23.11) 5.35 (16.32) 3.94 (10.97) 2.76 (7.03) 1.82 (4.27) 1.13 (2.45)
12 9.94 (67.25) 10.19 (57.31) 9.92 (47.12) 9.09 (37.19) 7.76 (28.11) 6.30 (20.35) 4.85 (14.05) 3.47 (9.21) 2.36 (5.74) 1.51 (3.38) 0.90 (1.87)
13 10.27 (64.21) 10.31 (53.94) 9.83 (43.63) 8.78 (33.80) 7.31 (25.02) 5.79 (17.71) 4.33 (11.91) 3.00 (7.59) 1.98 (4.58) 1.22 (2.60) 0.70 (1.38)
14 10.55 (61.01) 10.38 (50.46) 9.66 (40.07) 8.40 (30.42) 6.83 (22.01) 5.26 (15.18) 3.80 (9.93) 2.56 (6.13) 1.62 (3.57) 0.96 (1.95) 0.52 (0.99)
15 10.79 (57.64) 10.36 (46.85) 9.40 (36.49) 7.97 (27.10) 6.30 (19.12) 4.69 (12.83) 3.29 (8.14) 2.13 (4.85) 1.30 (2.72) 0.73 (1.42) 0.38 (0.69)
16 10.93 (54.09) 10.24 (43.16) 9.07 (32.92) 7.47 (23.85) 5.72 (16.39) 4.14 (10.67) 2.79 (6.53) 1.73 (3.74) 1.01 (2.01) 0.54 (1.00) 0.26 (0.45)
17 11.00 (50.41) 10.06 (39.41) 8.65 (29.35) 6.89 (20.69) 5.13 (13.80) 3.57 (8.68) 2.31 (5.11) 1.37 (2.80) 0.76 (1.43) 0.38 (0.66) 0.17 (0.28)
18 11.00 (46.59) 9.78 (35.59) 8.14 (25.81) 6.29 (17.67) 4.50 (11.38) 3.00 (6.88) 1.86 (3.88) 1.05 (2.02) 0.55 (0.96) 0.26 (0.42) 0.11 (0.16)
19 10.87 (42.64) 9.37 (31.77) 7.58 (22.40) 5.62 (14.82) 3.87 (9.20) 2.48 (5.33) 1.46 (2.86) 0.77 (1.40) 0.38 (0.62) 0.16 (0.25) 0.06 (0.08)
20 10.63 (38.58) 8.90 (27.96) 6.92 (19.06) 4.92 (12.13) 3.25 (7.21) 1.98 (3.97) 1.08 (1.99) 0.54 (0.91) 0.24 (0.37) 0.09 (0.13) 0.03 (0.04)
21 10.29 (34.48) 8.30 (24.19) 6.20 (15.88) 4.21 (9.68) 2.65 (5.47) 1.50 (2.82) 0.77 (1.32) 0.36 (0.55) 0.14 (0.20) 0.05 (0.06) 0.01 (0.01)
22 9.82 (30.32) 7.60 (20.50) 5.42 (12.91) 3.51 (7.49) 2.06 (3.98) 1.09 (1.92) 0.52 (0.82) 0.21 (0.30) 0.07 (0.09) 0.02 (0.02) 0.00 (0.00)
23 9.18 (26.18) 6.81 (17.00) 4.64 (10.18) 2.80 (5.54) 1.54 (2.74) 0.76 (1.21) 0.31 (0.45) 0.11 (0.14) 0.03 (0.03) 0.00 (0.00)
24 8.44 (22.06) 5.97 (13.62) 3.77 (7.66) 2.12 (3.88) 1.08 (1.76) 0.46 (0.68) 0.17 (0.22) 0.05 (0.05) 0.01 (0.01)

Table 12 Portion of percentage probability of partner holding Y HCP (top row) given you hold X HCP (left column). Bracketed values are N-or-more accumulations

So if you hold 16 HCP, say, the probability that partner has:

  • Exactly 8 HCP is 10.93%
  • 8 or more HCP is 54.09%

Given the partnership holds a combined number of HCP, what is the probability of the various distributions of those HCP between the two hands?

This is analogous to the distribution of cards in a particular suit between two hands shown in Table 7 above.

The following code uses the hcp-prob-separate HCP data generated earlier to determine the probability of the split of given combined HCP holdings.

"If two hands hold a specific combined HCP count, what is the probability
 of the distribution of those HCP between the two hands"
(def HCP-split
  (let [res (reduce
              (fn [acc [[h1 h2] p]]
                (update acc [(+ h1 h2) [h1 h2]] (fnil + 0.0) p))
              {}
              hcp-prob-separate)
        tots (reduce
               (fn [acc [[h _] p]]
                 (update acc h (fnil + 0.0) p))
               {}
               res)
        res (reduce
              (fn [acc [[a b] p]]
                (assoc-in acc [a b] (* 100.0 (/ p (tots a)))))
              {}
              res)]
    (into (sorted-map)  ; tidy up result for display
          (for [[k v] res] [k (into (sorted-map) v)]))))

;=> {0 {[0 0] 100.0},
;    1 {[0 1] 50.0,
;       [1 0] 50.0},
;    2 {[0 2] 30.303030303030305,
;       [1 1] 39.393939393939384,
;       [2 0] 30.303030303030305},
;    3 {[0 3] 22.178988326848252,
;       [1 2] 27.821011673151748,
;       [2 1] 27.821011673151748,
;       [3 0] 22.178988326848252},
;    4 {[0 4] 15.79960275848456,
;       [1 3] 23.062213942930455,
;       [2 2] 22.276366597169968,
;       [3 1] 23.062213942930455,
;       [4 0] 15.79960275848456},
;    ...

Table 13 below shows a few examples of the HCP distribution, the full table can be downloaded in csv format here. The distribution of HCP is similar to that for cards in given suit.

# X-Y Prob (%)
12 0-12 1.53
1-11 3.14
2-10 5.05
3-9 8.31
4-8 11.54
5-7 13.52
6-6 13.80
7-5 13.52
8-4 11.54
9-3 8.31
10-2 5.05
11-1 3.14
12-0 1.53
# X-Y Prob (%)
13 0-13 1.14
1-12 2.42
2-11 4.02
3-10 6.94
4-9 9.97
5-8 12.08
6-7 13.44
7-6 13.44
8-5 12.08
9-4 9.97
10-3 6.94
11-2 4.02
12-1 2.42
13-0 1.14
# X-Y Prob (%)
14 0-14 0.85
1-13 1.86
2-12 3.19
3-11 5.70
4-10 8.57
5-9 10.73
6-8 12.36
7-7 13.51
8-6 12.36
9-5 10.73
10-4 8.57
11-3 5.70
12-2 3.19
13-1 1.86
14-0 0.85
# X-Y Prob (%)
15 0-15 0.62
1-14 1.42
2-13 2.52
3-12 4.63
4-11 7.25
5-10 9.48
6-9 11.28
7-8 12.80
8-7 12.80
9-6 11.28
10-5 9.48
11-4 7.25
12-3 4.63
13-2 2.52
14-1 1.42
15-0 0.62

Table 13 Some percentage probabilities of HCP dividing between two hands

As an example of how this might be useful, consider playing in 4 Hearts with the following hands after an uncontested auction:

♠︎ KQJ109
♥︎ AK62
♦︎ 82
♣︎ J5
 
♠︎ A4
♥︎ Q9843
♦︎ KJ73
♣︎ Q9

Left hand opponent (West) leads a small Club to East’s King. East continues with the Club Ace and then switches to a low Diamond. Should you play the King or Jack?

Clearly if the two missing Diamond honours are with either East or West it will not matter. You will either make the contract or not depending on who holds them. However, if they are split, the contract depends on whether the Ace is with East or West (note low from Axxx is routine for good players in this situation).

The opponents have 14 HCP between them. East has shown up with seven (Club Ace and King) so far. If East also has the Diamond Ace (and West the Queen), the HCP split would be 3-11 or 2-12, depending on who holds the Heart Jack, compared with a 4-10 or 5-9 split if West has the Diamond Ace (and East the Queen). From the table above the latter splits are about twice as likely as the former. This makes playing the Diamond Jack a much better prospect than the King.

Interestingly, while Bridge literature regularly discusses suit division and its relative probabilities to guide play, discussion about HCP division is largely non-existent (at least in my experience).

Suit and HCP Distribution

In the previous blog we consider the combination of suit distribution and HCP holdings for a single hand. While it is possible to calculate these probabilities for two hands, the calculation and result set is significantly larger. The following illustrative and non-optimised code calculates a point solution for a given suit distribution and HCP holding for each hand.

(defn distr-HCP-two-hands
  "Calculate the probability of:
  Hand A holding d1 suit distribution and h1 HCP, and,
  Hand B holding d2 suit distribution and h2 HCP
  where d1, d2 are vectors of the suits' length (eg. [4 2 3 4])"
  [d1 d2 h1 h2]
  (let [c5213c3913 (* (comb 52 13) (comb 39 13))
        z [[0 0] [0 1] [1 0]]  ; possible honour holding of the two hands
        ps (for [[sa1 sa2] z, [sk1 sk2] z, [sq1 sq2] z, [sj1 sj2] z,
                 [ha1 ha2] z, [hk1 hk2] z, [hq1 hq2] z, [hj1 hj2] z,
                 [da1 da2] z, [dk1 dk2] z, [dq1 dq2] z, [dj1 dj2] z,
                 [ca1 ca2] z, [ck1 ck2] z, [cq1 cq2] z, [cj1 cj2] z
                 :let [sx1 (- (d1 0) (+ sa1 sk1 sq1 sj1))
                       hx1 (- (d1 1) (+ ha1 hk1 hq1 hj1))
                       dx1 (- (d1 2) (+ da1 dk1 dq1 dj1))
                       cx1 (- (d1 3) (+ ca1 ck1 cq1 cj1))
                       sx2 (- (d2 0) (+ sa2 sk2 sq2 sj2))
                       hx2 (- (d2 1) (+ ha2 hk2 hq2 hj2))
                       dx2 (- (d2 2) (+ da2 dk2 dq2 dj2))
                       cx2 (- (d2 3) (+ ca2 ck2 cq2 cj2))
                       hcp1 (+ (* 4 (+ sa1 ha1 da1 ca1))
                               (* 3 (+ sk1 hk1 dk1 ck1))
                               (* 2 (+ sq1 hq1 dq1 cq1))
                               (* 1 (+ sj1 hj1 dj1 cj1)))
                       hcp2 (+ (* 4 (+ sa2 ha2 da2 ca2))
                               (* 3 (+ sk2 hk2 dk2 ck2))
                               (* 2 (+ sq2 hq2 dq2 cq2))
                               (* 1 (+ sj2 hj2 dj2 cj2)))]
                 :when (and
                         (= hcp1 h1)
                         (= hcp2 h2)
                         (not-any? neg? [sx1 hx1 dx1 cx1])
                         (not-any? neg? [sx2 hx2 dx2 cx2]))]
             (* (comb 9 sx1)
                (comb 9 hx1)
                (comb 9 dx1)
                (comb 9 cx1)
                (comb (- 9 sx1) sx2)
                (comb (- 9 hx1) hx2)
                (comb (- 9 dx1) dx2)
                (comb (- 9 cx1) cx2)))]
    (double (/ (apply + ps) c5213c3913))))

(distr-HCP-two-hands [4 4 3 2] [3 2 3 5] 12 10)
;=> 2.852657421381616E-6

The code runs for about a minute on my laptop. This can be significantly reduced by using honour indexes and pre-calculated vectors of values similar to the first blog, but it is still a sizeable calculation.

An alternative approach is to approximate the result by treating the suit distribution and HCP holding as independent variables (which strictly they are not). This approximation is reasonable for more common holdings but fails for more extreme distributions and HCP holdings. From probability theory:

P(Distr and HCP) = P(Distr) x P(HCP|Distr) = P(HCP) x P(Distr|HCP)
where P(A|B) is the probability of A given that B is true

Using the approximation of independent variables we get:

P(Distr and HCP) ~= P(Distr) x P(HCP)

For example, consider the two hands:

  • Hand A: 4-4-3-2 suit distribution and 12 HCP
  • Hand B: 3-2-3-5 suit distribution and 10 HCP

The probabilities are:

  • Estimate = 3.706883995099E-4 x 0.007965990398622 = 2.9529002313764E-6
  • Actual = 2.852657421381616E-6
  • Error = 3.5140%

Other common cases typically yield errors in the 3-5% range.

Next Article

This article has focused on the probability of various attributes of two hands that form a Bridge partnership. The next post will look at individual suit combinations and plays.

Bridge Hand Probability Analysis

Introduction

Bridge is a wonderful card game. It is sufficiently complex and interesting that some extremely talented people spend a good proportion of their lives playing, analysing, commenting, writing and teaching it. It also lends itself to computer analysis but not in the way chess or similar “complete knowledge” games do. In Bridge the exactly position (card holdings) is usually not completely known. So it is a game about probability and inference.

This is the first in (hopefully) a series of articles on computer analysis of the game of Bridge. It looks at the probability of holding various types of hand after the initial deal and before any other information is available. Several standard tables are generated that represent some key aspects of the game. A general algorithm is developed that allows a broad range of hand probabilities to be calculated.

The code examples are in Clojure but should translate readily to other languages. Some general understanding of both probability theory and Bridge is assumed.

Basic Terminology

Bridge deals are made up of 52 unique cards equally distributed between four hands – North (N), South (S), East (E) and West (W) – with 13 cards in each hand. The cards are shuffled (mixed up) before being dealt (distributed) so that the cards in each hand are randomly selected. The cards are grouped into four suits – Spades (♠︎), Hearts (♥︎), Diamonds (♦︎) and Clubs (♣︎). Spades and Hearts are called the major suits, Clubs and Diamonds are called the minor suits.

Each suit has 13 cards: Ace (A), King (K), Queen (Q), Jack (J), 10, 9, …, 2 (in rank order highest to lowest). The A, K, Q and J of each suit are collectively known as honours (honors US).

The distribution of a hand is the number of cards in each suit. These need to sum to 13, so there are only a certain number of distribution “patterns”. Some examples are 4333, 4432, 5332, etc. These are “generic” distributions in the sense that a 4333 distribution could have the 4-card suit as S, H, D or C (i.e. 4-3-3-3, 3-4-3-3, 3-3-4-3 or 3-3-3-4). The normal convention, as above, is to place dashes (-) between suit counts to denote specific suit distributions, and to exclude them when representing generic distributions. In the generic case the suit counts are always listed in order of most cards to fewest cards.

A common method of assessing the strength of a hand is to use a High Card Points (HCP) count. It assigns points to the four honour cards in each suit as follows: A=4, K=3, Q=2 and J=1. This means there a 40 HCP in any deal, distributed between the four hands.

An example hand:

♠︎ KJ3
♥︎ A10952
♦︎ QJ4
♣︎ A8

This hand has:

  • Generic distribution: 5332
  • Specific distribution: 3-5-3-2
  • HCP: 15

Combinations

We need some utility functions for our analysis. The most useful is the combination function which calculates the number of ways you can select “k” objects from a collection of “n” objects where order is not important. It will be denoted C(n,k) here and can be calculated using the following equation:

C(n,k) = n!/k!(n-k)!
where n! = n factorial = n(n-1)(n-2)…1
Note C(n,0) = C(n,n) = 1.

For example, given A,B,C and D. There are C(4,1) = 4!/1!3! = 4 ways to select one letter (A, B, C or D), and C(4,2) = 4!/2!2! = 6 ways to select two letters (AB, AC, AD, BC, BD or CD).

The Clojure code to calculate combinations is straightforward. However, note the use of *’ instead of just * for the multiplier function. The former supports arbitrary precious arithmetic which is important as factorials become very large, very quickly.

(defn fact
  "Return the factorial of integer n >= 0"
  [n]
  (apply *' (range 1 (inc n))))

(defn comb
  "Return the combination - ways of selecting k from n (k<=n)"
  [n k]
  (/ (fact n) (*' (fact k) (fact (- n k)))))

Initial Analysis

Let’s start by answering some basic questions.

How many deals are there?

One way to look at this is to imagine laying out the 52 cards in every possible order and then taking the first 13 as the North (say) hand, the next 13 as the South hand, etc. This isn’t quite correct as it includes the card order within each hand. We don’t care about this order. To remove it, we can divide by the number of ways 13 cards can be ordered within a hand. The number of ways 52 cards can be ordered is 52!. The number of ways 13 cards can be ordered is 13!. This leads to the result of:

52!/13!4 = 53,644,737,765,488,792,839,237,440,000

Another, perhaps more obvious, approach is to consider each hand in turn. The first, North (say), selects 13 cards from 52, the second, selects 13 cards from the remaining 39 cards (after North’s selection). The third hand selects 13 cards from the remaining 26 cards. The final 13 cards go to the last hand. This leads to:

C(52,13)*C(39,13)*C(26,13)*C(13,13) = 53,644,737,765,488,792,839,237,440,000

The same result. Note the last term is 1 but is included for completeness.

Either way it is a seriously big number and pretty much guarantees you will never play the same deal no matter how often you play!

How many hands are there?

This is easy using the analysis above. It is just the number of ways 13 cards can be selected from 52:

C(52,13) = 635,013,559,600

This is significantly smaller than the number of deals. Using the birthday problem approximation you would need to play around 938,000 hands before there was a fifty percent chance of holding the same hand. This equates to playing 50 hands a day, each day of the year, for 51 years.

Suit Distribution

The obvious first question is:

What is the probability of each distribution?

Let’s consider a specific case, say, 4-3-2-4 (i.e. 4♠︎, 3♥︎, 2♦︎ and 4♣︎). To make up this hand we need to select 4 Spades from the 13 on offer, 3 Hearts from 13, 2 Diamonds from 13 and 4 Clubs. This means there are C(13,4)*C(13,3)*C(13,2)*C(13,4) ways to construct this distribution:

C(13,4)*C(13,3)*C(13,2)*C(13,4) = 11,404,407,300

As there are C(52,13) possible ways to construct all hands, the probability of this exact distribution is:

C(13,4)*C(13,3)*C(13,2)*C(13,4) / C(52,13) = 0.017959313 (or 1.796%)

This is the probability of the specific 4-3-2-4 distribution. If we want to determine the probability of the generic 4432 distribution we need to consider all the 12 various 4432 specific distributions:

4-4-3-2, 4-4-2-3, 4-3-4-2, 4-2-4-3, 4-3-2-4, 4-2-3-4,
3-4-4-2, 2-4-4-3, 3-4-2-4, 2-4-3-4, 3-2-4-4, 2-3-4-4

This leads to a result for the generic 4432 distribution of:

12*C(13,4)*C(13,3)*C(13,2)*C(13,4) / C(52,13) = 0.21551175 (or 21.55%)

So the generic 4432 distribution occurs about 21.55% of the time.

We can generalise this result for all distributions. The following code calculates the probability of each specific distribution. It generates all the possible suit length (0-13) combinations (144 = 38,416) and selects those that add to 13. For these, the probability is calculated as above.

(def distr-specific
  (let [c5213 (comb 52 13)]
    (for [s (range 14)
          h (range 14)
          d (range 14)
          c (range 14)
          :when (= 13 (+ s h d c))]
      (let [cs (* (comb 13 s) (comb 13 h) (comb 13 d) (comb 13 c))
            pp (/ (* 100.0 cs) c5213)]
        [[s h d c] pp]))))

;=> ([[0 0 0 13] 1.5747695224491076E-10]
;    [[0 0 1 12] 2.661360492938992E-8]
;    [[0 0 2 11] 9.580897774580372E-7]
;    ...
;    [[3 4 3 3] 2.6340325788532972]
;    [[3 4 4 2] 1.7959313037636118]
;    ...
;    [[12 1 0 0] 2.661360492938992E-8]
;    [[13 0 0 0] 1.5747695224491076E-10])

(apply + (map second distr-specific))
;=> 100.00000000000003

(count distr-specific)
;=> 560

The result shows there are 560 specific distributions and, encouragingly, their probabilities sum to a total of 100%. Throughout this article, when probability tables are generated, some summation code is usually included to validate the result.

The specific distributions can be grouped into generic distributions using the following code, which also counts the number of specific distributions associated with each generic distribution.

(def distr-generic
  (let [ds-fn (fn [acc [d p]]
                (let [dg-key (vec (sort > d))
                      acc (update-in acc [dg-key :prob] (fnil + 0.0) p)
                      acc (update-in acc [dg-key :cnt] (fnil inc 0))]
                  acc))]
    (reduce ds-fn (sorted-map) distr-specific)))

;=> {[4 3 3 3] {:prob 10.536130315413189, :cnt 4},
;    [4 4 3 2] {:prob 21.551175645163344, :cnt 12},
;    [4 4 4 1] {:prob 2.9932188396060195, :cnt 4},
;    [5 3 3 2] {:prob 15.516846464517606, :cnt 12},
;    [5 4 2 2] {:prob 10.579668043989278, :cnt 12},
;    [5 4 3 1] {:prob 12.930705387098, :cnt 24},
;    ...
;    [13 0 0 0] {:prob 6.299078089796431E-10, :cnt 4}}

(apply + (map :prob (vals distr-generic)))
;=> 99.99999999999996

(count distr-generic)
;=> 39

Full results are shown in Table 1 below and are downloadable here as a csv file. The “Specific count” column is the number for specific distributions that make up each generic distribution. So the columns are related as follows:

“Specific count” * “Specific Prob (%)” = “Generic Prob (%)”
Generic Distribution Specific Count Specific Prob (%) Generic Prob (%)
4333 4 2.6340 10.5361
4432 12 1.7959 21.5512
4441 4 0.7483 2.9932
5332 12 1.2931 15.5168
5422 12 0.8816 10.5797
5431 24 0.5388 12.9307
5440 12 0.1036 1.2433
5521 12 0.2645 3.1739
5530 12 0.0746 0.8952
6322 12 0.4702 5.6425
6331 12 0.2873 3.4482
6421 24 0.1959 4.7021
6430 24 0.0553 1.3262
6511 12 0.0588 0.7053
6520 24 0.0271 0.6511
6610 12 0.0060 0.0723
7222 4 0.1282 0.5130
7321 24 0.0784 1.8808
7330 12 0.0221 0.2652
7411 12 0.0327 0.3918
7420 24 0.0151 0.3617
7510 24 0.0045 0.1085
7600 12 0.0005 0.0056
8221 12 0.0160 0.1924
8311 12 0.0098 0.1176
8320 24 0.0045 0.1085
8410 24 0.0019 0.0452
8500 12 0.0003 0.0031
9211 12 0.0015 0.0178
9220 12 0.0007 0.0082
9310 24 0.0004 0.0100
9400 12 0.0001 0.0010
10-111 4 0.0001 0.0004
10-210 24 0.0000 0.0011
10-300 12 0.0000 0.0002
11-110 12 0.0000 0.0000
11-200 12 0.0000 0.0000
12-100 12 0.0000 0.0000
13-000 4 0.0000 0.0000
Total 560 100.00

Table 1 Percentage probability of all distributions

Although 4333 is the most balanced and likely specific distribution, it is much less common than 4432 because there are only 4 ‘variants’ compared with 12 variants for 4432. Similarly 4441 is comparatively rare compared with other semi-balanced hands.

It is also interesting to consider the table in probability order with an aggregated total. Part of this table is shown in Table 2 below.

Generic Distribution Generic Prob (%) Aggregate Prob (%)
4432 21.55 21.55
5332 15.52 37.07
5431 12.93 50.00
5422 10.58 60.58
4333 10.54 71.11
6322 5.64 76.76
6421 4.70 81.46
6331 3.45 84.91
5521 3.17 88.08
4441 2.99 91.07
7321 1.88 92.96
6430 1.33 94.28
5440 1.24 95.52
5530 0.90 96.42
6511 0.71 97.13
6520 0.65 97.78
7222 0.51 98.29
7411 0.39 98.68
7420 0.36 99.04

Table 2 Aggregate percentage probability of most common distributions

As we can see, only three distributions (4432, 5332 and 5431) represent half of all hands, the top six cover 75% and the top half (there are 39 in total) cover over 99%.

Armed with these results, we can answer distribution based questions such as:

What is the probability of holding a suit of a given length?

The code below uses the generic distribution table above to find all distributions that contain a suit of the specified length (the first :let line). It then retrieves the probabilities of these distributions as a list (the second :let line), and sums them to produce a total for each length.

(for [n (range 14)
      :let [ks (filter #(contains? (set %) n) (keys distr-generic))
            ps (for [k ks] (:prob (get distr-generic k)))]]
  [n (apply + ps)])

;=> [0 5.106552086923343]
;   [1 30.79141395392653]
;   [2 64.90069876863775]
;   ...

The full results are shown in Table 3 below.

Suit length Probability (%)
0 5.10655
1 30.79141
2 64.90070
3 74.22930
4 66.66225
5 45.80767
6 16.55325
7 3.52664
8 0.46676
9 0.03704
10 0.00165
11 0.00004
12 0.00000
13 0.00000

Table 3 Percentage probability of holding a suit of a given length

Holding a void (zero cards) is more common than holding a 7-card suit. Over a third of hands have a singleton or void, perhaps explaining the prevalence of systems with splinter bids. 9-card suits are very rare, 10+ card suits are practically non-existent.

What is the probability of holding two suits of given lengths?

We can use the same general approach by generating all the two suit length combinations as (a,b) pairs and summing the probabilities of the generic distributes that contain them. However, there are a few subtleties. First, as the probability of (a,b) is going to be the same as the probability of (b,a), we only need to consider one of these cases, say ‘a’ less than or equal to ‘b’.

Secondly, for each pair of lengths, we need to find those distributions that contain both. This is a little tricky when a=b. For example, with a length pair of (2,2) and a distribution of 5332. Both ‘a’ (2) and ‘b’ (2) are contained in 5332, if we treat them separately, but not as a pair (i.e. two instances). Whereas (3,3) is contained in 5332.

To account for this the code uses the frequencies function to create a map of the number of instances of each length in the distribution. These counts are then checked based on whether ‘a’ equals ‘b’. If so, a count of two or more is required, otherwise one each is sufficient.

(for [a (range 14)
      b (range a (- 14 a))
      :let [k-fn (fn [d]
                   (let [df (frequencies d)]
                     (if (= a b)
                       (>= (get df a 0) 2)
                       (and (>= (get df a 0) 1)
                            (>= (get df b 0) 1)))))
            ks (filter k-fn (keys distr-generic))
            ps (for [k ks] (:prob (get distr-generic k)))]]
  [[a b] (apply + ps)])

;=> ([[0 0] 0.009827127477294894]
;    [[1 0] 0.2372297355270522]
;    [[1 1] 1.2329342241025114]
;    [[2 0] 1.1305919257098023]
;    [[2 1] 9.968069518369386]
;    [[2 2] 16.935689280673436]
;    [[3 0] 2.605385268689623]
;    [[3 1] 18.387322400099496]
;    [[3 2] 44.699851023464674]
;    [[3 3] 29.76641012186663]
;    ...
0 1 2 3 4 5 6
0 0.00983
1 0.23723 1.23293
2 1.13059 9.96807 16.93569
3 2.60539 18.38732 44.69985 29.76641
4 2.97744 21.06305 37.19462 46.34424 25.78773
5 2.90124 16.91843 29.92147 29.34275 24.75371 4.06910
6 2.05519 8.92791 10.99562 10.41690 6.02830 1.35637 0.07234
7 0.74102 2.38118 2.75548 2.14608 0.75354 0.10851 0.00556
8 0.15685 0.35512 0.30087 0.22606 0.04521 0.00313
9 0.01923 0.02786 0.02603 0.01005 0.00097
10 0.00125 0.00149 0.00110 0.00015
11 0.00004 0.00002 0.00001
12 0.00000 0.00000
13 0.00000

Table 4 Percentage probability of holding two suits of a given length

Two suited hands 5-4 or better occur about 37% of the time. Suggesting that two-suited bids have some merit. 6-4 is more common than 5-5.

Hand distributions are only part of the story. What about hand strength?

HCP Distribution

As with suit distribution, the initial question is:

What is the probability of holding a given number of HCP?

Let’s again consider a specific example. What is the probability of a hand containing exactly 4 HCP? Using the HCP scale (A=4, K=3, Q=2, J=1) it is clear that the 4 HCP could be made up in any of the following ways:

1 x A
1 x K, 1 x J
2 x Q
1 x Q, 2 x J
4 x J

By dividing the cards into five groups, 4xA, 4xK, 4xQ, 4xJ and 36xOther, we can apply the same combination selection approach. So the number of hands that contain exactly one Ace and 12 Other cards (i.e. non-honour cards) is:

C(4,1)*C(4,0)*C(4,0)*C(4,0)*C(36,12) = 5,006,710,800

Similarly, the number of hands containing exactly one King and one Jack and 11 Other cards is:

C(4,0)*C(4,1)*C(4,0)*C(4,1)*C(36,11) = 9,612,884,736

In general, the number of hands containing ‘a’ aces, ‘k’ kings, ‘q’ queens and ‘j’ jacks is:

C(4,a)*C(4,k)*C(4,q)*C(4,j)*C(36,(13 – (a+k+q+j)))

So we could calculate the number of hands for each of the HCP combinations above, sum them, and divide by C(52,13) to get the probability of holding exactly 4 HCPs, but it is easier to work the other way around. By considering the 5 x 5 x 5 x 5 combinations of honour cards (A, K, Q and J) and their corresponding HCP score, we can accumulate the total number of hands for each HCP value as shown in the following code.

(defn hcp-prob
  "Return a sorted map of HCP probabilities"
  []
  (let [c5213 (comb 52 13)
        plst (for [a (range 5)
                   k (range 5)
                   q (range 5)
                   j (range 5)
                   :let [x (- 13 (+ a k q j))]
                   :when (>= x 0)]
               (let [hcp (+ (* 4 a) (* 3 k) (* 2 q) (* 1 j))
                     cs (* (comb 4 a)
                           (comb 4 k)
                           (comb 4 q)
                           (comb 4 j)
                           (comb 36 x))
                     prob (/ cs c5213)]
                 [hcp prob]))
        h-fn (fn [acc [h p]] (update acc h (fnil + 0.0) (* 100.0 p)))]
    (reduce h-fn (sorted-map) plst)))

;=> {0 0.3638961034872365,
;    1 0.788441557555679,
;    2 1.356119478995768,
;    ...

(apply + (map val (hcp-prob)))
;=> 99.99999999999997

The full results are shown in Table 5 below and can be download as a csv file here.

HCP Exactly N Prob (%) N-or-less Prob (%) N-or-more Prob (%)
0 0.3639 0.3639 100.0000
1 0.7884 1.1523 99.6361
2 1.3561 2.5085 98.8477
3 2.4624 4.9708 97.4915
4 3.8454 8.8163 95.0292
5 5.1862 14.0025 91.1837
6 6.5541 20.5565 85.9975
7 8.0281 28.5846 79.4435
8 8.8922 37.4768 71.4154
9 9.3562 46.8331 62.5232
10 9.4051 56.2382 53.1669
11 8.9447 65.1828 43.7618
12 8.0269 73.2097 34.8172
13 6.9143 80.1240 26.7903
14 5.6933 85.8174 19.8760
15 4.4237 90.2410 14.1826
16 3.3109 93.5520 9.7590
17 2.3617 95.9137 6.4480
18 1.6051 97.5187 4.0863
19 1.0362 98.5549 2.4813
20 0.6435 99.1985 1.4451
21 0.3779 99.5763 0.8015
22 0.2100 99.7864 0.4237
23 0.1119 99.8983 0.2136
24 0.0559 99.9542 0.1017
25 0.0264 99.9806 0.0458
26 0.0117 99.9923 0.0194
27 0.0049 99.9972 0.0077
28 0.0019 99.9990 0.0028
29 0.0007 99.9997 0.0010
30 0.0002 99.9999 0.0003
31 0.0001 100.0000 0.0001
32 0.0000 100.0000 0.0000
33 0.0000 100.0000 0.0000
34 0.0000 100.0000 0.0000
35 0.0000 100.0000 0.0000
36 0.0000 100.0000 0.0000
37 0.0000 100.0000 0.0000

Table 5 Percentage Probability of holding a specific number of HCP

Our original question on the probability of holding a hand with exactly 4 HCP can now be read directly from the above table as 3.8454%. We can also see, for example, that if you open hands with 12+ HCP, you would open about 34.8% of the time (excluding weak distributed openings). Strong club systems using 16+ HCP would open 1C just under 10% of the time.

The next challenge is to combine distribution and HCP so we can answer questions like what is the probability of a ‘balanced’ hand with 14-16 HCP. Unfortunately, because distribution and HCP are not mutually exclusive we can’t simply used: prob(A and B) = prob(A) x prob(B).

Combined Suit and HCP Distribution

Again let’s consider the following question first:

What is the probability of holding a given distribution and number of HCP?

We can extend the approach above only this time we need to divide the cards into a lot more groups. We need one for each honour card as we are now interested in both its HCP value and its suit. The remaining non-honour cards need to be broken into four groups – one for each suit.

As an example, consider the probability of this hand:

♠︎ Kxx
♥︎ Axxxx
♦︎ QJx
♣︎ xx

The non-honour cards have been replaced with ‘x’ as their rank (or face value) is irrelevant. The number of ways this hand can be selected is:

C(1,0)*C(1,1)*C(1,0)*C(1,0)*C(9,2)* (Spades)
C(1,1)*C(1,0)*C(1,0)*C(1,0)*C(9,4)* (Hearts)
C(1,0)*C(1,0)*C(1,1)*C(1,1)*C(9,1)* (Diamonds)
C(1,0)*C(1,0)*C(1,0)*C(1,0)*C(9,2) (Clubs)

Note that as C(1,0) = C(1,1) = 1, the honour cards don’t directly contribute to the probability result but they do determine the number of remaining cards (Xs) and the HCP value. This hand would be counted in the 5332 distribution and 10 HCP group. Its probability would be added to all the other hands that have the same distribution and HCP count.

The idea is to iterate over all the honours and Xs, and for each valid hand, determine its distribution, HCP and probability, and aggregate it with all the others with the same distribution and HCP. At the end, the probability of each distribution and HCP combination is determined.

The main problem with this approach is there are 216 x 104 (655,360,000) iterations in 20 nested loops! Don’t try this on an abacus. Fortunately modern computers are insanely quick. The following “heroic” code, illustrative but not optimised, runs in just over 3 minutes on my Macbook Pro.

(defn distr-hcp-prob
  "Return a map of distribution and HCP probabilities (not optimised)"
  []
  (let [c5213 (comb 52 13)
        z [0 1]
        plst (for [sa z, sk z, sq z, sj z, sx (range 10)
                   ha z, hk z, hq z, hj z, hx (range 10)
                   da z, dk z, dq z, dj z, dx (range 10)
                   ca z, ck z, cq z, cj z, cx (range 10)
                   :let [ss (+ sa sk sq sj sx)
                         hs (+ ha hk hq hj hx)
                         ds (+ da dk dq dj dx)
                         cs (+ ca ck cq cj cx)]
                   :when (= (+ ss hs ds cs) 13)]
               (let [hcp (+ (* 4 (+ sa ha da ca))
                            (* 3 (+ sk hk dk ck))
                            (* 2 (+ sq hq dq cq))
                            (* 1 (+ sj hj dj cj)))
                     distr (vec (sort > [ss hs ds cs]))
                     cs (* (comb 9 sx)
                           (comb 9 hx)
                           (comb 9 dx)
                           (comb 9 cx))]
                 [[distr hcp] (* 100.0 (/ cs c5213))]))
        p-fn (fn [acc [k p]] (update acc k (fnil + 0.0) p))]
    (reduce p-fn (sorted-map) plst)))

;=> {[[4 3 3 3] 0] 0.04704195862969728,
;    [[4 3 3 3] 1] 0.0918438239913137,
;    [[4 3 3 3] 2] 0.15808658206170367,
;    [[4 3 3 3] 3] 0.27387426011745303,
;    ...

(apply + (map val (distr-hcp-prob)))
;=> 99.99999999999093

This code can be significantly improved by reorganising it by:

  • moving the Xs loops and the probability calculation to the top
  • testing the card count earlier to eliminate pointless lower iterations
  • making use of various pre-calculated results
  • using bit-based honour indexes for fast vector lookups and less nesting

These changes result in a significant improvement reducing the runtime to around 25 seconds (code and more details in the Generalised Algorithm for Table Generation section below).

It is also noteworthy that the Clojure for loop is “lazy” and only returns the next, or next few, items in the sequence when requested by the reduce function. This means the memory requirement of the calculation is quite low. Without laziness the entire sequence would need to be “realised” and held in memory which would be somewhat problematic.

Finally note there are alternative ways to create “cartesian products” of sequences using the Clojure Combinatorics library.

A subset of the result is shown below in Table 6 because of space restrictions. The full table in csv format is available here.

10 11 12 13 14 15 16 17 18
4333 0.9597 0.9167 0.8246 0.7126 0.5925 0.4687 0.3551 0.2585 0.1804
4432 1.9802 1.8903 1.6996 1.4669 1.2166 0.9581 0.7234 0.5234 0.3627
4441 0.2797 0.2670 0.2400 0.2066 0.1706 0.1332 0.0997 0.0712 0.0485
5332 1.4389 1.3719 1.2313 1.0626 0.8779 0.6880 0.5176 0.3727 0.2563
5422 0.9903 0.9431 0.8466 0.7291 0.6012 0.4685 0.3515 0.2511 0.1715
5431 1.2204 1.1627 1.0441 0.8980 0.7391 0.5735 0.4282 0.3038 0.2055
5440 0.1202 0.1148 0.1032 0.0885 0.0724 0.0555 0.0408 0.0283 0.0185
5521 0.3057 0.2901 0.2607 0.2232 0.1828 0.1400 0.1040 0.0724 0.0483
5530 0.0875 0.0833 0.0749 0.0641 0.0523 0.0398 0.0292 0.0200 0.0130
6322 0.5392 0.5110 0.4564 0.3937 0.3217 0.2478 0.1844 0.1308 0.0877
6331 0.3324 0.3151 0.2817 0.2425 0.1978 0.1516 0.1123 0.0790 0.0524
6421 0.4580 0.4333 0.3879 0.3328 0.2711 0.2062 0.1524 0.1060 0.0698
6430 0.1312 0.1245 0.1116 0.0956 0.0776 0.0586 0.0427 0.0292 0.0187
6511 0.0709 0.0667 0.0600 0.0510 0.0413 0.0308 0.0225 0.0151 0.0096
6520 0.0659 0.0622 0.0559 0.0476 0.0384 0.0285 0.0207 0.0138 0.0086
6610 0.0076 0.0072 0.0065 0.0055 0.0043 0.0031 0.0022 0.0014 0.0008
7222 0.0515 0.0479 0.0424 0.0367 0.0295 0.0220 0.0161 0.0113 0.0073
7321 0.1906 0.1773 0.1574 0.1356 0.1090 0.0807 0.0588 0.0406 0.0258
7330 0.0273 0.0255 0.0227 0.0195 0.0156 0.0115 0.0082 0.0056 0.0034
7411 0.0405 0.0377 0.0336 0.0287 0.0230 0.0168 0.0121 0.0082 0.0050
7420 0.0377 0.0351 0.0313 0.0268 0.0214 0.0156 0.0112 0.0074 0.0045
7510 0.0117 0.0109 0.0097 0.0083 0.0065 0.0046 0.0033 0.0021 0.0012
7600 0.0006 0.0006 0.0005 0.0004 0.0003 0.0002 0.0002 0.0001 0.0000
8221 0.0213 0.0187 0.0165 0.0143 0.0113 0.0078 0.0056 0.0038 0.0023
8311 0.0131 0.0116 0.0102 0.0088 0.0070 0.0048 0.0034 0.0023 0.0013
8320 0.0122 0.0108 0.0095 0.0082 0.0065 0.0044 0.0031 0.0021 0.0012
8410 0.0052 0.0046 0.0041 0.0035 0.0027 0.0018 0.0013 0.0008 0.0004
8500 0.0004 0.0003 0.0003 0.0003 0.0002 0.0001 0.0001 0.0000 0.0000
9211 0.0023 0.0018 0.0016 0.0014 0.0011 0.0006 0.0004 0.0003 0.0002
9220 0.0011 0.0008 0.0007 0.0006 0.0005 0.0003 0.0002 0.0001 0.0001
9310 0.0013 0.0011 0.0009 0.0008 0.0006 0.0004 0.0002 0.0002 0.0001
9400 0.0001 0.0001 0.0001 0.0001 0.0001 0.0000 0.0000 0.0000 0.0000

Table 6 Part of the Distribution vs. HCP table

This allows us to answer more complex questions like:

How often do you hold a weak no-trump hand?

Let’s say we define a weak no-trump as 12-14 HCP with either 4333 or 4432 distribution. Summing the six cells above matching this criteria gives 6.51%.

If we also include 5332 distributions with a 5-card minor, we need to add a further 3.17 / 2 (as 5-card minors only occurs half the time), resulting in 8.10%.

How often do you hold a weak-two in a major?

Here we just need to decide what HCP range and distributions constitutes a weak-two opening bid, sum the results and divide by two (to exclude the minors). For 5-10 HCP, with 6322 or 6331 distributions, we get 2.18%.

How often do you hold a strong no-trump hand?

Assuming 16-18 HCP and 4333, 4432 and 5332 (including majors) distributions, we get 3.55%.

Generalised Algorithm for Table Generation

From these results alone, we can’t account for more sophisticated considerations such as suit quality, number of key cards or singleton honours. However, it is relatively easy to modify the code above to cover a broad range of probabilities based on two variables.

The following code takes a single function that returns the “row” and “column” values, as a vector, based on the honour combinations and card counts for each iteration. The honour cards for each suit are represented by the lower four bits of a suit index (is, ih, id and ic) as follows: A = 1000, K = 0100, Q = 0010 and J = 0001. The table below shows all the 16 combinations.

Index Bits Honours Card Count HCP
0 0000 0 0
1 0001 J 1 1
2 0010 Q 1 2
3 0011 QJ 2 3
4 0100 K 1 3
5 0101 KJ 2 4
6 0110 KQ 2 5
7 0111 KQJ 3 6
8 1000 A 1 4
9 1001 AJ 2 5
10 1010 AQ 2 6
11 1011 AQJ 3 7
12 1100 AK 2 7
13 1101 AKJ 3 8
14 1110 AKQ 3 9
15 1111 AKQJ 4 10

Table 7 Honour combinations associated with the index value

These allow for some pre-processing of aggregate values into vectors that can be quickly referenced using just the single index.

The code ignores iterations when either key function returns a non-true (i.e. nil or false) value. This allows filtering and “normalisation” (results inflated to sum to 100%) of subsets of the combinations. This is useful for comparisons with single variable solutions (see below).

(defn hand-map
  "Using the supplied keys function, return a raw and normalised map of
  row and column keys versus probability ignoring non-true keys"
  [keys-fn]
  (let [c5213 (comb 52 13)
        combs [1 9 36 84 126 126 84 36 9 1]     ; pre-calculated comb(9,x)
        hcnt [0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4]  ; honour count by index
        hcps [0 1 2 3 3 4 5 6 4 5 6 7 7 8 9 10] ; hcp by index
        ;
        plst (apply concat
                    (for [sx (range 10)
                          hx (range 10)
                          dx (range 10)
                          cx (range 10)
                          :when (<= (+ sx hx dx cx) 13)]
                      (let [cs (* (combs sx)
                                  (combs hx)
                                  (combs dx)
                                  (combs cx))
                            prob (* 100.0 (float (/ cs c5213)))]
                        (for [is (range 16)
                              ih (range 16)
                              id (range 16)
                              ic (range 16)
                              :let [ss (+ sx (hcnt is))
                                    hs (+ hx (hcnt ih))
                                    ds (+ dx (hcnt id))
                                    cs (+ cx (hcnt ic))]
                              :when (= (+ ss hs ds cs) 13)]
                          (let [hcp (+ (hcps is)
                                       (hcps ih)
                                       (hcps id)
                                       (hcps ic))
                                rc-key (keys-fn [ss hs ds cs]
                                                [is ih id ic]
                                                hcp)]
                            [[(rc-key 0) (rc-key 1)] prob])))))
        ;
        p-fn (fn [acc [k p]]
               (if (and (k 0) (k 1))
                 (update acc k (fnil + 0.0) p)
                 acc))
        raw (reduce p-fn (sorted-map) plst)
        tot (apply + (map val raw))
        ;
        n-fn (fn [acc [k p]] (assoc acc k (* p (/ 100.0 tot))))
        norm (reduce n-fn (sorted-map) raw)]
    {:raw raw
     :norm norm}))

Using this code the earlier distribution vs. HCP result would be generated using the following code:

"Distribution and HCP probabilities"
(hand-map
  (fn [vs vi hcp] [(vec (sort > vs)) hcp]))

This approach allows for a broad range of zero, one and two variable relationships to be calculated on any aspect of card holdings involving honour combinations and suit distributions. For example:

Probability of holding a singleton King (zero variable)

The following code calculates this single value (zero variables). For each combination it checks each suit for a length of one and a King honour.

"Probability of a holding a singleton King"
(hand-map
  (fn [vs vi hcp] ["Singleton King"
                   (some
                     #(and (= 1 (vs %)) (= 4 (vi %)))
                     (range 4))]))

;=>
; {:raw {["Singleton King" true] 2.45614190016599},
;  :norm {["Singleton King" true] 100.0}}

The result of 2.456% is higher than you might have thought.

Probability of holding a specific number of Aces if you have 16+ HCP (one variable)

This is a one variable example. The variable is the number of Aces. The other fixed values is 16 or more HCP.

"Probability of holding a specific number of aces with 16+ HCP"
(let [aces [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]]
  (hand-map
    (fn [vs vi hcp] [(>= hcp 16)
                     (apply + (map aces vi))])))

;=> {:raw {[true 0] 0.06541575839532875,
;          [true 1] 1.5688942600834856,
;          [true 2] 5.052602400387602,
;          [true 3] 2.807934725002544,
;          [true 4] 0.2641056474450006},
;   :norm {[true 0] 0.6703153483184444,
;          [true 1] 16.076461210878005,
;          [true 2] 51.774022361136055,
;          [true 3] 28.772910219442497,
;          [true 4] 2.7062908602249824}}

So if you hold 16 or more HCP the probability of holding the specified number of Aces is:

Aces Probability (%)
0 0.67
1 16.08
2 51.77
3 28.77
4 2.71

Table 8 Probability of holding a specific number of Aces with 16+ HCP

Probability of holding a specific number of Aces for all HCP values (two variables)

The above result can easily be extended to all HCP values (instead of just 16+ HCP) by “freeing” the HCP variable as shown in the code below. Of course now normalisation of any subset has to be performed separately.

"Probability of holding a specific number of aces and HCP"
(let [aces [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]]
  (hand-map
    (fn [vs vi hcp] [hcp
                     (apply + (map aces vi))])))

The results are shown below and can be downloaded as a CSV file here.

HCP 0 1 2 3 4
0 0.36390
1 0.78844
2 1.35612
3 2.46236
4 3.05700 0.78844
5 3.67239 1.51381
6 4.07960 2.47449
7 3.71524 4.31284
8 3.35970 4.96481 0.56768
9 2.68226 5.71328 0.96069
10 1.90530 6.00541 1.49440
11 1.31782 5.12856 2.49829
12 0.78724 4.42847 2.65104 0.16011
13 0.43953 3.31575 2.92184 0.23721
14 0.22792 2.21836 2.89547 0.35157
15 0.10151 1.45162 2.30733 0.56322
16 0.04300 0.80700 1.89932 0.54677 0.01483
17 0.01568 0.42424 1.32570 0.57701 0.01906
18 0.00495 0.20486 0.83164 0.53668 0.02695
19 0.00141 0.08428 0.51270 0.39646 0.04132
20 0.00031 0.03330 0.26309 0.31050 0.03634
21 0.00006 0.01102 0.12960 0.20048 0.03671
22 0.00001 0.00319 0.05776 0.11722 0.03187
23 0.00000 0.00082 0.02173 0.06773 0.02163
24 0.00000 0.00015 0.00795 0.03172 0.01608
25 0.00002 0.00234 0.01455 0.00951
26 0.00000 0.00061 0.00591 0.00514
27 0.00000 0.00014 0.00201 0.00276
28 0.00000 0.00002 0.00067 0.00116
29 0.00000 0.00017 0.00049
30 0.00000 0.00004 0.00018
31 0.00000 0.00001 0.00005
32 0.00000 0.00002
33 0.00000 0.00000
34 0.00000 0.00000
35 0.00000
36 0.00000
37 0.00000

Table 9 Percentage probability of holding a specific HCP value and number of Aces

Probability of holding a specific number of Keycards for all HCP values

Keycards are defined as the four Aces and the King of trumps. The Queen of trumps is sometimes included. We will assume that the longest suit, or one of them if there are several, is the trump suit. The following code will produce a similar table to the Aces one above. In this case, we will include the keycard count both with, and without, the Queen of trumps.

"Probability of holding a specific number of keycards and HCP
(assumes one of the longest suits is trumps)"
(let [aces [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
      kings [0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
      queens [0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]]
  (hand-map
    (fn [vs vi hcp]
      (let [inx (->> (map vector vs vi)
                     (sort-by first >)
                     first
                     peek)
            kcds (+ (apply + (map aces vi))
                    (kings inx))]
        [hcp [kcds (queens inx)]]))))

The results are shown below and can be downloaded as a CSV file here.

0-Q 0+Q 1-Q 1+Q 2-Q 2+Q 3-Q 3+Q 4-Q 4+Q 5-Q 5+Q
0 0.36390
1 0.78844
2 1.00808 0.34804
3 1.46033 0.65399 0.34804
4 1.57982 0.82318 1.44243
5 1.41167 1.18930 2.33699 0.24824
6 1.27307 1.20774 3.00980 1.06349
7 0.92933 1.07349 3.77905 1.59223 0.65399
8 0.61917 0.94239 3.66454 2.01087 1.65522
9 0.39269 0.65989 3.15431 2.49294 2.24690 0.40950
10 0.20388 0.43626 2.57033 2.30077 2.88262 1.01126
11 0.10118 0.26570 1.74543 1.95070 3.16818 1.29606 0.41743
12 0.04411 0.13420 1.10128 1.54337 2.80455 1.63106 0.76829
13 0.01579 0.06525 0.63525 1.00744 2.30161 1.74794 0.91154 0.22953
14 0.00541 0.02712 0.30987 0.62410 1.68513 1.48433 1.16258 0.39479
15 0.00136 0.00954 0.14272 0.34541 1.06626 1.19193 1.11213 0.44883 0.10550
16 0.00029 0.00311 0.05650 0.16295 0.62605 0.84402 0.90710 0.56281 0.14810
17 0.00005 0.00075 0.01889 0.07284 0.32524 0.51456 0.70542 0.51582 0.15724 0.05089
18 0.00000 0.00015 0.00579 0.02740 0.14745 0.29427 0.45942 0.40731 0.19947 0.06382
19 0.00000 0.00002 0.00130 0.00889 0.06142 0.14662 0.27137 0.30764 0.16401 0.06611 0.00879
20 0.00000 0.00025 0.00257 0.02171 0.06411 0.14622 0.19237 0.12402 0.08278 0.00951
21 0.00000 0.00003 0.00055 0.00656 0.02575 0.06763 0.11000 0.09101 0.06346 0.00919 0.00370
22 0.00000 0.00010 0.00172 0.00865 0.02835 0.05704 0.05199 0.04719 0.01161 0.00338
23 0.00000 0.00001 0.00033 0.00251 0.01042 0.02529 0.02872 0.03328 0.00806 0.00328
24 0.00000 0.00005 0.00062 0.00324 0.01020 0.01401 0.01800 0.00567 0.00412
25 0.00000 0.00000 0.00011 0.00086 0.00357 0.00568 0.00973 0.00392 0.00255
26 0.00000 0.00002 0.00018 0.00106 0.00220 0.00447 0.00193 0.00182
27 0.00000 0.00003 0.00027 0.00069 0.00174 0.00100 0.00119
28 0.00000 0.00000 0.00005 0.00019 0.00064 0.00043 0.00054
29 0.00000 0.00001 0.00004 0.00019 0.00015 0.00028
30 0.00000 0.00001 0.00005 0.00005 0.00011
31 0.00000 0.00000 0.00001 0.00001 0.00004
32 0.00000 0.00000 0.00000 0.00001
33 0.00000 0.00000 0.00000
34 0.00000 0.00000 0.00000
35 0.00000 0.00000
36 0.00000
37 0.00000

Table 10 Percentage probability of holding a specific HCP value and number of Keycards (with and without trump Q)

One final example:

Probability of holding a weak-two hand

Earlier we calculated the probability of a major weak two hand using only distribution (6322 and 6331) and HCP (5-10) as 2.18%. We can refine the criteria further using this more detailed approach.

Let’s say we define an ‘idealish’ weak-two in a major as:

  • 5-10 HCP
  • 6-card major with two honours
  • no void
  • no second suit (4 or more cards)
  • no singleton honour

The following code can be used to calculate the probability:

"Probability of holding  an 'ideal' 5-10 HCP, 2-honour
weak-two major hand with no singleton honour"
(hand-map
  (fn [vs vi hcp]
    (let [hcnt [0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4]]
      (if (and
            (>= hcp 5) (<= hcp 10)            ; 5-10 HCP
            (or (and (= 6 (vs 0))             ; 6 Spades ...
                     (>= (hcnt (vi 0)) 2))    ; and 2 honours
                (and (= 6 (vs 1))             ; 6 Hearts ...
                     (>= (hcnt (vi 1)) 2)))   ; and 2 honours
            (> (apply min vs) 0)              ; no voids
            (< (second (sort > vs)) 4)        ; 2nd suit < 4
            (every? #(or                      ; for all suits either:
                       (not= 1 (vs %))        ; not a singleton or
                       (zero? (vi %)))        ; no honours
                    (range 4)))
        ["Major weak-two" ""]
        [false false]))))

;=> {["Major weak-two" ""] 1.162334466504511}

So our final result shows this type of hand occurs about 1.16% of the time.

Hopefully, by using these examples, the reader will be able to craft code to find the probability of any particular hand type that may interest them.

Next Article

This article has focussed on the probability of various attributes of a single hand. The next step is to look at characteristics of the two hands of a partnership.

Efficient Recursive Levenshtein (Edit) Distance Algorithm

Efficient Recursive Levenshtein (Edit) Distance Algorithm

Background

Levenshtein Distance is a way to ascribe a numeric distance between two sequences (often characters in a string or word) by counting the minimum number of insertion, deletion and substitution operations required to transform one sequence to the other.

As documented in Wikipedia (and elsewhere) there is an elegant recursive equation to determine the Levenshtein distance as follows:


Levenshtein Distance Equation

If you think of transforming from sequence ‘a’ to sequence ‘b’ the first recursion represents a deletion from the ‘a’ sequence. The second recursion represents an insertion into the ‘b’ sequence, and the last recursion is either a substitution or a match (and skip over) depending on the equality check. The length is incremented in all cases except where there is a match.

When one sequence is exhausted (i.e. length=0) the length of the remaining sequence is added to the result (as either deletions or insertions depending which sequence is left).

Basic Computer Algorithm

The mathematical equation is fairly easily translated into a recursive computing function. The Clojure equivalent if translated literally would be something like:

(defn ld
  "Calculate the Levenshtein distance - basic literal code."
  [va vb i j]
  (cond
    (zero? (min i j)) (max i j)
    :else (let [k (if (= (va i) (vb j)) 0 1)]
            (min (+ (ld va vb (dec i) j) 1)
                 (+ (ld va vb i (dec j)) 1)
                 (+ (ld va vb (dec i) (dec j)) k)))))

(ld (vec " lawn") (vec " flaw") 4 4)  ; => 2

Literal translation of the Levenshtein equation

Note that each sequence is padded with an initial dummy character (blank in this case) to account for the difference between the one-based indexing used in the mathematical equation and the zero-based indexing used in computing. Without this adjustment the indexing gets messy and obscures the relationship with the equation.

A simpler and more idiomatic approach is to work directly with the sequences and avoid the indexing completely with code like this:

(defn ld
  "Calculate the Levenshtein distance - basic idiomatic code."
  [va vb]
  (cond
    (empty? va) (count vb)
    (empty? vb) (count va)
    :else (let [k (if (= (peek va) (peek vb)) 0 1)]
            (min (+ (ld (pop va) vb) 1)
                 (+ (ld va (pop vb)) 1)
                 (+ (ld (pop va) (pop vb)) k)))))

(ld (vec "lawn") (vec "flaw"))  ; => 2

Idiomatic (Clojure) representation of the Levenshtein equation

Both these implementations work and it’s not hard to find many examples of them on the Web (e.g. Rosetta Code) but they scale very poorly.

The solution tree grows by a factor of three for each level and the number of levels varies between the length of the shortest sequence and the sum of the lengths of both sequences. The function has a computing complexity of O(3n) which is essentially useless for anything but the shortest strings.

Some versions of this code employ ‘memorisation’ techniques in an attempt to improve performance. This helps because many nodes in the solution tree are duplicates which would otherwise be calculated over and over again. However memorisation introduces state and detracts for the functional purity of the solution. It also doesn’t address the underlying scaling problem.

Another approach is to use an iterative method based on a matrix representation. This is much more efficient (see below) but it masks the elegance of the original function.

Can we improve performance while maintaining the pure functional style of the equation? Two areas for improvement suggest themselves.

The first is the fact that as you recurse down the solution tree, the distance returned never reduces (i.e. it only gets larger or remains the same). So processing can stop once the result exceeds a previously calculated minimum.

The second is to note that two of the three recursion function calls use the third recursion result as input one recursion later. By passing this result down to the next recursive level, it doesn’t need to be recalculated.

We will look at these two optimisation methods below.

Upper Bound Optimisation

The idea is to pass an upper bound to the lower levels so that further processing can be avoided once that bound is reached. This is similar (but simpler) to alpha-beta pruning in two-person game trees. In this case, we need only a single alpha (or beta) value. It turns out that this approach provides significant pruning of the solution tree while vastly improves performance.

First let’s restructure the code above to pass a ‘running’ result down the tree. The new code looks like this:

(defn ld
  "Calculate the Levenshtein distance - basic with running result."
  [va vb res]
  (cond
    (empty? va) (+ res (count vb))
    (empty? vb) (+ res (count va))
    :else (let [k (if (= (peek va) (peek vb)) 0 1)]
            (min (ld (pop va) vb (+ res 1))
                 (ld va (pop vb) (+ res 1))
                 (ld (pop va) (pop vb) (+ res k))))))

(ld (vec "lawn") (vec "flaw") 0)  ; => 2

Idiomatic Levenshtein distance with a ‘running’ result

Here the initial call needs to pass the starting length of zero. This code doesn’t improve performance but it allows the result to be tested prior to further calls to lower levels.

Because the lower level calls can only ever increase (or keep the same) length, we can stop processing when the result equals (or exceeds) the current known minimum.

The following code introduces a fourth argument which holds the current known minimum. This value is updated after each branch is processed to let the next branch know the current best (minimum) value. Also the ‘substitution and match’ branch has been evaluated first because this is the only branch that can return a zero length increment which makes the ‘pruning’ minimum value more likely to be the lowest. This is equivalent to the heuristics applied is alpha-beta pruning where the player’s moves should be ordered with the likely strongest occurring first as this improves the pruning efficiency.

(defn ld
  "Calculate the Levenshtein distance - upper bound constraint."
  [va vb res minval]
  (cond
    (>= res minval) minval
    (empty? va) (+ res (count vb))
    (empty? vb) (+ res (count va))
    :else (let [k (if (= (peek va) (peek vb)) 0 1)
                r1 (ld (pop va) (pop vb) (+ res k) minval)
                r2 (ld va (pop vb) (+ res 1) (min r1 minval))
                r3 (ld (pop va) vb (+ res 1) (min r1 r2 minval))]
            (min r1 r2 r3))))

(ld (vec "lawn") (vec "flaw") 0 10000)  ; => 2

Levenshtein distance with an upper bound

The code introduces another termination case that tests whether the result (res) equals (or exceeds) the current best minimum (minval). If so, no further processing is performed as it will never improve on the current known minimum. Otherwise the next branch is evaluated with the lowest upper bound from the previous branches being passed on as the new upper bound.

Slightly more polished version

By taking advantage of Clojure’s multiple arity function definitions, we can simplify the call to the function by making the 2-arity function call the 4-arity version behind the scenes. This doesn’t change the functionality at all, it just hides some of the plumbing. The revised version is shown below.

(defn ld
  "Calculate the Levenshtein distance - upper bound constraint."
  ; ------ 2-arity
  ([seqa seqb]
   (let [minval (max (count seqa) (count seqb))]
     (ld (vec seqa) (vec seqb) 0 minval)))
  ; ------ 4-arity
  ([seqa seqb res minval]
   (cond
     (>= res minval) minval
     (empty? seqa) (+ res (count seqb))
     (empty? seqb) (+ res (count seqa))
     :else (let [k (if (= (peek seqa) (peek seqb)) 0 1)
                 r1 (ld (pop seqa) (pop seqb) (+ res k) minval)
                 r2 (ld seqa (pop seqb) (+ res 1) (min r1 minval))
                 r3 (ld (pop seqa) seqb (+ res 1) (min r1 r2 minval))]
             (min r1 r2 r3)))))

(ld "lawn" "flaw")  ; => 2

Upper bound Levenshtein distance

Note that we can set the minval initial value to the longest sequence as this is the worst case length (requiring every character to be replaced).

Performance Improvements

The table below shows the number of nodes processed by the original and bounded versions of the code for some sample sequences of increasing length. Indicative times are also provided but these are not rigorous benchmarks.

Original Bound
Sample Type nodes/sample msec/sample nodes/sample msec/sample
lawn->flaw 1 0.10 13 0.01
Mixed strings (len=5) 841 0.49 32 0.01
Mixed strings (len=6) 4,494 2.51 64 0.02
Mixed strings (len=7) 24,319 13.48 134 0.03
Mixeds strings (len=8) 132,864 73.08 254 0.06
abcdefghi->123456789 731,281 448.00 9841 2.35
a12345678->123456789 731,281 418.00 74 0.02
levenshtein->einstein 1,242,912 763.00 264 0.07
levenshtein->meilenstein 22,523,360 12,992.00 365 0.10

It is clear that the bounded version is a substantial improvement over the original version. This is most obvious as the length of the strings increase. However, the bounded version itself can fluctuate significantly depending on the input values as seen by the two highlighted lines in the table above. Here the input strings are the same length but the nodes processed vary by a factor of over 100.

Reuse of the ‘substitution’ value

The second optimisation approach is revealed by considering the following diagram showing two levels of recursion for the original Levenshtein equation.


Levenshtein Distance Recursion

The (i-1,j-1) term, also known at the substitution term, in the first recursion is also used by the other two terms at the next level down. So some additional optimisation can be achieved by preserving this value and passing it down to the next level. As only four new terms are calculated, instead of six, there should be a modest but noticeable improvement.

The modified code adds two new parameters that represent the ‘left’ (i-1,j) and ‘right’ (i,j-1) substitution value previously calculated. The code starts to get a little more opaque but the main theme is still relatively clear.

(defn ld
  "Calculate the Levenshtein distance - upper bound constraint
  and reuse of the 'substitute' term value."
  ([seqa seqb]
   (let [minval (max (count seqa) (count seqb))]
     (ld (vec seqa) (vec seqb) 0 minval nil nil)))
  ;
  ([va vb res minval r2 r3]
  (cond
    (>= res minval) minval
    (empty? va) (+ res (count vb))
    (empty? vb) (+ res (count va))
    :else
    (let [k (if (= (peek va) (peek vb)) 0 1)
          r1 (ld (pop va) (pop vb) (+ res k) minval nil nil)
          r2 (if r2 r2 (ld (pop va) vb (+ res 1) (min r1 minval) nil r1))
          r3 (if r3 r3 (ld va (pop vb) (+ res 1) (min r1 r2 minval) r1 nil))]
      (min r1 r2 r3)))))

(ld "lawn" "flaw")  ; => 2

Performance

The table below compares the bounded, and the bounded and reuse versions.

Bound Bound and reuse
Sample Type nodes/sample msec/sample nodes/sample msec/sample
lawn->flaw 13 0.01 13 0.01
Mixed strings (len=5) 32 0.02 24 0.01
Mixed strings (len=6) 64 0.02 42 0.01
Mixed strings (len=7) 134 0.05 76 0.03
Mixed strings (len=8) 254 0.10 126 0.04
123456789->abcdefghi 9,841 3.15 2377 0.78
123456789->a12345678 53 0.02 53 0.02
levenshtein->einstein 264 0.11 136 0.05
levenshtein->meilenstein 365 0.13 205 0.06

There is a small additional improvement by reusing the ‘substitution’ value. This is most noticeable where the bounded version works less well (highlighted rows).

Conclusion

The ‘standard’ recursive function to compute the Levenshtein distance is elegant but scales very badly, O(3n), which makes it impractical (and dangerous) for most applications. By adding an upper-bound constraint the recursive function can be substantially improved. Some further improvement is achieved by reusing the ‘substitution’ value. These improvements arise by significantly reducing the number of nodes in the solution tree that need to be processed.

Iterative version

Levenshtein distance can be represented in a matrix or grid format. One sequence is laid out at the top, horizontally, and the other is laid out to the left, vertically. Each is prepended with a notional ‘null’ entry and the initial distance (0, 1, 2, …) from this null entry is entered in the first row and first column of the grid.

From this starting position the grid is filled in cell by cell, left to right, top to bottom. The cell values represent the Levenshtein distance between the two sub-sequences – one from the left to the current cell’s horizontal location and the other from the top to the current cells vertical location. The ‘rule’ for determining the value of the next cell is to take the minimum of:

  1. The cell immediately above it plus one
  2. The cell immediately left of it plus one
  3. The cell immediate above and left of it plus one if the corresponding sequence entries are different, or zero if they are the same

When the grid is completed, the bottom right value is the Levenshtein distance between the two sequences. An example is shown in the following diagram (“?” shows the cell to be determined, blue cells are the ones used as input, along with the highlighted sequence entries which are tested for equality).


Levenshtein Distance Equation

There are clearly strong parallels here between the recursive equation and the grid construction.

The big difference between the methods is that the grid construction is at worst O(n2). The grid method also lends itself to an iterative implementation. A simple Clojure iterative version is shown below. It uses two row variables rx and ry that progressively move down the grid. The ry row is built up from the rx row above it, and, its own last lefthand value. Once completed, the rx row is replaced with the ry row and the process is repeated.

(defn ld-grid-iter
  "Calculate the Levenshtein (edit) distance iteratively using
  a grid representation"
  [seqa seqb]
  (let [va (vec seqa)
        vb (vec seqb)
        clen (inc (count va))
        rlen (inc (count vb))
        rx (vec (range clen))]
    (loop [r 1, c 1, rx rx, ry (assoc rx 0 1)]
      (if (= r rlen)
        (peek rx)
        (if (= c clen)
          (recur (inc r) 1 ry (assoc ry 0 (inc r)))
          (let [k (if (= (va (dec c)) (vb (dec r))) 0 1)
                ry (assoc ry c (min (+ (rx c) 1)             ; above
                                    (+ (ry (dec c)) 1)       ; left
                                    (+ (rx (dec c)) k)))]    ; diagonal
            (recur r (inc c) rx ry)))))))

(ld-grid-iter "lawn" "flaw")  ; => 2

Iterative grid version of Levenshtein distance

The performance comparison of the ‘bounded and reuse’ recursive version developed above and the iterative grid version for the same sample set is shown in the following table.

Bound and reuse Iterative grid
Sample Type nodes/sample msec/sample nodes/sample msec/sample
lawn->flaw 13 0.01 16 0.01
Mixed strings (len=5) 24 0.01 25 0.01
Mixed strings (len=6) 42 0.02 36 0.01
Mixed strings (len=7) 76 0.02 49 0.01
Mixed strings (len=8) 126 0.04 64 0.01
123456789->abcdefghi 2,377 0.75 81 0.01
123456789->a12345678 53 0.01 81 0.02
levenshtein->einstein 136 0.11 88 0.03
levenshtein->meilenstein 205 0.08 121 0.03

In general, the iterative grid version outperforms the recursive version, as you would expect, but the recursive version holds up surprising well at least for typical word-length sequences (less than around a length of 12).

There is scope to optimise the iterative version using upper bounds in a similar way to the recursive version although this is not explored here. And of course it is possible to turn the iterative grid version into a recursive grid version for the functional purist with code like:

(defn ld-grid-recursive
  "Calculate the Levenshtein (edit) distance recursively using
  a grid representation"
  ([seqa seqb]
   (ld-iter-recursive seqa seqb 1 (vec (range (inc (count seqa))))))
  ;
  ([seqa seqb r vx]
  (if (empty? seqb)
    (peek vx)
    (let [r-fn (fn [v [a x0 x1]]
                 (let [k (if (= a (first seqb)) 0 1)]
                   (conj v (min (+ x1 1)           ; above
                                (+ (peek v) 1)     ; left
                                (+ x0 k)))))       ; diag
          vx (reduce r-fn [r] (map vector seqa vx (rest vx)))]
      (ld-grid-recursive seqa (rest seqb) (inc r) vx)))))

(ld-grid-recursive "lawn" "flaw")  ; => 2

Recursive grid version of Levenshtein distance

High Quality HTML Tables using Text Only Layouts

High Quality HTML Tables using Text Only Layouts

Or … How to create a perfect table

Tables are a powerful way to present information. HTML provides a comprehensive set of elements to construct them, and CSS provides extensive formatting capability. However, in reality, tables are fiddly to get right. It is rare that common or generic styling works for all tables. Usually each table needs some tweaking.

There are many minor irritations that blight the perfect table:

  • column or row font styles, sizes or weights are incorrect
  • table or column widths cause unwanted wrapping or whitespace
  • cell data is too crowded or wrongly aligned
  • colours or borders need adjustment
  • column or row spanning is required
  • cell numeric format is inconsistent

These problems are exacerbated when you don’t have full control over the table layout, such as when it is rendered in a framework with its own defaults (e.g. themes), or when it is difficult to modify the associated CSS directly.

The following is a proposed texttab specification to define and style a table using a text only format. A basic Clojure implementation is also provided.

The specification uses inline CSS styling to provide a high degree of flexility and precision over the table’s appearance, albeit at the cost of additional styling text overhead. Ideally it is used to adjust an existing table’s base styles to make small adjustments often required by particular tables.

It is designed to be preprocessed into inline HTML that is suitable for Markdown or similar post processing.

The main features include:

  • simple data representation
  • control of base HTML element styles table, th, td, and tr
  • setting styles for entire table rows and columns
  • setting styles for individual cells
  • support for colspan and rowspan
  • support for printf-style number format strings
  • support for simple column calculations like sum and average

Two quick examples show some of the capabilities available to construct and style tables. The plain text code used to define the tables is shown first, followed by the resulting table as rendered by the browser.

	table {width "auto" font-size "6pt"}
	td {height "20px" padding "1px" vertical-align "top"}
	^b {background-color "#808080"}
	td-width | "20px" | *
	td | 1  |    | 2  |
	td |    | ^b |    | ^b
	td | 3  |    |    | 4
	td |    | ^b | 5  |  
1 2
3 4
5

The following is a more complex and somewhat contrived table that shows many of the styling techniques. The details are explained in the Specification section below.

	table {width "auto"}
	^p-r {padding "4px 16px 4px 4px"}
	^p-l {padding "4px 4px 4px 16px"}
	| Longer style definitions, like ^1 below, can be split
	| by repeating the definition as the styles are merged
	^1 {background-color "#dddddd" font-weight "bold" format "%.1f"}
	^1 {color black}
	^bt {border-top "2px solid #808080"}
	^lb {background-color "#ddddff"}
	^db {background-color "#bbbbff"}
	^r {background-color "#ffcccc"}
	^c2 {colspan "2"}
	^r2 {rowspan "2" vertical-align "middle"}
	td-text-align | "left" | "right" | *
	td-color | "blue"
	td-^ |    ^p-r   | ^p-l | *
	th   |Location^r2| Day^c2^lb | ^ |Night^c2^db| ^
	th^1 |    ^      |low^lb |high^lb|low^db|high^db
	td^bt| Site #147 |  17.5 |  24.0 |  11.6 | 13.1 
	td   | Site #179 |  15.9 |  25.4 |  4.1^r| 11.7
	td   | Site #204 |  18.2 |  25.7 |  10.6 | 12.9
	td^1^bt| Average |^^col-avg|^^col-avg|^^col-avg^r|^^col-avg
Location Day Night
low high low high
Site #147 17.5 24.0 11.6 13.1
Site #179 15.9 25.4 4.1 11.7
Site #204 18.2 25.7 10.6 12.9
Average 17.2 25.0 8.8 12.6

Being able to selectively apply the full range of CSS styling to rows, columns and cells makes it easy to produce visually appealing tables.

Texttab Specification (Version 1.1)

The texttab specification describes the data and styling for a web-based (HTML and CSS) table definition in a textual format. The specification is intended to be converted from text to HTML table elements and inline CSS styles suitable for rendering by a web browser.

This specification is not formal in a technical sense, but hopefully clear and concise enough to allow any interested party to implement it fairly consistently.

The tables constructed from the specification only use four standard HTML elements: table, tr, th and td. Standard CSS styles are added to these elements using the style attribute. Styles are derived from four possible sources:

  1. Base element style
  2. Column style
  3. Row style
  4. Cell style

The specification uses two characters with special meaning:

  • Vertical bar (|) as a column separator
  • Caret (^) to specify and apply reference styles

These characters can be “escaped” using a backslash (\) if they are required as table content.

The specification assumes each data row and style definition is on a seperate line. As style definitions are aggregated, long style definitions can be split and repeated on separate lines.

There are two data definitions and three styling definitions. The data definitions define the actual cell values while the styling affects their appearance.

Data definition

The data definitions specify the row type followed by the cell values that make up the columns. The row type is either ‘th‘ or ‘td‘ reflecting the HTML element that will be used to construct the cells in the row.

Row data is define as:

	th | data1 | data2 ...
	td | data1 | data2 ...

For example:

	th | Team      | Played | Won | Score
	td | Blue Mist | 4      | 1   | 34.6
	td | Wayne's Warriors| 3 | 3 | 103.5
	td | Rabbits   | 3      | 0    | 0.0

There is no requirement to align the data columns other than to aid readability.

Blank cells

Blank cells are represented by zero or more spaces. A row ending with a vertical bar (|) has an implied blank cell to its right.

Some examples of blank cells are shown below (the first two rows are identical, and all rows have four table columns).

	th | a |   | c  | d
	td |a|| c|d
	td |   | b | c |

Blank cells can contain one or more reference styles (see below). The following four cells are all blank but two have associated styles.

	td |   | ^1 | ^1^bg |

Inline HTML elements

The specification allows inline (non-escaped) HTML as cell content. Inline HTML provides further formatting options within a table cell including:

  • images <img src="...">
  • links <a href="...">...</a>
  • markup (e.g. like superscript <sup>1</sup>).

Example:

	table {width "40%"}
	td {vertical-align "top"}
	th | Type | Item
	td | Image | <img src="http://www.occasionalenthusiast.com/wp-content/uploads/2016/04/ttimage.jpg">
	td | Link | <a href="http://www.google.com">Google</a>
	td | Superscript | Hello World<sup>1</sup>
	td | Escaped | Hello World\<sup\>1\</sup\>
Type Item
Image
Link Google
Superscript Hello World1
Escaped Hello World<sup>1</sup>

The implementation may provide an implementation option (see below) to disable inline HTML.

Where inline HTML is enabled, the ‘<‘ and ‘>‘ characters can be escaped using a backslash ‘\<‘ and ‘\>‘ respectively.

Style definitions

There are three styling definitions:

  • Element styling (i.e. table, tr, th or td)
  • Named column styling (applies to all the cells in a particular table column)
  • Reference styling (applies to specific rows, columns and cells)

All styles aggregate and later style definitions replace (override) earlier styles with the same row type and style name.

Element styles

Element styles apply to the standard HTML table elements and are global in the sense they apply across the whole table. They are defined as:

	<element> {style1 "value1" style2 "value2" ...}
	<element> {style1 "value1", style2 "value2", ...}

<element> is one of the following four HTML table element names: table, tr, th and td.

Commas between the style/value pairs are optional (as in Clojure).

For example:

	table {font-family "sans-serif" font-size "9pt"}
	th {background-color "#cceeee"}

Reference styling

Reference styling defines a style that can be used to style rows, columns and cells. A reference style is defined by:

	^<style-ref> {style1 "value1" style2 "value2" ... }
	^<style-ref> {style1 "value1", style2 "value2", ... }

<style-ref> can be any case-sensitive string of characters (at least a-z, A-Z, 0-9, _ and -) excluding whitespace and the caret (^) character. Generally it is a short string, or a single character, as it is applied by appending ^<style-ref> to the styling target.

To style an entire data row with a reference style, append it to the row type at the start of the row:

	th^<style-ref> | data1 | data2 ...
	td^<style-ref1>^<style-ref2> | data1 | data2 ...

Cell styling is similar but the style reference is appended to the cell data:

	th | data1^<style-ref> | data2 ...
	td | data1 | data2^<style-ref1>^<style-ref2> ...

In both cases, multiple styles can be applied to the same target by appending additional reference styles as required.

Examples:

	^1 {background-color "#eeeeee"}
	^2 {color "red", font-weight "bold"}
	^bd {border "2px solid #cc0000"}
	
	th^1^2| data1 | data2 | data3
	td^1 | data1 | data2^2 | data3
	td   | data1^2^bd | data2 | data3^bd

Column styling using reference styles is discussed in the next section.

Column styles

Column styling applies to all the cells in a particular table column for the row type specified (either th or td). There are two varieties of column styling, named and reference.

Named column styles are defined by:

	th-<style-name> | "value1" | "value2" ...
	td-<style-name> | "value1" | "value2" ...
	t*-<style-name> | "value1" | "value2" ...

The styles starting with “th-” only apply to th data rows, while those starting with “td-” only apply to td data rows. Column styles starting with “t*” apply to all rows regardless of their type.

Named styles are particularly useful when many columns require a different value.

Reference column styles are defined in a similar way only using defined reference styles:

	th-^ | ^<style-ref1> | ^<style-ref2> ...
	td-^ | ^<style-ref1> | ^<style-ref2> ...
	t*-^ | ^<style-ref1> | ^<style-ref2> ...

As with named styles the reference styles apply to th, td or both respectively. Multiple reference styles can be used in one column definition:

	th-^ | ^<style-ref1>^<style-ref2> | ^<style-ref2> ...

For both column styles varieties, the last style value can be an asterisk character (*) to denote that the previous style value/reference will be propagated across all the remaining columns.

Style column values can be left blank where no style is required and there is no need to specify values for all remaining columns. Remaining columns without a style value are assumed to have no column style.

Some examples of column styles:

	th-text-align | "left" | "center" | *
	td-text-align | "left" | | | "right"
	t*-color | "blue"
	td-^ | ^1 |  |  | ^2 | ^1^3
	td-^ | ^left^bold | ^right | *

Style rows can be intermingled with data rows to change the column styling throughout the table.

For example:

	table {font-size "20px"}
	td {width "24px" height "24px" text-align "center" vertical-align "middle"}
	td {padding "0px" border "none"}
	^1 {background-color "#cceecc"}
	^2 {background-color "#aaccaa"}
	td-^|^1|^2|^1|^2|^1|^2|^1|^2
	td  |&#9814;|  |  |  |&#9818;|  |  |
	td-^|^2|^1|^2|^1|^2|^1|^2|^1
	td  |  |  |  |  |  |  |  |
	td-^|^1|^2|^1|^2|^1|^2|^1|^2
	td  |  |  |  |  |&#9812;|  |  |
	td-^|^2|^1|^2|^1|^2|^1|^2|^1
	td  |  |  |  |  |  |  |  |
	td-^|^1|^2|^1|^2|^1|^2|^1|^2
	td  |  |  |  |  |  |  |  |
	td-^|^2|^1|^2|^1|^2|^1|^2|^1
	td  |  |  |  |  |  |  |  |
	td-^|^1|^2|^1|^2|^1|^2|^1|^2
	td  |  |  |  |  |  |  |  |
	td-^|^2|^1|^2|^1|^2|^1|^2|^1
	td  |  |  |  |  |  |  |  |

Colspan and Rowspan

CSS does not directly support colspan and rowspan but for this specification they are simply treated the same as other styles. The implementation strips them out and applies them as separate attributes.

For example:

	^cs2 {colspan "2" background-color "LightSkyBlue"}
	
	t*-background-color | | | | "Thistle"
	td-width | "50px" | *
	th | head1 | head2^cs2 | ^ | head4
	td | data1 | data2 | data3 | data4
head1 head2 head4
data1 data2 data3 data4

A single carat (^) character is used to indicate a “placeholder” for cells that will be overlaid by a row or column span. These cells are deleted from the row once styles are assigned to make space for the span. The placeholder cells maintain the integrity of the table grid structure so that column styles and calculations work as expected, as in the above example.

Numeric Formatting

In a similar manner to colspan and rowspan, the non-CSS style format can be used to render numeric data formatted by the standard printf style format string.

For example:

	td {font-family "monospace"}
	^m {format "$%,.2f" text-align "right"}
	td-^|       | ^m    | *
	th  | Item | Q1 | Q2
	td  | #0001 | 130 | 141.2
	td  | #0002 | 1550.50 | 1661.236
Item Q1 Q2
#0001 $130.00 $141.20
#0002 $1,550.50 $1,661.24