Base de feu :Comment affronter des adversaires dans un jeu ?

Question

Je mets en œuvre un jeu d'échecs social.Chaque utilisateur peut créer une nouvelle partie et attendra que le système lui trouve un adversaire.

Lorsque l'utilisateur crée un jeu, il spécifie des contraintes :la couleur qu'ils aimeraient jouer et la note minimale de l'adversaire aux échecs.

Les adversaires peuvent soit correspondre, soit ne pas correspondre. Par exemple, les deux adversaires suivants s'affronteront :

// 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

Ainsi, si l'utilisateur 1 est le premier utilisateur du système et qu'il a créé son jeu, il attendra.Une fois que l'utilisateur 2 a créé son jeu, il doit être immédiatement mis en correspondance avec l'utilisateur 1.

De l’autre côté, les deux adversaires suivants ne s’affronteront pas, car ils veulent tous deux jouer les blancs.Dans ce cas, les deux doivent attendre que quelqu'un d'autre crée un jeu avec color: 'black' (ou couleur non précisée), et minRating cela correspondrait aux exigences.

// 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
}                                       }

Mes préoccupations concernaient les scénarios dans lesquels des milliers d'utilisateurs créent de nouveaux jeux en même temps.Comment puis-je m'assurer de faire correspondre mes adversaires sans créer d'impasse ?c'est à dire.comment puis-je éviter les scénarios dans lesquels l'utilisateur 1, l'utilisateur 2 et l'utilisateur 3 tentent de trouver un adversaire en même temps et que leurs algorithmes de correspondance renvoient l'utilisateur 99.Comment puis-je me remettre de ce scénario, en attribuant l'utilisateur 99 à un seul d'entre eux ?

Comment utiliseriez-vous la puissance de Firebase pour mettre en œuvre un tel système de correspondance ?

Answer 1

C'est une tâche difficile dans un environnement NoSQL, surtout si vous souhaitez faire correspondre plusieurs champs

dans votre cas, je configurerais un simple index par couleur et dans la couleur je stockerais la référence au jeu avec la priorité définie sur minRating.De cette façon, vous pouvez interroger les jeux par couleur préférée avec la priorité minRating.

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

si vous souhaitez avoir des informations à chaque fois que le match ouvre le jeu :

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
});

Cependant, cela deviendrait plus complexe si vous introduisiez plusieurs champs pour filtrer les jeux par exemple. dropRate, timeZone, 'jeux joués' etc...Dans ce cas, vous pouvez imbriquer les index plus profondément :

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

Answer 2

Le choix évident comme point de départ serait la couleur, car il s’agit d’une exigence exclusive.Les autres ressemblent davantage à des résultats pondérés, ils pourraient donc simplement augmenter ou diminuer le poids.

Utilisez les priorités pour les plages min/max et conservez chacune dans un « index » distinct.Ensuite, récupérez les allumettes pour chacun et créez une union.Considérez cette structure :

/matches
/matches/colors/white/$user_id
/matches/ranking/$user_id (with a priority equal to ranking)
/matches/timezones/$user_id (with a priority of the GMT relationship)

Maintenant, pour interroger, je voudrais simplement récupérer les correspondances dans chaque catégorie et les classer en fonction du nombre de correspondances.Je peux commencer par les couleurs, car il ne s'agit probablement pas d'une note facultative ou relative :

var rootRef = new Firebase('.../matches');

var VALUE = {
   "rank": 10, "timezone": 5, "color": 0
}

var matches = []; // a list of ids sorted by weight
var weights = {}; // an index of ids to weights

var colorRef = rootRef.child('colors/black');
colorRef.on('child_added', addMatch);
colorRef.child('colors/black').on('child_removed', removeMatch);

var rankRef = rootRef.child('ranking').startAt(minRank).endAt(maxRank);
rankRef.on('child_added', addWeight.bind(null, VALUE['rank']));
rankRef.on('child_removed', removeWeight.bind(null, VALUE['rank']));

var tzRef = ref.child('timezone').startAt(minTz).endAt(maxTz);
tzRef.on('child_added', addWeight.bind(null, VALUE['timezone']));
tzRef.on('child_removed', removeWeight.bind(null, VALUE['timezone']));

function addMatch(snap) {
   var key = snap.name();
   weights[key] = VALUE['color'];
   matches.push(key);
   matches.sort(sortcmp);
}

function removeMatch(snap) {
   var key = snap.name();
   var i = matches.indexOf(key);
   if( i > -1 ) { matches.splice(i, 1); }
   delete weights[key]; 
}

function addWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] += amt;
      matches.sort(sortcmp);
   }
}

function removeWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] -= amt;
      matches.sort(sortcmp);
   }
}

function sortcmp(a,b) {
   var x = weights[a];
   var y = weights[b];
   if( x === y ) { return 0; }
   return x > y? 1 : -1;
}

D'accord, j'ai maintenant donné ce que tout le monde demande dans ce cas d'utilisation : comment créer une clause Where rudimentaire.Cependant, la réponse appropriée ici est que les recherches doivent être effectuées par un moteur de recherche.Ce n’est pas une condition de localisation simple.Il s'agit d'une recherche pondérée des meilleures correspondances, car les champs comme la couleur ne sont pas facultatifs ou simplement le meilleur match, tandis que d'autres - classement peut-être - sont les correspondances les plus proches dans les deux sens, tandis que certains affectent simplement le qualité du match.

Vérifier lampe de poche pour une intégration ElasticSearch simple.Avec cette approche, vous devriez pouvoir profiter des excellents outils de pondération, du tri dynamique et de tout ce dont vous avez besoin pour effectuer un algorithme de correspondance approprié.

Concernant les impasses.Je ne mettrais pas trop l'accent ici tant que vous n'aurez pas des centaines de transactions par seconde (c'est-à-diredes centaines de milliers d'utilisateurs en compétition pour des matchs).Divisez le chemin où nous écrirons pour accepter une jointure et effectuer une transaction afin de garantir qu'une seule personne réussit à l'obtenir.Gardez-le séparé des données lues afin que le verrou sur ce chemin ne ralentisse pas le traitement.Gardez la transaction à une taille minimale (un seul champ si possible).