Niveau 9 – Mécaniques intransitives

L’article original « Level 9: Intransitive Mechanics » a été écrit par Ian Schreiber et fait partie d’un cours de game design en ligne, publié sur le blog Game Balance Concepts.

L’article original et cette traduction sont publiés sous licence Creative Commons (Attribution).

N’hésitez pas à visiter le blog de Ian Schreiber et suivre son compte Twitter.

~ ~ ~ ~ ~ ~ ~

Lectures / Jeux

Voir « ressources supplémentaires » à la fin de cet article pour d’autres lectures.

Cette semaine

Bien le bonjour ! Aujourd’hui nous allons apprendre comment équilibrer les mécaniques intransitives. Pour rappel, « intransitif » est juste une façon un peu geek de dire « des jeux comme Pierre-Ciseau-Papier » – c’est-à-dire des jeux où il n’existe pas de stratégie dominante, parce que tout peut être battu par quelque chose d’autre.

Nous voyons des mécaniques intransitives tout le temps dans les jeux. Dans les jeux de combat, un motif typique est que les attaques normales sont battues par des blocages, les blocages sont battus par des projections (« choppes ») et les projections sont battues par les attaques. Dans les jeux de stratégie en temps-réel, un motif typique est que vous avez des volants qui peuvent détruire l’infanterie, l’infanterie qui fonctionne bien contre les archers, et les archers qui sont doués pour faire tomber les volants. Les jeux de stratégie au tour par tour ont souvent certaines unités qui fonctionnent bien contre d’autres, un motif d’exemple étant que les tanks lourds perdent face à l’infanterie anti-tanks, qui perd contre l’infanterie normale, qui perd contre les tanks lourds. Les jeux de tir à la première personne ont parfois une relation intransitive entre les différentes armes ou véhicules, comme les lance-roquettes qui sont bons contre les tanks (parce qu’ils sont lents et facile à toucher), qui sont eux-même bons contre les véhicules légers (qui sont détruits par la cadence de tir du tank une fois qu’ils sont à portée), qui eux-même sont bons contre les lance-roquettes (parce qu’ils peuvent les éviter et passer entre les missiles qui arrivent lentement). Les MMO et les JdR ont souvent des classes de personnage qui sont particulièrement bons pour se battre contre d’autres classes aussi. Ainsi vous voyez que les mécaniques intransitives se glissent un peu partout.

Certaines de ces relations pourraient ne pas être immédiatement évidentes. Par exemple, prenez en considération un jeu où un type d’unité a une attaque à longue portée, qui est battue par un attaquant à courte portée qui peut devenir invisible ; qui est à son tour battu par un attaquant à moyenne portée avec un radar qui révèle les unités invisibles ; et l’attaquant à moyenne portée est bien évidemment faible face à l’attaquant à longue portée.

Parfois c’est purement mathématique ; dans Magic l’Assemblée, une créature 1/3 perdra en combat contre une créature 3/2, qui perd face à une créature 2/1 initiative, qui en retour perd face à la créature originale. À l’intérieur du métagame d’un JCC vous avez souvent trois ou quatre paquets dominants, chacun étant conçu pour battre un ou plusieurs autres. Ce genre de choses n’étant pas nécessairement conçu avec l’intention d’être intransitif, mais c’est ce qui finit par arriver.

Solutions des mécaniques intransitives

Aujourd’hui nous allons nous salir un peu les mains avec les plus mathématiques des maths que nous avons déjà réalisées jusqu’à présent, en empruntant au besoin des outils d’algèbre, d’algèbre linéaire, et de la théorie des jeux. Durant le processus nous apprendrons comment résoudre les mécaniques intransitives, de manière à pouvoir en apprendre plus sur la façon dont elle fonctionnent dans notre jeu que ce que nous pouvons attendre comme comportement du joueur à un niveau expert.

À quoi une ressemble une « solution » ici ? Ce ne peut-être une courbe de coût, parce que chaque choix bat certaines fois et perd d’autres fois. À la place, c’est un ratio entre la fréquence à laquelle vous choisissez parmi toutes les options disponibles, et à quelle fréquence vous pouvez vous attendre à ce que votre adversaire choisisse parmi ses options. Par exemple, rassembler une armée avec 30% d’archers, 50% d’infanterie et 20% de volants (ou 3:5:2) pourrait être une solution à un jeu intransitif qui comporte ces unités, sous certaines conditions.

En tant que concepteur de jeu, vous pourriez vouloir que certains objets du jeu soit utilisés plus ou moins fréquemment que d’autres, et en changeant les coûts relatifs et la disponibilité de chaque objet vous pouvez changer le mix optimal d’objets que les joueurs utiliseront en jeu. En concevant votre jeu spécialement pour avoir une ou plusieurs stratégies optimales parmi lesquelles choisir, vous saurez à l’avance comment le jeu pourrait se développer. Par exemple, vous pourriez vouloir que certaines choses n’arrivent que rarement pendant la partie mais être spectaculaires quand c’est le cas, et si vous comprenez comment vos coûts affectent les fréquences relatives, vous pouvez concevoir un jeu pour être volontairement comme ça. (Ou, si cela paraît être le cas pendant le playtest, que vos joueurs utilisent une chose plus souvent qu’une autre, ce type d’analyse pourrait être capable de faire la lumière sur pourquoi c’est le cas).

Ça intéresse qui ?

La question mériterait d’être posée, si toutes les mécaniques intransitives sont simplement des versions glorifiées de Pierre-Ciseau-Papier, quel est l’intérêt ? Peu de gens jouent à Pierre-Ciseau-Papier pour s’amuser, alors pourquoi devraient-ils s’amuser avec un jeu qui utilise la même mécanique mais habillée différemment ?

D’autre part, un jeu intransitif est au moins aussi intéressant qu’un jeu avec une seule stratégie dominante (« Pierre-Pierre-Pierre ») parce que vous verrez plus de variété en jeu. D’autre part, une mécanique intransitive incluse dans un jeu plus large peut permettre aux joueurs de changer ou modifier leurs stratégies en milieu de partie. Les joueurs pourraient faire certains choix à la lumière de ce qu’ils voient que font les autres joueurs maintenant (en temps-réel), en particulier dans les jeux basés sur l’action où vous devez réagir à la réaction de votre adversaire à votre réaction à son action en l’espace de quelques millisecondes.

Dans les jeux avec des mécaniques de bluff, les joueurs pourraient faire des choix sur la base de ce qu’ils ont vu que les autres joueurs faisaient dans le passé et essayent de s’en servir pour inférer leur coup à venir, ce qui est particulièrement intéressant dans les jeux avec une information partielle mais incomplète (comme le Poker). Ainsi, par chance, vous pouvez voir que parce qu’un jeu possède une mécanique intransitive, cela ne signifie pas que c’est aussi terne que Pierre-Ciseau-Papier.

En plus, les mécaniques intransitives servent comme une forme de « frein d’urgence » sur les stratégies dominantes qui s’envolent. Même si vous ne connaissez pas exactement quelle est la meilleure stratégie de votre jeu, si toutes les stratégies ont une relation intransitive, vous pouvez au moins savoir qu’il n’y a pas une seule stratégie dominante qui invalide toute les autres, parce qu’elle sera faible face à au moins une contre-stratégie. Même si le jeu lui-même est déséquilibré, les mécaniques intransitives permettent de corriger le métagame – même si ce n’est pas l’idéal de se reposer uniquement dessus (un tel choix serait une conception paresseuse), mais il est préférable d’avoir un filet de sécurité que pas si vous publiez un jeu où les changements majeurs d’équilibrage ne peuvent pas être faits facilement après coup.

Ainsi, si j’ai réussi à vous convaincre que les mécaniques intransitives valent le coût d’être incluses dans au moins certains types de jeu, préparez-vous à apprendre comment les résoudre !

Résoudre le jeu Pierre-Ciseau-Papier de base

Commençons par résoudre le jeu de base Pierre-Ciseau-Papier pour voir comment cela fonctionne. Comme chaque jet est théoriquement aussi bon qu’un autre, nous pourrions nous attendre à ce que le ratio soit 1:1:1, ce qui signifie que vous choisissez chaque jet aussi souvent les uns que les autres. Et c’est ce que nous trouverons, mais il est important de comprendre comment en arriver là de manière à pouvoir résoudre les problèmes plus complexes.

Tout d’abord, regardons les résultats. Appelons les jets de notre adversaire « r », « p » et « s » et nos jets « R », « P » et « S » (nous avons les majuscules parce que nous sommes géniaux). [ NdT : afin d’éviter les ambiguïtés, je conserve les lettres r, p et s ] Comme gagner et perdre sont égaux et opposés (c’est-à-dire, une victoire + une défaite s’équilibrent) et les égalités sont pile au milieu, donnons la valeur +1 à une victoire, -1 à une défaite, et 0 à une égalité. Le calcul ici devrait fonctionner pour n’importe quelle valeurs de points, mais ces chiffres rendent tout plus facile. Nous pouvons maintenant construire une table de résultats :


rps
R0-11
P10-1
S-110

Bien entendu, tout cela est de notre point de vue – par exemple, si nous jouons (R)ock et notre adversaire joue (s)cissors, nous gagnons, pour un gain net de +1 à notre score.La table de notre adversaire serait simplement l’inverse.

Recadrons cela un petit peu, en appelant r, p et s les probabilités que l’adversaire choisisse ou non chaque coup respectif. Par exemple, supposons que vous savez à l’avance que votre adversaire utilise une stratégie de r = 0,5, p = s = 0,25 (c’est-à-dire qu’ils jouent 2 Rock pour chaque Paper ou Scissors). Quelle est la meilleure contre-stratégie ?

Pour répondre à cette question, nous pouvons construire une série de trois équations qui vous donnent vos gains pour chaque coup [ NdT : à partir de la matrice ci-dessus ; multiplier les points par la probabilité ] :

  • Gain for R = 0r + (-1)p + 1s = s-p
  • Gain for P = 1r + 0p + (-1)s = r-s
  • Gain for S = (-1)r + 1p + 0s = p-r

Ainsi sur la base des probabilités, vous pouvez calculer les gains. Dans le cas de notre adversaire porté sur la pierre, les gains sont R = 0, P=0,25 et S=-0,25. Comme P a les meilleurs bénéfices des trois jets, en partant du principe que l’adversaire ne change pas sa stratégie du tout, alors notre meilleure contre-stratégie est de jouer Papier tout le temps, et nous pouvons nous attendre à ce que cela nous rapporte 0,25 par coup – c’est-à-dire, que tous les quatre coups, nous gagnerons une partie de plus que nous en perdons. En fait, nous trouverons que si notre adversaire joue pierre même un tout petit peu plus souvent que les autres, le gain net pour P sera meilleur que les autres, et que note meilleure stratégie est toujours de jouer Paper 100% du temps, jusqu’à ce que notre adversaire modifie sa stratégie. C’est significatif ; cela nous dit qu’une mécanique intransitive est très fragile, et que même le plus léger déséquilibre de la part du joueur peut mener à une stratégie complètement dominante de la part de l’adversaire.

Bien entendu, contre un adversaire humain qui note que nous jouons toujours P, leur contre-stratégie serait de jouer une plus grande proportion de s, ce qui alors nous force à jouer un peu de R, ce qui ensuite les amène à jouer p, ce qui nous fait jouer S, ce qui les amène à jouer r, et ainsi de suite. Si nous ajustons constamment nos stratégies pour nous contrer, est-ce que nous pouvons atteindre un stade où les deux d’entre nous font du mieux qu’ils peuvent ? Au fil du temps, est ce que nous tendons vers une certaine forme d’état stable ?

Quelques théorèmes de maths

Avant de répondre à cette question, voici plusieurs choses pour lesquelles je vais vous demander de me faire confiance ; des personnes bien plus intelligentes que moi les ont de fait prouvées mathématiquement, mais ce n’est pas un cours sur les preuves mathématiques alors je mets de côté cet aspect des choses et j’espère que vous me pardonnerez pour ça.

Tout d’abord si les mécaniques de jeu sont symétriques (c’est-à-dire, que les deux joueurs ont exactement le même ensemble d’options et qu’elles fonctionnent de la même manière), la solution finira par être la même pour les deux joueurs ; la probabilité que l’adversaire choisisse Rock est la même que notre probabilité.

Ensuite chaque gain doit être le même que les autres ; c’est-à-dire, R = P = S ; si n’importe quelle stratégie vaut d’être choisie de n’importe quelle manière, elle fournira les mêmes gains que toutes les autres stratégies valides, parce que si les gains étaient un peu moins élevés que les autres cela ne vaudrait plus le coup d’être choisi (vous prendriez n’importe quoi d’autre avec un gain plus élevé), et si c’était plus élevé que les autres, vous le choisiriez exclusivement et ignorerez les autres. Ainsi, tous les coups potentiels qui méritent d’être pris ont les mêmes gains.

Enfin, en particulier dans les jeux à somme nulle symétriques, le gain de toutes les options doit être égal à zéro (parce que les gains seront les mêmes pour les deux joueurs à cause de la symétrie, et la seule façon que les gains s’ajoutent pour donner zéro et d’être égaux est qu’ils soient tous deux à zéro).

En résumé :

  • Tous les gains qui valent la peine d’être choisis, donnent un gain égal à chacun.
  • Les jeux à somme nulle symétriques ont tous [ NdT : la somme de tous ] les gains égale à zéro.
  • Les jeux symétriques ont la même solution pour tous les joueurs.

Conclure la solution Pierre Ciseau Papier

Revenons à nos équations. Pierre-Ciseau-Papier est un jeu symétrique à somme nulle, donc :

  • R = P = S = 0.

Comme l’adversaire doit choisir exactement un coup, nous connaissons aussi les probabilités de ses coups font 100% une fois cumulés.

  • r + p + s = 1

À partir d’ici nous pouvons résoudre le système d’équations par substitution :

  • R = 0 = s-p, donc p=s
  • P = 0 = r-s, donc r=s
  • S = 0 = p-r, donc p=r
  • r+p+s = r+r+r = 1, donc r=1/3
  • Comme r=p=s, alors p=1/3s=1/3

Ainsi notre solution est que l’adversaire devrait utiliser r, p et s chacun avec un probabilité de 1/3. Cela suggère que contre un adversaire complètement aléatoire, ce que nous choisissons n’a pas d’importance, nos chances de gagner sont les mêmes quoi qu’il arrive. Bien entendu, l’adversaire sait aussi cela, et ainsi si nous choisissons une stratégie déséquilibrée il peut modifier le ratio de ses coups pour nous battre ; notre meilleure stratégie est aussi de choisir chaque coup avec une probabilité de 1/3.

Notez qu’en situation de jeu réelle, cela ne veut pas dire que la meilleure stratégie est de jouer au hasard (disons, en lançant secrètement un dé avant chaque coup) ! Comme je l’ai dit avant, lorsque des humains essaient de jouer aléatoirement, ils ont tendance à ne pas y arriver, alors dans le monde réel la meilleure stratégie est quand même que jouer chaque coup aussi souvent que les autres, mais en même temps, quel coup vous choisissez dépend de votre capacité à détecter et exploiter les motifs dans le jeu de votre adversaire, tout en masquant n’importe quel motif apparent dans votre jeu. Ainsi notre solution de 1:1:1 ne dit pas quel coup vous devriez choisir à n’importe quel moment (ce qui est en fait là d’où vient la compétence dans le jeu), mais simplement qu’au cours du temps nous nous attendons à ce que la stratégie optimale soit un ratio 1:1:1 (parce que toute déviation offre à votre adversaire une stratégie qui gagne plus souvent jusqu’à ce que vous réajustiez votre stratégie de nouveau à 1:1:1).

Résoudre Pierre-Ciseau-Papier avec des scores inégaux

Le précédent exemple était parfait pour Pierre-Ciseau-Papier, mais comment pouvons-nous appliquer cela à quelque chose de plus intéressant ? Pour notre prochaine étape, changeons la mécanique de score. Par exemple, dans les jeux de combat il y a un système intransitif usuel qui veut que les attaques battent les projections, que les projections battent les blocages, et que les blocages battent les attaques, mais chacun d’entre eux inflige une quantité de dégâts différente, alors ils ont tendance à avoir des résultats différents dans le sens où chaque choix risque une différente quantité. Comment Pierre-Ciseau-Papier évolue lorsque nous changeons les coûts ?

Voici un exemple. Supposons que j’ajoute une nouvelle règle : chaque victoire en utilisant Rock compte double. Vous pourriez aussi aisément voir cela comme ça : dans un jeu de combat, les attaques infligent des dégâts normaux, et les blocages infligent la même quantité de dégâts qu’une attaque (disons qu’un blocage réalisé avec succès permet une contre-attaque), mais les projections infligent le double de dégâts comparativement à une attaque ou un blocage. Mais disons simplement que « chaque victoire avec Rock compte double » ici pour la simplicité. Comment est-ce que cela affecte nos probabilités ?

À nouveaux nous démarrons avec un tableau de gains :


rps
R0-12
P10-1
S-210

Puis nous utilisons ceci pour construire nos trois équations de gains :

  • R = 2s-p
  • P = r-s
  • S = p-2r

À nouveau, le jeu est symétrique et à somme nulle, et à la fois notre adversaire et nous devons choisir exactement un coup, alors nous avons toujours :

  • R = P = S = 0
  • r+p+s = 1

Puis nous résolvons :

  • R = 0 = 2s-p, donc 2s = p
  • P = 0 = r-s, donc r = s
  • S = 0 = p-2r, donc 2r = p
  • r+p+s = r+2r+r = 1, donc r=1/4
  • r=s, donc s=1/4
  • 2r=p, donc p=1/2

Donc ici nous obtenons un résultat surprenant : si nous doublons les gains pour Rock, le résultat final est que Paper est choisi la moitié du temps, alors que Rock et Scissors sont choisis chacun un quart du temps ! C’est une réponse à laquelle vous ne seriez pas arrivé par vous même sans faire les calculs, mais en rétrospective elle fait sens : comme Scissors est un coup plus risqué, les joueurs le choisiront moins. Si vous savez que votre adversaire a moins de chance de joueur Scissors, Papier a plus de chance de faire une égalité ou une victoire, et ainsi c’est réellement Papier (et non Rock) qui est joué plus fréquemment.

Ainsi si vous aviez un jeu de combat où une projection réussie inflige deux fois plus de dégâts qu’une attaque ou un blocage réussi, mais que vous infligiez autant de dégâts avec un blocage ou une attaque, alors vous pourriez vous attendre à voir deux fois plus de tentatives d’attaques que de projections ou de blocages !

Résoudre Pierre-Ciseau-Papier avec des gains incomplets

Supposons que nous prenions en compte le coût en ressources dedans. Les jeux de combat n’ont typiquement pas de « coût » associé à l’exécution d’une action (autre que le temps, peut-être), mais les jeux de stratégie en temps-réel ont en général des coûts en ressources pour produire des unités.

Prenons ici un simple jeu de stratégie temps-réel où vous avez des chevaliers (knights) qui battent des archers, qui battent des volants (fliers), et les volants battent les chevaliers. Allons plus loin et disons que si vous envoyez un type d’unité contre le même type, ils se tuent mutuellement alors il n’y a aucune perte ou gain net de n’importe quel côté, mais que c’est un peu différent avec les gagnants. Disons que lorsque les chevaliers attaquant les archers, ils gagnent, mais ils perdent 20% de leur santé suite à la volée de flèches initiale avant qu’ils arrivent au contact. Et disons que contre les volants, les archers perdent 40% de leur santé pour contre-attaquer. Mais contre les chevaliers, les volants ne subissent aucun dégât du tout, parce que les chevaliers ne peuvent rien faire d’autre que rester sur place et recevoir les dégâts (leurs épées ne fonctionnent pas très bien contre des ennemis une vingtaine de mètres au dessus d’eux, qui leur balancent des pierres par dessus). Finalement, disons que les chevaliers coûtent 50 or, les archers coûtent 75 Or et les volants coûtent 100 Or. Maintenant, comment est-ce que tout cela fonctionne ?

Nous partons de la table des gains :


kaf
K50-50=0(-50*0.2)+75=+65-50
A-75+(0.2*50)= -6575-75=0(-75*0.4)+100=+70
F50-100+(75*0.4)= -70100-100=0

Explications : si nous prenons tous les deux la même unité, cela se termine à zéro, c’est juste du bon sens, mais ce qui se passe réellement ici est que nous payons tous les deux la même quantité et perdons tous les deux l’unité. Ainsi nous avons tous les deux une perte nette, mais l’un par rapport à l’autre, cela reste une somme nulle (par exemple, avec Knight vs Knight, nous avons un gain de +50 comparativement à l’adversaire parce que nous battons son chevalier, mais nous perdons aussi -50 Or parce que notre chevalier meurt aussi, et en faisant l’addition de ces résultats ensemble nous finissons avec un gain net de zéro).

Et que se passe t’il lorsque notre Knight rencontre un Archer ennemi ? Nous tuons leur Archer, ce qui représente un avantage de 75 Or, mais ils ont aussi réduit les PV de notre Knight de 20%, alors nous pouvons dire que nous avons perdu 20% de notre coût de Knight de 50, ce qui signifie que nous avons perdu l’équivalent de 10 Or dans le processus. Ainsi le résultat final est que nous n’avons qu’une avance de 65 Or.

Lorsque notre Knight rencontre un ennemi Flier, nous perdons le Knight alors nous avons 50 Or en moins. Et cela ne fait rien à l’adversaire. Quand est-ce que le coût du Flier est pris en compte ? Dans ce cas, pas du tout, vraiment – l’adversaire continue à avoir un Flier avec le combat, alors il possède toujours l’équivalent de 100 Or de Flier en jeu, il n’a rien perdu… du moins, pas encore !

Ainsi dans le de différents coûts ou victoires incomplètes, la partie difficile est simplement d’altérer votre tableau de gains. À partir de là, le processus reste le même :

  • K = 0k + 65a + (-50)f = 65a-50f
  • A = (-65)k + 0a + 70f = 70f-65k
  • F = 50k + (-70)a + 0f = 50k-70a
  • K = A = F = 0
  • k+a+f = 1

Après résolution nous trouvons :

  • K = 0 = 65a-50f, donc 65a = 50f
  • A = 0 = 70f-65k, donc 70f = 65k, donc f = (13/14)k
  • F = 0 = 50k-70a, donc 50k = 70a, donc a = (10/14)k
  • k+a+f = k + (10/14)k + (13/14)k = (37/14)k = 1, donc k = 14/37
  • f = (13/14)k = (13/14)(14/37), donc f = 13/37
  • a = (10/14)k = (10/14)(14/37), donc a = 10/37

Dans ce cas, vous verriez de fait un mix assez égal d’unités, avec les chevalier qui sont un peu plus présents et les archers un peu moins. Si vous vouliez que les volants soient plus rares, vous pourriez jouer avec leur coût, ou permettre aux chevaliers de leur infliger un peu de dégâts, ou n’importe quoi d’autre.

Résoudre Pierre-Ciseau-Papier avec un scoring asymétrique

Jusqu’à présent nous sommes partis d’un jeu qui était symétrique : nous avons le même ensemble de coups, et nous gagnons ou perdons tous les deux les mêmes quantités en suivant le même ensemble de règles. Mais tous les jeux intransitifs ne sont pas parfaitement symétriques. Par exemple, supposons que je conçoive une variante de Pierre-Ciseau-Papier où à chaque tour, je révèle une nouvelle carte qui modifie les récompenses en cas de victoire. Pour ce tour, ma carte dit que mon adversaire obtient deux points s’il gagne avec Rock, mais pas moi (je marquerai normalement). Comment est-ce que cela change les choses ?

De fait cela complique grandement la situation, parce que maintenant les deux joueurs doivent déterminer les probabilités des coups de leur adversaire, et ces probabilités peuvent ne plus être les mêmes ! Disons que le joueur A a le double bonus sur la victoire avec Rock, et le joueur B ne l’a pas. Quelle est la stratégie optimale pour les deux joueurs ? Et quel avantage cela donne au joueur A, si c’était le cas ? Cherchons la réponse en construisant deux tables de gains.

La table de gains du joueur A ressemble à ça :


rBpBsB
RA0-12
PA10-1
SA-110

La table de gains du joueur B ressemble à ça :


rApAsA
RB0-11
PB10-1
SB-210

Ici nous pouvons partir du principe que RA=PA=SA et RB=PB=SB, et aussi que rA+pA+sA = rB+pB+sB = 1. Toutefois, nous ne pouvons pas partir du principe que RA=PA=SA=RB=PB=SB=0, parce que nous ne savons pas que les gains pour les joueurs A et B sont égaux ; en fait, l’intuition nous dit qu’ils ne le sont probablement pas ! Maintenant nous avons cette série d’équations intimidantes :

  • RA = 2sB – pB
  • PA = rB – sB
  • SA = pB – rB
  • RB = sA – pA
  • PB = rA – sA
  • SB = pA – 2rA
  • RA = PA = SA
  • RB = PB = SB
  • rA + pA + sA = 1
  • rB + pB + sB = 1

Nous pourrions faire cela de la manière la plus difficile par des substitutions, mais il y a une façon plus facile d’utiliser les matrices. Voici comment cela fonctionne : nous réécrivons les tables de gains sous forme de matrices. Voici pour la première :


RA0-12
[PA10-1]

SA-110

Ici, la colonne de gauche représente le côté gauche des trois premières équations ci-dessus, la seconde colonne est rA, la troisième colonne est pA et la quatrième colonne est sA. Deux modifications pour la clarté : en premier déplaçons la colonne la plus à gauche vers la droite, ce qui rend plus facile de travailler avec ; et en second, comme RA=PA=SA, remplaçons les simplement par une simple variable X, qui représente les gains nets pour le joueur A :


0-12X
[10-1X]

-110X

C’est simplement une façon d’écrire ces trois équations, en faisant omission des noms des variables, mais en les conservant toutes alignées dans le même ordre, de manière à ce que chaque colonne représente une différente variable :

0rB -1pB +2sB = X

1rB +0pB -1sB = X

-1rB +1pB +0sB = X

L’algèbre nous dit que nous pouvons tout multiplier dans une équation avec une constante, et que tout reste vrai (ce qui signifie que nous pourrions multiplier n’importe quelle ligne de la matrice par n’importe quelle valeur et cela restera valide, tant que nous multiplions les quatre entrées dans les lignes avec la même valeur). L’algèbre nous dit aussi que nous pourrions ajouter les deux côtés de deux équations ensemble et le résultat restera vrai, ce qui signifie que vous pourrions ajouter chaque entrée de deux lignes ensemble et la ligne résultante restera une entrée valide (ce que nous pourrions utiliser pour ajouter aux lignes déjà présentes, ou même remplacer une ligne existante avec le nouveau résultat). Et nous pouvons aussi ré-arranger les lignes, parce que toutes restent vraies quel que soit l’ordre dans lequel on les a placées. Ce que nous voulons faire ici est de placer la matrice dans ce que nous appelons une forme triangulaire, c’est-à-dire, d’une forme où tout sous la diagonale vaut zéro, et les diagonales elles-mêmes (marquées ici avec un astérisque) doivent être non-nulles :


*???
[0*??]

00*?

Ainsi, nous commençons d’abord par les réordonner en échangeant les lignes du dessus et du milieu :


-110X
[0-12X]

10-1X

Pour éliminer le +1 dans la ligne du bas, nous ajoutons les lignes du haut et du bas ensemble replaçons la ligne du bas comme cela :


-110X
+10-1X

01-12*X

Notre matrice est maintenant :


-110X
[0-12X]

01-12*X

Maintenant voulons éliminer le +1 sur la ligne du bas, alors nous ajoutons les lignes du milieu et de bas ensemble et remplaçons la colonne du bas avec le résultat :


-110X
[0-12X]

0013*X

Maintenant nous pouvons les écrire sous la forme d’équations standard et les résoudre, en partant du bas, et en utilisant les substitutions :

  • +1(sB) = 3*X, donc sB = 3*X
  • -1(pB) +2(sB) = X, donc -1(pB)+2(3*X) = X, donc pB = 5*X
  • -1(rB) + 1(pB) = X, donc rB = 4*X

À ce stade nous n’avons pas réellement besoin de savoir ce qu’est X, mais nous savons que le ratio pour le joueur B est 3 Scissors à 5 Papier à 4 Rock. Comme sB+pB+rB=1, cela signifie :

rB = 4/12 pB = 5/12 sB = 3/12

Nous pouvons utiliser la même technique avec la seconde série d’équations pour déterminer le ratio optionnel pour le joueur A. Encore une fois, la table de gains est :


rApAsA
RB0-11
PB10-1
SB-210

Ce qui devient la matrice suivante :


0-11RB
[10-1PB]

-210SB

À nouveau nous réorganisons, et comme RB=PB=SB, appelons-les toutes avec une nouvelle variable Y (nous n’utilisons pas X pour éviter la confusion avec le X précédent ; souvenez-vous que les gains d’un joueur peuvent être différents de ceux ici). Échangeons le bas et le haut cette fois, tout en remplaçant les gains par Y :


-210Y
[10-1Y]

0-11Y

Pour éliminer le + dans la ligne du centre, nous devons multiplier la ligne du centre par 2 avant de l’ajouter à la ligne du dessus (ou, multiplier la ligne du dessus par 1 / 2 mais je trouve que c’est plus facile de multiplier avec les nombres entiers que des fractions).


-210Y
++1*20*2-1*2Y*2

01-2Y*3

Notre matrice est maintenant :


-210Y
[01-2Y*3]

0-11Y

En ajoutant la deuxième et la troisième ligne pour éliminer le -1 dans la ligne du bas nous obtenons :


-210Y
[01-2Y*3]

00-1Y*4

À nouveau en travaillant à rebours et en substituant :

  • sA = -Y*4
  • pA – 2sA = Y*3, donc pA = -Y*5
  • -2rA + pA = Y, donc -2rA = 6Y, donc rA = -Y*3

Maintenant, cela pourrait paraître un peu étrange que nous ayons beaucoup de nombres négatifs ici quand nous avons obtenus des nombres positifs avant. C’est probablement un effet secondaire du fait que le gain moyen pour le joueur A est probablement positif alors que celui du joueur B est probablement négatif, mais dans n’importe quel cas tout cela ne comptera pas parce que nous ne nous intéressons qu’au ratio relatif entre Rock, Paper et Scissors. Pour le joueur A, c’est 3 Rock pour 4 Scissors pour 5 Paper.

rA = 3/12 pA = 5/12 sA = 4/12

Ce qui est très différent du mix optimal pour le joueur B :

rB = 4/12 pB = 5/12 sB = 3/12

À présent, nous pouvons utiliser cela pour déterminer l’avantage réel pour le joueur A. Nous pourrions faire ceci en fabriquant un tableau 12×12 et en y mettant toutes les 144 combinaisons et en les comptant en utilisant les probabilités, ou nous pourrions faire une simulation Monte Carlo, ou nous pourrions simplement entrer ces valeurs dans nos équations existantes. Pour moi, c’est la dernière option qui est la plus facile, mais nous avons déjà une série d’équations d’avant qui relient directement celles-là ensemble :

sA = -Y*4, donc Y = -1/12

rB = X*4, donc X = +1/12

Nous savons que RA=PA=SA et RB=PB=SB, donc cela signifie que le gain pour le joueur A est +1/12 et pour le joueur c’est -1/12. Cela fait bien sens et agir comme une vérification ; comme cela reste un jeu à somme nulle, nous savons que le gain pour A doit être égal au gain négatif pour B. Dans un jeu symétrique les deux devraient être zéro, mais il n’est pas symétrique. Cela dit, il apparaît que si les joueurs jouent de façon optimale, l’avantage est vraiment petit : seulement une victoire de plus toutes les 12 parties si les deux jouent de façon optimale !

Résoudre un Pierre-Ciseau-Papier étendu

Jusqu’à présent toutes les relations que nous avons analysées n’avaient que trois choix. Pouvons-nous utiliser la même technique avec plus ? Oui, cela signifie que nous ferons un peu plus de la même chose.

Analysons le jeu Pierre-Ciseau-Papier-Lézard-Spock (Rock-Paper-Scissors-Lizard-Spock). Dans ce jeu, Pierre bat Ciseau et Lézard ; Papier bat Pierre et Spock ; Ciseau bat Papier et Lézard ; et Lézard bat Spock (et Lézard bat Papier, Spock bat Ciseaux et Pierre). Notre table de gain est (avec un « k » pour Spock comme nous avons déjà un « s » pour Scissors et « z » pour Lizard pour que cela ne ressemble pas au nombre 1):


rpszk
R0-111-1
P10-1-11
S-1101-1
Z-11-101
K1-11-10

Nous savons aussi que r+p+s+z+k=1 et R=P=S=L=K=0. Nous pourrions résoudre cela à la main aussi, mais il existe une autre façon de faire cela en utilisant Excel ce qui rend les choses plus facile parfois.

D’abord vous aurez à saisir la matrice ci-dessus dans une grille de cellules de 5×5 quelque part. Vous aurez aussi besoin d’ajouter une autre colonne de 1×5 avec que des 1 (ou n’importe quel nombre non égal à zéro) pour représenter la variable X (le gain) à droite de votre grille 5×5. Ensuite, sélectionnez un nouvelle colonne 1×5 qui est vide (cliquez et tirez), et ensuite entrez cette formule dans la barre de formules :

=MMULT(MINVERSE(A1:E5),F1:F5)

Pour le paramètre MINVERSE, mettez les cellules en haut à gauche et en bas à droite de votre grille de 5×5 (j’ai utilisé A1:E5 si la grille est dans le coin en haut à gauche de votre feuille de calcul). Pour le paramètre final (j’ai utilisé F1:F5 ici), donnez la valeur 1 à toute la colonne de 1×5. Enfin, et cela c’est important, appuyez sur Ctrl+Maj+Entrée lorsque vous avez fini de saisir la formule (et pas juste Entrée). Cela propage la formule à toutes les cinq cellules que vous avez sélectionnées et les traite comme une zone unifiée, ce qui est nécessaire.

Un avertissement est que cette méthode ne fonctionne pas toujours ; en particulier, s’il n’y a pas de solutions ou un nombre infini de solutions, cela vous donnera #NUM comme résultat au lieu d’un nombre. En fait, si vous entrez la table de gain ci-dessus, cela vous donnera cette erreur : en mettant l’une des entrées quelque chose de très légèrement différent (disons, en changeant l’un des +1 en +0,999999), vous générerez une solution unique qui est seulement imprécise par une petite fraction, alors arrondissez-là à la décimale la plus proche pour la « vraie » réponse. Un autre avertissement est que n’importe qui connaissant un peu les maths risque d’être choqué quand vous ferez ça, parce qu’est une manière de tricher et vous n’êtes pas supposé résoudre une matrice comme ça.

Excel nous donne une solution de 0.2 pour chacune des cinq variables, ce qui signifie qu’il est équiprobable que l’adversaire choisisse n’importe lequel des coups. Nous pouvons ensuite vérifier que oui, en effet, R=P=S=L=K=0, et ainsi cela n’a pas d’importance quel coup on choisit, n’importe lequel fera l’affaire aussi bien qu’un autre si l’adversaire joue aléatoirement avec des chances égales pour chaque coup.

Résoudre le Pierre-Ciseau-Papier avec des relations inégales

Toutes les mécaniques intransitives ne sont pas équilibrées à égalité. Dans certains cas, même sans les coûts avec des poids différents, certains coups sont simplement meilleurs que d’autres. Par exemple, prenons en considération le jeu déséquilibré de Pierre-Ciseau-Papier-Dynamite (Rock-Paper-Scissors-Dynamite). L’idée est qu’avec ce quatrième coup, Dynamite bat Rock (par explosion), et Scissors bat Dynamite (en coupant la mèche). On pourrait discuter qui de Papier ou Dynamite devrait gagner, mais pour notre propos, disons que Dynamite bat Paper. En théorie cela fait que Dynamite et Scissors semblent de vrais bons choix, parce qu’ils battent tous les deux les trois autres coups. Cela fait aussi que Rock et Paper semblent de mauvais choix, parce qu’ils perdent face à deux des trois autres coups. Qu’en disent les maths ?

Notre table de gains ressemble à ça :


rpsd
R0-11-1
P10-1-1
S-1101
D11-10

Avant d’aller plus loin, nous rencontrons un problème : si vous regardez avec attention, vous verrez que Dynamite est supérieur ou égal à Paper dans toutes les situations. C’est-à-dire que pour chaque entrée dans la ligne de P, c’est inférieur ou égal à l’entrée correspondante dans la ligne D (et de même, chaque entrée dans la colonne p est inférieure ou égal à la colonne d). Paper et Dynamite perdent tous les deux face à Scissors, les deux battent Rock, mais contre l’un et l’autre, Dynamite gagne. En d’autres termes, il n’y a aucune raison logique de prendre Paper parce que lorsque vous y réfléchissez, vous prendriez Dynamite à la place ! En terme de théorie des jeux, nous disons que Paper est strictement dominé par Dynamite. Si nous avions essayé de résoudre cette matrice mathématiquement comme nous l’avons fait auparavant, nous serions arrivés à des réponses bien étranges et nous aurions rapidement trouvé que ce n’était pas solvable (ou que les réponses ne faisaient pas sens, comme une probabilité pour r, p, s, ou d qui était inférieur à zéro ou plus grande que un). La raison pour laquelle cela n’aurait pas fonctionné est qu’à un certain stade nous aurions dû partir du principe que R=P=S=D, mais dans ce cas ce n’est pas vrai – le gain pour Paper doit être inférieur que le gain pour Dynamite, ainsi c’est une hypothèse invalide. Pour corriger cela, avant d’aller plus loin, nous devons systématiquement éliminer tous les choix qui sont dominés. En d’autres termes, retirer Paper comme choix.

La nouvelle table de gain devient :


rsd
R01-1
S-101
D1-10

Nous vérifions à nouveau pour voir si, après la première série d’éliminations, aucune autre stratégie n’est maintenant dominée (parfois une ligne ou une colonne n’est pas strictement dominée par une autre, avant que vous ne retiriez d’autres choix dominés, et ainsi vous devez refaire la procédure de façon répétitive jusqu’à ce que vous éliminiez tout). Encore une fois, pour faire la vérification des stratégies dominées, vous devez comparer chaque paire de lignes pour voir si une domine l’autre, et ensuite chaque paire de colonnes de la même manière. Oui, cela veut dire qu’il y a beaucoup de comparaisons si vous donnez à chaque joueur dix ou douze choix !

Dans ce cas éliminer Paper était tout ce qui était nécessaire, et de fait nous sommes revenus à la même table de gains que pour le Pierre-Ciseau-Papier d’origine, mais avec Papier étant « renommé » en Dynamite. Et maintenant vous savez pourquoi, mathématiquement, cela ne fait jamais sens d’ajouter Dynamite comme quatrième coup.

Une autre relation inégale

Et si à la place nous avions créé un nouveau coup qui n’était pas faiblement dominé, mais fonctionnait un peut différemment de la normale ? Par exemple, quelque chose qui serait équivalent à Scissors, à l’exception qu’il aurait fonctionné dans l’ordre inverse, en battant Rock mais en perdant face à Papier ? Disons… Engin de Construction (Construction Vehicle) (C), qui écrase (gagne contre) Rock, mais reçoit un procès-verbal (perd contre) Paper, et finit à égalité contre Scissors parce qu’aucun des deux ne peut vraiment interagir.

Maintenant notre table de gains ressemble à ça :


rpsc
R0-11-1
P10-11
S-1100
C1-100

Ici, aucun coup est strictement meilleur qu’un autre, alors nous pouvons commencer à résoudre. Nous savons que r+p+s+c=1, et que les gains R=P=S=D=0. Notre matrice devient :


0-11-10

10-110
[-11000]

1-1000

En ré-arrangeant les lignes pour obtenir autre chose que zéro le long de la diagonale, nous faisons cela en inversant l’ordre entre le haut et le bas :


1-1000

-11000
[10-110]

0-11-10

En mettant à zéro la première colonne en ajoutant les deux premières lignes, et en soustrayant la troisième de la première nous obtenons :


1-1000

00000
[0-11-10]

0-11-10

C’est curieux ! La seconde ligne est pleine de zéros (ce qui ne nous donne absolument aucune information utile, cela nous dit simplement que zéro égale zéro), et les deux lignes du bas sont exactement les mêmes l’une que l’autre (ce qui signifie que la dernière ligne est redondante et encore une fois ne nous dit rien de particulier). Nous voilà avec seulement deux lignes d’information utile. En d’autres termes, nous avons deux équations (trois si vous comptez r+p+s+c=1) et quatre inconnues.

Cela veut dire qu’il y a de fait plus d’une seule solution valide ici, et potentiellement un nombre infini de solutions. Nous déterminons les solutions à la main :

  • r-p=0, donc r=p
  • -p+s-c=0, donc c=s-p

En substituant avec r+p+s+c=1, nous obtenons :

  • p+p+s+(s-p)=1, donc p+2s=1, donc p=1-2s (et donc, r=1-2s).

En substituant en retour avec c=s-p, nous obtenons c=s-1+2s, donc c=3s-1.

Nous avons ainsi fait en sorte d’exprimer toutes les trois autres variables en terme de s :

  • p=1-2s
  • r=1-2s
  • c=3s-1

Ainsi il semblerait tout d’abord qu’il y ait en fait un nombre infini de solutions : choisissez n’importe quelle valeur pour s, et cela vous donnera les valeurs correspondantes pour p, r et c. Mais nous pouvons réduire les fourchettes encore plus.

Comment ? En se souvenant que toutes ces variables sont des probabilités, ce qui signifie qu’elles doivent toutes être dans la fourchette de 0 (si elles n’arrivent jamais) à 1 (si elles arrivent tout le temps). Les probabilités ne peuvent jamais être inférieures à zéro et supérieures à 1. Cela nous permet de limiter l’étendue de s. S’il y a une chose dont nous sommes sûrs, c’est qu’elle doit être entre 0 et 1.

À partir de l’équation c=3s-1, nous savons que s doit être au moins 1/3 (sinon, c serait négatif) et s peut être au mieux 2/3 (sinon c serait plus grand que 100%). En regardant à p et r, nous savons que s peut aller de 0 à 1/2. En combinant les deux fourchettes, s doit être entre 1/3 te 1/2. C’est intéressant : cela nous montre que quoi qu’il arrive, Scissors est une partie indispensable de toutes les stratégies idéales, en étant utilisé quelque part entre un tiers et la moitié du temps.

À la condition basse de la limite (s=1/3), nous trouvons que p=1/3, r=1/3 et c=0, ce qui est une stratégie valide. À la limite haute (s=1/2), nous trouvons que p=0, r=0, c=1/2. Et nous pourrions aussi opter pour n’importe quelle stratégie entre les deux disons s=2/5, p=1/5, c=1/5.

Est-ce que n’importe laquelle de ces stratégies est « meilleure » que les autres, de telle manière qu’une seule gagnerait plus que les autres ? Malheureusement cela demande un peu plus de théorie des jeux à l’intérieur de laquelle je souhaitais entrer pour aujourd’hui, mais je peux vous dire que la réponse est « ça dépend » sur la base de certaines hypothèses sur à quel point votre adversaire est rationnel, et si les joueurs sont capables de faire des erreurs occasionnelles lorsqu’ils implémentent leur stratégie, et ce que les joueurs connaissent de la manière de jouer de leurs adversaires, entre autres choses. Pour notre propos, nous pouvons dire que n’importe lequel est aussi bon qu’un autre, bien que je sois certain que les théoriciens de jeux professionnels pourrait débattre du cas d’un point de vue philosophique pour certaines valeurs par rapport à d’autres.

Aussi, pour notre propos, nous pourrions dire qu’Engin de Construction n’est probablement pas un bon ajout au jeu Pierre-Ciseau-Papier, parce qu’il permet une stratégie où le fait de jouer C peut être complètement ignoré, et une autre stratégie gagnante où à la fois P et R sont ignorés, ce qui nous fait nous demander pourquoi nous perdons autant de ressources en développement pour implémenter deux ou trois coups que nous ne verrions jamais joués une fois que les joueurs seraient suffisamment compétents !

Résoudre le jeu de Malkav

Jusqu’à présent nous avons systématiquement examiné chacune de nos hypothèses de base : qu’un jeu a un gain symétrique, qu’il est à somme nulle, qu’il y a exactement trois choix. Il y a une autre chose que nous n’avons pas couvert dans le cas de deux joueurs, et c’est ce qui se passe si les joueurs ont différentes séries de choix – pas simplement un gain asymétrique, mais un jeu asymétrique. Si nous nous sommes reposés sur le fait que chaque joueur avait exactement autant de coups, que se passe t’il lorsqu’un joueur a, disons, six coups différents quand son adversaire n’en a que cinq ? Il semblerait être qu’un tel problème soit insolvable pour une solution unique (il y a six inconnues et seulement cinq équations, n’est-ce-pas?) mais en fait il apparaît que nous pouvons utiliser une technique plus puissante pour résoudre un tel jeu de façon unique, dans certains cas.

Prenons en considération une carte appelée « Jeu de Malkav » d’un obscur JCC [ NdT : Vampyr The Eternal Struggle ] dont la plupart d’entre vous n’a probablement jamais entendu parler. Cela fonctionne comme cela : tous les joueurs choisissent secrètement et simultanément un nombre. Le joueur qui a joué cette carte choisit en 1 et 6, alors que tous les autres joueurs choisissent entre 1 et 5. Chaque joueur gagne autant de vie que le nombre qu’il a choisi… à moins qu’un autre joueur choisisse un nombre exactement de moins un, auquel cas il perd autant de vie à la place. Ainsi par exemple si vous choisissez 5, vous gagnez 5 vies, à moins qu’un autre joueur choisisse 4. Si n’importe qui d’autre choisit 4, vous perdez 5 vies… et il gagne 4, à moins que quelqu’un d’autre choisisse 3, et ainsi de suite. Cela peut devenir très compliqué avec beaucoup de joueurs, alors considérons simplement le cas de deux joueurs. Faisons aussi une hypothèse simplificatrice que le jeu est à somme nulle, et que si vous gagnez 1 vie c’est équivalent en valeur à votre adversaire qui perd 1 vie (je me rends compte que ce n’est pas nécessairement valide, et cela va varier si la base des totaux de vie relatifs, mais au moins c’est un point de départ pour comprendre ce que vaut réellement cette carte).

Nous pourrions nous demander, quel est le gain attendu à jouer cette carte, dans l’ensemble ? Est-ce que l’option supplémentaire de jouer 6 quand votre adversaire ne peut uniquement jouer que jusqu’à 5 ? Quelle est la meilleure stratégie et quel est le résultat final attendu ? En résumé, est-ce que la carte vaut le coût d’être jouée… et si oui, lorsque vous la jouez, comment décidez-vous quoi choisir ?

Comme d’habitude, nous démarrons avec une table de gains. Appelons les choix P1-P6 (pour le Player (joueur) qui a joué la carte) et O1-O5 (pour l’ Opponent (adversaire) :


O1O2O3O4O5
P103-2-3-4
P2-305-2-3
P32-507-2
P432-709
P5432-90
P65432-11

Nous pourrions essayer de résoudre cela, et il ne semble qu’il existe un choix dominé pour n’importe quel joueur, mais nous allons rapidement trouver que les nombres devient velus très vite… et aussi que cela se révèle être insolvable pour des raisons que vous trouverez si vous les cherchez. De base, avec 6 équations et 5 inconnues, il y a redondance… à l’exception dans ce cas, aucune ligne ne s’annule, et à la place vous finissez avec au moins deux équations qui se contredisent l’une et l’autre. Alors il doit y avoir des stratégies dominées ici… c’est juste qu’elles ne sont pas immédiatement évidentes, parce qu’il y a un ensemble de lignes ou colonnes qui sont collectivement dominées par un autre ensemble, ce qui est plus difficile à trouver juste en regardant. Comment allons-nous les trouver ?

Nous commençons par trouver le meilleur coup pour chaque joueur, si il savait ce que l’adversaire allait faire à l’avance. Par exemple, si l’adversaire sait que nous allons jouer P1, leur meilleur coup est O5 (ce qui leur donne un net de +4 et nous une perte de -4). Mais ensuite nous continuons à réagir à leur réaction : si le joueur sait que l’adversaire va choisir O5, leur meilleur coup est P4. Mais contre P4, le meilleur coup est O3. Contre O3, le meilleur coup est P2. Contre P2, il y deux bons coups équivalents : O1 et O5, alors nous devons considérer les deux options :

  • Contre O5, la meilleure réponse est P4, comme avant (et nous continuons à tourner dans la séquence intransitive O5->P4->O3->P2->O5 indéfiniment).
  • Contre O1, la meilleure réponse est P6. Contre P6, la meilleure réponse est O5, ce qui nous ramène à la séquence intransitive O5->P4->O3->P2->O1->P6->O5.

Et si nous avions démarré à un endroit différent, disons en jouant initialement P3 ? Alors la meilleure réponse de l’adversaire est O2, notre meilleure réponse à cela est P6, ce qui tend à nous mener à la boucle O5->P4->O3->P2->O1->P6->O5. Si nous démarrons avec P5, la meilleure réponse est O4, qui reçoit la réponse P3, que nous avons juste couvert. Et si nous démarrions avec O1, O2, O3, O4, O5, P2, P4 ou P6 ? Toutes on déjà été prises en compte plus tôt dans une séquence, alors il ne reste plus rien à analyser.

Ainsi, nous voyons que quel que soit ce avec quoi nous démarrons, il arrive après une série de jeux répétés que seulement un petit ensemble de coups finit par faire partie des la nature intransitive de ce jeu parce qu’ils forment deux boucles intransitives (O5/P4/O3/P2 et O5/P4/O3/P2/O1/P6). En observant ces séquences, les seuls choix utilisés par n’importe lequel des joueurs sont O1, O3, O5, P2, P4, P6. N’importe quel autre choix finissant par être strictement inférieur : par exemple, à n’importe quel moment où il est avantageux de jouer P6 (c’est-à-dire, que vous vous attendez à un gain positif), il n’y a aucune raison pour vous de préférer P5 à la place (même si vous vous attendez à ce que votre adversaire joue O5, votre meilleure réponse n’est pas P5 mais P4).

En utilisant cette technique pour trouver les boucles intransitives, vous pouvez souvent réduire un large nombre de choix à un ensemble plus petit de choix viables… ou au pire, vous pouvez prouver que la totalité des grands ensembles sont en fait viables. De temps à autre vous trouverez un jeu (Le Dilemme du Prisonnier étant un exemple célèbre, si vous en avez entendu parler) où il existe un ou plusieurs endroits dans la table qui sont aussi avantageux pour les deux joueurs, de manière à ce qu’après une série de parties répétées, tous les joueurs seront attirés à ces endroits ; les théoriciens des jeux les appellent les Équilibres de Nash (Nash Equilibriums) après le nom du mathématicien qui le premier a écrit dessus. Mais vous n’avez pas à vous en inquiéter.

Alors dans ce cas, nous pouvons réduire la tableau à un ensemble de valeurs significatives :


O1O3O5
P2-35-3
P43-79
P653-11

À partir de là nous résolvons, en étant conscients que ce n’est pas symétrique. Donc, nous savons que O1=O3=O5 et P2=P4=P6, mais nous ne savons pas s’ils sont égaux à zéro ou si l’un est l’inverse de l’autre. (A priori, P2 est positif et O1 est négative, parce que nous pourrions nous attendre à ce que a personne jouant cette carte d’avoir un avantage, mais nous verrons cela plus tard).

Nous construisons une matrice, en utilisant X pour représenter le gain de P2, P4 et P6 :


-35-3X
[3-79X]

53-11X

Cela peut être réduit à une forme triangulaire et ensuite résolu, de la même manière que les problèmes précédents. Amusez-vous à le faire ! Je vous donne la réponse en dessous.

Maintenant, résoudre cette matrice vous donne les probabilités O1, O3 et O5, mais de manière connaître les probabilités de choisir P2, P4 et P6 vous devez basculer la matrice le long de la diagonale, de manière à ce que les O soient tout à gauche et les P soient tout en haut (cela s’appelle une transposition). Dans ce cas nous avons aussi besoin de rendre tous les nombres négatifs, car une telle matrice est du point de vue du joueur O, et donc a des gains opposés :


3-3-5Y
[-57-3Y]

3-911Y

Cela, aussi, peut être résolu normalement. Si vous êtes curieux, les réponses finales sont en gros :

P2:P4:P6 = 49% : 37% : 14%

O1:O3:O5 = 35% : 41% : 24%

Le gain attendu pour le joueur P (montré comme « X » au dessus) : 0,31, et le gain pour le joueur O (montré comme « Y » au dessus) est l’inverse de X : – 0,31.

En d’autres termes, dans le cas d’une partie de ce jeu à deux joueurs, lorsque les deux joueurs jouent de façon optimale, le joueur qui a joué cette carte prend la tête avec un avantage de moins d’un tiers de point de vie – alors que nous confirmons que jouer cette carte et avoir l’option supplémentaire de choisir 6 est en fait un avantage, mais il apparaît qu’il est tout petit. D’un autre côté, la possibilité de larges basculements soudains pourrait la rendre valable en condition de jeu réelles (ou peut-être pas), selon le paquet que vous jouez. Et bien entendu, le jeu devient de plus en plus compliqué dans les situations multi-joueurs que nous n’avons pas considérées ici.

Résoudre Pierre-Ciseau-Papier à trois joueurs

Jusqu’à présent nous avons couvert à peu près tous les cas possibles de jeu à deux joueurs, et vous pouvez combiner les différentes méthodes au besoin pour à peu près n’importe quelle application, ou n’importe quel type de jeu à deux joueurs. Est-ce que nous pouvons étendre ce type d’analyse à plusieurs joueurs ? Après tout, beaucoup de ces jeux impliquent plus qu’un simple face à face, ils peuvent impliquer des contextes d’équipe ou de chacun pour soi.

Les équipes sont assez faciles, s’il n’y a que deux équipes : traitez chaque équipe comme un seul « joueur » pour le propos de l’analyse. Chacun pour soi est un peu plus difficile parce que vous devez gérer plusieurs adversaires, et vous verrez que la complexité tend à exploser avec chaque joueur successif. Les jeux à trois joueurs sont énervants mais peuvent encore être résolus ; les jeux à quatre joueurs sont probablement la limite haute de ce que j’ai jamais tenté de faire à la main en utilisant n’importe laquelle des méthodes que j’ai mentionné aujourd’hui. Si vous avez un jeu à six joueurs complètement intransitif où chaque joueur possède un ensemble d’options différentes et une matrice de gains massive qui donne les gains de chaque joueur pour chaque combinaison… et bien, disons simplement que cela peut être fait, probablement avec l’aide d’un ordinateur et un théoricien des jeux professionnel, mais à ce stade vous ne voudriez sans doute pas le faire. Une chose que les théoriciens des jeux ont appris est que plus le jeu est complexe, plus cela a tendance à demander du temps aux joueurs humains dans le laboratoire pour converger vers les stratégies optimales… ce qui signifie que pour une jeu très complexe, le playtesting vous donnera une meilleure idée de comment le jeu se joue réellement « sur le terrain » que faire les maths pour prouver les solutions optimales, parce que les joueurs ne trouveront pas les solutions optimales de toutes manières. Ainsi, pour un système compliqué comme cela, vous aurez de meilleurs résultats avec le playtest… ou plus exactement, vous vous en sortirez mieux en simplifiant vos mécaniques !

Prenons un exemple cas de multijoueurs : un Pierre-Ciseaux-Papier à trois joueurs. Nous définissons les règles comme suit : si tous les joueurs font le même coup ou si tous les joueurs choisissent un coup différent, il y a égalité. Si deux joueurs font le même coup, et le troisième joueur en choisit un différent (« l’homme à part »), alors n’importe qui ayant fait le coup gagnant obtient 1 point de chaque perdant. Ainsi si deux joueurs font Pierre et le troisième fait Ciseaux, chacun des joueurs Pierre reçoit 1 point et le Ciseaux malchanceux perd 2 points. Ou si c’est l’inverse, un joueur joue Pierre alors que le les deux autres jouent Ciseaux, le joueur Pierre gagne 2 points alors que les chacun des deux autres joueurs perd 1 point. (L’idée derrière ces nombres est de conserver le jeu en somme nulle, pour simplifier, mais vous pouvez utiliser cette méthode pour résoudre n’importe quelle mécanique de score).

Bien entendu, nous savons grâce à la symétrie que la réponse à cela est 1:1:1, comme l’autre version à deux joueurs. Alors ajoutons la même modification qu’avant : gagner avec Pierre compte double (ce qui signifie, parce que c’est une somme nulle, que les pertes avec Ciseaux comptent double). Dans le cas du jeu à deux joueurs, nous avons trouvé que la solution suivante : Pierre=Ciseaux=1/4 et Papier=1/2. Est-ce que cela change dans le cas du jeu à trois joueurs, puisqu’il y a maintenant deux adversaires, ce qui rend encore plus dangereux de jouer Ciseaux (et possiblement encore plus profitable de jouer Pierre) ?

L’astuce dont nous avons besoin ici est pour rendre cela solvable est de regarder le problème de la perspective d’un seul joueur, et traiter tous les adversaires collectivement comme un adversaire unique. Dans ce cas, nous arrivons à une tableau de gains qui ressemble à ça :


rrrprspppsss
R0-12-204
P2100-1-2
S-40-2210

Vous pourriez dire : attendez une minute, il y a trois variables ici et six inconnues (deux « r » et deux « p » et deux « s », une pour chaque adversaire) ce qui signifie qu’il n’y a pas de solution unique. Mais la bonne nouvelle est que ce jeu est symétrique, ainsi nous pouvons le résoudre, parce que les probabilités des adversaires sont prises ensemble et multipliées (souvenez-vous que nous multiplions les probabilités lorsque nous avons besoin que deux choses indépendantes arrivent en même temps). Une chose pour laquelle il faut être vigilant : il y a réellement neuf possibilités pour les adversaires, pas six, mais certaines d’entre elles sont dupliquées. La table réelle est comme cela :


rrrpprrssrpppsspss
R0-1-122-2004
P211000-1-1-2
S-400-2-22110

Tout cela signifie que lorsque vous utilisez la matrice originale et l’écrivez dans sa forme étendue, nous devons nous souvenir de multiplier rp, rs et ps par 2 chacun, puisqu’il y a deux façon d’obtenir chacun d’entre eux (rp et pr, par exemple). Notez que je n’ai pas mentionné ici de quel adversaire il s’agit ; comme je l’ai dis avant, cela n’a pas d’importance parce que ce jeu est symétrique, et la probabilité que n’importe quel joueur jour Pierre ou Ciseaux est la même que pour les autres joueurs.

Ce tableau de gains ne se présente pas très bien sous forme de matrice puisque nous avons affaire à deux variables plutôt qu’une. Une manière de faire cela serait de tout diviser en trois petites matrices, une pour chacun des premiers choix des adversaires, et ensuite les comparer avec le second choix des adversaires… et ensuite résoudre chaque matrice individuellement, et en combinant les trois solutions en une seule à la fin. C’est beaucoup de travail, alors essayons de la résoudre avec l’algèbre à la place, en écrivant tout normalement et en voyant si nous pouvons isoler quelque chose en combinant les termes comme :

  • Gain pour R = -2rp+4rs-2pp+4ss = 0
  • Gain for P = 2rr+2rp-2sp-2ss = 0
  • Gain for S = -4rr-4rs+2pp+2sp = 0
  • r+s+p=1 (comme d’habitude)

Le « =0 » à la fin est là parce que nous savons que ce jeu est symétrique et à somme nulle.

Par où commencez-vous avec quelque chose comme ça ? Un point de départ utile est en général d’utiliser r+s+p=1 pour éliminer une des variables en l’exprimant en termes des autres, et en faisant la substitution dans les trois équations de gain ci-dessus. En éliminant Rock (r=1-s-p) et en faisant la substitution, après avoir multiplié et combiné les termes, nous obtenons :

  • -4pp+2ps-2p+4s = 0
  • -2p-4s+2 = 0
  • 2pp-6ps+8p+4s-4 = 0

Nous pourrions isoler p ou s dans la première et la dernière équation en utilisant la Formule Quadratique (vous savez « moins b plus ou moins la racine carrée de 4ac, le tout divisé par 2a »). Cela nous mènerait à deux solutions possibles, bien que dans la plupart des cas, vous trouveriez que vous pouvez en éliminer un quand il sort des limites de 0 et 1 (car r, p et s doivent exister dans cette fourchette, car ce sont des probabilités).

Toutefois, l’équation du milieu ci dessus nous rend la vie plus facile, car nous pouvons résoudre pour p ou s en termes de l’autre :

  • p = 1-2s

En substituant dans les deux autres équations ce nous donne le même résultat, qui nous permet de savoir que nous sommes probablement sur la bonne voir comme les équations ne se contredisent pas l’une et l’autre :

  • 20ss-26s+6 = 0

Ici nous devons utiliser la terrifiante Formule Quadratique. En multipliant tout, nous trouvons que s=(26+/-14)/40… c’est-à-dire, s=100% or s=30%. Est-ce que sont toutes deux des solutions valides ? Pour y répondre, nous évaluons p=1-2s et n’importe quelle autre équation avec r.

Pour s=30%, nous trouvons p=40% et r=30%, et c’est une solution valide. Pour s=100%, nous obtenons p=-100% et r=100%, ce qui est invalide (p ne peut être inférieur à zéro), ce qui nous laisse uniquement avec une seule solution valide : r:p:s = 3:4:3.

Il apparaît qu’avoir plusieurs joueurs a un effet sur le problème de « victoire avec Pierre compte double », mais cela pourrait ne pas être le résultat attendu ; avec trois joueurs, c’est de fait plus près de 1:1:1 que ce n’était avec deux joueurs ! Peut-être c’est parce que la probabilité d’égalité avec un qui joue Pierre, un qui joue Papier et un qui joue Ciseaux rend Ciseaux moins risqué que cela ne serait le cas dans un jeu à deux joueurs, parce que même si un adversaire choisi Pierre, l’autre pourrait choisir Papier et transformer notre double perte en égalité.

Résumé

Cette semaine nous avons vu comment évaluer les mécaniques intransitives en utilisant les maths. C’est probablement la chose la plus compliquée que nous avons faite, car cela rassemble les courbes de coût des mécaniques transitives, les probabilités et les statistiques et c’est pourquoi je fais cela à la toute fin du cours seulement après les avoir couverts ! Pour résoudre ces mécaniques, vous suivez ce processus :

  • Faites un tableau des gains.
  • Éliminez tous les choix dominés pour les deux joueurs (en comparant toutes les combinaisons de lignes et de colonnes et en voyant si n’importe quelle paire contient une ligne ou une colonne qui est strictement supérieure ou égale à une autre). Continuez à faire cela jusqu’à ce que tous les choix restants soient viables.
  • Trouvez toutes les « boucles » intransitives en cherchant la meilleure réponse au choix initial de chaque joueur.
  • Calculez les gains de chaque choix pour un des joueurs, en faisant en sorte que les gains soient égaux à la même variable X. Dans un jeu à somme nulle, X pour un joueur sera l’inverse du X de l’autre joueur. Dans un jeu symétrique, X vaut zéro, alors mettez simplement tous les gains à zéro à la place.
  • Ajoutez une équation de plus, que la somme des probabilités de tous les choix font 1.
  • Utilisez la substitution algébrique, les matrices de forme triangulaire, Excel, ou n’importe quel autre moyen que vous avez à votre disposition, résolvez pour autant de variables que vous pouvez. Si vous arrivez à connaître la valeur de X, cela vous dit le gain (ou la perte) attendu pour ce joueur. Faire la somme de toutes les valeurs X des joueurs vous dit si le jeu est à somme nulle (X1+X2+…=0), à somme positive (>0) ou à somme négative (<0), et à hauteur de combien.
  • Si vous pouvez trouver une valeur unique pour chaque choix qui est entre 0 et 1, celles-ci sont les probabilités optimales avec lesquelles vous devriez choisir chaque coup. Pour les jeux asymétriques, vous aurez besoin de faire cela individuellement pour chaque joueur. C’est votre solution.
  • Pour les jeux avec plus de deux joueurs qui font chacun des choix simultanés, choisissez les gains d’un joueur comme votre point de référence, et traitez tous les autres joueurs comme un seul adversaire combiné. Les maths deviennent plus difficiles ici pour chaque joueur que vous ajoutez au delà de deux. Après tout, avec deux joueurs toutes les équations sont strictement linéaires ; avec trois joueurs vous devez résoudre des équations quadratiques, avec quatre joueurs vous avez des équations cubiques, avec cinq joueurs vous verrez des équations quartiques, et ainsi de suite.

Je devrai aussi pointer que le domaine de la théorie des jeux est très large, et couvre une grande variété d’autres jeux que nous n’avons pas couverts ici. En particulier, il est aussi possible d’analyser des jeux où les joueurs choisissent séquentiellement plutôt que simultanément, et aussi les jeux où les joueurs peuvent négocier par avance, en faisant appel ou en proférant des menaces, et en coordonnant leurs mouvements et ainsi de suite (comme cela pourrait être trouvé dans les jeux à somme positive où deux joueurs peuvent commercer ou sinon coopérer pour dépasser leurs adversaires). Ces jeux sont au delà de la portée de ce cours, mais si vous êtes intéressés, je vous donnerai une série de références à la fin.

Si vous travaillez sur un jeu en ce moment…

Réfléchissez à votre jeu et voyez s’il comporte n’importe quelle mécanique intransitive. Sinon, demandez-vous s’il y aurait des opportunités ou raisons de prendre certaines mécaniques transitives et les convertir en intransitives (par exemple, si vous travaillez sur un JdR, peut-être qu’avoir juste une séquence d’armes où chacune est meilleure que la précédente, il y a éventuellement une opportunité à un certain stade dans le jeu d’offrir au joueur un choix de différentes armes qui sont toutes bonnes dans l’ensemble, mais chacune est meilleure qu’une autre dans différentes situations).

Si vous avez des mécaniques intransitives dans votre jeu, trouvez celle qui est la plus proéminente, et analysez-la comme nous l’avons fait aujourd’hui. De tous les choix que vous offrez au joueur, est-ce qu’il y a l’un d’entre eux qui soit un choix dominant ou dominé ? Quel est le ratio attendu sur la fréquence à laquelle le joueur devrait choisir chacune de ces options disponibles, en partant de l’hypothèse d’un jeu optimal ? Est-ce que c’est ce à quoi vous vous attendez ? Est-ce c’est ce que vous voulez ?

Travail à la maison

En guise de pratique, vous pouvez commencer à faire les calculs à la main pour confirmer tous les problèmes que j’ai résolus aujourd’hui, pour commencer à avoir une bonne prise en main. Une fois que vous êtes à l’aise, voici un jeu dérivé d’un mini-jeu que j’ai vu une fois dans une des séries de JdR Suikoden (j’ai oublié laquelle). Le jeu utilisait 13 cartes, mais pour simplifier je vais seulement utiliser un pâquet de 5 cartes pour ce problème. Voici les règles :

  • Joueurs : 2
  • Mise en place : Chaque joueur prend 5 cartes, numérotées de 1 à 5. Un troisième paquet de cartes numérotées de 1 à 5 est mélangé et placé face cachée comme pioche.
  • Déroulement de la partie : Au début de chaque tout, une carte de la pioche est retournée face visible ; le tour vaut le nombre de points égal à la valeur de la carte. Les deux joueurs choisissent ensuite leur propre carte, et jouent simultanément. Le joueur qui a joué la carte la plus haute obtient les points pour ce tour ; en cas d’égalité, personne n’obtient de points. Les deux joueurs mettent de côté les cartes qu’ils ont décidé de jouer à ce tour ; ces cartes ne peuvent plus être utilisées à nouveau.
  • Fin de partie : Le jeu se termine après les cinq tours ont été joués, ou après qu’un joueur atteint 8 points. Celui qui a le plus de points gagne la partie.

Il est facile de voir qu’il n’existe pas de stratégie dominante. Si l’adversaire joue complètement au hasard (20% de chance de jouer chaque carte), vous finissez loin devant si vous jouez simplement le nombre dans votre main qui correspond aux points que vaut chaque tour (ainsi vous jouez votre 3 si un 3 est retourné, jouez votre 4 sur un 4, etc). Vous pouvez démontrer cela dans Excel en mélangeant la main de l’adversaire de manière à ce qu’ils jouent aléatoirement, et en comparant cette stratégie avec la stratégie de « correspondance des points » que j’ai décrite ici, et vous verrez rapidement que la correspondance de points gagne un grand nombre de fois. (Vous pourriez aussi calculer toutes les chances de cela, car il n’y a que 120 façons d’arranger 5 cartes, si vous le vouliez).

Est-ce que cela signifie que la « correspondance de points » est la stratégie dominante ? Certainement pas. Si je sais que mon adversaire joue cette stratégie, je peux l’écraser en jouant une carte plus forte que faire la correspondance sur toutes les cartes, et finir par jouer mais ma carte 1 sur le tour à 5 points. Je perdrai 5 points, mais je capturerai les autres 10 points pour la victoire. Est-ce que la stratégie « un plus haut » domine ? Non, car « deux plus haut » battra « un plus haut »… et « trois plus haut » battra « deux plus haut », et « quatre plus haut » battra « trois plus haut » et « correspondance de points » battra « quatre plus haut » – une relation intransitive. Ainsi, le but de ce jeu est de deviner ce que votre adversaire jouera, et ensuite jouer « un plus haut » que cela (ou si vous pensez que votre adversaire joue son 5, jouer votre 1 dessus).

Comme chaque stratégie est aussi bonne qu’une autre si choisie parmi les 5 présentées, vous pourriez penser que cela signifie que vous ne pouvez pas faire pire que choisir une de ces stratégies au hasard… excepté que comme nous l’avons vu, si vous jouez aléatoirement « correspondance de points » vous bat ! Alors il est probablement vrai que la stratégie optimale n’est pas 1:1:1:1:1, mais plutôt un autre ration. Déterminons ce que c’est.

Si vous n’êtes pas sûr de par où commencer, voyez cela comme ça : pour n’importe quelle partie il n’y a que 5 stratégies : correspondance, un de plus, deux de plus, trois de plus ou quatre de plus. Déterminez la table de gain pour suivre chaque stratégie sur les cinq cartes. Vous pouvez changer de stratégie d’un tour à un autre, comme pierre-ciseaux-papier, mais sans autre information sur le premier tour vous n’avez que cinq choix, et chacun de ces choix peut vous aider ou vous faire du mal selon ce que joue votre adversaire. Ainsi, pour la première partie au moins vous partiriez avec cette table de gains (après tout, pour le premier tout, il n’y a que cinq stratégies que vous pouvez suivre, vous n’avez que cinq cartes chacun) :


matchingmatch+1match+2match+3match+4
M0-53913
M+150-7-13
M+2-370-9-10
M+3-9190-11
M+4-13-310110

Références

Voici deux références que j’ai trouvé utiles lorsque j’ai constitué la présentation d’aujourd’hui.

« Game Architecture and Design » (Rollings & Morris), Chapitres 3 et 5. C’est là où j’ai trouvé l’idée d’utiliser les systèmes d’équations pour résoudre les jeux intransitifs. J’avais essayé de pousser les choses un petit peu plus loin aujourd’hui que ce que les auteurs avaient fait dans ce livre, mais bien entendu, cela signifie que le livre est un peu plus simple est probablement plus accessible que ce que j’ai fais ici. Et il y a, vous savez, tout le reste du livre qui s’intéresse à plein d’autres sujets. Je suis en train de le lire et alors je ne peux pas vous donner le cachet d’approbation personnelle à ce stade, mais je ne peux pas en dire de mal non plus, alors jetez un œil et faites-vous un avis par vous-même.

« Game Theory: a Critical Text » (Heap & Varoufakis). J’ai trouvé que c’était utile et une assez accessible à la Théorie des Jeux. Mon seul avertissement serait que dans l’intérêt de la concision, les auteurs ont tendance à définir des acronymes puis les utiliser avec généreusement dans le reste du texte. Cela fait qu’il est parfois difficile de sauter des passages, car vous pourriez aussi sauter quelques définitions clefs, et ensuite rencontrer des phrases qui ont plus d’acronymes inconnus que de mots !

~ ~ ~ ~ ~ ~ ~

Article précédent : Niveau 8 – Statistiques et métriques

Article suivant : Niveau 10 – Boss de fin