Improving the Matching & Searching Algorithm

Games Other Halo
1

This topic concerns something we all know and have occasionally mentioned, but never seems to boil to the top of popularity. In short: The current H4 GUI for MM searching is inefficient, frustrating, and drives 343i to have to choose between giving players the flexibility to select the game they want and preventing playlist proliferation (dig that consonance, baby) . . . when having the best of both is perfectly possible.

This will take a bit to set up, so if you are still reading, please withhold judgement until the punch line is reached.

Imagine if, when you went into MM, you saw the following menu (and yes, I’m intentionally throwing in an unrelated suggestion which will hardly go unnoticed):

Social Play: Hop on, sign in, and blast enemy Spartans with your friends!
Slayer
Action Sack
Team Sports

Competitive Play: See how you stack up against others of similar skill . . . all skill levels welcome!
4v4 Team Slayer & Objective
6v6 Team Slayer & Objective
4v4 Team SWAT
4v4 Team Minigames
2v2 Team Doubles
2x4 Multi-Team
6-Player FFA

Now let’s say you want to play just social Slayer. Click on Slayer and the search begins. But let’s say you just want to play 4v4 social Slayer. In that case, you highlight Slayer, press “Y” (or some other button of choice), and you see the following:

Select gametypes to include in search:
4v4 Slayer
8v8 Slayer

Now you can deselect 8v8. If you wish to save the search criteria because you intend to play 4v4 for awhile, press “Y” again. Criteria save; 4v4 search begins. If you wish this to be for just this search without saving, press “B”. Criteria do not save; 4v4 search begins.

For a second, more complex example, let’s say you don’t care if you play KoTH or CTF - but you don’t want to play Extraction, Slayer, or Oddball. Highlight 4v4 Slayer & Objectives, press “Y”, and set up:

Select gametypes to include in search:
[] Slayer
[X] CTF
[] Extraction
King of the Hill
[_] Team Oddball

Save (or not save) and search.

Behind the scenes, the matching system performs a multi-dimensional search (I can describe this in detail if anyone cares, but will forgo that for the moment . . . just be aware that this type of search is not difficult to execute efficiently). Once a lobby is formed, the only gametypes available for voting will be those gametypes that every person in the lobby shares. So if you select everything - but your lobby includes someone just searching for CTF and nothing else - all 3 choices will be CTF. If everyone selects everything, than any of the choices might appear in the 3 slots. And if you get sick of playing CTF because of the one nut who doesn’t want to play anything else, then you just deselect “CTF”, search, and you will be placed in a lobby where CTF does not show as an option (note how this removes the need for a “veto” option by moving the veto from the lobby to the search criteria).

The advantage of this type of matching - and it is a massive advantage - is that it increases the effective size of the player pool for matching. Within a top-level list, everyone who has a particular gametype selected for search is a match option. To see the benefits, we can look at a concrete example (along with wishful thinking for population sizes).

Many people who play objectives really don’t care if it’s CTF or Extraction (they may have a slight preference, but would be happy with either). But if the two gametypes are split, those slight preferences become absolute vetoes:

Slayer List: 14,000
CTF List: 5,000
Extraction List: 1,000
KoTH List: 1,500
Oddball List: 500

Total 4v4 Population: 22,000

This snowballs. Because people just want to play an objective, they examine the list populations, know that they’ll get faster matches and better games in CTF. So even though they wouldn’t mind Extraction, the lower population dissuades them from visiting the list at all . . . leading to an even lower population . . . and so forth. However, with the multidimensional matching, you end up with the following numbers of people who have included those gametypes in their searches:

4v4 Slayer & Objectives
Slayer: 17,500
CTF: 12,500
Extraction: 5,500
KoTH: 8,000
Oddball: 3,500

While no gametype can exceed the total population of 22,000, each gametype within a list can have up to 22,000 people available for matching. Compare this to the above, where the matching population is a priori restricted to just the population of the gametype-specific playlist. Not only that, but if a player is absolutely insistent on playing Oddball and nothing else, that player is not only assured of getting Oddball (just like in the separated lists), but he or she has a vastly larger population out of which a match can be made.

There is no need to force players to play CTF if they do not want to, nor is there a need to force Oddball players into a 100-player list in order to ensure they play only Oddball. If matching were set up as outlined above, the best of both worlds results.

Nor do the single-gametype players needlessly dominate the matching. If a player initially searches with everything selected, but gets only Extraction and is tired of Extraction, that player merely needs to remove Extraction from his or her options, and all subsequent lobbies will be devoid of Extraction. The only penalty to that player is a reduced set of opportunities (by one gametype) for finding a match, and the only penalty to the player pool as a whole is a -1 to the Extraction population (but - rather importantly - not to the remainder of the list).

In the limit that every player selects just a single gametype, the matchmaking reduces to the exact equivalent of having separate lists for the gametypes. It can never get worse than that. It will always be at least equal to what we have now, and as the number of players searching for multiple gametypes increases, the quality of the matches and speed of matching improve accordingly.

From a player pool / matching perspective, the ideal situation is a single pool of players that includes all gametypes. However, this makes selecting the gametypes players want to search for quite inconvenient. From a usability standpoint, the number of gametypes within a list should be kept to a reasonable number that provides both a good pool and an unintimidating set of options. So the following would be okay:

Binary Slayer
Rock 'n Rail
Mini Slayer
Fiesta Classic
Lightning Flag

The following would not:

SWAT
Covenant SWAT
Forerunner SWAT
SHWATguns
Team Snipers
Team Snapshots
Legendary BRs
Team Slayer
v5 TTD Slayer
Infinity Slayer
Slayer Pro
Paintball

So proper implementation of the above depends primarily on ensuring that no list has more than 5 or 6 search options and that those options are ones that are likely to have a good deal of cross-participation.

TFNHF #3: Ranked Play & Ranks
TFNHF #2: You’re reading it.
TFNHF #1: DLC

2

Note how this could have solved the Slayer Pro dilemma (numbers are examples; I do not know the exact ones):

Total Slayer population: 5,000
% who only want to play Infinity: 70%
% who only want to play Pro: 5%
% who would play either: 25%

With the split lists, Pro would only have a population of 250.

With the combined lists, Pro would (actually, did) get outvoted the vast majority of the time.

With the multidimensional search, the effective matching population becomes:

Infinity: 4,750
Pro: 1,500

And you can definitely get good games with reasonable match times in a 4v4 list with a population of almost 1,500 players.

3

This is pretty ingenious. How come no one has thought of this before?

No more backing out of lobbies, no more quitting at the beginning of matches, and no more avoiding playlists because of one gametype.

This would have solved all of my problems with matchmaking. Since the gametypes selected pre-search rule out any gametypes players don’t want to play, we’d be voting/vetoing based strictly on maps. All the developer would have to do is put good gametypes in matchmaking (which 343i is not very good at, based on my experience with Halo 4).

This would also make it a lot easier for the developer to judge which gametypes are the most popular.

4

Thanks.

I’d wanted to post about this for a while, but always forgot to or didn’t feel like taking the time to write it down when I remembered. But after the whole DLC and IS thing - which I’m sure most of the players knew ahead of time wouldn’t work - it spurred me to finally get off my -Yoink- and post it.

I don’t know how much power Microsoft has in those decisions compared to 343i, but the distinct lack of good judgement (in my opinion, at least) for that experiment gave me pause for H5. So I thought I’d try to put down all my thoughts (and there are more) in the hopes that they’re not completely stupid and end up being somewhat helpful.

5

I thought of something else, too. This would help ease rotational gametypes. The gametype could always be there . . . they just toggle whether you can select that gametype in the playlist. So if it’s that game’s turn, it shows up. If not, it doesn’t. That way, the rotational ones don’t have to be in their own playlist so that they end up a 2-week period with 250 peak players in it.

6

That is actually a very clever way of letting people play what they want without segregating certain playlists. This would definitely be a great idea for future Halo games.

7

Since Subduction’s reply above, here are the active threads from the H4 forum that the above matching system would have rendered moot:

TeaM Objectives
KoTH
Need More Consolidation
Dominion Trashed

Here are the ones from the MM forum:

Extraction
Rotational Playlists & DLC
Playlist Reorganization
SWAT
Dominion

So that’s about 1 thread a day in the 2 primary forums. Moreover, there are numerous JIP / quit / lobby dissolving problem threads that the above indirectly addresses, as it (1) allows players to search for exactly what they want to play - and nothing else; and, (2) increases the effective matching population to reduce search times.

We need something like this.

8

Maximus’ suggestion in this thread is the best I’ve seen. What I like about it, is it places the power to choose in the individual player’s hands.

As a newcomer who likes to play big team slayer variants almost exclusively, I feel that the playlist reorganization has unnecessarily forced me to play CTF, KoTH and Big Team Regicide quite a bit. Before reorganization, BTIS had a healthy population at almost all times, and the new BTB playlist has maintained roughly the same numbers.

I realize, and respect that there are some within the playlist who like a little variation, and enjoy the occasional objective gametype. I truly want them to enjoy and get the games they want. But it is also frustrating for me to know that based on the votes for IS gametypes in every lobby, that there is more than enough population to support me only playing slayer with others who just want to play slayer as well.

Max’ suggestion would allow those who want variety to be matched in lobbies with similar minded individuals, while leaving me free to play only slayer. And the individual player can then choose the appropriate balance between potential wait times and how selective/exclusive he wants his playlist to be.

9

As lesser attractive alternative, if the same system that tracks our CSR/Trueskill, and matches us with similarly skilled players, would track our preferences for gametypes/maps based on our voting in the lobby, and then use that information as one of the factors in placing us in a lobby, to attempt to place people who like the same gametypes/maps in the same lobby, it would not be as ideal as Maximus’ idea, but would still increase the likelihood that I get to play the games I want, without sacrificing population.