Recently I had the opportunity to work on the backend services of an online game where two players can mount a deck of summonable creatures and fight against each other in real time on their mobile devices. The game is fun and as the user base begins to grow a problem arises: how can we join two players in a fair fight?
Imagine that we have, at a given moment, 1200 players searching for an opponent to fight. Some of them may have 10 hours of gaming while others may have 200 hours. Some are in early levels, others, way more advanced. Some may have a long stream of wins while others barely win a couple of fights. How do we measure who is a good opponent to who?
The K-Nearest Neighbors (KNN) is, probably, one of the first algorithms we learn when studying machine learning or applied statistics due to its simplicity and easy-to-grasp concepts. It is a distance-based machine-learning algorithm because it relies on the idea that related data should appear in the same region so, if two samples have a correlation, they should appear near each other in their projected space.
Look at the graphics:
On the left graphic, there are 3 classes: yellow, green, and blue. We also have an unknown class point, represented by the white color, which we wish to classify based on the probability that it pertains to one of their “neighbor” classes.
To achieve that, we calculate the distance between the white point to all the other points in the population as exemplified in the right image, and then choose the
k nearest points. If
k=3, for example, we have
2 yellow points and 1 blue point selected, so there is a
66,6% of chance that this point is of yellow class, and... that's it. This is the basic idea of the K-Nearest Neighbors (KNN) algorithm. Really! It's just that.
You can see the three steps illustrated in the following graphics:
So, the problem to solve is to choose a fair opponent for a given player among the universe of online players. I can’t publish real data here, but we can simulate and illustrate the problem with our own generated data. So let’s start with basic data creation on SQLServer.
if (object_id('tempdb..#PlayerData') is not null) drop table #PlayerData create table #PlayerData ( PlayerID int primary key identity, WinLossRatio float, Accuracy float, PingTimeMS int, ) -- create a population of 100,000 random players declare @i int = 1 while @i <= 100000 begin insert into #PlayerData (WinLossRatio, Accuracy, PingTimeMS) values (rand(), rand(), round(rand()*1000, 0)) set @i = @i + 1 end select top 5 * from #PlayerData
Good! We have a PlayerData table with 100,000 random players and 3 relevant attributes:
While the first two are related to the player’s in-game performance, we also have available on our database, the last known user’s ping information. This is pretty useful to move away players with bad connection conditions and to show that we can do multi-dimensional projections on KNN implementation.
/* we should normalize the PingTimeMS data to the (0..1) range, considering the max(PingTimeMS) as the limit, so lets store it in @MaxPingTimeMS */ declare @MaxPingTimeMS float = (select max(PingTimeMS) FROM #PlayerData) declare @k int = 3 /* K hyper parameter of KNN */ declare @TargetPlayerID int = 1 -- query to find the K-nearest neighbors of the TargetPlayerID select top (@K) WITH TIES player.PlayerID, player.WinLossRatio, player.Accuracy, (player.PingTimeMS / @MaxPingTimeMS) NormalizedPing, /* euclidean distance between attributes */ sqrt( power(player.WinLossRatio - opponent.WinLossRatio, 2) + power(player.Accuracy - opponent.Accuracy, 2) + power( (player.PingTimeMS / @MaxPingTimeMS) - (opponent.PingTimeMS / @MaxPingTimeMS), 2) ) AS Distance from #PlayerData as player, (select * from #PlayerData where PlayerID <> @TargetPlayerID) as opponent where player.PlayerID = @TargetPlayerID and player.PingTimeMS < 400 /* minimum acceptable latency */ order by Distance
Bingo! We had, with a single query, calculated the
Kbetter fit for a
@TargetPlayerID player fight considering all the
3 selected opponents' attributes using machine learning techniques! We can generalize this query in a
stored procedure and execute it from the backend controller code inside a REST API endpoint and consume it on our devices.
This is, obviously, a pretty naive implementation with the purpose of exemplifying how we could rapidly implement and test machine learning techniques in this scenario. The KNN is known for its poor performance with large datasets but, if we can keep our problem’s population short enough, and choose wisely the attributes, we can use KNN for near real-time match-making in online gaming.
On the project where we test this idea, we have around
2,500,000 fights per day,
~60..80 fights starting per second on peaks and the database server barely reaches 30% of CPU load which means we can still support a good amount of player base increase before we reach the hardware limit.
Keep it simple, stupid, they say!
Thanks for reading!
Originally written for http://programmingdrops.com/