gambit

Silnik szachowy tylko z pozoru jest jednym projektem. To trzy podsystemy, z których każdy może zepsuć całość na własny sposób, i dopiero razem dają coś, co gra sensownie. gambit jest o tym, żeby te trzy części zgadzały się ze sobą na tyle dobrze, że wynik zaczyna przypominać grającego przeciwnika, a nie generator losowych ruchów.

Scala 3 daje tu wyrazisty język do modelowania planszy, ruchów i drzewa wariantów. Ale prawdziwe wyzwanie nie jest składniowe, tylko algorytmiczne: bezbłędny generator, uczciwa ocena i przeszukiwanie, które nie liczy w nieskończoność.

Generator ruchów, który raz na milion pozycji przepuści nielegalny ruch, sprawi, że silnik zagra coś niemożliwego. Ocena, która źle waży figury, poprowadzi go w przegraną z przekonaniem. Przeszukiwanie bez odcięć będzie myśleć godzinami nad ruchem, który ma paść w sekundę.

Żadnego z tych trzech nie da się zbyć. Słaby w którymkolwiek z nich silnik przegra, i to z konkretnego, dającego się wskazać powodu, a nie z ogólnej słabości.

Naiwne przeszukiwanie sprawdza każdą możliwą kontynuację, a tych są miliardy już na kilka ruchów w głąb. Odcięcie alfa-beta zauważa, że jeśli jedna odpowiedź przeciwnika już obala wariant, reszty jego odpowiedzi nie trzeba liczyć. Przy dobrym porządku ruchów tnie to przestrzeń tak mocno, że silnik sięga głębiej w tym samym czasie.

To nie jest drobna optymalizacja, tylko różnica między silnikiem, który widzi trzy ruchy do przodu, a takim, który widzi sześć. W szachach ta głębia przekłada się wprost na siłę gry.

Poprawność generatora ruchów weryfikuje się tak zwanym perft: liczysz wszystkie pozycje osiągalne na zadaną głębokość i porównujesz z liczbami, które cała społeczność szachowa zna na pamięć. Jeśli twoja liczba się nie zgadza, masz gdzieś buga, i to dokładnie widać, na której głębokości rozjazd się zaczyna.

Efektem jest kompletny silnik, który bierze pozycję i oddaje ruch: generator wystawia wszystkie legalne kontynuacje, ocena mówi, która prowadzi w lepszą stronę, a alfa-beta przeszukuje na tyle głęboko, na ile pozwala czas. Trzy podsystemy, które z osobna są tylko częściami, razem dają przeciwnika, który potrafi zagrać.