Problemi del mondo reale con il mescolamento ingenuo

Question

Sto scrivendo una serie di articoli pensati per insegnare i concetti iniziali di programmazione attraverso l'uso di argomenti relativi al poker.Attualmente sto lavorando sul tema dello shuffle.

COME Jeff Atwood sottolinea su CodingHorror.com, un semplice metodo di mescolamento (iterazione attraverso un array e scambio di ciascuna carta con una carta casuale in un altro punto dell'array) crea una distribuzione non uniforme delle permutazioni.In un'applicazione reale, utilizzerei semplicemente il file Knuth Fisher-Yates mescola per una casualità più uniforme.Ma non voglio impantanarmi nella spiegazione dei concetti di programmazione con l'algoritmo molto meno intuitivo per i programmatori.

Ciò porta alla domanda:Quale vantaggio avrebbe un black-hat se sapesse che stai usando un ingenuo mescolamento di un mazzo da 52 carte?Sembra che sarebbe infinitesimamente piccolo.

Answer 1

Non è come se stessi scrivendo un programma di poker che verrà utilizzato per un vero sito di gioco d'azzardo online.La capacità di qualcuno di imbrogliare il programma non è un grosso problema quando insegni alle persone come programmare.

Lascia una nota dicendo che questo è un modello scadente del mondo reale (con un riferimento ad esso come possibile falla di sicurezza) e continua semplicemente con l'insegnamento.

Answer 2

Il knuth shuffle è un cambiamento insignificante rispetto allo shuffle ingenuo:Basta scambiarla con qualsiasi carta nella sezione rimanente (non mescolata) del mazzo invece che in qualsiasi punto dell'intero mazzo.Se lo pensi come scegliere ripetutamente la carta successiva in ordine dalle restanti carte non scelte, è anche abbastanza intuitivo.

Personalmente, penso che insegnare agli studenti un algoritmo scadente quando quello corretto non è più complicato (e più facile da visualizzare!) sia un cattivo approccio.

Answer 3

Si scopre che il vantaggio è piuttosto significativo. Dai un'occhiata a questo articolo

Parte del problema è l'algoritmo difettoso, ma un'altra parte è il presupposto che sia possibile ottenere numeri "casuali" da un computer.

Answer 4

Un algoritmo semplice ed equo per mescolare le carte sarebbe quello di assegnare un numero casuale in virgola mobile (ad esempio, tra 0 e 1) a ciascuna carta nel mazzo, quindi ordinare il mazzo in base ai numeri assegnati.

Questo è in realtà un esempio perfetto per far capire agli studenti che solo perché qualcosa è intuitivo, l'ingenuo mescolamento nel nostro caso, non significa che sia corretto.

Answer 5

Soggettivo.

Sembra che sarebbe infinitesimamente piccolo.

Essere d'accordo.

Answer 6

Per inciso, c'era un post del blog su ITtoolbox sul mescolamento che potrebbe essere interessante quando si tratta di simulare un mescolamento.

Per quanto riguarda la tua domanda, considera che sono 52!le configurazioni del mazzo con cui si potrebbe iniziare che possono svolgere un ruolo nel punto in cui le cose finiscono come nell'esempio di Jeff del mazzo da 3 carte, nota che l'1 nel sovrarappresentato si verifica in ogni slot una volta.Nota anche che dice che dovresti avere qualche migliaio di esempi prima che diventi evidente dove sia il vantaggio, ma con un mazzo non è probabile che inizi di nuovo con lo stesso identico mazzo iniziale, vero?Prenderesti le carte distribuite, le metteresti sul fondo e le mescoleresti, cosa che probabilmente non si ripeterà, penso.