Beam search não é monotônico, e isso contaminou minhas medições
Uma beam search mais larga não é uma beam search estritamente melhor. Num nível do Sunny Sort, largura 45 encontra uma linha vencedora, largura 90 falha, e largura 200 encontra de novo — e como toda medição de dificuldade do projeto perguntava "isso ainda é vencível?" com uma largura só, a resposta vinha errada com frequência suficiente para enviesar a curva inteira.
Como apareceu
Um nível surgia como insolúvel na sondagem e solucionável na geração. Mesmo nível, mesmo orçamento de jogadas, dois vereditos diferentes do mesmo solver.
A diferença era a largura de beam que cada etapa por acaso usava.
| Largura do beam | Resultado |
|---|---|
| 45 | resolve |
| 90 | falha |
| 200 | resolve |
Por que um beam mais largo pode ser pior
A beam search guarda os melhores k estados em cada profundidade e descarta o resto. Alargar k guarda mais estados — mas também muda quais estados estão na fronteira, porque a fronteira é ordenada por heurística, não por verdade.
Uma linha vencedora costuma passar por um estado que a heurística pontua mal. Na largura 45 esse estado sobrevive porque há pouca concorrência na profundidade dele. Na largura 90 chegam mais candidatos, todos com nota melhor na heurística e nenhum levando a lugar nenhum, e o estado que importava é empurrado para fora da fronteira.
Mais busca, resposta pior. A propriedade que as pessoas assumem — que acrescentar largura só pode ajudar — é propriedade de busca exaustiva, não de uma busca truncada.
O que custou antes de eu perceber
O modo de falha é assimétrico, e é isso que o torna perigoso. Uma beam search nunca reporta uma vitória que não consegue demonstrar, então um resultado positivo é confiável. Um negativo significa apenas "esta largura não achou uma linha", que se lê de forma idêntica a "não existe linha".
Ou seja, as medições produziam só falsos negativos:
- níveis declarados impossíveis que eram vencíveis;
- largura de decisão medida em 76% contra 86% reais na mesma configuração.
Esse segundo número é o que dói. Largura de decisão é a métrica em que toda a decisão sobre pressão se apoiou — a fatia de jogadas válidas que mantêm a vitória viva. Uma subestimação de dez pontos empurra todo julgamento sobre quanta liberdade um nível permite na mesma direção, e nada na saída parece suspeito. É um número plausível, afirmado com confiança, e errado.
A correção
DepthProbe.Winnable e BestLine agora tentam várias larguras antes de concluir qualquer coisa. Um nível só é declarado invencível quando todas as larguras tentadas falharam; a melhor linha é a melhor que qualquer uma delas achou.
Tanto o analisador quanto a verificação de justiça do gerador usam as versões de várias larguras. Nenhum nível é declarado impossível por causa de uma peculiaridade do solver.
O custo é tempo de busca, pago offline durante a geração, por uma máquina, uma vez. A alternativa era publicar níveis que o jogador não vence e a quem não se pode explicar o porquê.
A parte que vale generalizar
Isso está registrado no log de design com entrada própria, não porque a correção seja interessante, mas por causa do tipo de bug que é.
Ele nunca quebrou nada. Nunca lançou exceção. Produziu um número exatamente do formato certo, na faixa certa, que uma pessoa razoável leria e usaria. Toda decisão tomada a jusante daquela medição herdou o erro em silêncio — e o único motivo de ele ter sido pego é que duas etapas do mesmo pipeline por acaso usavam larguras diferentes e discordaram em voz alta.
Se uma ferramenta responde uma pergunta buscando, a largura da busca faz parte da resposta. Pergunte de mais de um jeito antes de acreditar.