glicko2.gno

  1package glicko2
  2
  3import (
  4	"math"
  5)
  6
  7// http://www.glicko.net/glicko/glicko2.pdf
  8
  9const (
 10	// Step 1.
 11	// Determine a rating and RD for each player at the onset of the rating period. The
 12	// system constant, τ , which constrains the change in volatility over time, needs to be
 13	// set prior to application of the system. Reasonable choices are between 0.3 and 1.2,
 14	// though the system should be tested to decide which value results in greatest predictive
 15	// accuracy. Smaller values of τ prevent the volatility measures from changing by large
 16	// amounts, which in turn prevent enormous changes in ratings based on very improbable
 17	// results. If the application of Glicko-2 is expected to involve extremely improbable
 18	// collections of game outcomes, then τ should be set to a small value, even as small as,
 19	// say, τ = 0.2.
 20	GlickoTau = 0.5
 21
 22	GlickoInitialRating     = 1500
 23	GlickoInitialRD         = 350
 24	GlickoInitialVolatility = 0.06
 25
 26	glickoScaleFactor = 173.7178
 27)
 28
 29type PlayerRating struct {
 30	ID address
 31
 32	Rating           float64
 33	RatingDeviation  float64
 34	RatingVolatility float64
 35
 36	// working values, these are referred to as μ, φ and σ in the paper.
 37	wr, wrd, wrv float64
 38}
 39
 40func NewPlayerRating(addr address) *PlayerRating {
 41	return &PlayerRating{
 42		ID:               addr,
 43		Rating:           GlickoInitialRating,
 44		RatingDeviation:  GlickoInitialRD,
 45		RatingVolatility: GlickoInitialVolatility,
 46	}
 47}
 48
 49// RatingScore is the outcome of a game between two players.
 50type RatingScore struct {
 51	White, Black address
 52	Score        float64 // 0 = black win, 0.5 = draw, 1 = white win
 53}
 54
 55func getRatingScore(scores []RatingScore, player, opponent address) float64 {
 56	for _, score := range scores {
 57		if score.White == player && score.Black == opponent {
 58			return score.Score
 59		}
 60		if score.Black == player && score.White == opponent {
 61			return 1 - score.Score
 62		}
 63	}
 64	return -1
 65}
 66
 67func UpdateRatings(source []*PlayerRating, scores []RatingScore) {
 68	// step 2: assign working wr/wrd/wrv
 69	for _, player := range source {
 70		player.wr = (player.Rating - GlickoInitialRating) / glickoScaleFactor
 71		player.wrd = player.RatingDeviation / glickoScaleFactor
 72		player.wrv = player.RatingVolatility
 73	}
 74
 75	for _, player := range source {
 76		// step 3: compute the quantity v. This is the estimated variance of the team’s/player’s
 77		// rating based only on game outcomes
 78		// step 4: compute the quantity ∆, the estimated improvement in rating
 79		v, delta, competed := glickoVDelta(player, source, scores)
 80
 81		newRDPart := math.Sqrt(player.wrd*player.wrd + player.wrv*player.wrv)
 82		if !competed {
 83			// fast path for players who have not competed:
 84			// update only rating deviation
 85			player.RatingDeviation = newRDPart
 86			player.wr, player.wrd, player.wrv = 0, 0, 0
 87			continue
 88		}
 89
 90		// step 5: determine the new value, σ′, of the volatility.
 91		player.wrv = glickoVolatility(player, delta, v)
 92		// step 6 and 7
 93		player.wrd = 1 / math.Sqrt(1/v+1/(newRDPart*newRDPart))
 94		player.wr = player.wr + player.wrd*player.wrd*(delta/v)
 95
 96		// step 8
 97		player.Rating = player.wr*glickoScaleFactor + 1500
 98		player.RatingDeviation = player.wrd * glickoScaleFactor
 99		player.RatingVolatility = player.wrv
100		player.wrv, player.wrd, player.wr = 0, 0, 0
101	}
102}
103
104func glickoVDelta(player *PlayerRating, source []*PlayerRating, scores []RatingScore) (v, delta float64, competed bool) {
105	var deltaPartial float64
106	for _, opponent := range source {
107		if opponent.ID == player.ID {
108			continue
109		}
110		score := getRatingScore(scores, player.ID, opponent.ID)
111		if score == -1 { // not found
112			continue
113		}
114		competed = true
115
116		// Step 3
117		gTheta := 1 / math.Sqrt(1+(3*opponent.wrd*opponent.wrd)/(math.Pi*math.Pi))
118		eMu := 1 / (1 + math.Exp(-gTheta*(player.wr-opponent.wr)))
119		v += gTheta * gTheta * eMu * (1 - eMu)
120
121		// step 4
122		deltaPartial += gTheta * (score - eMu)
123	}
124	v = 1 / v
125	return v, v * deltaPartial, competed
126}
127
128const glickoVolatilityEps = 0.000001
129
130// Step 5
131func glickoVolatility(player *PlayerRating, delta, v float64) float64 {
132	aInit := math.Log(player.wrv * player.wrv)
133	A := aInit
134	var B float64
135	rdp2 := player.wrd * player.wrd
136	if delta*delta > rdp2+v {
137		B = math.Log(delta*delta - rdp2 - v)
138	} else {
139		k := float64(1)
140		for ; glickoVolatilityF(A-k*GlickoTau, aInit, rdp2, delta, v) < 0; k++ {
141		}
142		B = A - k*GlickoTau
143	}
144	fA, fB := glickoVolatilityF(A, aInit, rdp2, delta, v), glickoVolatilityF(B, aInit, rdp2, delta, v)
145	for math.Abs(B-A) > glickoVolatilityEps {
146		C := A + ((A-B)*fA)/(fB-fA)
147		fC := glickoVolatilityF(C, aInit, rdp2, delta, v)
148		if fC*fB <= 0 {
149			A, fA = B, fB
150		} else {
151			fA = fA / 2
152		}
153		B, fB = C, fC
154	}
155	return math.Exp(A / 2)
156}
157
158// rdp2: player.rd, power 2
159func glickoVolatilityF(x, a, rdp2, delta, v float64) float64 {
160	expX := math.Exp(x)
161	return (expX*(delta*delta-rdp2-v-expX))/(2*pow2(rdp2+v+expX)) -
162		(x-a)/(GlickoTau*GlickoTau)
163}
164
165func pow2(f float64) float64 { return f * f }