Não existe posição de xadrez alcançável com mais de 218 lances possíveis

• Não existe nenhuma posição com mais lances possíveis do que a posição de xadrez de 218 lances publicada por Nenad Petrović em 1964
• Como é inviável, na prática, explorar todas as posições, o limite foi provado com otimização matemática e técnicas de modelagem por computador
• O espaço de busca foi reduzido de forma eficaz com a remoção de peças desnecessárias, a permissão de posicionamento parcial de peças e a simplificação do roque, entre outros recursos
• Por fim, foi confirmado com a ferramenta de otimização Gurobi que 218 lances é o máximo, além de validar adicionalmente recordes como 144 lances (sem promoções)
• Com este estudo, desenvolvedores de engines de xadrez e de compressão podem eliminar a incerteza sobre o limite máximo de lances

---

Introdução: a controvérsia da posição de xadrez de 218 lances

Desde que o grande mestre de composição de xadrez Nenad Petrović publicou, em 1964, uma posição com 218 lances possíveis, várias tentativas buscaram quebrar esse recorde. O autor, como cientista da computação, quis encerrar essa questão analisando as posições por meio de computador. Existem cerca de 4,8 × 10^44 posições de xadrez alcançáveis, mas uma busca dessa escala é inviável na prática.

Introdução da otimização matemática

Minimização de peças e combinações desnecessárias

• Há poucos casos em que peças pretas adicionais aumentam o número de lances possíveis
  • Como quando permitem captura por um peão branco ou evitam uma situação de xeque ao rei adversário
• A maior parte das peças pretas pode ser removida sem afetar o número máximo de lances
• Desde que a quantidade de peças permitida seja respeitada, é possível substituir peças pretas por peças mais fracas ou ajustar o posicionamento sob algumas restrições, como cravadas
• No caso das peças brancas, ocorre o contrário: substituir tudo por peças fortes como rainhas pode gerar posições ilegais, então é necessário um ajuste cuidadoso

Situações de xeque e limite de lances

• Como uma posição em que o rei preto está em xeque não é legal, ela não precisa ser considerada
• Quando o rei branco está em xeque, seus movimentos ficam severamente limitados (no máximo 120 lances), tornando impossível chegar a 218
• Portanto, a busca pode se restringir a posições sem xeque

Posicionamento parcial de peças e modelagem matemática

Para reduzir a complexidade combinatória, a abordagem usa um modelo com posicionamento parcial (fractional) de peças, movimentos e algumas regras de xadrez relaxadas

• Por exemplo, uma peça pode existir com 27,3% de probabilidade em e4 e com 72,7% em outra casa
• Dessa forma, o problema foi implementado como programação linear inteira (ILP, Integer Linear Programming) em ferramentas modernas de otimização, como o Gurobi
• No início, surgiram limites de memória e tempo (falta de memória após cerca de 55 mil segundos)
• Para simplificar o espaço de busca, foram aplicadas medidas adicionais, como simplificação das regras de roque, ignorar xeque, ignorar cravadas e simplificar as condições de en passant

Otimização e conclusão

Por fim, após melhorar o modelo com a introdução de restrições auxiliares para bloquear buscas combinatórias desnecessárias, a otimização foi concluída com o programa Gurobi

• O limite superior foi sendo reduzido de 305 lances → 271,67 lances → 218 lances
• Foi confirmado que apenas 12 posições representativas com 218 lances possíveis são alcançáveis
• Também foi demonstrado, por meio de proof games, que essas posições são legais e podem ser alcançadas sem dificuldade

Além disso, também foram validados o máximo de 144 lances sem promoção, 288 lances em posições ilegais e o recorde de 271 lances em posições legais inalcançáveis

Resultados e significado

• Graças a este estudo, desenvolvedores de engines de xadrez e pesquisadores de algoritmos de compressão passaram a ter confiança de que um limite de 256 lances é suficiente para projeto de memória e afins
• Foi provado matematicamente que não existe posição com caminho legal que permita mais de 218 lances possíveis

Resumo do FAQ

• Uma partida de xadrez pode ser mais longa do que 218 lances, mas este estudo trata do número máximo de escolhas possíveis em um único turno
• Se algumas posições parecerem inalcançáveis, menciona-se que há vários caminhos possíveis, como casos em que o lance anterior termina em captura
• O método aplica uma técnica de oráculo matemático que elimina rapidamente combinações absolutamente impossíveis em um espaço combinatório gigantesco
• O código usado e até a validade matemática das evidências produzidas foram publicados para garantir confiabilidade

Próximas tarefas e sugestões de pesquisa adicional

Aplicando essa técnica, é possível atacar diversos outros problemas de xadrez, como máximo de capturas, máximo de stalemates, máximo de xeques, máximo de xeque-mates e máximo de mates em 2 lances. Ainda assim, em alguns casos, pode ser necessário um algoritmo de otimização criativo separado.

Conclusão

• 218 lances é o máximo oficial de lances possíveis em um único turno em uma posição de xadrez
• Em termos práticos, softwares de xadrez e pesquisadores podem projetar suas estruturas com base em 218 (ou 256)
• O código relacionado e os resultados da otimização foram publicados no GitHub

Referência

• Inclui links para proof games e posições, como a posição de 218 lances de Nenad Petrović e a de 144 lances (sem promoção) de Jenő Bán
• Mais detalhes e o código estão disponíveis no repositório no GitHub

[GN⁺]

Comentários no Hacker News

• Embora eles não tenham dito isso diretamente, o significado aqui é: "nesta posição, o jogador tem 218 lances legais para escolher"
  • Fico surpreso por ter lido esse artigo errado esse tempo todo, obrigado. Eu tinha entendido como "o número máximo de lances necessários para chegar a uma posição de xadrez é 218". Por isso eu estava me perguntando por que esse artigo não fazia sentido nenhum para mim
  • Eu tinha pensado: "quantos lances são necessários em uma partida para chegar a esta posição?"
  • Sim, é realmente estranho que o artigo nunca use a expressão "possible moves". A palavra-chave é "possible". O artigo continua dizendo algo como "have moves", mas essa é uma forma pouco familiar para o público em geral (talvez seja mais comum na terminologia do xadrez)
  • Obrigado. Eu estava confuso com esse artigo, achei que fosse sobre a posição única que exigiria o maior número de lances
• Quero muito elogiar o Lichess. Ele oferece um serviço e conteúdo fantásticos de graça, e até recursos que no Chess.com são pagos estão disponíveis sem custo. Também há muitas variantes de jogo
  No Lichess, o nível de jogo em variantes como 960 ou Crazyhouse é muito mais alto do que no Chess.com
  • É gratuito, oferece os mesmos recursos dos servidores comerciais, é open source e amigável para desenvolvedores. Também não tem anúncios (nem mesmo em contas gratuitas) e tem uma estrutura organizacional transparente sob a legislação francesa
    É literalmente absurdamente bom. Recomendo apoiar, se puder
• No texto em https://lichess.org/@/Tobs40/blog/there-is-no-reachable-chess-position-with-more-than-218-moves/a5xdxeqs#checking-more-positions-to-make-things-less-slow, o autor explica que inicialmente removeu algumas regras complexas e estava disposto a reintroduzi-las depois, se necessário (caso a solução encontrada violasse essas regras)
  O interessante é que solucionadores de programação linear inteira mista (MILP) já dão suporte a esse tipo de tratamento. Em termos técnicos, isso é chamado de row generation, normalmente usado quando se escreve o problema em forma de matriz, na qual as linhas são restrições e as colunas são variáveis
  Adicionar novas linhas (dinamicamente) é o mesmo que introduzir restrições apenas quando houver violação
  Esse método é usado principalmente para resolver o problema do caixeiro-viajante (Traveling Salesman Problem)
  (Por sinal, a Wikipédia tem Column generation, mas não row generation)
  • Olá, sou o autor do artigo do Lichess
    Relaxar ou omitir regras do xadrez também afetou a escolha das variáveis. Antes de entrar na modelagem matemática, tentei coisas como lazy constraints, mas não houve melhora significativa de velocidade. Por exemplo, só de deixar de considerar se o rei branco estava em xeque já houve muita simplificação
  • Esse tipo de abordagem costuma ser mais chamado de lazy constraints (explicação relacionada)
  • Fico realmente curioso se um solver MILP conseguiria terminar nesse espaço de busca gigantesco; meu palpite é que não
• Pergunta sincera por curiosidade: se o solver de programação inteira do Gurobi não encontrou uma solução melhor do que 218, isso garante que não existe uma melhor que 218? E isso é equivalente a uma prova matemática?
  (Premissa da discussão: o Gurobi não tem bugs, e também não há bugs na definição do problema nem na implementação do autor)
  Quero entender se há alguma possibilidade de o Gurobi estar preso em um máximo local, ou se ele realmente provou uma solução ótima global
  • O Gurobi fornece não apenas a melhor solução inteira encontrada até agora, mas também um limite para a solução ótima possível. Esse limite usa várias técnicas, como relaxação linear do problema, cutting planes etc. Então, se o solver não tiver bugs, a solução realmente é ótima
  • Sou o autor!
    Se o Gurobi e meu código estiverem funcionando como pretendido, e não houver erros lógicos no processo de simplificação do modelo de xadrez, então o meu resultado prova que "o valor máximo de lances legais possíveis em posições de xadrez alcançáveis a partir da posição inicial por uma sequência legal de lances é 218 como limite superior e inferior". Em outras palavras, o Gurobi provou, por meio de limites sobre todo o espaço de busca, que "não existe caso melhor que esse"
  • Não sei especificamente como o Gurobi foi aplicado aqui, mas, em geral, solvers de otimização combinatória desse tipo constroem uma árvore de prova mostrando que, para qualquer atribuição das variáveis, não é possível encontrar solução melhor. Em casos simples, você pode de fato verificar essa árvore e seguir a redução ao absurdo. No caso deste artigo, imagino que a árvore de prova seja gigantesca. Ainda assim, em princípio ela pode ser inspecionada
  • Em teoria, não é uma prova, mas na prática é como se fosse

• Não há posição de xadrez alcançável com mais de 218 lances
  Seria muito mais claro dizer "não há mais de 218 lances legais possíveis a partir de uma posição"

Verificar todas as cerca de 8.7x10^45 posições de xadrez alcançáveis?
Esse número na verdade é uma superestimativa
https://github.com/tromp/ChessPositionRanking estima com mais precisão o número de posições legais de xadrez em cerca de 4.8x10^44

• Essa estimativa não é tipo só 20 vezes menor? Nessa escala, não parece uma diferença tão grande
• Uma é "legal", a outra é "todo o espaço do problema"
  Do ponto de vista computacional, o espaço completo do problema é mais importante, porque todos os casos precisam ser "computados" antes mesmo de se determinar se são legais ou não. Não existe uma maneira simples de percorrer apenas posições legais
• Olá a todos
  Um conhecido me avisou que meu artigo estava sendo discutido aqui
  Peço desculpas por ter escolhido um título menos claro; espero que agora esteja mais claro. Obrigado pelo feedback e pelas palavras gentis
  Se alguém tiver perguntas sobre provas de fatos semelhantes no xadrez, também posso responder ^^
  Obrigado
  Tobi
  • Então, só para confirmar: isso significa que, para qualquer posição no tabuleiro, o número de lances disponíveis nunca passa de 218? É esse o entendimento correto?
• Qual é o número mínimo de bits necessário para representar um tabuleiro de xadrez alcançável?
  Atualização: o artigo diz que existem cerca de 8.7x10^45 posições de xadrez alcançáveis, e https://github.com/lechmazur/ChessCounter usa esse número como limite superior
  (isso corresponde a cerca de 153 bits)
  • Se for algo em torno de 4.8x10^44, então log2(4.8x10^44) dá 149 bits
    Mas, para decodificar de forma eficiente, seriam necessários 153 bits, usando o teto de log2 do número recomendado pelo projeto ChessPositionRanking (8726713169886222032347729969256422370854716254). O ChessCounter não fornece código de decodificação eficiente
  • O rei pode estar em qualquer uma das 64 casas
    O mesmo vale para torre/rainha/cavalo, mas como podem ter sido capturados, são necessários 65 estados possíveis para cada uma dessas 5 peças
    Os bispos só podem estar em metade dessas casas, então são 33 estados para cada
    Peões têm 4 promoções possíveis, podem ter sido capturados e, dependendo do caso, ficam em algo como 20 a 30 posições; no geral, cerca de 290 estados por peão
    Isso dá cerca de 112 bits para representar o estado do tabuleiro de uma cor de peças; arredondando, 224 bits para ambos os lados
    En passant e restrições de roque (como roque indisponível) não exigem bits extras depois do arredondamento, pois isso só adiciona alguns estados a certas peças
    Esse provavelmente é o formato fixo mais comprimido para representar um tabuleiro
    Em uma representação esparsa, como os dois reis sempre existem, você poderia representar as peças vivas com um número decimal de n dígitos e posições com n+2 números de 64 bits, acrescentando um pouco de informação extra para roque, en passant etc. Em média, se metade das peças tiver desaparecido, isso dá cerca de 180 bits para representar o estado do tabuleiro
    O histórico de lances também exigiria cerca de 10 bits por lance (um par preto/branco; um ply são 5 bits), então daria para guardar algo como 18 lances. Isso é um pouco menor do que o ponto médio da duração média de uma partida de xadrez
    Para comprimir mais, provavelmente só implementando um dicionário gigantesco
  • Tipo e cor da peça podem ser representados com 4 bits
    Então, uma codificação de tamanho fixo para o tabuleiro inteiro seria 64*4=256 bits = 32 bytes
    Ou, em uma representação de tamanho variável apenas para as peças, usando 6 bits para o índice de cada uma das 64 casas, seriam quantidade*10 bits
    Por exemplo, a posição inicial seria 32*10=320 bits = 40 bytes
  • Esse valor restricted de 8.7e45 no GitHub restringe alguns padrões de promoção de peões
    5.68e50 em general é o verdadeiro limite superior e permite todas as promoções possíveis
• O peão preto em b2 está reduzindo bastante os lances possíveis das outras peças
  Esse peão só tem uma jogada possível (capturar o cavalo ao lado). Se ele não estivesse lá, quatro rainhas brancas e um cavalo poderiam entrar em b2. Só que, na verdade, esses lances não podem existir porque o rei preto já estaria em xeque-mate
  É tentador mover a rainha em e5 para outro lugar, de forma que não seja xeque-mate imediato, e assim liberar mais a casa b2
  P.S.: parece que esse peão precisa sobreviver ali para evitar stalemate
  • O peão preto em b2 não pode se mover em uma posição com White to move
    Se fosse a vez das pretas, ele também não poderia se mover, porque o rei está pinado pela rainha branca em e5. Sem esse pin, ele poderia fazer 4 lances. Promoção menor também seria possível
  • Eu também fiquei confuso com a ideia de que "as peças pretas são inúteis". Parecia que, em vez de fazer duas rainhas se encararem, dava para trocar uma delas por uma peça preta e criar lances de captura entre as duas... mas aí percebi que, no fim, "só um lado pode se mover"
  • Sou o autor
    A posição é White to move. Mesmo que o peão em b2 não estivesse pinando o rei por causa da rainha branca, o peão preto ainda não poderia se mover
    O peão em b2 é necessário para proteger o rei preto contra xeque. Caso contrário, a própria posição não seria legal
    Eu realmente conferi tudo com muito cuidado, então podem ficar tranquilos: não foi possível construir mais de 218 lances para as brancas. Ainda assim, estou surpreso e grato por tanta gente ter se interessado pelo meu artigo, haha ^^
  • É a vez das brancas. Se fosse a vez das brancas com as pretas em xeque, isso não seria legal e seria uma posição inalcançável. Não haveria como chegar legalmente a esse estado no turno anterior das pretas
    Parece que daria para aumentar o número de lances trocando um dos peões pretos por um cavalo branco, mas os dois cavalos já existem, e todos os peões já foram promovidos, então isso não é possível. (Se trocar os dois peões, as pretas não conseguem mais alcançar esse estado no turno anterior)
• Estou confuso. Mas depois daquele modelo com 271, queria saber que mudanças foram feitas para chegar à solução ótima. Só está escrito "com esse modelo melhorado..."
  • Sou o autor!
    Você leu o artigo inteiro?
    Não é 271, e sim 271.666... :) Esse valor vem de um modelo em que todas as decisões (0 ou 1) são relaxadas para valores contínuos (0.0~1.0 e qualquer valor intermediário). Ou seja, você pode assumir que uma peça existe em quantidade 0.23. A chance de um determinado lance ser possível também pode ser tratada como 0.843 etc.
    Usando esse tipo de "mágica negra", o cálculo fica muito mais rápido e pode produzir um número de lances maior do que o realmente existente.
    Assim, esse método serve para descartar rapidamente subespaços ruins entre as possibilidades. Sem esse tipo de técnica, seria impossível examinar exaustivamente todo o espaço de busca
• Será que estou deixando passar alguma coisa, ou a posição mostrada no começo na verdade não é alcançável? É a vez das brancas, mas os peões pretos estão em suas casas iniciais, e o rei não tem casas vazias adjacentes; ele parece preso entre peças e peões, então essa posição não parece alcançável
  • Há uma prova de que essa posição realmente é alcançável aqui: https://lichess.org/study/PLtuv3v5/zWPNxbSA
    Aliás, acho que você entendeu errado ao achar que os peões pretos estão em suas posições iniciais. Na verdade, o peão preto avançou até o outro lado do tabuleiro (campo das brancas)
  • O peão preto está no campo das brancas (1ª e 2ª fileiras)