Discussion :

[mazertys17]

Bonjour.

J'aimerai l'avis d'experts en algo/mathématique à propos de la conception d'un générateur de grilles de bingo.
Il est trés facile de générer une suite de grille, de plaques de grilles avec des nombres aléatoires.

Mais il faut que, face à une suite aléatoire de nombres de 0 à 90, il y ait le moins de doublons possible, y compris avec des suite de 10 000 grilles ou + par exemple.

Pour rappel une grille de bingo ressemble à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
[1, 0, 0, 34, 47, 0, 0, 77, 81],
[0, 12, 0, 42, 58, 0, 74, 82],
[8, 0, 21, 33, 47, 0, 63, 0, 85],

le but est de compléter la grille en fonction des numéros tirés, et enfonction du jeu, on gagne si on complète une ligne, 2 lignes ou la totalité de la grille.
Sachant que des milliers de joueurs peuvent jouer en même temps.

Le but est donc de s'assurer qu'il n'y ai pas 2 joueurs qui gagnent en même temps.

Question bête : est-ce seulement possible ?
Il semblerait que non : le nombre de probablité est vertigineux et il y aura inévitablement quelques doublons au moins.

Question qui nous intéresse ?
Peut ont toutefois optimiser la conception des grilles aléatoire pour faire en sorte qu'il y ait le moins de doublons possible ?
Et si oui, comment ?

J'ai cherché des petites combines mais globalement je pense qu'il faut des compétences et compréhensions mathématiques plus poussées pour répondre vraiment à cette question.


Merci donc au petit géni qui pourra m'éclairer sur cette question !

[Flodelarab]

Bonjour

Mazertys17, tu regardes trop les grilles et pas assez le tirage. En effet, le tirage est un ordre parmi 100 numéros (soit 100! = factorielle de 100), et à chaque tour on consomme un numéro de la liste triée. Ce que tu souhaites est de n'avoir qu'un gagnant à chaque tour (en oubliant les premiers tours pour lesquels trop peu de numéros ont été tirés). Plus le temps s'écoule et plus tu as de gagnants virtuels (seul le premier compte, évidemment). Donc avec 100 numéros, 9 numéros par grille, tu peux avoir 92 tours gagnants maximum, donc 92 gagnants uniques. Avec 10000 grilles, malaise : doublons à foison.

une suite aléatoire de nombres de 0 à 90

Pourtant tu obtiens 98. 92 et 0.

[mazertys17]

Flodelarab Merci pour ta réponse.

En effet...sachant qu'en plus, j'ai oublié de le préciser, on ne peut pas intervenir sur le tirage en lui même. Il doit être totalement aléatoire : le tirage est externe au programme.

Pourtant tu obtiens 98. 92 et 0.

Oui en effet je me suis trompé j'ai sauté la dizaine je vais réctifier ça.

Donc en somme tu pense qu'il est impossible d'empêcher les doublons OU MEME de contrôler les probabilités afin d'en avoir le moins possible ?

[valentin03]

Flodelarab Merci pour ta réponse.

En effet...sachant qu'en plus, j'ai oublié de le préciser, on ne peut pas intervenir sur le tirage en lui même. Il doit être totalement aléatoire : le tirage est externe au programme.

Oui en effet je me suis trompé j'ai sauté la dizaine je vais réctifier ça.

Donc en somme tu pense qu'il est impossible d'empêcher les doublons OU MEME de contrôler les probabilités afin d'en avoir le moins possible ?

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus il y a de générations et plus ça prend de temps.

[mazertys17]

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus y en a et plus ça prend de temps.

Sans doute...mais comment ?

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.
Rien que ça donne mal à la tête...même avec un bon PC de gamer ça doit prendre un certain temps de faire tous les calculs de combinaison...
Sachant qu'on ajoute à ça une puissance 15 de la grille bingo.

Ca fait beaucoup. Au final, à moins, peut être, de ne pas vraiment générer les nombre aléatoirement, ce que j'ai essayé d'imaginer, c'est mission impossible...en tout cas pour quelqu'un comme moi qui n'a pas les maths dans la peau.

[mazertys17]

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus y en a et plus ça prend de temps.

Sans doute...mais comment ?

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.
Rien que ça donne mal à la tête...même avec un bon PC de gamer ça doit prendre un certain temps de faire tous les calculs de combinaison...
Sachant qu'on ajoute à ça une puissance 15 de la grille bingo.

Ca fait beaucoup. Au final, à moins, peut être, de ne pas vraiment générer les nombre aléatoirement, ce que j'ai essayé d'imaginer, c'est mission impossible...en tout cas pour quelqu'un comme moi qui n'a pas les maths dans la peau.

Et en plus a supposer qu'on mette l'algo sur le papier est-ce qu'on risque pas de rester bloqué à un moment ou l'autre ?

[Flodelarab]

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.

Oui tu t'abuses. Je t'ai déjà dit que c'était 90! (factorielle de 90). Il y a 90! tirages possibles, soit 1.485716e+138 possibilités. Mais cela n'a pas vraiment de rapport avec le fait de répartir les gagnants.

[mazertys17]

soit 1.485716e+138 possibilités

En int ça doit faire un sacret parquet de chiffres non ?

ça donne ça pour être exact :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

Mais cela n'a pas vraiment de rapport avec le fait de répartir les gagnants

Bah pour celà il faudrait évaluer chaque ligne, double ligne et grille complête par rapport aux milliers d'autres grilles, le tout sur ces 1.485716e+138 possibilités, non ?
Où je ne m'abuse pas encore .

Et là soit il faut un ordi quantique soit faire appel à la NAZA dirrectement
Où alors je m'abuse encore...mais franchement j'ai pas l'impression j'ai beau être nul en math là ça me paraît quand même beaucoup...

C'est pour ça que j'ai d'ailleurs même pas cherché à lancé le calcul car ça me paraît inutile.

[mazertys17]

APRES, il y a tout de mêmes certains facteurs qui me paraissent pouvoir réduire le champ des possibles, mais là aussi, étant nul en math j'ai l'impression de jouer aux apprentis sorciers

EX : chaque colonne indique une dizaine : colonne 1, de 1 à 9, colonne 2 de 11 à 20 etc...
ou encore chaque carton a 15 numéros soit 90 / 6, et chaque ligne a 5 chiffres.
Donc on peut peut être bidouiller des séries en les comparant par fournées de 6.

Mais au final ça reste des combinaisons monstrueuses.

Peut être qu'en construisant au fur et à mesure chaque grille en prenant en compte un algorythme ?

Bref en fait j'ai l'impression, peut être à tord, que c'est beaucoup de peine pour rien car au final les probabilités seront de toute façon les mêmes...mais je me trompe peut être ?

[valentin03]

En int ça doit faire un sacret parquet de chiffres non ?
ça donne ça pour être exact :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

Bah pour celà il faudrait évaluer chaque ligne, double ligne et grille complête par rapport aux milliers d'autres grilles, le tout sur ces 1.485716e+138 possibilités, non ?
Où je ne m'abuse pas encore .

Et là soit il faut un ordi quantique soit faire appel à la NAZA dirrectement
Où alors je m'abuse encore...mais franchement j'ai pas l'impression j'ai beau être nul en math là ça me paraît quand même beaucoup...

C'est pour ça que j'ai d'ailleurs même pas cherché à lancé le calcul car ça me paraît inutile.

Ton sujet ne nécessite aucune sorte de calcul, seulement des tests; et qui ne porteront que sur les générations précédentes; N grilles = N tests, x lignes par grilles = x fois N tests et on peut permuter x et N que ça n'y change rien.

[mazertys17]

Ton sujet ne nécessite aucune sorte de calcul, seulement des tests; et qui ne porteront que sur les générations précédentes; N grilles = N tests, x lignes par grilles = x fois N tests

Oui mais le problème est le même.
Les tests je les ai mis en place mais rapidement j'ai vu que ça n'avançait a rien.
A quoi bon tester 100 tirages, 1000, 1 milliard de tirage sur des dizaines de milliers de grilles quand tous ces tests ne sont même pas 1% des probabilités réelles ?

Je rappelle que le but n'est pas de générer quelques grilles, mais une dizaine de milliers de grilles, pas moins.

[valentin03]

Oui mais le problème est le même.
Les tests je les ai mis en place mais rapidement j'ai vu que ça n'avançait a rien.
A quoi bon tester 100 tirages, 1000, 1 milliard de tirage sur des dizaines de milliers de grilles quand tous ces tests ne sont même pas 1% des probabilités réelles ?

Je rappelle que le but n'est pas de générer quelques grilles, mais une dizaine de milliers de grilles, pas moins.

10 000 grilles à 10 lignes par grille ça reste gérable en C, ça serait plus long avec de l'interprété, mais les ordinateurs ça peut travailler pendant qu'on dort.
Quand on a testées les dix lignes des dix milles grilles on a fait 100% du test.pas la peine de parler de milliards.

[tbc92]

Le but est donc de s'assurer qu'il n'y ai pas 2 joueurs qui gagnent en même temps.

Ca, c'est impossible.
Je pars sur l'hypothèse qu'on a 10 n° par grille ... mais ça resterait valable avec n'importe quelle autre valeur.

Si tu as par exemple une grille avec 12 15 18 25 35 46 51 53 65 78
et une autre avec 13 16 19 26 36 47 52 54 65 78
Le seul nombre en commun est 78,
Mais si au moment du tirage, on sort dans cet ordre 12 15 18 25 35 46 51 53 65 13 16 19 26 36 47 52 54 65 puis 78, les possesseurs de ces 2 grilles vont compléter leur grille tous les 2 en même temps.

La difficulté, elle est en fait différente.
Si un joueur a une grille avec les n° 1 2 3 4 5 6 7 8 9 10, il va se sentir 'défavorisé'. Alors que ce n'est pas du tout le cas. Mais c'est probablement la plus grosse contrainte.
Il faut donc que toutes les grilles aient au moins un n° dans chaque dizaine, ou une règle de ce genre, pour que les gens aient un sentiment de justice.

Bonne nouvelle, tu parles de générer énormément de grilles. Si tu devais générer seulement 20 ou 30 grilles, tu aurais d'autres problèmes à régler, des problèmes d'équité.
Imagine la situation où tu dois générer 10 grilles, et tu génères ça :
12 15 18 25 35 46 51 53 65 78
12 15 18 25 35 46 51 53 65 79
12 15 18 25 35 46 51 53 65 80
12 15 18 25 35 46 51 53 65 81
12 15 18 25 35 46 51 53 65 82
12 15 18 25 35 46 51 53 65 83
12 15 18 25 35 46 51 53 65 84
12 15 18 25 35 46 51 53 65 85
12 15 18 25 35 46 51 53 65 86
11 14 17 26 34 41 45 50 60 77
Bien entendu, c'est caricatural. Mais c'est volontaire, pour que le biais soit plus visible.
Le possesseur de la dernière grille serait très avantagé. En gros il aurait une chance sur 2 de gagner, alors que les 9 autres joueurs se partageraient les 50% de chances restantes de gagner.
Dans ton cas, comme tu génères pas mal de grilles, tu ne devrais pas avoir ce risque là. Mais il faut se méfier quand même.

A suivre.

[mazertys17]

tbc92 excelent !

Maintenant c'est un peu cynique ce que je vais dire mais a la limite c'est pas grave si certaines grilles ont plus de chance de gagner que d'autre, (sachant que ça reste relatif a un ensemble de grilles et non a chaque grille individuellement si j'ai bien compris).

La seule chose a viser c'est empêcher les doublons...

Donc d’après toi, c'est strictement impossible ?

Et autrement vois tu un moyens de les limiter autant que possible, un peut avec l'esprit caricatural que tu cite, c'est à dire en construisant les grilles selon une logique ?
Ou autres moyens encore ?

Ou au final quelque soit la methode le nombre de doublons sera toujours quasiment identique ?

[tbc92]

Prend 2 joueurs ; ils ont chacun leur grille, avec 10 numéros sur la grille. Ils ont chacun coché 9 numéros sur leur grille et ils attendent tous les 2 le 10ème numéro. Et, pas de chance, le numéro qu'ils attendent est le même, c'est le n°78 , le même pour tous les 2.
Forcément, ils vont finir leur grille en même temps.

Si tu as 5000 joueurs qui jouent en même temps, le cas sera fréquent que 2 joueurs finissent leur grille en même temps. Et même des fois 3 ou 4 joueurs en même temps.

Dans ton 1er message, tu ne le dis pas clairement, mais chaque grille comporte 16 numéros.

Bien entendu, pour que le jeu soit juste, toutes les grilles doivent avoir le même nombre de numéros, mais est-ce que ce nombre de 16 est imposé ?

On doit pouvoir faire des calculs (ou des simulations), et voir si on peut limiter la probabilité d'avoir 2 vainqueurs en même temps.
Toujours en exagérant au maxumum, si tu as des grilles avec 75 ou 80 ou 85 numéros au lieu de 16, c'est sûr qu'il y aura plein d'ex-aequos. Et idem, avec des grilles à 3 ou 4 numéros, il va y avoir plein d'ex-aequos.

Peut-être que pour limiter le risque d'ex-aequos, il faut mettre 20 voire 25 numéros sur chaque grille. Le risque ne sera jamais 0, loin de là. Mais tu peux peut-être le réduire de cette façon.

[mazertys17]

tbc92 Merci pour ta réponse
En fait il y en a 15 par grilles.
5 par lignes et cela ne change pas.

Comme dans cet exemple :


Et même pour aller plus loin il y en a 90 par plaque de 6 grilles :


Chaque collone représente une dizaine.

J'ai déjà fais des simulation et le nombre de doublons était impressionnant surtout au bout de 50 tirages...
Alors en fait normalement quand un joueur ou plusieurs a gagné on arrête là le tirage.

[tbc92]

Avec cette disposition en créant en fait des pages de 6 grilles 'complémentaires', on peut faire un comptage approximatif.
On a une page de 6 grilles, que je vais noter g1, g2 ...g6 ; g1 g2 et g3 sont les 3 grilles de gauche, et g4 à g6 les 3 grilles de droite, de haut en bas à chaque fois.
Dans la grille g4, ici, on a 2 nombres de la 1ère dizaine (8 et 9), 2 nombres de la 2ème dizaine (10 et 18), 2 nombres de la 3ème dizaine (27 et 28), 1 nombre de la 4ème dizaine (33) etc etc
Je parle de dizaine, mais la 1ère dizaine ne contient que 9 nombres (1 à 9), alors que la dernière dizaine en contient 11(80 à 90).
On va se limiter aux pages qui ont la même disposition :
Dans la grille g4, on a 2 nombres de la 1ère dizaine, 2 nombres de la 2ème dizaine, 2 nombres de la 3ème dizaine, 1 nombre de la 4ème dizaine etc

Pour la 1ère colonne, on a 6 grilles possibles pour le 1, 5 ou 6 grilles pour le 2, 4 ou 5 grilles pour le 3, 3 , 4 ou 5 grilles possibles pour le 4, etc ...
Ca nous fait environ 17000 possibilités pour disposer les nombres 1 à 9
Pour la 2ème colonne, on a un peu plus de combinaisons, puisqu'on a 10 nombres et non plus 9 ; environ 58000 possibilités
Idem pour les colonnes suivantes.
Et pour la dernière colonne, on monte à envron 150000 possibilités, avec nos 11 nombres à la dizaine.
Et en tout, on arrive à 5*10^42 possibilités. c'est énorme.
On parle d'imprimer 10000 feuilles de 6 grilles, c'est une infime proportion.

On peut quasiment imprimer 10000 feuilles de 6 grilles au hasard, on a un risque que 2 grilles soient strictement identiques, mais ce risque est faible. Et de toutes façons, dans le déroulement du jeu, il y aura forcément des joueurs qui finissent la grille en même temps. Donc, si ces joueurs finissent en même temps, peu importe qu'ils finissent en même temps avec des grilles différentes, ou avec des grilles similaires.

[mazertys17]

tbc92 Oui, bien vu.

Donc en fait c'est tout simplement impossible de concevoir les grilles aléatoirement dans le but d'empêcher qu'il y ait des doublons lors d'un tirage allant jusqu'à 90 numéros.

C'est étrange parceque sur les fournisseurs de cartons ils prétendent avoir des séries sans doublons.
Peut être veulent-ils simplement dire qu'il n'y a pas 2 grilles pareils ?

On peut quasiment imprimer 10000 feuilles de 6 grilles au hasard, on a un risque que 2 grilles soient strictement identiques, mais ce risque est faible.

Oui et en plus, ça a la limite, on peut le rectifier si on voit 2 grilles semblables.

OK merci pour ces réponses je vais poursuivre la réflexion tout de même car on ne peut pas s'amuser non plus a générer des grilles ou d'un coup il y a 50 gagnants en même temps...
Ca reste a creuser.

[tbc92]

Si, c'est possible de s'assurer qu'il n'y a pas 2 grilles semblables, bien entendu.
Je dis souvent : on est capable d'aller sur la lune, donc un truc comme ça, c'est bien évidemment possible.
Simplement, le programme est un peu plus compliqué à faire. Tout est possible, à condition d'y mettre un peu de moyens.

Et en l'occurrence, le fait que tu poses la question 'Donc en fait c'est tout simplement impossible ... ' me conforte dans l'idée que le programme 'simple' est plus à ta portée que le programme qui s'assure qu'il n'y a pas de doublon.

[valentin03]

Tu commence par parler de Bingo et tu finis en présentant des cartons de Loto; WTF ?