Conseils pour le matchmaking ?

[niahoo]

Hello, 

Je souhaite créer un petit service sur mon jeu permettant de trouver facilement un adversaire pour des parties courtes (~5min) se jouant à deux. Mais je me tate un peu sur le design.

Mon cas sera simple pour commencer : il n'y aura qu'un seul pool de joueurs. Quand un joueur souhaite commencer une partie, il clique sur un bouton et il se retrouve inscrit dans le pool. Là commence la recherche. S'il n'y a personne pour jouer avec lui (ou que ça ne correspond pas avec son niveau, il est en attente).

Pour trouver un adversaire, j'examine chaque adversaire potentiel et je prends en compte différents facteurs en leur attribuant un score. J'applique un coefficient à chaque facteur selon leur ordre d'importance.

• Le classement du joueur, type classement Elo. Si un a une trop grande différence de niveau, faut-il quand même lancer un match ?
  
• Les derniers adversaires rencontrés : on fait baisser le score si l'adversaire potentiel est dans les X derniers joueurs rencontrés.
  
• Les joueurs ont la même IP. Favoriser ou discriminer, ou pas ?
  
• Si l'adversaire attend depuis longtemps de commencer une partie, on le favorise.
  

Voyez-vous autre chose ? Mon jeu ce n'est pas du temps réel, donc je ne prends pas en compte des trucs comme le ping par exemple. Mais ça peut être intéressant de les citer aussi.

[Ter Rowan]

Le classement du joueur, type classement Elo. Si un a une trop grande différence de niveau, faut-il quand même lancer un match ?

rajoute deux options de choix pour les joueurs :  "se battre contre vraiment plus fort que soi", "se battre contre vraiment plus faible que soi" (bien sûr dans les 2 cas, "dans l'éventualité où il y a peu de monde")

rajoute en outre une option pour ta room (cf la suite); en cas de match disproportionné(a toi de définir la disproportion) selon le classement, ne pas tenir compte du match pour les statistiques (oui / non)

Les derniers adversaires rencontrés : on fait baisser le score si l'adversaire potentiel est dans les X derniers joueurs rencontrés.

pertinent

[*]

Les joueurs ont la même IP. Favoriser ou discriminer, ou pas ?

je dirais "disciminer" (score plus faible, pas éliminer) pour ta room (cf la suite)

[*]Si l'adversaire attend depuis longtemps de commencer une partie, on le favorise.

pertinent (poids)

Voyez-vous autre chose ? Mon jeu ce n'est pas du temps réel, donc je ne prends pas en compte des trucs comme le ping par exemple. Mais ça peut être intéressant de les citer aussi.

je dirais possibilité de créer une room privée (genre t as même de la monétisation derrière)
dans ce cas le propriétaire de la room peut changer les paramètres :
faire partie du pool sur invitation, sur mot de passe, pour tous le monde. Avec changement de paramètre à la clef (laisser le choix des options aux joueurs ou non, changer le poids des paramètres, etc...)
voire même changer des paramètres de jeu (si cela a un sens) genre "arênes de feu" : les pouvoirs du bois n'ont aucun effet, les pouvoirs de l'eau sont divisés par 5 les pouvoirs du feu sont multipliés par deux ...

comme cela, quelque soit ton choix, tu frustreras moins ceux qui veulent un autre choix, voire tu trouveras des modèles que tu pourras reprendre à ton compte si ils marchent mieux


plus globalement, je pense qu'en dehors des choix utilisateurs, il ne faut rien bloquer juste avoir des coeff bien maitrisés voire, au lieu de simple coeff, des fonctions (du genre gaussienne). Ex :
pour le classement "genre Elo" avoir le même niveau vaut 10, avoir un niveau de diff vaut 9, avoir trois niveaux de diff vaut 2, ...avoir plus que n niveaux de diff vaut 0.1

comme ça, au pire si les deux joueurs sont ok pour se battre contre très différents d'eux, ils pourront le faire, qui plus est sans impact sur leur niveau (ou pas)

[Thêta Tau Tau]

Le classement du joueur, type classement Elo. Si un a une trop grande différence de niveau, faut-il quand même lancer un match ?

Avec des parties longues ça serait un problème, puisque se faire rouler dessus pendant 30 minutes c'est pas vraiment agréable. Mais avec tes parties de 5 minutes le problème se pose beaucoup moins.

Sinon il faut aussi prendre en compte les chances de victoires d'un noob contre un expert. Par exemple dans un jeu de carte à collectioner, le noob peut toujours avoir de la chance et gagner, alors qu'aux échecs, une partie avec une trop grande différence de niveau n'aura que peu d'intérêt.

Les derniers adversaires rencontrés : on fait baisser le score si l'adversaire potentiel est dans les X derniers joueurs rencontrés.

Ok, j'irais même jusqu'à bloquer carrément le dernier adversaire voir les n derniers pour éviter de jouer en boucle contre les mêmes personnes.

Les joueurs ont la même IP. Favoriser ou discriminer, ou pas ?

[/quote]
Le matchmaking sert à mettre face à face des gens qui ne se connaissent pas, donc je ne le prendrait pas en compte ou je discriminerais.
Et bien sur il faut une possibilité de lancer un match avec quelqu'un sans passer par le matchmaking.

Si l'adversaire attend depuis longtemps de commencer une partie, on le favorise.

Perso ce que je ferais c'est que plus on attends, plus on accepte une différence d'ELO importante.
Par exemple s'il n'y a que 2 joueurs avec un gros écart dans la liste d'attente, on les fait patienter pour voir si des joueurs de leur nivreu arrivent, mais au bout d'un moment, on les fait quand même jouer ensemble.


Et il faut aussi prendre en compte le nombre de connectés.
Par exemple s'il y a 300 joueurs connectés on peut espérer faire des matchs bien équilibrés alors que s'il n'y a que 4 joueurs connectés c'est pas vraiment la peine de faire attendre les joueurs puisqu'il y a de toute façon peut de chance de faire des match équilibrés.

[Xenos]

Et si, pour chaque algo, le joueur pouvait choisir? Le set de paramètres peut être aléatoire, mais les sets des joueurs déjà inscrits peuvent l'influencer. Par exemple, au début, chaque set de paramètre est équiprobable. Au fil du temps, certains sets de paramètres seront préférés par les joueurs, et d'autres seront délaissés. Les sets les plus plébiscités auront alors plus de chance d'être les sets par défaut des nouveaux joueurs.

Inutile de "favoriser" manuellement les joueurs au fil du temps si c'est fait de façon probabiliste (aléatoire), cela se fera naturelle (la probabilité de ne joueur qu'au bout de S secondes est de P^S avec P la probabilité d'être choisit à chaque seconde).

Pour l'histoire de "pas deux fois le même adversaire", je ne suis pas d'accord: les deux joueurs pourraient très bien désirer un rematch. Alors, à moins que l'on ne puisse "défier" un joueur précis, interdire deux fois de suite le même adversaire me semble problématique (d'ailleurs, s'il n'y a que 2 joueurs en ligne, si le jeu leur interdit de rejouer l'un contre l'autre, ils seront bien embêtés: tu vas te retrouver à gérer des brouettes de cas particuliers comme cela).

Quand l'algo choisit un adversaire, le joueur peut-il refuser le match? Cela pourrait résoudre beau nombre de problèmes: l'adversaire choisit, le jeu affiche la feuille de stats des deux joueurs, avec un comparatif clair et visuel, et chaque joueur peut refuser le match ou l'accepter.

[niahoo]

Hello,

Merci pour vos réponses, je vais répondre à certains points :

rajoute deux options de choix pour les joueurs : "se battre contre vraiment plus fort que soi", "se battre contre vraiment plus faible que soi" (bien sûr dans les 2 cas, "dans l'éventualité où il y a peu de monde")

Bonne idée, peut-être même en opt-out.

rajoute en outre une option pour ta room (cf la suite); en cas de match disproportionné(a toi de définir la disproportion) selon le classement, ne pas tenir compte du match pour les statistiques (oui / non)

En fait le principe de Elo si j'ai bien compris c'est que justement, plus ton adversaire est faible par rapport à toi, moins tu gagnes de points. Donc il arrive un moment où le match ne te rapporte rien. (Ce que tu dis plus bas en fait)

je dirais possibilité de créer une room privée (genre t as même de la monétisation derrière)
dans ce cas le propriétaire de la room peut changer les paramètres :
faire partie du pool sur invitation, sur mot de passe, pour tous le monde. Avec changement de paramètre à la clef (laisser le choix des options aux joueurs ou non, changer le poids des paramètres, etc...)
voire même changer des paramètres de jeu (si cela a un sens) genre "arênes de feu" : les pouvoirs du bois n'ont aucun effet, les pouvoirs de l'eau sont divisés par 5 les pouvoirs du feu sont multipliés par deux ...

Pas mal l'idée de pouvoir créer des rooms avec différents paramètres. Ensuite, le fait qu'elles puissent être privées me semble pertinent pour des serveurs hébergés par des joueurs hôtes. Perso je ne compte pas mettre à disposition des serveurs à installer mais ça se fait pas mal sur d'autres jeux. Ou bien, effectivement monétiser le fait d'héberger ces rooms privées. Quel serait l'intérêt pour le payeur ?

comme ça, au pire si les deux joueurs sont ok pour se battre contre très différents d'eux, ils pourront le faire, qui plus est sans impact sur leur niveau (ou pas)

Cependant, si tu perds contre quelqu'un avec un bien meilleur classement que toi, ça ne change pas les classements des deux joueurs. Par contre si tu gagnes, là ça modifie beaucoup ! ça me semble pas une mauvaise chose.

Avec des parties longues ça serait un problème, puisque se faire rouler dessus pendant 30 minutes c'est pas vraiment agréable. Mais avec tes parties de 5 minutes le problème se pose beaucoup moins.

C'est un jeu aux points de vies, donc si tu te fais rouler dessus ça sera court ! Je fais le jeu des potions en ce moment là, c'est toi qui avait eu l'idée de base.

Sinon il faut aussi prendre en compte les chances de victoires d'un noob contre un expert. Par exemple dans un jeu de carte à collectioner, le noob peut toujours avoir de la chance et gagner, alors qu'aux échecs, une partie avec une trop grande différence de niveau n'aura que peu d'intérêt.

Malheureusement je n'ai pas encore implémenté le jeu donc je ne sais pas comment il se joue vraiment J'aimerais un ratio chance/skill assez équilibré. 40%/60% me semble sympa mais je ne sais pas encore comment ça se mesure.

Ok, j'irais même jusqu'à bloquer carrément le dernier adversaire voir les n derniers pour éviter de jouer en boucle contre les mêmes personnes.

C'est un petit jeu pour rigoler, c'est pas très grave de jouer plusieurs fois contre la même personne. Les parties ne devraient pas se ressembler donc je ne souhaite pas bloquer ça. Mais clairement faire baisser le score de correspondance. Comme le dit Xenos il faut pouvoir jouer même si peu de joueurs sont connectés. Ce qui, ne nous leurrons pas, sera le cas

Et bien sur il faut une possibilité de lancer un match avec quelqu'un sans passer par le matchmaking.

Oui bien sûr, on pourra donner un lien vers une partie privée ou proposer une partie à un autre joueur connecté.

Perso ce que je ferais c'est que plus on attends, plus on accepte une différence d'ELO importante.

Plus on attend plus le score de correspondance va augmenter donc de fait, le classement sera moins pris en compte (relativement).

Pour le reste on rentre dans l'algorithmique. ça va pas être de la tarte de gérer les timers

Et si, pour chaque algo, le joueur pouvait choisir? Le set de paramètres peut être aléatoire, mais les sets des joueurs déjà inscrits peuvent l'influencer.

Pas trop sûr de comprendre, mais je préfère choisir mes coefficients et faire des tests. Le but est de minimiser l'attente en favorisant des parties assez équilibrées. On peut donc avoir les bon coefficients par calcul.

Inutile de "favoriser" manuellement les joueurs au fil du temps si c'est fait de façon probabiliste (aléatoire), cela se fera naturelle (la probabilité de ne joueur qu'au bout de S secondes est de P^S avec P la probabilité d'être choisit à chaque seconde).

Bien vu ! Il faudra voir comment l'implémentation gère ça, s'il y a besoin ou non de renforcer cette probabilité ; ta formule est valable dans le cas où les joueurs sont choisis au hasard, or justement je mets en place des critères.

On pourrait cependant imaginer une seconde room ou il est clairement établi que les adversaires sont sélectionnés totalement au hasard.

Pour le rematch, j'avais l'idée, çà sort un peu du cadre du matchmaking mais je compte mettre un tel bouton "revanche" à la fin d'une partie, les deux joueurs ayant 20 sec. pour cliquer dessus et si les deux le font, la partie recommence.

Quand l'algo choisit un adversaire, le joueur peut-il refuser le match? Cela pourrait résoudre beau nombre de problèmes: l'adversaire choisit, le jeu affiche la feuille de stats des deux joueurs, avec un comparatif clair et visuel, et chaque joueur peut refuser le match ou l'accepter.

Je n'y ai pas du tout pensé. À première vue ça ne me plaît pas. Si le matchmaking fonctionne bien (pas gagné mais admettons) alors cela signifie que si on lui met un joueur ne correspondant pas vraiment à son niveau ou qu'il a déjà combattu très récemment, c'est qu'on n'a pas mieux à lui proposer. De plus, il n'y aura pas vraiment de fiche de persos dans ce jeu plutôt simpliste.

Ceci étant dit, le matchmaking est là pour trouver un adversaire sans réfléchir. Il faut pour cela s'inscrire dans la room (unique pour le moment). Si on ne s'inscrit pas, on ne risque rien. On peut donc consulter le classement tranquilou, et éventuellement regarder les fiches des adversaires potentiels (si fiche il y a, ça vaut pour n'importe quel jeu ce système), et enfin proposer un match à une certaine personne directement. Dans ce cas là, il faut clairement que l'adversaire puisse refuser le match.

Bon, ça donne matière à réfléchir tout ça. En parallèle, je suis en train de plancher sur l'IA afin de pouvoir proposer des challenges spécifiques.

[Xenos]

D'un autre coté, l'option de refuser le match te permet de te passer totalement d'un algo de sélection en dur:
• Chaque joueur a des paramètres, qui constituent un vecteur V[n] (dimension n car n paramètres)
• Le match maker choisit deux adversaires de vecteurs V1 et V2, totalement au hasard.
• Si les adversaires acceptent le match, c'est que la paire V1-V2 est une paire que les joueurs apprécient. S'ils refusent le match, c'est que cette paire n'est pas appréciée des joueurs. On peut même affiner en différenciant les cas où V1&V2 acceptent, V1&V2 refusent, V1 refuse V2 accepte et V1 accepte V2 refuse.
• L'algo intègre cette information dans un base de données, et il apprend ainsi à fournir une meilleure paire la prochaine fois.

De fil en aiguille, à force de matchs, tu auras forcément la solution optimale que tes joueurs apprécieront: peu importe qu'en pratiquent, ils aiment les matchs déséquilibrés ou qu'ils les détestent, l'algo adaptatif trouvera la solution qui leur plaira le plus, sans trop de code (mais avec beaucoup de données).

Il y a surement des articles sur le net décrivant les algorithmes apprenants dans ce genre de cas (choisir deux éléments correspondant chacun à un vecteur V[n] à partir de paires V1-V2 valides et de paires V1-V2 invalides). De tête, sans recherche, on pourrait faire ainsi:
• Stocker toutes les paires V1V2 avec l'indication "duel accepté=1/refusé=0"
• Si deux paires se superposent (ou, à défaut, sont très proches), on n'en stocke qu'une et l'indication "accepté/refusé" devient la moyenne pondérée de ces deux paires (donc, si j'ai déjà une paire V1/V2/1 et que j'insère une paire V3/V4/0 avec V1=V3 et V2=V4, alors je modifie la paire V1/V2/0 existante pour V1/V2/0.5 et si une autre paire V3/V4/1 survient, je modifierai V1/V2/0.5 en V1/V2/0.75 ou en V1/V2/0.666)
• Piocher une paire V3V4 au hasard
• Chercher la paire V1/V2/x existante la plus proche (avec distance(V1-V3)=d1 et distance(V2-V4)=d2)
• Proposer ce duel si et seulement si rand(0..1) <= x

[Ter Rowan]

rajoute en outre une option pour ta room (cf la suite); en cas de match disproportionné(a toi de définir la disproportion) selon le classement, ne pas tenir compte du match pour les statistiques (oui / non)

En fait le principe de Elo si j'ai bien compris c'est que justement, plus ton adversaire est faible par rapport à toi, moins tu gagnes de points. Donc il arrive un moment où le match ne te rapporte rien. (Ce que tu dis plus bas en fait)

comme ça, au pire si les deux joueurs sont ok pour se battre contre très différents d'eux, ils pourront le faire, qui plus est sans impact sur leur niveau (ou pas)

Cependant, si tu perds contre quelqu'un avec un bien meilleur classement que toi, ça ne change pas les classements des deux joueurs. Par contre si tu gagnes, là ça modifie beaucoup ! ça me semble pas une mauvaise chose.

je précise :
l'intérêt pour un joueur faible de choisir l'option jouer avec joueur très fort est de pouvoir jouer fréquemment, et fonction du choix de NON "ne pas tenir compte du match pour les statistiques" alors d'éventuellement gagner bcp de points dans le classement
l'inconvénient , c'est qu'il va probablement se faire retourner

l'intérêt pour un joueur fort de choisir l'option jouer avec un joueur très faible est de pouvoir jouer fréquemment
l'inconvénient, c'est que s'il perd et qu'il est dans l'option de NON "ne pas tenir compte du match pour les statistiques" alors d'éventuellement perdre bcp de points.

pour le joueur faible, c'est plutôt bénef mais pour le joueur fort, entre attendre 5 minutes de plus et risquer de perdre tellement de points qu'il faudra faire 10 parties (donc x minutes) pour revenir au niveau, combien préféreront juste attendre. C'est pourquoi je pense qu'il faut proposer l'option "pour du beurre dans le cas d'un match disproportionné"

Ou bien, effectivement monétiser le fait d'héberger ces rooms privées. Quel serait l'intérêt pour le payeur ?

d'avoir la plus grosse, de craner devant les copains "viendez dans ma room, c'est la mienne, en plus j'ai mis mes paramètres qui roxent de la mort qui tue"
la monétisation sur un petit jeu, est juste une question d ego

[niahoo]

Ok pour la monétisation.

Pour les classements on peut donc faire simplement des matches non-cotés, ou notre classement n'est pas modifié, et des matchs cotés ou il n'y a pas d'options, en gardant à l'esprit qu'on ne perd pas de points à perdre contre beaucoup plus fort que soi, et que perdre contre beaucoup plus faible reste très rare. Surtout que le classement n'apporte pas d'avantages en jeu. Deux rooms quoi.

Je pensais aussi à implémenter des genres de succès dans la partie solo. En gros, faire une progression grossièrement scénarisée à difficulté croissante (un genre de mini mode aventure quoi) dont certains matchs font office de jalons. Quand on gagne un tel match, on passe en league supérieure. Mais ça voudrait dire que si les rooms sont par league alors on perd la possibilité de faire se rencontrer des joueurs de league différente quand il n'y a personne. Du coup, avec cette histoire de matches non côtés, on pourrait avoir la room non-cotée ou on tient compte du classement pour le matchmaking mais où tout le monde peut se rencontrer ; et des rooms cotées par league. MAIS du coup si on est tout seul dans sa room de league il faut avoir l'option de redescendre et ça redevient relou comme système.

Xenos j'ai l'impression que ça va vraiment prendre beaucoup de données, donc ça tient pas en RAM et ça sera lent. Surtout c'est assez galère à coder pour le temps que j'ai, et il faudra en plus que je fasse des scripts de nettoyage car je veux accepter les joueurs non-inscrits (temporaires). Par contre l'idée des vecteurs me paraît sympa parce que justement je me disais qu'avoir le score sur une seule dimension était problématique. Donc le calcul de distances c'est cool.

Bon après je souhaite que ça reste simple.

[Xenos]

Si tu as des contraintes de perfs, tu peux ne stocker que l'optimium |(Va-Vb)| (valeur absolue de chaque coordonnée de la différence de deux vecteurs).
• Tu pioches deux joueurs au pif
• Tu calcules |(V1-V2)|
• Tu calcules la distance à l'optimum D=d(|(V1-V2)|, |(Va-Vb)|)
• Tu pioches un nombre aléatoire R=rand(0..D)
• Si R<N fixé, t'as trouvé ta paire, sinon, tu augmentes N (incrémenté de k>0, ou multiplié par k>1) et tu recommences
• Si le match est accepté par les deux joueurs, tu altères |(Va-Vb)| avec |(V1-V2)|, par exemple sous la forme |(Va-Vb)'| = |(Va-Vb)|*p+|(V1-V2)|*(1-p) (pour p ∈ [0..1])

L'intérêt d'augmenter N est d'assurer qu'il existera rapidement une itération où N>D, et donc, R=rand(0..D) sera forcément inférieur à N: la paire de joueur a été trouvée.
Le calcul peut encore s'accélérer en utilisant le carré de la distance plutôt que la distance D. Cela tendra à "tasser" les paires choisies vers la différence optimale |(Va-Vb)|, pour les premières itérations.
A défaut, suivant le code derrière, il est peut-être plus efficace d'aller chercher les {V1,V2} qui sont les plus proches de |(Va-Vb)| et les proposer dans l'ordre (supposons que l'algo soit pour un joueur J1 fixé, on peut prendre tous les joueurs J2 de la room, calculer |(V1-V2)| pour tous ces joueurs, calculer D, classer les J2 par ordre de D décroissant, proposer chaque duel dans l'ordre et altérer l'optimum en conséquence).

Ca me semble rapidement calculable, simple à coder (tu peux même sauver le vecteur optimal en dur et ne pas l'altérer, au moins pour une v0), léger en mémoire, plutôt efficace pour trouver des paires de joueurs, maintenable, évolutif (important! Si tu veux ajouter de nouveaux paramètres à considérer pour le choix de la paire de joueurs, il suffit de l'ajouter aux vecteurs) et paramétrable (si un joueur veut que l'algo ignore un des paramètres, il suffira de le sortir des vecteurs).