[Résolu] Algorithme de match making - Composer des équipes sans joueurs en commun

[Sephi-Chan]

Coucou,

Ces derniers temps j'ai découvert un bug sur mon algorithme de match making (en réalité, une implémentation très naïve qui convenait pour mes essais mais inutilisable en vrai).

Le jeu se joue en parties d'un format donné (par exemple 3 équipes de 4 joueurs, noté 3x4). A tout instant, un joueur peut inviter d'autres joueurs à jouer avec lui à une partie d'un format donné (par exemple : moi A, j'invite B, C et D pour une partie en 3x4). Une fois que tous les joueurs invités ont répondu favorable à la recherche, elle est enregistrée dans le système.

Le but est ensuite de créer des parties qui regroupent les différentes recherches. Ici, le système tentera de créer autant de parties possible pour le format 3x4. Bien sûr, s'il n'y a qu'une seule recherche pour ce format, ça ne suffit pas. L'autre point important : il ne faut pas que les parties aient de joueurs en commun.

Je cherche donc à établir un bon algorithme pour faire ça et je viens vers vous pour vos suggestions.


Voici la structure de données de base que je propose :

{

  // On associe un format à toutes les recherches pour celui-ci.

  "2x3" : [ { name: "A", players: [ 1, 2, 3 ] }, { name: "B", players: [ 3, 4, 5 ] }, { name: "C", players: [ 4, 5, 6 ] } ],

  "3x4" : [ { name: "D", players: [ 1, 2, 3, 4 ] } ]

}

Et en sortie, je souhaiterai (mais je suis ouvert à d'autres propositions) avoir une structure de données telle que :

{

  // L'équipe B n'a pas été gardée car elle contenait un joueur en commun avec

  // l'équipe A (qui est prioritaire car inscrite la première).

  // Il y a un tableau pour chaque partie que le système peut créer pour le

  // format 2x3 avec les équipes qu'on lui a donné (ici 1 seule partie peut

  // être formée, avec les équipes A et C).

  "2x3" : [ [ { name: "A", players: [ 1, 2, 3 ] }, { name: "C", players: [ 4, 5, 5 ] } ] ],



  // Ici. Hélas il n'y a pas assez d'équipes pour former la moindre partie.

  // Il aurait fallu au moins 3 équipes sans joueurs en commun.

  "3x4" : [ { name: "D", players: [ 1, 2, 3, 4 ] } ]

}

Voilà ! A vos suggestions !

[Ter Rowan]

je vais raisonner que sur un type de match (3x4 OU 2x3) car je ne sais pas si un joueur peut être dans des parties de type différent ou pas, mais le principe reste le même

j ai besoin de plusieurs variables :

en entrée un tableau d'équipes de joueurs (comme tu le fais), un joueur pouvant être dans plusieurs équipes : var source = [{....},{},...]

en intermédiaire un tableau de joueurs, initialement vide
var players = []

en intermédiaire un tableau d'équipes pour un match, initialement vide
var match= []


en final un tableau de matchs, un joueur ne pouvant être que dans un match
var target= [{....},{},...]

1) je mélange aléatoirement (ou autrement) ma source

2) je parcours la source. Pour chaque team de la source

2.1) je parcours les joueurs de la team. Si au moins un joueur de la source est dans le tableau player, je passe à la team suivante (retour au 2)

2.2) aucun des joueurs n'étant déjà inscrits, je les inscris : players[id player] = true / id équipe, ce que tu veux (deuxieme boucle sur les joueurs de la team)

2.3) j ajoute la team dans le tableau match

2.4) si le tableau match contient le nombre d'équipes voulu, j ajoute le tableau match dans target (en copie) puis je vide le tableau match

voilà j ai fini

qu'un joueur puisse jouer ou pas dans des matchs de type différents revient au meme, tout dépend de la gestion du tableau intermédiaire players

[Sephi-Chan]

Impeccable ! Je trouve cet algorithme bien plus propre que celui que j'avais produit (récursif). Je prends !

Pour info, voici le code de mon dispatcheur et de sa suite de tests unitaires. L'algorithme décrit est implémenté dans dispatchable_groups_for_format.

# Dispatch ready game searches into games whenever it is possible.

class Dispatcher

  attr_reader :communication_client





  def initialize(game_searches, communication_client)

    @game_searches        = game_searches

    @communication_client = communication_client

  end





  def dispatch!

    Game.transaction do

      dispatchable_game_searches_by_format.inject([]) do |games, (format, group_of_game_searches)|

        group_of_game_searches.each do |game_searches|

          game = Game.create!(format: format, status: Game::CREATED)

          game_searches.each do |game_search|

            team = game.teams.create!(game_search: game_search, status: Team::ALIVE, players: game_search.players)

            game_search.update!(status: GameSearch:ISPATCHED, game: game)

            team.players.each do |player|

              communication_client.push(player, {

                event:          Queues::MatchMaker::GAME_SEARCH_SUCCEEDED,

                players:        team.players.map { |player| { id: player.id, name: player.name } },

                game_search_id: team.game_search_id,

                status:         GameSearch::SUCCEEDED,

                game_id:        game.id

              })

            end

          end



          games << game

        end



        games

      end

    end

  end





  private



  def game_searches_by_format

    @game_searches.group_by(&:format)

  end





  def dispatchable_game_searches_by_format

    game_searches_by_format.inject({}) do |hash, (format, game_searches)|

      groups         = dispatchable_groups_for_format(format, game_searches)

      hash[format] ||= groups if groups.any?

      hash

    end

  end





  # For a given format, returns a list of game searches for each dispatchable game.

  # Example: [ [ GameSearch A, GameSearch B ], [ GameSearch C, GameSearch D ] ]

  def dispatchable_groups_for_format(format, game_searches)

    dispatched_player_ids  = []

    selected_game_searches = []

    groups                 = []



    game_searches.each do |game_search|

      if (game_search.player_ids & dispatched_player_ids).empty?

        dispatched_player_ids.push(*game_search.player_ids)

        selected_game_searches << game_search

        if format.teams_count == selected_game_searches.size

          groups << selected_game_searches

          selected_game_searches = []

        end

      end

    end



    groups

  end

end

Et la suite de tests, avec la participation bénévole des personnages du Cycle des Princes d'Ambre.

require 'spec_helper'



describe Dispatcher do

  let(:communication_client) { stub }

  let(:format_2_3)           { FactoryGirl.build(:format, teams_count: 2, teams_size: 3) }



  let(:corwin)               { FactoryGirl.create(:player, name: 'Corwin') }

  let(:mandor)               { FactoryGirl.create(:player, name: 'Mandor') }

  let(:caine)                { FactoryGirl.create(:player, name: 'Caine') }

  let(:corwin_invitation)    { FactoryGirl.build(:invitation, :accepted, player: corwin) }

  let(:mandor_invitation)    { FactoryGirl.build(:invitation, :accepted, player: mandor) }

  let(:caine_invitation)     { FactoryGirl.build(:invitation, :accepted, player: caine) }

  let(:first_game_search)    { FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3) }



  let(:brand)                { FactoryGirl.create(:player, name: 'Brand') }

  let(:bleys)                { FactoryGirl.create(:player, name: 'Bleys') }

  let(:julian)               { FactoryGirl.create(:player, name: 'Julian') }

  let(:brand_invitation)     { FactoryGirl.build(:invitation, :accepted, player: brand) }

  let(:bleys_invitation)     { FactoryGirl.build(:invitation, :accepted, player: bleys) }

  let(:julian_invitation)    { FactoryGirl.build(:invitation, :accepted, player: julian) }

  let(econd_game_search)   { FactoryGirl.create(:game_search, :ready, invitations: [ brand_invitation, bleys_invitation, julian_invitation ], format: format_2_3) }



  let(:fiona)                { FactoryGirl.create(:player, name: 'Fiona') }

  let(:deirdre)              { FactoryGirl.create(:player, name: 'Deirdre') }

  let(:flora)                { FactoryGirl.create(:player, name: 'Flora') }

  let(:fiona_invitation)     { FactoryGirl.build(:invitation, :accepted, player: fiona) }

  let(:deirdre_invitation)   { FactoryGirl.build(:invitation, :accepted, player: deirdre) }

  let(:flora_invitation)     { FactoryGirl.build(:invitation, :accepted, player: flora) }

  let(:third_game_search)    { FactoryGirl.create(:game_search, :ready, invitations: [ fiona_invitation, deirdre_invitation, flora_invitation ], format: format_2_3) }



  let(:random)               { FactoryGirl.create(:player, name: 'Random') }

  let(:gerard)               { FactoryGirl.create(:player, name: 'Gerard') }

  let(:dworkin)              { FactoryGirl.create(:player, name: 'Dworkin') }

  let(:random_invitation)    { FactoryGirl.build(:invitation, :accepted, player: random) }

  let(:gerard_invitation)    { FactoryGirl.build(:invitation, :accepted, player: gerard) }

  let(:dworkin_invitation)   { FactoryGirl.build(:invitation, :accepted, player: dworkin) }

  let(:fourth_game_search)   { FactoryGirl.create(:game_search, :ready, invitations: [ random_invitation, gerard_invitation, dworkin_invitation ], format: format_2_3) }





  it 'composes no game when there is only 1 ready team' do

    games = Dispatcher.new([ first_game_search ], communication_client).dispatch!

    games.should be_empty

  end





  it 'composes 1 game when 2 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    game_searches  = [ first_game_search, second_game_search ]

    games          = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]

  end





  it 'compose 2 games when 4 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    expected_hash_3 = hash_including(common_keys.merge(game_search_id: third_game_search.id, players: [ { id: fiona.id, name: fiona.name }, { id: deirdre.id, name: deirdre.name }, { id: flora.id, name: flora.name } ]))

    communication_client.should_receive(:push).with(fiona,   expected_hash_3)

    communication_client.should_receive(:push).with(deirdre, expected_hash_3)

    communication_client.should_receive(:push).with(flora,   expected_hash_3)



    expected_hash_4 = hash_including(common_keys.merge(game_search_id: fourth_game_search.id, players: [ { id: random.id, name: random.name }, { id: gerard.id, name: gerard.name }, { id: dworkin.id, name: dworkin.name } ]))

    communication_client.should_receive(:push).with(random,  expected_hash_4)

    communication_client.should_receive(:push).with(gerard,  expected_hash_4)

    communication_client.should_receive(:push).with(dworkin, expected_hash_4)



    game_searches  = [ first_game_search, second_game_search, third_game_search, fourth_game_search ]

    games          = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]



    games[1].teams[0].players.should == [ fiona, deirdre, flora ]

    games[1].teams[1].players.should == [ random, gerard, dworkin ]

  end





  it 'compose 1 games when 3 teams are ready for the same 2-teams format' do

    common_keys     = { event: Queues::MatchMaker::GAME_SEARCH_SUCCEEDED, status: GameSearch::SUCCEEDED, game_id: anything }

    expected_hash_1 = hash_including(common_keys.merge(game_search_id: first_game_search.id, players: [ { id: corwin.id, name: corwin.name }, { id: mandor.id, name: mandor.name }, { id: caine.id, name: caine.name } ]))

    communication_client.should_receive(:push).with(corwin, expected_hash_1)

    communication_client.should_receive(:push).with(mandor, expected_hash_1)

    communication_client.should_receive(:push).with(caine,  expected_hash_1)



    expected_hash_2 = hash_including(common_keys.merge(game_search_id: second_game_search.id, players: [ { id: brand.id, name: brand.name }, { id: bleys.id, name: bleys.name }, { id: julian.id, name: julian.name } ]))

    communication_client.should_receive(:push).with(brand,  expected_hash_2)

    communication_client.should_receive(:push).with(bleys,  expected_hash_2)

    communication_client.should_receive(:push).with(julian, expected_hash_2)



    game_searches = [ first_game_search, second_game_search, third_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ brand, bleys, julian ]

    games[0].game_searches.should == [ first_game_search, second_game_search]

  end





  it 'composes no game since the 2 teams has players in common' do

    corwin_invitation       = FactoryGirl.build(:invitation, :accepted, player: corwin)

    mandor_invitation       = FactoryGirl.build(:invitation, :accepted, player: mandor)

    caine_invitation        = FactoryGirl.build(:invitation, :accepted, player: caine)

    first_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3)



    corwin_other_invitation = FactoryGirl.build(:invitation, :accepted, player: corwin)

    bleys_invitation        = FactoryGirl.build(:invitation, :accepted, player: bleys)

    julian_invitation       = FactoryGirl.build(:invitation, :accepted, player: julian)

    second_game_search      = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_other_invitation, bleys_invitation, julian_invitation ], format: format_2_3)



    game_searches = [ first_game_search, second_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games.should be_empty

  end





  it 'composes one game with searches 1 and 3 since team 2 has players in common with 1' do

    communication_client.should_receive(:push).exactly(6).times



    corwin_invitation       = FactoryGirl.build(:invitation, :accepted, player: corwin)

    mandor_invitation       = FactoryGirl.build(:invitation, :accepted, player: mandor)

    caine_invitation        = FactoryGirl.build(:invitation, :accepted, player: caine)

    first_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_invitation, mandor_invitation, caine_invitation ], format: format_2_3)



    corwin_other_invitation = FactoryGirl.build(:invitation, :accepted, player: corwin)

    bleys_invitation        = FactoryGirl.build(:invitation, :accepted, player: bleys)

    julian_invitation       = FactoryGirl.build(:invitation, :accepted, player: julian)

    second_game_search      = FactoryGirl.create(:game_search, :ready, invitations: [ corwin_other_invitation, bleys_invitation, julian_invitation ], format: format_2_3)



    fiona_invitation        = FactoryGirl.build(:invitation, :accepted, player: fiona)

    deirdre_invitation      = FactoryGirl.build(:invitation, :accepted, player: deirdre)

    flora_invitation        = FactoryGirl.build(:invitation, :accepted, player: flora)

    third_game_search       = FactoryGirl.create(:game_search, :ready, invitations: [ fiona_invitation, deirdre_invitation, flora_invitation ], format: format_2_3)



    game_searches = [ first_game_search, second_game_search, third_game_search ]

    games         = Dispatcher.new(game_searches, communication_client).dispatch!



    games[0].teams[0].players.should == [ corwin, mandor, caine ]

    games[0].teams[1].players.should == [ fiona, deirdre, flora ]

  end

end

Merci Ter Rowan !

[Ter Rowan]

Merci Ter Rowan !

mais de rien

PS c 'est fou, j'arrive même pas à comprendre ton code alors que c'est mon algo
PPS Julian prend deux places avec son cheval et ses chiens, de mémoire... ton cas test est pourri :p

[Sephi-Chan]

Merci Ter Rowan !

mais de rien

PS c 'est fou, j'arrive même pas à comprendre ton code alors que c'est mon algo

C'est peut-être plus clair ainsi, en expliquant les petits spécificités de Ruby :

def dispatchable_groups_for_format(format, game_searches)

  # J'initialise mes tableaux vides.

  dispatched_player_ids  = []

  selected_game_searches = []

  groups                 = []



  # Je parcours les équipes (dans ma terminologie, les recherches de partie).

  game_searches.each do |game_search|

    # Je vérifie si la recherche a des joueurs en commun avec ma liste de joueurs. J'utilise pour cela l'opérateur d'intersection.

    # Si l'intersection est vide, c'est qu'on n'a aucun joueur en commun et on descend donc dans l'algorithme, sinon on passe à l'itération suivante.

    if (game_search.player_ids & dispatched_player_ids).empty?

      # J'inscrit mes joueurs. J'utilise pour ça push. Le * sert à envoyer chaque élément du tableau plutôt que le tableau lui-même.

      dispatched_player_ids.push(*game_search.player_ids)

      # J'ajoute la recherche à la liste des recherches. << est un peu comme push.

      selected_game_searches << game_search

      if format.teams_count == selected_game_searches.size

        groups << selected_game_searches

        selected_game_searches = []

      end

    end

  end



  groups

end

PPS Julian prend deux places avec son cheval et ses chiens, de mémoire... ton cas test est pourri :p

Les animaux ne sont pas admis dans l'établissement ! :non: