which is the best approach or algorithm to calculate real-time ranking

Question

I want to know the fastest and most efficient way to compute points and ranking in real time.

I'm doing a betting football game (a game where users try to predict the outcome of a game before it). In my country is called "Quiniela".

Players put "predictions" just before the match starts. My question is: from the moment the game starts, which is the most efficient way (not just code level but to the database and server) to calculate the ranking for the players "real time" as their predictions regarding the actual outcome of the game.

For example:

If a Team1 vs Team2 plays, the user U1 predicted that the game would end 0-0, U2 predicted the game would end 1-0, U3 predicted the game would would end 1-1.

When starting the game, the U1 would be to first in the ranking because, if the match ends like this, his prediction would be correct, or at least the most accurate.

Then the score switches to 1-0, and the user U1 would be the last of the ranking (because his prediction is not possible anymore), U2 would be the first and U3 second.

If the score changes to 1-1, U2 would go first, U3 would be second (because he guessed part of the result) and U3 last.

I thought about creating a tree of possibilities with one level (0-0 first node, with 1-0 and 0-1 as child nodes) as you change the score, changes the Ranking "temporarily" and I would keep it in cache.

Once the game is over, I keep the latest Ranking in the database.

There is a more optimal way to solve this problem? It has been proposed before and already solved? I'm using MySQL for database, PHP (Cake Php) for the server and a bunch of mobiles who ask for the ranking once in a while.

Answer 1

You could use a heuristic function that given a score and a prediction calculates the "value" of the prediction as an integer. This "value" could be the distance between the prediction and the score (a negative value means the prediction is impossible, 0 means it's an exact match and a positive value means it's still possible). Since the "value" of each prediction is an integer sorting is easy and finding the winner is even easier.

I have written a possible implementation of this heuristic function (for a gaming score with house and away scores) using Node.js along with a few tests (using your examples).

You can find the gist at https://gist.github.com/jparreira/081aeaddc592696c0222.

// Heuristic function to calculate the "value" of a prediction against a given score
// basically it measures the distance of the prediction to the given score as an integer number
// a negative scoring means that a match with this prediction is already impossible
 
function scoring(score, prediction) {
  res = 0;
 
  // calculates the diatance of prediction for the house result
  house_distance = prediction.house - score.house;
 
  if(house_distance > 0)
        res += Math.abs(house_distance);
  else
        res -= Math.abs(house_distance);
 
  // calculates the distance of prediction for the away result
  away_distance = prediction.away - score.away;
 
  if(away_distance > 0)
    res += Math.abs(away_distance);
  else
    res -= Math.abs(away_distance);
 
  return res;
}
 
// a series of score to test
 
scores = [
	{ house:0, away:0 },
	{ house:1, away:0 },
	{ house:1, away:1 },
	{ house:2, away:1}
];
 
// the predictions to evaluate
 
predictions = [
    { house:0, away:0 },
    { house:1, away:0 },
    { house:1, away:1 },
    { house:2, away:1 }
];
 
// iterate through the scores and evaluate each prediction
 
for(s=0; s < scores.length; s++) {
	console.log("******************************************");
	console.log ("CALCULATING HEURISTICS FOR SCORE: " + scores[s].house + "-" + scores[s].away);
 
	user_winner = null;
	winner_scoring = null;
 
	// iterate through the predictions
	for(i=0; i < predictions.length; i++) {		
		user = i + 1;
 
		// calculate this prediction scoring
		prediction_scoring = scoring(scores[s], predictions[i]);
 
		console.log("   prediction of user U" + user + " " + predictions[i].house + "-" + predictions[i].away + " got scoring of " + prediction_scoring);
 
		if(prediction_scoring >= 0) {
			// prediction is an exact match or at least is still possible
			if(user_winner == null || prediction_scoring < winner_scoring) {
				// first evaluation or current prediction is better than the current winner
				user_winner = i;
        	    winner_scoring = prediction_scoring;
			}
        }
	}
 
	// shows the current winner
	console.log("CURRENT WINNER FOR THIS SCORE IS U" + (user_winner + 1));	
}