Implement Algorithm for party matching

[BlackYps]

The planned 4v4 TMM queue needs an algorithm that can match parties of different sizes to create complete teams.
here is an outline how that algorithm could work:

1. you list all the parties in queue by their average rating.
2. Take a party and select the neighboring parties alternating between lower and higher until you have 8 players. If the next party to select would leave you with more than 8 players you skip that party and try the next one.
3. you now have a list of parties that will be in your potential game. Distribute them into two teams by starting with the party with the highest total rating and then adding the next smaller one to whatever team has less total rating at that moment.
4. add this game to a games list
5. repeat 2. to 4. for every party.
6. you now have a list of potential games with minimal rating variation and minimal rating imbalance
7. select the game with the highest fairness from the list to finally match the parties in that game. (Highest fairness could be calculated from trueskil game quality or directly from rating variation and imbalance from the steps before)

I would assign myself for this, but I am missing the rights in this repo

[Askaholic]

A few things:

It seems to me like this algorithm is broken into 2 separate stages, create teams and then evaluate quality. Since our existing code is already structured like this, all you'd have to do is figure out the "create teams" step for 4v4 (or in general), and our existing algorithm will handle the "evaluate quality" step. Right now we have a special case for creating teams of 2 from parties of 1:

server/server/matchmaker/algorithm.py

Lines 289 to 308 in 31168aa

	def make_teams_from_single(
	searches: List[Search],
	size: int
	) -> Tuple[List[Search], List[Search]]:
	"""
	Make teams in the special case where all players are solo queued (no
	parties).
	Tries to put players of similar skill on the same team as long as there are
	enough such players to form at least 2 teams. If there are not enough
	similar players for two teams, then distributes similarly rated players
	accross different teams.
	# Algorithm
	1. Group players into "buckets" by rating. This is a sort of heuristic for
	determining which players have similar rating.
	2. Create as many games as possible within each bucket.
	3. Create games from remaining players by balancing teams with players from
	different buckets.
	"""

As well as a general way to handle any party size but without taking rating into account:

server/server/matchmaker/algorithm.py

Lines 408 to 418 in 31168aa

	def make_teams(
	searches: List[Search],
	size: int
	) -> Tuple[List[Search], List[Search]]:
	"""
	Tries to group as many searches together into teams of the given size as
	possible. Returns the new grouped searches, and the remaining searches that
	were not succesfully grouped.
	Does not try to balance teams so it should be used only as a last resort.
	"""

As for the algorithm you described, steps 2 and 3 won't work exactly as written. For instance in step 2 you could get a list of parties with sizes like [3, 3, 2] and there would be no possible way to split those into even teams in step 3. If you can adapt your step 2 algorithm to create relatively balanced teams of 4, then you can simply ship those off to the existing matchmaker code and it will find appropriate matches between the teams.

The existing matchmaker code can be found here:

server/server/matchmaker/algorithm.py

Lines 142 to 160 in 31168aa

	def find(self) -> List[Match]:
	self._logger.debug("Matching with stable marriage...")
	searches = list(self.searches)
	if len(searches) < 30:
	ranks = _MatchingGraph.build_full(searches)
	else:
	ranks = _MatchingGraph.build_fast(searches)
	_MatchingGraph.remove_isolated(ranks)
	self.matches.update(StableMarriage().find(ranks))
	remaining_searches = [
	search for search in self.searches if search not in self.matches
	]
	self._logger.debug("Matching randomly for remaining newbies...")
	self.matches.update(RandomlyMatchNewbies().find(remaining_searches))
	self._register_unmatched_searches()
	return self._remove_duplicates()

It's based on the stable marriage algorithm but modified for simple (undirected) graphs (since game quality is symmetric).

[BlackYps]

As I see it we have basically two options. First we could use the general structure of the existing code and generify the "team building" process. So it would look like this:
0. put all full sized parties in a teams list
1. list all the remaining parties in queue by their average rating.
2. Take the first party and select the neighboring parties until you have 4 players.
If the next party to select would leave you with more than 4 players you skip that party and try the next one.
3. Add this to the teams list
4. repeat 2. and 3. with the remaining players until you have exhausted the list. Alternating the beginning between top
and bottom, so the top players don't get excluded everytime the player number isn't divisible by the team size
5. perform stable marriage with the teams list

This would be rather fast to implement, but I see the potential issue that we could get games that are not really optimal.
Alternatively we could do this:
1. list all the parties in queue by their average rating.
2. Take a party and select the neighboring parties alternating between lower
and higher until you have 8 players. If the next party to select would leave
you with more than 8 players or unable to bisect it into two teams of 4 you skip that party and try the next one.
or you could find a party to drop so you can incorporate the new candidate
3. you now have a list of parties that will be in your potential game. Distribute
them into two teams by starting with the party with the highest total rating and then
adding the next smaller one to whatever team has less total rating at that moment.
4. add this game to a games list
5. repeat 2. to 4. for every party.
6. you now have a list of potential games with minimal rating variation and minimal rating imbalance.
7. remove all games with match quality below threshold
8. find combination of potential games that allows for maximal number of games to launch
(not trivial, because a player is listed in more than one potential game)
8a. loop: pick the first game from the game list and remove all other games that contain the same players
8b. save this game combination
8c. eliminate the first game and repeat 8a and 8b until list is empty
9. if there is more than one solution, pick the one with highest total game quality
possible shortcuts: sort by game quality first, abort when you find a solution with
the full number of theoretically possible games (floor(playersInQueue/(teamSize*2)))

This is incompatible with the stable marriage approach.

Does it make sense to implement the first algorithm first, to get a working 4v4 queue out fast and then maybe "upgrade" to the second one later? Or should we aim for the second one right away?

[cleborys]

I talked to @BlackYps about how to proceed and we think that the current matchmaker code with the two stages of 1. constructing full-sized teams from parties and then 2. doing 1v1 matching on the full-sized teams is quite complicated and trying to fit his algorithm in that model would be very hacky. I'll make a suggestion for how to refactor the code so that the "queue" logic is separated from the "matchmaker" logic (right now part of the "building teams from buckets" happens in matchmaker_queue) so that afterwards it would hopefully be easy to swap out the "matchmaker" parts.

I think it would also be helpful to experiment with different matchmaking algorithms and see how they score against each other, something that's probably better done offline. The only thing missing for that is good data for the input - ideally at every queue pop we would like to save a list of all searches present (their trueskill ratings should be enough) to then use as simulation input.
I can't think of a good way to achieve this. It's a bit too much data to simply log out (?!), it seems quite annoying (but I think it's possible) to reconstruct from existing log data, it seems overkill to write this to the database.
Of these reconstructing from existing log data is maybe the best option for now but I think logs are still hard to obtain, especially if we want lot of data?
If graphana was an option then I think that would be ideal, but I'm not yet convinced that we can send this data to graphana in an appropriate format.

Let me know if you have suggestions :)