Criando um gerador de quebra-cabeças procedural

Este post descreve o gerador de nível para o meu jogo de quebra-cabeça Linjat . Uma postagem pode ser lida sem preparação, mas é mais fácil assimilar se você jogar em vários níveis. Publiquei o código fonte no github ; tudo o que foi discutido no artigo está no src/main.cc

Exemplo de plano de postagem:

• Linjat é um jogo de lógica em que você precisa fechar todos os números e pontos da grade com linhas.
• Os quebra-cabeças são gerados proceduralmente usando uma combinação de solucionador, gerador e otimizador.
• O Solver tenta resolver os quebra-cabeças da maneira que uma pessoa faria e atribui a cada quebra-cabeça uma classificação de interesse.
• O gerador de quebra-cabeças é projetado de tal maneira que é possível alterar facilmente uma parte do quebra-cabeça (número), enquanto todas as outras partes (pontos) são alteradas para que o quebra-cabeça permaneça solucionável.
• O otimizador de quebra-cabeças resolve repetidamente os níveis e gera novas variações das mais interessantes encontradas no momento.

As regras

Para entender como o gerador de níveis funciona, você precisa, infelizmente, entender as regras do jogo. Felizmente, eles são muito simples. O quebra-cabeça consiste em uma grade contendo quadrados, números e pontos vazios. Um exemplo:


O objetivo do jogador é desenhar uma linha vertical ou horizontal através de cada um dos números, sujeita a três condições:

• Uma linha através de um número deve ter o mesmo comprimento que o número.
• As linhas não podem se cruzar.
• Todos os pontos devem ser fechados com linhas.

Solução de exemplo:


Viva! O design do jogo está pronto, a interface do usuário está implementada e agora só resta encontrar centenas de bons quebra-cabeças. E para esses jogos, geralmente não faz sentido tentar criar esses quebra-cabeças manualmente. Este é um trabalho de computador.

Exigências

O que torna o quebra-cabeça desse jogo bom? Estou inclinado a acreditar que os jogos de quebra-cabeça podem ser divididos em duas categorias. Existem jogos nos quais você explora um espaço de estado complexo do começo ao fim (por exemplo, Sokoban ou Hora do Rush ) e nos quais pode não ser óbvio quais estados existem no jogo. E há jogos nos quais todos os estados são conhecidos desde o início, e gradualmente modelamos o espaço de estados usando o processo de eliminar os desnecessários (por exemplo, Sudoku ou Picross ). Meu jogo definitivamente se enquadra na segunda categoria.

Os jogadores têm requisitos muito diferentes para esses diferentes tipos de quebra-cabeças. No segundo caso, eles esperam que o quebra-cabeça possa ser resolvido apenas por dedução e que nunca precisarão voltar atrás / adivinhar / tentar e errar ^{[0] [1]} .

Não basta saber se um quebra-cabeça só pode ser resolvido pela lógica. Além disso, precisamos entender de alguma forma como os quebra-cabeças criados são bons. Caso contrário, a maioria dos níveis será apenas escória trivial. Em uma situação ideal, esse princípio também pode ser usado para criar uma curva de progresso suave, para que, à medida que o jogador avance no jogo, os níveis se tornem gradualmente mais difíceis.

Solver

O primeiro passo para atender a esses requisitos é criar um solucionador de jogos otimizado para essa finalidade. O solucionador de retrocesso permite determinar com rapidez e precisão se o quebra-cabeça é solucionável; Além disso, ele pode ser modificado para determinar se a solução é única. Mas ele não pode dar uma idéia de quão complicado é o quebra-cabeça, porque as pessoas os resolvem de maneira diferente. O solucionador deve imitar o comportamento humano.

Como uma pessoa resolve esse quebra-cabeça? Aqui estão alguns movimentos óbvios que o tutorial do jogo ensina:

• Se um ponto puder ser alcançado a partir de apenas um número, para fechar um ponto, você precisará desenhar uma linha a partir desse número. Neste exemplo, o ponto pode ser alcançado apenas entre os três, mas não entre os quatro:
  
  
  
  
  E isso leva a esta situação:
  
  
  
• Se a linha não couber em uma direção, ela deverá ser colocada em outra. No exemplo acima, os quatro não podem mais ser posicionados verticalmente, então sabemos que será horizontal:
  
  
  
• Se for sabido que a linha de comprimento X deve estar em uma determinada posição (vertical / horizontal) e não houver espaço vazio suficiente para colocar uma linha de X células vazias em ambos os lados, será necessário cobrir vários quadrados no meio. Se os quatro fossem três no exemplo mostrado acima, não saberíamos se estenderia todo o caminho para a direita ou esquerda. Mas saberíamos que a linha deve cobrir dois quadrados do meio:
  
  
  

Raciocínio semelhante é a própria base do jogo. O jogador procura maneiras de esticar uma pequena linha e, em seguida, examina o campo novamente, porque pode fornecer informações para outra conclusão lógica. Criar um solucionador que siga essas regras será suficiente para determinar se uma pessoa pode resolver o quebra-cabeça sem voltar atrás.

No entanto, isso não nos diz nada sobre a complexidade ou interesse do nível. Além da solvabilidade, precisamos de alguma forma quantificar a complexidade.

Uma primeira idéia óbvia para a função de classificação: quanto mais movimentos você precisar para resolver o quebra-cabeça, mais difícil será. Essa é provavelmente uma boa métrica em outros jogos, mas a minha, provavelmente, é mais importante do que o número de jogadas permitidas que um jogador possui. Se um jogador pode tirar 10 conclusões lógicas, ele provavelmente encontrará uma delas muito rapidamente. Se houver apenas um movimento certo, levará mais tempo.

Ou seja, como primeira aproximação, precisamos que a árvore de decisão seja profunda e estreita: há uma longa dependência de movimentos do começo ao fim, e a cada momento há apenas um pequeno número de maneiras de subir a cadeia ^[2] .

Como determinamos a largura e a profundidade de uma árvore? Uma solução única para o quebra-cabeça e a avaliação da árvore criada não fornecerá uma resposta exata. A ordem exata em que os movimentos são feitos afeta a forma da árvore. Precisamos considerar todas as soluções possíveis e fazer com elas algo como otimização para os melhores e os piores casos. Eu estou familiarizado com a técnica de pesquisa aproximada de gráficos de pesquisa em jogos de quebra-cabeça , mas para este projeto eu queria criar um solucionador de uma passagem, e não uma pesquisa exaustiva. Devido à fase de otimização, tentei garantir que o tempo de execução do solucionador fosse medido não em segundos, mas em milissegundos.

Eu decidi não. Em vez disso, meu solucionador não faz um movimento de cada vez, mas resolve o quebra-cabeça em camadas: assumindo um estado, ele encontra todos os movimentos válidos que podem ser feitos. Então ele aplica todos esses movimentos ao mesmo tempo e começa de novo em um novo estado. O número de camadas e o número máximo de movimentos encontrados em uma camada são usados ​​como valores aproximados da profundidade e largura da árvore de pesquisa como um todo.

Veja como resolver um dos quebra-cabeças difíceis com este modelo. Linhas pontilhadas são linhas esticadas nessa camada do solucionador, linhas sólidas são aquelas que não foram alteradas. As linhas verdes têm o comprimento correto, as vermelhas ainda não estão completas.


O próximo problema é que todos os movimentos feitos pelo jogador são criados iguais. O que listamos no início desta seção é apenas senso comum. Aqui está um exemplo de uma regra de dedução mais complexa, cuja pesquisa exigirá um pouco mais de reflexão. Considere o seguinte campo:


Os pontos em C e D podem ser cobertos apenas pelos cinco e pelos quatro do meio (e nem um único número pode cobrir os dois pontos ao mesmo tempo). Isso significa que os quatro no meio devem cobrir um ponto de dois e, portanto, não podem ser usados ​​para cobrir A. Portanto, o ponto A deve fechar os quatro no canto inferior esquerdo.

Obviamente, seria tolice considerar essa cadeia de raciocínio igual à simples conclusão de que "este ponto só pode ser alcançado a partir desse número". É possível dar mais peso a essas regras mais complexas na função de avaliação? Infelizmente, em um solucionador baseado em camadas, isso não é possível, porque não é garantido que você encontre uma solução pelo menor custo. Este não é apenas um problema teórico - na prática, muitas vezes acontece que parte do campo pode ser resolvida por um único argumento complexo ou por uma cadeia de movimentos muito mais simples. De fato, um solucionador baseado em camada encontra o caminho mais curto e não menos oneroso, e isso não pode ser refletido na função de avaliação.

Como resultado, cheguei a essa decisão: alterei o solucionador para que cada camada consistisse em apenas um tipo de raciocínio. O algoritmo ignora as regras de raciocínio em uma ordem aproximada de complexidade. Se a regra encontrar algumas jogadas, elas serão aplicadas, a iteração será encerrada e a próxima iteração iniciará a lista desde o início.

Em seguida, a decisão recebe uma avaliação: cada camada recebe custos com base em uma regra que foi usada nela. Isso ainda não garante que a solução seja a mais barata, mas se os pesos forem selecionados corretamente, o algoritmo pelo menos não encontrará uma solução cara se houver uma barata.

Além disso, é muito parecido com o modo como as pessoas resolvem quebra-cabeças. Eles primeiro tentam encontrar soluções fáceis e começam a mover ativamente seus cérebros apenas se não houver movimentos simples.

Gerador

A seção anterior determinou se um determinado nível era bom ou ruim. Mas isso não basta, ainda precisamos gerar níveis para que o solucionador possa avaliá-los. É muito improvável que um mundo gerado aleatoriamente seja solucionável, sem mencionar interessante.

A idéia principal (não é de forma alguma nova) é o uso alternativo do solucionador e do gerador. Vamos começar com um quebra-cabeça, que provavelmente é insolúvel: basta colocar dois a cinco números em quadrados aleatórios da célula:


O Solver funciona até que ele possa se desenvolver ainda mais:


Em seguida, o gerador adiciona mais informações ao quebra-cabeça na forma de um ponto, após o qual a execução do solucionador continua.


Nesse caso, o ponto adicionado ao solucionador não é suficiente para desenvolvimento adicional. Em seguida, o gerador continuará adicionando novos pontos até satisfazer o solucionador:


E então o solucionador continua seu trabalho habitual:


Esse processo continua até que o quebra-cabeça seja resolvido ou até que haja mais informações a serem adicionadas (por exemplo, quando cada célula que pode ser alcançada a partir do número já contém um ponto).

Este método funciona apenas se as novas informações adicionadas não puderem tornar incorretas nenhuma das conclusões feitas anteriormente. Isso seria difícil de fazer ao adicionar números à grade ^[3] . Mas adicionar novos pontos ao campo tem essa propriedade; pelo menos para as regras de raciocínio que eu uso neste programa.

Onde o algoritmo deve adicionar pontos? No final, decidi adicioná-los ao espaço vazio, que pode ser fechado no estado inicial com o maior número possível de linhas, para que cada ponto procure fornecer o mínimo de informações possível. Não tentei colocar especificamente o ponto no local em que seria útil para avançar na solução do quebra-cabeça no momento em que o solucionador fica preso. Isso cria um efeito muito conveniente: a maioria dos pontos no início do quebra-cabeça parece completamente inútil, o que torna o quebra-cabeça mais difícil do que realmente é. Se tudo isso for um monte de jogadas óbvias que um jogador pode fazer, mas por algum motivo, nenhuma delas não funciona corretamente. Como resultado, verificou-se que o gerador de quebra-cabeças se comporta um pouco como um porco.

Esse processo nem sempre cria uma solução, mas é bastante rápido (cerca de 50 a 100 milissegundos); portanto, para gerar um nível, basta repeti-lo várias vezes. Infelizmente, ele geralmente cria quebra-cabeças medíocres. Desde o início, existem movimentos óbvios demais, o campo se enche muito rapidamente e a árvore de decisão acaba sendo rasa.

Optimizer

O processo descrito acima criou quebra-cabeças medíocres. No último estágio, utilizo esses níveis como base para o processo de otimização. Funciona da seguinte maneira.

O otimizador cria um pool que contém até 10 opções de quebra-cabeça. O pool é inicializado com um novo quebra-cabeça aleatório gerado. A cada iteração, o otimizador seleciona um quebra-cabeça da piscina e executa sua mutação.

A mutação exclui todos os pontos e depois altera ligeiramente os números (ou seja, diminui / aumenta o valor de um número selecionado aleatoriamente ou move o número para outra célula na grade). Você pode aplicar várias mutações ao campo ao mesmo tempo. Em seguida, executamos o solucionador no modo de geração de nível especial descrito na seção anterior. Ele adiciona pontos suficientes ao quebra-cabeça para que ele se torne solucionável novamente.

Depois disso, iniciamos o solucionador novamente, desta vez no modo normal. Durante essa execução, o solucionador monitora a) a profundidade da árvore de decisão, b) a frequência da necessidade de diferentes tipos de regras; c) a largura da árvore de decisão em diferentes momentos no tempo. O quebra-cabeça é avaliado com base nos critérios descritos acima. A função de avaliação prefere soluções profundas e estreitas, e níveis de complexidade aumentada também agregam mais peso aos quebra-cabeças nos quais são necessárias regras mais complexas de raciocínio.

Em seguida, um novo quebra-cabeça é adicionado à piscina. Se a piscina contiver mais de 10 quebra-cabeças, o pior será descartado.

Esse processo é repetido várias vezes (aproximadamente 10.000-5.000 iterações me levaram). Depois disso, a versão mais alta do quebra-cabeça é salva no banco de dados no nível do quebra-cabeça. Veja como é o progresso do melhor quebra-cabeça em uma execução de otimização:


Tentei usar outras maneiras de estruturar a otimização. Em uma versão, o recozimento simulado foi utilizado, outros eram algoritmos genéticos com várias operações de cruzamento. Nenhuma das soluções foi executada, assim como um algoritmo ingênuo, com um conjunto de opções voltando ao topo.

Solução única e única

Quando um quebra-cabeça tem uma solução única, surge uma dificuldade interessante. É possível permitir ao jogador assumir que existe uma solução e tirar conclusões com base nisso? Seria justo se o gerador de quebra-cabeças sugerisse que o jogador o fez?

Em um post no HackerNews, eu disse que existem quatro opções para abordar essa situação:

• Declare a exclusividade da solução desde o início e force o gerador a criar níveis que exijam esse tipo de raciocínio. Esta é uma péssima decisão porque complica o entendimento das regras. E geralmente esses são os detalhes que as pessoas esquecem.
• Não garanta a exclusividade de uma decisão: potencialmente, tenha muitas decisões e tome todas elas. De fato, isso não resolve o problema, mas o afasta.
• Apenas suponha que este é um evento muito raro, que na prática não é importante. (Essa é a solução usada na implementação inicial.)
• Mude o gerador de quebra-cabeças para que não gere quebra-cabeças nos quais o conhecimento da singularidade da solução ajudaria. (Provavelmente a solução certa, mas exigindo trabalho adicional.)

Inicialmente, escolhi a última opção, e esse foi um erro terrível. Aconteceu que eu levei em conta apenas uma maneira pela qual a singularidade da solução levou ao vazamento de informações, e na verdade é bastante raro. Mas existem outros; um deles estava de fato presente em todos os níveis que gerava e muitas vezes levava ao fato de que a solução se tornava trivial. Portanto, em maio de 2019, alterei os modos Difícil e Especialista usando a terceira opção.

O caso mais irritante é um empate com uma linha tracejada neste campo:


Por que um jogador astuto pode tirar essa conclusão? Um empate pode cobrir qualquer um dos quatro quadrados vizinhos. Nenhum deles tem pontos, portanto não precisa ser coberto por uma linha. E o quadrado abaixo não tem sobreposições com outros números. Se houver uma solução única, esse deve ser o caso quando outros números cobrirem os três quadrados restantes e os dois fecharem o quadrado abaixo dele.

A solução é adicionar mais alguns pontos ao reconhecer esses casos:


Outro caso comum é um traço com uma linha pontilhada neste campo:


Os quadrados à esquerda e em cima dos dois não são diferentes. Nenhum deles tem um ponto, e nenhum pode ser alcançado a partir de qualquer outro número. Qualquer solução em que um empate cubra o quadrado superior terá uma solução correspondente na qual fecha o quadrado esquerdo e vice-versa. Se houvesse uma única solução única, não seria possível, e o empate deveria ter coberto o quadrado inferior.

Decidi esse tipo de caso da maneira "se doer, não toque". O Solver aplicou essa regra em um estágio inicial da lista de prioridades e atribuiu um peso negativo a esses movimentos. Os quebra-cabeças com esse recurso geralmente são descartados pelo otimizador, e os poucos restantes são descartados no estágio da seleção final de níveis para o jogo publicado.

Esta não é uma lista completa: durante o teste de reprodução com uma busca deliberada por erros, encontrei muitas outras regras para soluções exclusivas. Mas a maioria deles parecia rara e eles eram suficientes para encontrar, então eles não simplificaram muito o jogo. Se alguém resolver o quebra-cabeça usando esse raciocínio, não vou culpá-lo.

Conclusão

Inicialmente, o jogo foi desenvolvido como um experimento na geração processual de quebra-cabeças. O design e o gerador do jogo andaram de mãos dadas, por isso é difícil aplicar as próprias técnicas diretamente a outros jogos.

A pergunta à qual não tenho resposta: o investimento de tais esforços na geração processual se justificou?O feedback dos jogadores sobre o design de níveis foi muito controverso. Nos comentários positivos, costumava-se dizer que alguns truques complicados sempre são sentidos nos quebra-cabeças. Na maioria das críticas negativas, eles me escreveram que o jogo carece de um gradiente de complexidade.

Ainda tenho alguns quebra-cabeças na infância, e gostei tanto do gerador que provavelmente usarei uma abordagem processual semelhante para eles. Vou mudar apenas uma coisa: desde o início, conduzirei testes ativos com a busca de erros.

Anotações

[0] Ou, pelo menos, me pareceu. Mas quando eu assisti os jogadores ao vivo, quase metade deles apenas fez palpites e depois iterou através deles. Oh bem.

[1] Os leitores do meu artigo também devem ler o artigo Resolvendo Campo Minado e melhorando Magnus Hoff.

[2] Esclarecerei que a profundidade / estreiteza de uma árvore é uma métrica que considerei significativa para o meu jogo, e não para todos os outros quebra-cabeças. Por exemplo, há um bom argumento de que o quebra-cabeça da Hora do Rush é interessante se tiver várias maneiras de resolver quase, mas não exatamente do mesmo tamanho. Mas aconteceu porque o Rush Hour é um jogo para encontrar a solução mais curta, e não apenas qualquer solução.

[3] Excluindo a adição de unidades. Não havia pontos na primeira versão do quebra-cabeça, e o plano era o gerador adicionar unidades, se necessário. Mas isso parecia muito restritivo.