Algorytmika. Rzecz o istocie informatyki (2)
Oto następny fragment książki Davida Harela, która w przekładzie Piotra Carlsona i Zbigniewa Weissa ukaże się nakładem Wydawnictw Naukowo–Technicznych.
Gry
Przejście testu Turinga wydaje się być dobrym warunkiem koniecznym posiadania przez komputer pełnej, takiej jak ludzka, inteligencji. Jednak, jak już wspomniano, komputery nie mają szans przejścia przez ten test i prawdopodobnie tak już będzie w dającej się przewidzieć przyszłości, musimy zatem zadowolić się skromniejszymi oczekiwaniami. Większość badaczy sztucznej inteligencji zajmuje się, ogólnie mówiąc, jedną z następujących działalności: (1) próbami wyjaśnienia, w jaki sposób ludzie uczą się, rozumieją, wnioskują i robią plany, oraz (2) próbami obdarzenia komputerów zdolnością inteligentnego zachowania się w bardzo wąskich dziedzinach. Zajmując się pierwszą z tych działalności, badacze ci bliżsi są psychologom i neurobiologom niż matematykom i informatykom. Nas interesują tutaj bardziej wysiłki drugiej grupy.
Jedną z wyspecjalizowanych dziedzin, w których badacze sztucznej inteligencji osiągnęli znaczące wyniki, są gry. Omawianie tego zagadnienia warto chyba rozpocząć od krótkiego przeglądu wiadomości.
· W roku 1979 program komputerowy pokonał mistrza świata w tryktraka. Program ten nie został jednak nowym mistrzem, gdyż gra nie odbywała się na oficjalnych zawodach, niemniej jednak wygrana jest wygraną. Mecz w tryktraka składa się z wielu pojedynczych rozgrywek, tak że czynnik losowy wprowadzony przez rzucanie kostką jest zminimalizowany i w rzeczywistości dominuje jakość gry.
· Są programy grające wyjątkowo dobrze w warcaby; pokonują one z reguły swoich twórców. Ponadto niektóre programy są skonstruowane tak, że — podobnie jak człowiek — uczą się na własnych błędach, osiągając coraz lepsze wyniki.
· Niektóre programy grające w szachy uzyskały tytuł mistrzowski. Jeden z nich w grach turniejowych zdobył aż 2363 punkty rankingowe! Arcymistrzowie potrafią jednak te programy pokonać i jak na razie tytułu mistrza świata programowi komputerowemu przyznać nie możemy. Ostatnio nowe programy szachowe działające na małych, specjalnych komputerach pokonują uważane za najlepsze na świecie programy szachowe wykonywane na bardzo dużych komputerach.
Dlaczego programy nie potrafią grać perfekcyjnie w szachy czy warcaby, a zatem pokonywać w grze ludzi? Dlaczego komputer nie może przejrzeć możliwych ruchów i wybrać najlepszego? Odpowiedź tkwi w drzewach gry. Na przykład w grze w kółko i krzyżyk nie ma żadnych trudności. Pierwszy gracz ma dziewięć możliwych ruchów, na które jego przeciwnik może odpowiedzieć na jeden z ośmiu sposobów, na które z kolei pierwszy gracz może odpowiedzieć na jeden z siedmiu sposobów itd. Drzewo gry składa się zatem z korzenia mającego dziewięć następników, z których każdy ma osiem następników itd. Niektóre wierzchołki w tym drzewie są kończące, co znaczy, że reprezentują albo zwycięstwo jednego z graczy, albo wypełnioną tabliczkę bez zwycięzcy. W każdym przypadku dowolna sekwencja dziewięciu ruchów prowadzi do wierzchołka kończącego. Drzewo ma zatem maksymalną głębokość 9 z maksymalnym stopniem rozgałęzienia 9 w korzeniu. Ogółem nie ma więcej niż 9!, czyli 362 880 możliwości do sprawdzenia, można więc łatwo napisać program grający perfekcyjnie w kółko i krzyżyk.
Z szachami natomiast jest całkiem inna historia. Białe mają 20 możliwych pierwszych posunięć, a średnia liczba możliwych następnych posunięć w dowolnej pozycji szachowej wynosi około 35. Stopień rozgałęzienia drzewa wynosi więc średnio około 35. Głębokością drzewa jest liczba posunięć (dwukrotnie większa niż liczba kolejek w grze), która może łatwo osiągnąć 80 do 100. Oznacza to, że liczba możliwości, które należy sprawdzić w typowej grze, wynosi 35100 (…). W konsekwencji jeśli nawet zignorujemy przechowywanie informacji pomocniczej i pamięć potrzebną przy wędrowaniu na siłę przez wszystkie możliwe posunięcia, a także założymy, iż każde z nich można sprawdzić w ciągu jednej mikrosekundy, żaden program nigdy nie będzie grał w szachy perfekcyjnie. Dla warcabów te liczby nie są aż tak duże, ale perfekcyjne warcaby są poza dyskusją.
Jak zatem działają dobre programy szachowe? No właśnie, używają one heurystyk, czyli, inaczej mówiąc, zasad praktycznych. W przypadku gier heurystyki są używane jako pomoc przy decydowaniu, które części drzewa gry będą rozważane przy próbie wyboru dobrego posunięcia. Typowe heurystyczne przeszukiwanie opiera się na intuicyjnych regułach wprowadzonych do programu przez programistę, aby zignorować pewne części drzewa gry. Można by na przykład zdecydować, że jeśli w ostatnich pięciu posunięciach w czteropolowym sąsiedztwie pionka nie zmieniło się nic, to tego pionka nie będzie się ruszać, a zatem przeszukiwanie może nie obejmować wszystkich części drzewa umieszczonych poniżej odpowiedniego wierzchołka. Taka reguła mogłaby się okazać pomocna — wyraźnie prowadzi do mniejszych drzew, które trzeba rozważać — ale oczywiście mogłaby kosztować przegraną. Bobby Fisher mógłby wykorzystać ten właśnie pionek do zwycięstwa w trzech posunięciach. Jest to przykład bardzo uproszczony; heurystyki zawarte w prawdziwych programach grających w szachy są zwykle znacznie bardziej wyrafinowane. Są to jednak, tak czy inaczej, heurystyki i używanie ich grozi zawsze pominięciem najlepszego ruchu.
