poniedziałek, 11 czerwca 2012

Szachy i komputery (16) - autor Wojtek Żuchowski


Superkomputery szachowe

Superkomputer szachowy to klaster wyposażony we własne oprogramowanie i rozwiązania sprzętowe stworzone specjalnie do gry w szachy. Obecnie jedynym aktywnym superkomputerem szachowym jest Hydra.
Początkowo do gry w szachy wykorzystywano autorskie programy działające na superkomputerach ogólnego przeznaczenia. Przykładem takiego programu był Chess, powstały w latach 70., który działał na komputerach firmy Control Data Corporations. W 1977 roku wersja 4.5 uzyskała w turnieju z udziałem ludzi wynik 2271 (najniższy tytuł międzynarodowy, mistrza FIDE, wymaga rankingu 2300).
Innym programem przeznaczonym na superkomputery, w tym przypadku Cray firmy Cray Research, która w 1980 roku zapewniła finansowanie projektu, był Cray Blitz, wywodzący się z programu Blitz. Jego następcą jest działający na domowych komputerach, ciągle rozwijany darmowy Crafty.
Pierwszym komputerem przeznaczonym wyłącznie do gry w szachy był Belle, rozwijany w latach 70. i 80. przez Kena Thompsona. Zawierał kilkaset układów obliczeniowych, w tym specjalizowane, i mógł przetwarzać 160–180 tysięcy pozycji na sekundę (kilkadziesiąt razy więcej od ówczesnych superkomputerów ogólnego przeznaczenia), co w praktyce oznaczało głębię ośmiu – dziewięciu półruchów. To pozwoliło mu pokonać w 1982 roku na North American Computer Chess Championship Cray Blitza działającego na nieporównanie droższym sprzęcie. Wciąż jednak siła gry była niższa od poziomu utytułowanych graczy.
Silniejszy był HiTech, zbudowany na uniwersytecie Carnegie Mellon w pierwszej połowie lat 80. Zawierał 64 jednostki obliczeniowe i specjalnie zaprojektowany generator posunięć. Jako pierwszy pokonał arcymistrza, choć ten miał wówczas ranking około 2300 punktów, czyli 200 poniżej dolnej granicy wymaganej do tytułu. Innym projektem rozwijanym w tym czasie na uniwersytecie Carnegie Mellon był komputer ChipTest, który dał początek sławnemu Deep Blue.
Pierwszym naprawdę silnym typowo szachowym superkomputerem był Deep Thought, który w 1989 roku przegrał obie partie w minimeczu z Garrim Kasparowem. Jego poprzednikiem był ChipTest, stworzony w 1985 roku przy udziale tego samego człowieka, Feng-hsiung Hsu, a następcą – sławny Deep Blue.
ChipTest wykorzystywał autorski projekt obliczającego posunięcia układu typu VLSI (ang. Very-large-scale integration) i był sterowany stacją roboczą Suna. Jego prędkość wynosiła początkowo 50 tysięcy pozycji na sekundę. W 1987 roku zmienił nazwę na ChipTest-M, a jego prędkość wzrosła do 500 tysięcy pozycji na sekundę. W 1998 roku na podstawie ChipTesta powstała pierwsza wersja Deep Thought, wykorzystująca dwa wspomniane układy, która wkrótce, jako wersja 0.02, osiągnęła prędkość 720 tysięcy pozycji na sekundę.
W 1989 roku Feng-hsiung Hsu i Murray Campbell, współtwórca ChipTesta, zostali zatrudnieni przez IBM z zadaniem zbudowania jeszcze lepszej maszyny, która mogłaby powalczyć ze ścisłą czołówką szachistów. Deep Thought pod znakiem IBM-a, kiedy grał z Kasparowem, wykorzystywał trzy dwuprocesorowe układy VLSI i też działał pod kontrolą stacji roboczej Suna. Był zdolny ocenić dwa miliony pozycji w ciągu sekundy.
W 1991 roku powstała druga wersja Deep Thought, działająca na komputerze z serii 6000 IBM-a, której dodano następnych 18 procesorów szachowych, co pozwoliło osiągnąć wydajność sześciu – siedmiu milionów pozycji na sekundę.
W 1993 roku Deep Thought został przemianowany na Deep Blue. W 1996 roku rozegrano pierwszy ze sławnych pojedynków między Deep Blue a ówczesnym mistrzem świata Garrim Kasparowem. Wtedy Deep Blue działał z prędkością 100 milionów pozycji na sekundę dzięki 32 procesorom komputera serii 6000, którym towarzyszyły 32 karty z procesorami VLSI, po sześć na każdej (łącznie 192). Deep Blue wygrał pierwszą partię, aby przegrać cały mecz.
Rok później Deep Blue działał już z prędkością 200 milionów pozycji na sekundę. Miał 256 procesorów VLSI (po osiem na każdej z 32 kart towarzyszących dwukrotnie szybciej taktowanym niż rok wcześniej, 400-megahercowym procesorom Power Two Super Chip IBM-a, wyposażonym w czterokrotnie większą od poprzednika ilość pamięci podręcznej trzeciego poziomu) i był dużo bogatszy w szachową wiedzę (głównie za sprawą arcymistrza Joela Benjamina). Sterował nim program działający pod kontrolą systemu AIX. W rewanżu z Kasparowem Deep Blue pokonał mistrza jednym punktem. (O kontrowersjach związanych z tym meczem mogliście przeczytać w osobnym rozdziale).
Co zdecydowało o sukcesie Deep Blue? Jeśli pominąć fatalną grę zniechęconego Kasparowa w ostatniej, decydującej partii i to, że mistrz świata przegapił szansę na wymuszenie remisu w drugiej, a także założyć, że w tej drugiej partii nie nastąpiła ingerencja człowieka (pisałem o tym w rozdziale poświęconym stylowi, więcej przeczytacie w rozdziale o pojedynkach człowiek kontra maszyna) – przede wszystkim była to moc obliczeniowa, ale także nowe algorytmy oceny pozycji (m.in. na podstawie materiału, temp i bezpieczeństwa króla) wzbogacone zaprogramowaną wiedzą szachową oraz funkcja określana jakoselective extensions, pozwalająca obliczać tylko wybrane warianty i odrzucać te najmniej obiecujące lub ewidentnie błędne (choć działanie Deep Blue było silnie oparte na metodzie brutalnej siły). I oczywiście poprawki zwykłych błędów znalezionych w pierwszej wersji.
Funkcja oceny pozycji sama „nauczyła” się odpowiednich parametrów dzięki analizie tysięcy partii.
Książką otwarć zajęli się przede wszystkim arcymistrzowie: Joel Benjamin, John Fedorowicz i Nick de Firmian. Stworzono ją na podstawie 600 tysięcy partii na wysokim poziomie. Ponadto Deep Blue był wyposażony w stworzone przez Kena Thompsona tablice końcówek dla pięciu bierek i wybrane tablice dla sześciu.
Po zwycięstwie z Kasparowem Deep Blue został wycofany z użycia – spełnił swoją rolę jako poligon doświadczalny i narzędzie marketingowe.
Przez kilka następnych lat w szranki z najlepszymi szachistami stawały coraz bardziej „inteligentne”, ogólnodostępne programy szachowe, takie jak Deep Fritz i Deep Junior. Następnym superkomputerem szachowym na miarę Deep Blue była Hydra.
Hydra powstała w 2004 roku na podstawie projektu „Brutus”, nad którym prace rozpoczęły się w październiku 2000 roku. Pomysłodawcą był Ken Thompson, twórca jednego z pierwszych komputerów szachowych, Belle. Przekonał on do swojego projektu firmę ChessBase, która do jego realizacji wybrała dr. Christiana Donningera. Hydra znajduje się w Abu Dhabi w Zjednoczonych Emiratach Arabskich (podczas turniejów i meczów jest sterowana przez internet), a jej rozwój jest sponsorowany przez PAL Group. Jest skonstruowana podobnie jak Deep Blue: jako klaster podstawowych procesorów i specjalizowanych układów (Xilinx Vertex II Pro), sterowanych autorskim oprogramowaniem. Od początku w planach było kilka wersji Hydry: Orthus, Chimera, Scylla i „właściwa” Hydra. Najsilniejsza dotąd wersja składała się z 64-procesorowego klastra (opartego na układach Xeon Intela) wyposażonego w specjalizowane jednostki na kartach FPGA i łącznie 64 GB RAM-u. Wydajność tej wersji w obliczeniach szachowych była zbliżona do ostatniej wersji Deep Blue, wynosiła około 200 milionów pozycji na sekundę, z tym że efektywność wybierania wariantów do liczenia i oceny pozycji była znacznie większa.
Obecnie oficjalnie działają wersje Chimera i Scylla. Na Chimerę składa się 16 procesorów Intel Xeon 3,06 GHz wspomaganych przez specjalizowane układy na kartach FPGA i łącznie 32 GB RAM-u. Scylla to 16 węzłów wyposażonych w dwa lub cztery procesory Intel Xeon 3,6 GHz, również wspomagane specjalizowanym układami na kartach FPGA, unowocześnionymi w stosunku do słabszej wersji, i łącznie 64 GB RAM-u. (Dodatkowy węzeł zarządza pozostałymi 16). Ponadto Scylla działa pod kontrolą udoskonalonego w porównaniu z Chimerą oprogramowania.

Brak komentarzy:

Prześlij komentarz