Ranking Servers for Natural Selection 2

The next version of Natural Selection 2 contains an algorithm I designed for ranking servers. It powers the “play now” button at the top of the menu.

The goal is to come up with a smooth expression that is proportional to the probability that a player will have a good game on a server. For a good game, all conditions should be simultaneously true, so we express this as a product. Each component is defined below.

\displaystyle \text{Score} = \text{PlayersScore} \cdot \text{Ping} \cdot \text{Performance} \cdot \text{Skill} \cdot \text{Joinable} \cdot \text{Favorite}

Number of Players

This function determines the viability of a game from the number of players. Games start to become viable as they pass 12 players.

\displaystyle \text{Viability} = \frac{1}{1 + e^{- 0.5 (\text{Players} - 12)}}

Viability as a function of the number of players

Viability as a function of the number of players

We don’t just want to put the player on the biggest game available though, we also want to maintain a healthy server pool with many viable games. To do this we also want to help seed servers by putting players on the server that will increase the viability of as many player slots as possible as much as possible. To do this we give servers a bonus based on the derivative of viability.

\displaystyle \frac{d \text{Viability}}{d \text{Players}} = \frac{201.714 e^{0.5 \text{Players}}}{(403.429 + e^{0.5 \text{Players}})^2}

Derivative of "Viability" with respect to the number of players

Derivative of “Viability” w.r.t. the number of players

We only care about increasing the viability of the server if there are open slots, so in the combined function we scale the effect of the derivative of viability by the number of open player slots. Seeding servers is also only a secondary goal. The primary goal must be giving the player a good game, or players will just ignore the ranking or “play now” button, so seeding is given a lower weight in the combined function.

\displaystyle \text{PlayersScore} = \frac{2}{3} \text{Viability} + \frac{1}{3}\frac{d \text{Viability}}{d \text{Players}} \max(0, \text{MaxPlayers} - \text{Players} - 1)

The combined viability score for a 24 player server

The combined viability score for a 24 player server

The combined function ensures that servers with almost enough players for a good game get priority over servers that are already healthy, but that otherwise players will end up on a server with a healthy number of players.

Ping

The player’s latency to the server is as important a factor as whether the server has enough players. Once it crosses 100 milliseconds, it is a key factor.

\displaystyle \text{Ping} = \frac{1}{1 + e^{1/40 (\text{PingMs - 100})}}

Score as a function of latency in millseconds

Score as a function of latency in millseconds

The combined function showing the tradeoff between the number of players on the server and the latency to the server

The combined function showing the tradeoff between the number of players on the server and the latency to the server

Skill

All other things being equal, we’d like to put the player on a server with similarly skilled players. However, when a player joins a server, they will change the mean score of the server, so the amount we care about the server’s average skill level should increase as the number of players on the server increases. We use a statistic inspired by the z score. (The mean skill is available to us, but the variance is not, so this assumes a default.) Rather than doing something expensive with erf as would be customary to convert a z score into something like a probability, we use a simple exponential. Aside from being a cheaper function, it prevents the ranking from prioritizing skill over ping even when the skill difference is tremendous.

\displaystyle \text{if}\ \text{players} < 2, \text{Skill} = 1

\displaystyle \text{else}, \text{Skill} = \exp{\left(-0.1 \frac{|\text{ServerSkill} - \text{PlayerSkill}| \sqrt{\text{Players} - 1}}{100 \sqrt{12}}\right)}

Performance, Favorites, and Joinable

Servers in NS2 are graded on their ability to keep up with the load placed on them. According to matso, you don’t want to play on a server with score less than -10, and everything above 10 is about equivalent.

\displaystyle \text{Performance} = \frac{1}{1 + e^{- 0.2 \text{PerfScore}}}

We give special priority to favorites, and to servers that have open slots. For “play now,” joinable is just a filter. For server ranking, it’s somewhat useful to see servers you expect to see in the list even if you can’t join them, just so you know they still exist.

\text{Joinable} = \text{if}\ \text{Players} < \text{MaxPlayers}\ 1\ \text{else}\ 0.05
\text{Favorite} = \text{if}\ \text{IsFavorite}\ 2\ \text{else}\ 1

Advertisements

5 comments

  1. Pingback: Aim To Please Update (279) Released! - Natural Selection 2

  2. CptClutch

    This is amazing, well implemented and designed! This will definitely help retain NS2 players, even if the player population increases. I only have one question: Does this algorithm take care of huge servers (such as woozas 64 player) not steal players from other servers?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: