Techniki Bitboard: Kodowanie Szachownicy w 64 Bity

Dlaczego reprezentować planszę jako bity

Naiwne przedstawienie szachownicy polega na tablicy 8x8, w której każda komórka przechowuje kod figurę lub pustą. Sprawdzanie, czy wieża może zaatakować coś, oznacza chodzenie o jedno pole na raz aż do napotkania figury lub krawędzi, cztery oddzielne kierunki z rozgałęziającą się logiką na każdym kroku. Jest to wolno, gdy trzeba robić to miliony razy na sekundę podczas poszukiwań. Zamiast tego reprezentacja bitboardowa wykorzystuje dwanaście 64-bitowych liczb całkowitych dla standardowej pozycji szachowej: po jednej dla każdej kombinacji typu figury (pion, skoczek, hetman, wieża, królowa, król) i koloru (biały, czarny). Indeks bitu n, od 0 do 63, odpowiada konkretnemu polu, zwykle bit 0 to a1, a bit 63 to h8, skanując od lewej do prawej, od dołu do góry. Jeśli białe piony znajdują się na polu g1, bit 6 w bitboardzie białych pionów jest ustawiony na 1; wszystkie pozostałe bity w tym liczniku są ustawione na 0. Ta reprezentacja przekształca zapytania o planszę w operacje arytmetyczne. Całkowita zajętość planszy to po prostu bitwise OR wszystkich dwanaściu bitboardów figur. Całkowita zajętość białych to OR tylko sześciu bitboardów białych. Aby znaleźć, które z docelowych kwadratów w przekątnej hetmana rzeczywiście zawierają przeciwnika, silnik ANDuje jego wstępnie obliczony bitboard ataku z bitboardem zajętości przeciwnika; każdy 1 bit pozostały w wyniku jest prawidłowym polem ataku, odkrytym bez sprawdzania pojedynczych kwadratów. Praktyczny efekt to prędkość mierzona w cyklach procesora zamiast iteracji pętli. Współczesny procesor wykonuje 64-bitowe operacje AND, OR, XOR lub przesunięcie bitowe w jednym cyklu, więc operacja, która zajęłaby dziesięć lub więcej porównań w opartym na tablicach reprezentowaniu planszy, skurczy się do jednej instrukcji. Pomnóż tę oszczędność przez miliony pozycji, które silnik bada na sekundę podczas głębokiego poszukiwania, a różnica między opartą na tablicach a bitboardową generacją ruchów staje się różnicą między programem hobbystycznym a silnikiem konkurencyjnym. Jest to również powód, dla którego bitboardy nie ograniczają się tylko do szachów: Othello, szachy w locie, Connect Four i inne gry o stałym rozmiarze siatki z stanami zajętości binarnymi czerpią ten sam trik, gdy rozmiar siatki wygodnie mieści się w słowie maszyny.

Podstawowe Operacje Bitowe na Planszy

Cztery operacje robią prawie całą robotę w silniku bitboardowym, a każda z nich bezpośrednio odpowiada koncepcji szachowej. AND znajduje przecięcia. ANDowanie bitboardu ataku prekomputowanego figury z bitboardem zajętości przeciwnika daje dokładnie te pola, które ta figura może zaatakować. ANDowanie bitboardu ruchu do przodu pionka z bitboardem pustych pól (operacja logiczna NOT, czyli bitwise komplement) potwierdza, czy pole przed nim jest faktycznie wolne do zajęcia. OR łączy zbiory bez utraty informacji, ponieważ ustawienie bita, który już jest równy 1, nic nie zmienia. Dzięki temu buduje się bitboardy zajętości: OR-ując bitboardy wszystkich figur jednego koloru, otrzymuje się pola zajęte przez tę stronę, a OR-ując obie strony razem, uzyskuje się całkowitą zajętość. Używa się go również do dodania figury do bitboardu, poprzez OR-owanie z bitboardem, który ma tylko jeden bit ustawiony na 1. XOR przesuwa bity, co dokładnie zachodzi, gdy figura się porusza: bit w pierwotnym polu zmienia się z 1 na 0, a bit w docelowym polu zmienia się z 0 na 1, wszystko to osiąga się poprzez XOR-owanie bitboardu figury z bitboardem, który ma tylko te dwa bity ustawione. XOR jest również używany do aktualizacji bitboardu figury, która została zajęta, czyszcząc bit w docelowym polu. Ta właściwość sprawia, że XOR jest samowiązujący się, co jest wygodne podczas przeszukiwania: ponowne zastosowanie identycznego XOR przywraca oryginalny bitboard dokładnie. Shift symuluje ruch w danym kierunku. Przesunięcie bitboardu białych pionków o 8 pozycji w lewo (ponieważ każdy rząd ma 8 bitów), generuje wszystkie pola, na które pion mógłby się ruszyć, zanim sprawdzi się blokady lub promocja. Zajęcia po przekątnych pionów wykorzystują przesunięcia o 7 lub 9, z zastosowaną maską najpierw, aby zapobiec przepełnieniu bitów z krawędzi planszy, co jest artefaktem pakowania dwuwymiarowej planszy w jedno wymiarowy bitstring. Poza tymi czterema, silniki polegają na dwóch dodatkowych elementach: licznik bitów (liczba ustawionych bitów, przydatna do liczenia materiału i oceny mobilności) oraz skanowanie bitów (znajdowanie indeksu danego ustawionego bita), gdzie sekwencja De Bruijna, omówiona później w tym artykule, staje się niezbędna.

Problem z przesuwającym się elementem

Skoczki, królowie i piony mają ustalone, krótkodystansowe wzorce ruchu: skoczek atakuje z dowolnego pola zawsze tym samym ustalonym zestawem przesunięć, więc jego pełny zestaw możliwych tablic bitowych ataków, jeden na każde pole początkowe, można obliczyć raz i przechowywać w tabeli 64 wpisów bez dodatkowej pracy podczas wykonywania programu. Roki, gońce i królowe są inne, ponieważ przesuwa się po nich aż do uderzenia w brzeg planszy lub w blokującą figurę, przyjazną lub wrogą. Rok na d4 bez przeszkód może osiągnąć cały rząd d i 4. rangę; ten sam rok z pionkiem na d6 może osiągnąć tylko d5 i d6 do góry, zanim blokujący go element to zatrzyma. Zatem zestaw legalnych pól docelowych zależy nie tylko od pozycji roka, ale także od pełnego wzoru zajętych pól wzdłuż jego rzędu i kolumny, zwany zajętością. Na oko oznacza to ponowne obliczanie ruchów legalnych poprzez raycasting pole po polu, sprawdzając każde pole pod kątem blokady przed kontynuowaniem, co wprowadza dokładnie ten sam rodzaj obliczeń obciążonych pętlami, które bitboardy miały wyeliminować. Liczba możliwych konfiguracji blokujących istotnych dla roka jest duża: do 2 do potęgi 12 dla roka w centrum planszy (12 istotnych pól wzdłuż jego rzędu i kolumny, pomijając krawędzie, ponieważ krawędź sama w sobie jest zawsze ważnym punktem zatrzymania niezależnie od zajętości), przechowywanie wstępnie obliczonej odpowiedzi dla każdej możliwej wzoru zajętości, dla każdego pola, zarówno dla roka, jak i gońca, jest zasadniczo wykonalne, ponieważ suma wynosi kilka setek tysięcy wpisów w tabeli, co mieści się w budżecie pamięci współczesnego silnika. Pozostałe pytanie polega na algorytmie: przy danym losowym bitboardzie zajętości 64-bitowym, jak przekształcić istotne bity blokujące w kompaktowy indeks do tej wstępnie obliczonej tabeli, szybko i bez kolizji, które zwracają nieprawidłową odpowiedź? To pytanie odpowiadają mu magiczne bitboardy, a to jest temat następnej sekcji.

Magiczne Bitboardy: Haszowanie Zajętości do Indeksu

Technika magicznych bitboardów rozwiązuje problem wyszukiwania figur szachowych z przesunięciem, używając pojedynczej operacji mnożenia. Dla każdego pola i każdej figury szachowej silnik wstępnie oblicza maskę bitową zajętości, która dotyczy faktycznie istotnych pól dla danego pola, zwaną maską istotnej zajętości – która celowo wyklucza zewnętrzny brzeg planszy w tym kierunku, ponieważ przesunięcie zawsze się zatrzymuje tam, niezależnie od tego, co się na nim znajduje. Przy danej pozycji na szachownicy silnik najpierw wydobywa tylko bity z bitboardu zajętości rzeczywistej, które znajdują się w tej masce istotnej, używając operacji AND. Następnie ta zmodyfikowana zajętość jest mnożona przez specjalnie dobrany 64-bitowy stały, magiczną liczbę, a górne bity tego 64-bitowego iloczynu są wydobywane za pomocą przesunięcia w prawo. Wynik to mała liczba, wystarczająco mała, aby służyć bezpośrednio jako indeks do tablicy wstępnie obliczonych bitboardów atakujących dla danego pola. To, co czyni magiczną liczbę magiczną, polega na tym, że dla konkretnego ograniczonego zestawu wzorców zajętości, które są faktycznie osiągalne dla danego pola z jego maską istotnej zajętości, mnożenie rozprasza bity wejściowe na górnych bitach iloczynu w taki sposób, aby uniknąć kolizji, lub inaczej, w taki sposób, że jeśli wystąpią kolizje, to zachodzą tylko między wzorcami zajętości, które mapują się na tę samą identyczną legalną ruch – co czyni kolizję bezużyteczną. Szukanie takich stałych historycznie wymagało losowego przeszukiwania: generuje się kandydatową 64-bitową liczbę, testuje się ją przeciwko każdemu możliwemu wzorcowi istotnej zajętości dla danego pola i sprawdza się, czy wynikowe indeksy nigdy nie kolidują destrukcyjnie; jeśli tak się stanie, odrzuca się kandydata i próbuje się kolejną. Ta brutalna metoda przeszukiwania niezawodnie znajduje działające magice w ciągu sekund czasu obliczeniowego, a po znalezieniu są to stałe, które są zakodowane na stałe w kodzie źródłowym silnika, ponieważ przeszukiwanie musi nastąpić tylko raz, podczas tworzenia silnika, a nie podczas rzeczywistej gry. Wynikiem jest dramatyczny zysk. Obliczanie pełnego bitboardu prawych ruchów króla lub hetmana, uwzględniając wszystkie możliwe blokady, staje się: jeden AND do maskowania istotnej zajętości, jedno mnożenie przez magiczną liczbę, jedno przesunięcie w prawo do wydobycia indeksu i jedna operacja wyszukiwania w tablicy. Cztery szybkie operacje zastępują to, co w przeciwnym razie byłaby zmiennodługością pętla ray-casting, a ponieważ nie ma rozgałęzień na podstawie zawartości planszy, ta sekwencja wykonuje się w przewidywalnym tempie, przyjaznym dla potoków na nowoczesnych procesorach, co ma ogromne znaczenie, gdy dzieje się to miliard razy podczas głębokiego przeszukiwania.

Sekwencje De Bruijna: Znajdowanie Najniższego Ustawionego Bita Natychmiast

Silniki bitboardowe stale potrzebują odpowiadać na bardziej precyzyjne pytanie: przy danym 64-bitowym liczniku z ustawionymi bitami, który kwadrat odpowiada najniższemu ustawionemu bitem? Powoduje to się wtedy, gdy silnik iteruje po poszczególnych kwadrach w bitboardzie, na przykład przechodząc przez każdy kwadrat, w którym atakuje element, aby wygenerować odrębny ruch dla każdego z nich. Niewłaściwy sposób polega na sprawdzeniu bita 0, następnie bita 1, a następnie bita 2 i tak dalej, aż znajdzie 1, co jest pętlą do 64 iteracji w najgorszym przypadku. Klasyczna sztuczka bitowa przyspiesza znalezienie samego najniższego ustawionego bita: obliczanie bitboardu AND z jego własnym dwuelementowym uzupełnieniem izoluje tylko najniższy ustawiony bit do własnej wartości 64-bitowej, w którym wszystkie inne bity są wyzerowane, w jednym kroku. Pozostawia to drugie problem: przy danym zidentyfikowanym pojedynczym bitowym wzorcu, który kwadrat spośród 64 możliwych pozycji reprezentuje, wyrażony jako prosty indeks liczbowy zamiast wzoru bitowego? Tutaj wkracza sekwencja De Bruijna. Sekwencja De Bruijna rzędu k nad dwójkowym alfabetem to cykliczna sekwencja o długości 2 do potęgi k, w której każdy możliwy podciąg o długości k występuje dokładnie raz jako sekwencja odczytywana z powrotem, z uwzględnieniem pętli. Dla skanowania bitów 64-bitowych silniki używają określonej sekwencji De Bruijna rzędu 6, ponieważ 2 do potęgi 6 wynosi 64. Niezwykła właściwość jest taka, że jeśli weźmiesz zidentyfikowany pojedynczy bitowy wzorzec, pomnóż go przez tę sekwencję De Bruijna, a następnie przesunięcie o 58 bitów (zachowując tylko górne 6 bitów) produktu 64-bitowego, wynikowy 6-bitowy numer jest unikalnym indeksem między 0 i 63, a ten indeks przekazuje bezpośrednio do małej tabeli 64 wpisów, która została wstępnie obliczona raz, aby odwzorować każdy z tych 64 możliwych indeksów na rzeczywisty numer kwadratu oryginalnego bitu. Powodem, dla którego to działa, jest to, że mnożenie przez dobrze skonstruowaną sekwencję De Bruijna powoduje, że każdy z 64 możliwych pojedynczych bitowych wejść przesunie wzorzec stałej o różną, unikalną ilość, więc górne 6 bitów produktu kończy się inaczej dla każdego możliwego położenia bitu, dokładnie taka właściwość hashowa, którą zapewnia sekwencja De Bruijna dzięki jej konstrukcji kombinatorycznej. Cała operacja, izolowanie najniższego bita, mnożenie, przesunięcie i wyszukiwanie, zajmuje niewielką liczbę instrukcji maszynowych niezależnie od tego, gdzie w danym momencie znajduje się ustawiony bit, zastępując zmienną długość pętli stałą, przewidywalną, bez rozgałęzień, dokładnie taki cel projektowy, który motywuje magiczne bitboardy dla przesuwnych elementów.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Bitboard Techniques: Encoding a Chessboard in 64 Bits i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.