The Winnability of Klondike Solitaire and Many Other Patience Games

O artigo apresenta o "Solvitaire", um programa de inteligência artificial de propósito geral que utiliza técnicas de busca e otimização para determinar com alta precisão a porcentagem de vitórias de 73 variantes de 35 jogos de paciência, incluindo o Klondike, oferecendo resultados novos ou significativamente aprimorados em relação ao conhecimento anterior.

O essencial

Imagine que o mundo dos jogos de cartas de paciência (como o famoso "Solitário" do Windows) é uma vasta floresta cheia de caminhos secretos. Durante mais de 200 anos, os jogadores sempre se perguntaram: "Será que esta mão específica que recebi é possível de ganhar?" ou "Quantas vezes, em média, eu consigo vencer?"

A resposta para essa pergunta, especialmente para o jogo clássico Klondike, foi considerada um dos grandes "embaraços" da matemática aplicada. Ninguém sabia exatamente a porcentagem de vitórias com precisão.

Neste artigo, dois pesquisadores (Charlie Blake e Ian Gent) apresentaram uma solução brilhante: um "super-robô" chamado Solvitaire.

Aqui está a explicação do que eles fizeram, usando analogias simples:

1. O Problema: A Floresta Escura

Pense em cada jogo de paciência como uma montanha russa gigante. Às vezes, o trilho leva ao topo (vitória), e às vezes, ele termina num buraco (derrota). O problema é que existem trilhos infinitos.

• O Klondike: É o jogo mais famoso. Sabíamos que era possível ganhar, mas não sabíamos se era 50% das vezes, 80% ou 90%. As estimativas anteriores eram como tentar adivinhar o tempo de amanhã olhando apenas para o céu: "acho que vai chover" (mas com uma margem de erro enorme).
• O Desafio: Existem centenas de variações de paciência. Fazer um programa diferente para cada jogo seria como construir uma chave diferente para cada fechadura do mundo.

2. A Solução: O "Canivete Suíço" (Solvitaire)

Os autores criaram o Solvitaire. Em vez de fazer um robô específico para o Klondike, outro para o Spider e outro para o FreeCell, eles criaram um robô universal.

• A Linguagem Mágica: Eles inventaram uma linguagem simples (como um formulário em JSON) onde você descreve as regras do jogo. É como dar instruções a um cozinheiro: "Use 52 cartas, faça 7 pilhas, permita mover cartas vermelhas sobre pretas". O Solvitaire lê essas regras e aprende a jogar aquele jogo específico instantaneamente.
• A Abordagem: Eles não tentaram apenas "adivinhar" a resposta jogando milhões de vezes (o que é lento e impreciso). Eles usaram uma busca exaustiva inteligente. Imagine que você está em um labirinto. Em vez de correr aleatoriamente, o Solvitaire usa um mapa mental para garantir que ele explore todos os caminhos possíveis, sem repetir o mesmo caminho duas vezes.

3. As Ferramentas do Detetive (Técnicas de IA)

Para não ficar preso no labirinto por séculos, o Solvitaire usa truques de inteligência artificial:

• Tabelas de Transposição (O Caderno de Anotações): Se o robô já passou por um estado do jogo antes, ele anota no caderno e não volta a tentar. É como não tentar abrir a mesma porta fechada duas vezes.
• Quebra de Simetria (A Regra do Espelho): Se você tem 4 espaços vazios na mesa, eles são todos iguais. Não adianta tentar colocar a carta no espaço 2 se já tentou no espaço 1 e falhou. O robô ignora os espaços "iguais" para economizar tempo.
• Dominâncias (O Pulo do Gato): O robô aprende regras de lógica. Por exemplo: "Se eu puder colocar uma carta na pilha de vitória (fundação), eu devo fazer isso agora, porque não há vantagem em esperar". Isso corta milhares de caminhos inúteis.
• Streamliners (O Filtro Rápido): Às vezes, o robô faz um "palpite inteligente" rápido. Se o palpite funcionar, ótimo! Se não, ele volta e faz a busca completa. É como tentar abrir a porta com a chave rápida antes de chamar o chaveiro.

4. Os Resultados: A Verdade Revelada

O Solvitaire analisou 73 variações de 35 jogos diferentes. Os resultados foram surpreendentes:

• Klondike (O Clássico): Com a regra "pensativa" (onde você sabe onde todas as cartas estão, mesmo as viradas para baixo), a chance de vitória é de 81,945%.
  • O que isso significa? Antes, a margem de erro era enorme (como dizer "entre 70% e 90%"). Agora, eles reduziram essa margem para menos de 0,1%. É como passar de "acho que é azul" para "é exatamente azul royal, código #4169E1".
• Outros Jogos: Eles descobriram que jogos como o British Canister são quase impossíveis de ganhar (menos de 0,0002% de chance), enquanto o FreeCell é quase sempre vencível (99,998%).
• Correção de Erros: Ao comparar seus resultados com outros programas famosos, eles descobriram que os outros robôs tinham "bugs" (erros de lógica) e estavam dando respostas erradas em casos raros. O Solvitaire corrigiu esses erros.

5. Por que isso importa?

O artigo começa com uma história engraçada: o método de "Monte Carlo" (usar sorte para calcular probabilidades) foi inventado pelo matemático Stanislaw Ulam enquanto ele estava entediado jogando paciência na cama, tentando descobrir a chance de ganhar.

• O Legado: Mais de 70 anos depois, este artigo finalmente responde à pergunta que Ulam fez, mas com uma precisão que ele só poderia sonhar.
• A Lição: Mostrou que uma única inteligência artificial, bem projetada, pode resolver problemas complexos em muitas áreas diferentes, sem precisar ser reprogramada do zero para cada novo desafio.

Em resumo: Os autores construíram um "super-juiz" de jogos de cartas. Eles não apenas disseram quantas vezes você ganha no Klondike, mas provaram matematicamente que a resposta é 81,945%, acabando com décadas de especulação e mostrando que, na maioria das vezes, se você não ganha, é culpa do sorteio das cartas, não da sua habilidade!

Resumo técnico

1. O Problema

O artigo aborda a questão fundamental da winnability (probabilidade de vitória) em jogos de paciência (solitários) de um único jogador. Apesar de serem passatempos populares há mais de 200 anos, a porcentagem exata de vitórias para a maioria das variantes permanece desconhecida ou baseada em estimativas imprecisas.

• O "Embaraço": A ignorância sobre a winnability do Klondike (o jogo padrão do Windows Solitaire) foi descrita anteriormente como "um dos embaraços da matemática aplicada".
• Desafios: A complexidade do espaço de estados, a presença de cartas ocultas (em variantes não "pensativas") e a necessidade de busca exaustiva para provar que um jogo é impossível de vencer tornam o problema computacionalmente difícil.
• Limitações Anteriores: Estudos anteriores geralmente focavam em um único jogo ou utilizavam solvers especializados para famílias pequenas de jogos, muitas vezes com intervalos de confiança estatística amplos ou baseados em heurísticas incompletas.

2. Metodologia

Os autores desenvolveram e utilizaram um solver de propósito geral chamado Solvitaire, baseado em busca de profundidade (Depth-First Search - DFS) com retrocesso (backtracking), combinado com diversas técnicas de Inteligência Artificial para otimização.

Características Principais do Solvitaire:

• Linguagem de Regras Flexível: O solver não possui regras "hard-coded". As regras dos jogos são descritas em formato JSON, permitindo que o mesmo motor resolva uma vasta gama de variantes (Klondike, FreeCell, Spider, etc.) sem reescrever o código.
• Abordagem "Thoughtful" (Pensativa): Para lidar com cartas ocultas, o estudo foca na variante "thoughtful", onde o jogador conhece a posição e o valor de todas as cartas desde o início. Isso transforma o problema em um problema de busca determinística, permitindo a prova exata de winnability.
• Técnicas de Otimização de Busca:
  • Tabelas de Transposição: Armazenam estados visitados para evitar rebuscas redundantes.
  • Quebra de Simetria: Reduz o espaço de busca tratando pilhas e células vazias como indistinguíveis quando as regras permitem.
  • Dominâncias (Dominances): Técnicas que permitem descartar movimentos legais sem perder soluções válidas. O artigo fornece as primeiras provas formais de correção para duas dominâncias críticas:
    1. Movimentos Seguros para Fundações: Mover cartas para as fundações quando é matematicamente seguro fazê-lo.
    2. Movimentos de Pilhas Incompletas: Restringir o movimento de sub-pilhas no tabuleiro apenas se a carta acima puder ser movida imediatamente para a fundação.
  • Streamliners: Heurísticas que aceleram a busca assumindo propriedades que podem não ser verdadeiras em todas as soluções (ex: forçar movimentos para fundações), mas que são revertidas se falharem, garantindo a completude do resultado final.
• Método de Monte Carlo Simples: Para estimar a porcentagem de winnability, o sistema gera milhares de instâncias aleatórias e as resolve. A taxa de sucesso é calculada com intervalos de confiança de 95%.

3. Principais Contribuições

• Generalização: Demonstra que um único solver genérico pode superar ou igualar solvers especializados em uma vasta gama de jogos, algo inédito na literatura.
• Provas de Correção: Fornece as primeiras provas matemáticas rigorosas para dominâncias amplamente utilizadas na comunidade de solvers de paciência, validando sua segurança e eliminando a dependência de suposições empíricas.
• Descoberta de Bugs: Através da comparação cruzada com solvers existentes (como os de Jan Wolter para Canfield e Matt Birrell para Klondike), o Solvitaire identificou e corrigiu bugs sutis e dominâncias incorretas nos códigos de outros pesquisadores.
• Análise de Variantes: Realizou um estudo extensivo sobre como pequenas alterações nas regras (ex: tamanho do "draw", permissão de "worrying back" - devolver cartas da fundação para o tabuleiro) afetam drasticamente a winnability.

4. Resultados

O estudo analisou 73 variantes de 35 jogos diferentes, utilizando cerca de 30 anos de tempo de CPU.

• Klondike (O Resultado Principal):
  • Para a variante "thoughtful" (cartas conhecidas), a winnability foi calculada como 81,945% ± 0,084%.
  • Isso representa uma redução de 30 vezes no intervalo de confiança em relação ao melhor resultado anterior.
  • Foi demonstrado que a permissão de "worrying back" aumenta a winnability em cerca de 0,4% a 0,5% dependendo do tamanho do "draw".
• Outros Jogos:
  • Resultados novos ou significativamente aprimorados foram obtidos para jogos como Canfield (71,245% ± 0,031%), FreeCell (99,998881% ± 0,000207%), Black Hole, Spider, e muitos outros.
  • Para jogos como British Canister, a winnabilidade é extremamente baixa (~0,000129%), provando que a intuição popular de que são "jogos fáceis" está errada.
• Desempenho: O Solvitaire demonstrou ser competitivo ou superior aos solvers especializados em Klondike e FreeCell, embora tenha ficado ligeiramente atrás no Canfield (devido a otimizações específicas de domínio no solver concorrente).

5. Significado e Conclusão

• Resolução de um Problema Clássico: O trabalho cumpre a visão original de Stanislaw Ulam, que inventou o método de Monte Carlo justamente para estimar a winnability de jogos de paciência. Agora, com precisão estatística alta, essa questão é respondida para dezenas de jogos.
• Validação de IA em Jogos de Um Jogador: Demonstra que técnicas gerais de IA (busca, tabelas de transposição, dominâncias) são poderosas o suficiente para resolver problemas complexos de jogos de cartas, superando a necessidade de heurísticas específicas para cada jogo.
• Impacto na Comunidade: A disponibilidade do código de código aberto (Solvitaire) e dos dados experimentais permite que a comunidade científica e entusiastas verifiquem, reproduzam e expandam os resultados.
• Limitações e Futuro: O estudo focou na variante "thoughtful". A winnability real do Klondike (sem ver cartas ocultas e sem "undo") permanece um problema aberto e muito mais difícil, servindo como um desafio para pesquisas futuras.

Em suma, o artigo estabelece um novo padrão de precisão e generalidade na análise computacional de jogos de paciência, combinando rigor matemático (provas de dominâncias) com poder computacional massivo.