Hedging Toward Skill

by Douglas Zare
23 August 2000

Hedging Toward Skill

by Douglas Zare

Backgammon is a game of luck and skill. To a casual observer, it may appear to be all luck. As one gains more skill and familiarity with the game, the depth of skill required to play well becomes increasingly clear. The luck is still there, though, much to our joy and frustration.

Sometimes one wants to strip away the luck. Is move A better than move B? Is player X stronger than player Y? A proper respect for the luck in the game is needed. Below, we will consider a method for cancelling most of the luck in backgammon, and will apply it to analyze a game between the computer programs Jellyfish and Snowie, both set on levels much stronger than I am.

I call the following equation the fundamental equation of games of luck and skill:

Final - Initial = Net Luck + Net Skill

Final refers to the final score. This might be +1 or -4 for a money game, or 100% mwc (match winning chances) or 0% mwc for a match.
Initial refers to the starting equity or mwc of the situation considered.
Net Luck, as outlined in "A Measure of Luck" has average value 0 on each roll. It also has average value 0 in each game or match.
Net Skill is the difference in the total magnitude of the errors of the players when compared with technically perfect play.

Variance Reduction in Rollouts

Variance reduction for rollouts is described in more detail in David Montgomery's article in the February 2000 issue of Gammonline and in a preprint by Fredrik Dahl, "Variance reduction for Markov processes using state space evaluation for control variates." It is implemented in Jellyfish and Snowie. I summarize it for comparison.

When rolling out a position (comparing play A with play B), we start with a position (or two) whose equity we do not know. We might have Jellyfish play both sides many times, so we hope that the Net Skill is 0, that Jellyfish makes errors of equal magnitude from both sides of a position. This may be unreasonable if one side's choices are easy and the other side's are difficult, and must be reassessed with each rollout. Let us rearrange the fundamental equation under the assumption that Net Skill is 0: Initial = Final - Net Luck.

After rolling a position out, the final result is clear, but what we want is different by the Net Luck. Over a long rollout, the average Net Luck will be close to 0, but we can do better than that. One way is to compute an Estimated Net Luck fairly, and subtract that from the result of the rollout. The estimate Initial ~ Final - Estimated Net Luck will be off by the difference between the actual Net Luck and the Estimated Net Luck, and with an accurate, unbiased estimate of luck, we will get an accurate, unbiased estimate of the equity of the position.

Variance Reduction of Skill

This is suggested in the above preprint by Fredrik Dahl.

Suppose two excellent players play. To find the Net Skill displayed, we could use Snowie to estimate the errors made by each side. Unfortunately, that method is biased. Suppose one of the players is Snowie: Snowie does not play perfectly, but it would rate its own play as perfect, and would reward those whose play resembles Snowie's rather than perfect play. Instead, let us consider the fundamental equation applied to a game. The initial position is even (we don't know who will win the first roll) so the Initial equity is 0. Thus, we can rewrite the equation as Net Skill = Final - Net Luck.

The final result of a rollout is a fair estimate for the initial equity, but often not a good enough estimate. It would completely ignore the effect of luck, and would be incorrect by the average Net Luck. The idea of variance reduction is to compute an Estimated Net Luck fairly, and subtract that from the final result instead. This is off by the average amount of the Net Luck - Estimated Net Luck.

Snowie estimates the luck in a roll by estimating the equity of the best play it sees after rolling, and subtracting the equity of the position before rolling. This is a good estimate, and is equivalent to measuring skill by summing up the errors compared with what Snowie thinks is the best play. I have found this to be tremendously helpful, but because Snowie does not estimate the equity perfectly, this method is biased, and unsuitable for analyzing matches between players close to Snowie's level or in positions where Snowie is less reliable. However, one can fix any estimate of match winning chances to produce an unbiased estimate. An evaluation as good as Snowie's may be corrected to eliminate most of the luck in backgammon without bias.

Instead of comparing the evaluation of the apparently best play after rolling with the estimated equity before rolling, just ask whether the roll was above average or below average. This ensures that the estimated luck will average to 0. Example: Suppose Snowie currently evaluates a position as worth 0.2, but precisely half of the rolls would leave a position Snowie believes is worth 1 and half of the rolls would leave a position Snowie believes is worth -1. Snowie's estimate of the luck if one rolls well is +0.8. Since the average is 0, the unbiased estimate should be that the luck is +1. To be fair, one must evaluate the initial position one ply deeper than the position after rolling.

Jellyfish Level 7 time factor 1000 vs Snowie 3 3-ply Tiny, 20%

The following is a 1-point match between Snowie 3 (3-ply, tiny, 20%) and Jellyfish 3 (Level 7, 1000). This was the first match I tried. Most plays are straightforward, but not all: Jellyfish primes Snowie, obtains a racing lead as Snowie's board crashes, and bears in safely. Afterwards, I performed a variance reduction using Snowie 3 set on 1-ply evaluation.

All of the evaluations are in the unusual units of match equity, which is +1 for a won match and -1 for a lost one. The perspective is always that of Jellyfish, so a bad roll for Snowie shows up as positive luck. Note that the evaluation for a given move does not always agree with the average for the next move, even when these correspond to the same position. Average is the higher ply evaluation.

JF 1: 5-2 13/8 24/22
Average/Evaluation/Luck: 0.000 / 0.012 / +.012

JF 2: 3-3 13/10*(2) 8/5(2)
A/E/L: 0.054 / 0.284 / +.230

JF 3: 4-2 24/20 22/20
A/E/L: 0.255 / 0.266 / +.011

JF 4: 3-2 13/10 13/11
A/E/L: 0.308 / 0.257 / -.051



Red to play 3-2 B: 137 W: 154

JF 5: 3-2 11-8 6-4
SW Tiny, 20% and SW 1-ply prefer 11/8 10/8, but SW Huge, 100% agrees with this play.
A/E/L: 0.282 / 0.238 / -.044

JF 6: 3-1 10/7 8/7
A/E/L: 0.307 / 0.261 / -.046



Red to play 4-1 B: 128 W: 136

JF 7: 4-1 20/15*
Holding the anchor with 8/4 8/7 is preferred by SW Huge, 100% (by 0.1% mwc) and by Tiny, 20%, though 1-ply rates them as equal.

A/E/L: 0.362 / 0.238 / -.124

JF 8: 4-1 B/20
A/E/L: 0.161 / 0.284 / +.123

JF 9: 1-1 15/13* 10/9(2)
A/E/L: 0.391 / 0.510 / +.119



Red to play 2-1 B: 135 W: 147

JF 10: 2-1 13/11 6/5
SW Huge, 100% prefers 6/4* 6/5 by 0.06% mwc, though Tiny, 20% agrees with not hitting. 1-ply rates them as equal.

A/E/L: 0.455 / 0.464 / +.009