Krzemowy arcymistrz

Swego czasu Garri Kasparow powiedział, że "jest ostatnim człowiekiem-mistrzem świata w szachach" - następnym będzie komputer. Część tej prognozy sprawdziła się dość szybko, choć nie ma to nic wspólnego z komputerami, a wynika z rozłamów do jakich doszło wśród szachowej elity arcymistrzów.

Swego czasu Garri Kasparow powiedział, że "jest ostatnim człowiekiem-mistrzem świata w szachach" - następnym będzie komputer. Część tej prognozy sprawdziła się dość szybko, choć nie ma to nic wspólnego z komputerami, a wynika z rozłamów do jakich doszło wśród szachowej elity arcymistrzów.

Pisanie programów grających w szachy jest klasycznym wyzwaniem dla informatyków od początku istnienia maszyn cyfrowych. W każdej dziedzinie człowiek wyznacza sobie zadania, które wydają się być granicą ludzkich możliwości w danej chwili.

Dla konstruktora robotów celem takim jest zbudowanie urządzenia grającego w tenisa stołowego. Automat ów powinien dokonywać niebywałych wyczynów: śledzić lot piłeczki, w ułamku sekundy dokonywać skomplikowanych obliczeń przetwarzanych na ruchy rakietki, uruchamiać niezliczone mechanizmy umożliwiające przemieszczanie się, czyli robić to wszystko co potrafi każdy gracz z krwi i kości. Współczesny pingpongista musiałby szukać takich maszyn w trudno dostępnych laboratoriach. Inaczej rzecz ma się z szachami. Tutaj używanie komputera jest niemal obowiązkowe, a dobre programy są dostępne dla każdego zainteresowanego.

Przeciętny gracz-amator musi nieźle napocić się, aby stawić czoła popularnym programom typu Fritz czy ChessGenius, zajmującym raptem kilkaset kB na dysku. Potentat na rynku szachowych mikrokomputerów, niemiecka firma Mephisto, gwarantuje, że jej najlepsze produkty grają na poziomie zawodnika klasy mistrza krajowego (cena: 1-2 tys. USD).

Czy krzemowe układy ożywiane impulsami elektrycznymi mogą mierzyć się z inteligencją szarych komórek? Tam, gdzie istnieją jednoznaczne reguły wnioskowania, maszyny cyfrowe konkurują z człowiekiem. Medyczny system ekspertowy MYCIN na podstawie wyników badań jest w stanie postawić nie gorszą diagnozę w zakresie chorób krwi niż wysokiej klasy specjalista. Kłopoty zaczynają się jednak wtedy, gdy problem jest trudny do określenia. Jak zakodować w postaci bitów czy bajtów wyraz oczu pacjenta, z których zawodowa intuicja lekarza potrafi odczytać, że chodzi o coś więcej niż o zwykłe przeziębienie? Królewska gra jest jednak ściśle zdefiniowana. Komputery mają tu więc swoją szansę. Ich siłą jest wszak szybkość. Wystarczy sprawdzić wszelkie możliwe kombinacje dla danej pozycji na szachownicy i rozwiązanie, w postaci optymalnego ruchu, gotowe. Nie jest to jednak takie proste.

Szachy a informatyka

Przeciętna partia składa się średnio z 30-40 posunięć. Tymczasem liczba możliwych sytuacji na szachownicy, jakie mogą powstać po dziesięciu posunięciach jest większa, niż liczba atomów w naszej galaktyce. Komputer z konwencjonalnym programem musiałby pracować dosłownie wieki, aby dokonać tak wielu obliczeń. Mimo to przodujące firmy software'owe, wykorzystując najnowsze zdobycze techniki, nieustannie poprawiają swoje programy tak, żeby mogły stawić czoła najlepszym graczom.

Działania takie nieraz wzbogacają teorię szachów. I tak specjaliści z laboratoriów AT&T (Bell Labs) wykazali, że w najgorszym przypadku trzeba co najmniej 67 posunięć, aby dwa gońce dały mata królowi ze skoczkiem. Podobne analizy przeprowadzono także dla innych końcówek z pięcioma figurami.

Komputerowe szachy mają także wpływ na rozwój informatyki: przyczyniają się do powstawania nowych algorytmów, głównie z zakresu teorii grafów, pozwalają na badania wydajności konfiguracji hardware'owych z dużą liczbą procesorów pracujących równolegle. Wystarczy spojrzeć na długą listę problemów naukowych i technicznych, które da się sformułować w kategoriach teoriografowych, aby docenić znaczenie badań w tej dziedzinie: od przeszukiwania struktur drzewiastych do znajdowania dróg i mnożenia macierzy. Algorytmy te są wykorzystywane niemal w każdym programie (listy, sortowanie, rekursja) a z całą pewnością w każdym komputerze, bowiem bez nich nie byłoby możliwe sprawne działanie systemu operacyjnego (teoria kolejek) czy zarządzanie pamięcią (podczas badań nad szachami udoskonalono znany od 30 lat tzw. algorytm "hash-transposition"). Interdyscyplinaryzm i tutaj więc święci triumfy.

Geniusz wszechczasów

Niewątpliwie jednak ważnym motorem tych badań są kwestie prestiżowe. Zapewne więc względy reklamowe powodują też, że firma IBM inwestuje drogie osobo-lata pracy programistycznej w projekt o nazwie "Deep Thought" (DT).

Jego początki datują się na 1986 r., kiedy to pracownicy Uniwersytetu Carnegie Mellona w Pittsburghu skonstruowali komputer szachowy z wykorzystaniem stacji roboczej Sun 3/160. Idea lidera grupy, genialnego doktora Feng Hsiung Hsu, polegała na skonstruowaniu specjalnego układu scalonego, który mógł być zastosowany jako generator (engine) posunięć szachowych. Pierwszy, skonstruowany przez nich, model pozwalał na analizę ok. 50 tys. pozycji w ciągu sekundy, tj. 10 razy więcej niż konkurencyjne software'owe rozwiązania. W ten sposób udało przerzucić się ciężar obliczeń z oprogramowania na sprzęt i uzyskać dużą szybkość analizy.

Przed pięcioma laty Deep Thought po raz pierwszy zdobył mistrzostwo świata w kategorii komputerów stacjonarnych analizując wtedy ok. miliona pozycji/s. Wtedy właśnie cała grupa naukowców została zatrudniona przez IBM z budżetem na prowadzenie badań w wysokości 1 mln USD rocznie.

Kolejna udoskonalona wersja systemu z 1992 r. składała się z 24 procesorów połączonych z centralnym procesorem POWER-6000 (Performance Optimization With Enhanced RISC), który ściśle rzecz biorąc był układem złożonym z trzech specjalizowanych procesorów i analizował 10 mln pozycji/s.

Aktualnie IBM testuje najnowszą wersję konfiguracji zdolnej do analizy ponad miliarda pozycji/s przy użyciu 1 tys. procesorów. Oprogramowanie stanowiące ok. 90 tys. linii kodu w języku C opiera się na prostej idei "brute force", czyli systematycznej (z zastosowaniem metody backtrackingu) oceny wszelkich możliwych kombinacji tzw. drzewa wariantów pozycji. Niewiele ma to wspólnego z oprogramowaniem "sztucznej inteligencji" o co zwykło się posądzać programy szachowe. Owszem, DT korzysta z wielu "inteligentnych" algorytmów, takich jak Forward Pruning czy Singular Extension, celem ich jest wszakże jedynie zwiększenie prędkości przeszukiwania drzewa kombinacji do określonej głębokości - w praktyce do 10-15 posunięć w zależności od liczby figur na szachownicy.

Obecnie siłę "Deep Thought" szacuje się na 2700 punktów ELO, co daje mu miejsce w pierwszej dziesiątce najlepszych szachistów świata. Umiejętność przewidywania na więcej niż 15 ruchów do przodu zapewne wystarczy by wygrać także z mistrzem świata. To właśnie jest celem projektu IBM.

Kto wygra?

Jak zwykle w takich sytuacjach prognozy są podzielone. Jedna grupa uważa, że coraz szybsze układy elektroniczne i doskonalsze algorytmy spowodują, że człowiek będzie musiał ulec maszynie, która jest w stanie zmagazynować również wiedzę dotyczącą otwarć szachowych. Inne przewidywania mówią, że ludzie ucząc się także od komputerów będą w efekcie dominować nad programami, które w końcu sami tworzą. Być może to co zobaczymy w następnych latach będzie wariantem pośrednim, tzn. zarówno zawodowi gracze, jak i profesjonalne programy osiągną tak wysoki poziom, że szachy przestaną pasjonować, skoro w każdej sytuacji z góry będzie wiadomo, jaki ruch jest optymalny. Póki co jednak: szach komputerowi!


TOP 200