From b1b753e317daa10e03a6a3b210d185539fac176b Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Tue, 12 Sep 2023 23:56:45 +0200 Subject: 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. --- schema.sql | 37 +++++++++++++++++++++ server.js | 93 +++++++++++++++++++++++++++++++++++++++++++++++----- tools/elo.js | 58 ++++++++++++++++++++++++++++++++ views/game_stats.pug | 25 ++++++++++++++ views/user_stats.pug | 34 +++++++++++++------ 5 files changed, 229 insertions(+), 18 deletions(-) create mode 100644 tools/elo.js create mode 100644 views/game_stats.pug 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, @@ -1795,6 +1789,59 @@ app.get('/api/replay/:game_id', function (req, res) { return res.send(SQL_SELECT_REPLAY.get({game_id})) }) +/* + * 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 -- cgit v1.2.3