OPOLCHESS – robot do gry w szachy (1) Oprogramowanie FXChess XF

 

Sławę Turkowi przyniosła niezwykła umiejętność gry w szachy. Turek rozgrywał partie m.in. z Katarzyną Wielką, Benjaminem Franklinem i Napoleonem Bonapartem. Maszyna była urządzeniem genialnym jak na tamte czasy. Dopiero po latach ujawniono prawdę o tym automacie. Zastosowane rozwiązania mechaniczne pozwalały ukryć w nim szachistę. Ta historia intrygowała ludzi przez wiele lat. Dopiero po prawie dwóch stuleciach rozwój nauki i techniki umożliwił budowę automatycznego szachisty.

Potyczki z robotem

Przełomu w dziedzinie algorytmów gier dokonał Alan Turing, który sformułował algorytm gry w szachy jeszcze przed powstaniem pierwszego komputera. Algorytm przetestował za pomocą kartki papieru i ołówka, a zapis gry zachował się do dzisiaj. Ten pojedynek człowieka z maszyną w ludzkiej postaci odbył się w 1952 r. w Manchester [3].

W 1950 r. w ośrodku badawczym Los Alamos w USA opracowano superkomputer MANIAC I (Mathematical Analyzer, Numerator, Integrator, and Computer) przeznaczony do badań nad bombą atomową. W ramach testów zaprogramowano go do gry na szachownicy 6 × 6 pól. W pierwszej partii komputer ten poniósł porażkę z mistrzem szachowym, choć rozpoczął grę z przewagą królowej. W drugiej pokonał przypadkową osobę i było to pierwsze zwycięstwo maszyny nad człowiekiem w grze logicznej [3].

Pierwszy w historii mecz między dwoma komputerami szachowymi rozegrano w 1966 r. Był to pojedynek Rosja – USA. Wielkim wydarzeniem było zorganizowanie pierwszych w historii Mistrzostw Świata Szachów Komputerowych w 1974 r. Przełomowym w rozwoju szachów komputerowych okazał się 1988 r., w którym Deep Thought jako pierwszy komputer w historii pokonał arcymistrza szachowego, Benta Larsena. W 1997 r. komputer Deep Blue pokonał legendę szachów Garry’ego Kasparova. Firma IBM – twórca tego komputera – nigdy nie zgodziła się na rewanż, a legendarną maszynę rozmontowano i częściowo umieszczono w muzeum.

Turek z Opola

Historia Turka stała się inspiracją do opracowania programu FXChess XF [6] oraz do realizacji projektu OPOLCHESS [1, 2, 5] – robota do gry w szachy. Autor programu swoją przygodę z szachami komputerowymi rozpoczął od opracowania w 2005 r. wraz z kolegami programu Ultimate Chess na uczelni Ingeniørhøjskolen i Køenhavn w Danii. W ramach wykładu konsultacji udzielał sam arcymistrz szachowy Bent Larsen. W 2006 r. w ramach pracy dyplomowej na Politechnice Opolskiej, realizowanej pod kierunkiem dr hab. inż. Krystyny Macek-Kamińskiej, powstał przewidziany na platformy 64-bitowe program FXChess XF.

Celem realizacji projektu jest opracowanie własnego Turka, pierwszego w Opolu robota, który będzie samodzielnie rozgrywał partie szachów. Robot ten ma strukturę RRR z chwytakiem trójpalczastym i do pewnego stopnia przypomina rękę. Obecnie projekt jest w końcowej fazie realizacji. Zarówno program do gry w szachy, jak i robot z układem sterowania i interfejsem komunikacyjnym zostały ukończone. Aktualnie tworzony jest moduł komunikacyjny do programu FXChess XF, którego zadaniem jest zapewnienie komunikacji pomiędzy programem i robotem.

Algorytmy i reprezentacja danych

Teoria gier klasyfikuje szachy jako grę dwuosobową, skończoną, o sumie zerowej i pełnej informacji. Najprostszym algorytmem stosowanym w grach tego typu jest algorytm minimaks. Jego ideą jest minimalizowanie maksymalnej, możliwej do poniesienia straty, a ograniczeniem w stosowaniu jest wykładnicza złożoność obliczeniowa O(aⁿ) [4, 7]. Metodę usprawniono implementując odcięcie alfa-beta.

Algorytm minimaks z odcięciami alfa-beta pomija węzły drzewa gry, które nie wpływają na wybór najlepszego ruchu. Po przeszukaniu pierwszej podgałęzi drzewa algorytm zapamiętuje najlepszy wynik. Jeżeli w kolejnej podgałęzi napotka wynik gorszy, to przerywa jej analizę. Im szybciej nastąpi odcięcie, tym większa jest efektywność tego algorytmu. Dlatego jako rozszerzenie algorytmu alfa-beta zastosowano sortowanie ruchów, aby ruchy odcinające występowały jak najszybciej.

Podczas gry przeszukiwanie jest ograniczone zadanym czasem wykonania ruchu. Jeśli przeszukiwanie nie zakończyłoby się na czas, to w pozostałej części drzewa mógłby znajdować się niekorzystny ruch. Najczęściej stosowane do rozwiązania tego problemu jest iteracyjne pogłębianie. Polega ono na iteracyjnym przeszukiwaniu drzewa gry na coraz większą głębokość, aż do upływu limitu czasu. Jeżeli przeszukiwanie na jakimś poziomie nie zostanie ukończone przed upływem limitu czasu ruchu, to przyjmowane jest najlepsze rozwiązanie z poprzedniej iteracji.

Jednym z kluczowych elementów każdego programu szachowego jest funkcja ewaluacyjna, będąca tajemnicą twórcy. Jej zadaniem jest szacowanie, w jakim stopniu zaistniała na szachownicy sytuacja jest korzystna dla gracza. Nawet najszybszy algorytm przeszukiwania drzewa gry, w połączeniu ze źle sformułowaną funkcją ewaluacyjną, może dać kiepski efekt końcowy. Główny problem polega na tym, że funkcja ta jest statyczna i nie uwzględnia dynamiki gry ani strategii graczy, a jej złożoność wpływa na czas obliczeń. W przypadku złożonej funkcji ewaluacyjnej wzrasta czas przeszukiwania drzewa gry, natomiast funkcja zbyt prosta może zwracać błędne wyniki.

W początkowej i środkowej fazie gry program bazuje na tej funkcji oraz reprezentacji punktowej bierek i sytuacji na szachownicy. W fazie końcowej, gdy jest już znalezione rozwiązanie prowadzące do zwycięstwa, rozgrywka prowadzona jest zgodnie z odnalezionym wariantem wygrywającym. Ciekawostką jest to, że w początkowej fazie gry, gdy na szachownicy znajduje się duża liczba bierek, gracz człowiek rozpatruje nieliczne warianty gry, lecz głębiej niż robi to komputer. Komputer natomiast rozpatruje wszystkie możliwe ruchy, co zajmuje mu dużo czasu. W trakcie gry sytuacja ta się zmienia. Im mniej bierek pozostaje na szachownicy, tym mniej wariantów jest do sprawdzenia. Tym samym komputer rozpatruje ruchy na coraz większą głębokość. Stąd rada dla grających. Grając z komputerem unikajcie wymiany bierek. Zmniejszając liczbę bierek dajecie przewagę komputerowi. Twórcy programów komputerowych wiedzą o tym i często zachęcają programy do wymian.

Najprostszą metodą ewaluacji stanu szachownicy jest porównanie wartości bierek posiadanych przez każdego z graczy. Prowadzone przez wiele lat analizy zakończeń rozgrywek szachowych pozwoliły na określenie wartości poszczególnych bierek. Najczęściej przyjmuje się notację 1-3-3-5-9, zakładającą: pion – 1, goniec i skoczek – 3, wieża – 5, hetman – 9, król – 124 lub więcej. Wartość króla przyjmuje się tak, aby był on cenniejszy od wszystkich pozostałych bierek, ponieważ dopuszczenie do jego zbicia to mat, czyli porażka. W praktyce często stosuje się wielokrotności tych wartości, co pozwala uwzględnić dodatkowe czynniki, jak pozycja bierki, możliwość wykonania roszady itp. [4, 9].

W komercyjnych programach do gry w szachy stosuje się bazy tzw. otwarć i końcówek. Są to bazy danych opracowane głównie na podstawie rozgrywek na poziomie arcymistrzowskim. Ich stosowanie ułatwia wyznaczanie ruchów w początkowej i końcowej fazie gry. Program FXChess XF nie wykorzystuje tych baz, ponieważ w większości są one udostępniane odpłatnie. Aby zachęcić program do zdobywania przewagi w środku pola, co jest zgodne ze sposobem rozgrywania partii przez arcymistrzów szachowych, wartości poszczególnych bierek uzależniono od ich pozycji na szachownicy. Przykładowo, ruch pionem ustawionym przed królem, jest ceniony wyżej niż ruch pionem ustawionym przy krawędzi szachownicy. Jednocześnie wartość pionów wzrasta wraz z ich przemieszczaniem do przodu. Ta dodatkowa motywacja ma na celu zdobycie możliwie największego obszaru na szachownicy, szczególnie w jej centrum i zachęcanie programu do promocji pionów, czyli ich zamiany na figury po dojściu do ostatniego rzędu.

Podczas przeszukiwania drzewa bardzo często dochodzi do powtarzania się jednakowych pozycji bierek na szachownicy w różnych węzłach drzewa. Jeżeli jakaś sytuacja została już rozpatrzona na odpowiednią głębokość i znany jest wynik tego przeszukiwania, to można zrezygnować z ponownego przeszukiwania tej gałęzi. Powstaje zatem problem zapamiętywania ustawień bierek na szachownicy. W tym celu stosuje się tak zwane hasze (ang. hash code – skrót). Najważniejszą cechą haszy jest ich unikatowość. Ze względu na ograniczenia czasowe, w praktyce stosuje się hasze krótsze od wymaganych, które nie zapewniają pełnej unikatowości. Dopuszczają one możliwość nadania różnym sytuacjom jednakowego kodu, co grozi błędami w analizie drzewa gry, jednak ryzyko z tym związane jest niewielkie.

Najbardziej znaną metodą haszowania jest zaimplementowana w programie metoda Zobrista. Swą popularność zawdzięcza prostocie i wydajności. Polega na tym, że w każdym ruchu można wykonać zmianę stanu maksymalnie jednej bierki każdego z graczy. Najpierw obliczany jest hasz początkowy drzewa gry, a następnie wykonywane są operacje XOR z wartościami hasza dla bierek w aktualnej i poprzedniej pozycji. Taki sposób wykorzystano również w omówionym programie.

Tablice bitowe

Dla zwiększenia wydajności programu zastosowano szachownice bitowe (ang. bitboards). Technika ta zyskała największą popularność po wprowadzeniu na rynek maszyn 64-bitowych. Pozwala na stosowanie reprezentacji szachownicy jako szeregu liczb 64-bitowych. Sprawdzanie szacha, możliwości wykonania bicia i generowanie ruchów są operacjami bardzo szybkimi, gdyż sprowadzają się do kilku prostych operacji binarnych.

Konstrukcja mechaniczna oraz układ sterowania robota zostaną omówione w kolejnych publikacjach na łamach Forum Młodych.

Bibliografia

1. Gruszka R., Hnatiuk M.: Ramię robota do gry w szachy z układem sterowania. Praca dypl. Politechnika Opolska 2009.
2. Galeczka K., Gawlik K.: Wykonanie chwytaka i modułu komunikacyjnego robota do gry w szachy. Praca dypl. PO 2009.
3. Friedel F.: A short history of computer chess. 1997.
4. Beowulf Computer Chess Engine.
5. Kupczyk M.: Szachownica robota do gry w szachy z układem rozpoznawania ruchu. Praca dypl. PO 2009.
6. Tomczewski M.: Implementacja inteligentnych szachów komputerowych z zastosowaniem znanych algorytmów sztucznej inteligencji. Praca dypl. PO 2006.
7. Winston P. H.: Artificial intelligence. Addison Wesley, 1992.

• • • • • Część 2 • • • • • Część 3

Krzysztof Gawlik, Radosław Gruszka, Krzysztof Galeczka, Marcin Hnatiuk, Marcin Kupczyk,
Michał Tomczewski, dr inż. Krzysztof Tomczewski – SKN Spektrum