Jak tasować karty w grze karcianej?

Próbuję opracować grę karcianą dla Androida. Czy ktoś może mi zasugerować, jak napisać kod do efektywnego tasowania kart do gry?

Tasowanie kart to algorytm, który łatwo jest napisać intuicyjnie i całkowicie się myli. Istnieje dobre odniesienie do prawidłowego wdrażania tasowania kart na Wikipedii . To, co tu prezentuję, to bardzo nieznacznie uproszczona wersja algorytmu opisana na tej stronie w części Nowoczesny algorytm .

Oto podstawowy pomysł, w prostym języku angielskim:

Rozważ talię kart. W tej dyskusji możesz mieć dowolną liczbę kart w talii i mogą one zaczynać się w dowolnej kolejności.

Będziemy mówić o „pozycji” w talii, gdzie „pozycja” to liczba kart znajdujących się wyżej w talii niż karta w tej pozycji. Na przykład karta na górze talii znajduje się w pozycji 0, karta poniżej, która jest w pozycji 1 (ponieważ jest o 1 karta wyżej - górna karta), aw standardowej talii 52 kart dolna karta znajduje się na pozycji 51, ponieważ 51 kart jest wyżej niż w talii.

Teraz bierzemy pod uwagę każdą pozycję w talii, pojedynczo, zaczynając od dołu i idąc w górę na szczyt.

Dla każdej pozycji losowo wybieramy jedną z kart, które znajdują się w tej pozycji lub w pozycji o niższym numerze (pamiętaj, że górna część talii to 0, a my pracujemy w górę z dołu talii, więc dla każdej pozycji skutecznie zbierasz wszystkie karty na tej pozycji i powyżej i losowo wybierasz jedną z tych kart).

Po dokonaniu losowego wyboru zamieniamy kartę na pozycję, którą aktualnie rozważamy, na losowo wybraną kartę. Jeśli losowo wybraliśmy kartę, która była już w tej pozycji, nie jest przeprowadzana zamiana.

Po zamianie (lub braku zamiany, jeśli losowo wybraliśmy kartę, która była już w rozważanej pozycji), przechodzimy do następnej pozycji w talii i kontynuujemy.

W Pseudokod, a n oznacza liczbę kart w talii, a jest tablicą reprezentującą pokład, algorytm wygląda tak:

for each i in [n .. 1] do
     j ← random integer in [ 0 .. i ]
     exchange a[j] and a[i]

Najpierw musisz zdefiniować sekwencję wszystkich kart, które chcesz przetasować:

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

Następnie przechodzisz przez każdą pozycję w sekwencji i losowo przypisujesz jej kartę.

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);
}

Teraz shuffledjest losowa sekwencja wszystkich twoich kart.

Chciałbym włączyć się i wspomnieć o „szyfrowaniu z zachowaniem formatu” jako metodzie tasowania kart w grze.

Zasadniczo potrzebujesz algorytmu szyfrowania, który przyjmuje wartość od 0 do 51, oraz klucz (ziarno losowe) i wyrzuca wartość od 0 do 51. Ponieważ szyfrowanie jest z definicji odwracalne, co oznacza, że ​​żadne 2 liczby wejściowe nie mogą być zaszyfrowane ten sam numer wyjściowy, co oznacza, że ​​jeśli zaszyfrujesz od 0 do 51, otrzymasz od 0 do 51 jako wyjście w innej kolejności. Innymi słowy, masz tasowanie i nawet nie musisz wykonywać żadnego przetasowania.

W takim przypadku musisz stworzyć lub znaleźć algorytm szyfrowania, który wziął 6 bitów i wypluł 6 bitów (0–63). Aby wyciągnąć następną kartę z talii, będziesz mieć zmienną indeksu, która zaczyna się od zera, zaszyfrujesz ten indeks, zwiększysz indeks i spojrzysz na wartość, która wyszła z szyfru. Jeśli wartość wynosi> = 52, ignorujesz ją i generujesz nowy numer (i oczywiście ponownie zwiększasz indeks). Ponieważ szyfrowanie 0–63 spowoduje, że dane wyjściowe będą miały wartość 0–63, w innej kolejności po prostu ignorujesz każdą wychodzącą wartość> = 52, dzięki czemu masz algorytm, który przyjmuje 0–51 i wyrzuca 0–51.

Aby przetasować talię, ustaw indeks z powrotem na zero i zmień klucz szyfrowania (seeduj losowo).

Twój algorytm nie musi być jakością kryptograficzną (i nie powinno tak być, ponieważ byłoby to drogie obliczeniowo!). Jednym z naprawdę dobrych sposobów wymyślenia algorytmu szyfrowania o niestandardowych rozmiarach, takiego jak ten, byłoby skorzystanie z sieci feistel, która pozwala dostosować rozmiar i jakość w zależności od potrzeb. Dla okrągłej funkcji sieci feistel zaleciłbym coś takiego jak murmurhash3, ponieważ jest szybki i ma dobry efekt lawinowy, co sprawiłoby, że losowanie wydawałoby się losowe.

Sprawdź mój post na blogu, aby uzyskać jeszcze bardziej szczegółowe informacje i kod źródłowy: http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/

Java 1.5 enum poradnik ma ciekawy sposób wdrożenia talię kart, budując pomost, tasowanie i radzenia sobie. Wszystko bardzo proste przy użyciu enums iCollections

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
    }
}

I klasa zarządzająca talią.

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;
     }
}

Po prostu użyj funkcji takiej jak itertools jak w Pythonie. Nie znam nazwy tej samej funkcji w Java try ”. Http://code.google.com/p/neoitertools/ ”

Znajdź wszystkie permutacje obiektu zwanego „kartami”

    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);