Szachy komputerowe

Silniki szachowe – oprogramowanie służące do analizowania pozycji, albo wariantów (możliwych do wykonania ruchów) oraz generujący ruchy, które są przez program uważane za najlepsze. Silniki wykorzystują protokół UCI (ang. Universal Chess Interface) albo XBoard do komunikacji (przesyłanie informacji o: ewaluacji, posunięciach które chce wykonać program, NPS, Pondermove itp...) z GUI (ang. Graphical user interface) szachowymi takimi jak Cute Chess, ChessBase or Fritz DGT. Oprogramowanie tego typu są wykorzystywane, na stronach internetowych/aplikacjach szachowych takich jak: chess.com (przegląd/analiza - Stockfish 16, Torch albo Komodo), lichess.org ( przegląd/analiza - Stockfish 16), służą one do oceniania partii rozgrywanych przez gracza.

Radio Shack Chess Computer 2150L
(lata 90. XX wieku)

Historia

Historia maszyn do gry w szachy jest starsza niż historia komputerów. Już Charles Babbage (1846) rozważał możliwości nauczenia gry w szachy jego niedokończonej, mechanicznej maszyny liczącej Analytical Engine. Najstarszą maszynę, która faktycznie potrafiła w ograniczonym stopniu grać w szachy, stworzył Leonardo Torres y Quevedo około 1890 r. Potrafiła ona w pełni poprawnie rozwiązywać problemy szachowe typu król-wieża-król, dla którego istnieje relatywnie prosty algorytm.

Podstawa teoretyczna teorii gier (algorytm min-max) potrzebna komputerom do praktycznej gry w szachy pojawiła się jednak dopiero w latach czterdziestych XX wieku. Choć rozważania nad szachami były popularne w literaturze na temat teorii gier, pierwszy rzeczywisty program powstał dopiero kilka lat później. W 1951 r. Alan Turing napisał szkielet programu grający w szachy, który jednak ze względu na brak dostępu do odpowiedniej maszyny liczącej, został przetestowany jedynie „ręcznie”. Pierwszym programem szachowym, który rzeczywiście został uruchomiony, był napisany w 1952 r. przez D.G. Prinza program do rozwiązywania problemów szachowych. Najstarszy program, który rzeczywiście grał w szachy, powstał w 1958 r.

Komputery pięły się w górę w rankingach szachowych, aż do historycznego meczu w maju 1997 komputera Deep Blue z mistrzem świata Garrim Kasparowem, wygranym przez komputer 3½ do 2½ (dwie wygrane Deep Blue, jedna Kasparowa, trzy remisy).

W obecnych czasach silniki szachowe są o wiele silniejsze od normalnych graczy. Najpotężniejsze oprogramowanie takie jak Stockfish albo Torch posiadają ranking powyżej 4000 ELO, w szachach typu CCRL 40/2 FRC (2 minuty na 40 posunięć).

Architektura programów do gry w szachy

Chess Champion MK I - komputer do gry w szachy

Teoria komputerowej gry w szachy opiera się na algorytmie min-max, gdyż liczba możliwych partii szachowych jest na tyle duża, że żaden współczesny komputer nie jest na tyle szybki aby można było zastosować algorytm typu brute force działający na tyle szybko, aby komputer zmieścił się w regulaminowym czasie rozgrywania partii szachowych. W najprostszej wersji program tworzy drzewo wszystkich możliwych ruchów do pewnej głębokości, wykonuje te ruchy, określa wartość pozycji po wykonaniu tych ruchów, i na podstawie tych wartości wybiera optymalną strategię. W każdej turze liczba możliwych ruchów gracza wynosi około 35. Dla pełnej analizy czterech półruchów (czyli po dwie rundy każdego gracza) wymaga zbadania około półtora miliona możliwości, dla sześciu prawie dwa miliardy. Analiza oparta na 3 ruchach w przód to zwykle zdecydowanie za mało, żeby dobrze grać.

Programy próbują używać różnych metod ograniczenia obszaru który należy przeszukać (game tree pruning). Najpopularniejsza z metod to przeszukiwanie alfa beta, w którym nie rozpatruje się tych pozycji, które nie wpłyną na ocenę sytuacji.

Drugą ważną techniką jest iteracyjne pogłębianie. Najpierw przeszukuje się drzewo gry do pewnej głębokości, po czym wybiera się kilka najbardziej obiecujących ruchów. Potem program wartościuje te ruchy do większej głębokości, żeby dowiedzieć się więcej o ich skutkach. Operacja ta jest powtarzana wielokrotnie aż do znalezienie prawdopodobnie najlepszego ruchu. Takie podejście umożliwia szybką rezygnację ze sporego odsetka wariantów gry. Np. nie ma zwykle sensu badać co się stanie wiele ruchów po tym, jak nastąpi wymiana hetmana za pionka, jeśli w grze są inne możliwości. Zwykle jest tak, że większość z dopuszczalnych ruchów stanowią ruchy ewidentnie „złe”, tak więc tego typu heurystyka zdecydowanie zmniejsza liczbę wariantów wymagających analizowania.

Ważnym elementem algorytmów szachowych jest system oceny pozycji. Nie ma praktycznej możliwości absolutnie dokładnej oceny pozycji, gdyż wiązało by się to z koniecznością analizy miliardów sekwencji ruchów od aktualnej sytuacji na szachownicy aż do zakończenia partii. Gdyby istniała funkcja umożliwiająca dokładną ocenę pozycji problem gry w szachy uprościłby się do oceny każdego z kilkudziesięciu dostępnych w danym momencie ruchów, bez konieczności obliczania kolejnych.

Funkcje oceny pozycji są więc siłą rzeczy tylko przybliżone, choć są one stale udoskonalane. Funkcje te oceniają kilka prostych parametrów:

• pierwszym z nich jest przewaga materialna – każdy pion to 1 punkt, goniec i skoczek po 3, wieża 5, hetman zaś 9; bardziej zaawansowane funkcje mają dokładniej ustalone współczynniki wagi figur; duża przewaga materialna to prawie pewne zwycięstwo
• drugim jest przewaga pozycyjna zależna od układu figur na planszy; na przykład zablokowana figura jest warta mniej niż wolna, można też oszacować bezpieczeństwo króla, panowanie nad centrum planszy itd.; istnieją też znacznie bardziej złożone systemy oceny (niektóre korzystają np. z sieci neuronowych), jednak nawet tak prosta funkcja pozwala na grę na bardzo wysokim poziomie; w szachach główny problem nie leży w ocenie pozycji, lecz w przeszukiwaniu drzew możliwości ruchów.

Funkcje oceny pozycji zawodzą gdy sytuacja na szachownicy zmienia się gwałtownie z ruchu na ruch, gdy np. właśnie trwa wymiana figur lub realizowana jest jakaś kombinacja szachowa. Stąd powstało pojęcie stanów wyciszonych (quiescent) i horyzontu zdarzeń. W stanie wyciszonym na szachownicy toczy się powolna walka pozycyjna, a warty do wzięcia pod uwagę horyzont zdarzeń jest bardzo rozległy, tzn. rozstrzygające posunięcie nie nastąpi w dającej się łatwo przewidzieć przyszłości. W takiej sytuacji większą rolę odgrywają funkcje oceny pozycji niż próby obliczania możliwych wariantów.

W stanie niewyciszonym gra w oparciu o funkcje oceny może z kolei prowadzić do całkowicie błędnych decyzji. W skrajnym wypadku, gdyby program miał ustawiony zbyt krótki horyzont zdarzeń i brał pod uwagę tylko chwilową ocenę pozycji jego koniec może przypaść akurat w chwili kiedy trwa wymiana hetmana za hetmana i jeden z nich już został zbity, drugi natomiast jeszcze nie. Naiwne ocenianie takiego stanu prowadzi do zupełnie błędnego wniosku, że jeden z graczy dysponuje gigantyczną przewagą, podczas gdy ona zniknie w następnym ruchu, którego jednak program już nie uwzględni. Jeśli stan nie jest wyciszony, należy kontynuować wymianę do końca, i ocenić sytuację kiedy nie ma już możliwych radykalnych zmian. Ludzie na ogół intuicyjnie rozróżniają te dwie sytuacje, zaś programy do gry w szachy muszą mieć zestaw kryteriów umożliwiających zmianę sposobu funkcjonowania w stanach wyciszonych i niewyciszonych.

Silniki szachowe do oceny pozycji wykorzystują tablicę figura-pole (ang. Piece-Square Tables), zawierające informacje o optymalnym położeniu danej bierki na szachownicy w zależności od momentu gry (otwarcie, gra środkowa, końcówka). Dla przykładu "bandowy" skoczek zostanie przez silnik potraktowany za mniej warty niż ten sam skoczek znajdujący się w centrum:

const KNIGHT_MG: Psqt = [
    -20, -10,  -10,  -10,  -10,  -10,  -10,  -20,
    -10,  -5,   -5,   -5,   -5,   -5,   -5,  -10,
    -10,  -5,   15,   15,   15,   15,   -5,  -10,
    -10,  -5,   15,   15,   15,   15,   -5,  -10,
    -10,  -5,   15,   15,   15,   15,   -5,  -10,
    -10,  -5,   10,   15,   15,   15,   -5,  -10,
    -10,  -5,   -5,   -5,   -5,   -5,   -5,  -10,
    -20,   0,  -10,  -10,  -10,  -10,    0,  -20
];

Na początku gry najtrudniej ocenić wartość ruchów. Większość programów zamiast używanych w późniejszym etapie algorytmów używa przygotowanej wcześniej książki otwarć zawierającej typowe zagrania i odpowiedzi do pewnej niewielkiej liczby ruchów początkowych, która nie jest stała bo zależy od typu otwarcia.

Kolejną optymalizacją programów do gry w szachy jest baza końcówek. Zawiera ona wszystkie pozycje, w których na planszy jest jedynie kilka figur i można dokładnie obliczyć wszelkie warianty gry, aż do jej zakończenia. Współcześnie bazy końcówek uwzględniają sytuacje gdy na szachownicy zostaje do pięciu figur, choć tworzone są już bazy dla sześciu. Baza końcówek umożliwia absolutnie precyzyjną ocenę czy uzyskana na szachownicy pozycja oznacza wygraną jednej ze stron, czy też remis. Kiedy program w wyszukiwaniu napotka na taką pozycję, ma on dokładną ocenę sytuacji i nie musi polegać na heurystykach.

Szachy a inne gry

Sukces programów do gry w szachy każe postawić pytanie, czy możliwe jest napisanie programów grających równie dobrze w inne gry, takie jak shōgi czy go.

W inne odmiany szachów powinno móc się grać podobnymi algorytmami. W shōgi jest więcej możliwych ruchów, przewaga materialna znaczy o wiele mniej, za to o wiele bardziej istotna jest przewaga pozycyjna. Buduje się skomplikowane układy mające na celu zapewnienie królowi bezpieczeństwa, których ocena jest dla komputera niełatwa. Liczba figur w grze jest też stała, więc gra nie upraszcza się z czasem, co uniemożliwia tworzenie bazy końcówek. Nie ma tu też stanów w pełni wyciszonych, gdyż gra przez cały czas sprowadza się do walki pozycyjnej. Napisanie programów do shōgi jest zatem znacznie trudniejszym zadaniem niż programów do gry w szachy, choć wiele doświadczeń z szachów można do tej gry przenieść.

Kolejnym wyzwaniem dla programistów jest go. Złożoność obliczeniowa go jest znacznie wyższa niż szachów. W każdym kroku możliwych jest nawet do 200-300 ruchów, co sprawia, że statyczna ocena życia grup pionków wymaga olbrzymiej mocy obliczeniowej. Programy do gry w go składają się zwykle z wielu modułów oceniających różne aspekty gry. Dokonał się jednak w tej dziedzinie duży postęp, czego świadectwem jest zwycięstwo programu AlphaGo nad zawodnikiem ze światowej czołówki. Metody programistyczne analogiczne do zastosowanych w AlphaGo znalazły zastosowanie również w szachach: na początku 2019 roku Leela Chess Zero osiągnęła poziom drugiego programu szachowego na świecie.

Zobacz też

• Mistrzostwa świata komputerów w szachach
• Free Internet Chess Server

Linki zewnętrzne

• A guide to Endgames Tablebase (ang.)
• Overtom Chess Computer Museum (ang.)
• Techniki informatyczne w szachach – artykuł Wojciecha Żuchowskiego