Koniec warcabów

Tekst z archiwum "Rzeczpospolitej"

Był to program komputerowy o nazwie Chinook. Naukowcy przeprowadzili dowód, że nikt nigdy nie zdoła z nim wygrać. Z Chinookiem można najwyżej zremisować

Używając terminologii teorii gier, możemy powiedzieć: warcaby zostały rozwiązane. Jeżeli program trafi na innego perfekcyjnego gracza, będzie remis. Warcaby to najbardziej skomplikowana ze wszystkich gier, które zostały rozwiązane. Możliwych jest w niej pięćset miliardów miliardów pozycji (piątka i dwadzieścia zer!)

Autorem programu Chinook był dr Jonathan Schaeffer z uniwersytetu w Albercie w Kanadzie. Jak stwierdził naukowiec na łamach  "Science", program do gry w warcaby oznacza przede wszystkim zwycięstwo brutalnej siły obliczeniowej nad subtelnymi metodami heurystycznymi. Co to oznacza? Otóż przy programowaniu sztucznej inteligencji możliwe są dwa podejścia. Albo będziemy się starać, by komputer myślał podobnie do człowieka i podejmował decyzje w sposób dla nas zrozumiały, albo każemy komputerowi przeanalizować każdą możliwą decyzję, łącznie z tymi, które nam od razu wydają się bezsensowne. Chinook swoją perfekcję zawdzięcza przede wszystkim drugiemu podejściu.

W połowie ubiegłego wieku Arthur Samuel, ekspert od maszyn komputerowych, stworzył pierwszy taki program. W roku 1963 programowi Samuela udało się wygrać jedną partię z człowiekiem. Przyniosło mu to duży rozgłos, choć była to tylko jedna partia, a przeciwnik nie był arcymistrzem warcabów.

Ostatni ludzki mistrz

W roku 1989 Jonathan Schaeffer postanowił opracować program, który nie tylko wygra jedną czy drugą partię ze zwykłym człowiekiem, ale pokona mistrza świata w warcabach. Program w swojej pierwszej wersji stanął w roku 1992 w szranki z najwybitniejszym chyba graczem w warcaby w dziejach tej gry – Marionem Tinsleyem.

Mecz zakończył się wynikiem 4: 2 dla Tinsleya. W roku 1994 miał miejsce rewanż. Po kilku remisowych partiach Tinsley zrezygnował z gry ze względów zdrowotnych.

Niedokończony mecz nie dawał Schaefferowi spokoju. Postanowił tak ulepszyć swój program, żeby nikt nie mógł mieć wątpliwości, że Chinook nie uległby Tinsleyowi.

50 komputerów jednocześnie nieprzerwanie przez kilkanaście lat pracowało nad programem. Praca ta dzieliła się na dwa etapy. Najpierw Chinook nauczył się zwycięskiego kończenia partii. Rozpracował wszystkie pozycje, w których na planszy jest mniej niż 11 pionków.

Od końca i od początku

Komputery analizowały najpierw pozycje, gdzie został tylko jeden pionek. Potem te, w których na planszy są dwa pionki – komputery sprawdziły, do jakiej pozycji z jednym pionkiem można z niej doprowadzić. Potem przyszedł czas na ustawienie z trzema pionkami – i tak cofając się, rozpracowano każdą pozycję, w której jest dziesięć pionków albo mniej.

W grze w warcaby (w najpopularniejszej wersji) biorą jednak udział 24 pionki. Schaeffer stwierdził, że nie starczy mu mocy obliczeniowej, żeby się cofnąć w możliwych kombinacjach aż do rozpoczęcia gry. Zaczął więc budować drugą część programu – tę, która rozpoczyna partię. Tu użył metod heurystycznych, dzięki którym komputer mógł w przybliżeniu wartościować każdy ruch.