Calculate Elo ratings.

Primarily for use with future matchmaking system to provide better games for
everyone.

Show top 5 players of each game on the game pages.

5 files changed, 229 insertions, 18 deletions

diff --git a/schema.sql b/schema.sql
index eef0a26..bebccb5 100644
--- a/schema.sql
+++ b/schema.sql
@@ -147,6 +147,42 @@ create view user_dynamic_view as
 		users
 	;
 
+-- Elo ratings & match making --
+
+create table if not exists ratings (
+	title_id integer,
+	user_id integer,
+	rating integer,
+	count integer,
+	last timestamp,
+	primary key (title_id, user_id)
+) without rowid;
+
+drop view if exists rating_view;
+create view rating_view as
+	select
+		title_id, name, rating, count, last
+	from
+		ratings
+		natural join users
+	order by
+		title_id,
+		rating desc
+;
+
+drop view if exists player_rating_view;
+create view player_rating_view as
+	select
+		games.game_id,
+		players.user_id,
+		players.role,
+		coalesce(rating, 1500) as rating,
+		coalesce(count, 0) as count
+	from players
+	natural join games
+	natural left join ratings
+;
+
 -- Friend and Block Lists --
 
 create table if not exists contacts (
@@ -487,6 +523,7 @@ begin
 	delete from threads where author_id = old.user_id;
 	delete from game_chat where user_id = old.user_id;
 	delete from players where user_id = old.user_id;
+	delete from ratings where user_id = old.user_id;
 	update games set owner_id = 0 where owner_id = old.user_id;
 end;
 
diff --git a/server.js b/server.js
index 80b259d..d0b55cf 100644
--- a/server.js
+++ b/server.js
@@ -1451,10 +1451,6 @@ function get_title_page(req, res, title_id) {
 		unread = SQL_SELECT_UNREAD_CHAT_GAMES.all(req.user.user_id)
 	let user_id = req.user ? req.user.user_id : 0
 
-	// Title page shows 
-
-	let a = Date.now()
-
 	let open_games = QUERY_LIST_GAMES_OF_TITLE_OPEN.all(title_id)
 	let ready_games = QUERY_LIST_GAMES_OF_TITLE_READY.all(title_id)
 	let replacement_games = QUERY_LIST_GAMES_OF_TITLE_REPLACEMENT.all(title_id)
@@ -1467,8 +1463,6 @@ function get_title_page(req, res, title_id) {
 	annotate_games(active_games, user_id, unread)
 	annotate_games(finished_games, user_id, unread)
 
-	console.log("LIST GAMES", Date.now() - a)
-
 	res.render('info.pug', {
 		user: req.user,
 		title: title,
@@ -1796,6 +1790,59 @@ app.get('/api/replay/:game_id', function (req, res) {
 })
 
 /*
+ * ELO RATINGS
+ *
+ * TODO:
+ * use role ratings in asymmetric games based on title_id, scenario, player_count
+ * add role_rating to Ev and update role_rating with low K-value
+ */
+
+const SQL_SELECT_RATING_GAME = SQL("select title_id, player_count, scenario, result, xtime from games where game_id=? and status>1 and player_count=user_count and player_count>1")
+const SQL_SELECT_RATING_PLAYERS = SQL("select * from player_rating_view where game_id=?")
+const SQL_INSERT_RATING = SQL("insert or replace into ratings (title_id,user_id,rating,count,last) values (?,?,?,?,?)")
+
+function elo_k(a) {
+	return a.count < 10 ? 60 : 30
+}
+
+function elo_ev(a, players) {
+	// https://arxiv.org/pdf/2104.05422.pdf
+	// original: 1 / ( 1 + 10**((Rb-Ra)/400) )
+	// unoptimized: 10**(Ra/400) / ( 10**(Ra/400) + 10**(Rb/400) )
+	// generalized: 10**(Ra/400) / ( 10**(Ra/400) + 10**(Rb/400) + 10**(Rc/400) + ... )
+	let sum = 0
+	for (let p of players)
+		sum += 10**(p.rating/400)
+	return 10**(a.rating/400) / sum
+}
+
+function elo_change(a, players, score) {
+	return Math.round( elo_k(a) * ( score - elo_ev(a, players) ) )
+}
+
+function update_elo_ratings(game_id) {
+	let game = SQL_SELECT_RATING_GAME.get(game_id)
+	if (!game)
+		return
+
+	let players = SQL_SELECT_RATING_PLAYERS.all(game_id)
+
+	let winner = null
+	for (let p of players)
+		if (p.role === game.result)
+			winner = p
+
+	for (let p of players)
+		if (winner !== null)
+			p.change = elo_change(p, players, p === winner ? 1 : 0)
+		else
+			p.change = elo_change(p, players, 1 / players.length)
+
+	for (let p of players)
+		SQL_INSERT_RATING.run(game.title_id, p.user_id, p.rating + p.change, p.count + 1, game.xtime)
+}
+
+/*
  * MAIL NOTIFICATIONS
  */
 
@@ -2144,6 +2191,8 @@ function put_game_state(game_id, state, old_active) {
 	if (state.state === "game_over") {
 		SQL_UPDATE_GAME_RESULT.run(2, state.result, game_id)
 		send_game_finished_notification_to_offline_users(game_id, state.result)
+		if (state.result && state.result !== "None")
+			update_elo_ratings(game_id)
 	} else {
 		send_your_turn_notification_to_offline_users(game_id, old_active, state.active)
 	}
@@ -2590,12 +2639,40 @@ const SQL_USER_STATS = SQL(`
 		scenario
 	`)
 
-app.get('/user-stats/:who_name', function (req, res) {
+const SQL_USER_RATINGS = SQL(`
+	select title_name, rating, count, date(last) as last
+	from ratings natural join titles
+	where user_id = ?
+	and count >= 5
+	order by rating desc
+	`)
+
+const SQL_GAME_RATINGS = SQL(`
+	select name, rating, count, date(last) as last
+	from ratings natural join users
+	where title_id = ? and rating >= 1600 and count >= 10
+	order by rating desc
+	limit 50
+	`)
+
+app.get('/user-stats/:who_name', must_be_administrator, function (req, res) {
 	let who = SQL_SELECT_USER_BY_NAME.get(req.params.who_name)
 	if (who) {
 		let stats = SQL_USER_STATS.all(who.user_id, who.user_id)
-		res.render('user_stats.pug', { user: req.user, who: who, stats: stats })
+		let ratings = SQL_USER_RATINGS.all(who.user_id)
+		res.render('user_stats.pug', { user: req.user, who, stats, ratings })
 	} else {
 		return res.status(404).send("Invalid user name.")
 	}
 })
+
+app.get('/game-stats/:title_id', must_be_administrator, function (req, res) {
+	let title_id = req.params.title_id
+	if (title_id in TITLES) {
+		let title_name = TITLES[title_id].title_name
+		let ratings = SQL_GAME_RATINGS.all(title_id)
+		res.render('game_stats.pug', { user: req.user, title_name, ratings })
+	} else {
+		return res.status(404).send("Invalid title.")
+	}
+})
diff --git a/tools/elo.js b/tools/elo.js
new file mode 100644
index 0000000..95ca58b
--- /dev/null
+++ b/tools/elo.js
@@ -0,0 +1,58 @@
+#!/usr/bin/env -S node
+
+const sqlite3 = require("better-sqlite3")
+
+const db = new sqlite3("db")
+
+const SQL_SELECT_GAMES = db.prepare("select * from games where status>1 and user_count=player_count and player_count>1 order by xtime")
+const SQL_SELECT_RATING = db.prepare("select * from player_rating_view where game_id=?")
+const SQL_INSERT_RATING = db.prepare("insert or replace into ratings (title_id,user_id,rating,count,last) values (?,?,?,?,?)")
+
+function elo_k(n) {
+	return n < 10 ? 60 : 30
+}
+
+function elo_ev(a, players) {
+	// Generalized formula for multiple players.
+	// https://arxiv.org/pdf/2104.05422.pdf
+	let sum = 0
+	for (let p of players)
+		sum += Math.pow(10, p.rating / 400)
+	return Math.pow(10, a.rating / 400) / sum
+}
+
+function elo_change(a, players, s) {
+	return Math.round(elo_k(a.count) * (s - elo_ev(a, players)))
+}
+
+function update_elo_ratings(game) {
+	let players = SQL_SELECT_RATING.all(game.game_id)
+	if (game.player_count !== players.length)
+		return
+
+	let winner = null
+	for (let p of players)
+		if (p.role === game.result)
+			winner = p
+
+	if (winner) {
+		for (let p of players) {
+			if (p === winner)
+				p.change = elo_change(p, players, 1)
+			else
+				p.change = elo_change(p, players, 0)
+		}
+	} else {
+		for (let p of players)
+			p.change = elo_change(p, players, 1 / game.player_count)
+	}
+
+	for (let p of players)
+		SQL_INSERT_RATING.run(game.title_id, p.user_id, p.rating + p.change, p.count+1, game.xtime)
+}
+
+db.exec("begin transaction")
+db.exec("delete from ratings")
+for (let game of SQL_SELECT_GAMES.all())
+	update_elo_ratings(game)
+db.exec("commit")
diff --git a/views/game_stats.pug b/views/game_stats.pug
new file mode 100644
index 0000000..a60d7cb
--- /dev/null
+++ b/views/game_stats.pug
@@ -0,0 +1,25 @@
+//- vim:ts=4:sw=4:
+doctype html
+html
+	head
+		include head
+		title #{title_name} - Ranking
+	body
+		include header
+		article
+			h1 #{title_name} - Ranking
+
+			table(style="min-width:auto")
+				thead
+					tr
+						th Player
+						th.r Rating
+						th.r Plays
+						th.r Last played
+				tbody
+					each row in ratings
+						tr
+							td= row.name
+							td.r= row.rating
+							td.r= row.count
+							td.r= row.last
diff --git a/views/user_stats.pug b/views/user_stats.pug
index a947b64..dee2883 100644
--- a/views/user_stats.pug
+++ b/views/user_stats.pug
@@ -5,12 +5,11 @@ doctype html
 html
 	head
 		include head
-		title Stats for #{who.name}
-		style td:nth-child(n+4){text-align:right}
+		title Statistics for #{who.name}
 	body
 		include header
 		article
-			h1 Stats for #{who.name}
+			h1 Statistics for #{who.name}
 
 			table(style="min-width:auto")
 				thead
@@ -18,8 +17,8 @@ html
 						th Title
 						th Scenario
 						th Role
-						th Played
-						th Won
+						th.r Played
+						th.r Won
 				tbody
 					each row in stats
 						tr
@@ -28,12 +27,27 @@ html
 							td= row.title_name
 							td= row.scenario
 							td= row.role
-							td= row.total
-							td= Math.round(row.won*100/row.total) + "%"
+							td.r= row.total
+							td.r= Math.round(row.won*100/row.total) + "%"
 				tfoot
 					tr
+						td Overall
 						td
 						td
-						td
-						td= all_total
-						td= Math.round(all_won*100/all_total) + "%"
+						td.r= all_total
+						td.r= Math.round(all_won*100/all_total) + "%"
+
+			table(style="min-width:auto")
+				thead
+					tr
+						th Title
+						th.r Rating
+						th.r Plays
+						th.r Last played
+				tbody
+					each row in ratings
+						tr
+							td= row.title_name
+							td.r= row.rating
+							td.r= row.count
+							td.r= row.last