Motor de xadrez minimax de 2 ply implementado com 84.688 expressões regulares

• Regex Chess é um motor minimax de 2 ply que escolhe uma jogada legal e “não totalmente horrível” em um tabuleiro de xadrez executando apenas 84.688 substituições de expressões regulares em sequência
• O estado coloca pilha e variáveis dentro de uma única string, e comandos como push, pop, consulta e atribuição de variáveis são processados por substituições com expressões regulares
• O desvio condicional é simulado trocando o marcador %%, que representa um estado ativo, e as substituições globais permitem execução paralela no estilo SIMD para vários estados ao mesmo tempo
• O motor cria todas as jogadas legais como estados paralelos e avalia até as respostas do oponente, mas não faz uma busca depth-3 que valide completamente até a legalidade dessas respostas
• No início, uma resposta a uma jogada levava cerca de 30 minutos, mas com remoção de variáveis intermediárias, otimização de matching, comandos de propósito específico e paralelização, a implementação final caiu para 1 a 10 segundos dependendo da posição

---

Estrutura básica do Regex Chess

• Regex Chess consiste em uma lista de 84.688 expressões regulares que formam o motor de xadrez inteiro
• A estrutura de execução é simples
  • percorre a lista de expressões regulares em ordem
  • aplica cada padrão e string de substituição ao estado atual do tabuleiro, representado como string
  • mostra o estado final na tela
• A entrada não é PGN, e sim um formato de coordenadas que concatena casa de origem e casa de destino, como e2e4
• O código do projeto está disponível no GitHub

Uma CPU de expressões regulares

• Em vez de escrever diretamente as regras do xadrez em expressões regulares, primeiro foi criado um pequeno computador que funciona com expressões regulares
• Esse computador usa um conjunto de instruções com execução condicional sem desvio, execução de um comando para múltiplos dados, e manipulação de pilha e variáveis
• O estado atual é representado por uma única string
  • %% indica o início de um estado de execução ativo
  • abaixo de #stack: ficam empilhados os itens da pilha
  • variáveis são armazenadas no formato #variable: value

• Manipulação de pilha e variáveis

  • push localiza o cabeçalho %%\n#stack:\n e insere um valor logo abaixo, colocando-o no topo da pilha
  • pop remove a linha logo abaixo de #stack:, eliminando o valor do topo da pilha
  • a consulta de variável procura #nome_da_variável: dentro da string de estado, copia o valor e o adiciona ao topo da pilha
  • a atribuição de variável trata tanto o caso em que a variável já existe quanto o caso em que ela não existe
    • se já existir, substitui o valor atual da variável pelo valor da pilha
    • se não existir, adiciona uma nova linha de variável
  • marcadores temporários, como crases, são usados para impedir que a mesma instrução seja reaplicada em ordem incorreta

Execução condicional sem desvio e limite de laços

• A execução condicional é implementada com cond(tag) e reactivate(tag)
• Se o valor no topo da pilha for False, o marcador ativo %% é trocado para a forma %tag, e as instruções seguintes deixam de ser aplicadas àquele estado
• Mais tarde, reactivate(tag) converte %tag de volta para %%, reativando o estado correspondente
• Dessa forma, é possível simular execução condicional sem ramificações explícitas
• Como o programa é uma lista sequencial de expressões regulares, não é possível executar laços diretamente
  • ele não consegue fazer computação Turing-completa
  • ainda assim, cálculos com limites definidos, como encontrar a próxima jogada no xadrez, podem ser tratados desenrolando os laços

Execução paralela com substituição global

• Como a substituição por expressão regular é aplicada globalmente à string inteira, se houver vários estados de execução %% dentro de uma única string de estado, a mesma instrução será aplicada a todos eles ao mesmo tempo
• Por exemplo, se duas pilhas tiverem dois inteiros cada, ao executar binary_add() as duas somas serão realizadas simultaneamente
• fork_inactive(tag) duplica o estado ativo atual e deixa a cópia em um estado com tag inativa
• fork_bool(variable) divide um estado em dois, um com valor True e outro com valor False
• Essa estrutura é usada no xadrez para avaliar simultaneamente vários estados possíveis do tabuleiro, em vez de processá-los um por um

Montador de macros e execução simbólica

• O motor não foi escrito inteiramente à mão só com expressões regulares; ele usa um montador de macros que transforma um programa em estilo Python em pequenas sequências de instruções
• Código em estilo Python como fib() é convertido em uma lista de instruções como push, lookup, binary_add e assign_pop
• Em vez de um parser tradicional e geração de código, usa-se execução simbólica (symbolic execution)
  • objetos de variável não são dicionários reais, mas objetos especiais que registram as operações executadas
  • a = b + 1 é registrado como lookup('b'), push(1), binary_add() e assign_pop('a')
• Instruções if registram tanto o caminho verdadeiro quanto o falso antes de voltar a uni-los
  • ao encontrar uma ramificação condicional, são criados dois caminhos na árvore de chamadas
  • ao rastrear várias vezes, é escolhido o ramo menos visitado para preencher ambos os caminhos
  • o ponto de junção é convertido em uma instrução reactivate

Como as jogadas de xadrez são geradas

• Escrever o motor de xadrez em si é parecido com escrever um motor em uma linguagem comum, mas o ponto central está em processar vários estados em paralelo
• A geração de movimentos de peão segue este fluxo
  • encontra todas as posições de peões brancos
  • cria um estado paralelo para cada peão
  • interrompe o estado principal original e ativa os estados por peão
  • verifica simultaneamente, em todos os estados de peão, os candidatos de avanço de uma casa, avanço de duas casas e capturas diagonais
  • volta a combinar a lista de jogadas candidatas de cada estado
• O exemplo usado na explicação manipula diretamente strings FEN, mas a implementação real expande o tabuleiro para 64 variáveis, uma por casa, para leitura e escrita
• Peças deslizantes como bispo, torre e dama, além de roque e en passant, também foram implementadas separadamente
• Os detalhes da implementação estão em chess_engine.py

Processamento de um turno e validação de jogadas

• Um turno segue a ordem de ler a jogada do humano, verificar se ela é legal e então gerar a resposta do computador
• from_pretty_utf8_to_fen() converte a exibição do tabuleiro de xadrez em Unicode para notação FEN e extrai a casa de origem e a de destino da entrada
• A legalidade da jogada humana não é validada por um código separado de regras, mas comparando com todos os próximos tabuleiros legais gerados
  • make_move cria o tabuleiro resultante da jogada informada
  • compute_legal_boards gera todos os tabuleiros legais possíveis a partir da posição atual
  • fork_on_list separa cada tabuleiro em um estado paralelo
  • estados diferentes do resultado da jogada aplicada são eliminados com destroy_active_thread()
• Se não houver jogada legal, toda a saída é substituída pelo texto hardcoded "Illegal Move"
• A resposta do computador é obtida gerando os tabuleiros de resposta possíveis para as pretas e suas pontuações, deixando ao final apenas o tabuleiro com a melhor pontuação por meio de keep_best_scoring_board(score)

Minimax de 2 ply e simplificação intencional

• compute_and_score_legal_boards desempenha o papel central na busca minimax depth-2
• Primeiro, o computador gera as jogadas candidatas que pode fazer; em seguida, gera as respostas possíveis do oponente para verificar se o rei pode ser capturado
• Como a validação de xeque exige gerar também as respostas do oponente, a estrutura de busca já se torna uma busca depth-2
• Cada posição candidata é avaliada pela pontuação resultante da melhor resposta do oponente
• Não é um minimax depth-2 completo
  • ele não valida se as jogadas de resposta do oponente são ilegais por deixarem o próprio rei em xeque
  • para tratar isso completamente, seria necessária uma busca depth-3, com custo muito maior
• As respostas geradas pelo computador em si não são ilegais, mas em alguns casos ele pode considerar lances que o oponente não poderia jogar e, por isso, escolher uma resposta mais fraca do que a real

Otimização de desempenho

• A implementação inicial levava cerca de 30 minutos para gerar uma resposta a uma jogada humana
• A implementação final leva cerca de 1 a 10 segundos por posição na máquina do autor
• O ganho de cerca de 100x veio de várias otimizações

• Remoção de variáveis intermediárias

  • consultar variáveis exige procurar seus valores em toda a string de estado, o que tem custo O(n)
  • ao fazer fork de estados de execução, as variáveis também são copiadas, aumentando o uso de memória
  • remover agressivamente variáveis que não são mais necessárias e reutilizar nomes de variáveis reduz tempo e memória
  • o estado interno durante a avaliação de uma jogada caiu de 10 GB para cerca de 300 MB antes e depois da otimização

• Otimização de matching de expressões regulares

  • apenas incluir uma quebra de linha no início da expressão regular de limpeza de instruções condicionais já quase dobra a eficiência desse comando
  • como as strings True e False aparecem com frequência dentro do estado, o padrão precisa ser restrito para localizar rapidamente apenas o valor no topo da pilha
  • pequenas diferenças de padrão que reduzem correspondências candidatas desnecessárias afetam o tempo total de execução

• Comandos de propósito específico e paralelização

  • partes lentas, como o laço de busca de posições de peças, foram combinadas em um único comando especial de expressão regular em vez de montar tudo com instruções já existentes
  • na geração de movimentos da torre, cada direção não é verificada em sequência; vários estados paralelos são criados para processar tudo de uma vez
  • a avaliação de posições também cria estados paralelos por tabuleiro candidato e os executa simultaneamente
  • a execução paralela é especialmente eficaz em tarefas nas quais a mesma operação se repete em muitos estados, como o cálculo do valor das peças

Implementações adicionais incluídas no código-fonte

• O código também inclui elementos de implementação que não são explorados em profundidade no texto principal
  • geração paralela de jogadas para peças deslizantes como bispo, torre e dama
  • procedimento para verificar se “uma casa está sob ataque” no contexto do roque
  • conversão entre tabuleiro FEN e representação por variáveis por casa
  • detecção de direito de roque por rastreamento das posições do rei e das torres
  • detecção e rastreamento de en passant
  • cerca de 2.000 linhas de testes validando a correção do motor ao longo de milhares de partidas
• O texto termina dizendo que esse tipo de projeto sem propósito prático ajuda a aprender vários temas de ciência da computação fora da própria área de atuação
• Como projetos relacionados, também são mencionados printf-tac-toe, um jogo da velha em C com printf, e um clone de Doom em JavaScript com 13 kB

[GN⁺]

Comentários do Hacker News

• Esse é o trabalho da mesma pessoa que mostrou que printf() é Turing-completo e fez um jogo de tiro em primeira pessoa em 13 kB de JavaScript
  https://github.com/HexHive/printbf
  https://github.com/carlini/js13k2019-yet-another-doom-clone

  • Quando li a frase “mostrou que printf() é Turing-completo e fez um jogo de tiro em primeira pessoa…”, sinceramente achei que ia terminar dizendo que esse jogo de tiro também tinha sido feito em printf
  • O diário de desenvolvimento do Doom é interessante pelos detalhes: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
    O prazo para concluir a competição era de um mês, mas parece que foi possível reutilizar código existente
    O trabalho em si deve ter sido bem divertido, e fico um pouco triste porque hoje, por causa da família e do trabalho, eu nunca conseguiria arrumar um mês inteiro de tempo livre para algo assim
  • Fiquei animado ao ler “um jogo de tiro em primeira pessoa em 13 kB de JavaScript”, mas me decepcionei um pouco quando descobri que usava WebGL para renderizar os gráficos

• Foi nesse ponto que senti que esse trabalho deixou de ser só uma loucura divertida e passou a ser algo realmente extraordinário. Todos os cálculos das várias posições possíveis aconteciam em paralelo, rodando regex sobre um conjunto crescente de estados e variáveis, ou seja, sobre threads
  “Agora chegamos à minha parte favorita da linguagem que criamos. Graças à mágica das regex e ao fato de fazermos substituições globais em toda a string, podemos executar várias threads ao mesmo tempo!”
  Também gostei da conclusão. “O que vocês esperam como conclusão de um post de blog desses? Não há propriamente uma conclusão. Eu só queria que mais gente fizesse esse tipo de coisa completamente inútil. É muito divertido, ninguém liga quanto tempo vai levar para terminar, ninguém liga se vai funcionar ou não e, de quebra, você acaba aprendendo mais sobre várias áreas da ciência da computação fora da sua área do que jamais quis.”
  É realmente uma atitude incrível

  • Se eu conseguisse afastar todas as outras preocupações, fico pensando se eu também seria capaz de fazer algo assim
    O que isso transmite é a força de não saber até onde dá para ir quando você senta e concentra a mente em uma única coisa, mas também que o autor claramente é uma pessoa muito talentosa, habilidosa e criativa

• Parece haver um bug em algum lugar. A partida abaixo termina com “Illegal move, you lose”, mesmo sem haver lance ilegal

  1. e2e4, e7e5
  2. d2d4, e5d4
  3. d1d4, a7a5
  4. g1f3, b7b5
  5. b1c3, a5a4
  6. c3b5, a4a3
  7. b5a3, a8a3
  8. b2a3 -->
     Illegal Move
     You Lose.
     Game over.
     FEN da partida acima:
     1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
  • Se você jogar a2a3 no primeiro lance, ou a2a3 no segundo lance depois de e2e4, também aparece como lance ilegal
    Mas ambos são lances legais, então é mesmo um bug
  • O mesmo acontece se você simplesmente jogar a2a4 no primeiro lance

• Não tenho medo de alguém que joga xadrez com 84.688 regex, mas tenho medo de alguém que joga xadrez com uma única regex

  • Se existir alguma heurística geral para linearizar regex aplicadas sequencialmente, ou seja, um jeito de combinar duas regex arbitrárias em uma só, talvez desse para aplicar aqui
    Me ajudem, fui nerd-sniped
    O problema potencial que me vem à cabeça imediatamente são as referências retroativas
    A regex ficaria gigantesca, mas no fundo isso seria praticamente codificar um motor de xadrez…

• Quando vejo algo assim, dá vontade de tirar o chapéu e oferecer uma solene gratidão aos verdadeiros heróis da humanidade

• O bug de movimento na coluna a foi corrigido: https://github.com/carlini/regex-chess/issues/1

• Caso anterior: xadrez escrito em sed https://news.ycombinator.com/item?id=6261314
  Claro que a versão em sed usa os comandos de controle de fluxo do sed e provavelmente só procura um lance à frente, então nesse aspecto é bem diferente desta versão

• Isso não é apenas um motor de xadrez, mas também um computador e linguagem assembly feitos usando apenas regex

• Normalmente não se perde tão rápido assim começando com a2a4!

  • Eu também encontrei um bug parecido na coluna a. O caminho foi e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

• Vale comparar com isto também: https://codegolf.stackexchange.com/q/3503/32575

  • Todas as regras de teste de divisibilidade são inevitavelmente linguagens regulares, então isso não é tão surpreendente. Se ficassem mais complexas, deixariam de ser “regras” que uma pessoa consegue executar