Szachy komputerowe

Szachy komputerowe - popularna nazwa dziedziny badań w zakresie sztucznej inteligencji polegająca na tworzeniu oprogramowania i specjalizowanych komputerów do gry w szachy.

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 Torrès y Qeuvedo 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 (minimaks) 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.

Pierwszym programem, który osiągnął poziom mistrza szachowego był Belle w 1983 uruchamiany na specjalnie zaprojektowanym sprzęcie. 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,5 do 2,5 (dwie wygrane Deep Blue, jedna Kasparowa, trzy remisy).

Architektura programów do gry w szachy

Teoria komputerowej gry w szachy opiera się na minimaksie, 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 ilość 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 wprzó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 jest 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 prawdodopodobnie najlepszego ruchu. Takie podejście umożliwia szybko rezygnację 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 ewidetnie "złe", tak więc tego typu heurystyka zdecydowanie zmiejsza liczbę wariantów wymagających analizowania.

Ważnym elementem algorytmów szachowych jest system oceny pozycji. Nie ma praktycznej możliwości absulutnie 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 momenecie 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 stanów wyciszonych (quiescent) i horyzontu zdarzeń. W stanie wyciszonym na szachownicy toczy się powolna walka pozycyjna, a horyzont zdarzeń jest bardzo rozległy, tzn. roztrzygające posunięcia 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 prowadzić do całkowicie błędnych decyzji. W skrajnym wypadku, gdyby program miał ustawiony zbyt krótki horyzont zdarzeń 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.

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 się do pięciu figur, choć tworzone są już bazy dla sześciu. Baza końcówek umożliwia absolutnie precyzyjną ocenę czy uzyskania 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. Ilość 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ść.

Prawdziwym wyzwaniem dla programistów jest go. Złożoność obliczeniowa go jest o kilkanaście rzędów wielkości wyższa od szachów. W każdym kroku jest możliwych około 200-300 ruchów, zaś statyczna ocena życia grup pionków jest de facto niemożliwa. Pojedynczym ruchem można tu zaprzepaścić całą grę, nawet jeśli pozostałe ruchy były bardzo dobre. Programy do gry w go nie używają więc takich algorytmów jak programy szachowe, a zamiast tego zwykle mają kilkadziesiąt modułów do oceny różnych aspektów gry i usiłują się posługiwać się w analizie takimi samymi pojęciami jak ludzie. Mimo to nadal grają bardzo słabo i są pokonywane nawet przez przeciętnych amatorów.