markovjunior

MarkovJunior é uma linguagem de programação probabilística onde programas são combinações de regras de reescrita e a inferência é realizada via propagação de restrições. É nomeada em homenagem ao matemático Andrey Andreyevich Markov, que definiu os algoritmos de Markov. Em sua forma básica, um programa MarkovJunior é uma lista ordenada de regras de reescrita. Por exemplo, o modelo MazeBacktracker usa duas regras: `RBB=GGR` e `RGG=WWR`. Em cada etapa de execução, o interpretador encontra a primeira regra com uma correspondência na grade, encontra todas as correspondências e aplica uma aleatória. O interpretador para quando nenhuma regra corresponde. A inferência probabilística permite impor restrições em estados futuros, gerando apenas execuções que levam a futuros restritos. Por exemplo, a inferência nas regras de Sokoban faz com que agentes organizem caixas em formas especificadas. O repositório inclui muitos geradores probabilísticos para masmorras, arquitetura, quebra-cabeças e simulações. Conceitos-chave incluem: - **Regras de reescrita**: Regras simples como `(B=W)` convertem quadrados pretos aleatórios em brancos. Regras mais complexas como `(WBB=WAW)` geram labirintos com uma única linha de código. Caracteres curinga (`*`) permitem qualquer cor na entrada ou saída inalterada. - **Rulenodes**: Combinam múltiplas regras, por exemplo, para caminhadas aleatórias com apagamento de laços ou geração de labirintos Aldous-Broder. - **Nós de sequência**: Executam rulenodes um após o outro, por exemplo, construindo diagramas de Voronoi para vales de rios. - **Nós de Markov**: Permitem retornar a nós passados, possibilitando algoritmos como a geração de masmorras de Bob Nystrom. - **Inferência**: Usa propagação de restrições (unidirecional ou bidirecional) para conectar estados, com parâmetro de temperatura para rigor. Pode resolver quebra-cabeças como Sokoban ou gerar caminhos Hamiltonianos. Materiais adicionais incluem uma visão geral da sintaxe XML, capturas de tela de maior resolução e notas técnicas não oficiais. O projeto discute problemas em aberto como síntese de programas para geração procedural e síntese de modelos a partir de exemplos. Cita influências de algoritmos de Markov, Imagegram, REFAL, mapas de Dijkstra e algoritmos clássicos como busca A*. O interpretador usa correspondência de padrões rápida com um algoritmo multidimensional de Boyer-Moore e suporta relaxamento estocástico para otimização baseada em gradiente.