Escreva um algoritmo ou programa que possa codificar e decodificar um tabuleiro de xadrez. O objetivo é fazer a menor representação de um tabuleiro de xadrez que possa ser usado (uma vez decodificado) para determinar todas as possibilidades de movimento de um jogador nesse turno.
A codificação deve ser capaz de mostrar:
- De quem é a vez.
- Se o jogador pode dominar de cada lado.
- Se o jogador pode executar um passante e, em caso afirmativo, qual de seus peões?
- Posições de todas as peças.
Nota importante sobre o roque: Se as brancas moverem seu rei um turno e o moverem de volta no próximo, deve ficar claro que eles não poderão se fortificar de nenhum dos lados depois disso. O mesmo ocorreria se eles movessem a torre esquerda ou direita. Embora o tabuleiro esteja visualmente no mesmo estado de dois turnos atrás, o estado do jogo mudou. Mais informações aqui: http://en.wikipedia.org/wiki/Chess#Castling
Nota importante sobre en-passant: Este também é um movimento sensível à curva. Leia as regras para mais informações. http://en.wikipedia.org/wiki/Chess#En_passant
Determine a entrada e a saída conforme necessário. Adereços principais para quem puder comprimir o máximo!
Sua pontuação é determinada no pior cenário - tamanho máximo possível em bits. Mostre como você calculou esse número e o que foi responsável. Atire no menor dos piores casos!
fonte
Respostas:
Mín: 12 bits
Máx:
Média:
Tinha e pensei ontem à noite que eu poderia torná-lo ainda menor.
O resultado é um tamanho impressionante de 12 bits !
E quanto a K +1 outro tipo de peça?
Existem 2 arranjos possíveis da subárvore.
Ambos resultam no mesmo tamanho de bit para todas as peças. Portanto, não faz diferença a que usamos, vou escolher o primeiro.
Então, no King +2 outros tipos de peças
Existem 5 subárvores possíveis (usarei 1 e 2 para indicar qual das peças).
Portanto, precisaremos de 3 bits para codificar qual subárvore usar.
Ainda fazendo a análise para mais peças
+3 Outros
+4 Outros
+5 Outros
Max: 208?
É possível codificar todas essas subárvores em 9 bits?
Se somarmos todas as subárvores possíveis, obtemos 392 subárvores possíveis.
Usando Freq ID
Uma vez que existem 164603 frequências de peças únicas .
(+000) (+00) Rolagem
Máx: = 204 bits
rev 3
Mín: 82 Máx: 199 Média: 160
Finalmente, comecei a fazer algumas análises para encontrar o tamanho máximo de bit. Com codificação huffman ideal para cada uma das frequências de peça únicas .
Observe que esse é o pior tamanho possível, que a coluna En-Passant bits se o número de peões for maior que um. Independentemente das cores e posição dos peões, existe o potencial de algumas placas serem 3 bits menores.
Além disso, existem apenas 144 tamanhos diferentes (pior caso) para o tamanho da placa.
75 - 216 bits (v2) v1 O tamanho mínimo é de 98 bits (12,25 bytes), apenas os dois reis da placa.
O tamanho máximo é de apenas 216 bits (27 bytes). No improvável: -
Em média, o tamanho será de cerca de 157 bits (19.625 bytes).
Peças
Para codificar a placa, estou usando um esquema de codificação de árvore binária. Um quadrado vazio é o mais frequente entre 32 e 62 aparições. A seguir, estão os peões, e as Torres, Cavaleiros, Bispos e os menos frequentes são a Rainha e o Rei.
O quadro inicial pode ser codificado em apenas 166 bits (20.75 bytes)
Para indicar quem se move, é preciso apenas um bit
A rolagem pode ser codificada em 4 bits.
Então, eu uso 171 bits (21.375 bytes)
O En-Passe pode ser codificado em apenas 16 bits (2 bytes)
Então, no total, isso é 187 bits (23.375 bytes).
Layout
Ainda não escreveu nenhum código.
Observe que 3 dos bits não são utilizados. Portanto, o máximo é 213bits .
Possíveis melhorias
1) Reduzido o formulário do bloco de cabeçalho de 24 para 8 bits (com sugestão de Peter Taylor)
2) Cabeçalho de comprimento variável
Um pequeno cabeçalho fixo de 4 bits
Próximo bloco de bits adicionais (se ainda é possível fazer rapel)
Próximo bloco de bits adicionais (se houver peões)
Então agora eu tenho um cabeçalho de comprimento variável de 4 a 11 bits
3) Use um esquema de codificação diferente, dependendo das peças restantes no quadro.
Alterando a codificação em árvore, dependendo de quais peças estão no quadro e da frequência.
Uma codificação possível para um estado final do jogo (sem peões)
Que é de cerca de ~ 4 bits por peça.
Que tipo de peças estão presentes no quadro?
Permutação é comprimento variável de 0 a 5 bits. Se apenas um tipo de peça for deixado, não o inclua.
Qual permutação dessas peças usar na árvore? Este é o fatorial do número de peças no exemplo acima, é de 5 peças, para 120 possíveis permutações que podem ser codificadas.
Lembre-se de que existem bits de adição para os quadrados e cores vazios.
Exemplos
Vamos dar um exemplo de apenas QK restante
Total de 81 bits
Vamos dar e exemplo de apenas reis restantes
Coloque tudo junto
Então eu calculo a menor codificação para placa em 75bits (9 bits e 3 bits)
Ainda não foi calculado como esse esquema de codificação afeta o tamanho máximo.
Melhoria 4
Reduza o número de bits para rolagem para apenas 2 bits. Apenas jogue para o jogador que é a vez.
Pensando nisso, talvez seja melhor incluir apenas os 2 bits dentro do bloco de cabeçalho.
fonte
1111
para "nenhum en passant possível" ou a coluna como um número binário).192 bits (pior caso)
Aqui está um esquema de armazenamento muito simples que deve lidar com promoções arbitrárias de peões e nunca exige mais do que 64 + 4 × 32 = 192 bits:
Os primeiros 64 bits armazenam um painel de bits que indica onde estão as peças (mas não o que são). Ou seja, armazenamos um bit para cada quadrado do tabuleiro de xadrez (começando no quadrado a1, depois b1, c1 etc. até o quadrado h8), de modo que um quadrado vago seja representado por 0 e um quadrado ocupado por 1.
Em seguida, para cada um dos quadrados marcados como ocupados no bitboard, armazenamos uma mordidela de 4 bits que codifica a peça nesse quadrado. O primeiro dos quatro bits codifica a cor da peça (0 = branco, 1 = preto), enquanto os três bits restantes codificam o tipo da peça:
Observe as duas codificações do rei, usadas para determinar qual turno do jogador ele deve se mover. (De fato, como sempre existem dois reis no tabuleiro, permitindo quatro combinações dos códigos 5 e 6, poderíamos facilmente codificar um segundo bit de informação aqui.)
Para codificar as informações extras necessárias para as regras en passant e castling, introduzimos um tipo de peça adicional, que indica um peão ou uma torre, dependendo da linha em que aparece:
Juntando tudo:
O número total de bits necessários para codificar o estado da placa é, portanto, 64 + 4 × # de peças a bordo. Como nunca pode haver mais de 32 peças no quadro, o comprimento máximo dessa codificação é de 192 bits.
Por exemplo, usando a codificação descrita acima, o estado inicial da placa seria codificado como (espaço em branco inserido para facilitar a leitura):
ou, em hexadecimal:
fonte
Pior caso de 160 bits
Depois de postar minha resposta anterior em 22 bytes, comecei a me perguntar se conseguiríamos chegar a 21 bytes. No entanto, quando vi os incríveis 166 bytes de Peter Taylor, pensei: "Espere, parece que cinco palavras de 32 bits podem ser possíveis!"
Então, depois de muita reflexão, eu pensei nisso: 159.91936391 bytes (um ajuste bastante apertado!) Esse nível de compactação precisaria de um programa bastante complicado, mas eu pensei em como fazê-lo funcionar em tempo razoável.
Este será um post longo, portanto, tenha paciência comigo, publicarei o que puder hoje e adicionarei alguns bits de código em breve.
Então, aqui está como fazer isso:
En Passant e roque codificados por posições ilegais (0 bits)
En Passant
Como mencionado em outras respostas, há no máximo 5 quadrados possíveis nos quais um peão vulnerável a um passante pode ficar. Estes são os quadrados próximos aos peões do jogador em que é a vez.
Para codificar isso, o peão vulnerável a passante é trocado pelo que estiver em um dos quadrados na primeira ou na última linha. Pode ser um homem ou um quadrado vazio. Isso produz uma posição ilegal, pois os peões não podem estar nessas linhas. O decodificador deve retornar o peão à sua posição correta, extraindo as informações passantes.
Para que isso não interfira com a codificação de rolagem, é importante que os quadrados em que os reis estão no início do jogo não sejam perturbados e que o procedimento de codificação passante não coloque os reis próximos um do outro, o que seria uma posição ilegal do rei. Para satisfazer o segundo desses pontos, o codificador tem duas opções para qual quadrado ele troca o peão passante. O quadrado de primeira escolha para cada um dos cinco peões é A8, B8, C8, G8, H8. Segunda opção: A1, B1, C1, G1, H1.
Castling
Um rei que tem permissão de castelo está por definição, ainda em sua praça inicial. Com o rei branco em seu quadrado inicial, há um total de 63 quadrados onde o rei preto pode permanecer, 58 dos quais são legais (ele não pode se mover ao lado do rei branco porque se colocaria em xeque). Se o rei branco tem permissão de castelo, ele também pode castelo com sua torre esquerda, sua torre direita ou ambas. Existem, portanto, 3x58 = 174 possibilidades em que o rei branco pode dominar, outros 174 em que o rei preto pode dominar e mais 3x3 = 9 em que ambos podem dominar, um total de 357.
Existem 420 arranjos ilegais dos dois reis em quadrados adjacentes: 3x4 = 12 quando o rei branco está no canto, 5x24 = 120 quando ele está no limite e 8x36 = 288 quando ele está em outro quadrado. Portanto, existem facilmente posições ilegais suficientes para codificar todas as possibilidades possíveis de rolagem.
Se pelo menos um rei puder castigar, o codificador procurará os dados de castelos e os dados posicionais daqueles reis que não podem castigar em uma tabela (ou, alternativamente, use um algoritmo que não especificarei aqui) e produzirá um código ilegal. posição dos dois reis. Trocaria então os reis com o que acontecesse nessas praças.
É importante que isso seja codificado e decodificado antes do passante, caso contrário, existem algumas interferências em potencial.
Comparação
Até agora, não usei bits! Olhando para a resposta de Peter, ainda tenho o seguinte para codificar:
Este é o pior caso de 29 homens (veja a resposta de Peter.) Abaixo mostrarei como faço uma melhoria marginal (pelo menos no caso de 29 homens) em ambos os pontos marcados em **.
Quais quadrados estão ocupados / de quem é a vez?
A maneira fácil de codificar quais quadrados são ocupados é com uma grade de 64 bits. Isso também nos diz quantos quadrados estão ocupados. No entanto, é um pouco de desperdício, porque não é possível haver mais de 32 quadrados ocupados. Minha solução é usar 1 para codificar para os quadrados ocupados quando for a vez das Brancas e 0 para codificar para quadrados ocupados quando for a vez das Pretas. Agora todas as combinações são usadas e não há desperdício.
Assim, economizamos um pouco para armazenar o turn: menos de 32 1, é a vez das brancas, mais de 32 1, é a vez das pretas. O único caso ambíguo é quando todos os homens estão no quadro e há 32 1 e 32 0. Portanto, um bit extra é necessário apenas para este caso. Como não pode haver promoções até que uma captura ocorra, esse bit extra não afeta o pior caso geral (o que ocorre com 3 homens capturados e 29 restantes).
Cor dos homens ocupando as praças
Sabemos do exposto quantos homens existem. O extrato a seguir do triângulo de Pascal conta quantas possibilidades existem para as diferentes distribuições de preto e branco. Por exemplo, para 3 homens, as possibilidades são: 3 homens negros (1 permutação) 2 pretos, 1 branco, (3 permutações), 1 preto, 2 brancos (3 permutações), 3 brancos (1 permutação). O total é 2 3 = 8. Em geral, para os números mais baixos de homens existem 2 n possibilidades. No entanto, todas as possibilidades de preto e branco são ilegais (pelo menos o rei de cada lado deve estar no tabuleiro), portanto o número real de permutações legais é 2 n -2 (ignore os 1s no triângulo Pascal).
Para mais de 16 homens no total, há uma restrição adicional, pois não pode haver mais de 16 homens de cada cor no quadro. Portanto, quando todos os 32 homens estão no quadro, deve haver 16 de cada um e o número total de possibilidades é 601080390, que é um pouco menor que 2 32 .
O número de possibilidades pode ser encontrado somando as "linhas" deste extrato do triângulo de pascal (com o que quero dizer as diagonais NE-SW da tabela, porque eu girei o triângulo 45 graus no sentido anti-horário para uma apresentação conveniente. para codificar o turno, os quadrados ocupados e a cor dos homens são, portanto, os seguintes:
Até 25 homens: pouco menos de 64 anos (número de homens)
Para mais de 25 homens:
Para as duas cores, quais homens e em que ordem?
De acordo com as respostas anteriores, nenhum peão pode ser promovido até que uma captura ocorra, porque cada peão é bloqueado por um peão da cor oposta na mesma coluna. A resposta de Peter considerou (como limite superior) que toda captura poderia levar a uma promoção para o lado que estava sendo capturado e duas para a captura lateral. No entanto, podemos dividir isso em vários casos:
O peão preto captura o peão branco: agora o peão de captura está livre para promover, pois ele está agora em uma coluna diferente. Seu colega na mesma coluna também pode promover. O peão preto na coluna original do peão branco também pode ser promovido. Este é o único caso que permite 3 promoções.
O peão preto passa pelo peão branco na coluna adjacente e depois captura a peça branca (exceto o peão) por trás. Isso permite que o peão de captura e o peão branco que estava na coluna original sejam promovidos. Uma promoção para cada lado.
O peão branco é capturado por peça (exceto o peão.) Isso normalmente permitiria uma promoção apenas para as pretas. A única exceção é quando ele libera uma formação de peão bloqueada que já foi causada por várias capturas que movem peões para a mesma coluna.
Portanto, como caso base, podemos considerar que cada captura permite uma promoção para os dois lados. No caso de o homem capturado ser um peão, pode haver uma promoção adicional para o lado da captura.
Eu escrevi um programa semelhante ao de Peter. É um pouco mais grosseiro, mas tem uma adição importante: pode calcular o número de permutações possíveis quando um jogador começa com menos do que os 8 peões normais. Aqui estão alguns dados produzidos pelo programa:
Podemos ver que, para um caso como 8 peões, 15 homens, 0 promoções, o número de permutações é apenas ligeiramente menor do que para 8 peões 16 homens, 0 promoções. No entanto, se considerarmos um caso como 7 peões, 15 homens, 0 promoções (o que é o mesmo que considerar que o homem capturado era definitivamente um peão), obteremos cerca da metade do número de permutações.
Portanto, para o caso de preto ter 16 homens e branco 15, podemos considerar uma estimativa superior de 2 promoções para preto e uma promoção para branco:
No entanto, podemos fazer melhor se procedermos da seguinte maneira.
A. Considere uma promoção para Black and White, assumindo que o homem que White perdeu pode ser de qualquer tipo:
B. Considere as possibilidades adicionais para as pretas se ele tiver duas promoções, multiplicadas apenas pelas possibilidades para as brancas nas quais ele perdeu um peão.
Somando esses dois, obtemos 2.25072E + 18, que é um número menor que 3.55766E + 18. Todas as possibilidades para até 3 capturas (29 homens restantes) estão listadas abaixo.
Portanto, para o pior caso de um lado com 15 homens e o outro com 14 homens, precisamos de 67,804 bits.
Adicionando isso aos 92.116 bits necessários para especificar quais quadrados e quais cores, obtemos um total de 67,804 + 92,116 = 159,92 bits.
fonte
Pior caso de 177 bits
Esse algoritmo, embora dificilmente simples, fornece o pior cenário de 177 bits (184b = 23B na prática), 13b (16b = 2B) no melhor cenário quando restam apenas dois reis.
fonte
sum_{i=0}^{15} sum_{j=0}^{15} 62! / (i! j! (62-i-j)!) < 2^87.45
.166 bits
1
bit: de quem é a vez?2
bits: quais opções de rolagem estão abertas? (Nota: lendo atentamente a pergunta, é necessário apenas registrar as opções de boliche para o jogador em que turno é).lg 6 ~= 2.585
bits: quais opções en passant estão abertas? (Veja minha outra resposta)lg sum_{i=1}^{16} sum_{j=1}^{16} 64! / (i! j! (64-i-j)! = lg 3629590441720924477681996172 ~= 91.552
bits: quais quadrados são ocupados por homens de que cor?lg 451366131803622235200 ~= 68.613
para indicar quais homens e em que ordem (veja abaixo)Usando codificação aritmética (já que a cada passo estamos aplicando uma distribuição uniforme), podemos obter
ceil(3 + 2.585 + 91.552 + 68.613) = 166
bits.A codificação para os homens: dado que sabemos quantos homens de uma determinada cor existem, podemos enumerar facilmente todas as distribuições / multisets possíveis de homens (por exemplo, com 5 homens, podemos ter um rei, uma rainha, duas torres e uma Peão) e então podemos considerar todas as permutações possíveis de cada distribuição.
No entanto, podemos melhorar ainda mais, levando em consideração as interdependências. Só estou fazendo isso em um nível muito básico: quantas promoções possíveis? Um peão só pode ser "aprovado" e capaz de promover de três maneiras: captura e, portanto, move-se para uma coluna diferente; ou seu peão oposto captura e então se move para uma coluna diferente; ou seu peão oposto é capturado. Assim, uma captura para branco cria potencialmente dois peões passados para branco e um para preto.
Podemos criar uma tabela parcial dos limites superiores nas promoções:
Também podemos calcular o número de permutações, considerando que um jogador tem
N
homens e não mais queP
peões promovidos:Combinando os dois, podemos obter o número de bits necessário para especificar as duas permutações, considerando o número de homens de ambos os lados:
Se não estiver nesta seção da tabela, podemos apenas assumir que ambos os lados têm até 8 promoções e ainda estamos indo melhor do que o pior caso, que é de 68.613 bits quando um tem 14 homens e o outro 15.
Observe que isso ainda está longe de ser uma representação perfeita, pois permite muitas posições ilegais.
Código para o cálculo da tabela de permutação:
fonte
<
pouco do que<=
no loop de saída do meu programa. Obrigado por apontar isso. Eu ainda conseguia recuperar a pontuação anterior colocando os 32 homens no quadro, mas não farei isso agora.178 bits (174 em uma pitada!) Pior caso
Olá, acabei de voltar à codificação, o que realmente não faço desde a faculdade. Vi este site e achei interessante. Fiz uma pequena verificação terórica e parece que são necessários pelo menos 146 bits para um algoritmo perfeito, provavelmente muito mais (explicarei nos comentários quando tiver um momento).
Enfim, é assim que eu estruturo os dados. O conceito básico é de 178 bits, mas com alguns truques de jiggery, ele pode ser reduzido para 174 (são 21 3/4 bytes). 175 é um pouco mais fácil de programar, mais legível por humanos e ainda dentro de 22 bytes.
A) Posição de ambos os reis: 6 bits cada para brancas e pretas de 12 bits
B) Dos 62 quadrados restantes, quais são ocupados? Uma matriz de 62 bits
C) De quem é a vez? 1 BIT
TOTAL ATÉ: 75 BITS
D) En Passant. Se for a vez das brancas se moverem, até 5 peões pretos podem parecer capturados En Passant. O peão preto deve estar na linha 5 (de baixo para cima começando em zero) e ter um peão branco ao lado. Uma situação com o número máximo de capturas possíveis é assim:
BWBBWBBW
Se houvesse 6 peões pretos na linha 5, o branco teria apenas 2 quadrados para permanecer e só poderia ameaçar 4 peões pretos, portanto, não é possível ter mais de 5 peões pretos aparentemente ameaçados por En passant ao mesmo tempo. Portanto, precisamos de um número de 1 a 5 indicando qual dos (até 5) peões na linha 5 que possui um peão hostil (neste caso branco) próximo a ele foi avançado 2 quadrados no último turno ( ou zero se nenhum peão nessa situação foi movida dessa maneira no último turno.)
E) Dos até 30 quadrados ocupados (sem incluir reis), o que eles contêm?
Existem 10 possibilidades, cada uma representada por um número decimal.
O bit menos significativo representa a cor.
Portanto, números pares são brancos, números ímpares são pretos.
Branco preto
Peão 0/1 (ou Torre com permissão de castelo *)
Knight 2/3
Bispo 4/5
Torre 6/7
Rainha 8/9
* Uma torre com permissão de castelo (e, portanto, nunca foi movida da primeira ou da última linha) é representada por 0 ou 1 em vez de 6 ou 7. Não pode ser confundida com um peão, porque os peões não podem ser encontrados na primeira ou última linha.
Isso fornece um número decimal de até 30 dígitos, que podemos multiplicar por 6 e, em seguida, adicionar o código para En passant. O número resultante caberá em 103 bits, que quando adicionados aos 75 mencionados acima são 103 + 75 = 178 bits . Na verdade, se simplesmente multiplicarmos por 10 em vez de 6, não faz diferença para o número de bits usados e a decodificação é mais fácil.
Isso é apenas 2 bits a mais que 22 bytes. No entanto, podemos reduzi-lo para 174 bits, conforme explicado abaixo.
Se nenhuma peça foi capturada, é impossível promover um peão .
A prova é a seguinte. Imagine que o branco está obcecado em promover seu peão (por exemplo) na coluna E, desde o início do jogo. Há um peão preto em frente a esse peão que está no caminho. Portanto, para promover esse peão, uma das seguintes ações deve acontecer:
1) O peão preto é capturado.
2) O peão preto captura outra peça e, portanto, se afasta do caminho.
3) o peão branco captura um peão em uma coluna adjacente, como a coluna D.
4) o peão branco passa (ou é passado por) um peão preto em uma coluna adjacente e depois captura uma peça nessa mesma coluna adjacente, fazendo com que o peão branco mude de coluna.
O caso 4 é o mais interessante, porque não é apenas o peão branco que começou na coluna E que agora tem um caminho claro para a promoção. O peão preto na coluna que permanece na coluna E também pode ser promovido. Portanto, uma única captura pode abrir caminho para um peão de cada cor promover.
De qualquer forma, o fato de que nenhum peão pode promover até que uma peça seja capturada significa que não precisamos armazenar a 30ª peça. Podemos resolvê-lo por eliminação (ou por subtração, porque o conjunto completo de códigos de peças no início do jogo sempre soma a mesma quantidade = 80). Um ponto menor é que devemos garantir que os quadrados onde as torres A posição no início do jogo está entre as primeiras verificadas (porque, se elas fossem a última, não saberíamos se a torre poderia ter ou não castelo). Isso é facilmente feito pela verificação da linha 0 e das linhas 7 a 1: Para r = 8 a 1 linha de varredura [r mod 8].
Portanto, a matriz de bits em (B) nos dirá quantas peças existem (excluindo reis.) Se houver 30, ignore a última peça ao codificar, o decodificador descobrirá o que era. Agora temos um número decimal de até 29 dígitos, que multiplicamos por 6 e adicionamos ao código En Passant. O número resultante será compactado em 99 bits, resultando em um total de 99 + 75 = 174 bits.
Como exemplo Aqui está uma posição real. As brancas acabam de fazer seu primeiro movimento (peão avançado do rei) e é a vez das pretas.
A) Posição dos reis (branco / preto no octal, 12 bits ): 03 73 = 000011 111011
B) Quais quadrados estão ocupados? Comece com a linha zero (linha inferior) e depois todas as outras linhas de cima para baixo, pulando os reis:
C) Turno do preto: Turn Bit = 1
D) En Passant. Não existe um peão branco ao lado de um peão preto; portanto, não há peões que possam ser capturados passant (mesmo que esse peão tenha avançado no último movimento), então D = 0. Se, em vez de considerar apenas peões com um peão hostil ao lado, considerarmos todos os peões que não têm peças amigáveis ao lado dos dois lados, D seria 1, pois existe um peão nessa situação, e esse particular o peão foi realmente movido no último turno.
E) Novamente, fileira de baixo primeiro, depois todas as outras fileiras de cima para baixo, pulando os reis e com as quatro torres sem cascas referidas como 0 ou 1 (números normalmente reservados para peões).
O trigésimo dígito (entre colchetes) pode ser descartado.
Embora não seja muito aparente aqui, o peão que as Brancas avançaram está na verdade em uma extremidade da lista de peões, porque examinamos linha por linha.
Nossos dados agora são assim, com 29 códigos para o conteúdo dos quadrados, mais o código En Passant:
É melhor digitalizar da direita para a esquerda ao decodificar e da esquerda para a direita (ordem inversa) ao codificar. Isso significa que, quando houver menos peças, teremos um número menor, mantendo a máxima consistência (ou seja, queremos que o espaço em branco / zeros esteja à frente, não à direita, para permitir a compactação de tábuas escassamente ocupadas.) Quando temos apenas dois reis no quadro, teremos os 75 bits mencionados acima, mais 3 bits para armazenar dados passantes = 78 bits no melhor caso. Cada peça adicional vem um pouco abaixo de 3,5 bits (duas peças podem ser armazenadas em 7 bits, porque 100 <128).
Há um problema prático em que um número inteiro de 99 bits é grande demais para caber em uma variável inteira de 64 bits, o que significa que muitas linguagens de programação não fornecem suporte para ele (você não pode simplesmente converter uma representação de string de 29 a 30 dígitos número para um número inteiro.) Como uma maneira fácil de codificar para 22 bytes, que pode quebrar uma série de 30 dígitos (29 códigos peça + de passagem código) em duas 15 algarismos cada uma das quais vai encaixar em 50 bits cada (total de 100 bits além dos 75 mencionados acima, é o pior caso para 175 bits.)
Para a compactação máxima, como mencionado acima, 29 dígitos decimais mais o código En Passant (6 valores possíveis) caberão praticamente em 99 bits (para um total de 174 bits), mas sem o suporte do idioma para números inteiros desse tamanho, é complicado de programar. Pode ser mais fácil separar os 29 bits de cor e trabalhar com os códigos de peça (5 possibilidades) e o código En passant (6 possibilidades) separadamente das cores (70 bits, quase se encaixa em uma variável de 64 bits).
fonte
Aqui está uma solução completa, o pior caso real, 181 bits
O foco aqui é um programa simples que você pode entender facilmente
A entrada é FEN, aqui está a posição de abertura, possui seis campos (5 e 6 ignorados):
O primeiro campo (posicionamento da peça) é analisado
Para produzir:
Campo um: codifique a localização dos reis (12 bits):
Campo dois: codificar peças (até 5 bits por peça):
Campo três: cor ativa (1 bit)
Campo quatro: disponibilidade de rolagem (4 bits)
Campo cinco: en passant (zero ou 3 bits)
Pior caso ingênuo 200 bits
QRRBBNN QQQQQQQQ
- 75 bitsqrrbbnn qqqqqqqq
- 75 bitsPior caso real
Cada jogador não pode promover todos os peões sem capturar outras peças . Aqui está o efeito de entropia da captura de peças:
PpR
(3 + 3 + 5 = 11 bits) =>Qq_
(5 + 5 + 1 = 11 bits)PPpp
(3 + 3 + 3 + 3 = 12 bits) =>QQq_
(5 + 5 + 5 + 1 = 16 bits)Na verdade, o pior caso é:
QRRBBNN QQQQQQQQ
- 75 bitsqrrbbnn qqqq
- 55 bitsO pior caso é promover todas as peças, em vez de deixar o peão para en passant.
Pior caso real total com código mostrado 12 + 75 + 55 + 34 + 1 + 4 = 181 bits
O FIQ mostra duas melhorias nesse esquema simples, mas são mais difíceis de codificar:
O único código restante não mostrado nesta resposta (por questões de brevidade) é: quebra da entrada FEN nos campos (
split /\s/
) e atribuição de variáveis.fonte
PPpp
=>QQq_
Dados totais precisam de 33 bytes
(Graças a alguém nos comentários, percebi que isso não funciona na promoção de peões. Atualizarei isso quando eu puder resolvê-lo)
para o primeiro byte, usamos cinco bits:
os próximos 32 bytes são usados para representar cada peça de xadrez, em uma ordem predefinida
mais à esquerda representa se foi capturado. 0 = não capturado
(se pode passar, então definitivamente não é capturado)
Algum código C para representar essa ideia (que na verdade não funciona)
fonte
256242 bitsAqui está um algoritmo básico de compactação que provavelmente pode ser aprimorado porque não exclui a representação de certas posições ilegais.
O quadro começa com 5 bits de informações do cabeçalho, da seguinte maneira:
Então, uma sequência de 12 bits representando as posições dos reis.
Em seguida, um número enorme de 64 dígitos na base 11, que é multiplicado por 9 para adicionar outro dígito no final representando o estado do en-passant. Cada dígito na base 11 representa um quadrado no quadro, com os seguintes valores possíveis:
E os dígitos na base 9:
11 64 × 9 é de cerca de 2 224,57 , o que requer 225 bits para codificar. Além disso, os 17 bits de cabeçalho na parte superior representam um total de 242 bits.
Obrigado a ugoren pelas melhorias.
fonte
13^64 * 9
é 239,99, economizando 11 bits. Economize mais codificando posições king separadamente.? bits
(≥ 217 pior caso, 17 melhor caso, 179 para o quadro inicial)
Descrição da codificação
Metadados extras consistem em quem é a vez (um bit) e roque (quatro bits, ou seja, pode o castelo branco do lado dos reis - do lado das rainhas - e da mesma forma para o preto).
Para a própria posição do tabuleiro, nós o codificamos como um conjunto de peças ativas. Bem, na verdade, certifique-se de enumerar as peças em uma ordem específica por razões que explicarei um pouco. Para cada peça, armazenamos sua cor (um bit), seu tipo (três bits para abranger 6 tipos, mais um tipo extra para "peão que pode ser levado por en passant"), bem como sua posição.
Aqui está a parte interessante: para codificar a posição de uma peça, em vez de armazená-la como coordenada, armazenamos sua distância relativa da última peça ao enumerar as peças na ordem da esquerda para a direita e de cima para baixo (por exemplo, A8 , B8, ..., G1, H1). Além disso, armazenamos a distância como um número de comprimento variável, usando
1
para significar que esta peça está ao lado da anterior,0xx
para pular 1-3 peças,000xxx
para pular 4-10 peças,000000xxxx
para 11-25,0000000000xxxxx
para 26-56 e finalmente000000000000000xxx
para 57-62.Exemplos
Fiz um resumo de algumas posições codificadas com essa codificação e anotei a posição inicial com alguns comentários.
Não sei como analisar o pior tamanho de bit, mas seguindo os exemplos da essência, acredito que o algoritmo deve ser um pouco eficiente, pelo menos.
Implementação do decodificador
Abaixo está um decodificador rápido e sujo para essa codificação (tomando como entrada os dados binários codificados no texto, como no exemplo anotado acima, e pulando sobre coisas que não são '0' ou '1'). Produz um tabuleiro de xadrez unicode para stdout.
fonte
Máx: 184 bits, Mín: 75 bits
Fui inspirado pela Huffman da @ AdamSpeight que codifica peças para tentar criar meu próprio esquema. Duvido que isso vença, mas tem limites calculáveis.
Este esquema trata as peças de xadrez como se houvesse 11 tipos diferentes de peças. Segui aproximadamente o algoritmo de codificação Huffman para agrupar essas classes por suas frequências e tipos reais para gerar as seguintes codificações:
O código de cada peça pode ser precedido por dois bits para mostrar a qual time pertence (
10
para branco,11
para preto).0
pode ser usado para codificar espaços vazios. Essas idéias nos permitem criar uma codificação quadrado por quadrado para todo o quadro, usando o procedimento que desejarmos. Assumirei a ordem da iteraçãoa1, b1, c1, ... f8, g8, h8
. Isso significa que apenas listar esses códigos, como mostrado acima, codifica todas as informações, exceto de quem é a vez. Um mecanismo de xadrez muito simples pode usar as "classes" para peões, torres e reis para determinar se o castiçal e o passante são legais. Além disso, esse esquema lida facilmente com promoções de peões. Se um jogador promove um peão para uma torre, os códigos do rei ou da rainha podem ser usados desde que a variante "movida" seja escolhida.Exceto as posições patológicas que eu acho que nunca aconteceriam, o pior cenário para essa codificação é quando todas as peças ainda estão no tabuleiro e o jogador anterior moveu um peão para a frente dois espaços. Como exemplo, o quadro abaixo codifica
1. e4
:Isso significa que a pior codificação tem 184 bits: 1 para indicar o jogador, 32 para os espaços vazios, 45 para os peões imóveis, 6 para o peão com dois saltos, 24 para os cavaleiros, 24 para os bispos, 28 para as torres, 12 para as rainhas e 12 para os reis.
À medida que as peças se movem e são capturadas, o tamanho da codificação diminui. O melhor cenário é representado por dois reis sozinhos no tabuleiro: 1 bit para indicar o jogador + 62 bits para indicar os quadrados vazios + 12 bits para indicar os reis fornece um comprimento mínimo de 75 bits.
Voltarei e editarei esta resposta com algum código que demonstra essa codificação em ação mais tarde hoje ou amanhã. Por enquanto, estou curioso para ver o que as outras pessoas pensam dessa codificação.
fonte
11001
significaB'S MOVE
W CAN KSC
W CANT QSC
B CANT KSC
B CAN QSC
). Ou seja, 4 bits em vez dos 5 bits por lado na sua codificação ou 3 bits por lado se você eliminar o marcador lateral nas torres. (KSC
Castelo = Rei-lado.QSC
= Castelo Queen's-side)184 bits = 23 bytes no pior caso, e não é muito complicado:
A. Quais quadrados ocupados: 64 bits = 8 bytes B. Quais cores para os <= 32 quadrados ocupados: 32 bits = 4 bytes E agora usando apenas os <= 30 quadrados ocupados por não-reis: B. use o PNBRQ codificado em raiz 5, para 5 ^ 30 possibilidades; e 32 * 31 * 2 * 4 * 4 * 9 para posições de rei, direitos de cor castanho, branco e preto, en passant square (entre 8 possibilidades mais nenhuma, a 9); esse número 5 ^ 30 * 32 * 31 * 2 * 4 * 4 * 9 = 266075134277343750000000000 = 2 ^ 87.782 se encaixa em 88 bits para um total de 64 + 32 + 88 = 184 bits para toda a codificação.
Isso pode ser reduzido, por exemplo, 32 * 31 * 2 * 4 * 4 * 9 = 285696 pode ser reduzido para 2 * (32 * 31 + 31 * 3 + 31 * 3 + 3 * 3) * 6 = 14244, usando fact no máximo 6 en vítimas-candidatos passantes (incluindo nenhuma) e codificação de direitos de castling e posições de rei dentro do mesmo conjunto usando direitos de castling de fatos apenas importam quando rei no quadrado inicial. Isso economiza 4 bits.
Tenho motivos para acreditar que não é possível obter 18 bytes, ou seja, o número total de posições legais no xadrez excede 2 ^ 144.
Seu esquema de 160 bits é muito engenhoso, mas acho que ele precisa ser fornecido como programas de codificação / decodificação antes de estar completamente confiante.
fonte
Pior caso de 171 bits:
Combinei algumas idéias e alguns de meus próprios pensamentos.
Vamos começar com uma placa de 64 bits. Cada bit representa um espaço ocupado no quadro. Eles preenchem ao longo das linhas. Portanto, o início se parece com:
1111 1111 1111 1111 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
Agora, cada peça será representada por 4 bits. 1º bit: color (
0=white, 1=black
) 2º-4º bits: um dos 8 tipos.No final, incluiremos um pouco para designar a curva.
0=white, 1=black
.4bits * 32 peças = 128 bits e já tenho 64 + 1 no turn e no board. Isso dá um total de 128 + 64 + 1 = 193 que eu nem comecei com en passant ou castling. Bem acima do meu limite sem nada - nem sequer vira. É aqui que os truques começam.
Ok - você vê esses tipos acima? Bishop0 e Bishop1? Peão0 e peão1? Esses tipos são assim designados, porque nos dizem um pouco para inserir depois desta peça. Portanto, Bishop0 significa que, depois disso, haverá um 0 - ou seja, a próxima peça será branca. Bishop1 nos diz que a próxima peça é preta, e o peão0 e o peão1 funcionam da mesma maneira. (Se esta peça é a última peça sendo enumerada, ela nos informa sobre o próximo turno).
Meu pior caso envolve todas as peças do tabuleiro; portanto, com 16 peões e 4 bispos, isso me economiza 20 bits. Estou com 173.
OK. Por outro lado, no meu pior caso - uma vez que há 16 cores codificadas, paramos de codificar cores - como a conhecemos. Meu pior caso agora envolve uma peça branca chegando ao canto mais distante sem capturas. Lá, economizo apenas um pouco. 172
Agora vou mudar a ordem em que nomeio as peças. Vamos nomeá-los ao longo de colunas começando do lado de fora, movendo-se para dentro. O quadro nomeado no início permanecerá o mesmo, mas quando eu coloco peças nele, começo de branco no canto inferior direito e subo a coluna. Então pulo para o canto inferior direito do preto e subo a coluna. Eu pulo para a célula desconhecida no canto inferior direito do branco, e assim por diante - isso significa que meu pior caso é novamente o começo. Minha razão tem a ver com o meu truque passante, os próximos dois bits que eu perco e com a bola.
Agora, para que um peão seja promovido (como já foi discutido em detalhes), uma peça deve ser capturada. Assim, quando sabemos que existem 32 peças, precisamos apenas denotar 31 delas. A última peça é identificada exclusivamente. Acontece que, para mim, isso economiza apenas 2 bits - porque minha última peça pode ser um peão / bispo (que normalmente me custa 3 bits porque eu salvo uma na peça seguinte), cuja cor já está determinada e, portanto, era apenas 2 bits. Estou com 170 bits.
Quando os peões são promovidos, eles simplesmente mudam de tipo. Para cada peça que sai do tabuleiro, me livrei de (no mínimo) 3 bits e duas promoções de peão me custaram 2 bits, então estou recusando (lentamente) as promoções.
Castling. Para que o roque aconteça, nem rei nem torre relevante podem ter se movido. Assim, quando uma torre é capaz de arremessar, ela e o rei estarão em seus lugares originais. Assim, as torres capazes de rolar serão listadas no mesmo local que os reis dessa cor. Como isso é ilegal (dois reis ou três da mesma cor no quadro) e só pode acontecer em três configurações possíveis para cada cor (esquerda, direita, ambas as torres são listadas como reis) - a decodificação é totalmente possível. Portanto, para nenhum bit codificamos o castling.
En Passant Aqui também usaremos posições ilegais. Apenas um peão pode estar em risco de passante de cada vez. Ele deve estar na quarta linha. O peão vulnerável será 'invertido' de volta à sua linha inicial - alternado com o que estiver lá. Como esse peão está em sua própria primeira linha - uma posição ilegal, a situação será óbvia para o decodificador - ele reverterá as posições e marcará o peão como vulnerável a passantes.
Precisávamos mexer com o pedido, porque a última peça precisa ser 'identificada exclusivamente'. Em uma ordem padrão, não poderíamos dizer se a torre no canto de trás poderia se erguer - isso não é conhecido. Quando trabalhamos de fora para dentro, garantimos que, onde quer que a torre seja 'listada', seja em seu próprio canto ou no meio do tabuleiro, porque foi trocada por um peão passável e vulnerável, haverá uma peça listada depois - então nos dizem o tipo da torre. Sabemos que haverá uma peça depois dela, porque, para que um peão seja vulnerável, deve haver um peão em seu interior (que será crucialmente codificado posteriormente conforme as instruções acima).
Ah, e para ajudar a garantir que o pior caso envolva todas as peças do tabuleiro, uma vez que tenhamos menos de 32 peças, podemos usar a placa de 64 bits para identificar as curvas e as posições ocupadas usando 0 para representar peças quando as peças brancas virar e 1 quando é preto virar.
Então, nós passamos e passamos de graça. Escolhemos a última peça de graça, embora demorasse algum tempo para finalizar o jogo com as regras do passante e do castling. Abaixamos 20 bits nas peças padrão. Creio que o pior caso aqui envolve um peão branco médio movido para frente e uma peça preta entre ela e sua rainha enquanto todas as peças estão no tabuleiro. Verificação dupla rápida: a primeira peça é capturada - chame-a de peão, 3 bits do tabuleiro no peão, 3 bits no tabuleiro na forma de uma última peça, um bit no marcador de turno desaparecendo. Promova dois peões 2 bits novamente no tabuleiro. Ah, droga, estou com 171.
EDIÇÃO Adicionei código para um decodificador (funcionando?) - no R - abaixo. Pega vetores de booleanos como entrada - (desculpe, eu não sou capaz de codificar bem em qualquer coisa que me permita realmente usar os bits). Também incluí a posição inicial.
Este código cria 4 funções. Um que faz uma separação básica das peças e da estrutura do tabuleiro, além de descobrir o tipo de peça e quaisquer peças "implícitas". A próxima função preenche a estrutura do quadro com essas peças em uma ordem ligeiramente bizarra (e diferente da do meu algoritmo inicial) [explicada nos comentários do código]. A próxima função pega a placa preenchida e detecta todas as posições ilegais - ela as corrige e renomeia os peões que são vulneráveis ao passante "x peão-e" e a qualquer torre que possa "x rook-c". A função final é um invólucro que executa essas funções em ordem e fornece uma saída que é a placa atual e também o turn.
Também incluí a codificação da posição inicial (no entanto, para vê-lo, você precisará chamar
c(startboard,newpieces)
e o código chama a função wrapper nessa posição.fonte
229/226 bits
Isso não é muito bem-sucedido, mas pode salvar outras pessoas no mesmo caminho.
A versão simples:
1
pouco para quem é a vez4
bits para as quatro possibilidades de rolagem3
bits para as possibilidades en passant . Isso tem mais profundidade do que eu entendi a princípio. En passant deve ser feito por um peão que se move da mesma fila (linha) que o peão que é capturado. A análise de caso indica que, uma vez que sabemos quantos peões da cor que foi movida pela última vez avançaram exatamente dois quadrados, haverá no máximo 6 casos passantes (incluindo o caso em que não há peão vulnerável a passantes ). O pior caso são 5 peões (potencialmente todos vulneráveis: por exemplo,PpPPpPPp
tem cinco vulneráveisP
). Com 6 peões, existem no máximo 2 peões inimigos na mesma fila, cada um dos quais pode ameaçar no máximo 2 peões de passagem . Portanto, precisamos deceil(lg 6) = 3
bits aqui.Depois o quadro. A placa possui 64 quadrados, portanto, um índice quadrado pode ser codificado em 6 bits. Listamos os homens por categoria, cores alternadas, começando pelo rei.
6
bits: posição do rei branco. (Garantido para estar no quadro).6
bits: posição do rei preto. (Garantido para estar no quadro. No pior dos casos, o rei branco está em um canto, existem 60 lugares possíveis; ele pode estar; no melhor caso, o branco não está no limite, existem 55).6
bits: posição da rainha branca. Se não houver rainha branca, repita a posição do rei branco como sinal.1
pouco seguido por 6 bits para a posição.0
pouco0
bit final .Isso custa alguns
12
bits para os reis e2*7*5-1 = 69
bits para os outros homens. Na pior das hipóteses, todos os 32 homens estão no conselho, custa7
bits para cada homem que não seja os reis, no total12 + 7*30 - 1 = 221 bits
. Portanto, com os8
bits iniciais do estado global, temos 229 bits .A versão avançada:
Usando a codificação aritmética, podemos operar com
lg num_possibilities
e não usarceil(lg num_possibilities)
apenas umaceil
no final.1
pouco para quem é a vez4
bits para as quatro possibilidades de rolagemlg 6
bits para as possibilidades en passant .6
bits para o rei brancolg 60
bits (pior caso) para o rei pretolg 63
bits (porque eu não quero complicar ao nível de verificações) da rainha branca, usando a posição do rei branco se não houver1
pouco, seguido porlg 62
,lg 61
, etc. bits para a sua posição.0
poucolg 63
bits (ou menos, se houver rainhas brancas) para a rainha negra.O enésimo homem que está realmente presente tem
66-n
valores possíveis. Se um tipo estiver ausente para uma cor, gastamos66-#men so far
bits gravando isso (mais um bit para o separador). Os casos extremos são:5+lg 6
no estado global,6+lg 60
nos reis,29
em bits separadores eSUM_{n=32}^{63} lg n
bits em posições. Total geral:ceil(225.82)
bits. Decepcionante.5+lg 6
no estado global,6+lg 60
nos reis,29
nos bits separadores,8*lg 63
dizendo que não há outras peças eSUM_{n=48}^{63} lg n
nas posições dos peões. Total geral:ceil(188.94)
bits. Melhor - salvando a segunda torre, cavaleiro e bispo para cada lado que avançamos um pouco.Portanto, o pior caso parece ser 226 bits , para uma economia de 3.
Definitivamente, podemos fazer melhor codificando peões antes de peças, já que eles são restritos a 48 quadrados em vez de 64. No entanto, no pior dos casos, todos os homens estão no tabuleiro e todos os peões foram promovidos, eu acho. isso acabaria custando 2 bits a mais porque precisaríamos de uma bandeira "sem peões" em vez de poder contar os homens.
fonte
Este é um tópico de discussão nos círculos de xadrez.
Aqui está uma prova muito simples com 164 bits https://groups.google.com/forum/#!topic/rec.games.chess.computer/vmvI0ePH2kI 155 é mostrada aqui http://homepages.cwi.nl/~tromp /chess/chess.html
Sobre estratégia simplificada:
fonte
Mín: 0 bits
Máx:
1734243 bits (4,3354,401 bits / placa amortizados)Esperado:
351177 bits (4,3764.430 bits / placa amortizados)Como eu posso determinar a entrada e a saída, no entanto, eu quero que eu decidi continuar com a codificação do histórico do jogo até este ponto. Uma vantagem é que as informações adicionais sobre quem é a vez, são passivas e quem tem a capacidade de localizar onde podem ser derivadas e não codificadas.
Tentativa 1:
Ingenuamente, pensei que poderia codificar cada movimento em 12 bits, 4 trigêmeos da forma (início x, início y, final x, final y), onde cada um possui 3 bits.
Assumiríamos a posição inicial e moveríamos as peças a partir daí, com o branco indo primeiro. O quadro é organizado de forma que (0, 0) seja o canto inferior esquerdo do branco.
Por exemplo, o jogo:
Seria codificado como:
Isso leva a uma codificação de 12 m bits em que m é o número de movimentos feitos
Por um lado, isso pode ficar muito grande; por outro, você pode considerar cada jogada como sendo seu próprio jogo, de modo que cada codificação realmente codifique m "tabuleiros de xadrez". Se você amortizou isso, obtém que cada "tabuleiro de xadrez" é de 12 bits. Mas acho que isso é um pouco trapaceiro ...
Tentativa 2:
Percebi que cada movimento na tentativa anterior codifica muitos movimentos ilegais. Então, decidi codificar apenas movimentos legais. Enumeramos os movimentos possíveis da seguinte forma, numere cada quadrado de modo que (0, 0) → 0, (1, 0) → 1, (x, y) → x + 8 y. Itere através dos ladrilhos e verifique se há uma peça e se ela pode se mover. Nesse caso, adicione as posições que podem ser encontradas em uma lista. Escolha o índice da lista que é a jogada que você deseja fazer. Adicione esse número ao total de movimentos em execução, ponderado por 1, mais o número de movimentos possíveis.
Exemplo como acima: A partir da posição inicial, a primeira peça que pode ser movida é o cavaleiro no quadrado 1, pode ser movida para o quadrado 16 ou 18, portanto, adicione-as à lista
[(1,16),(1,18)]
. Em seguida é o cavaleiro no quadrado 6, adicione seus movimentos. No geral, temos:[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos a jogada (12, 28), a codificamos como 13 na base 20, pois existem 20 jogadas possíveis.
Então agora temos o número do jogo g 0 = 13
Em seguida, fazemos o mesmo para o preto, exceto que numeramos os blocos ao contrário (para facilitar, não é necessário) para obter a lista de movimentos:
[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos a jogada (11, 27), a codificamos como 11 na base 20, pois há 20 jogadas possíveis.
Então agora temos o número do jogo g 1 = (11 ⋅ 20) + 13 = 233
A seguir, temos a seguinte lista de movimentos para o branco:
[(1,16),(1,18),(3,12),(3,21),(3,30),(3,39),(4,12),(5,12),(5,19),(5,26),(5,33),(5,40),(6,12),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27)(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos a jogada (6, 21), nós a codificamos como 13 na base 29, pois existem 29 possíveis.
Então agora temos o número do jogo g 2 = ((13 ⋅ 20) + 11) 20 + 13 = 5433
A seguir, temos a seguinte lista de movimentos para preto:
[(1,11),(1,16),(1,18),(2,11),(2,20),(2,29),(2,38),(2,47),(3,11),(4,11),(4,18),(4,25),(4,32),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos a mudança $ (10, 18) $ (10, 18)
Então agora temos o número do jogo g 3 = (((19 ⋅ 29 + 13) 20) + 11) 20 + 13 = 225833
E continue esse processo para todos os movimentos restantes. Você pode pensar em g como a função g (x, y, z) = x y + z. Assim, g 0 = g (1, 1, 13), g 1 = g (g (1, 1, 11), 20, 13), g 2 = g (g (g (1, 1, 13), 20, 11), 20, 13), g 3 = g (g (g (g (1, 1, 19), 29, 13), 20, 11), 20, 13)
Para decodificar um número de jogo g 0 , começamos na posição inicial e enumeramos todos os movimentos possíveis. Em seguida, calculamos g 1 = g 0 // l , m 0 = g 0 % l , onde l é o número de movimentos possíveis, '//' é o operador de divisão inteira e '%' é o operador de módulo. Deveria sustentar que g 0 = g 1 + m 0 . Em seguida, fazemos o movimento m 0 e repetimos.
A partir do exemplo acima, se g 0 = 225833, em seguida, g 1 = 225833 = 20 // 11291 e m 0 = 225833% 20 = 13. Próximo g 2 = 11291 // 20 = 564 e m 1 = 11291% 20 = 11. Então g 3 = 11291 // 20 = 564 e m 2 = 11291% 20 = 11. Portanto, g 4 = 564 // 29 = 19 e_m_ 3 = 564% 29 = 13. Finalmente g 5 = 19 // 29 = 0 e m 4 = 19% 29 = 19.
Então, quantos bits são usados para codificar um jogo dessa maneira?
Para simplificar, digamos que sempre haja 20 movimentos a cada turno e, no pior dos casos, sempre escolhemos o maior, 19. O número que obteremos é 19 is 20 m
+ 19 ⋅ 20 m-1 + 19 ⋅ 20 m-2 + ⋯ + 19 ⋅ 20 + 19 = 20 m + 1 - 1 onde _m é o número de movimentos. Para codificar 20 m + 1 - 1, precisamos do log 2 (20 m + 1 ) bits que é de cerca de (m + 1) ∗ log 2 (20) = 4,3219 ∗ (m + 1)
Em média, m = 80 (40 movimentos por jogador), o que levaria 351 bits para codificar. Se estivéssemos gravando muitos jogos, precisaríamos de uma codificação universal, pois não sabemos quantos bits cada número precisará
Na pior das hipóteses, quando m = 400 (200 movimentos por jogador), isso levaria 1734 bits para codificar.
Observe que a posição que queremos codificar deve ser dada pelo caminho mais curto para chegar lá, seguindo as regras. Por exemplo, o jogo teorizado aqui não precisa de m = 11741 para codificar a posição final. Em vez disso, executamos uma pesquisa de largura em primeiro lugar para encontrar o caminho mais curto para essa posição e codificá-la. Não sei até que ponto precisaríamos ir para enumerar todas as posições do xadrez, mas suspeito que 400 seja uma superestimação.
Cálculo rápido:
Existem 12 peças únicas ou o quadrado pode estar vazio, portanto, para posicioná-las em um tabuleiro de xadrez é 13 64 . Essa é uma superestimação enorme, pois inclui muitas posições inválidas. Quando estamos m movimentos de jogo, criamos cerca de 20 m posições. Então, estamos procurando quando 20 m = 13 64 . Registre os dois lados para obter m = 64 * log 20 (13) = 54,797. Isso mostra que devemos conseguir chegar a qualquer posição em 55 movimentos.
Agora que calculei o pior caso para m = 55 e não m = 400, editarei meus resultados. Para codificar uma posição em que m = 55 leva 243 bits. Também vou dizer que o caso médio é de cerca de m = 40, o que leva 177 bits para codificar.
Se usarmos o argumento de amortização anterior, codificamos 400 "tabuleiros de xadrez" em 1734 bits, para que cada "tabuleiro de xadrez" ocupe 4,333 bits no pior dos casos.
Observe que g = 0 indica um jogo válido, aquele em que a peça no quadrado mais baixo se move para o quadrado mais baixo possível.
Notas Adicionais:
Se você quiser se referir a uma posição específica no jogo, pode ser necessário codificar o índice. Isso pode ser adicionado manualmente, por exemplo, concatenar o índice para o jogo ou adicionar um movimento "final" adicional, como o último movimento possível a cada turno. Agora, isso pode levar em conta os jogadores que concederam, ou 2 consecutivos para indicar que os jogadores concordaram com um empate. Isso só é necessário se o jogo não terminar em xeque-mate ou impasse com base na posição, neste caso, está implícito. Nesse caso, ele eleva o número de bits necessários em média para 356 e, no pior caso, 1762.
fonte