Problèmes du monde réel avec le brassage naïf

Question

J'écris un certain nombre d'articles destinés à enseigner les concepts de la programmation de débutant en utilisant des sujets liés au poker. Actuellement, je travaille sur le thème du brassage.

As souligne Jeff Atwood sur CodingHorror.com. , une méthode simple de mélange (itération dans un tableau et échange de chaque carte avec une carte aléatoire ailleurs dans le tableau) crée une distribution inégale des permutations. Dans une application réelle, je voudrais simplement utiliser le Knuth Fisher-Yates shuffle pour un caractère aléatoire plus uniforme. Mais, je ne veux pas m'embarrasser d'explications sur les concepts de programmation avec l'algorithme beaucoup moins convivial.

Cela nous amène à la question suivante: quel avantage aurait un avantage pour un chapeau noir s’il savait que vous utilisez un mélange naïf d’un jeu de 52 cartes? Il semble que ce soit infiniment petit.

Answer 1

Ce n’est pas comme si vous écriviez un programme de poker qui sera utilisé pour un site de jeu en ligne réel. La possibilité pour quelqu'un de tricher au programme n'est pas un problème si vous apprenez aux autres à programmer.

Laissez une note indiquant qu'il s'agit d'un mauvais modèle du monde réel (avec une référence à celui-ci comme une faille de sécurité possible), et continuez simplement avec l'enseignement.

Answer 2

Le mélange de knuth est un changement insignifiant par rapport au mélange naïf: échangez-le avec n’importe quelle carte de la section restante (non brassée) du paquet au lieu de n’importe où dans le paquet entier. Si vous pensez que choisir de façon répétée la prochaine carte dans l'ordre parmi les cartes non choisies restantes, c'est également très intuitif.

Personnellement, je pense qu'apprendre aux élèves un algorithme médiocre lorsque celui qui convient n'est pas plus compliqué (et plus facile à visualiser!) est une mauvaise approche.

Answer 3

Il s'avère que l'avantage est assez important. Consultez cet article

.

Une partie du problème tient à l’algorithme défectueux, mais une autre partie à l’hypothèse que vous pouvez obtenir un message "aléatoire". les numéros d'un ordinateur.

Answer 4

Un simple & amp; Un algorithme correct pour le brassage consisterait à attribuer un nombre aléatoire (par exemple, entre 0 et 1) à chaque carte de la pioche, puis à trier la pioche par les numéros attribués.

C’est en fait un exemple parfait qui permet aux étudiants de se rendre compte que ce n’est pas parce que quelque chose est intuitif que le remaniement naïf, dans notre cas, est correct.

Answer 5

Subjective.

  

Il semble que ce soit infiniment petit.

D'accord.

Answer 6

Juste à côté, un article de blog terminé sur ITtoolbox à propos du brassage qui peut être intéressant pour simuler un brassage.

En ce qui concerne votre question, considérez qu’il y en a 52! Les configurations de deck par lesquelles on pourrait commencer peuvent jouer un rôle dans les choses comme dans l'exemple du deck à 3 cartes de Jeff, notez que le 1 dans le sur-représenté se produit une fois dans chaque emplacement. Notez également qu’il dit que vous devez avoir quelques milliers d’exemples avant qu’il devienne évident d’avoir un avantage, mais avec un deck, vous ne risquez pas de recommencer avec exactement le même deck initial, n’est-ce pas? Vous prendriez les cartes distribuées et les placeriez sur le fond et les mélanger, ce qui risquerait de ne pas se répéter, je pense.