Programmer Puzzle: kodowanie stanu szachownicy w trakcie gry

Question 1

Nie do końca pytanie, bardziej zagadka ...

Przez lata brałem udział w kilku wywiadach technicznych z nowymi pracownikami. Poza zadawaniem standardowych pytań „czy znasz technologię X”, próbowałem też wyczuć, jak podchodzą do problemów. Zazwyczaj wysyłałem im pytanie e-mailem dzień przed rozmową i oczekiwałem, że znajdą rozwiązanie do następnego dnia.

Często wyniki byłyby dość interesujące - błędne, ale interesujące - a osoba nadal otrzymywałaby moją rekomendację, gdyby mogła wyjaśnić, dlaczego przyjęła określone podejście.

Więc pomyślałem, że rzucę jedno z moich pytań do publiczności Stack Overflow.

Pytanie: Jaki jest najbardziej efektywny przestrzennie sposób kodowania stanu gry w szachy (lub jej podzbioru)? Oznacza to, że mając szachownicę z legalnie ułożonymi figurami, koduje zarówno ten stan początkowy, jak i wszystkie kolejne legalne ruchy podejmowane przez graczy w grze.

Do odpowiedzi nie jest wymagany kod, tylko opis algorytmu, którego użyjesz.

EDYCJA: Jak wskazał jeden z plakatów, nie brałem pod uwagę odstępu czasu między ruchami. Zapraszam do uwzględnienia tego również jako opcjonalnego dodatku :)

EDIT2: Tylko dla dodatkowego wyjaśnienia ... Pamiętaj, że koder / dekoder jest zgodny z regułami. Jedyne rzeczy, które naprawdę muszą być przechowywane, to wybory gracza - można założyć, że wszystko inne jest znane koderowi / dekoderowi.

EDIT3: Trudno będzie tutaj wybrać zwycięzcę :) Wiele świetnych odpowiedzi!

Question 2

Aktualizacja: Podobał mi się ten temat tak bardzo, że napisałem zagadki programistyczne, pozycje szachowe i kodowanie Huffmana . Jeśli przeczytałeś to, stwierdziłem, że jedynym sposobem na zapisanie pełnego stanu gry jest przechowywanie pełnej listy ruchów. Przeczytaj, dlaczego. Używam więc nieco uproszczonej wersji problemu dla układu elementów.

Problem

Ten obraz przedstawia początkową pozycję szachową. Szachy rozgrywane są na szachownicy 8x8, a każdy gracz zaczyna od identycznego zestawu 16 pionów, składającego się z 8 pionów, 2 wież, 2 skoczków, 2 gońców, 1 królowej i 1 króla, jak pokazano na ilustracji:

Pozycje są generalnie zapisywane jako litera w kolumnie, po której następuje numer w rzędzie, więc hetman białych jest na d1. Ruchy są najczęściej zapisywane w notacji algebraicznej , która jest jednoznaczna i generalnie określa jedynie minimum niezbędnych informacji. Rozważ to otwarcie:

e4 e5
Sf3 Nc6
…

co przekłada się na:

Białe przesuwają pionka króla z e2 na e4 (jest to jedyna figura, która może dostać się na e4, stąd „e4”);
Czarne przesuwają pionka króla z e7 na e5;
Białe przesuwają skoczka (N) na f3;
Czarne przesuwają skoczka na c6.
…

Tablica wygląda następująco:

Ważną umiejętnością dla każdego programisty jest umiejętność poprawnego i jednoznacznego określenia problemu .

Więc czego brakuje lub czego jest niejednoznaczne? Okazuje się, że dużo.

Stan planszy a stan gry

Pierwszą rzeczą, którą musisz ustalić, jest to, czy przechowujesz stan gry lub pozycję pionków na planszy. Samo zakodowanie pozycji figur to jedno, ale problem polega na tym, że „wszystkie kolejne legalne posunięcia”. Problem nie mówi też nic o znajomości ruchów do tego momentu. Właściwie to problem, jak wyjaśnię.

Roszada

Gra przebiegała w następujący sposób:

e4 e5
Sf3 Nc6
Gb5 a6
Ba4 Bc5

Tablica wygląda następująco:

później otwarcie

Biały ma możliwość roszady . Częścią wymagań jest to, że król i odpowiednia wieża nigdy nie mogą się poruszyć, więc to, czy król lub wieża każdej ze stron się poruszyły, będzie musiało zostać zapisane. Oczywiście, jeśli nie są na swoich pozycjach wyjściowych, przesunęli się, w przeciwnym razie należy to określić.

Istnieje kilka strategii, które można zastosować w celu rozwiązania tego problemu.

Po pierwsze, mogliśmy przechowywać dodatkowe 6 bitów informacji (po 1 dla każdej wieży i króla), aby wskazać, czy ta figura się przesunęła. Moglibyśmy to usprawnić, przechowując tylko trochę dla jednego z tych sześciu kwadratów, jeśli akurat w nim znajduje się właściwy kawałek. Alternatywnie możemy traktować każdą nieruchomą figurę jako inny typ figury, więc zamiast 6 typów figury po każdej stronie (pionek, wieża, skoczek, goniec, hetman i król) jest 8 (dodając nieporuszoną wieżę i nieporuszonego króla).

Mimochodem

Inną osobliwą i często zaniedbywaną zasadą w szachach jest En Passant .

Gra postępowała.

e4 e5
Sf3 Nc6
Gb5 a6
Ba4 Bc5
OO b5
Gb3 b4
c4

Pion czarnych na b4 ma teraz możliwość przesunięcia swojego pionka na b4 na c3, zabierając białego pionka na c4. Dzieje się to tylko przy pierwszej okazji, co oznacza, że jeśli czarny spasuje z tej opcji teraz, nie może jej wykonać w następnym ruchu. Więc musimy to przechowywać.

Jeśli znamy poprzedni ruch, z pewnością możemy odpowiedzieć, czy En Passant jest możliwy. Alternatywnie możemy zapamiętać, czy każdy pionek na czwartym rzędzie właśnie się tam poruszył podwójnym ruchem do przodu. Albo możemy spojrzeć na każdą możliwą pozycję En Passant na planszy i mieć flagę wskazującą, czy jest to możliwe, czy nie.

Awans

To ruch białych. Jeśli białe przesuną swojego pionka na h7 do h8, to mogą zostać awansowane na dowolną inną figurę (ale nie króla). W 99% przypadków jest ona promowana do królowej, ale czasami tak nie jest, zazwyczaj dlatego, że może to wymusić impas, jeśli w przeciwnym razie wygrasz. Jest to zapisane jako:

h8 = Q

Jest to ważne w naszym problemie, ponieważ oznacza, że nie możemy liczyć na stałą liczbę sztuk z każdej strony. Jest całkowicie możliwe (ale niewiarygodnie mało prawdopodobne), że jedna strona skończy z 9 damami, 10 wieżami, 10 gońcami lub 10 skoczkami, jeśli wszystkie 8 pionków awansuje.

Pat

Kiedy jesteś na pozycji, z której nie możesz wygrać, najlepszą taktyką jest próba impasu . Najbardziej prawdopodobnym wariantem jest sytuacja, w której nie możesz wykonać legalnego ruchu (zwykle z powodu dowolnego ruchu, gdy szachujesz króla). W takim przypadku możesz ubiegać się o remis. Ten jest łatwy do zaspokojenia.

Drugi wariant to trzykrotne powtórzenie . Jeśli ta sama pozycja na szachownicy wystąpi trzy razy w grze (lub wystąpi po raz trzeci w następnym ruchu), można ubiegać się o remis. Pozycje nie muszą występować w określonej kolejności (co oznacza, że nie muszą one powtarzać tej samej sekwencji ruchów trzykrotnie). To znacznie komplikuje problem, ponieważ musisz pamiętać o każdej poprzedniej pozycji na stole. Jeśli jest to wymóg problemu, jedynym możliwym rozwiązaniem problemu jest zapisanie każdego poprzedniego ruchu.

Na koniec obowiązuje zasada pięćdziesięciu ruchów . Gracz może ubiegać się o remis, jeśli żaden pionek się nie poruszył i żadna figura nie została zabrana w poprzednich pięćdziesięciu kolejnych posunięciach, więc musielibyśmy zapisać, ile ruchów został przesunięty lub zabrany pionek (ostatni z dwóch. 6 bitów (0-63).

Czyja to kolej?

Oczywiście musimy również wiedzieć, czyja kolej, a to jest tylko jedna informacja.

Dwa problemy

Ze względu na sytuację patową jedynym wykonalnym lub rozsądnym sposobem przechowywania stanu gry jest przechowywanie wszystkich ruchów, które doprowadziły do tej pozycji. Zajmę się tym jednym problemem. Problem ze stanem szachownicy zostanie uproszczony do tego: zapisz aktualne położenie wszystkich figur na szachownicy, ignorując roszadę, przelotny, patowy stan i czy to jest kolejka .

Układ elementów można ogólnie obsługiwać na jeden z dwóch sposobów: przechowując zawartość każdego kwadratu lub zapisując położenie każdego elementu.

Prosta zawartość

Istnieje sześć typów figur (pionek, wieża, skoczek, goniec, królowa i król). Każdy element może być biały lub czarny, więc kwadrat może zawierać jedną z 12 możliwych sztuk lub może być pusty, więc istnieje 13 możliwości. 13 można zapisać w 4 bitach (0-15). Najprostszym rozwiązaniem jest więc zapisanie 4 bitów na każdy kwadrat pomnożony przez 64 kwadraty lub 256 bitów informacji.

Zaletą tej metody jest to, że manipulacja jest niezwykle łatwa i szybka. Można to nawet rozszerzyć, dodając 3 dodatkowe możliwości bez zwiększania wymagań dotyczących przechowywania: pionka, który przesunął się o 2 pola w ostatniej turze, króla, który się nie poruszył i wieży, która się nie poruszyła, co wystarczy na wiele. wspomnianych wcześniej problemów.

Ale możemy zrobić lepiej.

Kodowanie Base 13

Często pomocne jest myślenie o pozycji na tablicy jako bardzo dużej liczbie. Jest to często wykonywane w informatyce. Na przykład problem zatrzymania traktuje program komputerowy (słusznie) jako dużą liczbę.

Pierwsze rozwiązanie traktuje pozycję jako 64-cyfrową liczbę o podstawie 16, ale jak pokazano, w tej informacji występuje nadmiarowość (czyli 3 niewykorzystane możliwości na „cyfrę”), więc możemy zmniejszyć przestrzeń liczbową do 64 podstawowych 13 cyfr. Oczywiście nie można tego zrobić tak wydajnie, jak podstawa 16, ale pozwoli to zaoszczędzić na wymaganiach dotyczących pamięci (a naszym celem jest zminimalizowanie przestrzeni dyskowej).

W podstawie 10 liczba 234 jest równoważna 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

W podstawie 16 liczba 0xA50 jest równoważna 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (dziesiętnie).

Możemy więc zakodować naszą pozycję jako p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ gdzie p _i reprezentuje zawartość kwadratu i .

2 ²⁵⁶ to w przybliżeniu 1,16e77. 13 ⁶⁴ równa się w przybliżeniu 1,96e71, co wymaga 237 bitów przestrzeni dyskowej. Oszczędność zaledwie 7,5% odbywa się kosztem znacznie zwiększonych kosztów manipulacji.

Kodowanie o zmiennej podstawie

Na legalnych planszach pewne figury nie mogą pojawić się na niektórych polach. Na przykład pionki nie mogą występować w pierwszym lub ósmym rzędzie, co zmniejsza możliwości dla tych kwadratów do 11. To zmniejsza liczbę możliwych tablic do 11 ¹⁶ x 13 ⁴⁸ = 1,35e70 (w przybliżeniu), co wymaga 233 bitów miejsca w pamięci.

W rzeczywistości kodowanie i dekodowanie takich wartości do i od dziesiętnego (lub binarnego) jest nieco bardziej zawiłe, ale można to zrobić niezawodnie i pozostawia się je czytelnikowi jako ćwiczenie.

Alfabety o zmiennej szerokości

Dwie poprzednie metody można opisać jako kodowanie alfabetyczne o stałej szerokości . Każdy z 11, 13 lub 16 elementów alfabetu jest zastępowany inną wartością. Każdy „znak” ma tę samą szerokość, ale wydajność można poprawić, jeśli weźmie się pod uwagę, że każdy znak nie jest tak samo prawdopodobny.

Kod Morse'a

Rozważmy kod Morse'a (na zdjęciu powyżej). Znaki w wiadomości są kodowane jako sekwencja myślników i kropek. Te kreski i kropki są przesyłane przez radio (zwykle) z przerwą między nimi, aby je rozgraniczać.

Zwróć uwagę, że litera E ( najczęściej spotykana litera w języku angielskim ) to pojedyncza kropka, najkrótsza możliwa sekwencja, podczas gdy Z (najmniej częsta) to dwie kreski i dwa sygnały dźwiękowe.

Taki schemat może znacznie zmniejszyć rozmiar oczekiwanej wiadomości, ale odbywa się kosztem zwiększenia rozmiaru losowej sekwencji znaków.

Należy zauważyć, że kod Morse'a ma inną wbudowaną funkcję: kreski są tak długie, jak trzy kropki, więc powyższy kod jest tworzony z myślą o tym, aby zminimalizować użycie myślników. Ponieważ 1 i 0 (nasze bloki konstrukcyjne) nie mają tego problemu, nie jest to funkcja, którą musimy replikować.

Wreszcie istnieją dwa rodzaje pauz w alfabecie Morse'a. Krótka pauza (długość kropki) służy do rozróżnienia kropek i kresek. Dłuższa przerwa (długość myślnika) służy do oddzielania znaków.

Jak to się ma do naszego problemu?

Kodowanie Huffmana

Istnieje algorytm radzenia sobie z kodami o zmiennej długości, zwany kodowaniem Huffmana . Kodowanie Huffmana tworzy podstawienie kodu o zmiennej długości, zazwyczaj wykorzystuje oczekiwaną częstotliwość symboli do przypisywania krótszych wartości do bardziej powszechnych symboli.

W powyższym drzewie litera E jest zakodowana jako 000 (lub lewa-lewa-lewa), a S to 1011. Powinno być jasne, że ten schemat kodowania jest jednoznaczny .

Jest to ważna różnica w stosunku do alfabetu Morse'a. Kod Morse'a ma separator znaków, więc może wykonywać niejednoznaczne podstawienia (np. 4 kropki mogą być H lub 2 Is), ale mamy tylko jedynki i 0, więc zamiast tego wybieramy jednoznaczne podstawienie.

Poniżej prosta implementacja:

private static class Node {
  private final Node left;
  private final Node right;
  private final String label;
  private final int weight;

  private Node(String label, int weight) {
    this.left = null;
    this.right = null;
    this.label = label;
    this.weight = weight;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    label = "";
    weight = left.weight + right.weight;
  }

  public boolean isLeaf() { return left == null && right == null; }

  public Node getLeft() { return left; }

  public Node getRight() { return right; }

  public String getLabel() { return label; }

  public int getWeight() { return weight; }
}

z danymi statycznymi:

private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;

static {
  List<string> list = new ArrayList<string>();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map<string, integer> map = new HashMap<string, integer>();
  for (String colour : COLOURS) {
    map.put(colour + " " + "King", 1);
    map.put(colour + " " + "Queen";, 1);
    map.put(colour + " " + "Rook", 2);
    map.put(colour + " " + "Knight", 2);
    map.put(colour + " " + "Bishop";, 2);
    map.put(colour + " " + "Pawn", 8);
  }
  map.put("Empty", 32);
  WEIGHTS = Collections.unmodifiableMap(map);
}

i:

private static class WeightComparator implements Comparator<node> {
  @Override
  public int compare(Node o1, Node o2) {
    if (o1.getWeight() == o2.getWeight()) {
      return 0;
    } else {
      return o1.getWeight() < o2.getWeight() ? -1 : 1;
    }
  }
}

private static class PathComparator implements Comparator<string> {
  @Override
  public int compare(String o1, String o2) {
    if (o1 == null) {
      return o2 == null ? 0 : -1;
    } else if (o2 == null) {
      return 1;
    } else {
      int length1 = o1.length();
      int length2 = o2.length();
      if (length1 == length2) {
        return o1.compareTo(o2);
      } else {
        return length1 < length2 ? -1 : 1;
      }
    }
  }
}

public static void main(String args[]) {
  PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
      new WeightComparator());
  for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
    queue.add(new Node(entry.getKey(), entry.getValue()));
  }
  while (queue.size() > 1) {
    Node first = queue.poll();
    Node second = queue.poll();
    queue.add(new Node(first, second));
  }
  Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
  addLeaves(nodes, queue.peek(), &quot;&quot;);
  for (Map.Entry<string, node> entry : nodes.entrySet()) {
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  }
}

public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
  if (node != null) {
    addLeaves(nodes, node.getLeft(), prefix + "0");
    addLeaves(nodes, node.getRight(), prefix + "1");
    if (node.isLeaf()) {
      nodes.put(prefix, node);
    }
  }
}

Jednym z możliwych wyników jest:

         White    Black
Empty          0 
Pawn       110      100
Rook     11111    11110
Knight   10110    10101
Bishop   10100    11100
Queen   111010   111011
King    101110   101111

Dla pozycji początkowej odpowiada to 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bity.

Różnica stanów

Innym możliwym podejściem jest połączenie pierwszego podejścia z kodowaniem Huffmana. Opiera się to na założeniu, że większość oczekiwanych szachownic (a nie losowo generowanych) z większym prawdopodobieństwem, przynajmniej częściowo, będzie przypominać pozycję wyjściową.

Więc to, co robisz, to XOR 256-bitowej bieżącej pozycji płytki z 256-bitową pozycją początkową, a następnie zakodowanie tego (używając kodowania Huffmana lub, powiedzmy, jakiejś metody kodowania długości przebiegu ). Oczywiście na początku będzie to bardzo wydajne (64 0 prawdopodobnie odpowiadające 64 bitom), ale wymagane będzie zwiększenie ilości pamięci w miarę postępu gry.

Pozycja elementu

Jak wspomniano, innym sposobem rozwiązania tego problemu jest zamiast tego przechowywanie pozycji każdej figury gracza. Działa to szczególnie dobrze na pozycjach końcowych, w których większość pól będzie pustych (ale w podejściu do kodowania Huffmana puste pola i tak używają tylko 1 bitu).

Każda strona będzie miała króla i 0-15 innych figur. Ze względu na promocję dokładny skład tych elementów może się różnić na tyle, że nie można założyć, że liczby oparte na pozycjach startowych są maksymalne.

Logicznym sposobem na podzielenie tego jest przechowywanie Pozycji składającej się z dwóch Stron (Białej i Czarnej). Każda strona ma:

Król: 6 bitów na lokalizację;
Ma pionki: 1 (tak), 0 (nie);
Jeśli tak, liczba pionków: 3 bity (0-7 + 1 = 1-8);
Jeśli tak, kodowane jest położenie każdego pionka: 45 bitów (patrz poniżej);
Liczba pionków: 4 bity (0-15);
Dla każdej figury: typ (2 bity na hetman, wieżę, skoczka, gońca) i położenie (6 bitów)

Jeśli chodzi o lokalizację pionków, pionki mogą znajdować się tylko na 48 możliwych polach (nie 64 jak pozostałe). W związku z tym lepiej nie marnować dodatkowych 16 wartości, których wymagałoby użycie 6 bitów na pionka. Więc jeśli masz 8 pionków, istnieje 48 ⁸ możliwości, co daje 28.179.280.429.056. Do zakodowania tak wielu wartości potrzeba 45 bitów.

To 105 bitów na stronę lub łącznie 210 bitów. Jednak pozycja początkowa jest najgorszym przypadkiem dla tej metody i będzie znacznie lepsza, gdy usuniesz kawałki.

Należy zaznaczyć, że możliwości jest mniej niż 48 ^8, ponieważ wszystkie pionki nie mogą znajdować się na tym samym polu. Pierwszy ma 48 możliwości, drugi 47 i tak dalej. 48 x 47 x… x 41 = 1,52e13 = 44 bity pamięci.

Możesz to jeszcze bardziej poprawić, eliminując kwadraty zajmowane przez inne figury (w tym drugą stronę), abyś mógł najpierw umieścić białe pionki niebędące pionkami, potem czarne pionki niebędące pionkami, potem białe i na końcu czarne. W pozycji początkowej zmniejsza to wymagania dotyczące przechowywania do 44 bitów dla bieli i 42 bitów dla czerni.

Podejścia łączone

Inną możliwą optymalizacją jest to, że każde z tych podejść ma swoje mocne i słabe strony. Możesz, powiedzmy, wybrać najlepsze 4, a następnie zakodować selektor schematu w pierwszych dwóch bitach, a następnie pamięć specyficzną dla schematu po tym.

Przy tak niewielkich kosztach ogólnych będzie to zdecydowanie najlepsze podejście.

Stan gry

Wracam do problemu przechowywania gry, a nie pozycji . Ze względu na trzykrotne powtórzenia musimy przechowywać listę ruchów, które miały miejsce do tego momentu.

Adnotacje

Musisz tylko ustalić, czy po prostu przechowujesz listę ruchów, czy też dodajesz adnotacje do gry? Gry w szachy są często opatrzone adnotacjami, na przykład:

Gb5 !! Nc4?

Ruch białych jest oznaczony dwoma wykrzyknikami jako genialny, podczas gdy ruch czarnych jest postrzegany jako błąd. Zobacz interpunkcję w szachach .

Dodatkowo może być konieczne zapisanie dowolnego tekstu, ponieważ ruchy są opisane.

Zakładam, że ruchy są wystarczające, więc nie będzie adnotacji.

Notacja algebraiczna

Moglibyśmy po prostu zapisać tutaj tekst ruchu („e4”, „Gxb5” itd.). Uwzględniając bajt kończący, masz około 6 bajtów (48 bitów) na ruch (najgorszy przypadek). To nie jest szczególnie wydajne.

Drugą rzeczą do wypróbowania jest zapisanie lokalizacji początkowej (6 bitów) i lokalizacji końcowej (6 bitów), tak aby 12 bitów na ruch. To jest znacznie lepsze.

Alternatywnie możemy określić wszystkie legalne ruchy z aktualnej pozycji w przewidywalny i deterministyczny sposób i stan, który wybraliśmy. Następnie wraca do wspomnianego powyżej kodowania zmiennej bazy. Białe i czarne mają po 20 możliwych ruchów w pierwszym ruchu, więcej w drugim i tak dalej.

Wniosek

Nie ma absolutnie poprawnej odpowiedzi na to pytanie. Istnieje wiele możliwych podejść, z których powyższe to tylko kilka.

To, co mi się podoba w tym i podobnych problemach, to to, że wymaga to umiejętności ważnych dla każdego programisty, takich jak rozważenie wzorca użycia, dokładne określenie wymagań i myślenie o przypadkach narożnych.

Pozycje szachowe zrobione jako zrzuty ekranu z programu Chess Position Trainer .

Question 3

Najlepiej przechowywać gry w szachy w standardowym formacie czytelnym dla człowieka.

Portable gra Notation zakłada standardową pozycję wyjściową (choć nie musi ) i po prostu wymienia ruchów, zakręt po zakręcie. Kompaktowy, czytelny dla człowieka, standardowy format.

Na przykład

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Jeśli chcesz, aby był mniejszy, po prostu zapnij go . Zadanie wykonane!

Question 4

Świetna łamigłówka!

Widzę, że większość ludzi zapisuje położenie każdego elementu. Co powiesz na prostsze podejście i przechowywanie zawartości każdego kwadratu ? To automatycznie zajmuje się promocją i zdobytymi kawałkami.

I pozwala na kodowanie Huffmana . Właściwie początkowa częstotliwość pionów na szachownicy jest do tego prawie idealna: połowa pól jest pusta, połowa pozostałych to pionki itd.

Biorąc pod uwagę częstotliwość każdego elementu, skonstruowałem drzewo Huffmana na papierze, którego nie będę tutaj powtarzał. Wynik, gdzie coznacza kolor (biały = 0, czarny = 1):

0 dla pustych kwadratów
1c0 za pionka
1c100 dla wieży
1c101 dla rycerza
1c110 dla biskupa
1c1110 dla królowej
1c1111 dla króla

Mamy dla całej płyty w jej początkowej sytuacji

puste kwadraty: 32 * 1 bit = 32 bity
pionki: 16 * 3 bity = 48 bitów
wieże / rycerze / biskupi: 12 * 5 bitów = 60 bitów
królowe / królowie: 4 * 6 bitów = 24 bity

Łącznie: 164 bity dla początkowego stanu karty. Znacząco mniej niż 235 bitów aktualnie najwyższej głosowanej odpowiedzi. I będzie się zmniejszać w miarę postępów w grze (z wyjątkiem promocji).

Patrzyłem tylko na położenie pionków na planszy; Dodatkowy stan (którego tura, kto wykonał roszadę, en passant, powtarzające się ruchy itp.) będzie musiał zostać zakodowany oddzielnie. Może najwyżej kolejne 16 bitów, czyli 180 bitów na cały stan gry. Możliwe optymalizacje:

Pomijanie rzadszych elementów i osobne przechowywanie ich pozycji. Ale to nie pomoże ... zastąpienie króla i hetmana pustym kwadratem oszczędza 5 bitów, czyli dokładnie 5 bitów potrzebnych do zakodowania ich pozycji w inny sposób.
„Żadnych pionków w tylnym rzędzie” można łatwo zakodować, używając innej tabeli Huffmana w tylnych rzędach, ale wątpię, by to bardzo pomogło. Prawdopodobnie nadal będziesz miał to samo drzewo Huffmana.
„Jeden biały, jeden czarny goniec” można zakodować, wprowadzając dodatkowe symbole, które nie mają cbitu, które można następnie wydedukować z kwadratu, na którym stoi goniec. (Pionki awansowane na biskupów zakłócają ten schemat ...)
Powtórzenia pustych kwadratów można zakodować według długości serii, wprowadzając dodatkowe symbole, na przykład „2 puste kwadraty w rzędzie” i „4 puste kwadraty w rzędzie”. Ale nie jest łatwo oszacować ich częstotliwość, a jeśli się pomylisz, to raczej zaszkodzi niż pomoże.

Question 5

Naprawdę duże podejście do tabeli przeglądowej

Pozycja - 18 bajtów
Szacunkowa liczba legalnych pozycji wynosi 10 ⁴³
Po prostu wylicz je wszystkie, a pozycja może być zapisana w zaledwie 143 bitach. Wymagany jest jeszcze 1 bit, aby wskazać, która strona ma grać jako następna

Wyliczenie nie jest oczywiście praktyczne, ale pokazuje, że wymagane są co najmniej 144 bity.

Ruchy - 1 bajt
Zwykle jest około 30-40 legalnych ruchów dla każdej pozycji, ale liczba może sięgać nawet 218. Wyliczmy wszystkie legalne ruchy dla każdej pozycji. Teraz każdy ruch można zakodować w jednym bajcie.

Nadal mamy dużo miejsca na ruchy specjalne, takie jak 0xFF, które reprezentuje rezygnację.

Question 6

Optymalizacja pod kątem średniej wielkości obudowy dla typowych gier granych przez ludzi zwiększyłaby zainteresowanie , zamiast najgorszego przypadku. (W stwierdzeniu problemu nie podano, który; większość odpowiedzi zakłada najgorszy przypadek).

W sekwencji ruchów dobry silnik szachowy generuje ruchy z każdej pozycji; wyświetli listę k możliwych ruchów, uporządkowaną według rankingu ich jakości. Ludzie na ogół częściej wybierają dobre ruchy niż losowe, więc musimy nauczyć się mapowania z każdej pozycji na liście prawdopodobieństwa, że ludzie wybiorą ruch, który jest „dobry”. Korzystając z tych prawdopodobieństw (na podstawie zbioru gier z pewnej internetowej bazy danych szachów), zakoduj ruchy za pomocą kodowania arytmetycznego . (Dekoder musi używać tego samego silnika szachowego i mapowania).

W przypadku pozycji wyjściowej podejście ralu zadziałałoby. Moglibyśmy to również udoskonalić za pomocą kodowania arytmetycznego, gdybyśmy mieli jakiś sposób zważyć wybory prawdopodobieństwem - np. Elementy często pojawiają się w konfiguracjach, które się wzajemnie bronią, a nie przypadkowo. Trudniej jest znaleźć łatwy sposób na włączenie tej wiedzy. Jeden pomysł: zamiast tego cofnij się do powyższego kodowania ruchu, zaczynając od standardowej pozycji otwarcia i znajdując sekwencję, która kończy się na pożądanej planszy. (Możesz spróbować wyszukiwania A * z odległością heurystyczną równą sumie odległości figur od ich ostatecznych pozycji lub coś podobnego). wiedza, umiejętności.

Trudno jest również oszacować, ile oszczędności przyniosłoby to w przypadku średniej złożoności, bez zbierania niektórych statystyk z rzeczywistego korpusu. Ale punkt wyjścia, w którym wszystkie ruchy są równie prawdopodobne, myślę, że już pokonałby większość propozycji tutaj: kodowanie arytmetyczne nie wymaga całkowitej liczby bitów na ruch.

Question 7

Atakowanie podproblemu kodowania kroków po zakodowaniu pozycji początkowej. Podejście polega na utworzeniu „połączonej listy” kroków.

Każdy krok w grze jest kodowany jako para „stara pozycja-> nowa pozycja”. Znasz początkową pozycję na początku partii szachów; przechodząc przez połączoną listę kroków, możesz dostać się do stanu po X ruchach.

Do zakodowania każdego kroku potrzebne są 64 wartości do zakodowania pozycji początkowej (6 bitów na 64 kwadraty na planszy - 8x8 kwadratów) i 6 bitów na pozycję końcową. 16 bitów na 1 ruch z każdej strony.

Ilość miejsca, jakie zajęłoby zakodowanie danej gry, jest wtedy proporcjonalna do liczby ruchów:

10 x (liczba białych ruchów + liczba czarnych) bitów.

AKTUALIZACJA: potencjalne komplikacje związane z awansowanymi pionkami. Trzeba umieć określić, do czego awansuje pionek - może wymagać specjalnych bitów (użyłby do tego szarego kodu, aby zaoszczędzić miejsce, ponieważ promocja pionka jest niezwykle rzadka).

UPDATE 2: Nie musisz kodować pełnych współrzędnych pozycji końcowej. W większości przypadków przenoszony element może przesunąć się maksymalnie do X miejsc. Na przykład pionek może mieć maksymalnie 3 opcje ruchu w dowolnym momencie. Zdając sobie sprawę z tej maksymalnej liczby ruchów dla każdego typu elementu, możemy zaoszczędzić bity na kodowaniu „celu”.

Pawn: 
   - 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
   - 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
   - Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits

Tak więc staje się przestrzenna złożoność na ruch czerni lub bieli

6 bitów na pozycję początkową + (zmienna liczba bitów w zależności od typu przenoszonej rzeczy).

Question 8

Widziałem to pytanie zeszłej nocy i zaintrygowało mnie, więc usiadłem w łóżku i wymyśliłem rozwiązania. Moja ostateczna odpowiedź jest właściwie bardzo podobna do int3.

Podstawowe rozwiązanie

Zakładając, że jest to standardowa gra w szachy i nie kodujesz reguł (tak jak białe zawsze wygrywają), możesz dużo zaoszczędzić, kodując tylko ruchy wykonywane przez każdą bierkę.

W sumie są 32 elementy, ale w każdym ruchu wiesz, jaki kolor się porusza, więc jest tylko 16 pól, o które trzeba się martwić, czyli 4 bity, które poruszają się w tej turze.

Każdy kawałek ma tylko ograniczony zestaw ruchów, który w jakiś sposób byś wyliczył.

Pion: 4 opcje, 2 bity (1 krok do przodu, 2 kroki do przodu, 1 po przekątnej)
Rook: 14 opcji, 4 bity (maksymalnie 7 w każdym kierunku)
Bishop: 13 opcji, 4 bity (jeśli masz 7 na jednej przekątnej, masz tylko 6 na drugiej)
Knight: 8 opcji, 3 bity
Dama: 27 opcji, 5 bitów (wieża + goniec)
Król: 9 opcji, 4 bity (8 jednoetapowych ruchów plus opcja roszady)

W przypadku promocji do wyboru są 4 figury (wieża, gońca, skoczka, hetmana), więc w tym ruchu dodalibyśmy 2 bity, aby to określić. Myślę, że wszystkie inne zasady są objęte automatycznie (np. En passant).

Dalsze optymalizacje

Po pierwsze, po przechwyceniu 8 elementów jednego koloru, można zmniejszyć kodowanie elementu do 3 bitów, następnie 2 bity na 4 sztuki i tak dalej.

Główną optymalizacją jest jednak wyliczenie tylko możliwych ruchów w każdym momencie gry. Załóżmy, że przechowujemy ruchy piona jako {00, 01, 10, 11}1 krok do przodu, 2 kroki do przodu, odpowiednio po skosie w lewo i po przekątnej w prawo. Jeśli niektóre ruchy nie są możliwe, możemy usunąć je z kodowania w tej turze.

Stan gry znamy na każdym etapie (z wykonania wszystkich ruchów), więc po przeczytaniu, która figura będzie się poruszać, zawsze możemy określić, ile bitów musimy odczytać. Jeśli zdamy sobie sprawę, że jedyne ruchy pionka w tym momencie to bicie po przekątnej w prawo lub ruch do przodu, wiemy, że czytamy tylko 1 bit.

Krótko mówiąc, pamięć bitów wymieniona powyżej dla każdego elementu to tylko maksimum . Prawie każdy ruch będzie miał mniej opcji i często mniej bitów.

Question 9

Na każdej pozycji uzyskaj liczbę wszystkich możliwych ruchów.

następny ruch jest generowany jako

index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves

udowodniona najlepsza wydajność miejsca do przechowywania losowo generowanej gry i średnio potrzeba około 5 bitów na ruch, ponieważ masz 30-40 możliwych ruchów. Składanie magazynu to po prostu generowanie n w odwrotnej kolejności.

Miejsce przechowywania jest trudniejsze do złamania z powodu dużej nadmiarowości. (Na pokładzie może znajdować się do 9 dam na jednym polu, ale w tym przypadku nie ma pionków, a gońcy, jeśli na planszy znajdują się na polach o przeciwnych kolorach), ale generalnie jest to jak przechowywanie kombinacji tych samych figur na pozostałych polach.)

EDYTOWAĆ:

Celem zapisywania ruchów jest przechowywanie tylko indeksu ruchu. Zamiast przechowywać Kc1-c2 i próbować zredukować te informacje, powinniśmy dodać tylko indeks ruchu wygenerowany z deterministycznego generatora ruchu (pozycja)

Przy każdym ruchu dodajemy informację o rozmiarze

num_of_moves = get_number_of_possible_moves(postion) ;

w puli i tej liczby nie można zmniejszyć

jest generowanie puli informacji

n=n*num_of_moves+ index_current_move

dodatkowy

Jeśli na pozycji końcowej dostępny jest tylko jeden ruch, zapisz jako liczbę wykonanych wcześniej ruchów wymuszonych. Przykład: jeśli pozycja początkowa ma 1 wymuszone ruchy na każdą stronę (2 ruchy) i chcemy zapisać to jako grę na jeden ruch, zapisz 1 w puli n.

przykład przechowywania w puli informacji

Załóżmy, że znamy już pozycje startowe i wykonujemy 3 ruchy.

W pierwszym ruchu jest 5 dostępnych ruchów i bierzemy indeks ruchu 4. W drugim ruchu jest 6 dostępnych ruchów i bierzemy pozycję z indeksem 3, aw trzecim jest 7 ruchów dostępnych dla tej strony i wybrał on indeks ruchu 2.

Formularz wektorowy; indeks = [4,3,2] n_moves = [5,6,7]

Kodujemy tę informację wstecz, więc n = 4 + 5 * (3 + 6 * (2)) = 79 (nie jest potrzebne mnożenie przez 7)

Jak to odpiąć? Najpierw mamy pozycję i dowiadujemy się, że dostępnych jest 5 ruchów. Więc

index=79%5=4
n=79/5=15; //no remainder

Bierzemy indeks ruchu 4 i ponownie sprawdzamy pozycję i od tego momentu dowiadujemy się, że jest 6 możliwych ruchów.

index=15%6=3
n=15/6=2

I bierzemy indeks ruchu 3, który przenosi nas na pozycję z 7 możliwymi ruchami.

index=2%7=2
n=2/7=0

Robimy ostatni ruch o indeksie 2 i dochodzimy do pozycji końcowej.

Jak widać, złożoność czasowa to O (n), a złożoność przestrzeni to O (n). Edycja: złożoność czasowa jest w rzeczywistości O (n ^ 2), ponieważ liczba, którą multiplikujesz, wzrasta, ale nie powinno być problemu z przechowywaniem gier do 10000 ruchów.

zapisywanie pozycji

Można to zrobić blisko optimum.

Kiedy dowiemy się o informacjach i przechowujemy informacje, pozwolę sobie na więcej o tym. Ogólną ideą jest zmniejszenie nadmiarowości (omówię to później). Załóżmy, że nie było awansów ani brania, więc jest 8 pionów, 2 wieże, 2 skoczki, 2 gońce, 1 król i 1 dama na stronę.

Co mamy do uratowania: 1. położenie każdego pokoju 2. możliwość roszady 3. możliwości przejścia 4. strona z możliwością ruchu

Załóżmy, że każdy element może stać wszędzie, ale nie 2 sztuki w tym samym miejscu. Liczba sposobów ułożenia 8 pionków tego samego koloru na planszy to C (64/8) (dwumian), czyli 32 bity, a następnie 2 wieże 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) i to samo dla innej witryny, ale zaczynające się od 8P -> C (48/8) i tak dalej .

Mnożąc to razem dla obu stron, otrzymujemy numer 4634726695587809641192045982323285670400000, czyli około 142 bity, musimy dodać 8 dla jednego możliwego en-passanta (pionek en-passant może znajdować się w jednym z 8 miejsc), 16 (4 bity) dla ograniczeń roszady i jeden bit dla witryny, która została przeniesiona. Otrzymujemy 142 + 3 + 4 + 1 = 150 bitów

Ale teraz przejdźmy do polowania na nadmiarowość na planszy z 32 elementami i bez brania.

zarówno czarne, jak i białe pionki są na tej samej kolumnie i zwrócone do siebie. Każdy pionek jest zwrócony w stronę innego pionka, co oznacza, że biały pionek może być najwyżej na 6 miejscu. Daje nam to 8 * C (6/2) zamiast C (64/8) * C (48/8), co zmniejsza informacje o 56 bitów.
możliwość roszady również jest zbędna. Jeśli na miejscu startu nie ma wież, nie ma możliwości wykonania roszady z tą wieżą. Więc możemy sobie wyobrazić dodanie 4 kwadratów na pokładzie, aby uzyskać dodatkowe informacje, jeśli roszada z tą wieżą jest możliwa i usunąć 4 roszady. Więc zamiast C (56/2) * C (40/2) * 16 mamy C (58/2) * C (42/2) i straciliśmy 3,76 bitów (prawie wszystkie 4 bity)
en-passant: Kiedy przechowujemy jedną z 8 możliwości en passant, znamy pozycję czarnego pionka i zmniejszamy informacyjną redindancy (jeśli jest to biały ruch i ma 3-ty pionek w przelocie, oznacza to, że czarny pion jest na c5, a biały jest albo c2, c3 lub c4), więc zamiast C (6/2) mamy 3 i straciliśmy 2,3 bitu. Zmniejszamy pewną redundancję, jeśli przechowujemy białą liczbę przelotową również po stronie, z której można to zrobić (3 możliwości -> lewa, prawa, obie) i wiemy, jaki jest pionek, który może przyjmować w przelocie. (na przykład z poprzedniego przykładu en passant z białymi czarnymi na c5 co może być w lewo, w prawo lub w obu. jeśli jest na jednym miejscu mamy 2 * 3 (3 na przechowywanie psissibilitów i 2 możliwe ruchy dla czarnego pionka na 7 lub 6 miejscu ) zamiast C (6/2) i zmniejszamy o 1,3 bita i jeśli po obu stronach zmniejszamy o 4,2 bita, w ten sposób możemy zmniejszyć o 2,3 + 1,3 = 3.
bishops: bisops może znajdować się tylko na polach opostite, co zmniejsza nadmiarowość o 1 bit dla każdego miejsca.

Jeśli podsumujemy, potrzebujemy 150-56-4-3,6-2 = 85 bitów na zapisanie pozycji szachowej, gdyby nie było taktu

I chyba niewiele więcej, jeśli uwzględniane są wpływy i promocje (ale o tym napiszę później, jeśli ktoś uzna ten długi post za przydatny)

Question 10

Większość ludzi kodowała stan tablicy, ale w odniesieniu do samych ruchów ... Oto opis kodowania bitowego.

Bity na sztukę:

Identyfikator elementu : maksymalnie 4 bity do identyfikacji 16 elementów na stronę. Można wywnioskować, że biały / czarny. Miej uporządkowanie zdefiniowane na elementach. Ponieważ liczba sztuk spada poniżej odpowiednich potęg dwóch, użyj mniejszej liczby bitów do opisania pozostałych elementów.
Pion: 3 możliwości w pierwszym ruchu, więc +2 bity (do przodu o jedno lub dwa pola, en passant). Kolejne ruchy nie pozwalają na ruch do przodu o dwa, więc wystarczy +1 bit. Awans można wywnioskować w procesie dekodowania, odnotowując, kiedy pionek osiągnął ostatnią pozycję. Jeśli wiadomo, że pionek jest promowany, dekoder będzie oczekiwał kolejnych 2 bitów wskazujących, do której z 4 głównych figur został awansowany.
Bishop: +1 bit na przekątną, do +4 bitów na odległość wzdłuż przekątnej (16 możliwości). Dekoder może określić maksymalną możliwą odległość, na jaką element może się przesunąć wzdłuż tej przekątnej, więc jeśli jest to krótsza przekątna, użyj mniej bitów.
Skoczek: 8 możliwych ruchów, +3 bity
Rook: +1 bit dla poziomu / pionu, +4 bity dla odległości wzdłuż linii.
Król: 8 możliwych ruchów, +3 bity. Wskaż roszadę ruchem „niemożliwym” - ponieważ roszada jest możliwa tylko wtedy, gdy król jest na pierwszym rzędzie, zakoduj ten ruch z poleceniem przesunięcia króla „do tyłu” - tj. Poza szachownicę.
Królowa: 8 możliwych kierunków, + 3 bity. Do +4 więcej bitów na odległość wzdłuż linii / po przekątnej (mniej, jeśli przekątna jest krótsza, jak w przypadku biskupa)

Zakładając, że na szachownicy znajdują się wszystkie figury, są to bity na ruch: Pion - 6 bitów w pierwszym ruchu, 5 kolejnych. 7 w przypadku awansu. Gońca: 9 bitów (maks.), Skoczek: 7, Wieża: 9, Król: 7, Dama: 11 (maks.).

Question 11

Czy problemem jest podanie kodowania, które jest najbardziej wydajne dla typowych partii szachów, czy też takie, które ma najkrótsze kodowanie w najgorszym przypadku?

W tym drugim przypadku najbardziej efektywny sposób jest również najbardziej nieprzejrzysty: utwórz wyliczenie wszystkich możliwych par (plansza początkowa, legalna sekwencja ruchów), które z ciągiem na trzykrotnie powtórzonej pozycji i nie więcej niż Pięćdziesiąt ruchów od czasu ostatniego ruchu pionka lub zbicia, jest rekurencyjne. Następnie indeks pozycji w tej skończonej sekwencji daje najkrótsze kodowanie w najgorszym przypadku, ale także i równie długie kodowanie dla typowych przypadków i jest, jak sądzę, bardzo kosztowne do obliczenia. Najdłuższa możliwa gra w szachy powinna obejmować ponad 5000 ruchów, przy czym zwykle dla każdego gracza dostępnych jest 20-30 ruchów w każdej pozycji (choć mniej, gdy pozostało kilka pionków) - daje to około 40000 bitów potrzebnych do tego kodowania.

Pomysł wyliczenia można zastosować, aby uzyskać łatwiejsze do wykonania rozwiązanie, jak opisano w sugestii Henka Holtermana dotyczącej kodowania ruchów powyżej. Moja sugestia: nie minimalna, ale krótsza niż w przykładach powyżej, które oglądałem i rozsądna do zastosowania:

64 bity określające, które pola są zajęte (macierz zajętości) oraz lista figur, które znajdują się w każdym zajętym kwadracie (może mieć 3 bity dla pionków i 4 bity dla innych figur): daje to 190 bitów na pozycję początkową. Ponieważ na pokładzie nie może być więcej niż 32 elementy, kodowanie macierzy zajętości jest nadmiarowe, więc można zakodować coś w rodzaju typowych pozycji na płycie, powiedzmy jako 33 ustawione bity plus indeks tablicy z listy wspólnych płyt.
1 trochę, aby powiedzieć, kto wykona pierwszy ruch
Ruchy kodu zgodnie z sugestią Henka: zazwyczaj 10 bitów na parę białych / czarnych ruchów, chociaż niektóre ruchy zajmują 0 bitów, gdy gracz nie ma alternatywnych ruchów.

Sugeruje to 490 bitów do zakodowania typowej gry w 30 ruchów i byłoby to dość wydajną reprezentacją dla typowych gier.

Wbrew zasadom kodowania remisu po trzykrotnym powtórzeniu pozycji i nie więcej niż pięćdziesięciu ruchów od ostatniego ruchu pionka lub zbicia: jeśli zakodujesz poprzednie ruchy z powrotem do ostatniego ruchu lub bicia pionka, masz wystarczająco dużo informacji, aby zdecydować, czy te zasady mają zastosowanie: nie ma potrzeby całej historii gry.

Question 12

Pozycję na karcie można zdefiniować w 7 bitach (0-63 i 1 wartość określająca, że nie ma jej już na karcie). Dlatego dla każdego elementu na planszy określ, gdzie się on znajduje.

32 sztuki * 7 bitów = 224 bity

EDYCJA: jak zauważył Cadrian ... mamy również przypadek „awansowanego pionka na hetmana”. Proponuję dodać dodatkowe bity na końcu, aby wskazać, który pionek został awansowany.

Tak więc dla każdego promowanego pionka podążamy za 224 bitami z 5 bitami, które wskazują indeks pionka, który był promowany i 11111, jeśli jest to koniec listy.

Tak więc minimalny przypadek (brak promocji) to 224 bity + 5 (brak promocji). Za każdego promowanego pionka dodaj 5 bitów.

EDYCJA: Jak wskazuje kudłaty żaba, na końcu potrzebujemy jeszcze jednego kawałka, aby wskazać, czyja kolej; ^)

Question 13

Użyłbym kodowania długości serii. Niektóre kawałki są unikalne (lub istnieją tylko dwa razy), więc mogę pominąć długość po nich. Podobnie jak cletus, potrzebuję 13 unikalnych stanów, więc mogę użyć półbajtu (4 bity) do zakodowania elementu. Początkowa tablica wyglądałaby wtedy następująco:

White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook

co daje mi 8 + 2 + 4 + 2 + 8 przekąsek = 24 przekąski = 96 bitów. Nie mogę zakodować 16 za pomocą skubania, ale ponieważ „Empty, 0” nie ma sensu, mogę traktować „0” jako „16”.

Jeśli szachownica jest pusta, ale dla jednego pionka w lewym górnym rogu, otrzymuję „Pion, 1, Pusty, 16, Pusty, 16, Pusty 16, Pusty, 15” = 10 przekąsek = 40 bitów.

W najgorszym przypadku mam pusty kwadrat między każdym kawałkiem. Ale do zakodowania fragmentu potrzebuję tylko 13 z 16 wartości, więc może mogę użyć innej, aby powiedzieć „Empty1”. Następnie potrzebuję 64 półbajtów == 128 bitów.

Do ruchów potrzebuję 3 bity na kawałek (kolor wynika z faktu, że biały zawsze porusza się jako pierwszy) plus 5 bitów (0..63) dla nowej pozycji = jeden bajt na ruch. W większości przypadków nie potrzebuję starej pozycji, ponieważ w zasięgu będzie tylko jedna figura. W nieparzystym przypadku muszę użyć pojedynczego nieużywanego kodu (potrzebuję tylko 7 kodów do zakodowania elementu), a następnie 5 bitów dla starej i 5 bitów dla nowej pozycji.

To pozwala mi zakodować roszadę w 13 kęsach (mogę przesunąć króla w stronę wieży, co wystarczy, by powiedzieć, co zamierzam).

[EDYCJA] Jeśli zezwalasz na inteligentny koder, potrzebuję 0 bitów do początkowej konfiguracji (ponieważ nie musi być w żaden sposób kodowany: jest statyczny) plus jeden bajt na ruch.

[EDIT2] Co pozostawia transformację pionka. Jeśli pionek dotrze do ostatniego rzędu, mogę go przesunąć w miejscu, aby powiedzieć „przekształca”, a następnie dodać 3 bity za figurę, którą jest zastępowany (nie musisz używać hetmana; możesz zastąpićpiona czymkolwiek ale Król).

Question 14

Tak jak kodują gry na książkach i papierach: każdy element ma symbol; ponieważ jest to gra „legalna”, białe ruszają się jako pierwsze - nie ma potrzeby oddzielnego kodowania białych lub czarnych, wystarczy policzyć ruchy, aby określić, kto się poruszył. Ponadto każdy ruch jest kodowany jako (figura, pozycja końcowa), gdzie `` pozycja końcowa '' jest zredukowana do najmniejszej liczby symboli, która pozwala dostrzec niejednoznaczności (może wynosić zero). Długość gry determinuje liczbę ruchów. Na każdym kroku można również zakodować czas w minutach (od ostatniego ruchu).

Kodowanie utworu można wykonać albo przez przypisanie każdemu symbolowi (łącznie 32), albo przez przypisanie symbolu do klasy i wykorzystanie pozycji końcowej do zrozumienia, który element został przeniesiony. Na przykład pionek ma 6 możliwych pozycji końcowych; ale średnio tylko kilka jest dostępnych na każdym kroku. Zatem statystycznie kodowanie według pozycji końcowej może być najlepsze w tym scenariuszu.

Podobne kodowania są używane dla zestawów spajków w neuronauce obliczeniowej (AER).

Wady: musisz ponownie rozegrać całą grę, aby uzyskać aktualny stan i wygenerować podzestaw, podobnie jak przeglądanie połączonej listy.

Question 15

Istnieje 64 możliwych pozycji na tablicy, więc potrzebujesz 6 bitów na pozycję. Mamy 32 początkowe elementy, więc na razie mamy łącznie 192 bity, gdzie każde 6 bitów wskazuje położenie danego elementu. Możemy z góry określić kolejność, w jakiej pojawiają się elementy, więc nie musimy mówić, która jest która.

Co jeśli bierka wypadnie z planszy? Cóż, możemy umieścić bierkę w tym samym miejscu, co inny element, aby zaznaczyć, że jest poza szachownicą, ponieważ w przeciwnym razie byłoby to nielegalne. Ale nie wiemy też, czy pierwsza figura znajdzie się na planszy, czy nie. Więc dodajemy 5 bitów wskazujących, który kawałek jest pierwszy (32 możliwości = 5 bitów reprezentujących pierwszy kawałek). Następnie możemy wykorzystać to miejsce na kolejne figury spoza planszy. To prowadzi nas do łącznie 197 bitów. Na planszy musi znajdować się co najmniej jeden element, żeby to zadziałało.

Wtedy potrzebujemy jednego bitu, na którego kolejkę - prowadzi nas do 198 bitów .

A co z promocją piona? Możemy to zrobić źle, dodając 3 bity na piona, dodając 42 bity. Ale wtedy możemy zauważyć, że przez większość czasu pionki nie są promowane.

Zatem dla każdego pionka znajdującego się na szachownicy bit „0” oznacza, że nie uzyskał promocji. Jeśli na szachownicy nie ma pionka, nie potrzebujemy go wcale. Następnie możemy użyć ciągów bitów o zmiennej długości, dla których ma promocję. Najczęściej będzie to królowa, więc „10” może oznaczać QUEEN. Wtedy „110” oznacza wieżę, „1110” oznacza gońca, a „1111” oznacza skoczka.

Stan początkowy zajmie 198 + 16 = 214 bitów , ponieważ wszystkie 16 pionków jest na szachownicy i nie jest promowane. Gra końcowa z dwoma promowanymi pionkami-królowymi może zająć około 198 + 4 + 4, co oznacza 4 żywe pionki bez promocji i 2 pionki hetmanów, co daje łącznie 206 bitów . Wydaje się całkiem solidny!

===

Kodowanie Huffmana, jak zauważyli inni, będzie następnym krokiem. Jeśli obserwujesz kilka milionów gier, zauważysz, że każdy element jest znacznie bardziej prawdopodobny na określonych polach. Na przykład, przez większość czasu pionki pozostają w linii prostej lub jeden w lewo / jeden w prawo. Król zwykle trzyma się bazy domowej.

Dlatego opracuj schemat kodowania Huffmana dla każdej oddzielnej pozycji. Pionki prawdopodobnie przyjmą średnio tylko 3-4 bity zamiast 6. Król powinien również wziąć kilka bitów.

Również w tym schemacie uwzględnij „zajęte” jako możliwą pozycję. Może to również bardzo solidnie poradzić sobie z roszadą - każda wieża i król będą miały dodatkową "pierwotną pozycję, przeniesioną". Możesz także zakodować en passant w pionkach w ten sposób - "oryginalna pozycja, może en passant".

Przy wystarczającej ilości danych takie podejście powinno przynieść naprawdę dobre wyniki.

Question 16

Spróbowałbym użyć kodowania Huffmana . Teoria, która się za tym kryje, jest taka - w każdej grze w szachy będzie kilka pionów, które będą się często poruszać, a niektóre nie będą się poruszać zbytnio lub zostaną wyeliminowane wcześnie. Jeśli pozycja wyjściowa ma już usunięte niektóre elementy - tym lepiej. To samo dotyczy kwadratów - niektóre kwadraty widzą całą akcję, a inne nie są zbytnio dotykane.

Miałbym więc dwa stoły Huffmana - jeden na figury, drugi na kwadraty. Zostaną wygenerowane na podstawie rzeczywistej gry. Mógłbym mieć jeden duży stół na każdą parę kawałek-kwadrat, ale myślę, że byłoby to dość nieefektywne, ponieważ nie ma wielu przypadków tego samego kawałka poruszającego się ponownie po tym samym polu.

Każdy kawałek miałby przypisany identyfikator. Ponieważ są 32 różne elementy, potrzebowałbym tylko 5 bitów na identyfikator elementu. Identyfikatory figur nie zmieniają się z gry na grę. To samo dotyczy kwadratowych identyfikatorów, do których potrzebowałbym 6 bitów.

Drzewa Huffmana byłyby kodowane przez zapisywanie każdego węzła w dół, gdy są one przemierzane w kolejności (to znaczy, najpierw wyprowadzany jest węzeł, a następnie jego dzieci od lewej do prawej). Dla każdego węzła będzie jeden bit określający, czy jest to węzeł liścia, czy węzeł gałęzi. Jeśli jest to węzeł liścia, będą po nim bity dające identyfikator.

Pozycja początkowa będzie po prostu określona przez serię par kawałek-lokalizacja. Potem będzie jedna para kawałek-lokalizacja na każdy ruch. Możesz znaleźć koniec deskryptora pozycji początkowej (i początek deskryptora ruchów), po prostu znajdując pierwszy element, który jest wymieniony dwukrotnie. W przypadku awansu pionka będą 2 dodatkowe bity określające, czym się stanie, ale ID figury nie ulegnie zmianie.

Aby uwzględnić możliwość promowania pionka na początku gry, między drzewami huffmanów a danymi będzie również „tabela awansów”. Na początku będą 4 bity określające, ile pionków zostanie ulepszonych. Następnie dla każdego pionka będzie miał swój zakodowany identyfikator i 2 bity określające, czym się stał.

Drzewa huffmanów zostaną wygenerowane z uwzględnieniem wszystkich danych (zarówno pozycji startowej, jak i ruchów) oraz tabeli awansów. Chociaż zwykle tabela promocji jest pusta lub zawiera tylko kilka wpisów.

Podsumowując graficznie:

<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)

<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>

<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>

<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>

<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)

Dodano: nadal można to zoptymalizować. Każda figura ma tylko kilka legalnych ruchów. Zamiast po prostu zakodować kwadrat docelowy, można by podać ID w oparciu o 0 dla możliwych ruchów każdej figury. Te same identyfikatory byłyby używane ponownie dla każdej figury, więc w sumie nie byłoby więcej niż 21 różnych identyfikatorów (hetman może mieć maksymalnie 21 różnych możliwych opcji ruchu). Umieść to w tabeli Huffman zamiast pól.

Stanowiłoby to jednak trudność w przedstawieniu stanu pierwotnego. Można wygenerować serię ruchów, aby umieścić każdy element na swoim miejscu. W takim przypadku należałoby jakoś zaznaczyć koniec stanu początkowego i początek ruchów.

Alternatywnie można je umieścić przy użyciu nieskompresowanych 6-bitowych kwadratowych identyfikatorów.

Czy oznaczałoby to ogólny spadek rozmiaru - nie wiem. Prawdopodobnie, ale powinien trochę poeksperymentować.

Dodano 2: Jeszcze jeden przypadek specjalny. Jeśli stan gry NIE ma ruchów, ważne staje się rozróżnienie, kto ruszy dalej. Na koniec dodaj jeszcze jeden kawałek. :)

Question 17

[zredagowane po poprawnym przeczytaniu pytania] Jeśli przyjmiesz, że każde stanowisko prawne można osiągnąć z pozycji wyjściowej (co jest możliwą definicją „legalnego”), wówczas dowolną pozycję można wyrazić jako sekwencję ruchów od początku. Fragment gry rozpoczynający się z niestandardowej pozycji można wyrazić jako sekwencję ruchów potrzebnych do dotarcia na start, włącznik włączający kamerę, a następnie kolejne ruchy.

Nazwijmy więc początkowy stan płyty pojedynczym bitem „0”.

Ruchy z dowolnej pozycji można wyliczyć, numerując pola i porządkując ruchy według (początek, koniec), przy czym konwencjonalny skok o 2 pola wskazuje na roszadę. Nie ma potrzeby kodowania nielegalnych ruchów, ponieważ pozycja szachownicy i zasady są zawsze znane. Flaga, która włącza kamerę, może być wyrażona jako specjalny ruch w paśmie lub, bardziej sensownie, jako numer ruchu poza pasmem.

Dla każdej strony dostępne są 24 ruchy otwierające, z których każdy może pomieścić 5 bitów. Kolejne ruchy mogą wymagać więcej lub mniej bitów, ale legalne ruchy są zawsze policzalne, więc szerokość każdego ruchu może szczęśliwie rosnąć lub rozszerzać się. Nie obliczyłem, ale wyobrażam sobie, że pozycje 7-bitowe byłyby rzadkie.

Korzystając z tego systemu, można zakodować 100 pół-ruchu w około 500 bitach. Jednak mądrze byłoby skorzystać z książki otwierającej. Załóżmy, że zawiera milion sekwencji. Niech więc początkowe 0 oznacza początek od standardowej tablicy, a 1, po którym następuje 20-bitowa liczba, oznacza początek tej sekwencji otwierania. Gry z nieco konwencjonalnymi otwarciami można skrócić o, powiedzmy, 20 pół-ruchów lub 100 bitów.

Nie jest to największa możliwa kompresja, ale (bez książki otwierającej) byłaby bardzo łatwa do wykonania, gdybyś miał już model szachowy, który zakłada pytanie.

Aby bardziej skompresować, chciałbyś uporządkować ruchy według prawdopodobieństwa, a nie w dowolnej kolejności i zakodować prawdopodobne sekwencje w mniejszej liczbie bitów (używając np. Tokenów Huffmana, jak wspominali ludzie).

Question 18

Jeśli czas obliczeniowy nie jest problemem, można użyć deterministycznego generatora możliwych pozycji, aby przypisać unikalne identyfikatory do danej pozycji.

Z danej pozycji najpierw wygeneruj liczbę możliwych pozycji w deterministycznym dworze, np. Zaczynając od dołu po lewej, przechodząc do prawego górnego. To określa, ile bitów będziesz potrzebować do następnego ruchu, w niektórych sytuacjach może to być tylko jeden. Następnie po wykonaniu przeniesienia zapisz tylko unikalny identyfikator tego ruchu.

Awans i inne zasady liczą się jako prawidłowe posunięcia, o ile są rozpatrywane w sposób deterministyczny, np. Na hetmana, na wieżę, na gońca, każdy liczy się jako osobny ruch.

Początkowa pozycja jest najtrudniejsza i może wygenerować około 250 milionów możliwych pozycji (myślę), co wymagałoby około 28 bitów plus dodatkowy bit, aby określić, czyj to ruch.

Zakładając, że wiemy, kto to jest obrót (każdy obrót zmienia się z białego na czarny), deterministyczny generator wyglądałby mniej więcej tak:

for each row
    for each column
        add to list ( get list of possible moves( current piece, players turn) )

'pobierz listę możliwych ruchów' zrobiłoby coś takiego:

if current piece is not null 
    if current piece color is the same as the players turn
        switch( current piece type )
            king - return list of possible king moves( current piece )
            queen - return list of possible queen moves( current piece )
            rook - return list of possible rook moves( current piece )
            etc.

Jeśli król jest szachowany, wtedy każda „lista możliwych ruchów xxx” zwraca tylko prawidłowe ruchy, które zmieniają sytuację czekową.

Question 19

W większości odpowiedzi pominięto 3-krotne powtórzenie. niestety dla 3-krotnego powtórzenia musisz zapisać wszystkie rozegrane pozycje ...

Pytanie wymagało od nas przechowywania w sposób efektywny przestrzennie, więc naprawdę nie musimy przechowywać pozycji, o ile możemy ją skonstruować z listy ruchów (pod warunkiem, że mamy standardową pozycję początkową). Możemy zoptymalizować PGN i to wszystko. Bellow to prosty schemat.

Na planszy jest 64 kwadraty, 64 = 2 ^ 6. Jeśli zapiszemy tylko początkowy i końcowy kwadrat każdego ruchu, który zajmie 12 bitów (promocja zostanie omówiona później). Zauważ, że ten schemat obejmuje już ruch gracza, empatię, przechwycenie piona, roszadę itp. ponieważ z nich można zbudować po prostu odtworzyć listę ruchów.

do promocji możemy zachować oddzielną tablicę wektorów, które będą brzmiały „w ruchu N promuj do elementu XYZ”. możemy zachować wektor (int, byte).

Kuszące jest również optymalizowanie wektorów (do, od), ponieważ wiele z tych wektorów (do, od) nie jest możliwych w szachach. na przykład. nie będzie ruchu z e1 do d8 itd. Ale nie mogłem wymyślić żadnego schematu. Wszelkie dalsze pomysły są mile widziane.

Question 20

Długo o tym myślałem (+ - 2 godziny). I nie ma oczywistych odpowiedzi.

Zarozumiały:

Ignorowanie stanu czasu (gracz nie miał limitu czasu, więc mógł wymusić remis, nie grając)
Kiedy rozegrano mecz?!? Jest to ważne, ponieważ zasady zmieniły się z biegiem czasu (tak będzie zakładać nowoczesną grę w późniejszym etapie nowoczesnej gry ...) Proszę odnieść się na przykład do reguły martwego pionka (wikipedia ma bardzo znany problem z jej pokazaniem), a jeśli chcesz aby cofnąć się w czasie, powodzenia, biskup poruszał się tylko powoli, a kiedyś używano kości. lol.

... tak więc aktualne są nowoczesne zasady. Po pierwsze niezależnie od powtórzeń i przesuń limit powtórzeń.

-C 25 bajtów zaokrąglone (64b + 32 * 4b + 5b = 325b)

= 64 bity (coś / nic) + 32 * 4 bity [1 bit = kolor {czarny / witka} + 3 bity = rodzaj figury {król, królowa, goniec, kNight, Rook, Pawn, MovedPawn} Uwaga: przesunięty pionek ... np. jeśli był to ostatni poruszony pionek w poprzedniej turze, co oznacza, że przejście „en passant” jest możliwe. ] + 5 bitów za stan faktyczny (kto się obraca, w przelocie, możliwość rookingu lub nie z każdej strony)

Na razie w porządku. Prawdopodobnie można go ulepszyć, ale wtedy należałoby wziąć pod uwagę zmienną długość i promocję !?

Teraz poniższe zasady obowiązują tylko wtedy, gdy gracz zgłosi się do remisu, NIE JEST to automatycznie! Rozważ więc, że te 90 ruchów bez bicia lub ruchu pionka jest wykonalne, jeśli żaden gracz nie zażąda remisu! Oznacza to, że wszystkie ruchy muszą być rejestrowane ... i dostępne.

-D powtórzenie pozycji ... np. Stan szachownicy, jak wspomniano powyżej (patrz C) lub nie ... (patrz poniżej dotyczące zasad FIDE) -E Pozostawia to złożony problem z dopuszczeniem do ruchu 50 bez bicia lub ruchu pionka. licznik jest konieczny ... Jednak.

Więc jak sobie z tym radzisz? ... Cóż, naprawdę nie ma sposobu. Ponieważ żaden z graczy nie może chcieć rysować ani zdawać sobie sprawy, że to się stało. Teraz, w przypadku E, licznik może wystarczyć ... ale tutaj jest sztuczka i nawet czytając zasady FIDE (http://www.fide.com/component/handbook/?id=124&view=article) nie mogę znaleźć odpowiedź ... a co z utratą umiejętności rookingu. Czy to powtórzenie? Myślę, że nie, ale jest to niewyraźny temat, nie poruszony, nie wyjaśniony.

Więc oto dwie reguły, które są dwiema złożonymi lub nieokreślonymi nawet próbami zakodowania ... Na zdrowie.

Tak więc jedynym sposobem na prawdziwe zakodowanie gry jest nagranie wszystkiego od początku ... co powoduje konflikt (lub nie?) Z pytaniem o „stan planszy”.

Mam nadzieję, że ta pomoc ... nie za dużo matematyki :-) Tylko po to, żeby pokazać, że niektóre pytania nie są tak łatwe, zbyt otwarte na interpretację lub wstępną wiedzę, aby były poprawne i skuteczne. Żaden z nich nie wziąłbym pod uwagę podczas rozmowy kwalifikacyjnej, ponieważ otwiera za dużo puszki robaka.

Question 21

Możliwa poprawa pozycji wyjściowej w rozwiązaniu Yacoby'ego

Żadna legalna pozycja nie ma więcej niż 16 sztuk każdego koloru. Liczba sposobów umieszczenia do 16 czarnych i 16 białych pionów na 64 polach to około 3.63e27. Log2 (3,63e27) = 91,55. Oznacza to, że możesz zakodować położenie i kolor wszystkich elementów w 92 bitach. To mniej niż 64 bity dla pozycji + do 32 bitów dla koloru, których wymaga rozwiązanie Yacoby. W najgorszym przypadku można zaoszczędzić 4 bity kosztem znacznej złożoności kodowania.

Z drugiej strony zwiększa rozmiar w przypadku pozycji, w których brakuje 5 lub więcej elementów. Te pozycje stanowią tylko <4% wszystkich pozycji, ale to prawdopodobnie większość przypadków, w których chcesz zarejestrować pozycję początkową inną niż początkowa.

Prowadzi to do kompletnego rozwiązania

Zakoduj położenie i kolor elementów zgodnie z powyższą metodą. 92 bity .
Aby określić rodzaj każdej figury, użyj kodu Huffmana: pionek: „0”, wieża: „100”, skoczek: „101”, goniec: „110”, hetman: „1110”, król: „1111”. Wymaga to (16 * 1 + 12 * 3 + 4 * 4) = 68 bitów na pełny zestaw elementów. Pełną pozycję płyty można zakodować w 92 + 68 = maksymalnie 160 bitów .
Należy dodać dodatkowy stan gry: turn: 1 bit, która roszada jest możliwa: 4 bity, możliwe „en passant”: do 4 bitów (1 bit mówi, że tak jest, a 3 bity określają, który). Pozycja początkowa jest zakodowana w = 160 + 9 = 169 bitów
Aby uzyskać listę ruchów, wylicz wszystkie możliwe ruchy dla danej pozycji i zapisz pozycję ruchu na liście. Lista ruchów obejmuje wszystkie szczególne przypadki (roszada, przelotny i rezygnacja). Użyj tylko tyle bitów, ile potrzeba, aby zapisać najwyższą pozycję. Średnio nie powinien przekraczać 7 bitów na ruch (średnio 16 możliwych figur i 8 legalnych ruchów na sztukę). W niektórych przypadkach wymuszony ruch wymaga tylko 1 bitu (ruch lub rezygnacja).

Question 22

Na planszy są 32 piony. Każdy element ma pozycję (jedna na 64 kwadraty). Potrzebujesz więc tylko 32 dodatnich liczb całkowitych.

Wiem, że 64 pozycje są trzymane w 6 bitach, ale nie zrobiłbym tego. Zatrzymałbym ostatnie bity za kilka flag (upuszczona figura, pionek królowej)

Question 23

Cletus odpowiedział dobrze, ale zapomniał również zaszyfrować, czyja kolej. Jest częścią obecnego stanu i jest niezbędna, jeśli używasz tego stanu do sterowania algorytmem wyszukiwania (jak pochodna alfa-beta).

Nie jestem szachistą, ale wydaje mi się, że jest jeszcze jeden przypadek narożny: ile ruchów zostało powtórzonych. Gdy każdy gracz wykona ten sam ruch trzy razy, gra kończy się remisem, prawda? Jeśli tak, to musisz zapisać te informacje w stanie, ponieważ po trzecim powtórzeniu stan jest teraz terminalem.

Question 24

Jak kilku innych wspomniało, możesz dla każdego z 32 elementów, które możesz zapisać, na którym kwadracie się znajduje i czy są na planszy, czy nie, daje to 32 * (log2 (64) + 1) = 224 bity.

Jednak biskupi mogą zajmować tylko czarne lub białe kwadraty, więc do tego potrzebujesz tylko log2 (32) bitów na pozycję, co daje 28 * 7 + 4 * 6 = 220 bitów.

A ponieważ pionki nie zaczynają z tyłu i mogą poruszać się tylko do przodu, mogą mieć tylko 56, powinno być możliwe użycie tego ograniczenia do zmniejszenia liczby bitów potrzebnych dla pionków.

Question 25

Tablica ma 64 kwadraty i może być reprezentowana przez 64 bity wskazujące, czy kwadrat jest pusty, czy nie. Potrzebujemy informacji o kawałkach tylko wtedy, gdy kwadrat ma figurę. Ponieważ gracz + element zajmuje 4 bity (jak pokazano wcześniej), możemy uzyskać aktualny stan w 64 + 4 * 32 = 192 bity. Rzuć w bieżącej turze i masz 193 bity.

Musimy jednak również zakodować legalne posunięcia dla każdej figury. Najpierw obliczamy liczbę prawidłowych ruchów dla każdej figury i dodajemy tę liczbę bitów po identyfikatorze figury pełnego kwadratu. Obliczyłem następująco:

Pion: Naprzód, pierwszy obrót o dwa do przodu, w pasie * 2, promocja = 7 bitów. Możesz połączyć pierwszy obrót naprzód i awans w jeden bit, ponieważ nie mogą nastąpić z tej samej pozycji, więc masz 6. Wieża: 7 pionowych kwadratów, 7 poziomych kwadratów = 14 bitów Skoczek: 8 pól = 8 bitów Biskup: 2 przekątne * 7 = 14 bitów Królowa: 7 pionowych, 7 poziomych, 7 przekątnych, 7 przekątnych = 28 bitów Król: 8 otaczających kwadratów

To nadal oznacza, że musiałbyś zmapować docelowe kwadraty na podstawie bieżącej pozycji, ale to (powinno być) proste obliczenie.

Ponieważ mamy 16 pionów, 4 wieże / skoczków / gońców i 2 hetmany / królów, to jest 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 więcej bitów, co daje łącznie do 505 bitów.

Jeśli chodzi o liczbę bitów wymaganych na sztukę dla możliwych ruchów, można dodać do tego pewne optymalizacje i prawdopodobnie zmniejszyć liczbę bitów, po prostu użyłem łatwych liczb do pracy. Na przykład w przypadku przesuwanych elementów można zapisać, jak daleko mogą się przesunąć, ale wymagałoby to dodatkowych obliczeń.

Krótko mówiąc: przechowuj dodatkowe dane (figury itp.) Tylko wtedy, gdy kwadrat jest zajęty i przechowuj tylko minimalną liczbę bitów dla każdej figury, aby przedstawić jej legalne ruchy.

EDIT1: Zapomniałem o roszadzie i promocji pionka na jakąkolwiek figurę. Mogłoby to przynieść sumę z wyraźnymi pozycjami do 557 ruchów (3 więcej bitów dla pionków, 2 dla królów)

Question 26

Każda figura może być reprezentowana przez 4 bity (pionek do króla, 6 typów), kolor czarny / biały = 12 wartości

Każdy kwadrat na planszy może być reprezentowany przez 6 bitów (x koordynacja, y koordynator).

Pozycje początkowe wymagają maksymalnie 320 bitów (32 sztuki, 4 + 6 bitów)

Każdy kolejny ruch może być reprezentowany przez 16 bitów (od pozycji do pozycji, kawałek).

Roszada wymagałaby dodatkowych 16 bitów, ponieważ jest to podwójny ruch.

Pionki w królowej mogą być reprezentowane przez jedną z 4 wolnych wartości z 4 bitów.

Bez wykonywania szczegółowych obliczeń matematycznych zaczyna to oszczędzać miejsce po pierwszym ruchu w porównaniu z przechowywaniem 32 * 7 bitów (predefiniowana tablica elementów) lub 64 * 4 bitów (predefiniowane przypisanie kwadratów)

Po 10 ruchach w obie strony maksymalna wymagana przestrzeń wynosi 640 bitów

... ale z drugiej strony, jeśli zidentyfikujemy każdą figurę unikatowo (5 bitów) i dodamy szósty bit do oznaczania pionków w hetmie, wtedy potrzebujemy tylko id figury + pozycja dla każdego ruchu. Spowoduje to zmianę obliczeń na ...

Pozycje początkowe = maks. 384 bity (32 sztuki, 6 + 6 bitów) Każdy ruch = 12 bitów (do pozycji, id elementu)

Następnie po 10 ruchach z każdej strony maksymalna wymagana przestrzeń wynosi 624 bity

Question 27

Podobnie jak Robert G, zwykle używałbym PGN, ponieważ jest to standard i może być używane przez szeroką gamę narzędzi.

Jeśli jednak gram w szachy AI na odległej sondzie kosmicznej, a więc każdy kawałek jest cenny, to właśnie bym zrobił dla ruchów. Później przejdę do kodowania stanu początkowego.

Ruchy nie muszą rejestrować stanu; dekoder może śledzić stan, a także jakie ruchy są legalne w danym momencie. Wszystkie ruchy, które należy zarejestrować, to wybrana z różnych alternatyw prawnych. Ponieważ gracze zmieniają się, ruch nie musi rejestrować koloru gracza. Ponieważ gracz może przesuwać tylko własne kolorowe elementy, pierwszym wyborem jest to, który element porusza (wrócę do alternatywy, która używa innego wyboru później). Przy maksymalnie 16 elementach wymaga to maksymalnie 4 bitów. Gdy gracz traci elementy, liczba wyborów maleje. Ponadto określony stan gry może ograniczać wybór pionków. Jeśli król nie może się poruszyć bez szachowania, liczba wyborów zmniejsza się o jeden. Jeśli król jest szachowany, każda figura, która nie może wyprowadzić króla z szachowania, nie jest dobrym wyborem.

Gdy element zostanie określony, będzie miał tylko określoną liczbę legalnych miejsc docelowych. Dokładna liczba zależy w dużym stopniu od układu planszy i historii gry, ale możemy obliczyć pewne maksima i oczekiwane wartości. Dla wszystkich oprócz skoczka i podczas roszady bierka nie może przejść przez inną bierkę. Będzie to duże źródło ograniczeń ruchu, ale trudno to oszacować. Kawałek nie może zejść z planszy, co również znacznie ograniczy liczbę miejsc docelowych.

Kodujemy przeznaczenie większości elementów numerując kwadraty wzdłuż linii w następującej kolejności: W, NW, N, NE (czarna strona to N). Linia zaczyna się na kwadracie najdalej położonym w danym kierunku, do którego można się poruszać, i biegnie w kierunku. W przypadku nieobciążonego króla lista ruchów to W, E, NW, SE, N, S, NE, SW. W przypadku skoczka zaczynamy od 2W1N i postępujemy zgodnie z ruchem wskazówek zegara; miejsce docelowe 0 jest pierwszym prawidłowym miejscem docelowym w tej kolejności.

Pionki: niewzruszony pionek ma 2 miejsca przeznaczenia, więc wymaga 1 bitu. Jeśli pionek może zbić innego, normalnie lub w przelocie (co dekoder może określić, ponieważ śledzi stan), ma również 2 lub 3 ruchy do wyboru. Poza tym pionek może mieć tylko 1 wybór, nie wymagający żadnych bitów. Kiedy pionek jest na siódmym ^miejscu , decydujemy się również na awans. Ponieważ pionki są zwykle promowane do królowych, a następnie rycerzy, kodujemy wybory następująco:
- królowa: 0
- rycerz: 10
- biskup: 110
- wieża: 111
Bishop: co najwyżej 13 miejsc docelowych, gdy w {d, e} {4,5} dla 4 bitów.
Rook: co najwyżej 14 miejsc docelowych, 4 bity.
Rycerze: maksymalnie 8 miejsc docelowych, 3 bity.
Królowie: kiedy roszada jest opcją, król wraca do S i nie może poruszać się w dół; daje to łącznie 7 miejsc docelowych. W pozostałym czasie król ma co najwyżej 8 ruchów, co daje maksymalnie 3 bity.
Królowa: To samo co wybory dla gońca lub wieży, łącznie 27 wyborów, czyli 5 bitów

Ponieważ liczba wyborów nie zawsze jest potęgą dwóch, powyższe nadal powoduje marnowanie bitów. Załóżmy, że wybór jest C , a zwłaszcza wybór jest numerowany C , a n = ceil (lg ( C )) (liczba bitów do kodowania wymagane do wyboru). Używamy tych zmarnowanych wartości, badając pierwszy bit następnego wyboru. Jeśli jest 0, nic nie rób. Jeśli jest to 1 ic + C <2 ⁿ , dodaj C do c . Dekodowanie liczby odwraca to: jeśli otrzymano c > = C , odejmij C i ustaw pierwszy bit następnej liczby na 1. Jeśli c<2 ⁿ - C , następnie ustaw pierwszy bit następnej liczby na 0. Jeśli 2 ⁿ - C <= c < C , to nic nie rób. Nazwij ten schemat „nasyceniem”.

Innym potencjalnym wyborem, który może skrócić kodowanie, jest wybranie pionka przeciwnika do zbicia. Zwiększa to liczbę wyborów dla pierwszej części ruchu, wybierania figury, co najwyżej o dodatkowy bit (dokładna liczba zależy od tego, ile kawałków może przesunąć aktualny gracz). Po tym wyborze następuje wybór bierki, która prawdopodobnie jest znacznie mniejsza niż liczba ruchów dla któregokolwiek z podanych figur gracza. Bierkę można zaatakować tylko jedną bierką z dowolnego głównego kierunku plus skoczkami, łącznie maksymalnie 10 atakujących figur; daje to w sumie maksymalnie 9 bitów na ruch przechwytywania, chociaż spodziewałbym się średnio 7 bitów. Byłoby to szczególnie korzystne w przypadku chwytania przez królową, ponieważ często będzie miał kilka legalnych miejsc docelowych.

W przypadku nasycenia kodowanie przechwytywania prawdopodobnie nie daje przewagi. Moglibyśmy dopuścić obie opcje, określając w stanie początkowym, które są używane. Jeśli nasycenie nie jest używane, kodowanie gry może również używać nieużywanych liczb wyboru ( C <= c <2 ⁿ ) do zmiany opcji podczas gry. Za każdym razem, gdy C jest potęgą dwójki, nie mogliśmy zmienić opcji.

Question 28

Thomas ma właściwe podejście do kodowania płytki. Jednak powinno to być połączone z podejściem ralu do przechowywania ruchów. Zrób listę wszystkich możliwych ruchów, wypisz liczbę bitów potrzebną do wyrażenia tej liczby. Ponieważ dekoder wykonuje te same obliczenia, wie, ile jest możliwych i może wiedzieć, ile bitów do odczytania, nie są potrzebne żadne kody długości.

W ten sposób otrzymujemy 164 bity dla figur, 4 bity dla informacji o roszadzie (zakładając, że przechowujemy fragment gry, w przeciwnym razie można go zrekonstruować), 3 bity dla informacji o uprawnieniach przelotowych - po prostu zapisz kolumnę, w której nastąpił ruch ( Jeśli en passant nie jest możliwe, zapisz kolumnę tam, gdzie nie jest to możliwe - takie kolumny muszą istnieć) i 1 dla tego, kto ma się poruszać.

Ruchy zwykle zajmują 5 lub 6 bitów, ale mogą wynosić od 1 do 8.

Jeden dodatkowy skrót - jeśli kodowanie zaczyna się od 12 1 bitów (sytuacja nieprawidłowa - nawet fragment nie będzie miał dwóch królów po jednej stronie) przerywasz dekodowanie, czyścisz planszę i zakładasz nową grę. Następny kawałek będzie trochę ruchu.

Question 29

Algorytm powinien deterministycznie wyliczać wszystkie możliwe miejsca docelowe w każdym ruchu. Liczba miejsc docelowych:

2 biskupów po 13 miejsc docelowych = 26
2 wieże po 14 miejsc docelowych = 28
2 rycerzy po 8 miejsc = 16
królowa, 27 miejsc docelowych
król, 8 miejsc docelowych

Wszystkie 8 łap mogą stać się królowymi w najgorszym (pod względem wyliczenia) przypadku, co daje największą liczbę możliwych miejsc docelowych 9 * 27 + 26 + 28 + 16 + 8 = 321. W ten sposób wszystkie miejsca docelowe dowolnego ruchu można wyliczyć za pomocą 9-bitowej liczby.

Maksymalna liczba ruchów obu stron to 100 (jeśli się nie mylę, to nie szachista). W ten sposób każda gra może być nagrana w 900 bitach. Dodatkowo pozycja początkowa każdego elementu może być zapisana przy użyciu 6-bitowych liczb, co daje łącznie 32 * 6 = 192 bity. Plus jeden bit za rekord „Kto rusza pierwszy”. W ten sposób każdą grę można nagrać przy użyciu 900 + 192 + 1 = 1093 bitów.

Question 30

Przechowywanie stanu płyty

Najprostszym sposobem, o którym pomyślałem, jest to, że najpierw należy mieć tablicę 8 * 8 bitów reprezentujących położenie każdej figury (więc 1, jeśli jest tam figura szachowa, a 0, jeśli jej nie ma). Ponieważ jest to stała długość, nie potrzebujemy żadnego terminatora.

Następnie przedstaw każdą figurę szachową w kolejności jej lokalizacji. Używając 4 bitów na sztukę, zajmuje to 32 * 4 bity (łącznie 128). Co jest naprawdę marnotrawstwem.

Używając drzewa binarnego, możemy przedstawić pionka w jednym bajcie, skoczka, wieżę i gońca w trójce oraz króla i hetmana w 4. Ponieważ musimy również przechowywać kolor figury, która zajmuje dodatkowy bajt. jako (wybacz mi, jeśli to źle, nigdy wcześniej nie patrzyłem na kodowanie Huffmana ):

Pion: 2
Wieża: 4
Rycerz: 4
Biskup: 4
Król: 5
Królowa: 5

Biorąc pod uwagę sumy:

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

Który bije używając zestawu bitów o stałym rozmiarze przez 28 bitów.

Więc najlepszą metodą, jaką znalazłem, jest przechowywanie go w tablicy 8 ² + 100 bitów

8*8 + 100 = 164

Przechowywanie ruchów
Pierwszą rzeczą, którą musimy wiedzieć, jest to, który kawałek się przemieszcza. Biorąc pod uwagę, że na planszy jest maksymalnie 32 elementy i wiemy, czym jest każdy element, zamiast liczby całkowitej reprezentującej kwadrat, możemy mieć liczbę całkowitą reprezentującą przesunięcie elementu, co oznacza, że musimy dopasować tylko 32 możliwe wartości, aby przedstawić kawałek.

Niestety istnieją różne specjalne zasady, takie jak roszada lub obalenie króla i utworzenie republiki (odniesienie do Terry'ego Pratchetta), więc zanim przechowamy bierkę do ruchu, potrzebujemy jednego bitu wskazującego, czy jest to ruch specjalny, czy nie.

Więc dla każdego normalnego ruchu mamy niezbędne 1 + 5 = 6bity. (1 bit, 5 bitów na sztukę)

Po zdekodowaniu numeru elementu znamy typ elementu i każdy element powinien przedstawiać swój ruch w najbardziej efektywny sposób. Na przykład (jeśli moje zasady szachowe są do zera) pionek ma w sumie 4 możliwe ruchy (w lewo, w prawo, jeden ruch do przodu, dwa do przodu).
Tak więc, aby przedstawić ruch pionka, potrzebujemy bitów „6 + 2 = 8”. (6 bitów dla nagłówka początkowego ruchu, 2 bity dla jakiego ruchu)

Ruch dla hetmana byłby bardziej złożony, ponieważ najlepiej byłoby mieć kierunek (8 możliwych kierunków, czyli 3 bity) i łącznie 8 możliwych pól, do których można się poruszać w każdym kierunku (więc kolejne 3 bity). Zatem aby przedstawić ruch hetmana, wymagałoby to 6 + 3 + 3 = 12bitów.

Ostatnią rzeczą, jaka mi się przytrafiła, jest to, że musimy zapamiętać, którzy gracze to tura. Powinien to być pojedynczy bit (biały lub czarny, aby przejść dalej)

Wynikowy format
Więc format pliku wyglądałby mniej więcej tak

[64 bity] Początkowe lokalizacje elementów
[maks. 100 bitów] Początkowe elementy [1 bit] Obrót gracza
[n bitów] Ruchy

Gdzie ruch jest
[1 bit] Typ ruchu (specjalny lub normalny)
[n bitów] Szczegóły ruchu

Jeśli ruch jest normalnym ruchem, szczegół ruchu wygląda mniej więcej tak, jak ruch
[5 bitów] bierka
[n bitów] ruch określonej bierki (zwykle w zakresie od 2 do 6 bitów)

Jeśli jest to ruch specjalny,
powinien mieć typ całkowity, a następnie dodatkowe informacje (na przykład, jeśli jest to roszada). Nie pamiętam liczby ruchów specjalnych, więc może wystarczy wskazać, że jest to ruch specjalny (jeśli jest tylko jeden)

Question 31

W podstawowym przypadku planszy początkowej oraz kolejnych ruchów, rozważ następujące kwestie.

Użyj programu szachowego, aby przypisać prawdopodobieństwa wszystkim możliwym posunięciom. Na przykład 40% dla e2-e4 20% dla d2-d4 i tak dalej. Jeśli niektóre ruchy są legalne, ale nie są brane pod uwagę przez ten program, daj im niewielkie prawdopodobieństwo. Użyj kodowania arytmetycznego, aby zapisać dokonany wybór, który będzie liczbą od 0 do 0,4 dla pierwszego ruchu, 0,4 do 0,6 dla drugiego i tak dalej.

Zrób to samo po drugiej stronie. Na przykład, jeśli istnieje 50% szans na e7-e5 jako odpowiedź na e2-e4, to zakodowana liczba będzie wynosić od 0 do 0,2. Powtarzaj, aż gra się skończy. Rezultatem jest potencjalnie bardzo mały zakres. Znajdź ułamek binarny o najmniejszej podstawie mieszczącej się w tym zakresie. To jest kodowanie arytmetyczne.

Jest to lepsze niż Huffman, ponieważ można je traktować jako ułamkowe kodowanie bitów (plus niektóre na końcu gry, aby zaokrąglić w górę do całego bitu).

Wynik powinien być bardziej zwięzły niż Huffman i nie ma specjalnych przypadków dotyczących awansu, en passant, ruchu według zasady 50 i innych szczegółów, ponieważ są one obsługiwane przez program oceny szachów.

Aby zagrać ponownie, ponownie użyj programu szachowego do oceny szachownicy i przypisz wszystkie prawdopodobieństwa do każdego ruchu. Użyj wartości zakodowanej arytmetycznie, aby określić, który ruch został faktycznie zagrany. Powtarzaj, aż skończysz.

Jeśli twój program szachowy jest wystarczająco dobry, możesz uzyskać lepszą kompresję za pomocą enkodera dwustanowego, w którym prawdopodobieństwa są definiowane na podstawie ruchów zarówno dla czerni, jak i bieli. W najbardziej ekstremalnym przypadku ponad 200 stanów, kod ten zawiera cały zestaw wszystkich możliwych partii szachowych i dlatego jest niewykonalny.

Jest to całkiem inny sposób wyrażenia tego, co już napisał Darius, tylko z niewielkim przykładem tego, jak może działać kodowanie arytmetyczne i prawdziwym przykładem wykorzystania istniejącego programu szachowego do pomocy w ocenie prawdopodobieństwa następnego ruchu (ruchów).

Answer 1

95