Szachy i komputery (6)

Jak działa silnik szachowy

Silniki szachowe są rozwijane od dziesiątków lat, ale dopiero od kilku ich siła gry pozwala im rywalizować z najlepszymi szachistami. Ma na to oczywiście wpływ wzrost wydajności sprzętu komputerowego i rosnąca efektywność kodu, ale przede wszystkim silniki mają coraz większą wiedzę, zwłaszcza o strategii, i coraz lepiej naśladują człowieka w ocenie pozycji i ruchów-kandydatów.

Gdy Deep Blue ponad dekadę temu pokonał Kasparowa, był zdolny przetworzyć około 200 milionów pozycji na sekundę, czyli kilkadziesiąt milionów razy więcej niż jego ludzki przeciwnik. W pierwszej partii przegrał, przegrałby też ze sto razy wolniejszym tandemem współczesnego programu i nowoczesnego peceta. Dlaczego?

Jak silnik widzi pozycję

Najczęściej stosowaną w silnikach szachowych metodą przedstawiania pozycji (nie mylić z kodem pozycji, FEN) są plansze bitowe (ang. bit board lub bitboard). Plansza bitowa to cyfrowy obraz wycinka pozycji, pozwalający silnikom (i procesorom) bardzo efektywnie przechowywać i przetwarzać pozycje przy użyciu prostych operacji logicznych. Zestaw takich dających się porównywać plansz tworzy kompletną pozycję. W szachach planszę bitową tworzy 64-bitowe słowo (szachownica ma 64 pola), w którym poszczególne znaki określają pola od A1 do H8. Plansza odnosi się do wybranego aspektu pozycji, na przykład pól dostępnych białemu hetmanowi, pól zajętych przez czarne piony lub kilku centralnych pól. (Każdy typ bierek, z rozróżnieniem kolorów, ma własną planszę). Z reguły planszom towarzyszy szereg zmiennych (na przykład określających prawo do roszady albo obecność przechodniego piona) i stałych (na przykład odpowiadających wybranej linii).

Stosuje się też „obracanie” plansz bitowych (o 45, 90 i 315 stopni), pozwalające efektywniej przetwarzać niektóre ruchy figur, na przykład po przekątnych.

Plansze bitowe mogą być łączone z listami bierek, które w początkach komputeryzacji były jedynym dostępnym (ze względu na ograniczenia sprzętu) sposobem przedstawiania pozycji, w celu zwiększenia efektywności niektórych operacji. Taka lista po prostu zawiera lokalizację wszystkich bierek.

Pozycje mogą być także przedstawiane w postaci tablic, na przykład 8×8 lub jednowymiarowej o długości 64. W takiej tablicy czarna wieża może być oznaczona na przykład liczbą –5, a biały pion – jedynką. Stosuje się także tablice o większych rozmiarach, na przykład 12×12 lub 16×16, aby efektywniej sprawdzać poprawność posunięć (czy pole docelowe znajduje się na szachownicy). Inną odmianą metody tablicowej jest 0x88.

Pozostałe metody to strumieniowa i Huffmana.

Sposób liczenia wariantów i oceny pozycji

Maszyna, czy to superkomputer wykorzystujący metodę brutalnej siły (ang. brute force), czy program naśladujący sposób myślenia człowieka, nie może wyjść poza algorytmy, jest pozbawiona wyobraźni, doświadczenia, skojarzeń. Moc obliczeniowa dzisiejszych komputerów wciąż jest dalece niewystarczająca w stosunku do liczby pozycji powstających po każdym posunięciu. Jeśli w danej pozycji białe mogą wykonać 30 dozwolonych posunięć, po każdym z nich czarne mają 30 dozwolonych odpowiedzi, a po każdej z nich także białe mają 30 odpowiedzi... Po kilku posunięciach liczba pozycji do oceny idzie w miliardy, a przecież nawet słaby amator liczy na więcej niż trzy – cztery do przodu... Metoda brutalnej siły, polegająca w czystej postaci na tym, że silnik w danej pozycji stara się policzyć całe wynikające z niej drzewo wariantów, aż do założonej głębi, czyli wszystkie możliwe posunięcia, wszystkie możliwe odpowiedzi na każde z posunięć, wszystkie możliwe odpowiedzi na każdą możliwą odpowiedź i tak dalej – nie wystarczy.

Kilka terminów spod maski

Jest wiele technik wykorzystywanych przy wybieraniu i liczeniu wariantów. W następnym podrozdziale pokażę, jak liczenie wariantów wygląda w praktyce, najpierw jednak w wielkim skrócie przedstawię kilka pojęć, które stoją za działaniem silnika.

W algorytmie min-max, podstawie obliczeń szachowych, chodzi o minimalizowanie maksymalnych możliwych strat. Przyjmuje się, że obaj gracze mają tę samą wiedzę o pozycji (pełną informację), suma gry wynosi zero, czyli zysk jednego gracza równa się stracie (z odwróconym znakiem) drugiego, i gracze starają się zarówno maksymalizować swoje zyski (grać najsilniejsze posunięcia), jak i minimalizować straty (grać posunięcia najbardziej oddalające porażkę). W skrócie: ruch x białych jest najlepszy (nawet jeśli prowadzi do porażki) po uwzględnieniu najlepszych odpowiedzi czarnych, a najlepsza odpowiedź czarnych na ruch x jest wybierana po uwzględnieniu możliwych odpowiedzi białych – i tak dalej. Oczywiście algorytm ten nie uwzględnia praktycznej strony gry z punktu widzenia człowieka: blefowania, zakładania pułapek, tworzenia praktycznych problemów, komplikowania pozycji, gdy przeciwnik jest w niedoczasie, itp.

Algorytm („odcinanie”) alfa-beta (ang. alpha-beta pruning) pozwala ograniczyć liczbę ocenianych wariantów. Chodzi w nim o to, aby nie liczyć wariantu po znalezieniu lepszego. Nazwa pochodzi od wartości alfa i beta dla wybranej pozycji, które oznaczają, odpowiednio, najmniejszy możliwy i największy możliwy zysk gracza A (będącego na posunięciu). Wariant jest „odcinany”, gdy jego wartość beta spadnie poniżej bieżącej wartości alfa, co oznacza, że istnieje przynajmniej jedno lepsze rozwiązanie (już znane, o bieżącej wartości alfa). Innymi słowy, jeśli w danym wariancie gracz B przy najlepszej grze uniknie pozycji o wartościach beta większych od alfa, silnik przerywa analizę wariantu prowadzącego do tej pozycji.

Pogłębianie iteracyjne (ang. iterative deepening depth-first search, IDDFS) to niezwykle ważny sposób na zwiększenie efektywności algorytmu alfa-beta, bo pozwala liczyć warianty w kolejności bliskiej optymalnej: od najlepiej ocenianego do wstępnie odrzuconych, i to na każdej kolejnej głębokości drzewa. W skrócie: jest tworzona lista posunięć według ich oceny, a następnie posunięcia są w tej kolejności analizowane. Gdy silnik osiąga następną głębokość, ponownie analizuje warianty od „najlepszego” do „najgorszego”, oczywiście w nowej kolejności (choć nie musi się ona zmienić).

Killer heuristic zwiększa efektywność liczenia wariantów w kolejnych iteracjach przez sprawdzanie w danej podgałęzi drzewa w pierwszej kolejności tych posunięć, które spowodowały odcięcie pozostałych wariantów w innej pozycji na tej samej głębokości drzewa (te posunięcia to tzw. killer moves). Jeśli odcięcie najlepiej ocenianego wariantu nastąpiło dzięki znalezieniu nowego ruchu, zastępuje on wcześniejszy „killer move” (lub jeden z kilku przechowywanych przez silnik).

Heurystyka pustych posunięć (ang. null-move heuristic) jest oparta na założeniu, że jeśli rozpatrywana pozycja nie byłaby gorsza od innych ocenionych pozycji nawet w przypadku, gdyby strona na posunięciu zrezygnowała z wykonania ruchu (hipotetycznie, bo to byłoby wbrew regułom gry), to jest duża szansa, że to właśnie w niej zostanie znaleziony wariant odcinający pozostałe. Tak więc silnik pomija posunięcie, oblicza warianty w tak powstałej pozycji, a jeśli nastąpi odcięcie wcześniej ocenionych gałęzi, wykonuje obliczenia już bez pomijania żadnych ruchów.

Zmniejszanie głębi obliczania słabszych posunięć (ang. late move reduction) opiera się na założeniu, że skoro to warianty najlepiej oceniane przy danej głębi przeszukiwania drzewa mają największe szanse odciąć pozostałe, ogólna efektywność obliczeń zwiększy się, jeśli to tym najlepiej ocenianym wariantom przyporządkuje się więcej czasu procesora (policzy się je głębiej).

Niezwykle ważne jest zmniejszenie liczby obliczeń przez uniknięcie sprawdzania już ocenionych pozycji, do których prowadzi więcej niż jedna kolejność posunięć. Umożliwiają to tablice transpozycji (ang.transposition table), będące formą tablic mieszających (ang. hash table). Typowy rozmiar tablicy transpozycji na współczesnym domowym pececie to 128–512 MB (najnowsze wpisy wypierają najstarsze). Tablice te zawierają ocenę już policzonych pozycji, a zatem, co najważniejsze – także wynikających z niej wariantów, a silnik, zanim oceni nową, sprawdza w tablicy transpozycji, czy już nie pojawiła się w analizie. Ponadto jest w nich przechowywana kolejność posunięć w danej pozycji zależnie od przyporządkowanej im oceny.