Jak tasować karty w grze karcianej?


13

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

Odpowiedzi:


21

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]

1
Algorytm jest również ładnie zobrazowany tutaj: bost.ocks.org/mike/algorithms/#shuffling
Felsir

9

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.


3
nazywa się to tasowaniem Knutha: en.wikipedia.org/wiki/Knuth_shuffle
krolth

2

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/


Ta odpowiedź, ponieważ jest obecnie sformułowana, niewiele pomaga, gdy URL nieuchronnie spada z powierzchni Internetu. Zastanów się nad opracowaniem odpowiedzi na temat najistotniejszych punktów połączonego artykułu, aby odpowiedź mogła stać sama.
Lars Viklund,

1
Dobra uwaga Lars, zaktualizowana o więcej informacji, aby czytelnik mógł przynajmniej wyszukać więcej informacji na temat wszystkich konkretnych składników rozwiązania tasowania kart przy użyciu szyfrowania zachowującego format. Dzięki!
Alan Wolfe

1

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


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

1
Odpowiedzi zawierające tylko kod są odradzane.
SurvivalMachine
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.