Attribuer un numéro a chaque situation

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Romain672
Membre Naturel
Messages: 10
Enregistré le: 02 Aoû 2021, 12:24

Attribuer un numéro a chaque situation

par Romain672 » 02 Aoû 2021, 13:15

Bonjour,
C'est a propos du jeu 'Yokai'.
Vous avez un sachet avec 4 boules jaunes, 4 boules vertes, 4 boules rouges, et 4 boules bleus.

Je vais appeler X la première couleur de boule que vous piochez. Y la seconde, Z la troisième, W la quatrième.
De même, je vais appeler A la première couleur de boule que votre coéquipier pioche. B la seconde, C la troisième, D la quatrième.

Vous en piochez deux que vous êtes seul a voir. Donc vous avez pioché XX ou XY.
Votre coéquipier fait de même. Donc la situation sera XXAA, XXAB, XYAA, ou XYAB.
Vous faites de même. Donc la situation sera XXAAXX, XXAAXY, XXAAYX, XXAAYY, XXAAYZ, XYAAXX, XYAAXY, XYAAXZ, XYAAYX, XYAAYY, XYAAYZ, XYAAZX, XYAAZY, XYAAZZ, XYAAZW, XXABXX, XXABXY, XXABYX, XXABYY, XXABYZ, XYABXX, XYABXY, XYABXZ, XYABYX, XYABYY, XYABYZ, XYABZX, XYABZY, XYABZZ, ou XYABZW.
[...]
(donc tirage sans remise)

Je souhaiterais attribuer un 'numéro de situation' a chaque possibilité. C'est a dire que j'aimerais que XYAAXZBB ait son propre numéro qui soit différent de tout les autres (et si possible relativement faible mais c'est secondaire), même de ceux qui sont plus court que lui. Et je veux que XYAAX soit différent de XXAAY.

(je suis bon en anglais dans le cas où vous auriez des liens)


Donc par exemple, ma première idée, était de donner des valeurs a chaque couleur: X=2, A=3, Y=5, B=7, Z=11, C=13, W=17, D=19. Puis de le multiplier par le numéro de la pioche du joueur-1.
Le problème XXAAX=2*0+2*1+3*0+3*1+2*2=9. Et XXAB=2*0+2*1+3*0+7*1=9 aussi.
Donc ce n'est pas ce que je veux vu que deux suites de lettres sont associés au même numéro.

De la même façon si a la place de multiplier par le numéro de la pioche du joueur, je multiplie par le (Xth nombre premier où X est le nombre de pioche de ce joueur)(donc a la place de 1/2/3/4/5, c'est 2/3/5/7/11 aussi).
J'obtiens tout simplement XXAA=2*2+2*3+3*2+3*3=25 & XYA=2*2+5*3+3*2=25.
Donc ça ne marche pas non plus.

Il semblerait qu'il faille multiplier cette liste des nombres premiers par une autre liste. Mais j'ai aucune idée de comment la construire (sans prendre des nombres genre 2/3/5/7 milliards, ce qui réglerais le problème je pense :D).
Merci :)



lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Attribuer un numéro a chaque situation

par lyceen95 » 02 Aoû 2021, 16:24

Quand tu multiplies, tu perds l'unicité : a*b=b*a ... la multiplication permet à peu près de savoir les nombres apparus (si tu prends des nombres premiers), mais aucune notion d'ordre.
Dans notre système de numération, on n'a pas d'ambiguité : 1234 ou 4321, il y a les 4 mêmes chiffres, mais ce sont bien des nombres différents.
Tu peux reproduire la même logique. 1230, c'est 0 unités + 3 dizaines + 2 centaines + 1 millier.
Ou encore , si je note b la base ( b=10 en général, mais ce n'est pas une obligation) 1230, c'est
Tu peux donc dire :
Chaque couleur porte un n° entre 0 et 3 (commence à 0...)
Donc la base est 4
0=bleu
1=Blanc
2=Rouge
3=Noir

, c'est 108 (et la seule façon d'obtenir 108, c'est 1230) , et c'est Blanc puis Rouge puis Noir puis Bleu

Romain672
Membre Naturel
Messages: 10
Enregistré le: 02 Aoû 2021, 12:24

Re: Attribuer un numéro a chaque situation

par Romain672 » 02 Aoû 2021, 17:42

Ok merci, j'y vois beaucoup plus clair :P

1) bleu+bleu (0) est la même que bleu (0). Je suppose que pour corriger ça faut ajouter 1 a la base.

2) les couleurs sont différentes selon les joueurs. Je peux remplacer bleu/blanc/rouge/noir par première/second/troisième/quatrième couleur vu.
Et du coup ça marche pour les deux joueurs (vu qu'on sait quand est ce qu'ils jouent). Même si les couleurs qu'ils voient sont différentes, ils peuvent voir qu'un maximum de 4 couleurs.
Du coup premier/premier/premier/deuxième/deuxième/deuxième donnerait du (base 5): 1+1*5+2*5^2+2*5^3+2*5^4+2*5^5=7806.

3) J'espérais pouvoir simplifier cette règle un peu (vu que la plupart des résultats sont impossibles, vu que les couleurs sont piochés dans l'ordre).
Du coup je pourrais enlever la première et la troisième pioche.
Ce qui fait que premier/premier/premier/deuxième/deuxième/deuxième, serait simplifié en premier/deuxième/deuxième/deuxième et donnerait du (base 5): 1+2*5+2*5^2+2*5^3=311.
Pour simplifier plus, la seconde et quatrième couleur auraient deux possibilités et je pourrais arbitrairement décider que pp (premier/premier) obtient le score 1. pd 2. dp 3. Et dd 4.
Ce qui fait que premier/premier/premier/deuxième/deuxième/deuxième, obtiendrait le score 'pd' associé a 2, et serait simplifié en deuxième/deuxième et donnerait du (base 5): 2+2*5+2*5^2=62.
Du coup, je perds l'option de différencier les quatre premières pioches, mais ce n'est pas si important (je pourrais leur donne arbitrairement des valeurs négatives même). Par contre différencier pppddd avec pppdddp est important pour moi vu que ça arrive tard.

J'ai beaucoup écris tout seul ici, mais si il y a une optimisation que j'ai oublié (genre pour augmenter la base) ou si j'ai fais une erreur quelque part, hésitez pas a me le dire :)

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Attribuer un numéro a chaque situation

par lyceen95 » 02 Aoû 2021, 21:31

Je n'ai pas tout suivi.
Je reste donc sur mon message précédent, et le point que tu as soulevé. Je partais du principe qu'on devait coder des tirages de longueur fixe. Comme ce n'est pas le cas, effectivement, tous les 0 de début de chaine sont 'indétectables'. On ne sait pas différencier 0001 de 001 ou 01 ou 1. Une solution pas trop coûteuse pour éviter ça, c'est de numéroter les couleurs de 1 à 4, et non de 0 à 3 comme je le disais .

Donc Bleu blanc Rouge Noir s'écrirait et non pas
Et donc compter ne base 5.

Romain672
Membre Naturel
Messages: 10
Enregistré le: 02 Aoû 2021, 12:24

Re: Attribuer un numéro a chaque situation

par Romain672 » 03 Aoû 2021, 07:20

Ok, merci en tout cas :)

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Attribuer un numéro a chaque situation

par fatal_error » 03 Aoû 2021, 08:16

hello,

quel est le but d'avoir des numéros?
la vie est une fête :)

Romain672
Membre Naturel
Messages: 10
Enregistré le: 02 Aoû 2021, 12:24

Re: Attribuer un numéro a chaque situation

par Romain672 » 05 Aoû 2021, 13:01

Je peux expliquer tout le jeu en fait du coup.
Yokai est un jeu en coopération de 2 à 4 joueurs (ici 2 joueurs) avec 4x4 cartes de 4 couleurs disposé sur la table en 4x4, et où chaque joueur a son tour regardes deux cartes puis en bouge une. Puis c'est au tour de l'autre joueur. Ils font ça 14 fois, et le but est ce que chaque couleur se touche (orthogonalement). Et toutes les cartes doivent se toucher (orthogonalement) a n'importe quel moment du jeu.
(et un but secondaire c'est de gagner le plus tôt possible)
(et il y a une histoire d'indices possible, mais ça ne concerne pas le problème, ni le screen)

Et donc par exemple j'ai fais ceci: https://www.zupimages.net/up/21/31/fxzs.jpg ce qui représente l'ensemble des mouvements que j'effectue si je 'joue tout seul' ou si mon coéquipier ne viens pas interférer avec ce que j'ai effectué.
Donc ce screen ne comporte que les mouvements et ce que regardes un seul joueur, alors que le jeu se jouer a 2. Et le problème est d'avoir un numéro correspondant a chaque situation (donc le second joueur aurait ses 4 propres couleurs, vu qu'il ne sait pas ce qu'a vu le premier joueur).
Et donc, plus les numéros sont commodes mieux c'est. (c'était aussi pour le fun d'essayer de trouver une solution vu que je n'arrivais pas, mais du coup on m'a expliqué :) )

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Attribuer un numéro a chaque situation

par fatal_error » 06 Aoû 2021, 20:54

re,

plusieurs points différents:

1)
par rapport à l'encodage en base 5, il est aussi possible à la place de considérer deux entiers
un entier qui encode la position
un entier qui est un simple compteur pour le nombre de cartes tirées

l'avantage est que (si on considère l'encodage actuel) 5^14 >> 4^14
et en particulier 5^14 = 6'103'515'625 > 4'294'967'295 (UINT_MAX) alors que 4^14 = 268'435'456 < UINT_MAX
du coup quitte à utiliser deux int, autant en conservant un unique pour l'"encodage" et un autre pour différencier les 0 des cartes non tirées des 0 des cartes tirées (mais à qui on a associé la valeur 0)

2)
en fait, le nombre de mains possibles pour les 16 cailloux c'est:
16!/(4!4!4!4!) = 1'513'512'000 (on divise par 4! parce que par l'ordre des jaunes est pas important, idem 4! pour les verts, etc)
pour associer à une main son id il y a des algos existants (un peu la flemme de me rappeler/chercher) mais j'imagine que c'est dans ce sens que tu voulais aller ?
(c'est marrant pour l'algorithmie, mais c'est clairement plus direct d'encoder en base 4)
la vie est une fête :)

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Attribuer un numéro a chaque situation

par lyceen95 » 06 Aoû 2021, 21:08

16!/(4!*4!*4!*4!) = 63 063 000 ; tu n'as divisé que 3 fois par 24.

C'est effectivement beaucoup plus petit que 4^16 ou 5^16.

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 29 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite