Idea: Selection system «PriorityScore»
I propose a new algorithm for selecting players based on the calculation of “PriorityScore” using the “KD-tree” search system.
More information:
I noticed my level-based matchmaking idea using a symmetrical range wasn’t well-received; many didn’t understand how it worked and believed it would cause problems. I’ve decided to improve the idea, using something significantly better than level-based matching alone. Let’s consider a matchmaking algorithm for PVP minigames where a player’s “PriorityScore” is the basis for the search, with a focus on using a KD-tree.
Selection system by level
1. Data Preparation:
Each player receives a PriorityScore, calculated using the formula: PriorityScore = 0.5 Level + 0.3 K/D + 0.2 Winrate. The coefficients (0.5, 0.3, 0.2) are weights indicating the importance of each parameter. These weights are determined experimentally to find the optimal balance between matchmaking speed and player skill balance. Winrate is the percentage of wins, normalized to a 0-1 range (e.g., 75% wins = 0.75).
Example Calculation based on player stats:
Level: 17
K/D: 1.7
Winrate: 43% = 0.43 (normalized value)
PriorityScore = 0.5 17 + 0.3 1.7 + 0.2 0.43
PriorityScore = 8.5 + 0.51 + 0.086
PriorityScore = 9.096
All players waiting for a game are entered into a KD-tree. A KD-tree is a smart data structure that allows for very fast nearest-neighbor searches (it’s basically a highly efficient player catalog). In this case, the KD-tree organizes players by their PriorityScore. Players on different platforms (PC, Mobile, Console) are stored in separate KD-trees.
2. Request for game search
When a player wants to start a game:
- The system calculates their PriorityScore.
- The system accesses the appropriate KD-tree (for their platform).
- Nearest-Neighbor Search:The system uses the KD-tree to find players with a PriorityScore close to the current player’s PriorityScore. It begins searching within a small range around the player’s PriorityScore. The system initially searches for players with a PriorityScore within ±10 of the current player’s value.
3. Search Expansion:
If the initial search range doesn’t find enough players (e.g., fewer than 7 players for a full game), the system gradually expands the search range. Importantly, the expansion is symmetrical—the system increases the range on both higher and lower sides of the target PriorityScore. This prevents a situation where, for example, high-level players consistently play with much lower-level players.
4. Dynamic Adjustment:
If the search takes too long (say, more than 20 seconds), the system further expands the search range and slightly lowers the PriorityScore similarity requirement to find players faster. However, the system aims to maintain balance by deviating minimally from the desired PriorityScore range.
5. Prioritization:
Players with low PriorityScores (new players) have higher priority in matchmaking to avoid long wait times.
Handling Extreme Cases:For players with extreme PriorityScores, the system expands the search to the opposite end of the scale but prioritizes closer matches.
6. Completing the search:
When enough players with relatively close PriorityScores are found, the game begins.
7. KD-tree Advantages:
Imagine a huge room full of people. Each person has a numerical value—PriorityScore—representing their skill level in the game. You need to quickly find people with similar PriorityScores to form a team.
A simple way is to approach each person and compare their PriorityScore to yours. This is slow and inefficient, especially with many people.
A KD-tree is like a smart room plan. This plan divides the room into zones so that people with similar PriorityScores are near each other. Now, you don’t need to check every person. You look at the plan, find the right zone, and quickly find the players you need.
Thus, the KD-tree allows you to very quickly find similar players by PriorityScore, without checking everyone in a row. This is especially important when there are a lot of players.
8. Experimental tuning:
An important part is the experimental tuning of the weights in the PriorityScore formula. It is necessary to conduct tests with different weights, tracking the search time and the balance of games. The goal is to find the optimal weights that will ensure both fast selection and balanced games.
Thanks for reading this far, and if you like the idea, don’t forget to vote for it!