Firebase: How to match opponents in a game?

algorithm, firebase, firebase-realtime-database, nosql

Solution

It is a challenging task in NoSQL environment especially if you want to match multiple fields

in your case, I would setup a simple index by color and within the color I would store the reference to the game with priority set to minRating. That way you can query the games by the prefered colour with the priority of minRating.

indexes: {
  color:{
     white:{
        REF_WITH_PRIORITY_TO_RATING: true
     },
     black:{
        REF_WITH_PRIORITY_TO_RATING: true
     }
  }
}

if you want to get info whenever the match opens the game:

ref = new(Firebase)('URL');
query =ref.child('color_index/white/').startAt(minPriority);
query.on('child_added',function(snapshot){
  //here is your new game matching the filter
});

This, however, it would get more complex if you introduce multiple fields for filtering the games for example `dropRate`, `timeZone`, 'gamesPlayed' etc... In this case, you can nest the indexes deeper:

indexes: {
  GMT0: {
    color:{
       white:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
       black:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
  }
  GMT1: {
       // etc
  }
}

Problem

I'm implementing a social chess game. Every user can create a new game, and they'll wait until the system will find an opponent for them. When user creates a game, they specify constraints: color they'd like to play, and opponent's minimal chess rating. Opponents can either match or not match. For example, the following two opponents will match: ``` // User 1 with rating 1700 // User 2 with rating 1800 // creates this game // creates this game game: { game: { color: 'white', minRating: 1650 minRating: 1600 } } // User did not specify a preferred color, // meaning they do not care which color to play ``` So, if User 1 is the first user in the system, and created their game, they'll wait. Once User 2 creates their game, they should be matched immediately with User 1. On the other side, the following two opponents won't match, because they both want to play white. In this case, both should wait until someone else creates a game with `color: 'black'` (or color not specified), and `minRating` that would match the requirements. ``` // User 1 with rating 1700 // User 2 with rating 1800 // creates this game // creates this game game: { game: { color: 'white', color: 'white' minRating: 1600 minRating: 1650 } } ``` My concerns related to scenarios where thousands of users creates new games at the same time. How do I make sure that I match opponents without creating deadlocks? i.e. how do I prevent scenarios when User 1, User 2, and User 3 are trying to find an opponent at the same time, and their matching algorithms return User 99. How do I recover from this scenario, assigning User 99 to only one of them? How would you use the power of Firebase to implement such a matching system?

Original source