Qual é o melhor algoritmo para jogar o jogo da forca jogo de palavras?

Question

Suponha que estamos jogando o jogo jogo da forca.O meu adversário e eu ambos temos acesso ao dicionário durante o jogo.Meu adversário escolhe uma palavra do dicionário com o conhecimento do algoritmo que vou usar para adivinhar a sua palavra secreta.Uma vez que o meu adversário escolheu uma palavra, eu tenho apenas o comprimento da palavra.Eu posso adivinhar uma carta que eu acho que vai ser na palavra, e se ele é a palavra, o meu adversário identifica todas as posições do que a letra na palavra.Se eu acho que uma letra que não está na palavra, que é contado como um erro.Se eu adivinhar a palavra antes de muitos erros, o que eu ganhar.

Do meu adversário meta deve ser a de escolher uma palavra que maximiza o número de erros (incorreta suposições) que eu faça antes que eu possa adivinhar a palavra.Meu objetivo é minimizá-los.(Tradicionalmente, se o número de erros é > algum número, então eu perder o jogo, mas podemos relaxar esta restrição.)

Considere três algoritmos para a carta de adivinhação.Estes são os principais que eu pensei, mas provavelmente existem mais, e eu de boas-vindas alternativo ideias.Em todos os três algoritmos, o primeiro passo será coletar a lista de palavras que são do mesmo comprimento que a palavra secreta.Em seguida, para cada letra do alfabeto, contar o número de palavras no dicionário que contém essa letra.Por exemplo, talvez 5000 conter "a", 300 conter "b", e assim por diante.Aqui está ele, em python:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

Depois que é onde os três algoritmos são divergentes.

1. No primeiro algoritmo, podemos adivinhar a carta que o maior número de palavras restantes contêm.Então, se 5000 palavras restantes contêm "um" e não outras letras são, em tantas palavras, vamos escolher "um" de cada vez.Se "a" é correta, isto nos dá a informação posicional que podemos filtrar a lista.Por exemplo, podemos filtrar a lista por todas as palavras que correspondem ".a..".(Pontos são desconhecidos letras.) Se "a" é incorreta, nós filtrar todas as palavras que contêm "um".No caso de existir um empate e duas letras são encontradas em um número igual de palavras, letras são escolhidas por ordem alfabética.Então, se sabemos que a palavra corresponde a ".sempre", vamos simplesmente adivinhar palavras em ordem alfabética.

2. Este é apenas um pouco diferente do primeiro algoritmo.Em vez de sempre escolher a ordem alfabética, no caso de empate, escolhemos letras aleatoriamente.Isto tem a vantagem de que o nosso adversário não sabe o que vai escolher.Na primeira estratégia, os "raios" é sempre melhor do que "dias".Isso evita que o problema.

3. Neste caso, escolhemos letras com probabilidade proporcional ao número de palavras que contenham a letra.No início, quando nós computados o número de palavras que contêm "a" e o número que contêm "b" e assim por diante, desde o "que" passou a ser encontrado em o maior número de palavras, nas estratégias 1 e 2 nós escolhemos "a" 100% do tempo.Em vez disso, temos ainda vai escolher "um" de uma pluralidade de tempo, mas um pequeno número de vezes que vamos escolher "z" mesmo que um pode ser encontrado em 10x de mais palavras.Eu tenho minhas dúvidas sobre esta estratégia óptima, mas ele foi usado na pesquisa em 2010.

Então, eu tenho duas perguntas:

1. O que é a melhor carta de adivinhação de estratégia que eu deveria usar assumindo que o meu adversário sabe que eu vou usar essa estratégia?Nesta queremos minimizar o número médio de tentativas que vai demorar para adivinhar a palavra secreta.
2. Para uma determinada palavra, dizer que "paga", que é o número médio de erros M eu deveria esperar?Existe uma forma fechada de forma a calcular M, como oposição à execução esta simulação muitas vezes e fazendo uma média dos resultados?

Esclarecimentos

• Qualquer dicionário de inglês pode ser usado.Por exemplo, este dicionário de inglês com 84k palavras..Subconjuntos de dicionários cuidadosamente escolhido para a ambiguidade também pode ser interessante, mas estão fora do escopo desta questão.
• Não há nenhuma restrição sobre o tamanho de palavra enquanto palavra está no dicionário.O adivinhar marcas vai saber o tamanho de palavra, antes de ele começa a adivinhar.
• Apenas o número total de erros matéria, que é independente do tamanho de palavra.Você não conseguir mais chances de palavras mais ou menos possibilidades para menores.
• Estou apenas interessado em minimizar o número médio de erros.Se há dois ideal de algoritmos que possuem uma equivalentemente pequeno número médio de erros, ambas são aceitáveis.
• Em princípio, é possível haver uma situação onde a escolha de uma letra (digamos, "b") leva a mais informações do que a outra (digamos, "um"), apesar de "um", ocorre em mais de palavras do que "b" não.Estou aberto a esta possibilidade, na prática, como bem.Os três algoritmos ilustrado acima partem do princípio de que isso não acontece devido ao fato de que uma suposição correta tende a render mais informações do que um incorreta (por exemplo,informações de posicionamento sobre a letra correta é geralmente melhor do que "esta carta não está na palavra").Mas um algoritmo ótimo não precisa fazer essa suposição.

Answer 1

É possível calcular a melhor estratégia, mas o cálculo pode ser bastante intenso, e eu não tenho certeza se ele vai dar um grande ganho mais simples heurísticas.Vou explicar como abaixo.A idéia principal é utilizar programação dinâmica.

Determinista estratégias

Deixe-me começar com o caso especial da determinista estratégias para a escolha de qual letra que adivinhar próxima, como eles são mais fáceis de analisar.Isso nos dará um aquecimento antes de passarmos à randomizados estratégias (que provavelmente será superior).

O estado do jogo em qualquer ponto pode ser resumido pelo par $(g,r)$, onde $g$ é o conjunto de letras que foram adivinhou até agora, e $r$ é as respostas (por exemplo, a seqüência de espaços em branco e letras de $g$ que é visível para o leitor).A ordem dos últimos palpites não importa (é por isso que basta ter um conjunto de $g$ do passado palpites).Vamos dizer que uma palavra $w$ é consistente com $(g,r)$ se ele continua a ser possível, por exemplo, se o adversário é a palavra do $w$ e fazer as estimativas $g$, então você gostaria de obter a resposta $r$.

Deixe $p(g,r)=1$ se é possível ganhar a partir daqui, se iniciando a partir do estado $(g,r)$.O que significa que existe uma estratégia para vencer:onde não importa qual o word, o adversário é o pensamento de (contanto que ele é consistente com $(g,r)$), o número de errado tentativas que você fez até agora, mais o número que você faça no futuro, com esta estratégia, não excede o limite superior.Caso contrário, definir $p(g,r)=0$.

Agora você pode calcular $p(g,r)$ com programação dinâmica, usando a relação de recorrência

$$p(g,r) = \bigvee_a \bigwedge_{(g',r')} p(g',r'),$$

onde $a$ intervalos de mais de todas as letras, não em $g$ (por exemplo, todas as possibilidades para a qual a letra que adivinhar próxima), e $(g',r')$ intervalos de mais de todas as respostas possíveis se você adivinhar $a$ no próximo (por exemplo, $g'=g\cup \{a\}$, e nós gama de mais de todas as palavras $w$ que são consistentes com $(g,r)$ e calcular a resposta r$'$ para as estimativas g$'$ se a palavra é $w$).

Em particular, eu sugiro que você calcular $p(g,r)$ usando a pesquisa de profundidade-primeiro e memoization.Em seguida, $p(\emptyset, - - \cdots -)$ vai dizer se é possível ganhar dentro do limite superior, não importa o que a palavra que o oponente escolhe.Traçando o cálculo para trás, você pode reconstruir a estratégia ideal.

É isto possível?Eu esperava que ele é.Eu acho que o número de estados possíveis $(g,r)$ não é muito grande.(Em particular, você pode ignorar estados $(g,r)$ onde você já fez muitas suposições incorretas, e qualquer estado, onde apenas uma palavra, é consistente com o estado é automaticamente uma vitória, então ele não precisa de mais análise.) Como uma optimização, dado um estado $(g,r)$, você pode tentar enumerar todas as palavras $w$ que são consistentes com eles e simular algumas fixo heurística e verificar se ele vai ganhar para cada palavra;se assim for, você não precisa fazer mais alguma profundidade-primeiro transversal e você pode imediatamente marca $p(g,r)=1$.Além disso, você só precisa considerar as estimativas $a$ que aparecem em pelo menos uma palavra que é consistente com $(g,r)$.

Portanto, ele deve ser bastante simples para calcular o ideal determinista estratégia.

Randomizados estratégias

Podemos seguir um método semelhante para lidar com randomizados estratégias, mas ele fica um pouco mais envolvido.Agora vamos $p(g,r)$ denotar a probabilidade de ganhar a partir de aqui, se usar o melhor de estratégias a partir de agora.Podemos voltar a calcular esta usando programação dinâmica.

A principal diferença está na relação de recorrência, onde calculamos $p(g,r)$ a partir das quantidades $p(g',r')$ onde $(g',r')$ alcance sobre todos os estados, que podem ocorrer a próxima depois de adivinhar mais uma carta.Aqui temos um simples jogo de dois jogadores.Primeiro vamos escolher uma distribuição de probabilidade sobre as letras não $g$.Em seguida, o adversário vê a nossa distribuição, e escolhe uma distribuição em palavras $w$ que são consistentes com $(g,r)$.O nosso pagamento de salários (e a quantidade que o adversário perde) é igual à probabilidade de que podemos ganhar a partir de agora as escolhas.Repare que isto pode ser calculada a partir do $p(g',r')$ valores.Acontece que, desde que ir primeiro e o oponente vê a nossa escolha, o adversário não precisa de um estudo randomizado estratégia;eles podem fazer igualmente bem com uma estratégia determinista, isto é, escolhendo uma única palavra $w$ com base em nossa distribuição.Em seguida, se formar uma matriz $M$ onde $M_{s,i}$ possui a probabilidade de ganhar se escolhermos a letra $i$ e o oponente escolhe palavra $w$;podemos preencher $M_{s,i}$ como $p(g',r')$ onde $g'=g \cup \{i\}$ e r$'$ é a resposta para adivinhar g$'$ se a palavra é $w$.Em seguida, procuramos resolver o problema de otimização $$\max_v \min_w (Mv)_w = -\min_v \max_w -(Mv)_w = -\min_v \|-Mv\|_\infty.$$ Isso pode ser resolvido usando programação linear.Assim, podemos calcular $p(g,r)$ usando programação linear a partir dos valores $p(g',r')$ onde g$'$ é maior do que $g$.

Colocando tudo isso junto, vamos usar o primeiro profundidade transversal com memoization (ou programação dinâmica), utilizando-se de programação linear em cada passo para resolver o jogo com 2 jogadores.Isto dá-nos o ideal randomizados estratégia para jogar jogo da forca.

A resultante do cálculo pode ser muito caro, pois exige bilhões ou trilhões de passos, onde você deve solucionar um programa linear em cada etapa.Então, eu não sei se é realista para usá-lo em prática.

Algumas otimizações são possíveis, como sugerido por @j_random_hacker.Primeiro você pode calcular $p(g,r)$ para determinista estratégias;em seguida, você só precisa considerar randomizados estratégias para os estados $(g,r)$ onde $p(g,r)=0$.

Heurística estratégias

Você listados alguns razoável heurísticas para a escolha de uma estratégia.Aqui está mais uma heurística.Dado o estado $(g,r)$, enumerar todas as possibilidades para o próximo acho que $a otin g$.Vamos nos concentrar em uma única carta $a$.Então, para cada $(g',r')$ que poderia ocorrer como um estado seguinte depois de adivinhar $a$ (para $g'=g\cup \{a\}$), contar o número de palavras $w$ consistente com $(g',r')$;tirar o máximo sobre esses números, e usar isso como a contagem de associados $a$.A heurística estratégia é escolher a letra $a$ cuja contagem é menor.

Calcular o número esperado de erros

Você pode calcular o número esperado de erros de um determinado randomizados estratégia usando programação dinâmica.Os detalhes são semelhantes ao acima, mas a recorrência relação torna-se mais simples:torna-se

$$p(g,r) = \min_w \mathbb{E}[p(g',r')],$$

onde $w$ intervalos mais consistente com todas as palavras $(g,r)$, e $(g',r')$ é a distribuição no estado seguinte, se a palavra é $w$ e a próxima letra adivinhou é escolhido por sua estratégia.Dada a sua estratégia e a palavra $w$, é fácil calcular a distribuição em suposições e, assim, obter a distribuição no próximo estados, portanto, é fácil calcular $\mathbb{E}[p(g',r')]$.