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.
W praktyce
Gracz (program lub człowiek) musi ocenić pozycję, wybrać ruchy-kandydatów, uszeregować je, obliczyć warianty i ocenić nowo powstające pozycje. A po każdym posunięciu tworzą się nowe ruchy-kandydaci i znów trzeba wybierać. Coś takiego nazywamy drzewem wariantów.
Silnik szachowy zaczyna od wstępnej, bardzo płytkiej oceny dozwolonych posunięć i uszeregowuje je według tej wstępnej oceny. Następnie po kolei oblicza i ocenia następujące po nich warianty, przyporządkowawszy im różną ilość czasu zależnie od pozycji na liście. Jeśli ocena jakiegoś wariantu w tym drugim przebiegu zmieni się, wariant przesunie się na liście w górę lub w dół. W następnym przebiegu wszystko się powtarza, z tym że ilość czasu przeznaczona na warianty powstające po każdym posunięciu proporcjonalnie rośnie.
Procedurom liczenia wariantów musi jednak towarzyszyć odpowiednia wiedza: zdolność oceny elementów pozycyjnych, jak: struktura, tempa, bezpieczeństwo króla, mobilność bierek, przewaga przestrzeni, oraz zależności między nimi, a także zdolność oceny materiału zależnie od pozycji, a nie na zasadzie: goniec – 3 punkty, wieża – 5 punktów.
Ocenę pozycji silniki podają jako wielokrotność liczby jeden (wartość piona) ze znakiem plusa (przewaga białych) lub minusa (przewaga czarnych). Ocena pierwszego wariantu na liście, która jest jednocześnie oceną pozycji, określa nie tyle obecną pozycję na szachownicy, co najlepszą końcową pozycję we wszystkich obliczonych wariantach. Gdy białe mają dwa piony więcej lub program doszedł do takiej pozycji w swoich obliczeniach (i nie widzi nigdzie pozycji z większą przewagą), to bez uwzględnienia czynników pozycyjnych ich przewaga wynosi +2,0. Gdy czarne mają lub mogą mieć (przy najlepszej grze przeciwnika) wieżę za skoczka, a białe nie mają nic w zamian (np. lepszej struktury, możliwości ataku), ich przewaga z punktu widzenia programu jest podobna, tyle że przed liczbą widać znak minusa. Gdy żadna ze stron nie ma przewagi materialnej ani możliwości jej zdobycia przy najlepszej grze przeciwnika, ale jedna z nich ma inicjatywę, solidniejszą strukturę lub lepiej zabezpieczonego króla, ocena najpewniej będzie gdzieś pomiędzy zerem a jedynką, ze znakiem plusa lub minusa.
Ważnym elementem oceny jest głębia, wyrażona w liczbie półruchów (ang. ply). Głębię wyraża jedna lub dwie liczby. Na przykład głębia 16 oznacza, że silnik ocenił wszystkie pozycje w branych pod uwagę wariantach następujące po ośmiu posunięciach każdej ze stron. Głębia 16/44 oznacza, że silnik ocenił wszystkie pozycje w branych pod uwagę wariantach następujące po ośmiu posunięciach każdej ze stron, ale w przynajmniej jednym wariancie, najpewniej wymuszonym, doszedł do 22 pełnych ruchów. Ze względu na selektywny charakter analizy ten parametr nie jest porównywalny między silnikami, a nawet różnymi wersjami tego samego silnika.
Mniej ważna, bo niewiele mówiąca o głębi, jest liczba sprawdzonych pozycji, bez znaczenia jest, jako wartość względna, czas użyty do namysłu. W oderwaniu od czasu do namysłu niewiele mówi też szybkość liczenia wariantów, wyrażona w pozycjach na sekundę (ang. nodes per second). Z tym ostatnim parametrem jest też związany następujący problem: na procesorach wielordzeniowych lub w konfiguracjach wieloprocesorowych, gdy zamiast wątków działają oddzielne procesy, wskazania programu mogą być po prostu błędne.
Tak więc dwa statystycznie równie mocne silniki na takim samym (lub tym samym) sprzęcie wcale nie muszą osiągać remisu za remisem, program może nawet przegrać sam z sobą. Do różnic w ocenie pozycji i w stylu gry dochodzą ustawienia parametrów silnika i wpływ książek debiutowych, zwłaszcza że w takiej książce z reguły przez większą część debiutu po każdym posunięciu jest kilka odpowiedzi, które silnik może zagrać, różniących się jedynie szansą (wyrażoną w procentach) na wylosowanie.
