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!
źródło
Odpowiedzi:
Min: 12 bitów
Max:
Śr .:
Wczoraj pomyślałem i pomyślałem, że mogę go jeszcze zmniejszyć.
Rezultat to imponujący rozmiar 12 bitów !
A co z innym rodzajem K +1?
Istnieje 2 możliwe ustawienie sub-drzewa.
Oba dają te same rozmiary bitów dla wszystkich sztuk. Więc nie ma znaczenia, z którego korzystamy, wybiorę pierwszy.
Tak więc na Królu +2 inne typy elementów
Istnieje 5 możliwych drzewek podrzędnych (użyję 1 i 2, aby wskazać, który z elementów).
Będziemy więc potrzebować 3 bitów do zakodowania, którego sub-drzewa użyć.
Nadal analizuję więcej sztuk
+3 Inne
+4 Inne
+5 Inne
Maks .: 208?
Czy można zakodować wszystkie te podgrzewa w 9 bitach?
Jeśli zsumujemy wszystkie możliwe podgrzewa, otrzymamy 392 możliwe podgrzewa.
Korzystanie z identyfikatora Freq
Ponieważ istnieje 164603 unikatowych częstotliwości sztuk .
(+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 .
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: -
Ś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.
Płytka początkowa może być zakodowana w zaledwie 166 bitach (20,75 bajtów)
Aby wskazać, kto się porusza, zajmuje to tylko jeden bit
Castling można zakodować w 4 bitach.
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
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)
2) Nagłówek o zmiennej długości
Mały 4-bitowy stały nagłówek
Następny blok dodatkowych bitów (jeśli castling jest nadal możliwy)
Następny blok dodatkowych bitów (jeśli obecne są pionki)
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)
Co stanowi około ~ 4 bitów na sztukę.
Jakie rodzaje elementów są obecne na planszy?
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ć.
Pamiętaj, że są bity dodatkowe dla pustych kwadratów i kolorów.
Przykłady
Podajmy przykład, że pozostało tylko QK
Łącznie 81 bitów
Podajmy i zostawmy przykład tylko królów
Złóż wszystko razem
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.
Myśląc o tym, może lepiej po prostu dołączyć 2 bity do bloku nagłówka.
źródło
1111
„Brak en passant możliwy” lub kolumna jako liczba binarna inaczej).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:
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.)
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:
Kładąc wszystko razem:
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):
lub w systemie szesnastkowym:
źródło
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:
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 3 = 8. Ogólnie rzecz biorąc, dla niższej liczby mężczyzn istnieją 2 n 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 n -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 32 .
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:
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:
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.
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.
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:
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:
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:
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.
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.
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.
źródło
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.
źródło
sum_{i=0}^{15} sum_{j=0}^{15} 62! / (i! j! (62-i-j)!) < 2^87.45
.166 bitów
1
bit: czyja to kolej?2
bitó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.585
bitó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?lg 451366131803622235200 ~= 68.613
przypadkach 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) = 166
bity.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:
Możemy również obliczyć liczbę permutacji, biorąc pod uwagę, że gracz ma
N
ludzi i nie więcej niżP
promowane pionki:Łą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:
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:
źródło
<
raczej niż<=
w pętli wyjściowej mojego programu. Dzięki za zwrócenie na to uwagi. Nadal mogłem odzyskać poprzedni wynik poprzez specjalne umieszczenie wszystkich 32 mężczyzn na planszy, ale teraz tego nie zrobię.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.
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:
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).
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:
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).
źródło
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):
Pierwsze pole (umieszczenie elementu) jest analizowane
Produkować:
Pole pierwsze: zakoduj lokalizację królów (12 bitów):
Pole drugie: kodowanie sztuk (do 5 bitów na sztukę):
Pole trzecie: aktywny kolor (1 bit)
Pole czwarte: dostępność castlingu (4 bity)
Pole piąte: en passant (zero lub 3 bity)
Najgorszy naiwny przypadek 200 bitów
QRRBBNN QQQQQQQQ
- 75 bitówqrrbbnn qqqqqqqq
- 75 bitówRzeczywisty 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ówqrrbbnn qqqq
- 55 bitówNajgorszym 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ć:
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.źródło
PPpp
=>QQq_
Łą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:
kolejne 32 bajty są używane do reprezentowania każdego kawałka szachowego, w ustalonej kolejności
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)
źródło
256242 bitówOto 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:
Następnie ciąg 12 bitów reprezentujących pozycje królów.
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:
A cyfry w bazie 9:
11 64 × 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.
źródło
13^64 * 9
to 239,99, oszczędzając 11 bitów. Zaoszczędź więcej, kodując osobno pozycje króla.? 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,
1
oznaczającą, że ten kawałek jest tuż obok poprzedniego,0xx
do pominięcia 1-3 sztuk,000xxx
do pominięcia 4-10 sztuk,000000xxxx
dla 11-25,0000000000xxxxx
dla 26-56 i wreszcie000000000000000xxx
za 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.
źródło
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:
Kod każdego elementu może być poprzedzony dwoma bitami, aby pokazać, do której drużyny należy (
10
dla białych,11
dla czarnych).0
moż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ść iteracjia1, 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
: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.
źródło
11001
oznaczaB'S MOVE
W CAN KSC
W CANT QSC
B CANT KSC
B CAN QSC
). To 4 bity zamiast 5 bitów na stronę w twoim kodowaniu lub 3 bity na stronę, jeśli wyeliminujesz znacznik boczny na wieżach. (KSC
= Zamek po stronie króla.QSC
= Zamek po stronie królowej)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.
źródło
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.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ą.
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.źródło
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 jest4
bity dla czterech możliwości roszowania3
bity 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.PpPPpPPp
Ma pięć wrażliwychP
). 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 potrzebujemyceil(lg 6) = 3
tutaj 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.
6
bitów: pozycja białego króla. (Gwarantuje, że będzie na pokładzie).6
bitó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).6
bitów: pozycja białej królowej. Jeśli nie ma białej królowej, powtórz pozycję białego króla jako sygnał.1
nieco 6 bitów dla pozycji.0
Bit.0
bit.To kosztuje pewne
12
bity dla królów i2*7*5-1 = 69
bity dla innych ludzi. W najgorszym przypadku, gdy wszyscy 32 mężczyźni są na planszy, kosztuje to7
w sumie bitów za każdego człowieka innego niż królowie12 + 7*30 - 1 = 221 bits
. Tak więc z początkowymi8
bitami dla stanu globalnego mamy 229 bitów .Wersja zaawansowana:
Używając kodowania arytmetycznego, możemy
lg num_possibilities
raczej operować, a nieceil(lg num_possibilities)
brać goceil
na końcu.1
bit dla którego tury to jest4
bity dla czterech możliwości roszowanialg 6
bity dla en passant możliwości.6
bitów dla białego królalg 60
bity (najgorszy przypadek) dla czarnego królalg 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 ma1
nieco następnielg 62
,lg 61
itp bitów dla jej pozycji.0
Bit.lg 63
bity (lub mniej, jeśli były jakieś białe królowe) dla czarnej królowej.N-ty mężczyzna, który jest rzeczywiście obecny, ma
66-n
możliwe wartości. Jeśli nie ma typu dla koloru, spędziliśmy66-#men so far
trochę na jego zapisie (plus jeden bit dla separatora). Skrajne przypadki to:5+lg 6
na stan globalny,6+lg 60
na królów,29
na bity separatora iSUM_{n=32}^{63} lg n
bity na pozycje. Łączna suma:ceil(225.82)
bitów. Niezadowalający.5+lg 6
na stan globalny,6+lg 60
na królów,29
na kawałki separatora,8*lg 63
mówiąc, że nie ma innych elementów, iSUM_{n=48}^{63} lg n
na 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.
źródło
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:
źródło
Min: 0 bitów
Max:
1734243 bity (4,3354.401 bitów / płytkę zamortyzowanych)Spodziewany:
351177 bitów (4,3764.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:
Zostałby zakodowany jako:
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 0 = 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 1 = (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 2 = ((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 3 = (((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 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)
Aby zdekodować grę o numerze g 0 , zaczynamy od pozycji początkowej i wyliczamy wszystkie możliwe ruchy. Następnie obliczamy g 1 = g 0 // l , m 0 = g 0 % 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 0 = g 1 + m 0 . Następnie wykonujemy ruch m 0 i powtarzamy.
W powyższym przykładzie, jeżeli g 0 = 225833 wtedy g 1 = 225833 // 20 = 11291 i m 0 = 225833% 20 = 13. Następnie g 2 = 11291 // 20 = 564 i m 1 = 11.291% 20 = 11. Wtedy g 3 = 11291 = 20 // i 564 m 2 = 11.291% 20 = 11. Dlatego g 4 = 564 // 29 = 19 and_m_ 3 = 564% 29 = 13. W końcu g 5 = 19 // 29 = 0, a m 4 = 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 2 (20 m + 1 ) bitów, czyli około (m + 1) ∗ log 2 (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 64 . 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 64 . Zaloguj obie strony, aby uzyskać m = 64 * log 20 (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.
źródło