WIP match makingwip-matchmaking

Use greedy best fit algorithm to partition tickets into matches.
Iterate using random start points to search for the best partitioning.

6 files changed, 533 insertions, 0 deletions

diff --git a/schema.sql b/schema.sql
index a0a3b02..fd54c9e 100644
--- a/schema.sql
+++ b/schema.sql
@@ -221,6 +221,42 @@ 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
+		natural join setups
+	group by
+		setup_id, pace
+	having n > 0
+	order by age desc
+;
+
 -- Friend and Block Lists --
 
 create table if not exists contacts (
@@ -659,6 +695,47 @@ begin
 		players.game_id = old.game_id and players.role in ( 'Both', old.active );
 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
+		natural join setups
+;
+
+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;
@@ -705,6 +782,7 @@ begin
 	delete from game_chat where user_id = old.user_id;
 	delete from ratings where user_id = old.user_id;
 	delete from players where user_id = old.user_id and game_id in (select game_id from games where status <= 1);
+	delete from tickets where user_id = old.user_id;
 	update players set user_id = 0 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 183148a..f15b4d4 100644
--- a/server.js
+++ b/server.js
@@ -95,6 +95,20 @@ 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.
  */
@@ -1079,6 +1093,7 @@ const SQL_SELECT_SETUPS = SQL("select * from setups where title_id=? order by se
 
 let RULES = {}
 let TITLE_TABLE = app.locals.TITLE_TABLE = {}
+let SETUP_TABLE = app.locals.SETUP_TABLE = {}
 let TITLE_LIST = app.locals.TITLE_LIST = []
 let TITLE_NAME = app.locals.TITLE_NAME = {}
 
@@ -1162,6 +1177,7 @@ function load_rules(rules_dir, rules_file, title) {
 
 	title.setups = SQL_SELECT_SETUPS.all(title.title_id)
 	for (let setup of title.setups) {
+		SETUP_TABLE[setup.setup_id] = setup
 		if (!setup.setup_name) {
 			if (title.setups.length > 1 && setup.scenario !== "Standard")
 				setup.setup_name = title.title_name + " - " + setup.scenario
@@ -2240,6 +2256,275 @@ function update_elo_ratings(game_id) {
 }
 
 /*
+ * 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 natural join users 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 * from tickets where user_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_logged_in, 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('/games/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('/games/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", setup.setup_name, "--", info.n, "matches", info.age.toFixed(2), "days")
+		if (info.n >= min_matches * setup.player_count || 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
+
+	// TODO: use path growing algorithm (or full blossom matchings) instead?
+	// https://sci-hub.hkvisa.net/10.1016/s0020-0190(02)00393-9
+
+	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
+		}
+	}
+
+	best_partition = best_partition.filter(m => score_match(F, m) < MATCH_LIMIT)
+
+	return { score: best_score, matches: best_partition }
+}
+
+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 (pace === PACE_FAST)
+		F = score_ticket_pair_fast
+
+	console.log("RUN MATCH MAKING")
+
+	let info = partition_matches(F, N, tickets, A)
+
+	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("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, 4, 2)
+	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, 2, 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")
+}
+
+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 dd34547..9f73e84 100644
--- a/views/about.pug
+++ b/views/about.pug
@@ -69,6 +69,41 @@ html
 				dd.
 					Anything goes. Read the game notice and adapt!
 
+			h2 Waiting room
+
+			p.
+				In the public waiting room you can post a request for a game, or respond to someone else's request for a game.
+				If you see a game you want to play, click the Join link and enter the game.
+				Once the game has enough players, the creator can start the game.
+
+			p.
+				If you'd like to post your own request for a game, click the create a new game link and
+				select the scenario and options you want to play.
+
+			p.
+				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.
+				<i>Don't queue up for too many games!</i>
+				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
new file mode 100644
index 0000000..11a6c54
--- /dev/null
+++ b/views/admin_match.pug
@@ -0,0 +1,53 @@
+//- 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 d386969..24dd9f2 100644
--- a/views/header.pug
+++ b/views/header.pug
@@ -9,6 +9,7 @@ header
 		if user
 			if ENABLE_FORUM
 				a(href="/forum") Forum
+			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
new file mode 100644
index 0000000..257752b
--- /dev/null
+++ b/views/match.pug
@@ -0,0 +1,81 @@
+//- vim:ts=4:sw=4:
+
+-
+	var n_live = 0, n_fast = 0, n_slow = 0
+	for (let t of tickets) {
+		if (t.pace === 1) n_live ++
+		if (t.pace === 2) n_fast ++
+		if (t.pace === 3) n_slow ++
+	}
+
+mixin show_ticket(ticket)
+	- var setup = SETUP_TABLE[ticket.setup_id]
+	div
+		label
+			input(type="checkbox" name="tickets" value=ticket.ticket_id)
+			| #{setup.setup_name}
+
+doctype html
+html
+	head
+		include head
+		title Matches
+		style.
+			div.buttons { margin-top: 8px }
+	body
+		include header
+		article
+			h1 Matchmaking
+
+			if tickets.length > 0
+				form(method="post" action="/games/match/unqueue")
+					if n_live > 0
+						h3 Tickets - Live
+						each ticket in tickets
+							if ticket.pace === 1
+								+show_ticket(ticket)
+						div.buttons
+							button(name="pace" value="1") Remove all
+							button(type="submit") Remove
+					if n_fast > 0
+						h3 Tickets - Fast
+						each ticket in tickets
+							if ticket.pace === 2
+								+show_ticket(ticket)
+						div.buttons
+							button(name="pace" value="2") Remove All
+							button(type="submit") Remove
+					if n_slow > 0
+						h3 Tickets - Slow
+						each ticket in tickets
+							if ticket.pace === 3
+								+show_ticket(ticket)
+						div.buttons
+							button(name="pace" value="3") Remove All
+							button(type="submit") Remove
+					p
+			else
+				h3 Tickets
+				p You have not queued for any matches.
+
+			h3 Matches
+
+
+			if limit
+				p.error= limit
+			else
+				p Select what you want to play:
+
+				form(method="post" action="/games/match/queue")
+					p
+						each title in TITLE_LIST
+							each setup in title.setups
+								label
+									input(type="checkbox" name="setups" value=setup.setup_id)
+									| #{setup.setup_name}
+								br
+
+					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