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: https://github.com/FAForever/server/blob/31168aa6b34ba1b81db5831a66fce4b750aecdfe/server/matchmaker/algorithm.py#L289-L308

As well as a general way to handle any party size but without taking rating into account: https://github.com/FAForever/server/blob/31168aa6b34ba1b81db5831a66fce4b750aecdfe/server/matchmaker/algorithm.py#L408-L418

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: https://github.com/FAForever/server/blob/31168aa6b34ba1b81db5831a66fce4b750aecdfe/server/matchmaker/algorithm.py#L142-L160 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 :)