Napisz algorytm lub program, który może kodować i dekodować szachownicę. Celem jest jak najmniejsze przedstawienie szachownicy, którego można by użyć (po odkodowaniu) do określenia wszystkich możliwości ruchu dla gracza w tej turze.

Kodowanie musi pokazywać:

• Czyja to kolej.
• Czy gracz może zamek z każdej strony.
• Czy gracz może wykonać en-passant, a jeśli tak, to który z jego pionków?
• Pozycje wszystkich elementów.

Ważna uwaga na temat roszowania: jeśli białe przesuną swojego króla o jedną turę, a następnie cofną go o następną, musi być jasne, że po tym nie mogą się zamykać po żadnej ze stron. To samo by się stało, gdyby przenieśli swoją lewą lub prawą wieżę. Chociaż plansza jest wizualnie w tym samym stanie, co dwie tury temu, stan gry się zmienił. Więcej informacji tutaj: http://en.wikipedia.org/wiki/Chess#Castling

Ważna uwaga na temat en-passant: Jest to również ruch wrażliwy na turę. Przeczytaj zasady, aby uzyskać więcej informacji. http://en.wikipedia.org/wiki/Chess#En_passant

Określ wejście i wyjście według potrzeb. Najważniejsze rekwizyty dla każdego, kto może go najbardziej skompresować!

Twój wynik jest określany w najgorszym przypadku - maksymalny możliwy rozmiar w bitach. Upewnij się, że pokazałeś, jak obliczyłeś ten numer i co rozliczałeś. Strzelaj do najmniejszego najgorszego przypadku!

Min: 12 bitów
Max:
Śr .:

Wczoraj pomyślałem i pomyślałem, że mogę go jeszcze zmniejszyć.

x   Colour to play next (0 -> Black, 1-> White)
1   Only King left?

00000 Position of White King (0 -> A1 ... 63 -> H8)
00000 Position of Black King

01 00000 11111  WK:A1, BK:H2 (Black to play)
11 00000 11111  WK:A1, BK:H2 (White to play)

Rezultat to imponujący rozmiar 12 bitów !

A co z innym rodzajem K +1?

x
 0
   0
     000  +Pawn
     001  +Rook   
     010  +Knight
     011  +Bishop
     100  +Queen

Istnieje 2 możliwe ustawienie sub-drzewa.

   /\      /\
  +  K    K  +

Oba dają te same rozmiary bitów dla wszystkich sztuk. Więc nie ma znaczenia, z którego korzystamy, wybiorę pierwszy.

x
 0
  0
   000
      1011001110000000000000000000000000000000000000000000000000000000000000
(+ 000) En-Passant (if >= 2 pawn & pawn in en-passant positions)
(+ 00 ) Castlings  (if >= 1 rook)
Min: 75 bit
Max: 109 bits

Tak więc na Królu +2 inne typy elementów

x
 0
  1
   PRBNQ
   00011  +N +Q
   00101  +B +Q
   00110  +B +N
   01001  +R +Q
   01010  +R +N
   01100  +R +B
   10001  +P +Q
   10010  +P +N
   10100  +P +B
   11000  +P +R

Istnieje 5 możliwych drzewek podrzędnych (użyję 1 i 2, aby wskazać, który z elementów).

   /\          /\       /\         /\          /\
  /  \        /  \     /  \       /  \        /  \
 K   /\      /\   2   /\   \     1   /\      /\   \
    1  2    K  1     K  2   1       K  2    1  2   K

Będziemy więc potrzebować 3 bitów do zakodowania, którego sub-drzewa użyć.

x
 0
  1
   PRBNQ
         000  Sub Tree used

Min:= 11 = Header 
       6 = 2 * 3
       4 = 1 * 4
       4 = 1 * 4
      60 = 60    Empty
      --
      85 bits

Max:=  11 = Header
        4 =  2 * 4 Kings
       48 = 16 * 3 Pawns
       12 =  4 * 3 Rook
       42 = 42 * 1 Empty
        3 =  1 * 3 En-Passant
        2 =  1 * 2 Castlings
      ---
      122 bits

Nadal analizuję więcej sztuk

+3 Inne

x
 0
  1
   PRBNQ
         0000  Sub Tree used (of 14 possible)

+4 Inne

x
 0
  1
   PRBNQ
         000000  Sub Tree used (of 42 possible)

+5 Inne

x
 0
  1
   PRBNQ
         0000000  Sub Tree used (of 132 possible)
 (+000)
 (+00)

Maks .: 208?

Czy można zakodować wszystkie te podgrzewa w 9 bitach?

Jeśli zsumujemy wszystkie możliwe podgrzewa, otrzymamy 392 możliwe podgrzewa.

 1  0
 2  2
 3  5
 4  14
 5  42
 6  132
    ---
    392  <= 2^9

Korzystanie z identyfikatora Freq

Ponieważ istnieje 164603 unikatowych częstotliwości sztuk .

Log2( 164603) = 17.3286110452
             ~ 18 bits

0
 0000 0000 0000 0000 00  Freq ID

(+000) (+00) Castling

Maks .: = 204 bity

rev 3

Min: 82 Maks .: 199 Średnio: 160

W końcu przeprowadziłem analizę, aby znaleźć maksymalny rozmiar bitu. Z optymalnym kodowaniem huffmana dla każdej unikalnej częstotliwości utworu .

               0   Player
              00  Castling
               0  En-Passant Possible
            ?000  En-Passant column (include if En-Passant Possible = 1
  0000 0000 0000  Tree Encoding ID
[Board Encoding]  Between 66 .. 180 bits 

Zauważ, że jest to najgorszy możliwy rozmiar, który bit En-Passant bity, jeśli liczba pionów jest większa niż jeden. Niezależnie od kolorów i położenia pionków istnieje prawdopodobieństwo, że niektóre deski będą o 3 bity mniejsze.

Są też tylko 144 różne rozmiary (najgorszy przypadek) dla rozmiaru planszy.

_{75 - 216 bitów (v2) v1 Minimalny rozmiar to 98 bitów (12,25 bajtów), tylko dwóch królów na planszy.}

Maksymalny rozmiar to tylko 216 bitów (27 bajtów). Jest mało prawdopodobne: -

  9 x Queens
  1 x King
  2 x Rooks
  2 x Knights
  2 x Bishops
on each side.

Średnio rozmiar będzie wynosił około 157 bitów (19,625 bajtów).

Kawałki

Do zakodowania płytki używam schematu kodowania drzewa binarnego. Pusty kwadrat jest najczęściej wybierany z dowolnego miejsca od 32 do 62 występów. Dalej są pionki, następnie gawrony, rycerze, biskupi, a najrzadziej królowa i król.

0 - left node
1 - righ node

     /\
    e  \    e:= Empty Square
      B/\W  B:= Black ; W:= White
      /  \
     /    \
    /      \
   /\      /\
  p  \    p  \  p:= Pawn
     /\      /\
    /  \    /  \
   /\  /\  /\  /\
  r  b n \ r b n \  r:= Rook; b:= Bishop; n:= Knight
         /\      /\ 
        q  k    q  k  q:= Queen ; k:= King

Płytka początkowa może być zakodowana w zaledwie 166 bitach (20,75 bajtów)

  A     B     C      D      E     F     G     H
-----+-----+-----+------+------+-----+-----+------+
10100 10101 10110 101110 101111 10110 10101 10100 | 8 
  100   100   100    100    100   100   100   100 | 7
    0     0     0      0      0     0     0     0 | 6
    0     0     0      0      0     0     0     0 | 5
    0     0     0      0      0     0     0     0 | 4
    0     0     0      0      0     0     0     0 | 3
  110   110   110    110    110   110   110   110 | 2
11100 11101 11110 111110 111111 11110 11101 11100 | 1

Aby wskazać, kto się porusza, zajmuje to tylko jeden bit

0-> Black , 1-> White

Castling można zakodować w 4 bitach.

 B  W
LR LR
00 00

Więc użyłem 171 bitów (21,375 bajtów)

En-Passe można zakodować w 16 bitach (2 bajty)

W sumie to 187 bitów (23,375 bajtów).

Układ

  bits    Encodes
 0 -  15  En-Passe
16 -  19  Castling
      20  Move 
21 -  23  Unused
24 -> ..  Board

Nie napisałem jeszcze żadnego kodu.

Zauważ, że 3 z nieużywanych bitów. Więc maks. To 213 bity .

Możliwe ulepszenia

1) Zmniejszono blok nagłówka z 24 do 8 bitów (z sugestią @Peter Taylor)

0 - 2 En-Passant
    3 Move
4 - 7 Castling
8 ... Board Pieces 

2) Nagłówek o zmiennej długości

Mały 4-bitowy stały nagłówek

0 0 0 0
| | | |
| | | +-> En-Passant Block Present?
| | | 
| | +---> Pawns on board?
| |
| +-----> Castling still possible?
|                
+-------> Who's move? 0-Black 
                      1-White

Następny blok dodatkowych bitów (jeśli castling jest nadal możliwy)

00 00
|| ||
|| |+-> White Castle Right
|| +--> White Castle Left
||
|+----> Black Castle Right
+-----> Black Castle Left

Następny blok dodatkowych bitów (jeśli obecne są pionki)

000--> En-Passant column Position

Więc teraz mam nagłówek o zmiennej długości 4 - 11 bitów

3) Użyj innego schematu kodowania w zależności od tego, jakie elementy zostaną na planszy.

Zmieniając kodowanie drzewa w zależności od tego, jakie elementy znajdują się na planszy i od częstotliwości.

Jedno możliwe kodowanie dla stanu gry końcowej (bez pionków)

        /\            
       e /\           
  Black /  \ White
       /    \
      /      \
     /        \       
    /\        /\
   /  \      /  \     
  /   /\    /   /\
 /\  / /\  /\  / /\   
r b n q k  r b n q k

Co stanowi około ~ 4 bitów na sztukę.

Jakie rodzaje elementów są obecne na planszy?

RBNQK Permutation
11111 (11111)

Permutacja to zmienna długość 0-5 bitów. Jeśli pozostanie tylko jeden rodzaj elementu, nie uwzględniaj go.

Jakiej permutacji tych kawałków użyć do drzewa? Jest to silnia liczby sztuk w powyższym przykładzie jest to 5 sztuk, więc 120 możliwych kombinacji, które można zakodować.

 #    !  bit 
 6  720  10  (If pawn included)
 5  120   6
 4   24   5
 3    6   3
 2    2   1  Don't include as of equal size.
 1    1   0  Don't include as its not needed.

Pamiętaj, że są bity dodatkowe dla pustych kwadratów i kolorów.

Przykłady

Podajmy przykład, że pozostało tylko QK

RBNKQ
00011

  /\
 s  \
    /\
  B/  \W
  /\  /\
q  k q  k

101 100  0 x 60 110 111 ==> 60 + (2 x 6) = 60 + 12 = 72 bits for the board

0000 00011 Header ==> 9 bits

Łącznie 81 bitów

Podajmy i zostawmy przykład tylko królów

 RBNQK
 00001 

  /\
 s  k
   / \
  B   W

 10 0 0 0 0 0 0 0   K... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 0   .... ....
  0 0 0 0 0 0 0 11  .... ...k

Złóż wszystko razem

 header  4   0 0 0 0
 pieces  5   0 0 0 0 1
 perm    0   - - - - - -
  board 66   10 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 0
              0 0 0 0 0 0 0 11

Obliczam więc najmniejsze kodowanie dla karty przy 75 bitach (9 bitów 3 bity)

Jeszcze nie obliczono, w jaki sposób ten schemat kodowania wpływa na maksymalny rozmiar.

Ulepszenie 4

Zmniejsz liczbę bitów do roszowania do zaledwie 2 bitów. Po prostu castling dla gracza, który jest teraz.

 0 Castling possible (from header block)
 LR 
 00

Myśląc o tym, może lepiej po prostu dołączyć 2 bity do bloku nagłówka.

192 bity (najgorszy przypadek)

Oto bardzo prosty schemat przechowywania, który powinien poradzić sobie z dowolnymi promocjami pionków i nigdy nie wymaga więcej niż 64 + 4 × 32 = 192 bitów:

• Pierwsze 64 bity przechowują bitboard, który informuje, gdzie są elementy (ale nie to , co są). Oznacza to, że przechowujemy jeden bit na każdy kwadrat szachownicy (zaczynając od kwadratu a1, następnie b1, c1 itd. Aż do kwadratu h8) tak, że wolny kwadrat jest reprezentowany przez 0, a zajmowany kwadrat przez 1.

• Następnie, dla każdego kwadratu oznaczonego jako zajęty na płycie, przechowujemy 4-bitowy skrobak kodujący kawałek na tym kwadracie. Pierwszy z czterech bitów koduje kolor elementu (0 = biały, 1 = czarny), podczas gdy pozostałe trzy bity kodują rodzaj elementu:

  +-----+-----+-----+-----+
  |Black|   Piece Type    |
  +-----+-----+-----+-----+
     4     3     2     1    Bits
  

  Rodzaj kawałka

  0 = (normalny) pionek
  1 = (normalny) wieża
  2 = rycerz
  3 = biskup
  4 = królowa
  5 = król (gracz, który wykona następny ruch)
  6 = król (inny gracz)

  Zwróć uwagę na dwa kodowania króla, używane do określenia, którą turę gracza ma wykonać ruch. (W rzeczywistości, ponieważ na planszy są zawsze dwaj królowie, co pozwala na cztery kombinacje kodów 5 i 6, moglibyśmy raczej łatwo zakodować tutaj drugi fragment informacji.)

  Black Type Description
  +----+----+--------------------------------+
  |  0 | 5  | White King; White to move next |
  +----+----+--------------------------------+
  |  0 | 6  | White King                     |
  +----+----+--------------------------------+
  |  1 | 5  | Black King; Black to move next |
  +----+----+--------------------------------+
  |  1 | 6  | Black King                     |
  +----+----+--------------------------------+
  

  Aby zakodować dodatkowe informacje potrzebne do reguł en passant i castling, wprowadzamy jeden dodatkowy typ elementu, który oznacza pion lub wieżę w zależności od wiersza, w którym się pojawia:

  7 (w rzędach 1 i 8) = wieża, która nigdy się nie poruszyła, a której król także nigdy się nie poruszył, a zatem kwalifikuje się do roszowania
  7 (w rzędach 4 i 5) = pionek, który właśnie awansował o dwa pola, oraz może zatem zostać schwytany en passant

Kładąc wszystko razem:

     Hex Description
    +---+---------------------------------------------+
    | 0 | White Pawn (normal)                         |
    | 1 | White Rook (has moved)                      |
    | 2 | White Knight                                |
    | 3 | White Bishop                                |
    | 4 | White Queen                                 |
    | 5 | White King; White to move next              |
    | 6 | White King                                  |
    | 7 | White Rook (pre castle) / Pawn (en Passant) |
    | 8 | Black Pawn (normal)                         |
    | 9 | Black Rook (has moved)                      |
    | A | Black Knight                                |
    | B | Black Bishop                                |
    | C | Black Queen                                 |
    | D | Black King; Black to move next              |
    | E | Black King                                  |
    | F | Black Rook (pre castle) / Pawn (en Passant) |
    +---+---------------------------------------------+

Całkowita liczba bitów wymagana do zakodowania stanu płytki wynosi zatem 64 + 4 × # elementów na płycie. Ponieważ na planszy nigdy nie może być więcej niż 32 elementy, maksymalna długość tego kodowania wynosi 192 bity.

Na przykład, przy użyciu kodowania opisanego powyżej, początkowy stan płyty zostałby zakodowany jako (wstawiono białe znaki dla czytelności):

1111 1111 1111 1111 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
0111 0010 0011 0100 0101 0011 0010 0111 0000 0000 0000 0000 0000 0000 0000 0000
1000 1000 1000 1000 1000 1000 1000 1000 1111 1010 1011 1100 1110 1011 1010 1111

lub w systemie szesnastkowym:

FFFF 0000 0000 FFFF 7234 5327 0000 0000 8888 8888 FABC EBAF

Najgorszy przypadek 160 bitów

Po opublikowaniu mojej poprzedniej odpowiedzi 22 bajtów, zacząłem się zastanawiać, czy uda nam się zejść do 21 bajtów. Jednak gdy zobaczyłem niesamowite bajty Petera Taylora, 166 bajtów, pomyślałem: „Trzymaj się, wygląda na to, że możliwe jest pięć 32-bitowych słów!”

Po długich przemyśleniach wymyśliłem: 159.91936391 bajtów (dość ciasne dopasowanie!) Ten poziom kompresji wymagałby dość skomplikowanego programu, ale zastanawiałem się, jak uruchomić go w rozsądnym czasie.

To będzie długi post, więc proszę o wyrozumiałość, opublikuję dziś, co mogę, i wkrótce dodam kilka fragmentów kodu.

Oto, jak to zrobić:

En Passant i castling kodowane przez nielegalne pozycje (0 bitów)

Mimochodem

Jak wspomniano w innych odpowiedziach, istnieje maksymalnie 5 możliwych pól, na których może stać pionek wrażliwy na en passant. Są to kwadraty obok pionków gracza, którego jest tura.

Aby to zakodować, pion podatny na en passant jest wymieniany z tym, co znajduje się na jednym z pól w pierwszym lub ostatnim rzędzie. Może to być mężczyzna lub pusty kwadrat. Stwarza to nielegalną pozycję, ponieważ pionki nie mogą znajdować się w tych rzędach. Dekoder musi przywrócić pion do prawidłowej pozycji, wyodrębniając informację en passant.

Aby nie zakłócało to kodowania castlingu, ważne jest, aby kwadraty, na których stoją królowie na początku gry, nie były zakłócane, oraz aby procedura kodowania en passant nie umieszczała królów obok siebie, co byłoby nielegalną pozycją króla. Aby zaspokoić drugi z tych punktów, enkoder ma dwie możliwości wyboru, który kwadrat wymienia en-pasywnego pionka. Kwadrat pierwszego wyboru dla każdego z maksymalnie 5 pionków to A8, B8, C8, G8, H8. Drugi wybór: A1, B1, C1, G1, H1.

Castling

Król, który ma pozwolenie na zamek, jest z definicji nadal na swoim początkowym polu. Z białym królem na jego początkowym polu, w sumie 63 pola, na których może stać czarny król, z których 58 jest legalnych (nie wolno mu poruszać się tuż obok białego króla, ponieważ wystawiłby się na próbę). Jeśli biały król ma pozwolenie na zamek, może albo zamek ze swoją lewą wieżą, prawą wieżą lub obiema. Istnieją zatem 3x58 = 174 możliwości, w których biały król może zamek, kolejne 174, w których czarny król może zamek, i kolejne 3x3 = 9, gdzie oba mogą zamek, w sumie 357.

Istnieją 420 nielegalne układy dwóch królów, którzy znajdują się na sąsiednich polach: 3x4 = 12, gdy biały król jest w rogu, 5x24 = 120, gdy jest na krawędzi, i 8x36 = 288, gdy znajduje się na innym polu. Dlatego istnieje wystarczająco dużo nielegalnych pozycji, aby zakodować wszystkie możliwe możliwości roszenia.

Jeśli co najmniej jeden król ma prawo do zamku, koder wyszukuje dane roszady i dane o położeniu tych królów, którym nie wolno zamykać się w tabeli (lub alternatywnie, użyj algorytmu, którego tutaj nie wymienię) i wygeneruje nielegalne pozycja dwóch królów. Następnie zamieniłby królów na cokolwiek, co zdarzyło się na tych polach.

Ważne jest, aby było to kodowane i dekodowane przed en passantem, w przeciwnym razie istnieją pewne potencjalne zakłócenia.

Porównanie

Do tej pory nie użyłem żadnych bitów! Patrząc na odpowiedź Piotra, wciąż mam do zakodowania:

Whose turn is it?                                   1.000 bits
Which squares are occupied by men of which colour? 91.552 bits 
Subtotal                                          *92.552 bits* 
For the two colours, which men and which order?   *68.613 bits* 
GRAND TOTAL                                       161.165 bits

Dotyczy to najgorszego przypadku 29 mężczyzn (patrz odpowiedź Piotra). Poniżej pokażę, jak nieznacznie poprawiam (przynajmniej w przypadku 29 mężczyzn) oba punkty oznaczone **.

Które pola są zajęte / czyja to kolej?

Prostym sposobem na zakodowanie zajętych kwadratów jest 64-bitowa siatka. To także mówi nam, ile kwadratów jest zajętych. Jest to jednak trochę marnotrawstwo, ponieważ nie jest możliwe zajęcie więcej niż 32 pól. Moim rozwiązaniem jest użycie 1 do zakodowania zajętych kwadratów, kiedy jest tura białych, a 0 do zakodowania zajętych kwadratów, kiedy jest tura czarnych. Teraz wszystkie kombinacje są używane i nie ma odpadów.

W ten sposób oszczędzamy trochę na przechowywanie tury: mniej niż 32 1, to kolej na białych, więcej niż 32 1, to kolej na czarnych. Jedynym dwuznacznym przypadkiem jest sytuacja, gdy wszyscy mężczyźni są na planszy, a są 32 1 i 32 0. Dlatego potrzebny jest dodatkowy bit tylko w tym przypadku. Ponieważ nie może być żadnych promocji, dopóki nie nastąpi schwytanie, ten dodatkowy bit nie wpływa na najgorszy ogólny przypadek (który występuje przy schwytaniu 3 mężczyzn i pozostaniu 29).

Kolor mężczyzn zajmujących kwadraty

Wiemy z powyższego, ilu jest mężczyzn. Poniższy wyciąg z trójkąta Pascala mówi, ile jest możliwości dla różnych rozkładów czerni i bieli. Na przykład dla 3 mężczyzn dostępne są następujące opcje: 3 czarnych mężczyzn (1 permutacja) 2 czarnych, 1 białych, (3 permutacje), 1 czarnych, 2 białych (3 permutacje), 3 białych (1 permutacja). Łącznie 2 ³ = 8. Ogólnie rzecz biorąc, dla niższej liczby mężczyzn istnieją 2 ⁿ możliwości. Jednak wszystkie czarne i wszystkie białe możliwości są nielegalne (przynajmniej król z każdej strony musi znajdować się na planszy), więc faktyczna liczba legalnych permutacji wynosi 2 ⁿ -2 (zignoruj ​​jedynki w trójkącie Pascals.)

W przypadku więcej niż 16 mężczyzn, istnieje dodatkowe ograniczenie polegające na tym, że na planszy nie może być więcej niż 16 mężczyzn każdego koloru. Dlatego gdy na planszy są wszyscy 32 mężczyźni, musi ich być 16, a łączna liczba możliwości to 601080390, czyli nieco mniej niż 2 ³² .

1   1    1    1      1     1      1       1       1        1        1         1         1         1          1          1          1 
1   2    3    4     5      6      7       8       9       10       11        12        13        14         15         16         17
1   3    6   10    15     21     28      36      45       55       66        78        91       105        120        136        153
1   4   10   20    35     56     84     120     165      220      286       364       455       560        680        816        969
1   5   15   35    70    126    210     330     495      715     1001      1365      1820      2380       3060       3876       4845
1   6   21   56   126    252    462     792    1287     2002     3003      4368      6188      8568      11628      15504      20349
1   7   28   84   210    462    924    1716    3003     5005     8008     12376     18564     27132      38760      54264      74613
1   8   36  120   330    792   1716    3432    6435    11440    19448     31824     50388     77520     116280     170544     245157
1   9   45  165   495   1287   3003    6435   12870    24310    43758     75582    125970    203490     319770     490314     735471
1  10   55  220   715   2002   5005   11440   24310    48620    92378    167960    293930    497420     817190    1307504    2042975
1  11   66  286  1001   3003   8008   19448   43758    92378   184756    352716    646646   1144066    1961256    3268760    5311735
1  12   78  364  1365   4368  12376   31824   75582   167960   352716    705432   1352078   2496144    4457400    7726160   13037895
1  13   91  455  1820   6188  18564   50388  125970   293930   646646   1352078   2704156   5200300    9657700   17383860   30421755
1  14  105  560  2380   8568  27132   77520  203490   497420  1144066   2496144   5200300  10400600   20058300   37442160   67863915
1  15  120  680  3060  11628  38760  116280  319770   817190  1961256   4457400   9657700  20058300   40116600   77558760  145422675
1  16  136  816  3876  15504  54264  170544  490314  1307504  3268760   7726160  17383860  37442160   77558760  155117520  300540195
1  17  153  969  4845  20349  74613  245157  735471  2042975  5311735  13037895  30421755  67863915  145422675  300540195  601080390

Liczbę możliwości można znaleźć, sumując „rzędy” tego wyciągu z trójkąta paskali (przez co mam na myśli przekątne NE-SW tabeli, ponieważ obróciłem trójkąt o 45 stopni w kierunku przeciwnym do ruchu wskazówek zegara dla wygodnej prezentacji. Liczba potrzebnych bitów w celu zakreślenia tury zajmowane kwadraty i kolory mężczyzn są zatem następujące:

Do 25 mężczyzn: nieco mniej niż 64+ (liczba mężczyzn)
Dla więcej niż 25 mężczyzn:

men permutations  bits required  occupied sq+turn   
    of colours                   (bits required)  total bits
26   55791790     25.7335495      64              89.7335495
27  100960110     26.58921015     64              90.58921015
28  175844430     27.3897244      64              91.3897244
29  290845350     28.115677       64              92.115677   
30  445962870     28.73234836     64              92.73234836
31  601080390     29.16298271     64              93.16298271
32  601080390     29.16298271     65              94.16298271

Dla dwóch kolorów, którzy mężczyźni i w jakiej kolejności?

Zgodnie z poprzednimi odpowiedziami, pionki nie mogą być promowane, dopóki nie nastąpi przejęcie, ponieważ każdy pionek jest blokowany przez pion o przeciwnym kolorze na tej samej kolumnie. Odpowiedź Piotra uznała (za górną granicę), że każde zdobycie może doprowadzić do jednej promocji dla strony, która ma zostać schwytana, i dwóch dla strony, którą należy schwytać. Możemy jednak podzielić to na kilka przypadków:

1. Czarny pionek przechwytuje biały pionek: Teraz pionek przechwytujący może się swobodnie promować, ponieważ znajduje się teraz w innej kolumnie. Jego kolega z tej samej kolumny może również promować. Czarny pionek w oryginalnej kolumnie białego pionka może również promować. To jedyny przypadek, który pozwala na 3 promocje.

2. Czarny pionek mija biały pionek na sąsiedniej kolumnie, a następnie chwyta za siebie biały kawałek (inny niż pion). Umożliwia to awansowanie pionka przechwytującego i białego pionka, który był w oryginalnej kolumnie. Jedna promocja dla każdej strony.

3. Biały pion jest chwytany za sztukę (inną niż pion). Zwykle pozwala to na jedną promocję tylko dla czarnych. Jedynym wyjątkiem jest sytuacja, w której uwalnia zablokowane pionki, które zostały już spowodowane kilkoma przechwyceniami przenoszącymi pionki do tej samej kolumny.

Tak więc, jako podstawowy przypadek, możemy wziąć pod uwagę, że każde zdobycie pozwala na jedną promocję dla obu stron. W przypadku, gdy schwytany mężczyzna jest pionkiem, strona przechwytująca może uzyskać dodatkową promocję.

Napisałem program podobny do Petera. Jest nieco ostrzejszy, ale ma ważny dodatek: może obliczyć liczbę permutacji możliwych, gdy gracz zaczyna z mniejszą niż normalną 8 pionkami. Oto niektóre dane generowane przez program:

Max promotions   0            1            2             3             4              5 
8 PAWNS 
13 men    18725850    146911050    567991710    1373480394    2297173164     2902775304
14 men    36756720    339459120   1555313760    4501448952    9021804792    13325103792
15 men    60810750    660810150   3555401850   12144582450   28834205400    50030580600
16 men    64864800    843242400   5383778400   21810428640   61514893440    1.26476E+11
7 PAWNS                         
13 men    17760600    141003720    546949260    1321302840    2200401060     2761730400
14 men    30270240    287567280   1331890560    3852728880    7641553920    11068817760
15 men    32432400    372972600   2075673600    7209001800   17135118000    29315286000
6PAWNS                          
13 men    14054040    114594480    447026580    1069488420    1739577840     2113185360
14 men    15135120    151351200    718918200    2087805720    4073028960     5697051360                         
5 PAWNS                         
13 men     6486480     55135080    217297080     510630120     794233440      910235040

Widzimy, że w przypadku takim jak 8 pionków, 15 mężczyzn, 0 promocji liczba permutacji jest tylko nieco mniejsza niż dla 8 pionków 16 mężczyzn, 0 promocji. Jeśli jednak weźmiemy pod uwagę przypadek taki jak 7 pionków, 15 mężczyzn, 0 awansów (co jest takie samo, jak biorąc pod uwagę, że schwytany człowiek był zdecydowanie pionkiem), otrzymujemy około połowy liczby permutacji.

Tak więc w przypadku, gdy czarne mają 16 mężczyzn, a białe 15 mężczyzn, możemy rozważyć górną granicę 2 promocji dla czarnych i jednej promocji dla białych:

5383778400 x 660810150 = 3.55766E+18 possibilities

Możemy jednak zrobić lepiej, postępując w następujący sposób.

A. Rozważ jedną promocję dla Czarnych i Białych, zakładając, że mężczyzna, którego stracił Biały, może być dowolnego rodzaju:

843242400 x 660810150 = 5.57223E+17 possibilities

B. Rozważ dodatkowe możliwości dla Czarnych, jeśli ma dwie promocje, pomnożone przez te same możliwości dla Białych, w których stracił pionka.

(5383778400-843242400) x 372972600 = 1.6935 E+18 possibilities.

Dodając te dwa razem, otrzymujemy 2.25072E + 18, czyli mniej niż 3,55766E + 18. Wszystkie możliwości maksymalnie 3 zdjęć (pozostałych 29 mężczyzn) są wymienione poniżej.

(Promotions, Pawns lost) possibilities

BLACK 16 MEN, WHITE 15 MEN. ESTIMATE   3.55766E+18 = 2^61.62563249
(1,0)   843242400 x (1,0)  660810150 = 5.57223E+17
(2,0)  4540536000 x (1,1)  372972600 = 1.6935 E+18
                               TOTAL   2.25072E+18 = 2^60.96509144


BLACK 16 MEN, WHITE 14 MEN. ESTIMATE   9.5675 E+19 = 2^66.3747752
(2,0)  5383778400 x (2,0) 1555313760 = 8.37346E+18
(3,0) 16426650240 x (2,1) 1331890560 = 2.18785E+19
(4,0) 39704464800 x (2,2)  718918200 = 2.85443E+19
                               TOTAL   5.87962E+19 = 2^65.67235739


BLACK 16 MEN, WHITE 13 MEN. ESTIMATE   2.69447E+20 = 2^67.86856193
(3,0) 21810428640 x (3,0) 1373480394 = 2.99562E+19
(4,0) 39704464800 x (3,1) 1321302840 = 5.24616E+19
(5,0) 64960896000 x (3,2) 1069488420 = 6.94749E+19
(6,0) 69702272640 x (3,3)  510630120 = 3.55921E+19
                               TOTAL   1.87485E+20 = 2^67.34533572


BLACK 15 MEN, WHITE 15 MEN. ESTIMATE   1.47491E+20 = 2^66.99918768
(2,0)  3555401850 x (2,0) 3555401850 = 1.26409E+19
(2,1)  2075673600 x (3,0) 8589180600 = 1.78283E+19
(3,0)  8589180600 x (2,1) 2075673600 = 1.78283E+19
(3,1)  5133328200 x (3,1) 5133328200 = 2.63511E+19
                  TOTAL BOTH COLUMNS   7.46486E+19 = 2^66.01674923


BLACK 15 MEN, WHITE 14 MEN. ESTIMATE   4.51366E+20 = 2^68.61286007      
(3,0) 12144582450 x (3,0) 4501448952 = 5.46682E+19
(3,1)  7209001800 x (4,0) 4520355840 = 3.25873E+19
(4,0) 16689622950 x (3,1) 3852728880 = 6.43006E+19
(4,1)  9926116200 x (4,1) 3788825040 = 3.76083E+19
(5,0) 21196375200 x (3,2) 2087805720 = 4.42539E+19
(5,1) 12180168000 x (4,2) 1985223240 = 2.41804E+19
                  TOTAL BOTH COLUMNS   2.57599E+20 = 2^67.80368692

Zatem w najgorszym przypadku jednej strony z 15 mężczyznami i drugiej z 14 mężczyznami potrzebujemy 67,804 bitów.

Dodając to do 92.116 bitów wymaganych do określenia, które kwadraty i jaki kolor, otrzymujemy w sumie 67,804 + 92,166 = 159,92 bitów.

Najgorszy przypadek 177 bitów

Ten algorytm, choć nie jest prosty, daje 177-bitowy najgorszy przypadek (184b = 23B w praktyce), 13b (16b = 2B) najlepszy scenariusz, gdy pozostały tylko 2 króle.

Bit     Description
  1     Turn (0=white 1=black)
  2-  7 White king position (2-4=letter, 5-7=number)
  8- 13 Black king position (8-10=letter, 11-13=number)
 14- 75 Which squares contain pieces (skipping the 2 king squares, so only 62)
        Ordered a1-h1,a2-h2,(...)
 76-105 Which color owns the square with their piece (0=white, 1=black)
        If there's LESS than 30 pieces (apart from kings), this area is
        smaller
106-end Square data

Square data has the following system:
Every square gets assigned a number which determines piece. Number is:
0 Queen
1 Rook
2 Bishop
3 Knight
4 Pawn OR allowed-castle rook depending on square
5 Pawn subject to potential enpassant

The first bits (max 13) is the potential enpassant slots from A-H, determined
from data of 1 + 14-105 for which of the squares has a piece, and which color
owns the piece and whose turn it is. For example, if turn is White (bit 1 is
0), all pieces on row 5 which is Black owned (determined from 14-105 metadata)
and has at least 1 adjacant (on the same row) square owned by White, is
explained in A-H order. A base 6 number is used which is converted to binary
for the storage. On reading, it's converted and read A-H according to the
numbers above (4 is obviously pawn in this case).
The second amount of bits takes care of the 1st and 8th row (not corners!)
in b1-g1,b8-g8. These only take up 2 bits since 4 or 5 is never needed
(pawn on 1st or 8th is invalid).
The third amount of bits takes care of the rest of the board, in the following
order: a1,h1,a2-h2,a3-h3,a4-h4,a5-h5,a6-h6,a7-h7,a8,h8 (skipping the
"enpassant" slots), in base 5 (since piece ID 0-4 are the only used) converted
to binary.

Best case: 13 bits (bit 1 for turn, bit 2-12 for kings)
Worst case: 177 bits
* 32 pieces with kings
* 5 viable enpassant pawns
* No pieces at 1st or 8th row (except if kings+rooks are at initial posions
whether or not they can castle)
In this case, the space as following:
  1   bit   turn
+ 12  bits  king positions
+ 62  bits  which squares have pieces
+ 30  bits  color of pieces
+ 13  bits  enpassant area
+ 0   bits  initial rows area
+ 59  bits  the rest of the area
= 177 bits  total

Potential optimizations but not really worth it IMO:
* Decrease average by make corners 2 bits as well if kings aren't at e1/e8
* Alter reading order to read b1-g1,b8-g8 last - decreases worst case to
  176 bits if the "which squares have pieces" area is cut off if 30 existing
  pieces has been defined already. Would actually save 8 bits on file but meh

166 bitów

• 1 bit: czyja to kolej?
• 2bitów: które opcje roszowania są otwarte? (Uwaga: po dokładnym przeczytaniu pytania konieczne jest zapisanie opcji roszowania tylko dla gracza, którego jest tura).
• lg 6 ~= 2.585bitów: które opcje en passant są otwarte? (Zobacz moją inną odpowiedź)
• lg sum_{i=1}^{16} sum_{j=1}^{16} 64! / (i! j! (64-i-j)! = lg 3629590441720924477681996172 ~= 91.552 bitów: które kwadraty są zajęte przez mężczyzn w jakim kolorze?
• W najgorszych lg 451366131803622235200 ~= 68.613przypadkach wskazać, którzy ludzie i w jakiej kolejności (patrz poniżej)

Używając kodowania arytmetycznego (ponieważ na każdym kroku stosujemy jednolity rozkład) możemy osiągnąć ceil(3 + 2.585 + 91.552 + 68.613) = 166bity.

Kodowanie dla mężczyzn: biorąc pod uwagę, że wiemy, ilu jest mężczyzn danego koloru, możemy łatwo wyliczyć wszystkie możliwe rozkłady / multisety mężczyzn (np. Z 5 mężczyznami możemy mieć jednego Króla, jedną Królową, dwie Wieże i Pion), a następnie możemy rozważyć wszystkie możliwe permutacje każdej dystrybucji.

Możemy jednak zrobić jeszcze lepiej, biorąc pod uwagę współzależności. Robię to tylko na bardzo podstawowym poziomie: ile możliwych promocji? Pionek może zostać „przekazany” i może awansować na trzy sposoby: przechwytuje i w ten sposób przesuwa się do innej kolumny; lub jego przeciwny pionek chwyta i tym samym przechodzi do innej kolumny; lub jego pionek przeciwnika zostanie schwytany. W ten sposób zdobycie bieli potencjalnie tworzy dwa pionki dla białych i jeden dla czarnych.

Możemy zbudować częściową tabelę górnych granic promocji:

(Max white promos, max black promos):

           White men
           16      15      14      13
Black men
       16  (0, 0)  (1, 2)  (2, 4)  (3, 6)
       15  (2, 1)  (3, 3)  (4, 5)  (5, 7)
       14  (4, 2)  (5, 4)  (6, 6)  (7, 8)
       13  (6, 3)  (7, 5)  (8, 7)  (8, 8)

Możemy również obliczyć liczbę permutacji, biorąc pod uwagę, że gracz ma Nludzi i nie więcej niż Ppromowane pionki:

Num of permutations (cumulative):
    max promotions: 0              1              2              3              4              5              6              7              8
 1 men              1              1              1              1              1              1              1              1              1
 2 men             10             10             10             10             10             10             10             10             10
 3 men             72             75             75             75             75             75             75             75             75
 4 men            436            496            500            500            500            500            500            500            500
 5 men           2305           3025           3120           3125           3125           3125           3125           3125           3125
 6 men          10746          17106          18606          18744          18750          18750          18750          18750          18750
 7 men          44170          88795         106260         109179         109368         109375         109375         109375         109375
 8 men         159832         415360         575240         619200         624744         624992         625000         625000         625000
 9 men         509841        1721961        2884815        3398769        3504735        3515301        3515616        3515625        3515625
10 men        1447200        6258240       13063080       17697780       19260180       19510320       19530840       19531230       19531240
11 men        3706065       20021265       52183395       85007571      102173181      106786581      107369592      107409918      107410281
12 men        8678340       57101220      183088620      364510476      509818716      570620556      584017632      585352152      585430164
13 men       18725850      146911050      567991710     1373480394     2297173164     2902775304     3107861328     3143928216     3146014014
14 men       36756720      339459120     1555313760     4501448952     9021804792    13325103792    15664512864    16283899632    16360920576
15 men       60810750      660810150     3555401850    12144582450    28834205400    50030580600    66655789200    73588394880    74576231730
16 men       64864800      843242400     5383778400    21810428640    61514893440   126475789440   196178062080   240747386880   253686232800

Łącząc oba, możemy uzyskać liczbę bitów wymaganych do określenia obu permutacji, biorąc pod uwagę liczbę mężczyzn po obu stronach:

           White men
           16      15      14      13      <13
Black men
       16  51.902  61.626  66.375  67.868  <=67.009
       15  --      67.000  68.613  67.534  <=65.243
       14  --      --      67.734  65.480  <=63.055
       13  --      --      --      63.102  <=60.676

Jeśli nie ma tego w tej części tabeli, możemy po prostu założyć, że obie strony mają do 8 promocji, a my nadal mamy się lepiej niż w najgorszym przypadku, który wynosi 68,613 bitów, gdy jeden ma 14 mężczyzn, a drugi ma 15 mężczyzn.

Pamiętaj, że wciąż jest to daleka droga od doskonałej reprezentacji, ponieważ pozwala na wiele nielegalnych pozycji.

Kod do obliczania tabeli permutacji:

import java.util.*;

public class ChessCombinatorics {
    public static void main(String[] args) {
        long[] f = new long[17];
        f[0] = 1;
        for (int i = 1; i < 17; i++) f[i] = i * f[i-1];

        // Indexed by num promotions, then total num men.
        long[][] distribs = new long[9][17];
        long[][] perms = new long[9][17];

        for (int promotedPawns = 0; promotedPawns < 9; promotedPawns++) {
            Map<Integer, Map<String, Long>> numCases = new HashMap<Integer, Map<String, Long>>();
            for (int i = 1; i < 17; i++) numCases.put(i, new HashMap<String, Long>());

            for (int extraQ = 0; extraQ <= promotedPawns; extraQ++) {
                for (int extraR = 0; extraR + extraQ <= promotedPawns; extraR++) {
                    for (int extraN = 0; extraN + extraR + extraQ <= promotedPawns; extraN++) {
                        int extraB = promotedPawns - extraN - extraR - extraQ;
                        int unpromotedPawns = 8 - promotedPawns;

                        // Promoted pawns should only count towards their new type if the existing ones are alive.
                        // Otherwise we double-count some cases.
                        int minQ, maxQ, minR, maxR, minN, maxN, minB, maxB;
                        if (extraQ == 0) {minQ = 0; maxQ = 1;} else {minQ = maxQ = 1 + extraQ;}
                        if (extraR == 0) {minR = 0; maxR = 2;} else {minR = maxR = 2 + extraR;}
                        if (extraN == 0) {minN = 0; maxN = 2;} else {minN = maxN = 2 + extraN;}
                        if (extraB == 0) {minB = 0; maxB = 2;} else {minB = maxB = 2 + extraB;}

                        for (int numQ = minQ; numQ <= maxQ; numQ++) {
                            for (int numR = minR; numR <= maxR; numR++) {
                                for (int numN = minN; numN <= maxN; numN++) {
                                    for (int numB = minB; numB <= maxB; numB++) {
                                        for (int numP = 0; numP <= unpromotedPawns; numP++) {
                                            // The number of possibilities at these values is (numK + numQ + numR + numN + numB + numP)! / (numK! numQ! numR! numN! numB! numP!)
                                            numCases.get(1+numQ+numR+numN+numB+numP).put(numQ+","+numR+","+numN+","+numB+","+numP, f[1 + numQ + numR + numN + numB + numP] / f[numQ] / f[numR] / f[numN] / f[numB] / f[numP]);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            for (int numMen = 1; numMen < 17; numMen++) {
                distribs[promotedPawns][numMen] = numCases.get(numMen).size();
                if (distribs[promotedPawns][numMen] > 0) {
                    for (Long l : numCases.get(numMen).values()) perms[promotedPawns][numMen] += l;
                }
            }
        }

        System.out.println("Num of permutations (cumulative):");
        System.out.println("    max promotions: 0              1              2              3              4              5              6              7              8");
        for (int numMen = 1; numMen < 17; numMen++) {
            System.out.print(String.format("%2d men", numMen));
            long cumul = 0;
            for (int promotedPawns = 0; promotedPawns < 9; promotedPawns++) {
                cumul += perms[promotedPawns][numMen];
                System.out.print(String.format("%15d", cumul));
            }
            System.out.println();
        }

        System.out.println("Entropy of permutations:");
        System.out.println("    max promotions: 0              1              2              3              4              5              6              7              8");
        for (int numMen = 1; numMen < 17; numMen++) {
            System.out.print(String.format("%2d men", numMen));
            long cumul = 0;
            for (int promotedPawns = 0; promotedPawns < 9; promotedPawns++) {
                cumul += perms[promotedPawns][numMen];
                System.out.print(String.format("  %6.3f", Math.log(cumul) / Math.log(2)));
            }
            System.out.println();
        }

    }
}

Najgorszy przypadek to 178 bitów (174 w mgnieniu oka!)

Cześć, właśnie wracam do kodowania, czego tak naprawdę nie robiłem od czasów college'u. Widziałem tę stronę i uważałem, że wygląda interesująco. Zrobiłem małą weryfikację teoretyczną i wydaje się, że do idealnego algorytmu potrzeba co najmniej 146 bitów, prawdopodobnie jeszcze kilka innych (wyjaśnię to w komentarzach, gdy będę miał chwilę).

W każdym razie w ten sposób tworzę dane. Podstawowa koncepcja ma 178 bitów, ale z pewnymi jiggery pokery może sprowadzić do 174 (to 21 3/4 bajtów). 175 jest nieco łatwiejszy do zaprogramowania, jest bardziej czytelny dla człowieka i nadal zawiera 22 bajty.

A) Pozycja obu królów: 6 bitów dla białych i czarnych 12 BITÓW

B) Z pozostałych 62 pól, które są zajęte? Matryca 62 bitów

C) Czyja to kolej? 1 BIT

CAŁKOWICIE TAK DALEKO: 75 BITÓW

D) En Passant. Jeśli nadejdzie kolej na ruch białych, do 5 czarnych pionków może wyglądać tak, jakby można je było złapać En Passant. Czarny pionek musi znajdować się w rzędzie 5 (od dołu do góry, zaczynając od zera), a obok niego musi znajdować się biały pionek. Jedna sytuacja z maksymalną liczbą możliwych przechwyceń wygląda następująco:

BWBBWBBW

Gdyby w rzędzie 5 było 6 czarnych pionków, białe miałyby tylko 2 kwadraty i mogłyby zagrozić tylko 4 czarnym pionkom, więc nie jest możliwe, aby więcej niż 5 czarnych pionów było jednocześnie zagrożonych przez En passant. Potrzebujemy więc liczb od 1 do 5 wskazujących, który z (do 5) pionków w rzędzie 5, który ma wrogi (w tym przypadku biały) pionek obok niego, został przesunięty o 2 pola w ostatniej turze ( lub zero, jeśli nie ma pionka w tej sytuacji został przesunięty w ten sposób na ostatniej turze).

E) Co zawierają do 30 zajętych kwadratów (nie licząc królów)?

Istnieje 10 możliwości, każda reprezentowana przez liczbę dziesiętną.

Najmniej znaczący bit reprezentuje kolor.

Dlatego liczby parzyste są białe, liczby nieparzyste są czarne.

Biało-czarny

Pion 0/1 (lub wieża, która może się zamykać *)

Rycerz 2/3

Biskup 4/5

Gawron 6/7

Królowa 8/9

* Wieżę, która może się zamykać (i dlatego nigdy nie została przeniesiona z pierwszego lub ostatniego rzędu) jest reprezentowana przez 0 lub 1 zamiast 6 lub 7. Nie można jej pomylić z pionkiem, ponieważ pionków nie można znaleźć na pierwszym lub ostatni rząd.

Daje to liczbę dziesiętną do 30 cyfr, którą możemy pomnożyć przez 6, a następnie dodać kod dla En passant. Wynikowa liczba zmieści się w 103 bitach, co po dodaniu do 75 wymienionych powyżej wynosi 103 + 75 = 178 bitów . W rzeczywistości, jeśli po prostu pomnożymy przez 10 zamiast 6, nie ma to znaczenia dla liczby użytych bitów, a dekodowanie jest łatwiejsze.

To tylko 2 bity więcej niż 22 bajty. Możemy jednak sprowadzić go do 174 bitów, jak wyjaśniono poniżej.

Jeśli żaden pionek nie został schwytany, pionek nie może awansować .

Dowód jest następujący. Wyobraź sobie, że od samego początku gry obsesja na punkcie awansowania pionka w kolumnie E (na przykład). Naprzeciwko pionka, który stoi na drodze, znajduje się czarny pionek. Dlatego, aby promować tego pionka, musi się zdarzyć jedna z następujących sytuacji:

1) Czarny pionek zostaje schwytany.

2) Czarny pionek chwyta kolejny pionek i dlatego zsuwa się z drogi.

3) biały pion chwyta pionka na sąsiedniej kolumnie, takiej jak kolumna D.

4) biały pion mija (lub mija) czarnego pionka na sąsiedniej kolumnie, a następnie chwyta pionek na tej samej sąsiedniej kolumnie, powodując zmianę białego pionka.

Przypadek 4 jest najbardziej interesujący, ponieważ nie tylko biały pionek, który zaczął się w kolumnie E, ma teraz jasną ścieżkę do awansu. Czarny pionek w kolumnie, który pozostaje w kolumnie E, może również promować. Dlatego pojedyncze zdobycie może oczyścić drogę do promowania jednego pionka każdego koloru.

W każdym razie fakt, że żaden pionek nie może awansować, dopóki pion nie zostanie schwytany, oznacza, że ​​nie musimy przechowywać 30-tego elementu. Możemy to wypracować poprzez eliminację (lub odejmowanie, ponieważ pełny zestaw kodów elementów na początku gry zawsze sumuje się w tej samej wysokości = 80). Jednym drobnym punktem jest to, że musimy zadbać o to, aby kwadraty były tam, gdzie są wieże stoją na początku gry są jednymi z pierwszych skanowanych (ponieważ gdyby były ostatnie, nie wiedzielibyśmy, czy wieża może się zamoczyć, czy nie.) Można to łatwo zrobić, skanując wiersz 0, a następnie rzędy 7 do 1: Dla r = 8 do 1 wiersza skanowania [r mod 8].

Zatem macierz bitów w (B) powie nam, ile jest kawałków (z wyjątkiem królów). Jeśli jest pełnych 30, zignoruj ​​ostatni kawałek podczas kodowania, dekoder obliczy, co to było. Mamy teraz do 29 cyfr po przecinku, które mnożymy przez 6 i dodajemy do kodu En Passant. Wynikowa liczba zostanie po prostu ściśnięta do 99 bitów, co daje w sumie 99 + 75 = 174 bitów.

Jako przykład Oto rzeczywista pozycja. Biały właśnie wykonał swój pierwszy ruch (zaawansowany pionek króla) i nadeszła kolej Czarnych.

rnbqkbnr
pppppppp


    P

PPPP PPP
RNBQKBNR

A) Pozycja królów (biała / czarna ósemkowa, 12 bitów ): 03 73 = 000011 111011

B) Które kwadraty są zajęte? Zacznij od rzędu zero (dolny rząd), a następnie wszystkie inne rzędy od góry do dołu, pomijając królów:

1111 111

1111 111
11111111
00000000
00000000
00001000
00000000
11110111 

C) Tura czarnych: Bit toczenia = 1

D) En Passant. Nie ma białego pionka obok czarnego pionka, dlatego nie ma pionka, który można by zabrać pasywnie (nawet jeśli ten pionek wykonał ostatni ruch), więc D = 0. Jeśli zamiast brać pod uwagę tylko pionki, które mają obok siebie wrogiego pionka, weźmiemy pod uwagę wszystkie pionki, które nie mają obok siebie przyjaznych pionków po obu stronach, wówczas D będzie wynosić 1, ponieważ w tej sytuacji jest jeden taki pionek, a ten konkretny pionek rzeczywiście został przesunięty w ostatniej turze.

E) Ponownie, najpierw rząd dolny, potem wszystkie inne rzędy od góry do dołu, pomijając królów, i czterema nieosłoniętymi wieżami określanymi jako 0 lub 1 (liczby normalnie zarezerwowane dla pionków).

RNBQ BNR =   0248 420
rnbq bnr =   1359 531
pppppppp =   11111111
PPPPPPPP = (0)0000000

30. cyfrę (w nawiasach) można odrzucić.

Chociaż nie jest to tutaj bardzo widoczne, pionek, który posunął się biały, faktycznie znajduje się na jednym końcu listy pionków, ponieważ skanujemy wiersz po rzędzie.

Nasze dane wyglądają teraz tak: z 29 kodami zawartości kwadratów oraz kodem En Passant:

 (0 discarded) 0000000 11111111 1359531 0248420 (0 en passant)

Najlepiej skanować od prawej do lewej podczas dekodowania i od lewej do prawej (odwrotna kolejność) podczas kodowania. Oznacza to, że gdy jest mniej elementów, będziemy mieli mniejszą liczbę, zachowując maksymalną spójność (tzn. Chcemy, aby puste spacje / zera wiodły, a nie ciągnęły, aby umożliwić kompresję rzadko zajętych desek). Gdy mamy tylko 2 królów na płycie będziemy mieli 75 bitów wymienionych powyżej, plus 3 bity do przechowywania danych en passant = 78 bitów w najlepszym przypadku. Każda dodatkowa część ma nieco mniej niż 3,5 bitu (2 sztuki mogą być przechowywane w 7 bitach, ponieważ 100 <128.)

Istnieje praktyczny problem polegający na tym, że 99-bitowa liczba całkowita jest zbyt duża, aby zmieścić się w 64-bitowej zmiennej całkowitej, co oznacza, że ​​wiele języków programowania nie zapewnia jej obsługi (nie można po prostu przekonwertować reprezentacji ciągu 29-30 cyfr liczba na liczbę całkowitą.) Jako prosty sposób kodowania 22 bajtów, możemy podzielić 30-cyfrowy numer (kody 29-częściowe + kod en passant) na dwie 15-cyfrowe liczby, z których każda zmieści się w 50 bitach (łącznie 100 bitów plus 75 wspomnianych powyżej sprawia, że ​​najgorszym przypadkiem jest 175 bitów.)

Dla maksymalnej kompresji, jak wspomniano powyżej, 29 cyfr dziesiętnych plus kod En Passant (6 możliwych wartości) zmieści się prawie w 99 bitach (w sumie 174 bitów), ale bez obsługi języka dla liczb całkowitych o tym rozmiarze jest to skomplikowane w programowaniu. Wydzielenie 29 bitów kolorów może być łatwiejsze i praca z kodami typu części (5 możliwości) i kodem pasywnym (6 możliwości) oddzielnie od kolorów (70 bitów, prawie pasuje do zmiennej 64-bitowej).

Oto pełne rozwiązanie, w rzeczywistości najgorszy przypadek to 181 bitów

Koncentruje się tutaj na prostym programie, który można łatwo zrozumieć

Dane wejściowe to FEN, tutaj jest pozycja otwarcia, ma sześć pól (5 i 6 są ignorowane):

rnbqkbnr / ppppppppp / 8/8/8/8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1

Pierwsze pole (umieszczenie elementu) jest analizowane

perl -pe 's/\d/"_"x$&/ge;s/\s.*//;s|/||g'

Produkować:

rnbqkbnrpppppppp________________________________PPPPPPPPPRNBQKBNR

Pole pierwsze: zakoduj lokalizację królów (12 bitów):

printf("%b",index('k',$_))
printf("%b",index('K',$_))

Pole drugie: kodowanie sztuk (do 5 bitów na sztukę):

s/_/0/g     Blank
s/P/100/g   From here, as normal chess meaning
s/p/101/g
s/Q/11000/g
s/q/11001/g
s/R/11010/g
s/r/11011/g
s/B/11100/g
s/b/11101/g
s/N/11110/g
s/n/11111/g
s/K//
s/k//

Pole trzecie: aktywny kolor (1 bit)

s/w/0/
s/b/1/

Pole czwarte: dostępność castlingu (4 bity)

m/K/?1:0
m/k/?1:0
m/Q/?1:0
m/q/?1:0

• FIQ pokazuje, że to pole można całkowicie usunąć.

Pole piąte: en passant (zero lub 3 bity)

printf("%b",ord($1)-ord("a")) unless m/-/
// The EP's rank is 3 or 6 based on active color, only need to encode file

Najgorszy naiwny przypadek 200 bitów

• Plasowanie dwóch królów - 12 bitów
• Deska
  • QRRBBNN QQQQQQQQ - 75 bitów
  • qrrbbnn qqqqqqqq - 75 bitów
  • Puste kwadraty - 30 bitów
• Aktywny kolor - 1 bit
• Castling - 4 bity
• En Passant - 3 bity

Rzeczywisty najgorszy przypadek

Każdy gracz nie może promować wszystkich pionków bez schwytania innych pionków . Oto efekt entropii przechwytywania elementów:

• PpR(3 + 3 + 5 = 11 bitów) => Qq_(5 + 5 + 1 = 11 bitów)
• PPpp(3 + 3 + 3 + 3 = 12 bitów) => QQq_(5 + 5 + 5 + 1 = 16 bitów)

Tak więc właściwie najgorszym przypadkiem jest:

• QRRBBNN QQQQQQQQ - 75 bitów
• qrrbbnn qqqq - 55 bitów
• Puste kwadraty - 34 bity

Najgorszym przypadkiem jest wypromowanie wszystkich elementów zamiast pozostawienia pionka en enantant.

CAŁKOWITA RZECZYWISTA OBUDOWA Z POKAZANYM KODEM 12 + 75 + 55 + 34 + 1 + 4 = 181 bitów

FIQ pokazuje dwie ulepszenia tego prostego schematu, ale trudniej je kodować:

• Usuń bit 2 z kodowania części w wierszach 1 i 8, ponieważ pionki nie mogą tam iść (oszczędność do 16 bitów)
• Używaj pionków do kodowania wież castingowych (4-bitowe oszczędności)

Jedynym pozostałym kodem nie pokazanym w tej odpowiedzi (dla zwięzłości) jest: złamanie FEN wejściowego w polach ( split /\s/) i przypisanie zmiennych.

Łącznie dane wymagają 33 bajtów

(Dzięki komuś w komentarzach zdałem sobie sprawę, że to nie działa na promocję pionków. Zaktualizuje to, kiedy będę w stanie rozwiązać)

dla pierwszego bajtu używamy pięciu bitów:

• pierwszy bit: tura gracza, 1 = biały
• drugi bit: zamek czarnego króla, 1 = zamek puszki
• trzeci bit: zamek z czarną królową, 1 = zamek może
• czwarty bit: zamek białego króla, 1 = zamek puszki
• piąty bit: biały zamek królowej, 1 = zamek może

kolejne 32 bajty są używane do reprezentowania każdego kawałka szachowego, w ustalonej kolejności

• 3-bity: reprezentują wiersz
• 3-bity: reprezentują kolumnę
• 1-bit: reprezentuje en-passant, 1 = can en-passant
• 1-bit: jeśli bit „can en-passant” ma wartość 1: wskazuje, po której stronie, 0 = w lewo
  oznacza, czy został on przechwycony. 0 = nie przechwycony
  (jeśli może en-passant, to na pewno nie zostanie przechwycony)

Trochę kodu C reprezentującego ten pomysł (który tak naprawdę nie działa)

int main() {
    char b, c[32], i;

    //decode:

    FILE *p=fopen("/path/to/file.csv","r");
    fscanf(p,"%d,",&b);
    for(i=0;i<31;i++) fscanf(p,"%d,",&c[i]);
    fscanf(p,"%d",&c[31]);
    fclose(p);
    if(b&16) /* white's turn */
    else /* black's turn */
    if(b&8) /* black king side can castle */
    if(b&4) /* black queen side can castle */
    if(b&2) /* white king side can castle */
    if(b&1) /* white queen side can castle */

    for(i=0;i<32;i++) {
        int row, column;
        row=c[i]&7;
        column=c[i]&56;
        if(c[i]&64 && isPawn(c[i])) { //can en-passant
            if(c[i]&128) //can en-passant to the right
            else //can en-passant to the left
        }
        if(!(c[i]&64)) {
            if(c[i]&128) //captured
            else //not captured
        }
    }

    //encode:

    p=fopen("/path/to/file.csv","w");

    if(b&16) b&=239;
    else b|=16;
    if(black_king_side_cannot_castle) b&=247;
    if(black_queen_side_cannot_castle) b&=251;
    if(white_king_side_cannot_castle) b&=253;
    if(white_queen_side_cannot_castle) b&=254;

    for(i=0;i<32;i++) {
        c[i]=row;
        c[i]+=column*8;
        if(isPawn(c[i]) && can_en_Passant) {
            c[i]|=64;
            if(can_en_Passant_left) c[i]&=127;
            else c[i]|=128;
        }
        if(!(c[i]&64)) {
            if(isCaptured(c[i])) c[i]|=128;
            else c[i]&=127;
        }
    }
    fprintf(p,"%d,",b);
    for(i=0;i<31;i++) fprintf(p,"%d,",c[i]);
    fprintf(p,"%d",c[31]);
    fclose(p);
    return 0;
}

256 242 bitów

Oto podstawowy algorytm kompresji, który prawdopodobnie można ulepszyć, ponieważ nie wyklucza reprezentacji niektórych nielegalnych pozycji.

Tablica zaczyna się od 5 bitów informacji nagłówka w następujący sposób:

0 1 1 1 1
---------
1 2 3 4 5

1: Turn (black = 1, white = 0)
2: Black can castle queen-side
3: Black can castle king-side
4: White can castle queen-side
5: White can castle king-side

Następnie ciąg 12 bitów reprezentujących pozycje królów.

0 0 0 1 0 0 1 1 1 1 0 0
-----------------------
0 0 0 0 0 0 0 0 0 1 1 1
1 2 3 4 5 6 7 8 9 0 1 2

01 - 03: white king's rank
04 - 06: white king's file
07 - 09: white king's rank
10 - 12: white king's file

Następnie ogromna 64-cyfrowa liczba w podstawie 11, która jest następnie mnożona przez 9, aby dodać kolejną cyfrę na końcu reprezentującą stan en-passant. Każda cyfra w podstawie 11 reprezentuje kwadrat na planszy z następującymi możliwymi wartościami:

0: empty

1: white pawn
2: white knight
3: white bishop
4: white rook
5: white queen

For the black equivalent of each white piece, add 5.

A cyfry w bazie 9:

0: no en-passant possible
1 - 8: en-passant on rank 1 - 8

11 ⁶⁴ × 9 to około 2 ^224,57 , co wymaga 225 bitów do zakodowania. Plus 17 bitów nagłówka u góry, to łącznie 242 bity.

Dzięki ugoren za ulepszenia.

? bitów

(≥ 217 najgorszych przypadków, 17 najlepszych przypadków, 179 na płycie początkowej)

Opis kodowania

Dodatkowe metadane składają się z tego, której tury jest (jeden bit) i roszady (cztery bity, tj. Może biały zamek po stronie królów? Po stronie królowych? I podobnie w przypadku czerni).

Dla samej pozycji planszy kodujemy ją jako zestaw aktywnych elementów. Cóż, właściwie, wyliczamy elementy w określonej kolejności z powodów, które wyjaśnię za chwilę. Dla każdego kawałka przechowujemy jego kolor (jeden bit), jego rodzaj (trzy bity, które obejmują 6 rodzajów, plus jeden dodatkowy rodzaj dla „pionka, który można zabrać en passant”), a także jego pozycję.

Oto interesująca część: aby zakodować pozycję kawałka, zamiast przechowywać go jako współrzędną, przechowujemy jego względną odległość od ostatniego kawałka podczas wyliczania kawałków w kolejności od lewej do prawej, od góry do dołu (tj. A8 , B8, ..., G1, H1). Ponadto przechowujemy odległość jako liczbę o zmiennej długości, 1oznaczającą, że ten kawałek jest tuż obok poprzedniego, 0xxdo pominięcia 1-3 sztuk, 000xxxdo pominięcia 4-10 sztuk, 000000xxxxdla 11-25, 0000000000xxxxxdla 26-56 i wreszcie 000000000000000xxxza 57–62.

Przykłady

Zrobiłem listę niektórych pozycji zakodowanych tym kodowaniem i opatrzyłem komentarzem pozycję początkową.

Nie wiem, jak analizować najgorszy przypadek wielkości bitów, ale idąc za przykładami w skrócie, uważam, że algorytm powinien być co najmniej nieco wydajny.

Implementacja dekodera

Poniżej znajduje się szybki i brudny dekoder tego kodowania (biorąc jako dane wejściowe dane binarne zakodowane w tekście, jak w powyższym opatrzonym komentarzem przykładzie i pomijając rzeczy, które nie są „0” lub „1”). Produkuje szachownicę jednorożca na standardowe wyjście.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

char buf[1024];
int wi = 0, ri = 0;

int read_n(int n) {
  int res = 0;
  for (int i = 0; i < n; i++) {
    res = res << 1 | (buf[ri++] == '1');
  }
  return res;
}

int read_varnum() {
  int v, c = 0;

  for (int i = 1; i <= 5; i++) {
    v = read_n(i);
    if (v != 0) return c + v;
    c += (1 << i) - 1;
  }

  assert(false); /* Shouldn't happen */
}

char *piece_to_str(int piece, int color) {       /* ↓ pawn that may be taken with en passant */
  char *pieces[] = { "♙", "♘", "♗", "♖", "♕", "♔", "♙",
                     "♟", "♞", "♝", "♜", "♛", "♚", "♟" };
  return pieces[color * 7 + piece];
}

int main(void) {
  int ch;
  while (ch = getchar(), ch != EOF) {
    if (ch == '0' || ch == '1') buf[wi++] = ch;
  }

  int board[64];
  memset(board, -1, 64 * sizeof(int));

  /* Read metadata */
  int is_white = read_n(1);
  int castling = read_n(4);

  /* Read the board state */
  int bi = -1;
  while (ri != wi) {
    int color = read_n(1);
    int kind  = read_n(3);
    int delta = read_varnum();
    board[bi + delta] = color << 8 | kind;
    bi += delta;
  }

  /* Print metadata */
  printf("  Current turn: %s's turn to play.\n", is_white? "white" : "black");
  printf("  Castling: White may castle? %s %s\n",
         castling & 0x8? "left" : "", castling & 0x4? "right" : "");
  printf("            Black may castle? %s %s\n",
         castling & 0x2? "left" : "", castling & 0x1? "right" : "");
  printf("\n");

  /* Print the board out */
  printf("+");
  for (int x = 0; x < 8; x++) printf("--");
  printf("-+\n");

  for (int y = 0; y < 8; y++) {
    printf("|");
    for (int x = 0; x < 8; x++) {
      int piece = board[y*8 + x],
          color = piece >> 8,
          kind  = piece & 0xFF;

      if (piece == -1) printf("  ");
      else printf(" %s", piece_to_str(kind, color));
    }
    printf(" |\n");
  }

  printf("+");
  for (int x = 0; x < 8; x++) printf("--");
  printf("-+\n");

  return 0;
}

Maks .: 184 bity, Min: 75 bitów

Zainspirowałem się Huffmanem @ AdamSpeight kodującym elementy, by spróbować stworzyć własny plan. Wątpię, czy to wygra, ale ma granice do obliczenia.

Ten schemat traktuje szachy tak, jakby istniało 11 różnych rodzajów elementów. W przybliżeniu zastosowałem algorytm kodowania Huffmana, aby pogrupować te klasy według ich częstotliwości i typów rzeczywistych, aby wygenerować następujące kodowania:

 Piece Class                | Frequency Per Team | Encoding
============================+====================+==========
 Pawn, normal               | 0 - 8              | 0
 Pawn, jumped two last turn | 0 - 1              | 1111
 Knight                     | 0 - 2              | 1000
 Bishop                     | 0 - 2              | 1001
 Queen-side rook, unmoved   | 0 - 1              | 10100
 Queen-side rook, moved     | 0 - 1              | 10101
 King-side rook, unmoved    | 0 - 1              | 10110
 King-side rook, moved      | 0 - 1              | 10111
 Queen                      | 0 - 1              | 1110
 King, unmoved              | 0 - 1              | 1100
 King, moved                | 0 - 1              | 1101

Kod każdego elementu może być poprzedzony dwoma bitami, aby pokazać, do której drużyny należy ( 10dla białych, 11dla czarnych). 0może być używany do kodowania pustych miejsc. Pomysły te pozwalają nam zbudować kodowanie kwadrat-kwadrat dla całej płyty za pomocą dowolnej procedury. Przyjmę kolejność iteracji a1, b1, c1, ... f8, g8, h8. Oznacza to, że wystarczy wymienić te kody, jak pokazano powyżej, koduje wszystkie informacje, z wyjątkiem tego, czyja jest kolej. Bardzo prosty silnik szachowy może wykorzystać „klasy” pionków, wież i królów, aby ustalić, czy roszowanie i en passant są legalne. Ponadto ten schemat z łatwością obsługuje promocje pionków. Jeśli gracz awansuje pionka na wieżę, można użyć kodu strony króla lub królowej, o ile wybrany zostanie wariant „przeniesiony”.

Z wyjątkiem patologicznych pozycji, które, jak sądzę, nigdy nie mogłyby się wydarzyć, najgorszym scenariuszem dla tego kodowania jest sytuacja, w której wszystkie pionki są nadal na planszy, a poprzedni gracz przesunął pionek o dwa pola do przodu. Na przykład poniższa tablica koduje 1. e4:

1101010010100010100110111010110010100110100010101101001001001100100100100000000000000101111000000000000000000011011011011011011011011011101001110001110011111101111001110011110001110110
===========================================================================
                              Black's move
1110100 111000 111001 111110 111100 111001 111000 1110110 | r n b q k b n r
    110    110    110    110    110    110    110     110 | p p p p p p p p
      0      0      0      0      0      0      0       0 | . . . . . . . .
      0      0      0      0      0      0      0       0 | . . . . . . . .
      0      0      0      0 101111      0      0       0 | . . . . P . . .
      0      0      0      0      0      0      0       0 | . . . . . . . .
    100    100    100    110      0    100    100     100 | P P P P . P P P
1010100 101000 101001 101110 101100 101001 101000 1010110 | R N B Q K B N R

Oznacza to, że kodowanie w najgorszym przypadku ma 184 bity: 1 dla wskazania gracza, 32 dla pustych miejsc, 45 dla niewzruszonych pionków, 6 dla pionka skaczącego o dwa miejsca, 24 dla rycerzy, 24 dla biskupów, 28 dla wież, 12 dla królowych i 12 dla królów.

W miarę przechwytywania i przechwytywania elementów rozmiar kodowania spadnie. Najlepszy scenariusz jest reprezentowany przez dwóch królów na planszy: 1 bit dla wskazania gracza + 62 bity dla wskazania pustych kwadratów + 12 bitów dla wskazania królów daje minimalną długość 75 bitów.

Wrócę i zredaguję tę odpowiedź za pomocą kodu, który demonstruje to kodowanie w działaniu dzisiaj lub jutro. Na razie ciekawi mnie, co sądzą o tym kodowaniu inni ludzie.

184 bity = 23 bajty najgorszy przypadek i niezbyt skomplikowane:

A. Które kwadraty zajęte: 64 bity = 8 bajtów B. Które kolory dla <= 32 zajętych kwadratów: 32 bity = 4 bajty A teraz używając tylko <= 30 kwadratów zajmowanych przez nie-królów: B. użyj PNBRQ zakodowanego w radix 5, dla 5 ^ 30 możliwości; oraz 32 * 31 * 2 * 4 * 4 * 9 dla pozycji króla, koloru poruszającego się, prawa do roszowania białych i czarnych przedmiotów, en passant square (wśród 8 możliwości plus żadna, 9); ta liczba 5 ^ 30 * 32 * 31 * 2 * 4 * 4 * 9 = 266075134277343750000000000 = 2 ^ 87,782 mieści się w 88 bitach, co daje w sumie 64 + 32 + 88 = 184 bity dla całego kodowania.

Można to zmniejszyć, np. 32 * 31 * 2 * 4 * 4 * 9 = 285696 można zmniejszyć do 2 * (32 * 31 + 31 * 3 + 31 * 3 + 3 * 3) * 6 = 14244, używając faktów maksymalnie 6 pasywnych kandydatów na ofiary (w tym żaden), a kodowanie praw rycerskich i pozycji króla w tym samym zestawie przy użyciu faktów rycerskich ma znaczenie tylko w przypadku króla na początkowym polu. To oszczędza 4 bity.

Mam powody sądzić, że nie jest możliwe osiągnięcie 18 bajtów, tj. Całkowita liczba legalnych pozycji w szachach przekracza 2 ^ 144.

Twój 160-bitowy schemat jest bardzo genialny, ale myślę, że należy go podać jako programy do kodowania / dekodowania, zanim będę całkowicie pewny.

Najgorszy przypadek 171 bitów:

Połączyłem kilka pomysłów, a także kilka własnych myśli.

Zaczniemy od 64-bitowej płyty. Każdy bit reprezentuje zajęte miejsce na planszy. Wypełniają się wzdłuż rzędów. Początek wygląda następująco:1111 1111 1111 1111 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111

Teraz każdy kawałek będzie reprezentowany przez 4 bity. 1. bit: kolor ( 0=white, 1=black) 2. – 4. bit: jeden z 8 typów.

0=king, 1=queen, 2=bishop0, 3=knight, 4=rook, 5=pawn0, 6=pawn1, 7=bishop1

Na koniec dodamy nieco oznaczenia tury. 0=white, 1=black.

4 bity * 32 elementy = 128 bitów, a ja mam już 64 + 1 z tury i planszy. To daje w sumie 128 + 64 + 1 = 193 Nawet nie zacząłem en enantant lub castling. Zupełnie ponad limit bez niczego - nawet bez zwrotów. Tutaj zaczynają się sztuczki.

Okej - widzisz te typy powyżej? Bishop0 i Bishop1? Pion 0 i pion 1? Te typy są tak oznaczone, ponieważ każą nam wstawić po tym kawałku. Więc Bishop0 oznacza, że ​​po nim będzie 0 - tzn. Że następny kawałek jest biały. Biskup 1 mówi nam, że następny kawałek jest czarny, a pion 0 i pion 1 działają tak samo. (Jeśli ten kawałek jest ostatnim wyliczanym, to zamiast tego mówi nam o następnej turze).

Mój najgorszy przypadek obejmuje wszystkie elementy na planszy, więc przy 16 pionkach i 4 biskupach oszczędza mi to 20 bitów. Jestem poniżej 173.

W porządku. Z drugiej strony, w moim najgorszym przypadku - gdy 16 kolorów jest zakodowanych, przestajemy kodować kolory - jak wiemy, idzie to do przodu. Mój najgorszy przypadek polega teraz na tym, że biały kawałek przedostaje się do odległego kąta bez przechwytywania. Tam oszczędzam tylko jeden kawałek. 172.

Zamierzam teraz zmienić kolejność, w jakiej nazywam kawałki. Nazwiemy je wzdłuż kolumn, zaczynając od wejścia na zewnątrz. Tablica nazwana na początku pozostanie taka sama, ale kiedy położę na niej pionki, zacznę od białych prawych u dołu i wejdę w górę tej kolumny. Następnie przeskakuję do prawego dolnego rogu czarnego i idę w górę tej kolumny. Przeskakuję do prawej dolnej białej komórki i tak dalej - oznacza to, że mój najgorszy przypadek to znowu początek. Mój powód ma związek z moją en passant trick, następnymi dwoma bitami, które tracę, i kastracją.

Teraz, aby pionek został awansowany (jak zostało to omówione szczegółowo powyżej), kawałek musi zostać schwytany. Zatem, gdy wiemy, że są 32 elementy, musimy tylko zaznaczyć 31 z nich. Ostatni kawałek jest jednoznacznie zidentyfikowany. Jak się okazuje, dla mnie to oszczędza tylko 2 bity - ponieważ mój ostatni kawałek może być pionkiem / biskupem (co normalnie kosztuje mnie 3 bity, ponieważ oszczędzam jeden na następnym kawałku), którego kolor jest już określony i tak było tylko 2 bity. Mam mniej niż 170 bitów.

Kiedy pionki są awansowane, po prostu zmieniają swój typ. Za każdy kawałek, który wychodzi poza planszę, pozbywam się (minimum) 3 bitów, a dwie promocje pionków kosztują mnie 2 bity, więc spadam (powoli) w promocjach.

Castling Aby nastąpił castling, ani król, ani odpowiednia wieża nie mogli się poruszyć. Tak więc, gdy wieża będzie w stanie roszczyć, zarówno ona, jak i król będą w swoich pierwotnych miejscach. Tak więc wieże zdolne do roszowania będą wymienione w tym samym miejscu, co królowie tego koloru. Ponieważ jest to nielegalne (dwóch królów lub trzech królów tego samego koloru na planszy) i może się zdarzyć tylko w trzech możliwych konfiguracjach dla każdego koloru (lewy, prawy, obie wieże są wymienione jako królowie) - dekodowanie jest całkowicie możliwe. Tak więc, bez żadnych fragmentów zakodowaliśmy castling.

En Passant Tutaj będziemy również wykorzystywać nielegalne pozycje. Tylko jeden pionek może być jednocześnie zagrożony en passant. Musi być w czwartym rzędzie. Pion, który jest wrażliwy, zostanie „odwrócony” z powrotem do jego rzędu macierzystego - przełączany z tym, co tam jest. Ponieważ pionek znajduje się w swoim pierwszym rzędzie - nielegalnej pozycji, sytuacja będzie oczywista dla dekodera - odwróci on pozycje i oznaczy pion jako podatny na en passant.

Musieliśmy omijać zamówienie, ponieważ ostatni kawałek musi być „jednoznacznie zidentyfikowany”. W standardowej kolejności nie bylibyśmy w stanie stwierdzić, czy wieża w tylnym rogu mogłaby się zamknąć - nie jest to znane. Kiedy pracujemy z zewnątrz, gwarantujemy, że gdziekolwiek wieża będzie „wymieniona”, czy to w jej własnym rogu, czy na środku planszy, ponieważ została zmieniona pionem wrażliwym na ryzyko, pionek zostanie wymieniony po to - więc powiedziano nam, jaki jest typ wieży. Wiemy, że będzie po nim pionek, ponieważ aby pion mógł być bezbronny, musi znajdować się pionek do jego wnętrza (który będzie musiał zostać zakodowany później, zgodnie z powyższymi instrukcjami).

Aha, i aby upewnić się, że najgorszy przypadek obejmuje wszystkie elementy na planszy, gdy mamy mniej niż 32 elementy, możemy użyć 64-bitowej planszy do zidentyfikowania tury, a także zajętych pozycji, używając zer do reprezentowania elementów, gdy białe turn i 1's, gdy jest czarny turn.

Więc jesteśmy en passant i castling za darmo. Ostatni kawałek wybraliśmy za darmo, choć zajęło to trochę finagowania, aby gra była przyjemna z zasadami en passant i castling. Porzuciliśmy 20 bitów na standardowych elementach. Uważam, że najgorszy przypadek polega na tym, że biały pionek przesunięty do przodu i czarny pion pomiędzy nim a królową, gdy wszystkie pionki są na planszy. Szybka podwójna kontrola: pierwszy pionek zostaje schwytany - nazwij go pionkiem, 3 bity od planszy w pionie, 3 bity na planszy w formie ostatniego elementu, jeden kawałek w znikającym znaczniku tury. Promuj dwa pionki 2 bity z powrotem na planszy. Cholera, mam 171 lat.

EDYCJA Dodałem kod dla (działającego?) Dekodera - w R - poniżej. Jako dane wejściowe przyjmuje wektory boolanów - (przepraszam - nie jestem w stanie dobrze kodować w niczym, co pozwoliłoby mi na użycie bitów) Podałem również pozycję początkową.

separate = function(vec){
    #Using a boolean vector (sorry R doesn't handle bits well and this will build quickest)
    board = matrix(vec[1:64],8,8,byrow=T)
    npieces = min(sum(board),64-sum(board))
    n = length(vec)
    a = vec[65:n]
    counter = 0
    pieces = list()
    white = 0
    Letters=c(letters,LETTERS)
    for (i in 1:npieces){
        col = ifelse(a[1],"black",{white=white+1;"white"})
        typ = a[2:4]
        a=a[-(1:4)]
        num = 4*typ[1] + 2*typ[2] + typ[3]
        type = switch(letters[num+1],a="king",b="queen",c="knight",d="rook",e="bishop0",f="bishop1",g="pawn0",h="pawn1")
        if (num > 3) {
            if(num%%2){
                a = c(T,a)
            } else {
                a = c(F,a)
            }
            type = substr(type,1,nchar(type)-1)
        }
        pieces[[Letters[i]]] = list(color=col,type=type)
        if (length(pieces)==31&&npieces==32) {
            col = ifelse(16-white,{white=white+1;"white"},"black")
            type = "TBD"
            pieces[[Letters[i+1]]] = list(color=col,type=type)
            break
        }
    }

    if (npieces==32) {
        f=function(y){sum(sapply(pieces,function(x)x$type==y))}
        if (f("pawn")<16) {pieces[[32]]$type="pawn"}
        if (f("bishop")<4) {pieces[[32]]$type="bishop"}
        if (f("knight")<4) {pieces[[32]]$type="knight"}
        if (f("queen")<2)  {pieces[[32]]$type="queen"}
        if (f("king")<2)   {pieces[[32]]$type="king"}
        if (f("rook")<(6-f("king"))) {pieces[[32]]$type="rook"}
    }
    return(list(board,pieces,turn=ifelse(a[length(a)],"black","white")))
}


fillboard = function(out) {
    board = out[[1]]
    pieces = out[[2]]
    turn = out[[3]]
    lpieces = lapply(pieces,function(x) paste(substr(x$color,1,1),x$type))
    game = matrix("     ",8,8)
    #Start with corners.
    a = c(1,57,8,64)
    #Then kings
    b = c(25,32)
    #Then rooks in en passant
    c = c(4,60,5,61)
    #Then kings in en passant
    d = 28:29
    exceptions = list(a,b,c,d)
    for (places in exceptions) {
        c= which(board[places])
        if (length(c)) {
            repl = lpieces[1:length(c)]
            game[places[c]] = unlist(repl)
            board[places] = F
            lpieces = lpieces[-(1:length(c))]
        }
    }
    #Loop through rows.
    for (i in c(1:4,8:5)) {
        j = which(board[i,])
        if (length(j)) {
            repl = lpieces[1:length(j)]
            game[i,j] = unlist(repl)
            board[i,j] = F
            lpieces = lpieces[-(1:length(j))]
        }
    }
    return(matrix(unlist(game),8,8,F))
}

swapillegal = function(matr) {
    mat = matr
    if (any(mat[8,]=="b pawn")) {
        j = which(mat[8,]=="b pawn")
        mat[8,j] = mat[5,j]
        mat[5,j] = "b pawn-e"
    }
    if (any(mat[1,]=="w pawn")) {
        j = which(mat[1,]=="w pawn")
        mat[1,j] = mat[4,j]
        mat[4,j] = "w pawn-e"
    }

    if (sum(mat[8,]=="b king") > 1) {
        j = which(mat[8,-4]=="b king")
        j[j==7] = 8
        mat[8,j] = "b rook-c"
    }
    if (sum(mat[1,]=="w king") >1) {
        j = which(mat[1,-4]=="w king")
        j[j==7] = 8
        mat[1,j] = "w rook-c"
    }
    return(mat)
}

decode = function(vec) {
    a = separate(vec)
    b = fillboard(a)
    c = swapillegal(b)
    list(board=c,turn=a[[3]])
}


startboard = c(rep(T,16),rep(F,32),rep(T,16))
#Re-ordering -- first spots will be the corners. Then kings. then en passant positions of those spots
pieces = c(F,F,T,T,F,F,T,T,T,F,T,T,T,F,T,T,F,F,F,F,T,F,F,F,F,F,T,F,F,T,F,F,F,F,T,F,T,F,F,F,T,F,F,T,T,F,T,T,F,T,T,F,T,T,F,T,T,F,T,T,F,T,T,F,T,T,T,F,T,F,T,T,F,T,F,F,T,T,T,F,T,F,T,F,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,F)
########## w rook -w rook -B rook -B rook -W king -B king -w kni  -w bi 0 -w Q  -w Bi 0 -w kni-w p0   - 2   -   3 -  4  - 5   -  6  -  7  -w p1 -b kni-b bi1  -b q  -b bi1  -b kni-b p1   -2    - 3   - 4   - 5   - 6   - b p0- implicit b p0.
#After the kings come all the prior en passant positions. which are empty at start. Then we start at whites bottom right, and move across rows to middle. Then we go to blacks bottom left, and fill across to the middle.
#Changing start to properly encode rooks for castling
newpieces= c(F,F,F,F,F,F,F,F,T,F,F,F,T,F,F,F ,pieces[-(1:16)])
test2 = decode(c(startboard,newpieces))

Ten kod tworzy 4 funkcje. Taki, który dokonuje pewnego podstawowego rozdzielenia elementów i struktury planszy, a także zastanawia się nad typem elementów i wszelkimi „ukrytymi” elementami. Następna funkcja wypełnia strukturę planszy tymi kawałkami w nieco zawrotnej kolejności (i różni się od kolejności mojego początkowego algorytmu) [wyjaśnione w komentarzach do kodu]. Następna funkcja bierze zapełnioną tablicę i wykrywa wszelkie nielegalne pozycje - następnie je naprawia i zmienia nazwy pionów podatnych na en passant „x pawn-e” i wszelkie wieże, które mogą zablokować „x rook-c”. Ostatnią funkcją jest opakowanie, które uruchamia te funkcje w kolejności i daje wyjście, którym jest bieżąca plansza, a także kolej.

Dołączyłem również kodowanie pozycji początkowej (chociaż aby to zobaczyć, będziesz musiał zadzwonić, c(startboard,newpieces)a kod wywoła funkcję otoki na tej pozycji.

229/226 bitów

Nie okazuje się to zbyt skuteczne, ale może uratować innych ludzi idących tą samą ścieżką.

Prosta wersja:

• 1 bit dla którego tury to jest
• 4 bity dla czterech możliwości roszowania
• 3bity dla en passant możliwości. Jest to głębia, którą na początku zrozumiałem. En passant musi zostać wykonany przez pionka poruszającego się z tej samej rangi (rzędu) co pion, który został schwytany. Analiza przypadków wskazuje, że gdy wiemy, ile pionów koloru, który ostatnio się przesunął, przesunęło się dokładnie o dwa kwadraty, będzie maksymalnie 6 en pasywnych przypadków (w tym przypadek, w którym nie ma pionka podatnego na en passant ). Najgorszy przypadek to 5 pionków (potencjalnie wszystkie wrażliwe: np. PpPPpPPpMa pięć wrażliwych P). Przy 6 pionach są maksymalnie 2 pionki wroga o tej samej wartości, z których każdy może zagrozić maksymalnie 2 pionkom en pasywnie . Dlatego potrzebujemy ceil(lg 6) = 3tutaj bitów.

Następnie tablica. Plansza ma 64 kwadraty, więc indeks kwadratowy można zakodować w 6 bitach. Wymieniamy mężczyzn według rangi, zmieniając kolory, zaczynając od króla.

• 6bitów: pozycja białego króla. (Gwarantuje, że będzie na pokładzie).
• 6bitów: pozycja czarnego króla. (Gwarantuje, że będzie na planszy. W najgorszym przypadku, gdy biały król jest w rogu, jest 60 możliwych miejsc, w których mógłby być; w najlepszym przypadku, gdy biały nie jest na krawędzi, jest ich 55).
• 6bitów: pozycja białej królowej. Jeśli nie ma białej królowej, powtórz pozycję białego króla jako sygnał.
• Za każdą dodatkową białą królową, po niej 1nieco 6 bitów dla pozycji.
• 0Bit.
• To samo dotyczy czarnych królowych.
• Podobny proces dotyczy wież, biskupów, rycerzy i pionków, chociaż możemy pominąć pionki dla koloru, jeśli mamy już pod uwagę 16 mężczyzn tego koloru.
• Usuń ostatni 0bit.

To kosztuje pewne 12bity dla królów i 2*7*5-1 = 69bity dla innych ludzi. W najgorszym przypadku, gdy wszyscy 32 mężczyźni są na planszy, kosztuje to 7w sumie bitów za każdego człowieka innego niż królowie 12 + 7*30 - 1 = 221 bits. Tak więc z początkowymi 8bitami dla stanu globalnego mamy 229 bitów .

Wersja zaawansowana:

Używając kodowania arytmetycznego, możemy lg num_possibilitiesraczej operować, a nie ceil(lg num_possibilities)brać go ceilna końcu.

• 1 bit dla którego tury to jest
• 4 bity dla czterech możliwości roszowania
• lg 6bity dla en passant możliwości.
• 6 bitów dla białego króla
• lg 60 bity (najgorszy przypadek) dla czarnego króla
• lg 63 bitów (bo nie chcę tego komplikować do poziomu patrzenia na czeki) dla białej królowej, używając pozycji białego króla, jeśli nie ma
• Dla każdego dodatkowego białej królowej, o 1nieco następnie lg 62, lg 61itp bitów dla jej pozycji.
• 0Bit.
• lg 63 bity (lub mniej, jeśli były jakieś białe królowe) dla czarnej królowej.
• itp.

N-ty mężczyzna, który jest rzeczywiście obecny, ma 66-nmożliwe wartości. Jeśli nie ma typu dla koloru, spędziliśmy 66-#men so fartrochę na jego zapisie (plus jeden bit dla separatora). Skrajne przypadki to:

1. Wszyscy obecni mężczyźni, w tym przynajmniej jeden pionek z każdej strony. Wydajemy 5+lg 6na stan globalny, 6+lg 60na królów, 29na bity separatora i SUM_{n=32}^{63} lg nbity na pozycje. Łączna suma:ceil(225.82) bitów. Niezadowalający.
2. Zostały tylko niewypromowane pionki. Wydajemy 5+lg 6na stan globalny, 6+lg 60na królów, 29na kawałki separatora, 8*lg 63mówiąc, że nie ma innych elementów, i SUM_{n=48}^{63} lg nna pozycje pionków. Suma całkowita: ceil(188.94)bitów. Lepiej - oszczędzając drugą wieżę, rycerza i biskupa z każdej strony, którą nieco wyprzedziliśmy.

Tak więc najgorszy przypadek to 226 bitów , co oznacza oszczędność 3.

Zdecydowanie możemy sobie poradzić w przeciętnym przypadku, kodując pionki przed pionkami, ponieważ są one ograniczone do 48 pól zamiast pełnych 64. Jednak w najgorszym przypadku wszyscy mężczyźni są na planszy, a wszystkie pionki zostały wypromowane kosztowałoby to 2 bity więcej, ponieważ potrzebowalibyśmy flagi „bez pionków” zamiast liczyć ludzi.

To jest temat dyskusji w kręgach szachowych.

Oto jeden bardzo prosty dowód ze 164 bitami https://groups.google.com/forum/#!topic/rec.games.chess.computer/vmvI0ePH2kI 155 pokazano tutaj http://homepages.cwi.nl/~tromp /chess/chess.html

Ponad uproszczona strategia:

• Ogranicz pionki do miejsca, w którym można znaleźć pionki
• Ogranicz armie, aby wziąć pod uwagę oryginalne elementy i możliwe promocje pionków
• Zastanów się dobrze nad promocjami i sytuacjami, w których promocje nie są możliwe

Min: 0 bitów

Max: 1734 243 bity (4,335 4.401 bitów / płytkę zamortyzowanych)

Spodziewany: 351 177 bitów (4,376 4.430 bitów / płytę zamortyzowanych)

Ponieważ mogę określić dane wejściowe i wyjściowe, postanowiłem jednak zakodować historię gry do tego momentu. Jedną z zalet jest to, że dodatkowa informacja o tym, kto tu jest, en-passant, a kto ma zdolność do blokowania, skąd można uzyskać, a nie zakodować.

Próba 1:

Naiwnie pomyślałem, że mogę zakodować każdy ruch w 12 bitach, 4 trojaczkach formy (początek x, początek y, koniec x, koniec y), gdzie każdy ma 3 bity.

Przyjęlibyśmy pozycję początkową i stamtąd przesuwaliśmy pionki, a białe były pierwsze. Plansza jest ułożona w taki sposób, że (0, 0) jest lewym dolnym rogiem bieli.

Na przykład gra:

  e4    e5
 Nf3    f6
Nxe5  fxe5
...    ...

Zostałby zakodowany jako:

100001 100010 100110 100100
110000 101010 101110 101101
101010 100100 101101 100100
...

Prowadzi to do kodowania 12 m bitów, gdzie m jest liczbą wykonanych ruchów

Z jednej strony może to być naprawdę duże, z drugiej strony każdy ruch można uznać za własną grę, więc każde kodowanie naprawdę koduje m „szachownic”. Jeśli amortyzujesz to, otrzymujesz, że każda „szachownica” ma 12 bitów. Ale czuję, że to trochę oszustwo ...

Próba 2:

Uświadomiłem sobie, że każdy ruch w poprzedniej próbie koduje wiele nielegalnych ruchów. Postanowiłem więc zakodować tylko legalne ruchy. Możliwe ruchy wyliczamy w następujący sposób, numerujemy każdy kwadrat tak, aby (0, 0) → 0, (1, 0) → 1, (x, y) → x + 8 lat. Iteruj przez płytki i sprawdź, czy jest tam kawałek i czy może się poruszyć. Jeśli tak, dodaj pozycje, możesz przejść do listy. Wybierz indeks listy, który jest ruchem, który chcesz wykonać. Dodaj tę liczbę do bieżącej sumy ruchów ważonej przez 1 plus liczbę możliwych ruchów.

Przykład jak wyżej: Z pozycji początkowej pierwszym elementem, który może się poruszyć, jest rycerz na polu 1, może przejść na pole 16 lub 18, więc dodaj je do listy [(1,16),(1,18)]. Następnie jest rycerz na polu 6, dodaj jego ruchy. Ogólnie otrzymujemy:

[(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)]

Ponieważ chcemy ruchu (12, 28), kodujemy go jako 13 w bazie 20, ponieważ istnieje 20 możliwych ruchów.

Teraz otrzymujemy numer gry g ₀ = 13

Następnie robimy to samo dla czarnych, z wyjątkiem tego, że numerujemy płytki w odwrotnej kolejności (aby ułatwić, nie jest wymagane), aby uzyskać listę ruchów:

[(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)]

Ponieważ chcemy ruchu (11, 27), kodujemy go jako 11 w bazie 20, ponieważ istnieje 20 możliwych ruchów.

Teraz otrzymujemy numer gry g ₁ = (11 ⋅ 20) + 13 = 233

Następnie otrzymujemy następującą listę ruchów dla białych:

[(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)]

Ponieważ chcemy ruchu (6, 21), kodujemy go jako 13 w bazie 29, ponieważ istnieje 29 możliwych ruchów.

Teraz otrzymujemy numer gry g ₂ = ((13 ⋅ 20) + 11) 20 + 13 = 5433

Następnie otrzymujemy następującą listę ruchów dla czarnych: [(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)]

Ponieważ chcemy przenieść $ (10, 18) $ (10, 18)

Teraz otrzymujemy numer gry g ₃ = (((19 ⋅ 29 + 13) 20) + 11) 20 + 13 = 225833

I kontynuuj ten proces dla wszystkich pozostałych ruchów. Możesz myśleć o g jako o funkcji g (x, y, z) = x y + z. Zatem g ₀ = g (1, 1, 13), g ₁ = g (g (1, 1, 11), 20, 13), g ₂ = g (g (g (1, 1, 13), 20, 11), 20, 13), g ₃ = g (g (g (g (1, 1, 19), 29, 13), 20, 11), 20, 13)

Aby zdekodować grę o numerze g ₀ , zaczynamy od pozycji początkowej i wyliczamy wszystkie możliwe ruchy. Następnie obliczamy g ₁ = g ₀ // l , m ₀ = g ₀ % l , gdzie l jest liczbą możliwych ruchów, „//” jest operatorem podziału liczb całkowitych, a „%” jest operatorem modułu. Powinien przyjąć, że g ₀ = g ₁ + m ₀ . Następnie wykonujemy ruch m ₀ i powtarzamy.

W powyższym przykładzie, jeżeli g ₀ = 225833 wtedy g ₁ = 225833 // 20 = 11291 i m ₀ = 225833% 20 = 13. Następnie g ₂ = 11291 // 20 = 564 i m ₁ = 11.291% 20 = 11. Wtedy g ₃ = 11291 = 20 // i 564 m ₂ = 11.291% 20 = 11. Dlatego g ₄ = 564 // 29 = 19 and_m_ ₃ = 564% 29 = 13. W końcu g ₅ = 19 // 29 = 0, a m ₄ = 19% 29 = 19.

Ile bitów używa się do zakodowania gry w ten sposób?

Dla uproszczenia, powiedzmy, że zawsze jest 20 ruchów na turę, aw najgorszym przypadku zawsze wybieramy największy, 19. Liczba, którą otrzymamy to 19 ⋅ 20 ^m

+ 19 ⋅ 20 ^m-1 + 19 ⋅ 20 ^m-2 + ⋯ + 19 ⋅ 20 + 19 = 20 ^{m + 1} - 1 gdzie _m jest liczbą ruchów. Aby zakodować 20 ^{m + 1} - 1, potrzebujemy około log ₂ (20 ^{m + 1} ) bitów, czyli około (m + 1) ∗ log ₂ (20) = 4,3219 ∗ (m + 1)

Średnio m = 80 (40 ruchów na gracza), więc kodowanie zajmuje 351 bitów. Gdybyśmy nagrywali wiele gier, potrzebowalibyśmy uniwersalnego kodowania, ponieważ nie wiemy, ile bitów będzie potrzebować każda liczba

Najgorszy przypadek, gdy m = 400 (200 ruchów na gracza), więc kodowanie zajęłoby 1734 bitów.

Pamiętaj, że pozycja, którą chcemy zakodować, musi zostać nam podana najkrótszą drogą, aby się tam dostać zgodnie z zasadami. Na przykład gra teoretycznie tutaj nie potrzebuje m = 11741, aby zakodować pozycję końcową. Zamiast tego uruchamiamy wyszukiwanie szerokości, aby znaleźć najkrótszą ścieżkę do tej pozycji i zamiast tego ją zakodować. Nie wiem, jak głęboko potrzebowalibyśmy zejść, by wyliczyć wszystkie pozycje w szachach, ale podejrzewam, że 400 to przecenienie.

Szybkie obliczenia:

Istnieje 12 unikatowych elementów lub kwadrat może być pusty, więc ustawienie ich na szachownicy wynosi 13 ⁶⁴ . Jest to ogromne przeszacowanie, ponieważ obejmuje wiele nieprawidłowych pozycji. Kiedy jesteśmy m, przenosimy się do gry, stworzyliśmy około 20 ^m pozycji. Szukamy więc, kiedy 20 ^m = 13 ⁶⁴ . Zaloguj obie strony, aby uzyskać m = 64 * log ₂₀ (13) = 54,797. To pokazuje, że powinniśmy być w stanie osiągnąć dowolną pozycję w 55 ruchach.

Teraz, gdy obliczyłem najgorszy przypadek jako m = 55, a nie m = 400, wyedytuję swoje wyniki. Aby zakodować pozycję, w której m = 55 zajmuje 243 bity. Powiem też, że średni przypadek wynosi około m = 40, co wymaga 177 bitów do zakodowania.

Jeśli użyjemy argumentu amortyzacji z wcześniejszego okresu, kodujemy 400 „szachownic” w 1734 bitach, więc otrzymujemy, że każda „szachownica” zajmuje w najgorszym przypadku 4,335 bitów.

Zauważ, że g = 0 oznacza prawidłową grę, tę, w której pionek na najniższym kwadracie przesuwa się na najniższy kwadrat, jaki może.

Dodatkowe uwagi:

Jeśli chcesz odwołać się do określonej pozycji w grze, może być konieczne zakodowanie indeksu. Można to dodać ręcznie, np. Połączyć indeks z grą lub dodać dodatkowy ruch „końcowy” jako ostatni możliwy ruch w każdej turze. Może to teraz uwzględniać graczy ustępujących lub 2 z rzędu, oznaczających graczy, którzy zgodzili się na remis. Jest to konieczne tylko wtedy, gdy gra nie zakończyła się matą lub patem na podstawie pozycji, w tym przypadku jest to sugerowane. W tym przypadku liczba potrzebnych bitów wynosi średnio 356, aw najgorszym przypadku 1762.