I like Chess, I like Math, and I like PL/SQL – implementing a chess rating algorithm in pl/sql satisfies three itches in one.
The Glicko system was invented by Dr. Mark Glickman in 1995 as a way of rating players and it, along with its successor Glicko-2, have been adopted in a variety of online chess servers such as in chess.com, fresschess.org, and lichess.org. The system is game-agnostic though and is used for rating players in other games such as Go at online-go.com and the card game Dominion at dominion.games.
Dr. Glickman has released both Glicko and Glicko-2 algorithms to the public domain.
The main idea of the Glicko systems is not just the rating itself, but also how much that rating changes. Thus each player also has measure of confidence in how accurate the rating is. The Glicko-2 system is further enhanced by the introduction of volatility. Thus a player might be rated 1500 with a low deviation value of 10; implying the player has a 95% confident the player is rated between 1490 and 1510. That would apply in either system.
The Glicko-2 volatility is an attempt to measure external uncertainty in the other two numbers. The volatility can vary by game and host of each implementing system but the general idea is a player that is playing often and is rated 1500 should have a reliable rating with low deviation. If that player then takes an extended break from the game, it’s not certain that rating is still reliable when the player returns. This absence means the rating is more volatile and thus the previously low deviation is adjusted to allow for greater changes up or down in the rating based on new game results.
Both Glicko systems are described in papers found at http://www.glicko.net/glicko.html. I have intentionally named many of my variables and functions to follow the names presented in Glickman’s description. Thus you will find v_tau, big_e, v_big_a, v_big_c, v_illinois, etc. While these don’t necessarily follow my normal coding style; my hope is this pattern will make it easier to follow along in my code when reading the source paper. I found them helpful in checking my implementation was true to the documentation.
The Glicko2 package follows. It has no dependencies on other objects except for DBMS_OUTPUT which is used in the example code to display the rating changes.
CREATE OR REPLACE PACKAGE glicko2
AS
-- Based on Glicko-2 system by Professor Mark E. Glickman, Boston University, March 22, 2022
-- http://www.glicko.net/glicko/glicko2.pdf
--
--
-- PL/SQL Implementation by Sean D. Stuber
--
--
-- .///.
-- (0 o)
---------------0000--(_)--0000---------------
--
-- Sean D. Stuber
-- sean.stuber@gmail.com
--
-- oooO Oooo
--------------( )-----( )---------------
-- \ ( ) /
-- \_) (_/
TYPE player_rec IS RECORD
(
id INTEGER,
rating NUMBER,
deviation NUMBER,
volatility NUMBER,
mu NUMBER,
phi NUMBER,
g_of_phi NUMBER
);
TYPE game_rec IS RECORD
(
player1 INTEGER,
player2 INTEGER,
result INTEGER -- 0=draw, 1=player1 wins, 2=player2 wins
);
TYPE player_tab IS TABLE OF player_rec;
TYPE game_tab IS TABLE OF game_rec;
PROCEDURE display_player(p_player IN player_rec);
FUNCTION game_score(p_games IN game_tab, p_player IN INTEGER, p_opponent IN INTEGER)
RETURN NUMBER;
PROCEDURE set_tau(p_tau IN NUMBER);
FUNCTION get_tau
RETURN NUMBER;
FUNCTION initialize_player(p_id IN INTEGER,
p_rating IN NUMBER DEFAULT 1500,
p_deviation IN NUMBER DEFAULT 350,
p_volatility IN NUMBER DEFAULT 0.06)
RETURN player_rec;
FUNCTION estimated_variance(p_player IN player_rec, p_players IN player_tab)
RETURN NUMBER;
FUNCTION estimated_delta(p_player IN player_rec, p_players IN player_tab, p_games IN game_tab)
RETURN NUMBER;
FUNCTION new_volatility(p_player IN player_rec, p_delta IN NUMBER, p_variance IN NUMBER)
RETURN NUMBER;
FUNCTION new_rating(p_player IN player_rec,
p_volatility IN NUMBER,
p_variance IN NUMBER,
p_players IN player_tab,
p_games IN game_tab,
p_tau IN NUMBER DEFAULT NULL)
RETURN player_rec;
PROCEDURE update_all_players(p_players IN OUT player_tab, p_games game_tab, p_tau IN NUMBER DEFAULT NULL);
PROCEDURE example;
END;
CREATE OR REPLACE PACKAGE BODY glicko2
AS
g_tau NUMBER := 0.5;
c_glicko_factor NUMBER := 173.7178;
c_convergence_tolerance NUMBER := 0.000001;
PROCEDURE display_player(p_player IN player_rec)
IS
BEGIN
DBMS_OUTPUT.put_line('-------------------------');
DBMS_OUTPUT.put_line('ID: ' || p_player.id);
DBMS_OUTPUT.put_line('rating: ' || p_player.rating);
DBMS_OUTPUT.put_line('deviation: ' || p_player.deviation);
DBMS_OUTPUT.put_line('volatility: ' || p_player.volatility);
-- Probably don't need/want to see these unless debugging
-- DBMS_OUTPUT.put_line('mu: ' || p_player.mu);
-- DBMS_OUTPUT.put_line('phi: ' || p_player.phi);
-- DBMS_OUTPUT.put_line('g_of_phi: ' || p_player.g_of_phi);
DBMS_OUTPUT.put_line('-------------------------');
END display_player;
PROCEDURE set_tau(p_tau IN NUMBER)
IS
BEGIN
g_tau := p_tau;
END set_tau;
FUNCTION get_tau
RETURN NUMBER
IS
BEGIN
RETURN g_tau;
END get_tau;
FUNCTION g(p_phi IN NUMBER)
RETURN NUMBER
IS
c_pi CONSTANT NUMBER := ACOS(-1);
BEGIN
RETURN 1 / SQRT(1 + (3 * p_phi ** 2) / c_pi ** 2);
END g;
FUNCTION initialize_player(p_id IN INTEGER,
p_rating IN NUMBER DEFAULT 1500,
p_deviation IN NUMBER DEFAULT 350,
p_volatility IN NUMBER DEFAULT 0.06)
RETURN player_rec
IS
BEGIN
RETURN player_rec(id => p_id,
rating => p_rating,
deviation => p_deviation,
volatility => p_volatility,
mu => (p_rating - 1500) / c_glicko_factor,
phi => p_deviation / c_glicko_factor,
g_of_phi => g(p_deviation / c_glicko_factor));
END initialize_player;
FUNCTION big_e(p_player_mu IN NUMBER, p_opponent IN player_rec)
RETURN NUMBER
IS
BEGIN
RETURN 1 / (1 + EXP(-p_opponent.g_of_phi * (p_player_mu - p_opponent.mu)));
END big_e;
FUNCTION estimated_variance(p_player IN player_rec, p_players IN player_tab)
RETURN NUMBER
IS
v_variance NUMBER := 0;
v_big_e NUMBER;
BEGIN
FOR j IN 1 .. p_players.COUNT
WHEN p_players(j).id != p_player.id
LOOP
v_big_e := big_e(p_player.mu, p_players(j));
v_variance := v_variance + ((p_players(j).g_of_phi ** 2) * v_big_e * (1 - v_big_e));
END LOOP;
v_variance := 1 / v_variance;
RETURN v_variance;
END estimated_variance;
FUNCTION game_score(p_games IN game_tab, p_player IN INTEGER, p_opponent IN INTEGER)
RETURN NUMBER
IS
v_score NUMBER;
BEGIN
FOR i
IN 1 .. p_games.COUNT
WHEN (p_games(i).player1 IN (p_player, p_opponent) AND p_games(i).player2 IN (p_player, p_opponent))
LOOP
v_score :=
CASE
WHEN p_games(i).result = 0 THEN 0.5
WHEN p_games(i).result = 1 AND p_games(i).player1 = p_player THEN 1
WHEN p_games(i).result = 2 AND p_games(i).player2 = p_player THEN 1
ELSE 0
END;
END LOOP;
RETURN v_score;
END game_score;
FUNCTION estimated_delta(p_player IN player_rec, p_players IN player_tab, p_games IN game_tab)
RETURN NUMBER
IS
v_variance NUMBER := estimated_variance(p_player, p_players);
v_delta NUMBER := 0;
BEGIN
FOR j IN 1 .. p_players.COUNT
WHEN p_players(j).id != p_player.id
LOOP
v_delta :=
v_delta
+ ( p_players(j).g_of_phi
* (game_score(p_games, p_player.id, p_players(j).id) - big_e(p_player.mu, p_players(j))));
END LOOP;
RETURN v_variance * v_delta;
END estimated_delta;
FUNCTION illinois_volatility(p_x IN NUMBER,
p_delta IN NUMBER,
p_phi IN NUMBER,
p_variance IN NUMBER,
p_volatility IN NUMBER)
RETURN NUMBER
IS
v_e_x NUMBER := EXP(p_x);
v_phisquared NUMBER := p_phi ** 2;
BEGIN
RETURN v_e_x
* (p_delta ** 2 - v_phisquared - p_variance - v_e_x)
/ (2 * ((v_phisquared + p_variance + v_e_x) ** 2))
- ((p_x - LN(p_volatility ** 2)) / g_tau ** 2);
END illinois_volatility;
FUNCTION new_volatility(p_player IN player_rec, p_delta IN NUMBER, p_variance IN NUMBER)
RETURN NUMBER
IS
v_a NUMBER := LN(p_player.volatility);
v_big_a NUMBER := v_a;
v_big_b NUMBER;
v_big_c NUMBER;
v_k INTEGER;
v_illinois NUMBER;
v_f_a NUMBER;
v_f_b NUMBER;
v_f_c NUMBER;
BEGIN
IF p_delta ** 2 >= p_player.phi ** 2 + p_variance
THEN
v_big_b := LN(p_delta ** 2 - p_player.phi ** 2 - p_variance);
END IF;
IF p_delta ** 2 <= p_player.phi ** 2 + p_variance
THEN
v_k := 1;
LOOP
v_illinois :=
illinois_volatility(v_a - v_k * g_tau, p_delta, p_player.phi, p_variance, p_player.volatility);
IF v_illinois < 0
THEN
v_k := v_k + 1;
CONTINUE;
END IF;
EXIT;
END LOOP;
v_big_b := v_a - v_k * g_tau;
END IF;
v_f_a := illinois_volatility(v_big_a, p_delta, p_player.phi, p_variance, p_player.volatility);
v_f_b := illinois_volatility(v_big_b, p_delta, p_player.phi, p_variance, p_player.volatility);
WHILE ABS(v_big_b - v_big_a) > c_convergence_tolerance
LOOP
v_big_c := v_big_a + ((v_big_a - v_big_b) * v_f_a / (v_f_b - v_f_a));
v_f_c := illinois_volatility(v_big_c, p_delta, p_player.phi, p_variance, p_player.volatility);
CASE
WHEN v_f_c * v_f_b <= 0
THEN
v_big_a := v_big_b;
v_f_a := v_f_b;
ELSE
v_f_a := v_f_a / 2;
END CASE;
v_big_b := v_big_c;
v_f_b := v_f_c;
END LOOP;
RETURN EXP(v_big_a / 2);
END new_volatility;
FUNCTION new_rating(p_player IN player_rec,
p_volatility IN NUMBER,
p_variance IN NUMBER,
p_players IN player_tab,
p_games IN game_tab,
p_tau IN NUMBER DEFAULT NULL)
RETURN player_rec
IS
v_result player_rec;
v_phi2 NUMBER;
v_mu NUMBER := 0;
BEGIN
IF p_tau IS NOT NULL
THEN
set_tau(p_tau);
END IF;
v_result.id := p_player.id;
v_phi2 := SQRT(p_player.phi ** 2 + p_volatility ** 2);
v_result.phi := 1 / SQRT(1 / (v_phi2 ** 2) + 1 / p_variance);
v_result.g_of_phi := g(v_result.phi);
FOR j IN 1 .. p_players.COUNT
WHEN p_players(j).id != p_player.id
LOOP
v_mu :=
v_mu
+ ( p_players(j).g_of_phi
* (game_score(p_games, p_player.id, p_players(j).id) - big_e(p_player.mu, p_players(j))));
END LOOP;
v_result.mu := p_player.mu + v_result.phi ** 2 * v_mu;
v_result.rating := c_glicko_factor * v_result.mu + 1500;
v_result.deviation := c_glicko_factor * v_result.phi;
v_result.volatility := p_volatility;
RETURN v_result;
END new_rating;
PROCEDURE update_all_players(p_players IN OUT player_tab, p_games game_tab, p_tau IN NUMBER DEFAULT NULL)
IS
v_variance NUMBER;
v_delta NUMBER;
v_volatility NUMBER;
v_updated_players player_tab := player_tab();
BEGIN
IF p_tau IS NOT NULL
THEN
set_tau(p_tau);
END IF;
v_updated_players.EXTEND(p_players.COUNT);
FOR i IN 1 .. p_players.COUNT
LOOP
v_variance := estimated_variance(p_players(i), p_players);
v_delta := estimated_delta(p_players(i), p_players, p_games);
v_volatility := new_volatility(p_players(i), v_delta, v_variance);
v_updated_players(i) := new_rating(p_players(i), v_volatility, v_variance, p_players, p_games);
END LOOP;
p_players := v_updated_players;
END update_all_players;
PROCEDURE example
IS
v_players player_tab
:= player_tab(initialize_player(1, 1500, 200, 0.06),
initialize_player(2, 1400, 30, 0.06),
initialize_player(3, 1550, 100, 0.06),
initialize_player(4, 1700, 300, 0.06));
v_games game_tab := game_tab(game_rec(1, 2, 1), game_rec(1, 3, 2), game_rec(1, 4, 2));
v_variance NUMBER;
v_delta NUMBER;
v_volatility NUMBER;
v_updated player_rec;
BEGIN
DBMS_OUTPUT.put_line('Before');
display_player(v_players(1));
set_tau(0.5);
v_variance := estimated_variance(v_players(1), v_players);
v_delta := estimated_delta(v_players(1), v_players, v_games);
v_volatility := new_volatility(v_players(1), v_delta, v_variance);
v_updated := new_rating(v_players(1), v_volatility, v_variance, v_players, v_games);
DBMS_OUTPUT.put_line('After');
display_player(v_updated);
END example;
END;
In Dr. Glickman's paper he includes an example calculating a player's rating after competing against 3 other ranked players. The package includes the EXAMPLE procedure to run his example.
BEGIN
glicko2.example;
END;
/
Before
-------------------------
ID: 1
rating: 1500
deviation: 200
volatility: .06
-------------------------
After
-------------------------
ID: 1
rating: 1464.050670539089251000090331474725619233
deviation: 151.516524124304315076736848217911789433
volatility: .0599959844006778356377413158384369581414
-------------------------
Player 1, won 1 game and lost 2 others. While each of the results was maybe to be expected (won vs lower rank, lost vs higher rank), player 1's rating still dropped a few points from 1500 to 1464. The initial deviation of 200 lowered as the system became a little more confident in its rating after the additional input. The volatility remained mostly the same. It was already fairly static, but it did lower very slightly as the ratings were fresh and thus confidence was as high as possible given the available data.
The mu, phi, and g_of_phi values are for internal use within the system and can be ignored.
Extending that example to include matches between the other players we can update all of the players ratings at the end of a rating period. I've kept player 1's results the same, player 2, loses every game, player 3 wins two and loses one, player 4 wins every game.
DECLARE
c_tau NUMBER := 0.5;
v_players glicko2.player_tab
:= glicko2.player_tab(glicko2.initialize_player(1, 1500, 200, 0.06),
glicko2.initialize_player(2, 1400, 30, 0.06),
glicko2.initialize_player(3, 1550, 100, 0.06),
glicko2.initialize_player(4, 1700, 300, 0.06));
v_games glicko2.game_tab
:= glicko2.game_tab(glicko2.game_rec(1, 2, 1),
glicko2.game_rec(1, 3, 2),
glicko2.game_rec(1, 4, 2),
glicko2.game_rec(2, 3, 2),
glicko2.game_rec(2, 4, 2),
glicko2.game_rec(3, 4, 2));
BEGIN
DBMS_OUTPUT.put_line('Before');
FOR i IN 1 .. v_players.COUNT
LOOP
glicko2.display_player(v_players(i));
END LOOP;
glicko2.update_all_players(v_players, v_games, c_tau);
DBMS_OUTPUT.put_line('After');
FOR i IN 1 .. v_players.COUNT
LOOP
glicko2.display_player(v_players(i));
END LOOP;
END;
Before
-------------------------
ID: 1
rating: 1500
deviation: 200
volatility: .06
-------------------------
-------------------------
ID: 2
rating: 1400
deviation: 30
volatility: .06
-------------------------
-------------------------
ID: 3
rating: 1550
deviation: 100
volatility: .06
-------------------------
-------------------------
ID: 4
rating: 1700
deviation: 300
volatility: .06
-------------------------
After
-------------------------
ID: 1
rating: 1464.050670539089251000090331474725619233
deviation: 151.516524124304315076736848217911789433
volatility: .0599959844006778356377413158384369581414
-------------------------
-------------------------
ID: 2
rating: 1395.575300667365091681790311891889886509
deviation: 31.52226732290745258692198451742165957159
volatility: .0600018359077613166409605623174229410253
-------------------------
-------------------------
ID: 3
rating: 1570.661236457502866661616824411132327558
deviation: 93.02707854276383549253944675925066799718
volatility: .0599959033294384056527124236262498706405
-------------------------
-------------------------
ID: 4
rating: 1846.840970178800326149436527884413374357
deviation: 194.563175845294448506167881660623266854
volatility: .0599984601432078028346829965616648799165
-------------------------
Note, in the UPDATE_ALL_PLAYERS procedure a new collection of player records is created rather than updating in place. This is to compute each player against the "before" ratings of every other player and once all of them have their new ratings, then update them with the "after" ratings.
I wanted to do something fun and interesting for Joel Kallman Day this year and I enjoyed this little project quite a bit. While the functions are useful in themselves for their intended purposes, those looking for the Oracle lesson to be gained. I used some of the newer record constructor and loop syntax introduced in 21c. I really appreciated the WHEN-clause on the FOR loops when iterating through players. For each player I could LOOP through all of them but skip the current player so I was only looping through the opponents. Of course, I could use an IF or CASE inside the LOOP, but I found the WHEN syntax to be a more natural way of declaring my intent. Similarly, when looping through games to find scores, I used this construction to search through all games, but only process the ones that applied to the particular pair of players I was interested in.
FOR i IN 1 .. p_games.COUNT WHEN (p_games(i).player1 IN (p_player, p_opponent) AND p_games(i).player2 IN (p_player, p_opponent))
Again, I could have checked for that condition inside the loop, but I found this to be more self-describing as to the intent of the loop.
I hope you found this useful and entertaining. Thank you for reading. Questions and comments, as always, are welcome.