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:
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 2 + 3 x 10 1 + 4 x 10 0 .
W podstawie 16 liczba 0xA50 jest równoważna 10 x 16 2 + 5 x 16 1 + 0 x 16 0 = 2640 (dziesiętnie).
Możemy więc zakodować naszą pozycję jako p 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0 gdzie p i reprezentuje zawartość kwadratu i .
2 256 to w przybliżeniu 1,16e77. 13 64 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 16 x 13 48 = 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.
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(), "");
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 8 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 .