Mischiamo le carte

Terence Hill in “…continuavano a chiamarlo Trinità” per mettere tutti tranquilli da sfoggio della sua indiscussa tecnica per mischiare le carte. 


Ma consideriamo ora una partita di poker o blackjack giocata online con un mazzo di carte virtuale: in questo caso come è possibile garantire che all’inizio di ogni partita il mazzo di carte abbia ricevuto una buona mescolatura? Il problema non è banale o di secondo ordine, tant’è che ogni sito espone in alcune pagine le tecniche utilizzare per la generazione di numeri casuali e garantire la massima casualità nella distribuzione delle carte. (Sul sito italiano PokerStars è possibile trovare le informazioni qui, mentre le informazioni del sito GiocoDigitale sono qui). Analizziamo quindi gli algoritmi di mescolamento (in inglese shuffling). Iniziamo con il definire un algoritmo di mescolamento come un algoritmo che partendo da una sequenza di oggetti (nel nostro caso un mazzo di carte) ne genera una permutazione casuale.

Algoritmo Naive

Il primo algoritmo non ha un nome proprio, per questo l’ho ribatezzato naive dal momento che il secondo che vedremo sarà più efficiente. Partendo da un mazzo di N carte lo shuffling viene effettuato nel seguente modo:

  1. A ciascuna delle N carte viene assegnato un numero generato casualmente, che chiamiamo key.
  2. Il mazzo di carte viene ordinato usando le keys associate alle carte usando un algoritmo di ordinamento che ha una complessità di caso peggiore pari a \Omega(N log N) , ad esempio il merge sort o heap sort.

Se consideriamo tempo costante, O(1) , la generazione dei numeri casuali la complessità del primo algoritmo è O(N + N log N) \sim O(N log N) . Ma è possibile ridurre la complessità del processo di shuffling? La risposta, affermativa, è stata data da Ronald A. Fisher e Frank Yates, il primo biologo/matematica ed il secondo matematico, nel 1938 nella loro opera: “Statistical tables for biological, agricultural and medical research“.

Algoritmo Fisher-Yates

Il metodo di Fisher-Yates, pensato per un approccio paper&pencil, richiede una tabella precompilati di RGN, e procede nel seguente modo:

  1. Partiamo una mazzo di N  carte non mescolate.
  2. Scegliamo un numero casuale k tra 1 ed il numero di carte non ancora mescolate.
  3. Scorriamo il mazzo prendiamo la k-esima carta non ancora mescolata e inseriamola in coda al mazzo di carte ordinate.
  4. Ripetiamo il punto 2 fino a quando non abbiamo più carte da mescolare.

“Mhhh?!? Qualcosa non torna!” starete pensando… ed avete ragione! Se osserviamo bene il metodo di Fisher&Yates da vita ad un algoritmo di complessità quadratica O(N^2) rispetto al numero di carte presenti nel nostro mezzo, a causa dell’implementazione del punto 3). “E allora ???” …

Algoritmo Durstenfeld-Knuth

The Art of Computer Programming  Volume 2

Copertina: The Art of Computer Programming Volume 2 (fonte: Amazon.com)

Nel 1964 Richard Durstenfeld, sulla rivista Communications of the ACM volume 7, pubblica “Algorithm 235: Random permutation” dove propone una modifica all’algoritmo Fisher-Yates che porta la complessità del problema di shuffling a O(N). L’algoritmo di Durstenfeld su reso popolare da Donald E. Knuth nel volume 2 della sua summa algoritmica The Art of Computer Programming come “Algorithm P“. L’algoritmo di Durstenfeld-Knuth procede nel seguente modo:

  1. Poniamo i \leftarrow N dove N è il numero di carte del nostro mazzo.
  2. Selezioniamo l’i-esimo elemento del nostro mazzo.
  3. Generiamo un numero intero j tale che 0 \leq j \leq i .
  4. Scambiamo la j-esima carta con la carta i-esima.
  5. Decrementiamo i, i \leftarrow i-1 finchè i \neq 0 .

Abbiamo ottenuto quello che volevamo: un algoritmo la cui complessità spaziale e temporale fosse lineare, O(N) rispetto al numero di carte che compongono il nostro mazzo.

Implementazione dell’algoritmo di Knuth

def knuth(cards):
     i = len(cards)
     while (i > 1):
          j = randint(0,i)
          i = i - 1
          cards[j], cards[i] = cards[i], cards[j]
Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: