Além da notação FEN, existem outras notações de posição de xadrez ainda mais compactas? Um que, é claro, também implicaria direitos de castela e possibilidades passantes. Uma parte que realmente falta na FEN é o fato de ela não ter informações sobre se a posição corresponde a um xeque-mate ou a um cheque. É claro que sempre se pode colocar a posição no quadro e ver se é um xeque-mate ou não, mas não é diretamente dedutível da notação. Portanto, essa propriedade também seria importante para distinguir entre possíveis notações (além da compacidade etc.)

Se ajudar, isso é solicitado por razões de praticidade e eficiência na programação. Obrigado por todas as sugestões.

Como você está falando de programação, provavelmente está procurando um esquema de armazenamento mais compacto no espaço de memória do computador do que o FEN. Além de pesquisar como é feito em grandes mesas, duas possibilidades me vêm à mente imediatamente.

FEN normal

Para o propósito desta discussão, o FEN "normal" é apenas uma sequência de texto típica representada com caracteres de 1 byte (8 bits). Vejamos o pior caso simplificado :

r1b1k1n1/1p1p1p1p/p1p1p1p1/1n1q1b1r/R1B1P1N1/1P1P1P1P/P1P1K1P1/1N1Q1B1R w KQkq e3 999 999

Naturalmente, este não é um FEN válido, mas é um limite superior eficaz para a nossa complexidade. Existem oito caracteres por classificação, mais sete barras, cinco espaços e treze caracteres adicionais compõem os campos restantes. São 89 caracteres, para um tamanho total de 712 bits .

FEN comprimido

Esta versão está apenas usando a representação a FEN e usando algumas observações básicas para reduzir o número de bits necessários para armazená-la. Aqui estão nossas observações:

1. As barras são desnecessárias para o armazenamento da máquina; cada classificação deve simplesmente "adicionar a 8". Para que possamos eliminar barras em nossa representação interna.
2. Os caracteres possíveis restantes (na primeira secção) são: kK qQ rR bB nN pP 12345678. A distinção entre 20 caracteres cabe em cinco bits, portanto, no nosso pior caso simplificado, temos cinco bits vezes oito arquivos vezes oito classificações é 320 bits para a primeira parte.
3. Não precisamos de espaços; novamente eles são uma conveniência para os seres humanos. Isso nos salva cinco caracteres.
4. "Quem tem o movimento" é um pouco: branco ou preto.
5. A disponibilidade do castling é de quatro bits: disponível / indisponível para cada um KQkq.
6. En passant geralmente não está disponível e pode ocupar muito espaço (seis bits para representar todos os quadrados), então vamos movê-lo para o final e torná-lo opcional: se houver bits passantes , ele estará disponível, mas, se estiver indisponível, basta finalizar a representação após o movimento e meio movimento de bits para economizar espaço.
7. Por simplicidade, estou apenas alocando dez bits para cada um dos contadores de movimentação e meio movimento. Isso significa que os jogos representados nesse formato não podem exceder 1023 jogadas (meias jogadas desde a última captura ou avanço do peão).

Nosso formato completo é assim (no pior dos casos, com en passant disponível):

<position><whose move><castling><half moves><full moves><en passant>
 320 bits  1 bit       4 bits    10 bits     10 bits     6 bits

Isso nos dá um tamanho total de 351 bits no nosso pior cenário impossível, um pouco menos da metade do tamanho do nosso ponto de partida.

µFEN

Se abandonarmos totalmente a FEN pela carne da representação, podemos reduzi-la um pouco mais. Considere um único quadrado arbitrário. Esse quadrado pode estar vazio ou pode ter um pedaço nele. Se tiver uma peça, ela pode ser branca ou preta, e pode ser um rei, rainha, torre, bispo, cavaleiro ou peão. É um total de treze estados diferentes, que podemos representar em quatro bits; algo assim:

0000: empty square
0001: White Pawn
0010: White Knight
0011: White Bishop
0100: White Rook
0101: White Queen
0110: White King
0111: unused
1000: unused
1001: Black Pawn
1010: Black Knight
1011: Black Bishop
1100: Black Rook
1101: Black Queen
1110: Black King
1111: unused

Obviamente, existem alguns "bits parciais" não utilizados, portanto esse esquema quase certamente poderia ser melhorado por alguém com mais conhecimento de técnicas de compactação ou simplesmente um mapeamento mais cuidadoso dos diferentes estados. Também na prática, isso pode ser maior que o FEN compactado descrito acima, pois não há compactação de espaços em branco contíguos. No entanto, representa toda a placa em uma constante de 256 bits (4 bits * 64 quadrados), o que representa uma melhoria de 20% nos piores casos.

Para simplificar, basta marcar na segunda metade do Compressed FEN para concluir a representação. Portanto, o formato fica assim:

<position><whose move><castling><half moves><full moves><en passant>
 256 bits  1 bit       4 bits    10 bits     10 bits     6 bits

Isso nos fornece um requisito de espaço no pior dos casos, de 287 bits . Não é tão ruim!

Nota 1: Lembre - se, isso é apenas uma análise do pior caso, porque eu tenho formação em ciência da computação. O FEN padrão geralmente tem um desempenho muito melhor do que eu o descrevi, pois as posições normais não são o cenário de todos em branco que usei para comparações aqui. Portanto, as melhorias percentuais provavelmente são um pouco menores do que eu realmente representei, mas a tendência provavelmente ainda se mantém, pelo menos para a representação compactada da FEN. Eu ficaria muito interessado se alguém quisesse fazer uma análise probabilística de caso médio para o padrão FEN (e, por extensão, a versão compactada proposta acima)!

Nota 2: Lembre - se de que as vantagens e desvantagens da velocidade para lidar com formatos compactados podem ou não valer a pena para seus aplicativos! Dependendo do idioma que você está usando e do nível de controle que você tem sobre bits individuais, você pode achar que o FEN simples é significativamente mais rápido de usar , mesmo que exija mais espaço!

Nota 3: Se você deseja adicionar um indicador "check / checkmate / no-check" a uma das novas notações propostas, são dois bits extras para representar os três estados adicionais. Basta jogá-lo antes do indicador en passant .

A Descrição de posição estendida ( EPD ) adiciona "operações" ao FEN. Essas operações incluem, entre outras, melhor jogada, contagem de repetições e jogada prevista. Obviamente, não é mais compacto, mas faz mais.

A menos que eu esteja perdendo algo óbvio, a representação

0      empty
100    white pawn
101    black pawn
110xxx any piece except Rook
111x   Rook

codifica um full house (isto é, antes de qualquer captura) em 32 * 1 + 16 * 3 + 12 * 6 + 4 * 4 = 168 bits posicionais. Além disso, é claro, 4 bits de castelo, 3 bits de passante e 7 ou 8 bits de regra de 50 movimentos.

O pior caso (8 peões foi promovido pelo custo de capturar outros 8 peões, resultando em 20 peças + 4 torres a bordo) requer 40 * 1 + 20 * 6 + 4 * 4 = 176 bits posicionais.

É possível ajustar a placa e todas as informações (exceto a regra dos 50 movimentos) em 256 bits fáceis de gerenciar. Eu sugeriria o seguinte. 64 quadrados e 4 bits por quadrado permitem 16 estados possíveis. 0 representaria o quadrado vazio. Então nós temos 6 peças, mas eu reservaria um 7 para a 'torre movida', para que a possibilidade de roque possa ser determinada. Um bit para indicar branco ou preto. Estamos usando 15 estados e restam mais 1 estado: valor 8 (1000 binários). Ele também representa um quadrado emotivo, mas podemos usá-lo no 3º ou 6º rank para indicar que o peão à frente dele moveu 2 quadrados e está sujeito a ser capturado 'en passant'. Por fim, também usamos esse valor para indicar o lado a ser movido. Encontre o primeiro quadrado vazio na metade inferior do quadro para indicar que ele está branco para se mover. Na metade superior para preto.

Você perguntou: Uma parte que realmente falta na FEN é o fato de ela não ter informações sobre se a posição corresponde a um xeque-mate ou se é uma verificação. É claro que sempre se pode colocar a posição no quadro e ver se é um xeque-mate ou não, mas não é diretamente dedutível da notação.

Nesse ponto, pode ser uma boa pergunta se alguém quiser incorporar uma informação computacionalmente complexa no que deveria ser apenas uma descrição.

O mesmo se aplica às notações de movimento - por exemplo, entre: notação algébrica (e2e4 b1c3) e SAN (e4 Nc3) - o último requer um mecanismo para calcular a posição TO de cada movimento e é complexo para decodificar computacionalmente, enquanto o primeiro não requer a gravação de um gerador de movimento inteiro para determinar a posição TO inferida - o que pode ser benéfico.