Voici les faits en premier.
dans le jeu de pont il y a 4 joueurs nommés nord, sud, est et Ouest.
Les 52 cartes sont traitées avec 13 cartes à chaque joueur.
Il y a un système de comptage d'honneur. Ace = 4 points, roi = 3 points, reine = 2 Points et Jack = 1 point.
Je crée un "concessionnaire de carte" avec des contraintes où, par exemple, vous pourriez dire que la main traitée vers le Nord doit avoir exactement 5 piques et entre 13 et 16 points d'honneur, le reste des mains est aléatoire. < / p>
Comment puis-je accomplir cela sans affecter le "aléatoire" de la meilleure façon et avoir un code efficace?
Je codis dans C # et .NET Mais une idée de pseudo-code serait bien!
5 Réponses :
Selon la vitesse de votre ordinateur, il pourrait em> suffire pour le faire: Comme avec toutes les questions de performance, la chose à faire est d'essayer et de voir! p> éditer em> je l'ai essayé et j'ai vu: P>
done 1000000 hands in 12914 ms, 4424 ok
Il suffit de poster la même idée ... Il serait intéressant de prévenir les contraintes incontournables, de sorte que votre réaction ne va pas aller à la boucle ...
Cela n'ira vraiment pas sous la section du code "efficace". Je cherche vraiment une façon de tricher un peu .. Il y a 22 090 320 000 combinaisons pour mélanger un pont et seront trop lourds, je pense .. Je prévois d'avoir cette opération en ligne sur mon hébergement Web
Il est "efficace" tant qu'il se comporte comme souhaité. Cela pourrait ne pas être très "efficace", c'est vrai, mais dans ce cas, une solution de contournement heuristique pourrait toujours être votre meilleur choix.
Merci pour cette mise à jour AAAKASHM, vous risquez peut-être juste qu'il ne fait aucun point d'essayer de compliquer les choses ici.
Une optimisation significative consiste à ne traiter que la main «Nord», puisqu'elle est la seule avec des contraintes. Vous pouvez commencer par traiter 5 piques aléatoires, puis 8 cartes aléatoires supplémentaires de ce qui reste du pont. Ensuite, si les contraintes ne sont pas remplies, ne vous embêtez pas de traiter pour personne d'autre. Il existe également d'autres moyens simples de traiter rapidement la main du Nord d'une manière cohérente avec les contraintes.
Essayer de faire une certaine méthode d'usine pour générer les offres prend beaucoup de temps à l'avant, à moins que l'accord ne soit très rare, surtout lors de l'utilisation du concessionnaire pour générer une poignée de transactions pour enchérir. De plus, les meilleures méthodes d'usine sont plus difficiles à mettre en œuvre correctement, ce qui conduit à des préjugés cachés s'il est mal mis en œuvre, tandis qu'une boucle de transaction tout entière est plus susceptible d'obtenir des probabilités correctes. Enfin, une méthode d'usine pour générer des types de personnes particulières est coûteuse en mémoire, même si elle est plus rapide.
Étant donné que les chiffres sont assez petits ici, vous pouvez simplement prendre l'approche heuristique: traiter vos cartes de manière aléatoire, évaluer les contraintes et simplement traiter si elles ne sont pas remplies.
J'irais pour ce flux, que je pense n'affecte pas le hasard (autre que par des solutions de taille qui ne répondent pas à des contraintes):
Vous pouvez écrire un programme qui génère les combinaisons de mon premier point ou simplement les crochets, tout en comptabilisant des symétries de couleur pour réduire le nombre de lignes de code :)
Cet algorithme ne fonctionnera pas, car il gâche des probabilités conditionnelles. C'est à peu près comment fonctionne de la "pile intelligente" de mon revendeur, mais votre première étape ne peut que chaque ensemble de cartes de valeur aies la même probabilité, car le nombre de façons de remplir le reste du reste de la main dépend du nombre des cartes d'honneur que vous avez déjà choisies. La fonctionnalité "Smart Stacking" de mon revendeur, mentionnée précédemment, ce genre d'analyse, mais nécessite une très grande table.
Par exemple, si vous avez traité cinq piques et n point d'honneur, quel est le nombre attendu de points d'honneur dans votre costume de pique? Dans la condition équitable, les points de pelle moyenne sont tout simplement n * 5/13. Mais votre technique d'échantillonnage produirait des points de pelle moyenne de N / 4.
(Ooops, les points attendus de Spades avaient tort, sauf lorsque n = 10, mais au moins dans ce cas, votre algorithme aura mal. :)
Puisque vous voulez pratiquer des enchères, je suppose que vous aurez probablement diverses formes de contraintes (et pas seulement l'ouverture de 1s, comme je suppose que ce problème actuel) à venir à l'avenir. Essayer de trouver la génération de mains optimale adaptée aux contraintes pourrait être un bon évier et ne vaut pas vraiment l'effort.
Je suggérerais que vous utilisiez l'échantillonnage de rejet: générer une offre aléatoire (sans aucune contrainte) et test si elle répond à vos contraintes.
Pour que cela soit réalisable, je vous suggère de vous concentrer sur la génération de l'offre aléatoire (sans aucune contrainte) aussi vite que possible.
Pour ce faire, cartographier chaque main sur un entier de 12Byte (le nombre total de mains de pont convient à 12 octets). Générer un entier aléatoire de 12 octets peut être effectué en seulement 3, 4 appels de numéro aléatoire sur 4 octets, bien sûr, car le nombre de mains n'est pas exactement montage dans 12 octets, vous pourriez avoir un peu de traitement à faire. ici, mais je m'attends à ce que ce ne soit pas trop.
Richard Pavlicek possède une excellente page (avec des algorithmes) pour mapper une transaction à un numéro et à un retour.
voir ici: http://www.rpbridge.net/7z68.htm
Je vous suggère également de regarder le logiciel de traitement des mains de pont existant (comme offre 3.1 , qui est librement disponible) aussi. Deal 3.1 prend également en charge faire une analyse double factice. Peut-être que vous pourriez le faire fonctionner pour vous sans avoir à rouler l'un de vos propres.
espère que cela aide.
Comme quelqu'un a déjà mentionné mon transal 3.1, j'aimerais signaler certaines des optimisations que j'ai faites dans ce code.
Tout d'abord, pour obtenir les contraintes les plus flexibles, je voulais ajouter une langue de programmation complète. Pour mon revendeur, vous pouvez donc générer des bibliothèques entières de contraintes avec différents types d'évaluateurs et de règles. J'ai utilisé TCL pour cette langue, car je l'apprenais déjà pour le travail et, en 1994, lorsque vous avez été libéré, TCL était la langue la plus facile à intégrer à l'intérieur d'une application C. P>
Deuxièmement, j'avais besoin de la Langue de contrainte à courir assez vite. Les contraintes sont en marche au fond de la boucle. Toutes beaucoup de code dans mon revendeur sont de petites optimisations avec des tables de recherche et similaires. P>
L'une des optimisations les plus surprenantes et les plus simples était de ne pas traiter des cartes à une assise jusqu'à ce qu'une contrainte soit vérifiée sur ce siège. Par exemple, si vous voulez que le nord correspond à la contrainte A et South correspondent à la contrainte B et que votre code de contrainte est le suivant: p> seulement lorsque vous arrivez à la première ligne. Remplissez la main nord. Si cela échoue, vous rejetez l'accord complet. S'il passe, remplissez ensuite la main sud et vérifiez sa contrainte. Si cela échoue, lancez l'ensemble de l'accord. Sinon, terminez l'affaire et acceptez-la. P> J'ai trouvé cette optimisation lors du profilage et remarquez que la plupart du temps a été dépensé dans le générateur de nombres aléatoires. P> Il y a une fantaisie Optimisation, qui peut fonctionner dans certains cas, appelez "Smart Stacping". P> h(5,10)*h(4,3)*h(4,0)*h(0,0)
Bonjour Thomas et merci d'une réponse très étendue. J'ai examiné votre programme et ça a l'air très bien, je ne suis pas un expert de TCL, même si cela est utilisé dans notre environnement de production au travail, mais je pourrais "voler" quelques idées. Le but de mon logiciel est de construire un site pour résoudre le problème pour moi et mon partenaire de pratiquer des enchères, nous n'avons jamais le temps de le faire, donc je crée une application Web .NET pour créer un système de soumission correspondant. . Je vais le faire assez beau pour que quiconque soit utilisé s'ils veulent :)
S'il s'agit d'un site, vous voudrez peut-être également permettre à une personne de télécharger un fichier d'offres plutôt que d'avoir le site générer les offres. Ensuite, vous pouvez utiliser n'importe quel logiciel de revendeur pour générer des offres, puis les télécharger (compte tenu du format approprié.)
+1: Pour la description. BTW, avez-vous apprécié l'idée de mappage dans ma réponse? Étant donné que la génération de nombres aléatoires est un goulot d'étranglement, la réduction du nombre d'appels de 52 (ou 13) à 4-5 serait une bonne optimisation.
Oui, mais l'idée de cartographie devient délicate avec certains types de simulations telles que lorsqu'une main particulière est connue ou que vous voulez dire "South a la pelle Ace et King". Vous pouvez toujours faire une cartographie, mais cela devient plus difficile. En outre, le temps sauvé en réduisant les appels vers le RNG pourrait être perdu de faire la grande arithmétique entier - vous devez faire de nombreuses opérations de division et de modulus sur des numéros de 96 bits pour obtenir le problème du numéro de cartographie.
Comme vous l'avez dit avant, extrayez la main nord uniquement lorsque vous avez besoin, etc. (c'est pourquoi j'ai comparé à 13 :-)) pourrait réduire les calculs. En outre, moins d'appels de nombres aléatoires implique de moins de chances d'erreur dans la distribution de probabilité résultante. De plus, ces jours-ci, avec des machines 64 bits, ces calculs (deux entiers 64 bits) doivent être rapides. Peut-être qu'un schéma de cartographie intelligent peut gérer l'empilement de la main. Bien sûr, je parle simplement que vous avez essayé de l'essayer :-)
Eh bien, mon empilement intelligent fonctionne essentiellement de cette façon, dans la mesure où il calcule les probabilités de différents types de mains. Théoriquement, cela pourrait compter les mains et ensuite vous choisir un numéro de 1 à N, sûr. N'oubliez pas que l'empilement intelligent n'est que pour une main, pas la toute affaire, car les probabilités conditionnelles sont exponentiellement plus compliquées. Vous pouvez avoir des conditions sur les autres mains, mais elles ne sont pas construites avec une usine. Le vrai problème avec l'empilement intelligent et la cartographie des transactions est la complexité du code, ce qui rend la vérification difficile.
Est l'exemple la seule contrainte? Pourriez-vous expliquer pourquoi de telles contraintes? Parce que si des contraintes sont comme "le nord doit avoir ..." C'est vraiment différent de "un joueur doit avoir ..."
Sans aller trop de détails sur le jeu de pont, la contrainte est pour une main spécifique. Normalement, les contraintes ne seraient pas à compliquer là où vous vous êtes fixé pour les quatre mains. Le but de ma tâche ici est de générer des planches pour pratiquer des soumissions sur des types de main spécifiques.
@Moron, dépend de ce que vous parlez ..
@Stefan: Désolé, je voulais dire Thomas Andrews 'Talk 3.1. Je crois que Han Sverans (ne vous souvenez pas du nom exact) avait un logiciel de distribution appelé revendeur. J'ai ajouté une réponse, cependant.
Le nom que vous recherchez, M, est Hans van Staveren et son programme s'appelle "concessionnaire".
Plus j'y pense, plus je pense que vous devriez simplement laisser vos utilisateurs télécharger un fichier d'offres généré ailleurs. Le problème est que si vous utilisez une langue flexible, vous devez faire beaucoup de contrôle pour voir si le code de leurs conditions est "sûr". Si vous laissez une forme ouverte au monde et dites: «Entrez quelques basiques visuelles ici, que je vais exécuter sur mon serveur», vous pouvez voir le problème. :) Vous pourriez bien sûr mettre en œuvre votre propre langue, mais cela risque probablement de limiter.
Je suis allé avec simplement générer les transactions et je vérifie les contraintes. Je devais veiller à ce qu'il n'y ait pas à de nombreuses contraintes, car il peut s'agir de nombreuses offres avant de frapper un et je prévois d'exécuter cela sur mon environnement hébergé et qu'ils fermeront mon site pendant 3 heures si j'utilise beaucoup de CPU sur des périodes . Merci à tous pour les bonnes réponses!