Algoritmo de embaralhamento das cartas do Freecell no Windows

Muita gente provavelmente já jogou o Freecell do Windows, que organiza as cartas aleatoriamente, e cada arranjo de cartas recebe um número. Ao escolher o mesmo número, as cartas são dispostas da mesma forma.

Até o Windows 2000, existiam jogos numerados de 1 a 32.000, mas a partir do XP esse total foi ampliado para 1.000.000.

O algoritmo que gera a disposição das cartas quando um número é inserido é público, e por isso também é usado em outros programas de Freecell.

Esse algoritmo foi implementado em um pequeno código C e depende das funções rand() e srand() implementadas no compilador da MS.

[valorqueen]

Tag hyung, você joga muito bem.

[qdr7h]

O algoritmo original de geração de números aleatórios parece ser random, mas na verdade usa uma fórmula de recorrência que produz uma sequência de números pseudoaleatórios. Cada implementação da função rand() varia, mas quase todos os algoritmos compartilham a característica de que, se a seed inicial for a mesma, a sequência de números gerada depois também será idêntica. Portanto, se o algoritmo de distribuição das cartas for determinístico, todas as distribuições de cartas acabam sendo determinadas de forma determinística pela seed.

Fugindo um pouco do tema, a questão de até que ponto é possível gerar números pseudoaleatórios que pareçam realmente aleatórios também foi, por muito tempo, um tema de pesquisa. O TAOCP Vol.2 também aborda isso brevemente.

[kandk]

Na verdade, não existe o conceito de aleatoriedade em computadores.
Por isso, normalmente mede-se o comportamento humano em milissegundos e isso é usado como seed aleatória.

[dlehals2]

Eu achava que os números aleatórios usavam o timestamp da hora atual, então eu estava enganado haha. Obrigado por compartilhar.

[regentag]

Ao inicializar, muita gente costuma usar o tempo como seed. Afinal, o tempo está sempre mudando.

[regentag]

Como referência, na ajuda do Windows está escrito: “Embora isso não tenha sido provado, todos os jogos jogados aqui têm solução”, mas, segundo as tentativas de várias pessoas, o jogo nº 11982 é conhecido até agora como impossível de vencer.

Mesmo além do nº 32.000, há arranjos de cartas conhecidos como impossíveis de vencer, como os de nº 146692, 186216, 455889, 495505, 512118, 517776 e 781948.

[namojo]

Nossa, como será que descobriram como registrar isso e ainda assim não conseguir resolver? Tem muita gente obstinada mesmo!

[bakyeono]

Que gente assustadora...!