Geração procedural de puzzles: por que verificar importa

Em 2011, Julian Togelius, Georgios Yannakakis, Kenneth Stanley e Cameron Browne mapearam uma área em expansão e deram nome a ela: geração procedural de conteúdo baseada em busca. A revisão classifica geradores pelo que produzem, como o conteúdo é representado no programa e, acima de tudo, como sua qualidade é avaliada. A abordagem trata o design de fases como um problema de otimização: gera candidatos, dá uma pontuação a cada um usando uma função de avaliação, mantém os melhores, cria variações e repete — muitas vezes com algoritmos evolutivos inspirados na biologia.

É na função de avaliação que mora o design. Ela pode medir uma fase diretamente (quantas peças, quanto espaço vazio), por simulação (deixar um jogador artificial tentar e observar o resultado) ou de forma interativa (perguntar a jogadores de verdade). Cada método tem um custo. Medidas diretas são baratas, mas superficiais. Simulações se aproximam mais da experiência, mas exigem um programa capaz de jogar. Consultar pessoas é o método mais fiel e, de longe, o mais lento.

É fácil imaginar isso em um puzzle de blocos deslizantes. Um candidato é uma grade com blocos posicionados; uma variação move, acrescenta ou remove uma peça. Uma medida direta pode contar o quanto o tabuleiro está cheio. Uma simulação pode entregá-lo a um solver e registrar se consegue limpá-lo e quantos movimentos o caminho exige. O gerador mantém os tabuleiros com boas notas, varia-os de novo e, depois de milhares de rodadas, converge para aquilo que a função recompensa. Aí está sua força e seu risco: ele encontra exatamente o que você pediu, inclusive tabuleiros que cumprem os números e entediam o jogador.

Fontes1Fonte 1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

Outra linha de pesquisa começa pelo lado oposto. Em vez de evoluir tabuleiros esperando que surjam bons resultados, Adam Smith e Michael Mateas propuseram descrever explicitamente o espaço de designs aceitáveis por meio de restrições lógicas e deixar um solver genérico encontrar tabuleiros que as satisfaçam. Com uma técnica chamada programação por conjuntos de respostas (answer set programming), o designer pode escrever regras como “a saída precisa estar acessível” ou “esta peça precisa ser movida pelo menos duas vezes” e receber apenas tabuleiros que respeitem essas condições.

A aplicação ao design de puzzles é direta. Muitas características interessantes podem ser expressas como restrições: um bloco precisa ser bloqueado por outro; uma chave precisa ser necessária. Escrever essas regras obriga o designer a dizer exatamente o que procura — uma disciplina útil tanto para pessoas quanto para máquinas.

Fontes2Fonte 2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

Qualquer que seja o gerador, um puzzle precisa ser solucionável; provar isso costuma ser a etapa mais difícil. Noor Shaker, Mohammad Shaker e Julian Togelius enfrentaram esse problema em Cut the Rope, um puzzle de física com tempo e espaço contínuos, no qual uma busca exaustiva seria impraticável. A solução foi um agente de raciocínio que propunha apenas movimentos sensatos em cada estado. Isso reduziu a busca o bastante para uma simples busca em profundidade encontrar soluções e confirmar que as fases geradas podiam ser jogadas.

Bilal Kartal, Nick Sohre e Stephen Guy seguiram outro caminho em Sokoban, o clássico puzzle de empurrar caixas. O gerador constrói puzzles a partir de partidas simuladas com busca em árvore de Monte Carlo; assim, cada puzzle produzido é solucionável por construção. Puzzles de blocos deslizantes também são difíceis: o problema geral é PSPACE-completo, como explica nossa história dos puzzles de blocos deslizantes, e não há um atalho conhecido que resolva rapidamente qualquer tabuleiro.

Fontes3Fonte 3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4Fonte 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

Um tabuleiro pode ter solução e ainda ser sem graça, ou só permitir um caminho que ninguém encontraria. Kartal e colegas abordaram o problema diretamente. Em um estudo com participantes, buscaram características de tabuleiro baratas de calcular e relacionadas à dificuldade percebida. Combinaram essas características em uma função de pontuação e confirmaram em um segundo estudo que puzzles com notas maiores eram considerados mais difíceis. Ou seja, foi preciso aprender o que é dificuldade com as pessoas, não simplesmente presumir.

Yannakakis e Togelius ampliam essa ideia em sua estrutura de geração procedural orientada à experiência: modelar a experiência do jogador com base em seu comportamento, relatos ou fisiologia e gerar conteúdo para influenciá-la. É um objetivo ambicioso e, sendo honestos, os modelos de diversão e frustração ainda são imprecisos. Em puzzles, qualidades como elegância, o prazer de “entender de repente” e justiça são ainda mais fáceis de reconhecer do que de calcular. Analisamos o que justiça significa para os jogadores em o que torna um puzzle justo.

Fontes4Fonte 4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5Fonte 5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

Para jogadores, fica uma regra prática: “fases infinitas” informa que existe um gerador, mas não diz como as fases são testadas. Procure jogos que expliquem como verificam seus tabuleiros e desconfie quando a dificuldade dá saltos aleatórios — pode ser sinal de que ninguém a está modelando.

Outros sinais de uma boa série de puzzles, gerada ou não: ideias novas chegam uma de cada vez, como recomenda a pesquisa sobre ritmo; os tabuleiros parecem distintos, em vez de quase cópias com uma peça deslocada; e, quando você trava, acredita que há uma solução. Esse último ponto é o mais difícil de simular e aquele que os geradores demoraram mais para merecer.

Os 2.000 tabuleiros do OutBrick formam um conjunto fixo, criado por designers, e não um fluxo gerado no seu aparelho. Antes do lançamento, reproduzimos o caminho de solução de cada tabuleiro seguindo as regras do jogo. Explicamos o processo, inclusive por que um solver que chega ao limite de tempo significa “desconhecido”, e não “impossível”, em como verificamos 2.000 tabuleiros de blocos deslizantes. Um solver prova que existe um caminho; não prova que o tabuleiro é divertido, por isso avaliamos o ritmo separadamente. Você pode conferir por conta própria no tabuleiro do dia.