David Madore's WebLog: Comment faire un jeu de cartes à partir d'un quadrangle généralisé

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]

↓Entry #2308 [older| permalink|newer] / ↓Entrée #2308 [précédente| permalien|suivante] ↓

(mercredi)

Comment faire un jeu de cartes à partir d'un quadrangle généralisé

L'entrée précédente m'a donné envie de concevoir des jeux de cartes avec des structures combinatoires mathématiques remarquables. Je vais déjà en tirer un avec une structure liée à celle des 27 droites sur une surface cubique (à savoir, l'ensemble des 36 double six de telles droites)[#], mais ce serait plutôt pour faire de la cartomancie oulipienne. Je me demandais ce que je pourrais inventer de plus jouable. Et d'un autre côté, parmi les structures combinatoires que j'avais vaguement à l'esprit, il y avait (je les ai mentionnées dans l'entrée précédente, et je vais dire ci-dessous de quoi il s'agit) les quadrangles généralisés.

((Ceux de mes lecteurs qui ne sont pas intéressés par les aspects mathématiques peuvent directement sauter au dessin des cartes ci-dessous, après quoi je pose quelques questions de design, si j'ose dire.))

Pour essayer d'imaginer quelque chose de jouable, j'ai médité sur la structure d'un jeu ordinaire de 52 cartes. Tout le monde sait qu'il s'agit des 13×4 cartes constituant chacune des combinaisons, des couples si on veut, entre un symbole de {A,2,3,4,5,6,7,8,9,X,V,D,R} (la « valeur » de la carte) et un symbole de {♣,♢,♡,♠} (la « couleur » de la carte, le terme français était d'ailleurs épouvantablement ambigu parce qu'il recouvre à la fois ce que les Anglais appellent suit, c'est-à-dire le symbole que je viens de dire, et ce que les Anglais appellent colour, c'est-à-dire noir pour ♣,♠ ou rouge pour ♢,♡ — mais passons). Mathématiquement, on a donc affaire au produit cartésien {A,2,3,4,5,6,7,8,9,X,V,D,R} × {♣,♢,♡,♠}, qui n'est pas une structure combinatoire très intéressante. Si on considère les cartes comme des points et les symboles comme des droites (verticales ou horizontales : voir le dessin ci-dessous), on a affaire à une simple grille. Maintenant, voici quelques propriétés de cette « géométrie », qui peuvent paraître bizarrement compliquées, mais dont on va voir le sens à les énoncer ainsi :

A 2 3 4 5 6 7 8 9 X V D R
  1. Sur chaque carte figurent exactement 2 symboles (distincts) [à savoir, l'indication de sa valeur et l'indication de sa couleur].
  2. Chaque symbole figure sur exactement 4 ou 13 cartes (distinctes) [4 dans le cas d'une valeur, 13 dans le cas d'une couleur].
  3. Deux cartes ayant deux symboles en commun coïncident [il n'y a pas de cartes différentes ayant la même valeur et la même couleur]. Diverses reformulations équivalentes : deux cartes distinctes ont au plus un symbole en commun ; deux symboles distincts figurent sur au plus une carte ; deux symboles figurant tous les deux sur deux cartes distinctes coïncident.
  4. Si C est une carte et σ est un symbole qui ne figure pas sur C, alors il existe exactement une carte D et un symbole τ tels que σ figure sur D et τ figure à la fois sur C et sur D. [Explication ci-dessous.]

La propriété (4) peut sembler bizarre, mais concrètement, elle signifie simplement que si C est une carte et σ est soit une valeur différente soit une couleur différente de celle de C, alors il existe une carte D qui a cette valeur ou couleur et qui pour l'autre symbole (couleur ou valeur respectivement) τ a la même que celle de C.

Cette dernière propriété, d'ailleurs, est en quelque sorte celle utilisée dans un nombre essentiellement infini de jeux de cartes (par exemple le jeu commercial Uno, le « huit américain » ou « maou maou », le « Tschau Sepp » suisse, etc.) qui sont des variantes mineures autour du principe suivant : chaque joueur a des cartes dans sa main dont il doit se débarrasser, ils jouent tour à tour et chacun peut poser une carte ayant un symbole commun avec la carte précédemment jouée (c'est-à-dire concrètement : ayant la même valeur ou la même couleur — le plus souvent la même couleur, bien sûr, puisqu'il y a plus de telles cartes). La propriété signifie alors que si la carte C a été jouée et que je veux passer le jeu à σ qui n'est pas actuellement jouable (i.e., changer la valeur ou la couleur), il y a une unique carte jouable D qui permettra de faire ce changement.

Si j'ai écrit les propriétés sous la forme bizarre ci-dessus, c'est pour pouvoir amener la définition d'un quadrangle généralisé, ou plus exactement, un quadrangle généralisé fini de paramètres (s,t) (deux entiers), définition que je vais formuler ici avec des cartes et des symboles (mais les termes classiques seraient points et droites, sachant que la définition est symétrique entre les deux, à permutation près des paramètres s et t ; je fais ici la convention que les cartes sont les points et les symboles les droites, mais le contraire irait tout aussi bien) :

  1. Sur chaque carte figurent exactement t+1 symboles (distincts).
  2. Chaque symbole figure sur exactement s+1 cartes (distinctes).
  3. Deux cartes ayant deux symboles en commun coïncident. Diverses reformulations équivalentes : une carte est complètement déterminée par la donnée de deux quelconques de ses symboles ; deux cartes distinctes ont au plus un symbole en commun ; deux symboles distincts figurent sur au plus une carte ; deux symboles figurant tous les deux sur deux cartes distinctes coïncident ; un symbole est complètement déterminé par la donnée de deux cartes sur lequel il figure.
  4. C σ D τ Si C est une carte et σ est un symbole qui ne figure pas sur C, alors il existe exactement une carte D et un symbole τ tels que σ figure sur D et τ figure à la fois sur C et sur D. (Cf. dessin ci-contre.)

Les propriétés (3)&(4) sont donc exactement les mêmes que ce que j'ai énoncé pour un jeu de cartes usuelles. La (1) est une généralisation de ce qu'elle était ci-dessus pour autoriser plus que 2 symboles par carte (par contre, on notera bien que la troisième propriété continue à parler de deux symboles : une carte est complètement déterminée par deux quelconques de ses symboles). La propriété (2), en revanche, diffère de ce qu'on avait pour un jeu de cartes ordinaires, en ce sens que chaque symbole figure maintenant sur le même nombre de cartes, au lieu qu'il y ait des types de symboles figurant sur un nombre plus ou moins grand de cartes.

Dans la propriété (4), on dit parfois que τ est le perpendiculaire de σ à travers C : cette terminologie a l'avantage de bien faire ressortir l'unicité, et elle est raisonnable quand on pense à l'exemple d'une grille (par exemple, le perpendiculaire à ♠ passant par 8♡ est 8 : c'est bien le cas sur le dessin de la grille que j'ai fait plus haut). Néanmoins, cette terminologie suggère une notion métrique (des angles), qui n'existent pas ici : on demande simplement une condition d'incidence entre σ et τ (à savoir, qu'ils figurent sur la carte D). D'autre part, comme cartes et symboles jouent des rôles totalement symétriques dans les propriétés (j'ai fait mes dessins avec les cartes pour points et les symboles pour droites, mais je pouvais faire le contraire), on pourrait tout aussi bien dire que D est la perpendiculaire de C à travers σ (et pour le coup, dans le cas d'une grille, c'est beaucoup moins intuitif : la perpendiculaire à 8♡ par ♠ est 8♠). Passons.

Une conséquence facile mais importante de ces propriétés (plus exactement, des propriétés (3)&(4)) est l'inexistence de triangles : il n'est pas possible que trois cartes distinctes aient deux à deux un symbole en commun sauf si ces trois symboles sont tous le même (ce qui contraste donc totalement avec les plans projectifs finis dont j'ai parlé dans l'entrée précédente où deux cartes quelconques ont un symbole en commun). Pour le cas d'un jeu ordinaire de 52 cartes, c'est complètement évident ; dans le cas général on peut raisonner comme ceci : si C, D₁ et D₂ sont trois cartes censées avoir deux à deux un symbole en commun mais non commun aux trois, soit σ le symbole commun supposé exister entre D₁ et D₂, il n'apparaît pas sur C (sinon les trois cartes auraient un unique symbole commun, contrairement à l'hypothèse), et d'après la propriété (4) des quadrangles généralisés, il doit exister une unique carte D ayant le symbole σ ainsi qu'un symbole en commun avec C — mais D₁ et D₂ vérifient cette propriété, d'où une contradiction.

Je ne vais pas essayer d'expliquer ce qu'on sait sur la classification des quadrangles généralisés, parce que je n'y connais pas grand-chose (pour moi, tout le sujet ressemble à un labyrinthe de petits théorèmes tordus tous semblables) et que je me planterais à coup sûr si j'essayais. Pour en savoir plus, on pourra par exemple consulter le livre de van Maldeghem, Generalized Polygons, ou plus spécifiquement celui de Payne & Thas, Finite Generalized Quadrangles, ou encore celui de Shult, Points and Lines. Personnellement, je trouve ça passablement illisible.

Disons juste qu'il existe quelques constructions « classiques », dont je n'évoquerai que la suivante. Si F est un corps fini ayant q éléments (où q est nécessairement une puissance d'un nombre premier ; par exemple, si q est premier, F peut être le corps ℤ/qℤ des entiers modulo q), on appelle quadrique projective de dimension 3 sur F l'ensemble des solutions (X₀:X₁:X₂:X₃:X₄) de l'équation X₀·X₁ + X₂·X₃ + X₄² = 0, où les ‘:’ entre les coordonnées X signifient qu'on demande que ces coordonnées ne soient pas toutes simultanément nulles et que de plus on identifie deux solutions proportionnelles (c'est-à-dire qui se déduisent l'une de l'autre par multiplication par un élément non nul de F) ; chacune de ces solutions s'appelle un point de la quadrique. (À titre d'exemple, si F = ℤ/3ℤ, (1:0:0:0:0)=(2:0:0:0:0) est un point de la quadrique car 1×0 + 0×0 + 0² = 0, (1:2:0:0:1)=(2:1:0:0:2) en est un autre, car 1×2 + 0×0 + 1² = 0 modulo 3, et (1:2:0:0:2) en est encore un autre.) Si on a deux solutions (X₀:X₁:X₂:X₃:X₄) et (Y₀:Y₁:Y₂:Y₃:Y₄) dont toute combinaison linéaire (à coefficients dans F) est encore solution (ce qui revient au même que de dire qu'en plus de X₀·X₁ + X₂·X₃ + X₄² = 0 et Y₀·Y₁ + Y₂·Y₃ + Y₄² = 0 on a aussi X₀·Y₁ + Y₀·X₁ + X₂·Y₃ + Y₂·X₃ + 2X₄·Y₄ = 0), on dit que l'ensemble de ces combinaisons linéaires est une droite sur la quadrique. (À titre d'exemple, la droite passant par (1:0:0:0:0) et (0:0:1:0:0), c'est-à-dire l'ensemble des (u:0:v:0:0), est une droite sur la quadrique car u×0 + v×0 + 0² = 0 quels que soient u et v.) Ces définitions fonctionnent sur n'importe quel corps (si ce n'est que mon choix d'équation de quadrique serait assez arbitraire sur un corps quelconque, alors que sur un corps fini elles reviennent toutes au même), mais sur un corps fini F à q éléments, on peut montrer qu'il y a q³ + q² + q + 1 = (q²+1)(q+1) points sur la quadrique, et exactement autant de droites, que chaque point est sur q+1 droites, que chaque droite contient q+1 droites, et que tout ça forme un quadrangle généralisé de paramètres (q,q). En fait, on obtient deux quadrangles généralisés différents : pour l'un, ce que j'ai appelé cartes seront les points de la quadrique et les symboles figurant sur la carte seront les droites passant par le point, alors que pour l'autre, ce sera le contraire, on mettra un symbole par point de la quadrique et une carte sera formée par une droite de la quadrique et étiquetée par les points sur celle-ci ; de façon peut-être surprenante, bien qu'ils aient les mêmes paramètres, ces deux quadrangles généralisés ne sont pas le même (sauf si q est pair, c'est-à-dire en fait, est une puissance de 2) : ceci est en contraste au cas des plans projectifs où le dual d'un plan projectif (c'est-à-dire l'échange des points et des droites) donne bien la même structure combinatoire.

Si je prends le cas particulier q=3, la construction ci-dessus définit un quadrangle généralisé de paramètres (3,3), qui a 40 cartes et 40 symboles (et en fait, à dualité près, c'est le seul). En voici[#2] une représentation possible (du moins pour les gens dont le navigateur sait afficher le SVG) :

[Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Carte à quatre symboles] [Dos des cartes]

Voici donc un jeu de 40 cartes (le dernier dessin de la liste est, bien sûr, le dos), chacune comportant 4 symboles parmi 40, chaque symbole apparaissant sur exactement 4 cartes, deux cartes distinctes ayant au plus un symbole en commun, et de sorte que si on se donne une carte C et un symbole σ qui n'est pas dessus, il y a une unique carte D qui comporte à la fois le symbole σ et un symbole τ en commun avec C. (À titre d'exemple, comme la première carte a les symboles 1234, n'importe quel autre symbole apparaît sur une unique carte avec l'un de ces chiffres.)

À quels jeux pourrait-on jouer avec un tel paquet de cartes ? Cela fait partie du problème. Un point de départ pourrait être, comme je le suggère plus haut, les variantes du jeu de défausse (« huit américain ») : chaque joueur essaie de se débarrasser de ses cartes et peut poser une carte à condition qu'elle ait un symbole en commun avec la carte précédemment jouée. (Notons que chaque carte a un symbole en commun avec exactement 12 des 39 autres : la proportion des cartes jouables est donc toujours de 31%, ce qui est très proche des 29% dans le cas d'un jeu de 52 cartes où on doit suivre avec la même valeur ou la même couleur.) Une autre possibilité serait de faire un jeu de poker : dans ce cas, deux des figures évidentes à atteindre avec quatre cartes seraient la droite (quatre cartes ayant un symbole en commun à toutes : il y en a 40 possibles, donc c'est une figure rare), ou le quadrangle (quatre cartes qui ont chacune un symbole commun avec la suivante cycliquement ; il y a 1620 quadrangles possibles ; comme je l'ai signalé plus haut, il n'existe pas de triangle : si trois cartes ont un symbole commun deux à deux, ce symbole est forcément le même pour les trois, et il s'agit d'une droite incomplète). On peut aussi certainement imaginer toutes sortes de solitaires/réussites. (Évidemment, il est plus facile de concevoir des jeux si on s'autorise à donner un sens particulier à tel ou tel symbole, c'est-à-dire à rompre la symétrie du paquet de cartes, mais ceci va à l'encontre de l'élégance de la structure mathématique représentée. Néanmoins, pour un jeu de poker, il faudra bien trouver un moyen soit de départager les mains de même forme, soit de décider ce qu'on fait quand ça se produit.)

Une autre question est de savoir quels symboles utiliser sur les cartes. Pour ça, j'ai eu à me bagarrer avec deux contraintes : la contrainte de mon sens de l'esthétique toujours difficile à satisfaire, et la contrainte pratique de trouver des symboles alors que le summum de mes talents en dessin informatique ne me permet même pas de faire un smiley. J'ai remarqué qu'il y a une symétrie de la structure qui opère par 10 cycles de longueur 4, c'est-à-dire que je peux diviser mes 40 symboles en 10 blocs[#3] de 4, chacun muni d'un ordre cyclique, de façon que si on remplace chaque symbole par le suivant cycliquement dans le bloc, chaque carte est transformée en une autre carte (éventuellement la même). J'ai donc cherché 10 quatuors de symboles qui présentent au moins un semblant de cycle : quatre couleurs dans le cycle des couleurs, les quatre « couleurs » d'un jeu de cartes traditionnel (mais l'ordre cyclique n'est vraiment pas clair), quatre phases de la lune, quatre saisons représentées par leurs signes astrologiques, et franchement, j'ai manqué un peu d'imagination, alors j'ai vaguement déniché quatre animaux chinois, et pour le reste j'ai pris quatre chiffres, quatre lettres latines majuscules, quatre lettres grecques minuscules, quatre sortes d'étoiles/astérisques, et enfin quatre symboles qui ne me semblaient pas trop moches (caducée, couronne, gemme et tête de mort — trouvez la symbolique que vous voudrez).

Si vous avez de meilleures suggestions, elles sont les bienvenues, mais ce n'est pas évident : j'ai besoin de dessins vectoriels, et le mieux que j'aie trouvé pour ça, à part pour juste faire des disques de couleur, est encore d'aller chercher dans les symboles Unicode de polices raisonnablement bien faites (notamment la police Symbola de George Douros, et la police DejaVu Sans). Je suis conscient qu'il y a plein de problèmes, mais les contraintes sont difficiles. Par exemple, c'est triste que tout soit en noir et blanc — d'un autre côté, je ne vois pas comment faire de la couleur sans briser des symétries : j'aurais pu mettre le cœur et le carreau en rouge, mais ça me semble mauvais car ça leur donnerait un rôle apparemment spécial. Je sais aussi bien que les phases de la lune ne sont pas évidentes à distinguer, que certains dessins ont des traits trop fins ou trop épais, mais je n'ai pas mieux sous la main. Comme en plus quatre de mes dix groupes de 4 symboles sont une carte à eux tout seuls (en l'occurrence, les chiffres, les lettres latines majuscules, les lettres latines minuscules, et les sortes d'astérisques), il fallait que ces symboles soient relativement « neutres » pour que la présence de quatre d'entre eux sur une carte ne détonne pas trop. On m'a suggéré d'aller fouiller dans openclipart, mais c'est un tel capharnaüm que je n'y trouve rien du tout. J'ai aussi vaguement regardé les hiéroglyphes (j'ai une police hiéroglyphique assez complète), et les idéogrammes chinois, mais je n'en ai pas trouvé qui me plaisent vraiment.

(Je précise par ailleurs que le cadre aux bords arrondis que j'ai mis autour de chaque carte ne serait pas destiné à être imprimé au final, sauf pour le dos commun. J'envisage des cartes de 63.5mm×88.9mm, et la limite extérieure de ce bord dessiné correspond à la tolérance intérieure extrême sur la découpe.)

L'étape suivante, ce sera de faire un jeu de cartes à partir d'un hexagone généralisé (plus exactement, l'hexagone « déployé de Cayley », qui a un rapport étroit avec les octonions et qui donne 63 cartes avec chacune 3 symboles parmi 63 ; un des très rares dessins qu'on en trouve en ligne est ici), mais ce sera certainement encore plus difficile de trouver des jeux à faire avec ça.

[#] De façon surprenante (je ne m'en suis rendu compte qu'a posteriori), le groupe des symétries de la structure des 27 droites sur la surface cubique, donc le groupe de symétries de mon premier jeu avec 36 cartes, est le même que le groupe projectif orthogonal de dimension 5 sur le corps à 3 éléments, donc celui avec 40 cartes que je présente dans cette entrée. Pour plus de précisions, voir page [26] de l'ATLAS des groupes finis.

[#2] Bon, à vrai dire, je ne suis pas complètement sûr si c'est la construction expliquée ci-dessus ou son dual. Je crois que les cartes sont les points de la quadrique et que les symboles sont les droites dessus, mais c'est peut-être l'inverse — parce que la manière dont j'ai fait les choses, c'est de prendre le programme Gap, considérer le groupe de symétries que je voulais, lister ses sous-groupes maximaux à conjugaison près, et choisir l'une des deux classes d'indice 40 qui me semblait la plus satisfaisante pour des raisons esthétiques, et ce n'est qu'après coup que j'ai cherché à identifier à quel quadrangle j'avais affaire.

[#3] Les dix blocs ne jouent eux-mêmes pas tous le même rôle : quatre d'entre eux apparaissent en bloc sur une carte (en l'occurrence, les chiffres, les lettres latines majuscules, les lettres latines minuscules, et les sortes d'astérisques), les six autres non. Toutes les combinaisons entre disque-de-couleur et couleur-de-carte sont réalisées (bien sûr de façon unique), ainsi que toutes les combinaisons entre phase de la lune et symbole astrologique de saison, ou encore entre caducée-couronne-gemme-tête-de-mort et animal. En fait, techniquement, le stabilisateur (dans le groupe de toutes les symétries du quadrangle) de mon système de 10 blocs de 4 est un produit direct entre un groupe diédral du carré et un groupe symétrique sur 4 objets.

↑Entry #2308 [older| permalink|newer] / ↑Entrée #2308 [précédente| permalien|suivante] ↑

[Index of all entries / Index de toutes les entréesLatest entries / Dernières entréesXML (RSS 1.0) • Recent comments / Commentaires récents]