Jak Syzygy przechowuje informacje?

11

Po przeczytaniu wszystkiego, co do tej pory znalazłem, wiem, że Syzygy używa zarówno plików win / draw / loss, jak i plików z odległości do zera, ale nie znalazłem żadnych informacji na temat wewnętrznego formatu plików, z których korzystają te pliki. Szukam wyjaśnienia niskiego poziomu szczegółowości.

Oscar Smith
źródło

Odpowiedzi:

14

Ponieważ nie ma jednej kompleksowej publikacji, jest ona oparta na kodzie sondowania , generatorze i różnych objaśnieniach Ronalda de Mana (autora generatora).


Podczas sondowania praktycznie dowolnej bazy tabel (zwanej także dużą skompresowaną mapą skrótu):

  1. Pozycja jest znormalizowana ...
  2. ... zmapowany do indeksu liczb całkowitych.
  3. Indeks jest przeglądany w tabeli, która identyfikuje, do którego „bloku” należy.
  4. Blok jest dekompresowany do momentu odzyskania informacji dla indeksu.

Następnie zwykle jest jakiś kod „poza” sondowaniem, przynajmniej w celu rozwiązania przechwyceń en pasywnych.


Począwszy od zewnętrznego kodu dla WDL. Tabele Syzygy wykorzystują optymalizację opartą na następującej obserwacji: Jeśli pozycja ma przejęcie, które osiąga określoną wartość (np. Wygrywa), wówczas sama pozycja ma przynajmniej tę wartość (np. Wygrywa). W takim przypadku tabela może przechowywać dowolną niższą wartość, zależnie od tego, która metoda jest najlepsza w przypadku kompresji, i można to łatwo skorygować, sprawdzając przechwycone tabele podrzędne.

Aby uzyskać DTZ, najpierw należy wykonać sondę WDL. Jeśli pozycja zostanie narysowana, wówczas DTZ wynosi 0, a tabela może przechowywać wszystko, w zależności od tego, która opcja jest najlepsza do kompresji. Jeśli najlepszym ruchem było przechwytywanie (które możemy zapamiętać z sondy WDL), wówczas DTZ wynosi +/- 1 lub +/- 101 w zależności od WDL, a tabela może ponownie przechowywać wszystko, w zależności od tego, który z nich jest najlepszy do kompresji.

Tabele pionków zawierają 4 podtabele, po jednej dla każdego pliku „pionka wiodącego” (po normalizacji).

Tabele (pod) WDL są dwustronne, tzn. Zasadniczo zawierają dwie oddzielne tabele dla każdej strony gry końcowej (chyba że materiał jest symetryczny).

Tabele DTZ przechowują tylko jedną stronę do przesunięcia. Dlatego może być konieczne krótkie 1-warstwowe wyszukiwanie w celu obliczenia DTZ dla drugiej strony.


(1) O normalizacji: Można to zrobić na wiele sposobów i nie jest łatwo z góry powiedzieć, który z nich doprowadzi do najlepszej kompresji. Generator po prostu próbuje różnych permutacji. Ostateczna kolejność elementów jest przechowywana w nagłówku pliku tabeli.

(2) Niektóre kombinatoryki. Wyzwaniem nie jest posiadanie dużych luk dla niemożliwych pozycji. Chociaż jest to dość trudne, nie sądzę, że Syzygy robi tutaj coś specjalnego. Koncepcyjnie, kawałki lub grupy elementów są umieszczane na planszy w kolejności określonej w nagłówku.

(3) Skompresowane wartości są przechowywane w blokach. Rozmiar bloku jest określony w nagłówku tabeli. Indeksy mapowania tabel na bloki są rzadkie, więc pozwala skakać bardzo blisko właściwego bloku, a następnie wymaga krótkiego skanowania do przodu lub do tyłu, aby znaleźć dokładny blok. Blok może przechowywać wartości dla maksymalnie 65536 pozycji.

(4) Tabele Syzygy używają niestandardowej kompresji w oparciu o RE-PAIR . Ważną cechą jest to, że faktycznie umożliwia wykorzystanie możliwości przechowywania dowolnych wartości, które zostały określone powyżej. Dekompresja jest bardzo szybka i może zatrzymać się, gdy tylko dostępna będzie wartość żądanego indeksu.

Opcjonalnie tabele DTZ mogą wymagać kolejnego kroku f (wdl, wartość przechowywana) = wartość rzeczywista. Ta dodatkowa mapa DTZ jest wymieniona w nagłówku tabeli i sama jest tabelą z 8-bitowymi wpisami. (Co ciekawe, okazało się to niewystarczające dla 7-częściowych gier końcowych, nawet z pionkami, więc jest teraz inna flaga, która umożliwia wpisy 16-bitowe).

W przypadku wartości DTZ, jeśli generator określił, że wszystkie wartości dla tabeli są mniejsze niż 100, dokładne liczby pół-ruchów nie są wymagane, aby zagwarantować idealną grę. Zamiast tego ustawia flagę w nagłówku tabeli i zaokrągla pół-ruchy do pełnych ruchów, aby zaoszczędzić miejsce.

Oczywiście nie ma potrzeby przechowywania znaku ani dodatkowego przesunięcia +/- 100 dla przeklętych gier końcowych, ponieważ można to wywnioskować z wartości WDL.

Ponieważ dekompresja jest bardzo szybka, nie ma potrzeby buforowania. Zamiast tego silniki mogą polegać na pamięci podręcznej stron systemów operacyjnych do przechowywania (wciąż skompresowanych) bloków.


6-częściowe tabele zawierają informacje WDL i DTZ dla 3 777 154 440 416 unikalnych pozycji w 150 gigabajtach, więc ~ 0,3 bitów na pozycję.

Podsumowując, wszystkie tabele Syzygy zostały ulepszone w stosunku do poprzednich formatów tabel w co najmniej 3 z tych obszarów, dzięki czemu jest to bardzo kompaktowy i szybki format. O dziwo generator jest również dość szybki.

Oczywiście użycie DTZ50 jest pragmatycznym wyborem, ponieważ jest to wystarczająca ilość informacji, aby niezawodnie robić postępy i umożliwia idealną grę (wynik) zarówno z regułą 50 ruchów, jak i bez niej. Jednak na podstawie dotychczas opublikowanych zmian w Cfish (RdM działa teraz na tabelach DTM), wiele technik będzie miało zastosowanie również do DTM.

Niklas
źródło