Motor de xadrez minimax implementado com expressões regulares

Motor de xadrez minimax de 2 níveis

• Xadrez e expressões regulares: O autor criou um programa que joga xadrez usando apenas expressões regulares. Esse programa recebe um tabuleiro de xadrez como entrada e é composto por 84.688 expressões regulares para executar jogadas válidas.

• Design de CPU com expressões regulares: Usando expressões regulares, foi projetado um conjunto de instruções de execução sem condição e de dados de uma única instrução múltipla (SIMD). Isso permite que um programa que joga xadrez seja escrito.

• Estrutura de dados: O estado atual do computador é representado por uma única string contendo a "pilha" do programa e todas as variáveis. Cada instrução manipula as variáveis da pilha ou realiza operações de leitura/gravação em uma variável específica.

• Operações básicas da pilha:

  • Comando push: adiciona um valor ao topo da pilha.
  • Comando pop: remove o elemento do topo da pilha.

• Comandos variável <-> pilha:

  • Leitura de variável: carrega o conteúdo da variável no topo da pilha.
  • Atribuição de variável: atribui um valor à variável, atualizando-a se ela já existir ou criando uma nova se não existir.

• Condicionais: Usa-se condicionais para controlar o fluxo do programa. Dependendo da condição, parte do programa é ativada ou desativada.

• Impossibilidade de loops: Como loops não podem ser implementados apenas com expressões regulares, todos os cálculos iterativos precisam ser expandido previamente.

• Execução multithread: É possível executar várias threads simultaneamente aproveitando a função de substituição global de regex.

• Escrita do motor de xadrez: O motor de xadrez é escrito de maneira semelhante a outras linguagens de programação e opera rapidamente com processamento paralelo.

• Jogadas por turno:

  • Leitura da jogada do jogador: lê e valida a jogada de entrada.
  • Geração da resposta do computador: gera todos os movimentos possíveis e escolhe o melhor.

• Busca minimax: seleciona a melhor jogada usando busca minimax de profundidade 2. Esse processo é realizado de forma eficiente por meio de paralelização.

Este projeto mostra um exemplo de implementação de um motor de xadrez com o uso único de expressões regulares, demonstrando o poder das expressões regulares e um design computacional criativo.

[GN⁺]

Comentários do Hacker News

• O autor desse projeto é o tipo de pessoa que provou que printf() é Turing-completo e escreveu um jogo de tiro em primeira pessoa em apenas 13kB de JavaScript

  • Link do GitHub: Turing-completude do printf()
  • Link do GitHub: Jogo JavaScript de 13kB

• O projeto é extraordinário porque calcula várias posições possíveis em paralelo

  • Você consegue executar vários threads ao mesmo tempo usando regex

• Não tenho muito a acrescentar especificamente sobre a conclusão do blog post, mas gostaria que mais pessoas tentassem projetos desse tipo sem utilidade prática

  • É divertido, não há pressão sobre tempo de conclusão ou taxa de sucesso, e se aprende bastante sobre diferentes áreas da ciência da computação

• Há um bug de "movimento ilegal, derrota" no jogo de xadrez

  • Em um jogo de exemplo, a partida termina apesar de não haver movimento ilegal

• Seria mais assustador alguém jogando xadrez com uma única expressão regular do que alguém fazendo isso com 84.688 expressões regulares

• Projetos como este merecem todo o respeito

• O bug relacionado ao movimento da coluna a foi consertado

  • Link do GitHub: correção de bug

• Esse projeto não é só um engine de xadrez; também é um computador e uma linguagem assembly feitos inteiramente com expressões regulares

• Houve um projeto de xadrez anterior escrito em sed

  • A versão em sed usa comandos de controle de fluxo e só explora 1 ply

• Ele não perde tão rápido quando começa com a2a4

• Tentar algo sem uma meta claramente "produtiva" pode levar ao surgimento de novas maneiras e à inovação

  • O engine perde peças no início do jogo
  • Entrar letras maiúsculas é tratado como movimento ilegal

• É um esforço em busca de inovação e de se tornar mais produtivo