Antes de jogar, a IA precisa encontrar seu lance dentro de um palheiro de cento e cinquenta mil palavras, e depois parar de procurar.
Escrito e editado em inglês. Esta versão em português foi produzida por tradução automática; quando a precisão importa, o original em inglês é a referência. Ler o original em inglês →
Dê a uma pessoa um conjunto completo de peças do WordChess e a instrução “jogue uma boa palavra”, e ela estreita o problema sem perceber que o fez. O computador não desfruta de nenhuma intuição assim. Num tabuleiro de 25×25, com um conjunto completo de cem peças só seu, ele pode tentar quase qualquer uma das 148.941 palavras do dicionário, e cada palavra pode ser colocada em milhares de coordenadas e orientações legais. Pior: uma jogada só é legal se cada letra nova que ela introduz também completar uma palavra real onde cruza o que já está no tabuleiro. Multiplique as palavras pelas posições e por essa restrição de cruzamento e você terá um espaço de busca que nenhum jogador, de silício ou não, consegue enumerar e classificar por inteiro.
É por isso que os motores sérios de jogos de palavras, entre eles o Quackle, a implementação de referência de código aberto, nunca percorrem o dicionário por força bruta. 4 A estrutura GADDAG de Steven Gordon, de 1994, e antes dela o DAWG, permitem que um programa faça as palavras crescerem a partir das peças já presentes no tabuleiro e verifique os cruzamentos durante o processo, de modo que os ramos ilegais morram cedo em vez de serem pontuados e descartados. 1 A tarefa não é “listar todas as palavras”. É “gerar apenas os lances que poderiam ser legais, e fazê-lo depressa”.
Mesmo um gerador enxuto devolve mais lances candidatos do que é possível avaliar a fundo, então o segundo problema é o tempo. O Maven, de Brian Sheppard, o primeiro programa a superar adversários humanos de ponta, enfrentou exatamente isso e respondeu em duas etapas: uma heurística rápida ordena as jogadas brutas por qualidade aproximada, e só uma lista curta das mais promissoras é estudada com cuidado, simulando a partida adiante muitas vezes para ver qual candidata de fato se sai melhor. 2 Outros jogos conhecem a mesma ideia por outros nomes, o “rollout” do gamão e o “playout” dos programas de Go; no Maven, ela se chama simulação.
O WordChess trabalha no mesmo espírito, sob uma restrição mais rígida: um orçamento fixo de tempo de busca por lance. Quando o orçamento se esgota, a IA se compromete com a melhor palavra encontrada até então. Não é uma concessão que os engenheiros lamentam; é o projeto inteiro. Um jogador que pensa para sempre não é um adversário melhor, apenas mais lento. O relógio obriga a máquina a fazer o que as pessoas fazem por instinto: contentar-se com um lance claramente bom em vez de um comprovadamente ótimo.
Conhecer o dicionário é a parte fácil. Saber quando parar de vasculhá-lo é a difícil.
O jeito preguiçoso de facilitar uma IA de jogo é torná-la burra ao acaso, fazê-la errar um lance que ela claramente viu. Os jogadores percebem, e se ressentem. O designer Sid Meier é frequentemente citado por ter cortado de Civilization recursos de alianças porque o computador conseguia explorá-los quase tão bem quanto um jogador; o efeito, nas palavras de Meier citadas por um relato sobre o design de adversários com IA, seria “deixar os jogadores com a sensação de que não podiam vencer porque o computador estava trapaceando”. 3 Uma dificuldade que parece desonestidade envenena o jogo, e é por isso que a literatura de pesquisa sobre ajuste dinâmico de dificuldade se ocupa de calibrar aquilo de que a IA é capaz, e não aquilo que ela tem permissão para ver. 5
O WordChess calibra seus quatro níveis ao longo de eixos que um humano reconheceria, nunca alimentando a IA com informação oculta. Os níveis diferem em quanto tempo podem buscar, em quão fundo seu vocabulário alcança no dicionário de palavras raras e em quais faixas de comprimento de palavra eles preferem. Um adversário fácil joga palavras plausivelmente fracas: reais, sensatas, curtas, não lixo. Um grão-mestre compartilha todo o léxico obscuro com o nível difícil e tem o maior tempo para garimpá-lo. O jogador perde para algo que parece um vocabulário melhor e uma leitura mais afiada, porque é exatamente isso que é.
| Nível | Alcance do vocabulário | Orçamento de busca | Tendência de comprimento |
|---|---|---|---|
| Fácil | Só comuns | O mais curto | Curtas |
| Normal | Comuns + intermediárias + metade das raras | Curto | Variadas |
| Difícil | Completo | Longo | Mais longas |
| Grão-mestre | Completo | O mais longo | Sem limite |
Uma calculadora devolve a mesma resposta todas as vezes; um adversário surpreende você. O WordChess acrescenta à seleção uma etapa deliberadamente aleatória, para que lances quase equivalentes nem sempre sejam decididos da mesma forma e a IA não repita a mesma palavra toda vez. Somado aos tetos de vocabulário de cada nível, o efeito é variedade: a sensação de que há alguém sentado do outro lado do tabuleiro fazendo escolhas, algumas das quais você também poderia ter feito.
Essa é a arte discreta da coisa. Um adversário crível precisa tanto de contenção quanto de força: a disposição de jogar uma palavra apenas boa, de deixar pontos na mesa, de ser vencível de um jeito que pareça merecido. O problema de engenharia mais difícil da máquina foi vasculhar o palheiro. O mais sutil foi aprender quando parar de procurar, o que saber e quanto se conter.