Add match making.

6 files changed, 512 insertions, 0 deletions

diff --git a/schema.sql b/schema.sql
index 4c64ecd..93b73cb 100644
--- a/schema.sql
+++ b/schema.sql
@@ -208,6 +208,44 @@ 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 (
@@ -525,6 +563,47 @@ 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;
@@ -570,6 +649,7 @@ 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 0fcaf43..4d3db19 100644
--- a/server.js
+++ b/server.js
@@ -96,6 +96,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.
  */
@@ -170,6 +184,7 @@ 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}"
@@ -1961,6 +1976,277 @@ 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 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 dd12772..85522df 100644
--- a/views/about.pug
+++ b/views/about.pug
@@ -74,6 +74,26 @@ 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.
+				<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 454c35a..dfeef5c 100644
--- a/views/header.pug
+++ b/views/header.pug
@@ -6,6 +6,8 @@ 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
new file mode 100644
index 0000000..504cef5
--- /dev/null
+++ b/views/match.pug
@@ -0,0 +1,71 @@
+//- 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") &#x274c; 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