Teste rápido, senhor. Como o senhor escreveria um código para embaralhar um baralho de cartas?
Eu estava pensando sobre isso depois de ler Os problemas do algoritmo de embaralhamento de cartões de Mike:
É aqui que a mente não-CS entra em ação. Minha primeira ideia foi gerar um baralho não embaralhado como uma estrutura semelhante a uma matriz – todas as cartas em ordem por naipe. Em seguida, eu criaria uma segunda estrutura semelhante a uma matriz. Eu percorreria cada carta do baralho não embaralhado, escolheria um número aleatório e inseriria a carta no local selecionado aleatoriamente na segunda matriz. Se a posição escolhida aleatoriamente na segunda matriz já estivesse ocupada, eu escolheria outro número aleatório, veria se ele foi usado e assim por diante, até que a seleção aleatória caísse em um local livre. Chamarei isso de abordagem de inserção aleatória.
Pareceu-me uma abordagem estranha, mas, ao contrário de Mike, tenho o benefício duvidoso de ter experiência em programação. Fui imediatamente para o meu velho amigo, o loop. Vamos supor que temos uma matriz com 52 membros que representam as 52 cartas do baralho.
var rand = new Random();
for (int i = cards.Length - 1; i > 0; i--)
{
int n = rand.Next(i + 1);
int temp = cards[i];
cards[i] = cards[n];
cards[n] = temp;
}
Então, fazemos um loop pelo baralho, trocando cada carta por outra carta de uma posição aleatória no baralho. Parece bastante simples, embora eu desejasse que houvesse um comando Swap embutido na linguagem C# para simplificar um pouco o código. É assustadoramente semelhante ao o embaralhamento de Knuth ou Fisher-Yateso que não significa que eu seja particularmente inteligente, mas que o embaralhamento é um problema de fácil solução.
Ou será que é? Isso parece correto; não há nada obviamente errado aqui. Mas o há dois problemas com esse código. O senhor pode vê-los?
O primeiro problema está bem aqui:
new Random();
Os computadores são péssimos geradores de números aleatórios. Qualquer embaralhamento que o senhor fizer, independentemente do algoritmo, será tão bom quanto o seu gerador de números aleatórios. Portanto, se o senhor estiver administrando, por exemplo, um cassino on-line, precisará ser muito cuidadoso quando o senhor começar a usar a palavra “Random” em seu código. Se o senhor não for cuidadoso, haverá… problemas.
A falha existe no algoritmo de embaralhamento de cartas usado para gerar cada baralho. Ironicamente, o código foi exibido publicamente em www.planetpoker.com/ppfaq.htm com a ideia de mostrar como o jogo é justo para os jogadores interessados (a pergunta relevante foi removida desde então). No código, uma chamada para randomize() é incluída para produzir um baralho aleatório antes de cada baralho ser gerado. A implementação, criada com o Delphi 4 (um IDE Pascal), semeia o gerador de números aleatórios com o número de milissegundos desde a meia-noite, de acordo com o relógio do sistema. Isso significa que a saída do gerador de números aleatórios é facilmente prevista. Um “gerador de números aleatórios” previsível é um problema de segurança muito sério.
Ao sincronizar nosso relógio com o relógio do cassino on-line e pressionar o botão “shuffle” (embaralhar), nosso programa pode calcular o embaralhamento exato. Isso significa que sabemos todas as cartas que ainda não apareceram, a mão de todos e quem ganhará. A captura de tela abaixo mostra as informações exibidas pelo nosso programa em tempo real durante um jogo real. Nosso programa sabe quais cartas devem aparecer com antecedênciaantes de serem revelados pelo jogo on-line.
Para ser justo, isso foi em 1999. Presumo que a maioria dos cassinos on-line já tenha contratado criptógrafos e estatísticos competentes. Com o espectro sempre iminente da trapaça interna e bots de pôquer, eles seriam tolos se não o fizessem.
O segundo problema com esse código é que o ele é muito complicado. Eric “purplicious” Lippert explica o motivo, em sua maneira inimitável:
A maneira padrão de implementar esse algoritmo é: associar cada cartão a um número real aleatório entre 0,0 e 1,0. Classificar a lista com base em seu número associado. Isso é O(n log n) e não tem viés.
Como se vê, a maneira mais fácil de implementar um embaralhamento é classificando. Não é exatamente mais rápido, como o tipo típico é O(n log n) em comparação com o O(n) do algoritmo de embaralhamento Knuth Fisher-Yates. Vamos apenas classificar por um número aleatório, neste caso, a GUID.
var cards = Enumerable.Range(0, 51); var shuffledcards = cards.OrderBy(a => Guid.NewGuid());
Portanto, podemos implementar um shuffle seguro e imparcial como um one-liner em uma linguagem de programação moderna.
O que prova… bem, nada, suponho, mas, como muitos outros problemas de programação, há muitas maneiras de embaralhar errado se o senhor não for cuidadoso.