KASPAROW vs. DEEP BLUE – narodziny SI?

0
40

W roku 1996 naprzeciwko siebie przy szachownicy zasiedli arcymistrz szachowy Garri Kasparow i pretendent do tytułu komputer Deep Blue. Deep Blue wygrał jedną z partii, w całym meczu odnosząc jednak porażkę. Odnotowana została pierwsza oficjalnie wygrana partia szachowa przez maszynę z aktualnym mistrzem świata. W roku 1997 doszło do rewanżu. Cały mecz zakończył się tym razem zwycięstwem Deep Blue – zaczęto anonsować nadejście nowej ery.

 

Maszyny grają w szachy

Pragnienie zbudowania myślącej maszyny, potrafiącej grać w szachy, istniało od dawna. Jeśli bowiem udałoby się nauczyć maszynę gry w szachy, wówczas także inne kwestie wymagające udziału ludzkiej inteligencji można by powierzyć urządzeniom.

Owo pragnienie było na tyle silne, że skłaniało nawet do mistyfikacji i oszustwa. W roku 1769 Wolfgang von Kempelen przedstawił konstrukcję, w której mechanizmach ukryty był człowiek dokonujący za pomocą dźwigni odpowiednich posunięć na szachownicy. “Mechaniczny Turek”, choć nie opierał się na działaniu Sztucznej Inteligencji, trzeba przyznać, był i tak nadzwyczaj precyzyjną i skomplikowaną konstrukcją. Charles Babbage (angielski matematyk, twórca tablic logarytmicznych) pod koniec pierwszej połowy XIX wieku rozważał hipotetyczne sposoby nauki gry w szachy, jakie należałoby zastosować w przypadku jego maszyny liczącej Analytical Engine. W roku 1912 Leonardo Torres y Quevedo zaprezentował maszynę potrafiącą rozwiązywać na szachownicy sytuacje typu król-wieża-król (automat miał do dyspozycji króla i wieżę, przeciwnik posiadał tylko króla). Z powodu zastosowania uproszczonego algorytmu obliczającego możliwe posunięcia, “El Ajedrecista” nie grał zbyt precyzyjnie i nie zawsze kończył partię w minimalnej ilości ruchów, choć zawsze udawało mu się dać przeciwnikowi mata. Jednak dopiero postępująca komputeryzacja mogła pozwolić na bardziej realne plany skonstruowania tego rodzaju urządzenia. 

Algorytmy szachowe tworzone z myślą wykorzystania przez powstające wówczas maszyny liczące zaczęły być projektowane w latach 50. Jednym z najbardziej interesujących, choć obecnym jeszcze jedynie na papierze, był algorytm Alana Turinga (nigdy nie był testowany z braku odpowiedniej maszyny liczącej). Kolejny algorytm z 1952 roku autorstwa Dietrich’a Prinz’a był pierwszym działającym na komputerze programem szachowy, z tym, że jego umiejętności ograniczały się jedynie do wyszukiwania pozycji dającej mata w dwóch posunięciach. Przełomowy był amerykański algorytm z 1958 roku – pierwszy w pełni funkcjonalny program do gry w szachy, choć, przyznać trzeba, jeszcze na bardzo niskim poziomie. Możliwości komputerów rosły, trzeba było jednak poczekać do roku 1983, aby program Belle jako pierwszy osiągnął poziom mistrza szachowego. W drugiej połowie lat osiemdziesiątych komputer HiTech stoczył kilka zwycięskich pojedynków z mistrzami szachowymi. Dopiero jednak rywalizacja z Deep Blue zakończyła się porażką aktualnego szachowego arcymistrza w warunkach turnieju szachowego.

Szachowe pojedynki człowieka z maszyną są dziś powszechne. Istnieje ogromna liczba programów pozwalających przeprowadzić taką rozgrywkę na dowolnym poziomie trudności. Wystarczy zwykły komputer osobisty by doświadczyć słodyczy zwycięstwa ludzkiej inteligencji, albo przeżyć gorycz porażki w starciu z urządzeniem, zależnie od umiejętności gracza. Wszystko w ramach zabawy i rozrywki.

 

Szachowe algorytmy

Współczesne programy szachowe opierają się na tzw. algorytmie min-max – ponieważ trudno o tak potężne jednostki obliczeniowe potrafiące przeprowadzić analizę wszystkich możliwych kombinacji posunięć figur i pionów w regulaminowym czasie szachowej rozgrywki (wystarczająco szybko do zastosowania algorytmu typu “brute force”, czyli techniki polegającej na sprawdzeniu wszystkich możliwych kombinacji). W praktyce algorytm tworzy drzewo możliwych posunięć jedynie do pewnej głębokości, analizuje te ruchy przewidując sytuacje po ich wykonaniu i przeprowadza jego zdaniem najbardziej optymalne posunięcia. Ponieważ liczba możliwych kombinacji w tym przypadku i tak jest bardzo duża, algorytmy stosują różne metody ograniczające obszar analizy (głębokości drzewa). Najbardziej popularną metodą jest przeszukiwanie alfa-beta, w którym pod uwagę nie są brane kombinacje będące opcją gorszego posunięcia od poprzedniej analizowanej sytuacji. Inny sposób określany jest mianem iteracyjnego pogłębiania i polega na analizie drzewa gry do pewnej głębokości, wybraniu najbardziej obiecujących ruchów i poddaniu analizie tylko tych konkretnych posunięć, aż do znalezienia jednego najbardziej korzystnego posunięcia. Takie metody optymalizacji skutecznie eliminują najmniej pożyteczne kombinacje ruchów. 

Ważnym elementem algorytmu jest funkcja oceny pozycji. Nie ma możliwości absolutnej oceny pozycji gdyż to wiązałoby się z analiza wszystkich możliwych kombinacji ruchów. Dlatego jej ocena pozostaje zawsze przybliżona. Funkcja analizuje kilka parametrów. Jednym z nich jest przewaga materialna (piony i figury mają swoje wagi). Duża przewaga materialna to wysokie prawdopodobieństwo zwycięstwa. Innym jest przewaga pozycyjna związana z układem figur na szachownicy.

Większość programów na początku rozgrywki używa przygotowanej wcześniej tzw. książki otwarć, wykazu zawierającego typowe zagrania i odpowiedzi dla niewielkiej liczby ruchów początkowych.

Kolejną metodą optymalizacji jest tzw. baza końcówek – zbiór rozwiązań partii, w których na planszy pozostała określona, niewielka liczba figur. W tym przypadku istnieje możliwość obliczenia wszystkich wariantów aż do zakończenia rozgrywki. Napotykając taką sytuację algorytm uzyskuje pewność jej oceny i nie musi już przeprowadzać czasochłonnych obliczeń pozycji z zastosowaniem heurystyki.

Algorytmy szachowe nie są najtrudniejszymi do zaprojektowania programami służącymi różnego rodzaju rozgrywkom (znacznie bardziej skomplikowane są algorytmy do gry w shōgi czy go). Szachy wydawały się być jednak skutecznym miernikiem i dobrym poligonem, na którym testować można różne “myślące systemy” mające znamiona “inteligencji”.

 

Deep Blue – “inteligentna” maszyna

Deep Blue, komputer mogący w ciągu sekundy wykonać analizę 200 milionów zagrań był efektem projektu ChipTest, który rozpoczął się w Carnegie Mellon University wraz z projektem Deep Thought realizowanym przez informatyka Feng-hsiung Hsu. Prace badawcze Feng-hsiung Hsu nad problemami obliczeń rozproszonych (współdzielonych zasobów obliczeniowych), już pod kierownictwem IBM, zaowocowały powstaniem tego superkomputera.

Deep Blue używał 32 węzłowego klastra IBM RS/6000 SP – po 8 procesorów zaimplementowanych w każdym węźle (256 procesorów wielkiej skali integracji). Algorytm, którym posługiwał się Deep Blue napisany został w języku C i pracował w systemie operacyjnym AIX (odmiana systemów Unixowych). Ogromna moc komputera pozwalała systemowi prowadzić rozgrywkę głównie w oparciu o siłowe (“brute force”) metody przeszukiwania. Parametry (związane z tzw. funkcją oceny) wprowadzone były do systemu w uogólnionej formie – ich optymalne wartości zostały wyliczone przez sam system na podstawie analizy tysięcy mistrzowskich partii szachowych. Baza danych systemu została  przed drugim pojedynkiem wzmocniona przez arcymistrza Joela Benjamina. Arcymistrzowie Miguel Illescas Cordoba, John Fedorowicz i Nick De Firmian odpowiedzialni byli za bibliotekę otwarć dla systemu, w której znalazło się ponad 4000 pozycji i 700 000 rozegranych arcymistrzowskich partii. 

 

Kulisy porażki

Jak wskazują analitycy spotkania, kluczem do sukcesu komputera mógł okazać się pojedynczy ruchu zrealizowany przez maszynę w pierwszej partii meczu. Deep Blue wykonał wówczas posunięcie wskazujące na zamysł jakiejś wyrafinowanej strategii. Ruch był zaskakujący – Kasparow zaś zdumiony. 

Druga partia tego pojedynku okazała się kluczowa. Kasparow, jak stwierdzili obserwatorzy spotkania, najwyraźniej rozkojarzony nietuzinkowym zagraniem komputera w pierwszej odsłonie meczu, zaczął grać ostrożnie i pozwolił zepchnąć się do defensywy. Stosowana przeciwko wielu przeciwnikom taktyka w tym przypadku nie powiodła się. Odpowiedź Deep Blue na próbę wciągnięcia go w pułapkę określona został jako oszałamiająca i wyjątkowa.  Zirytowany Kasparow poddał partię. Pomeczowa analiza wykazała jednak, że arcymistrz popełnił błąd – w momencie kiedy Kasparow zdecydował się poddać pojedynek, partia była remisowa. Nerwy wzięły górę. Do końca meczu nie zdołał się już pozbierać i w efekcie przegrał pojedynek 2,5 do 3,5. 

Po zakończeniu rozgrywki stwierdził (nie bez ironii), że taki styl gry musi być przejawem jakiejś “wyższej inteligencji”. Twierdząc, iż niektóre posunięcia był zbyt skomplikowany dla maszyny, sugerował ludzką interwencję. Atmosferę od samego początku podgrzewało kierownictwo IBM, które odmawiało wglądu do komputerowych logów obrazujących „sposób myślenia” urządzenia, o które Kasparow prosił od samego początku pojedynku. W pomeczowych wywiadach Kasparow niejednokrotnie dawał do zrozumienia, iż czuje się oszukany, że podczas rozgrywki doszło do czegoś dziwnego i nieregulaminowego, że przeciwnik w poszczególnych partiach grał inaczej, że jego styl nie dawał się określić – Kasparow wydawał się być przekonany o ingerencji czynnika ludzkiego w kluczowych momentach pojedynku.

Z kim zatem przegrał Kasparow? Z maszyną? Z korporacją? Z “Mechanicznym Turkiem”?Specjaliści prowadzący analizę pojedynku byli zdania, iż Kasparow przegrał z emocjami. Maszyna nie ulega presji, nie panikuje, nie rezygnuje, nie czuje się oszukana. „Myślenie” Deep Blue nie było stylowe ani osobliwe. Polegało na liczeniu. Maszyna przelicza bowiem ogromną liczbę różnych możliwych kombinacji, i taki styl „myślenia” sprawdza się doskonale właśnie podczas gier, gdzie występuje niewiele parametrów (32 figury) i skończona (choć bardzo duża) liczba kombinacji. 

A zagadkowy ruch wykonany pod koniec pierwszej partii? W istocie zespół IBM nie ukrywał, iż modyfikował algorytm na bieżąco pomiędzy rozgrywanymi partiami. Wszystko po to, aby maszyna mogła lepiej „czuć” styl gry Kasparowa. Jednak większość czynności dotyczyła podobno naprawy pewnego błędu powstałego w implementacji oprogramowania. 15 lat po zakończeniu pojedynku,  jeden z architektów Deep Blue, Murray Campbell, twierdził, że ów niezwykle subtelny ruch był wynikiem właśnie owego błędu. Konsekwencje błędu polegały na tym, iż komputer nie mogąc zdecydować się na optymalne posunięcie, przy kończącym się czasie, wybrał po prostu zagranie losowo z puli możliwych rozwiązań. Ruch był zatem wynikiem przypadku. Czy taka jest geneza owego wyrafinowanego zagrania z pierwszej partii meczu? Zadecydować miał błąd w oprogramowaniu? Ludzki błąd doprowadzić miał do zwycięstwa maszyny?… 

 

Symbolika pojedynku

Zasadnie, czy nie, dzień zwycięstwa Deep Blue stał się symbolicznym początkiem czasów myślącej maszyny. Choć już wcześniej zdarzyło się komputerowi wygrać w szachy z człowiekiem, choć algorytm wykorzystywany w pojedynku z Kasparowem był w swym charakterze algorytmem “brute force” i nie miał nic wspólnego z metodami typu “deep learning”, rozwijanymi dekadę później i charakterystycznymi dla systemów Sztucznej Inteligencji, choć nawet jeden z projektantów algorytmu głośno wyrażał opinię, iż w ogóle nie należy określać go mianem “inteligentny” – symbolika wydarzenia stała się jednak nad wyraz wymowna. Po latach Kasparow wspominając swój udział w przedsięwzięciu konkludował: “Myślę, że to jednak błogosławieństwo, przecież nie każdy ma okazję zostać częścią historii”.