Base di fuoco:Come abbinare gli avversari in un gioco?

Question

Sto implementando una partita a scacchi sociale.Ogni utente può creare un nuovo gioco e aspetterà finché il sistema non troverà un avversario per lui.

Quando l'utente crea un gioco, specifica i vincoli:colore con cui vorrebbero giocare e il punteggio minimo di scacchi dell'avversario.

Gli avversari possono eguagliare o non eguagliare. Ad esempio, i seguenti due avversari corrisponderanno:

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

Pertanto, se l'Utente 1 è il primo utente nel sistema e ha creato il gioco, aspetterà.Una volta che l'Utente 2 ha creato il proprio gioco, dovrebbe essere immediatamente abbinato all'Utente 1.

D'altro canto, i seguenti due avversari non si abbinano, perché entrambi vogliono giocare con il bianco.In questo caso, entrambi dovrebbero attendere che qualcun altro crei un gioco con color: 'black' (o colore non specificato), e minRating che corrisponderebbe ai requisiti.

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

Le mie preoccupazioni riguardavano scenari in cui migliaia di utenti creano nuovi giochi contemporaneamente.Come posso assicurarmi di abbinare gli avversari senza creare situazioni di stallo?cioè.come posso evitare scenari in cui l'Utente 1, l'Utente 2 e l'Utente 3 tentano di trovare un avversario contemporaneamente e i loro algoritmi di corrispondenza restituiscono l'Utente 99.Come posso recuperare da questo scenario, assegnando l'Utente 99 a uno solo di essi?

Come utilizzeresti la potenza di Firebase per implementare un sistema di corrispondenza di questo tipo?

Answer 1

È un compito impegnativo in ambiente NoSQL, soprattutto se si desidera abbinare più campi

nel tuo caso, imposterei un semplice indice per colore e all'interno del colore memorizzerei il riferimento al gioco con priorità impostata su minRating.In questo modo puoi interrogare i giochi in base al colore preferito con la priorità di minRating.

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

se vuoi avere informazioni ogni volta che la partita apre il gioco:

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

Ciò, tuttavia, diventerebbe più complesso se si introducessero più campi per filtrare i giochi, ad esempio dropRate, timeZone, "giochi giocati" ecc...In questo caso, puoi nidificare gli indici più in profondità:

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

Answer 2

La scelta più ovvia come punto di partenza sarebbe il colore, poiché si tratta di un requisito esclusivo.Gli altri sembrano più risultati ponderati, quindi potrebbero semplicemente aumentare o diminuire il peso.

Utilizza le priorità per gli intervalli minimo/massimo e mantieni ciascuno in un "indice" separato.Quindi prendi le partite per ciascuno e crea un'unione.Consideriamo questa struttura:

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

Ora per interrogare, prenderei semplicemente le corrispondenze in ciascuna categoria e le classificherei in base al numero di corrispondenze.Posso iniziare con i colori, perché presumibilmente non si tratta di una valutazione facoltativa o relativa:

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

Ok, ora ho spiegato ciò che tutti chiedono in questo caso d'uso: come creare una clausola where rudimentale.Tuttavia, la risposta appropriata in questo caso è che le ricerche dovrebbero essere eseguite da un motore di ricerca.Questa non è una condizione semplice.Questa è una ricerca ponderata per le migliori corrispondenze, perché campi come il colore non sono facoltativi o semplicemente il migliore corrispondenza, mentre altri - forse in classifica - sono la corrispondenza più vicina in entrambe le direzioni, mentre alcuni influenzano semplicemente il qualità della partita.

Guardare torcia elettrica per una semplice integrazione ElasticSearch.Con questo approccio, dovresti essere in grado di sfruttare gli ottimi strumenti di ponderazione di ES, l'ordinamento dinamico e tutto ciò di cui hai bisogno per condurre un algoritmo di corrispondenza corretto.

Per quanto riguarda gli stalli.Non mi concentrerei troppo qui finché non avrai centinaia di transazioni al secondo (ad es.centinaia di migliaia di utenti in competizione per le partite).Suddividi il percorso in cui scriveremo per accettare un'unione ed eseguire una transazione per garantire che solo una persona riesca a ottenerla.Mantienilo separato dai dati letti in modo che il blocco su quel percorso non rallenti l'elaborazione.Mantieni la transazione a una dimensione minima (un singolo campo se possibile).