Bagaimana cara mengocok kartu untuk permainan kartu?

13

Saya mencoba mengembangkan permainan kartu untuk Android. Adakah yang bisa menyarankan saya cara menulis kode untuk mengocok kartu bermain secara efektif?

Kishore
sumber

Jawaban:

21

Pengocokan kartu adalah algoritme yang mudah ditulis secara intuitif, dan sepenuhnya salah dengan melakukannya. Ada referensi yang bagus untuk menerapkan pengocokan kartu dengan benar di Wikipedia . Apa yang saya sajikan di sini adalah versi algoritma yang sedikit disederhanakan yang dibahas pada halaman tersebut di bawah Algoritma modern .

Inilah ide dasarnya, dalam bahasa Inggris yang sederhana:

Pertimbangkan setumpuk kartu. Untuk diskusi ini, Anda dapat memiliki sejumlah kartu di geladak, dan mereka dapat mulai dalam urutan apa pun.

Kita akan berbicara tentang "posisi" di dek, di mana "posisi" adalah berapa banyak kartu yang lebih tinggi di dek daripada kartu di posisi itu. Misalnya, kartu di atas geladak berada di posisi 0, kartu di bawahnya ada di posisi 1 (karena ada 1 kartu lebih tinggi dari itu - kartu teratas), dan di dek 52 kartu standar, bagian bawah kartu berada di posisi 51, karena 51 kartu lebih tinggi daripada di geladak.

Sekarang, kami mempertimbangkan setiap posisi di geladak, satu per satu, mulai dari bawah, dan bekerja dengan cara kami ke atas.

Untuk setiap posisi, kami secara acak memilih salah satu kartu yang berada pada posisi itu atau pada posisi yang bernomor lebih rendah (ingat, bagian atas geladak adalah 0, dan kami sedang mengerjakan cara kami naik dari bagian bawah geladak, jadi untuk setiap posisi, Anda secara efektif mengambil semua kartu pada dan di atas posisi itu dan secara acak mengambil salah satu kartu itu).

Ketika kami telah membuat pilihan acak, kami menukar kartu pada posisi yang saat ini kami pertimbangkan dengan kartu yang kami pilih secara acak. Jika kami memilih secara acak kartu yang sudah dalam posisi itu, maka tidak ada swap yang dilakukan.

Setelah bertukar (atau tidak bertukar, jika kami secara acak memilih kartu yang sudah dalam posisi yang kami pertimbangkan), kami beralih ke posisi berikutnya di geladak dan melanjutkan.

Dalam pseudocode, dengan n adalah jumlah kartu di dek, dan sebuah menjadi sebuah array yang mewakili dek, algoritma terlihat seperti ini:

for each i in [n .. 1] do
     j  random integer in [ 0 .. i ]
     exchange a[j] and a[i]
Trevor Powell
sumber
1
Algoritma ini juga divisualisasikan dengan baik di sini: bost.ocks.org/mike/algorithms/#shuffling
Felsir
9

Anda pertama-tama menentukan urutan semua kartu yang ingin Anda kocok:

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

Kemudian Anda berjalan melalui setiap posisi dalam urutan dan menetapkannya kartu secara acak.

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

Sekarang shuffledadalah urutan acak dari semua kartu Anda.

Thomas
sumber
3
ini dikenal sebagai Knuffle's shuffle: en.wikipedia.org/wiki/Knuth_shuffle
krolth
2

Saya ingin berpura-pura dan menyebutkan "format menjaga enkripsi" sebagai metode untuk mengocok kartu dalam permainan.

Pada dasarnya apa yang Anda miliki adalah algoritma enkripsi yang mengambil nilai 0 hingga 51, dan kunci (shuffle seed) dan mengeluarkan nilai 0 hingga 51. Karena enkripsi dapat dibalikkan menurut definisi yang berarti setiap 2 angka input tidak dapat dienkripsi ke nomor output yang sama, yang berarti jika Anda mengenkripsi 0 hingga 51, Anda akan mendapatkan 0 hingga 51 sebagai output dalam urutan yang berbeda. Dengan kata lain Anda memiliki shuffle dan bahkan tidak perlu melakukan pengocokan yang sebenarnya.

Dalam hal ini Anda harus membuat atau menemukan algoritma enkripsi yang mengambil 6 bit dan mengeluarkan 6 bit (0-63). Untuk menggambar kartu berikutnya dari dek Anda akan memiliki variabel indeks yang dimulai dari nol, Anda akan mengenkripsi indeks itu, menambah indeks dan melihat nilai yang keluar dari cipher. Jika nilainya> = 52, Anda mengabaikannya dan menghasilkan nomor baru (dan tentu saja menambah indeks lagi). Karena mengenkripsi 0-63 akan menghasilkan 0-63 sebagai output, dalam urutan yang berbeda, Anda hanya mengabaikan nilai apa pun yang keluar> = 52 sehingga Anda memiliki algoritma Anda yang menghasilkan 0-51 dan mengeluarkan 0-51.

Untuk merombak deck, atur kembali indeks ke nol dan ubah kunci enkripsi (shuffle seed).

Algoritme Anda tidak harus berkualitas kriptografi (dan seharusnya tidak, karena itu akan mahal secara komputasi!). Salah satu cara yang sangat baik untuk menghasilkan algoritma enkripsi berukuran khusus seperti ini adalah dengan menggunakan jaringan feistel, yang memungkinkan Anda menyesuaikan ukuran dan kualitas tergantung pada kebutuhan Anda. Untuk fungsi bundar dari jaringan feistel, saya akan merekomendasikan sesuatu seperti murmurhash3 karena cepat dan memiliki efek longsoran yang baik, yang akan membuat shuffles tampak acak dengan baik.

Lihat posting blog saya untuk info lebih lanjut dan kode sumber: http://blog.demofox.org/2013/07/06/fast-lightweight-random-shuffle-functionality-fixed/

Alan Wolfe
sumber
Jawaban ini seperti saat ini diungkapkan tidak banyak membantu ketika URL pasti jatuh dari permukaan Internet. Pertimbangkan untuk menguraikan jawaban pada poin-poin penting dari artikel yang ditautkan, sehingga jawabannya dapat berdiri sendiri.
Lars Viklund
1
Good point Lars, diperbarui dengan lebih banyak info sehingga pembaca setidaknya dapat mencari lebih banyak info tentang semua komponen spesifik dari solusi pengocokan kartu menggunakan enkripsi format yang menjaga. Terima kasih!
Alan Wolfe
1

The java 1,5 enum tutorial memiliki cara yang menarik untuk melaksanakan setumpuk kartu, membangun dek, menyeret dan berurusan. Semua sangat sederhana menggunakan enums danCollections

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

Dan kelas untuk mengelola dek.

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
sumber
0

Cukup gunakan fungsi seperti itertools seperti yang ada di Python. Saya tidak mengetahui nama fungsi yang sama di Jawa coba ". Http://code.google.com/p/neoitertools/ "

Cari tahu semua permutasi dari objek yang disebut "kartu"

Chris Thaliyath
sumber
-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
sumber
1
Jawaban khusus kode tidak disarankan.
SurvivalMachine