Base de fogo:Como combinar oponentes em um jogo?

Question

Estou implementando um jogo de xadrez social.Cada usuário pode criar um novo jogo e esperar até que o sistema encontre um oponente para ele.

Quando o usuário cria um jogo, ele especifica restrições:cor que gostariam de jogar e a classificação mínima de xadrez do oponente.

Os oponentes podem combinar ou não. Por exemplo, os dois oponentes a seguir irão combinar:

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

Então, se o Usuário 1 for o primeiro usuário no sistema e criou seu jogo, ele irá esperar.Assim que o Usuário 2 criar seu jogo, ele deverá ser combinado imediatamente com o Usuário 1.

Do outro lado, os dois adversários seguintes não irão igualar, porque ambos querem jogar com as brancas.Neste caso, ambos devem esperar até que alguém crie um jogo com color: 'black' (ou cor não especificada), e minRating que correspondesse aos requisitos.

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

Minhas preocupações estavam relacionadas a cenários em que milhares de usuários criam novos jogos ao mesmo tempo.Como posso ter certeza de que vou igualar os oponentes sem criar impasses?ou sejacomo evito cenários em que o usuário 1, o usuário 2 e o usuário 3 estão tentando encontrar um oponente ao mesmo tempo e seus algoritmos correspondentes retornam o usuário 99.Como me recupero desse cenário, atribuindo o usuário 99 a apenas um deles?

Como você usaria o poder do Firebase para implementar esse sistema de correspondência?

Answer 1

É uma tarefa desafiadora no ambiente NoSQL, especialmente se você deseja combinar vários campos

no seu caso, eu configuraria um índice simples por cor e dentro da cor armazenaria a referência ao jogo com prioridade definida para minRating.Dessa forma você pode consultar os jogos pela cor preferida com prioridade de minRating.

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

se você quiser obter informações sempre que a partida abrir o jogo:

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

Isto, no entanto, ficaria mais complexo se você introduzisse vários campos para filtrar os jogos, por exemplo dropRate, timeZone, 'jogos jogados' etc ...Nesse caso, você pode aninhar os índices mais profundamente:

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

Answer 2

A escolha óbvia como ponto de partida seria a cor, já que se trata de um requisito exclusivo.Os outros parecem mais resultados ponderados, então podem simplesmente aumentar ou diminuir o peso.

Utilize prioridades para intervalos mínimo/máximo e mantenha cada um em um "índice" separado.Em seguida, pegue os fósforos de cada um e crie uma união.Considere esta estrutura:

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

Agora, para consultar, eu simplesmente pegaria as correspondências em cada categoria e as classificaria pelo número de correspondências.Posso começar com cores, porque provavelmente não é uma classificação opcional ou 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, agora dei o que todos pedem neste caso de uso: como criar uma cláusula where rudimentar.No entanto, a resposta apropriada aqui é que as pesquisas devem ser realizadas por um mecanismo de busca.Esta não é uma condição simples de onde.Esta é uma busca ponderada pelas melhores correspondências, porque campos como cor não são opcionais ou simplesmente o melhor correspondência, enquanto outros - talvez a classificação - são os mais próximos em qualquer direção, enquanto alguns simplesmente afetam o qualidade da partida.

Confira lanterna para uma integração simples do ElasticSearch.Com essa abordagem, você poderá aproveitar as vantagens das excelentes ferramentas de ponderação, classificação dinâmica e tudo o mais necessário do ES para conduzir um algoritmo de correspondência adequado.

Em relação aos impasses.Eu não colocaria muito foco aqui até que você tenha centenas de transações por segundo (ou seja,centenas de milhares de usuários competindo por partidas).Divida o caminho onde escreveremos para aceitar uma adesão e faça uma transação para garantir que apenas uma pessoa consiga obtê-la.Mantenha-o separado dos dados lidos para que o bloqueio nesse caminho não retarde o processamento.Mantenha a transação em um tamanho mínimo (um único campo, se possível).