Comment mélanger les cartes pour un jeu de cartes?

13

J'essaie de développer un jeu de cartes pour Android. Quelqu'un peut-il me suggérer comment écrire du code pour mélanger efficacement les cartes à jouer?

kishore
la source

Réponses:

21

Le brassage de cartes est un algorithme qui est facile à écrire intuitivement et qui se trompe complètement. Il existe une bonne référence pour implémenter correctement le brassage des cartes sur Wikipédia . Ce que je présente ici est une version très légèrement simplifiée de l'algorithme couvert sur cette page sous L'algorithme moderne .

Voici l'idée de base, en anglais simple:

Considérez un jeu de cartes. Pour cette discussion, vous pouvez avoir n'importe quel nombre de cartes dans le jeu, et elles peuvent commencer dans n'importe quel ordre.

Nous allons parler de "position" dans le jeu, où "position" est le nombre de cartes plus élevé dans le jeu que la carte dans cette position. Par exemple, la carte sur le dessus du jeu est en position 0, la carte en dessous est en position 1 (car il y a 1 carte plus haut que cela - la carte du haut), et dans un jeu standard de 52 cartes, le bas carte est à la position 51, car 51 cartes sont plus élevées que dans le jeu.

Maintenant, nous considérons chaque position dans le jeu, une à la fois, en commençant par le bas et en remontant vers le haut.

Pour chaque position, nous sélectionnons au hasard l'une des cartes qui se trouve à cette position ou à une position de numéro inférieur (rappelez-vous, le haut du jeu est 0, et nous progressons du bas du jeu, donc pour chaque position, vous prenez efficacement toutes les cartes à cette position et au-dessus et vous choisissez au hasard une de ces cartes).

Lorsque nous avons fait la sélection aléatoire, nous échangeons la carte à la position que nous considérons actuellement avec la carte que nous avons choisie au hasard. Si nous avons sélectionné au hasard la carte qui était déjà dans cette position, aucun échange n'est effectué.

Après avoir échangé (ou non échangé, si nous avons sélectionné au hasard la carte qui était déjà dans la position que nous envisagions), nous passons à la position suivante dans le jeu et continuons.

En pseudocode, avec n étant le nombre de cartes dans le jeu, et a étant un tableau représentant le jeu, l'algorithme ressemble à ceci:

for each i in [n .. 1] do
     j  random integer in [ 0 .. i ]
     exchange a[j] and a[i]
Trevor Powell
la source
1
L'algorithme est également bien visualisé ici: bost.ocks.org/mike/algorithms/#shuffling
Felsir
9

Vous définissez d'abord une séquence de toutes les cartes que vous souhaitez mélanger:

List<Card> shuffled = new ArrayList<Card>();
shuffled.addAll(allCards);

Ensuite, vous parcourez chaque position de la séquence et lui attribuez une carte au hasard.

Random random = new Random();
for (int i = shuffled.size() - 1; i >= 0; i--) {
    int j = random.nextInt(i + 1);

    /* swap cards i,j */
    Card card = shuffled.get(i);
    shuffled.set(i, shuffled.get(j));
    shufflet.set(j, card);
}

Voici maintenant shuffledune séquence aléatoire de toutes vos cartes.

Thomas
la source
3
c'est ce qu'on appelle le shuffle de Knuth: en.wikipedia.org/wiki/Knuth_shuffle
krolth
2

Je voudrais faire un carillon et mentionner "format préservant le cryptage" comme méthode pour mélanger les cartes dans un jeu.

Essentiellement, ce que vous auriez est un algorithme de chiffrement qui prend une valeur de 0 à 51 et une clé (mélange aléatoire) et crache une valeur de 0 à 51. Comme le chiffrement est réversible par définition, cela signifie que 2 numéros d'entrée ne peuvent pas être chiffrés pour le même numéro de sortie, ce qui signifie que si vous chiffriez 0 à 51, vous obtiendrez 0 à 51 en sortie dans un ordre différent. En d'autres termes, vous avez votre mélange et vous n'avez même pas besoin de le mélanger.

Dans ce cas, vous devez créer ou trouver un algorithme de chiffrement qui prend 6 bits et crache 6 bits (0-63). Pour tirer la prochaine carte du jeu, vous auriez une variable d'index qui a commencé à zéro, vous crypteriez cet index, incrémenteriez l'index et regarderiez la valeur qui est sortie du chiffre. Si la valeur est> = 52, vous l'ignorez et générez un nouveau nombre (et incrémentez à nouveau l'index bien sûr). Étant donné que le cryptage de 0 à 63 se traduira par une sortie de 0 à 63, dans un ordre différent, vous ignorez simplement toute valeur qui sort> = 52 afin que vous ayez votre algorithme qui prend 0-51 et crache 0-51.

Pour mélanger le jeu, remettez l'index à zéro et changez la clé de chiffrement (graine aléatoire).

Votre algorithme n'a pas besoin d'être de qualité cryptographique (et il ne devrait pas l'être, car cela serait coûteux en calcul!). Un très bon moyen de proposer un algorithme de chiffrement de taille personnalisée comme celui-ci serait d'utiliser un réseau de feistels, qui vous permet de personnaliser la taille et la qualité en fonction de vos besoins. Pour la fonction ronde du réseau feistel, je recommanderais quelque chose comme murmurhash3 car il est rapide et a un bon effet d'avalanche, ce qui donnerait aux shuffles une apparence bien aléatoire.

Consultez mon article de blog pour des informations encore plus détaillées et le code source: http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/

Alan Wolfe
la source
Cette réponse, telle qu'elle est actuellement formulée, n'aide pas beaucoup lorsque l'URL tombe inévitablement de la surface d'Internet. Envisagez d'élaborer dans la réponse les points saillants de l'article lié, de sorte que la réponse puisse se suffire à elle-même.
Lars Viklund
1
Bon point Lars, mis à jour avec plus d'informations pour qu'un lecteur puisse au moins chercher plus d'informations sur tous les composants spécifiques d'une solution au brassage de cartes en utilisant un format préservant le cryptage. Merci!
Alan Wolfe
1

Le tutoriel java 1.5 enum a une façon intéressante d'implémenter un jeu de cartes, de construire le jeu, de mélanger et de distribuer. Tout est très simple en utilisant enums etCollections

public class Card {
    public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX,
        SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }

    public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

    private final Rank rank;
    private final Suit suit;
    private Card(Rank rank, Suit suit) {
        this.rank = rank;
        this.suit = suit;
    }

    public Rank rank() { return rank; }
    public Suit suit() { return suit; }
    public String toString() { return rank + " of " + suit; }

    private static final List<Card> protoDeck = new ArrayList<Card>();

    // Initialize prototype deck
    static {
        for (Suit suit : Suit.values())
            for (Rank rank : Rank.values())
                protoDeck.add(new Card(rank, suit));
    }

    public static ArrayList<Card> newDeck() {
        return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
    }
}

Et la classe pour gérer le deck.

public class Deal {
    public static void main(String args[]) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);
        List<Card> deck  = Card.newDeck();
        Collections.shuffle(deck);
        for (int i=0; i < numHands; i++)
            System.out.println(deal(deck, cardsPerHand));
    }

    public static ArrayList<Card> deal(List<Card> deck, int n) {
         int deckSize = deck.size();
         List<Card> handView = deck.subList(deckSize-n, deckSize);
         ArrayList<Card> hand = new ArrayList<Card>(handView);
         handView.clear();
         return hand;
     }
}
ufis
la source
0

Utilisez simplement une fonction comme itertools comme sur Python. Je ne connais pas le nom de la même fonction en Java, essayez ". Http://code.google.com/p/neoitertools/ "

Découvrez toutes les permutations de l'objet appelé "cartes"

Chris Thaliyath
la source
-2
    ArrayList deckCards = new ArrayList<Card>();
    //add your cards to the deck
    deckCards.add(card1);
    deckCards.add(card2);
    deckCards.add(card3);
    ....
    //shuffle the array list
    Collections.shuffle(deckCards);
Saad BOUSOKRI
la source
1
Les réponses uniquement codées sont déconseillées.
SurvivalMachine