Embaralhando com Python: por onde começar?

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Embaralhando com Python: por onde começar?

Danilo Cabello
Boa noite pessoal,

Estava pensando em fazer um jogo exemplo de Poker e lembrei de algumas
questões que envolve a imensidão de possibilidades que existem na hora
de embaralhar um baralho tradicional.

São 52! (fatorial) que é 2^225 possibilidades[1] totalizando em
80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000,000,000,000,000,
000,000,000[2] encontrei até um artigo falando sobre como um
desenvolvedor manipula um jogo de poker mal feito[4].

Os clubes mais conhecidos[3,4] tem uma página falando sobre isso, vi
no site do desenvolvedor argumentos que pra gerar todas as
possibilidades seria preciso 225 bits e que, por exemplo, o
PartyPoker[4] e ele informa que só usa 32 bits.

Há até entidades certificadoras da aleatoriedade dos algoritmos.

Fica a dúvida, qual a distribuição que o random do Python usa? Dá pra
fazer um programa simples aleatório o suficiente para o jogo de Poker
não ficar previsível? Teria que usar C pra escovar bits ou coisa do
gênero?

Abraços!

[1] - http://en.wikipedia.org/wiki/Shuffling#Randomization
[2] - http://www.pokerstars.com/poker/room/features/security/
[3] - http://www.partypoker.com/about_us/game_fairness/r_n_g.html
[4] - http://www.cigital.com/papers/download/developer_gambling.php

--
Danilo Cabello
Bottom-posting em prol da comunidade.
Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Pinguim Azul
Você pode usar algum site que tenha serviço de geração de números
realmente aleatórios, como o http://www.random.org/

2010/8/2 Danilo Cabello <[hidden email]>:

> Boa noite pessoal,
>
> Estava pensando em fazer um jogo exemplo de Poker e lembrei de algumas
> questões que envolve a imensidão de possibilidades que existem na hora
> de embaralhar um baralho tradicional.
>
> São 52! (fatorial) que é 2^225 possibilidades[1] totalizando em
> 80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000,000,000,000,000,
> 000,000,000[2] encontrei até um artigo falando sobre como um
> desenvolvedor manipula um jogo de poker mal feito[4].
>
> Os clubes mais conhecidos[3,4] tem uma página falando sobre isso, vi
> no site do desenvolvedor argumentos que pra gerar todas as
> possibilidades seria preciso 225 bits e que, por exemplo, o
> PartyPoker[4] e ele informa que só usa 32 bits.
>
> Há até entidades certificadoras da aleatoriedade dos algoritmos.
>
> Fica a dúvida, qual a distribuição que o random do Python usa? Dá pra
> fazer um programa simples aleatório o suficiente para o jogo de Poker
> não ficar previsível? Teria que usar C pra escovar bits ou coisa do
> gênero?
>
> Abraços!
>
> [1] - http://en.wikipedia.org/wiki/Shuffling#Randomization
> [2] - http://www.pokerstars.com/poker/room/features/security/
> [3] - http://www.partypoker.com/about_us/game_fairness/r_n_g.html
> [4] - http://www.cigital.com/papers/download/developer_gambling.php
>
> --
> Danilo Cabello
> Bottom-posting em prol da comunidade.
>
>
> ------------------------------------
>
> ,-----------------------------------------------------------.
> | Antes de enviar um e-mail para o grupo leia:              |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
> | E se você é usuário do BOL lembre-se de cadastrar o       |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
> `-----------------------------------------------------------´Links do Yahoo! Grupos
>
>
>



--
Ricardo Bittencourt
http://www.ricbit.com
Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Leonardo Santagada
In reply to this post by Danilo Cabello

On Aug 3, 2010, at 12:02 AM, Danilo Cabello wrote:
> Fica a dúvida, qual a distribuição que o random do Python usa? Dá pra
> fazer um programa simples aleatório o suficiente para o jogo de Poker
> não ficar previsível? Teria que usar C pra escovar bits ou coisa do
> gênero?

O Python usa o Mersenne Twister explicado na documentação[1]. Mas na mesma documentação fala que o random.shuffle tem problemas para gerar todas as possiveis permutações de uma lista mesmo pequena[2]. Então a resposta acho que é não. Ai tem duas saidas, ou usar algo dependente de plataforma (como /dev/random no linux) ou algum outro algoritmo para geração de números randomicos que tenha um periodo maior que o Mersenne Twister (não necessáriamente precisa ser em C, pode ser em python mesmo). Mas boa sorte pq a partir dai eu já não posso mais ajudar :)

[1] http://docs.python.org/library/random.html#module-random
[2] http://docs.python.org/library/random.html#random.shuffle

--
Leonardo Santagada
santagada at gmail.com



Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Carlos Ribeiro
In reply to this post by Danilo Cabello
2010/8/3 Danilo Cabello <[hidden email]>

> Boa noite pessoal,
>
> Estava pensando em fazer um jogo exemplo de Poker e lembrei de algumas
> questões que envolve a imensidão de possibilidades que existem na hora
> de embaralhar um baralho tradicional.
>
> São 52! (fatorial) que é 2^225 possibilidades[1] totalizando em
>
> 80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000,000,000,000,000,
> 000,000,000[2] encontrei até um artigo falando sobre como um
> desenvolvedor manipula um jogo de poker mal feito[4].
>
> Os clubes mais conhecidos[3,4] tem uma página falando sobre isso, vi
> no site do desenvolvedor argumentos que pra gerar todas as
> possibilidades seria preciso 225 bits e que, por exemplo, o
> PartyPoker[4] e ele informa que só usa 32 bits.
>

Uns muitos anos atrás tive aulas de matemática computacional com um
matemático que era especialista em números aleatórios. Ele apresentou muita
coisa sobre a teoria, incluindo testes de aleatoriedade (chi-square ou "qui
quadrado"), e mostrou várias formas como um gerador aleatório pode ser
viciado. É uma área complicada e cheia de "pegadinhas". De fato existem
geradores ruins, com certos tipo de "regularidade" que viciam os resultados.
Do que eu lembro, posso dizer que:

1) Em tese dá para fazer até com um gerador de um bit só. Uma coisa (tamanho
do número gerado) não tem nada a ver com a outra (embaralhamento perfeito).
O problema é que se você parte de um gerador "viciado", a combinação será
viciada também.

Para provar o ponto acima, imagine um gerador de bits aleatórios. Se você
concatenar uma string aleatória de bits, terá um número aleatório de n bits.
Basicamente, é assim que geradores "eletrônicos" de números aleatórios
funcionam, captando ruído branco de uma fonte randômica e gerando uma stream
de bits.

* Por outro lado, eu não estou certo de que você possa concatenar números de
uma quantidade aleatória de bits - a matemática para provar isso vai muito
além da minha capacidade. Mas com um bit só, eu tenho certeza de que
funciona.

2) Para embaralhar um baralho, você precisa embaralhar poucas cartas - 52
para um baralho "cheio". Você pode implementar um algoritmo confiável de
números aleatórios de N bits em Python puro, a performance deve ser
suficiente, especialmente se você usar bibliotecas e funções adequadas. Não
sei se os inteiros de precisão arbitrária funcionariam bem neste caso mas
acredito que seja um bom começo.

Aproveitando a deixa do item 1, faça um teste: implemente um gerador de um
bit só, pegando o bit menos significativo de um random() normal, e concatene
até obter 225 bits. Anote os resultados e passe por um teste como o chi
square, e veja se ele pode ser considerado "suficientemente aleatório".
Talvez existam outros testes melhores também.

--
Carlos Ribeiro
Consultoria em Projetos
twitter: http://twitter.com/carribeiro
blog: http://rascunhosrotos.blogspot.com
mail: [hidden email]


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Luciano Ramalho
In reply to this post by Leonardo Santagada
A parte do livro do Knuth "The Art of Computer Programming" que fala
sobre números aleatórios é uma das poucas que eu li, mas é muito
divertida.

O Knuth mostra que se você quiser fazer um super gerador de números
aleatórios combinando vários geradores (tipo, o gerador A produz um
número e se for par eu uso o gerador B, se impar eu uso o C), parece
até uma boa idéia intuitivamente, mas a intuição frequentemente está
errada na matemática.

Geradores combinando vários algoritmos tendem a ser piores que os
algoritmos que o compõe, devido a padrões de interferência que
acontecem, decorrentes da natureza ciclica dos algoritmos.

Pelo menos é o que eu me lembro agora. Li isso há uns 20 anos, porque
tive que fazer um programa para gerar 4 milhões de cartelas de bingo
sem repetir. O jornal Folha da Tarde deu um apartamento para alguém
baseado nas tais cartelas. O medo era que saíssem dois apartamentos!
Eu nunca fui processado, então acho que deu certo ;-).

[ ]s
Luciano


--
Luciano Ramalho
programador repentista || stand-up programmer
Twitter: @luciano
Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Carlos Ribeiro
2010/8/3 Luciano Ramalho <[hidden email]>

> A parte do livro do Knuth "The Art of Computer Programming" que fala
> sobre números aleatórios é uma das poucas que eu li, mas é muito
> divertida.
>
> O Knuth mostra que se você quiser fazer um super gerador de números
> aleatórios combinando vários geradores (tipo, o gerador A produz um
> número e se for par eu uso o gerador B, se impar eu uso o C), parece
> até uma boa idéia intuitivamente, mas a intuição frequentemente está
> errada na matemática.
>
> Geradores combinando vários algoritmos tendem a ser piores que os
> algoritmos que o compõe, devido a padrões de interferência que
> acontecem, decorrentes da natureza ciclica dos algoritmos.
>

É por isso que eu comentei que combinar geradores de um bit (concatenando
bits) para gerar uma cadeia arbitrária funciona (geradores de hardware
funcionam assim se não me engano), mas de vários bits eu já não tenho
certeza. Parece que é a mesma coisa mas a matemática de números aleatórios é
cheia de surpresas...

--
Carlos Ribeiro
Consultoria em Projetos
twitter: http://twitter.com/carribeiro
blog: http://rascunhosrotos.blogspot.com
mail: [hidden email]


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Magno Junior
Por que gerar número aleatório é tão difícil?

Se eu utilizasse um algoritmo simples, como pegar o segundo ou milésimo
atual e somar seus algarismos eu não teria um valor completamente aleatório?

Eu não consigo entender muito bem, mas a forma que vejo é que em teoria,
mesmo utilizando o dia, mes, ano e segundo pra gerar um valor único, ele
ainda poderia ser previsível ao menos em teoria, principalmente se rodasse
em cima de uma rotina programada pra ser executada em determinado momento do
dia. A explicação é por esse caminho mesmo?

Outra situação.  No mercado financeiro eu tenho uma situação realmente
aleatória? Se isso for verdade, eu não poderia usar os dados gerados pra
fazer um gerador de número realmente aleatório?
E se o mercado financeiro não é de fato aleatório, isso significa que em
teoria eu poderia criar um algoritmo pra prever como ele vai estar no
futuro?


Em 3 de agosto de 2010 09:22, Carlos Ribeiro <[hidden email]>escreveu:

>
>
> 2010/8/3 Luciano Ramalho <[hidden email] <ramalho%40gmail.com>>
>
>
> > A parte do livro do Knuth "The Art of Computer Programming" que fala
> > sobre números aleatórios é uma das poucas que eu li, mas é muito
> > divertida.
> >
> > O Knuth mostra que se você quiser fazer um super gerador de números
> > aleatórios combinando vários geradores (tipo, o gerador A produz um
> > número e se for par eu uso o gerador B, se impar eu uso o C), parece
> > até uma boa idéia intuitivamente, mas a intuição frequentemente está
> > errada na matemática.
> >
> > Geradores combinando vários algoritmos tendem a ser piores que os
> > algoritmos que o compõe, devido a padrões de interferência que
> > acontecem, decorrentes da natureza ciclica dos algoritmos.
> >
>
> É por isso que eu comentei que combinar geradores de um bit (concatenando
> bits) para gerar uma cadeia arbitrária funciona (geradores de hardware
> funcionam assim se não me engano), mas de vários bits eu já não tenho
> certeza. Parece que é a mesma coisa mas a matemática de números aleatórios
> é
> cheia de surpresas...
>
>
> --
> Carlos Ribeiro
> Consultoria em Projetos
> twitter: http://twitter.com/carribeiro
> blog: http://rascunhosrotos.blogspot.com
> mail: [hidden email] <carribeiro%40gmail.com>
>
> [As partes desta mensagem que não continham texto foram removidas]
>
>  
>


[As partes desta mensagem que não continham texto foram removidas]



------------------------------------

,-----------------------------------------------------------.
| Antes de enviar um e-mail para o grupo leia:              |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
| E se você é usuário do BOL lembre-se de cadastrar o       |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´Links do Yahoo! Grupos

<*> Para visitar o site do seu grupo na web, acesse:
    http://br.groups.yahoo.com/group/python-brasil/

<*> Para sair deste grupo, envie um e-mail para:
    [hidden email]

<*> O uso que você faz do Yahoo! Grupos está sujeito aos:
    http://br.yahoo.com/info/utos.html


Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Luciano Ramalho
2010/8/3 Magno Junior <[hidden email]>:
> Por que gerar número aleatório é tão difícil?
>
> Se eu utilizasse um algoritmo simples, como pegar o segundo ou milésimo
> atual e somar seus algarismos eu não teria um valor completamente aleatório?

Não. Por exemplo, uma interferência com outros softwares rodando na
máquina poderia significar que os milésimos com final 7 fossem gerados
com frequencia menor que os demais. Só um exemplo bobo para dar uma
idéia dos problemas de usar fontes de tempo como geradores.

É como disse von Neumann: "Anyone who considers arithmetical methods
of producing random digits is, of course, in a state of sin."

Um gerador aleatório *mesmo* usa o princípio da incerteza de
Heisenberg. Na prática, isso envolve detectores de partículas, então
não dá para fazer só em software.

O gerador de números aleatórios mais divertido que eu ouvi falar é um
sistema que usa uma webcam para capturar poses de uma lava lamp [1] e
aí processas estes frames com algoritmos de hash para gerar números
aleatórios.

[1] http://bit.ly/ccPJ5q


--
Luciano Ramalho
programador repentista || stand-up programmer
Twitter: @luciano
Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

José Alexandre Nalon
In reply to this post by Danilo Cabello
Olá!
 
> Outra situação.  No mercado financeiro eu tenho uma situação
> realmente aleatória?

Pra complementar o que o Ramalho falou: no caso do mercado
financeiro, temos séries temporais. Existe um teorema (de-
composição de Wold) que diz que parte da informação é de-
terminística, e parte é um processo de médias móveis. Um
processo de média móveis é resultado da aplicação de uma
espécie de média ponderada a uma sequência de números alea-
tórios com distribuição normal.

Há duas complicações: descobrir o que é a parte determinís
tica e quais os pesos da média móvel. Redes neurais costu-
mam fazer um bom trabalho aí.

Há uma complicação adicional no caso do mercado financeiro:
você não pode prever o mercado financeiro porque ele é re-
lativamente manipulado -- ou seja, existem perturbações na
forma de influências externas (ie.: influência de quem tem
grana) que simplesmente não podem ser determinadas -- a não
ser que seja você quem esteja manipulando.

[1] http://en.wikipedia.org/wiki/Wold_decomposition

---
José Alexandre Nalon
[hidden email]



Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Lucas de Oliveira-2
In reply to this post by Danilo Cabello
As pessoas são imprevisíveis correto?

Então um gerador de números aleatórios baseado em uma pessoa poderia ser uma
boa né XD.


Em 3 de agosto de 2010 00:02, Danilo Cabello <[hidden email]>escreveu:

>
>
> Boa noite pessoal,
>
> Estava pensando em fazer um jogo exemplo de Poker e lembrei de algumas
> questões que envolve a imensidão de possibilidades que existem na hora
> de embaralhar um baralho tradicional.
>
> São 52! (fatorial) que é 2^225 possibilidades[1] totalizando em
>
> 80,658,175,170,943,878,571,660,636,856,404,000,000,000,000,000,000,000,000,000,
> 000,000,000[2] encontrei até um artigo falando sobre como um
> desenvolvedor manipula um jogo de poker mal feito[4].
>
> Os clubes mais conhecidos[3,4] tem uma página falando sobre isso, vi
> no site do desenvolvedor argumentos que pra gerar todas as
> possibilidades seria preciso 225 bits e que, por exemplo, o
> PartyPoker[4] e ele informa que só usa 32 bits.
>
> Há até entidades certificadoras da aleatoriedade dos algoritmos.
>
> Fica a dúvida, qual a distribuição que o random do Python usa? Dá pra
> fazer um programa simples aleatório o suficiente para o jogo de Poker
> não ficar previsível? Teria que usar C pra escovar bits ou coisa do
> gênero?
>
> Abraços!
>
> [1] - http://en.wikipedia.org/wiki/Shuffling#Randomization
> [2] - http://www.pokerstars.com/poker/room/features/security/
> [3] - http://www.partypoker.com/about_us/game_fairness/r_n_g.html
> [4] - http://www.cigital.com/papers/download/developer_gambling.php
>
> --
> Danilo Cabello
> Bottom-posting em prol da comunidade.
>  
>



--
Lucas de Oliveira Gonçalves
Bacharelado em Sistemas de Informação
Conselheiro - Diretório Acadêmico do curso de Sistemas de Informação -
http://dasisucs.wordpress.com/
Universidade de Caxias do Sul


[As partes desta mensagem que não continham texto foram removidas]



------------------------------------

,-----------------------------------------------------------.
| Antes de enviar um e-mail para o grupo leia:              |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar  |
| E se você é usuário do BOL lembre-se de cadastrar o       |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´Links do Yahoo! Grupos

<*> Para visitar o site do seu grupo na web, acesse:
    http://br.groups.yahoo.com/group/python-brasil/

<*> Para sair deste grupo, envie um e-mail para:
    [hidden email]

<*> O uso que você faz do Yahoo! Grupos está sujeito aos:
    http://br.yahoo.com/info/utos.html


Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Carlos Ribeiro
In reply to this post by Magno Junior
2010/8/3 Magno Junior <[hidden email]>

> Por que gerar número aleatório é tão difícil?
>

É difícil, mas mais do que difícil, é contra intuitivo. Para o ser humano
qualquer série maluca de números parece randômica, quando pode ter padrões
ocultos que uma série matemática explica. O conceito não entra direito na
nossa cabeça.

Aproveitando o ensejo, pesquisando um pouco, achei uma referência útil para
testar a "randomicidade" de uma série de números qualquer:

http://www.fourmilab.ch/random/
"This page describes a program, ent, which applies various tests to
sequences of bytes stored in files and reports the results of those tests.
The program is useful for evaluating pseudorandom number generators for
encryption and statistical sampling applications, compression algorithms,
and other applications where the information density of a file is of
interest."

--
Carlos Ribeiro
Consultoria em Projetos
twitter: http://twitter.com/carribeiro
blog: http://rascunhosrotos.blogspot.com
mail: [hidden email]


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Danilo Cabello
Não tenho como dar quote em todos os e-mails, mas gostaria de
agradecer a colaboração de vocês, fiquei abismado com a riqueza das
informações em volta do assunto, com certeza aprendi sobre o assunto e
ganhei algumas referências, vou partir pra uma solução inicialmente
simples, mas sem ser com o random.shuffle do Python e depois evoluir
ela e testar a entropia conforme indicado.

Muito obrigado!
Abraços,
Danilo Cabello
Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Douglas Drumond
In reply to this post by Carlos Ribeiro
>
>
> > Por que gerar número aleatório é tão difícil?
> >
>
> É difícil, mas mais do que difícil, é contra intuitivo. Para o ser humano
> qualquer série maluca de números parece randômica, quando pode ter padrões
> ocultos que uma série matemática explica. O conceito não entra direito na
> nossa cabeça.
>
>
Um exemplo real e um fictício (mas que poderia ser real) para essa contra
intuição: não lembro se foi na primeira versão do iPod (aquele que só
sincronizava com Macs) ou se foi no primeiro iPod shuffle, a função para
músicas aleatórias era muito mais aleatória que a atual. Mas gerou
reclamações porque ocorriam repetições e as pessoas achavam que não era
aleatória. O algoritmo foi mudado.

O segundo exemplo ocorre no seriado Numb3rs, se não me engano no primeiro
episódio da primeira temporada: Charles (o matemático e personagem
principal) pede para um grupo de pessoas se espalharem aleatoriamente pela
sala. Depois ele pede para elas observarem o que fizeram e vêem que, na
verdade, elas ficaram igualmente espaçadas umas das outras. Ele comenta que
se fosse realmente aleatório, haveria agrupamentos.

A percepção que temos de aleatório é confusa. Vemos padrões onde não existem
(há uma palestra no TED sobre isso, não lembro o título) e às vezes não
vemos padrões onde existem.


[As partes desta mensagem que não continham texto foram removidas]

Reply | Threaded
Open this post in threaded view
|

Re: Embaralhando com Python: por onde começar?

Paulo Eduardo Neves-3
In reply to this post by Danilo Cabello
Em 3 de agosto de 2010 00:02, Danilo Cabello
<[hidden email]> escreveu:
> Dá pra
> fazer um programa simples aleatório o suficiente para o jogo de Poker
> não ficar previsível? Teria que usar C pra escovar bits ou coisa do
> gênero?

A discussão foi toda interessante e realmente gerar números totalmente
aleatórios em um computador é complicadíssimo, mas acho que para um
jogo de poker é mais do que suficiente. O importante é você escolher
uma boa semente (normalmente o tempo) e adicionar um sal secreto.

Claro que a dica não vale se seu jogo tiver uma grande recompensa a
ser ganha, a ponto de atrair matemáticos hackers sofisticados.

abs

--
Paulo Eduardo Neves
http://www.mosquito.pro.br