From fc9af57627fdffcbdcab1ac0dcf7989d6323a8a3 Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Thu, 5 Oct 2023 15:09:29 +0200 Subject: Revert "Add match making." This reverts commit b5a31813aa284b8b64bfd2660ea3a048275cee89. --- schema.sql | 80 -------------- server.js | 286 -------------------------------------------------- views/about.pug | 20 ---- views/admin_match.pug | 53 ---------- views/header.pug | 2 - views/match.pug | 71 ------------- 6 files changed, 512 deletions(-) delete mode 100644 views/admin_match.pug delete mode 100644 views/match.pug diff --git a/schema.sql b/schema.sql index 93b73cb..4c64ecd 100644 --- a/schema.sql +++ b/schema.sql @@ -208,44 +208,6 @@ create table if not exists setups ( unique (title_id, player_count, scenario) ); -create table if not exists tickets ( - ticket_id integer primary key, - user_id integer, - setup_id integer, - pace integer, - time real, -- julianday - unique (user_id, setup_id, pace) -); - -drop view if exists ticket_rating_view; -create view ticket_rating_view as - select - tickets.*, - coalesce(rating, 1500) as rating - from tickets - join setups using(setup_id) - left join ratings using(title_id, user_id) - where time < julianday('now', '-30 seconds') -; - -drop view if exists matchmaking_view; -create view matchmaking_view as - select - setup_id, - pace, - count(1) / player_count as n, - julianday() - min(time) as age - from - tickets - join setups using(setup_id) - where - time < julianday('now', '-30 seconds') - group by - setup_id, pace - having n > 0 - order by age desc -; - -- Friend and Block Lists -- create table if not exists contacts ( @@ -563,47 +525,6 @@ begin games.game_id = old.game_id; end; -drop trigger if exists trigger_part_check; -create trigger trigger_part_check before delete on players -begin - select - raise(abort, 'Cannot remove players from matches and/or finished games!') - where - old.user_id > 0 and exists ( - select 1 from games where games.game_id=old.game_id and ( is_match or status > 1 ) - ) - ; -end; - --- Log matchmaking runs and expired tickets - -create table if not exists matchmaking_log ( - time datetime default current_timestamp, - setup_id integer, - pace integer, - age real, - score integer, - tickets json, - matches json -); - -drop view if exists matchmaking_log_view; -create view matchmaking_log_view as - select - time, title_id, player_count, scenario, pace, age, score, tickets, matches - from - matchmaking_log - join setups using(setup_id) -; - -create table if not exists expired_tickets_log ( - user_id integer, - setup_id integer, - pace integer, - ctime datetime, - xtime datetime -); - -- Trigger to remove game data when filing a game as archived drop trigger if exists trigger_archive_game; @@ -649,7 +570,6 @@ begin delete from threads where author_id = old.user_id; delete from game_chat where user_id = old.user_id; delete from ratings where user_id = old.user_id; - delete from tickets where user_id = old.user_id; update games set owner_id = 0 where owner_id = old.user_id; update players set user_id = 0 where user_id = old.user_id; end; diff --git a/server.js b/server.js index 4d3db19..0fcaf43 100644 --- a/server.js +++ b/server.js @@ -96,20 +96,6 @@ function set_has(set, item) { return false } -function array_remove(array, index) { - let n = array.length - for (let i = index + 1; i < n; ++i) - array[i - 1] = array[i] - array.length = n - 1 -} - -function array_remove_item(array, item) { - let n = array.length - for (let i = 0; i < n; ++i) - if (array[i] === item) - return array_remove(array, i) -} - /* * Notification mail setup. */ @@ -184,7 +170,6 @@ app.locals.SITE_URL = SITE_URL app.locals.ENABLE_MAIL = !!mailer app.locals.ENABLE_WEBHOOKS = !!WEBHOOKS app.locals.ENABLE_FORUM = process.env.FORUM | 0 -app.locals.ENABLE_MATCHES = process.env.MATCHES | 0 app.locals.EMOJI_LIVE = "\u{1f465}" app.locals.EMOJI_FAST = "\u{1f3c1}" @@ -1975,277 +1960,6 @@ function update_elo_ratings(game_id) { SQL_INSERT_RATING.run(game.title_id, p.user_id, p.rating + p.change, p.count + 1, game.mtime) } -/* - * MATCHMAKING - */ - -const MATCH_LIMIT = 300 - -var _seed = random_seed() - -function random(range) { - // An MLCG using integer arithmetic with doubles. - // https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf - // m = 2**35 − 31 - return (_seed = _seed * 200105 % 34359738337) % range -} - -function shuffle(list) { - // Fisher-Yates shuffle - for (let i = list.length - 1; i > 0; --i) { - let j = random(i + 1) - let tmp = list[j] - list[j] = list[i] - list[i] = tmp - } -} - -const SQL_SELECT_TICKETS_FOR_PACE = SQL("select users.name, rating, setup_id, datetime(time) as time from ticket_rating_view join users using(user_id) where pace=? order by setup_id,time") - -const SQL_SELECT_MATCHMAKING = SQL("select setup_id, n, age from matchmaking_view where pace=?") -const SQL_INSERT_MATCHMAKING_LOG = SQL("insert into matchmaking_log (setup_id,pace,age,score,tickets,matches) values (?,?,?,?,?,?)") - -const SQL_SELECT_TICKETS_FOR_USER = SQL("select tickets.* from tickets join setups using(setup_id) where user_id=? order by pace, title_id, setup_id") -const SQL_SELECT_TICKETS_FOR_SETUP = SQL("select * from ticket_rating_view where setup_id=? and pace=? order by rating") -const SQL_INSERT_TICKET = SQL("insert or replace into tickets (user_id, setup_id, pace, time) values (?,?,?,julianday())") -const SQL_DELETE_TICKET = SQL("delete from tickets where user_id=? and ticket_id=?") -const SQL_DELETE_TICKET_PACE = SQL("delete from tickets where user_id=? and pace=?") -const SQL_DELETE_TICKET_USER = SQL("delete from tickets where user_id=?") - -const SQL_DELETE_TICKET_EXPIRE = SQL("delete from tickets where pace=? and time < julianday('now',?)") -const SQL_INSERT_TICKET_EXPIRE_LOG = SQL(` - insert into expired_tickets_log - (user_id, setup_id, pace, ctime, xtime) - select - user_id, setup_id, pace, datetime(time), datetime() - from - tickets where pace=? and time < julianday('now',?) -`) - -app.get('/games/match', must_be_logged_in, function (req, res) { - res.render('match.pug', { - user: req.user, - limit: check_join_game_limit(req.user), - tickets: SQL_SELECT_TICKETS_FOR_USER.all(req.user.user_id), - }) -}) - -app.get('/admin/match', must_be_administrator, function (req, res) { - res.render('admin_match.pug', { - user: req.user, - live_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(1), - fast_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(2), - slow_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(3), - }) -}) - -app.post('/api/match/queue', must_be_logged_in, function (req, res) { - let pace = req.body.pace | 0 - if (req.body.setups) { - if (typeof req.body.setups === "string") - SQL_INSERT_TICKET.run(req.user.user_id, req.body.setups|0, pace) - else - for (let setup of req.body.setups) - SQL_INSERT_TICKET.run(req.user.user_id, setup|0, pace) - } - res.redirect("/games/match") -}) - -app.post('/api/match/unqueue', must_be_logged_in, function (req, res) { - if (req.body.pace) { - SQL_DELETE_TICKET_PACE.run(req.user.user_id, req.body.pace|0) - } - if (req.body.tickets) { - if (typeof req.body.tickets === "string") - SQL_DELETE_TICKET.run(req.user.user_id, req.body.tickets|0) - else - for (let ticket of req.body.tickets) - SQL_DELETE_TICKET.run(req.user.user_id, ticket|0) - } - res.redirect("/games/match") -}) - -function tick_matches(pace, min_matches, max_age) { - for (let info of SQL_SELECT_MATCHMAKING.all(pace)) { - let setup = SETUP_TABLE[info.setup_id] - console.log("MATCH MAKING TICK (", pace, setup.setup_name, min_matches, max_age.toFixed(2), ") => ", info.n, info.age.toFixed(2)) - if (info.n >= min_matches || info.age >= max_age) - create_matches(setup, pace, info.age) - } -} - -function is_blacklist_match(m) { - for (let a of m) - for (let b of m) - if (a !== b && set_has(a.blacklist, b.user_id)) - return true - return false -} - -function score_ticket_pair(a, b) { - return Math.min(MATCH_LIMIT, Math.abs(a.rating - b.rating)) -} - -function score_ticket_pair_fast(a, b) { - let rd = Math.abs(a.rating - b.rating) - let td = Math.abs(a.time % 1 - b.time % 1) - if (td > 0.5) - td = 1 - td - // Ignore first 3 hour diff, then linearly approach limit at 9 hours - td = Math.max(0, td - 3/24) * (24/6) * MATCH_LIMIT - return Math.min(MATCH_LIMIT, (rd + td) | 0) -} - -function score_match(F, m) { - if (is_blacklist_match(m)) - return MATCH_LIMIT - if (m.length === 2) - return F(m[0], m[1]) - let score = 0 - let n = m.length - for (let a = 0; a < n; ++a) - for (let b = a+1; b < n; ++b) - score += F(m[a], m[b]) ** 2 - return Math.sqrt(score / (n / 2 * (n-1))) | 0 -} - -function add_best_ticket(F, this_match, tickets) { - let best_score = MATCH_LIMIT - let best_ticket = tickets[0] - for (let t of tickets) { - this_match.push(t) - let this_score = score_match(F, this_match) - this_match.pop(t) - if (this_score < best_score) { - best_score = this_score - best_ticket = t - } - } - this_match.push(best_ticket) - array_remove_item(tickets, best_ticket) -} - -function score_partition(F, partition) { - let score = 0 - for (let m of partition) - score += score_match(F, m) ** 2 - return Math.sqrt(score / partition.length) -} - -function partition_matches(F, N, original_tickets, attempts) { - let M = (original_tickets.length / N) | 0 - - let best_partition = null - let best_score = (M * MATCH_LIMIT) ** 2 - - for (let i = 0; i < attempts; ++i) { - var this_partition = [] - - let tickets = original_tickets.slice() - if (i > 0) - shuffle(tickets) - - while (tickets.length >= N) { - let this_match = [ tickets.pop() ] - while (this_match.length < N) - add_best_ticket(F, this_match, tickets) - this_partition.push(this_match) - } - - let this_score = score_partition(F, this_partition) - if (this_score < best_score) { - best_score = this_score - best_partition = this_partition - } - } - - if (best_partition) { - best_partition = best_partition.filter(m => score_match(F, m) < MATCH_LIMIT) - return { score: best_score, matches: best_partition } - } - - return { score: MATCH_LIMIT, matches: [] } -} - -function create_matches(setup, pace, age) { - let N = setup.player_count - let F = score_ticket_pair - let A = 47 - - let tickets = SQL_SELECT_TICKETS_FOR_SETUP.all(setup.setup_id, pace) - for (let t of tickets) - t.blacklist = SQL_SELECT_CONTACT_BLACKLIST.all(t.user_id) - - if (tickets.length < N) - return - - if (pace === PACE_FAST) - F = score_ticket_pair_fast - - let info = partition_matches(F, N, tickets, A) - if (info.matches.length > 0) { - SQL_INSERT_MATCHMAKING_LOG.run(setup.setup_id, pace, age, info.score, JSON.stringify(tickets), JSON.stringify(info.matches)) - for (let match of info.matches) - start_match(setup, pace, match) - } -} - -function start_match(setup, pace, tickets) { - let game_id = 0 - console.log("START MATCH", PACE_NAME[pace], setup.setup_name, tickets.map(t=>t.rating).join(",")) - SQL_BEGIN.run() - try { - game_id = SQL_INSERT_GAME.get( - 0, setup.title_id, setup.scenario, setup.options, setup.player_count, - pace, 0, 1, null, 1 - ) - for (let i = 0; i < tickets.length; ++i) { - SQL_INSERT_PLAYER_ROLE.run(game_id, "Random " + (i+1), tickets[i].user_id, 0) - - if (SQL_COUNT_ACTIVE_GAMES.get(tickets[i].user_id) + 1 >= LIMIT_ACTIVE_GAMES) - SQL_DELETE_TICKET_USER.run(tickets[i].user_id) - else if (pace === PACE_LIVE) - SQL_DELETE_TICKET_PACE.run(tickets[i].user_id, PACE_LIVE) - else - SQL_DELETE_TICKET.run(tickets[i].user_id, tickets[i].ticket_id) - } - SQL_COMMIT.run() - } finally { - if (db.inTransaction) - SQL_ROLLBACK.run() - } - start_game(SQL_SELECT_GAME.get(game_id)) -} - -function tick_slow_matches() { - tick_matches(PACE_SLOW, 3, 1) - SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_SLOW, "-14 days") - SQL_DELETE_TICKET_EXPIRE.run(PACE_SLOW, "-14 days") -} - -function tick_fast_matches() { - // Wait at most one day. - tick_matches(PACE_FAST, 3, 1) - SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_FAST, "-7 days") - SQL_DELETE_TICKET_EXPIRE.run(PACE_FAST, "-7 days") -} - -function tick_live_matches() { - // Wait at most 15 minutes - tick_matches(PACE_LIVE, 2, 0.25 / 24) - SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_LIVE, "-3 hours") - SQL_DELETE_TICKET_EXPIRE.run(PACE_LIVE, "-3 hours") -} - -if (app.locals.ENABLE_MATCHES) { - setInterval(tick_live_matches, 1000 * 60) - setInterval(tick_fast_matches, 1000 * 60 * 5) - setInterval(tick_slow_matches, 1000 * 60 * 15) - setTimeout(tick_live_matches, 1000 * 10) - setTimeout(tick_fast_matches, 1000 * 20) - setTimeout(tick_slow_matches, 1000 * 30) -} - /* * MAIL NOTIFICATIONS */ diff --git a/views/about.pug b/views/about.pug index 85522df..dd12772 100644 --- a/views/about.pug +++ b/views/about.pug @@ -74,26 +74,6 @@ html If you want to play with friends, check the "private" checkbox and invite your friends from the join page after you have created the game. - h2 Matchmaking - - p. - The match maker will match players up and start games automatically - once there are enough people waiting for the same game. - Players will be matched with opponents of similar Elo ratings when possible. - - p. - Live tickets expire after 3 hours if you don't get a match. - All of your other Live tickets are removed when you get matched for a Live game. - - p. - Fast tickets take the time of day into account. - Queue up when you want to start playing for the best results. - - p. - Don't queue up for too many games! - It can take a while for the matches to start, - so you may end up with more games than you can handle. - h2 Privacy statement p When you create an account we collect the following personal information: diff --git a/views/admin_match.pug b/views/admin_match.pug deleted file mode 100644 index 11a6c54..0000000 --- a/views/admin_match.pug +++ /dev/null @@ -1,53 +0,0 @@ -//- vim:ts=4:sw=4: - -mixin show_ticket(ticket) - - var setup = SETUP_TABLE[ticket.setup_id] - tr - td= ticket.name - td= ticket.rating - td= setup.setup_name - td #{ticket.time} UTC - -mixin show_ticket_list(list) - table - thead - tr - th User - th Rating - th Title - th Age - tbody - each ticket in list - +show_ticket(ticket) - -doctype html -html - head - include head - title Matches - style. - div.buttons { margin-top: 8px } - body - include header - article - h1 Waiting Room - Admin - - p Time is #{new Date().toISOString()} - - h2 Live Tickets - if live_tickets.length > 0 - +show_ticket_list(live_tickets) - else - p No live tickets. - - h2 Fast Tickets - if fast_tickets.length > 0 - +show_ticket_list(fast_tickets) - else - p No fast tickets. - - h2 Slow Tickets - if slow_tickets.length > 0 - +show_ticket_list(slow_tickets) - else - p No slow tickets. diff --git a/views/header.pug b/views/header.pug index dfeef5c..454c35a 100644 --- a/views/header.pug +++ b/views/header.pug @@ -6,8 +6,6 @@ header if user if ENABLE_FORUM a(href="/forum") Forum - if ENABLE_MATCHES - a(href="/games/match") Match a(href="/games/public") Public if user.waiting > 0 a(href="/games/active") Games (#{user.waiting}) diff --git a/views/match.pug b/views/match.pug deleted file mode 100644 index 504cef5..0000000 --- a/views/match.pug +++ /dev/null @@ -1,71 +0,0 @@ -//- vim:ts=4:sw=4: - -mixin show_ticket(ticket) - - var setup = SETUP_TABLE[ticket.setup_id] - label - input(type="checkbox" name="tickets" value=ticket.ticket_id) - case ticket.pace - when 1 - | #{EMOJI_LIVE} #{setup.setup_name} - when 2 - | #{EMOJI_FAST} #{setup.setup_name} - when 3 - | #{EMOJI_SLOW} #{setup.setup_name} - -mixin show_setup(setup) - label - input(type="checkbox" name="setups" value=setup.setup_id) - | #{setup.setup_name} - -mixin show_setup_list(list) - each setup in list - +show_setup(setup) - -doctype html -html - head - include head - title Matches - style. - label { display: block; margin: 2px 0; user-select: none } - div.group, details { margin: 6px 0 } - details > summary { user-select: none } - details > label { margin-left: 24px } - body - include header - article - h1 The Miraculous Match-making Machine - - p People go in one end; games come out the other. - - h2 Tickets - if tickets.length > 0 - form(method="post" action="/api/match/unqueue") - each ticket in tickets - +show_ticket(ticket) - if tickets.length > 7 - p - i Don't sign up for more games than you will be able to handle! - p - button(name="submit") ❌ Delete - else - p You are not queued for any matches. - - h2 Register - if limit - p.error= limit - else - form(method="post" action="/api/match/queue") - each title in TITLE_LIST - if title.setups.length > 2 - details - summary - u= title.title_name - +show_setup_list(title.setups) - else - div.group - +show_setup_list(title.setups) - p - button(name="pace" value=1) #{EMOJI_LIVE} Play Live - button(name="pace" value=2) #{EMOJI_FAST} Play Fast - button(name="pace" value=3) #{EMOJI_SLOW} Play Slow -- cgit v1.2.3