24

Człowiek kontra komputer – w jaką grę planszową wciąż jesteśmy niepokonani?

Trwa nieustający pojedynek pomiędzy człowiekiem, a komputerem. Tak naprawdę z jednej strony jest człowiek, a z drugiej zwykle połączenie ciągle rosnącej mocy obliczeniowej wraz z programistą lub całym zespołem programistów. Czas mija i upadają kolejne bastiony miękkiej tkanki na rzecz twardego krzemu. Przegraliśmy w szachy, przegraliśmy w Jeopardy! (odpowiednik Va banque), ale jest jedna gra […]

Trwa nieustający pojedynek pomiędzy człowiekiem, a komputerem. Tak naprawdę z jednej strony jest człowiek, a z drugiej zwykle połączenie ciągle rosnącej mocy obliczeniowej wraz z programistą lub całym zespołem programistów. Czas mija i upadają kolejne bastiony miękkiej tkanki na rzecz twardego krzemu. Przegraliśmy w szachy, przegraliśmy w Jeopardy! (odpowiednik Va banque), ale jest jedna gra planszowa, która ma już 4 tysiące lat, w którą komputery nie mogą pokonać nawet przeciętnego gracza.

Nasze porażki z komputerami

Mistrz szachowy Garri Kasparow został po raz pierwszy pokonany przez system komputerowy w 1996 roku. Chociaż trzy kolejne partie wygrał szachista, a dwie kolejne zremisował, to wygrana maszyny o nazwie Deep Blue stała się faktem. Poprawiona wersja komputera Deeper Blue rok później ostatecznie wygrała z rosyjskim szachistą. Aby to osiągnąć było potrzebne aż 245 wyspecjalizowanych procesorów szachowych, analizujących 200 milionów ruchów na sekundę. Od tego czasu komputery mocno wyewoluowały, podobnie jak programy szachowe i byle laptop nie będzie miał problemów z pokonaniem wybitnego gracza.

ibm-watson

Nawet w Jeopardy!, której odpowiednikiem był polski teleturniej Va banque, komputer Watson pokonał dwóch najlepszych graczy: jednego który wygrał najwięcej pieniędzy w historii teleturnieju i drugiego, który był najdłużej niepokonany. Watson wygrał przeszło dwukrotnie więcej pieniędzy od żywych graczy. W tym celu musiał analizować ludzką mowę, wnioskować i udzielać słownych odpowiedzi. Uczynił to wszystko bez podłączenia do internetu, ale mając za to 2880 rdzeni oraz 15 TB pamięci operacyjnej. Pojedynek miał miejsce trzy lata temu.

To nie jedyne gry, w które człowiek dał się pokonać. To samo dotyczy Pokera, Tryktraka, Scrabble, Othello i wiele innych. Jest jednak jeden wyjątek na linii naszych porażek. Gra mająca 4 tysiące lat i stosunkowo proste zasady, w którą nawet przeciętni gracze potrafią ograć szybkie komputery. Tym wyjątkiem jest gra Go.

Na czym polega najtrudniejsza dla komputerów gra?

W Go gra się na kwadratowej planszy z 19 liniami poziomymi i 19 pionowymi, które się przecinają. Białe i czarne kamienie kładzie się na przecięciach linii. Grę rozpoczyna się od pustej planszy, a celem jest otoczenie kamieniami jak największej powierzchni, większej od przeciwnika. Raz położone kamienie nie przesuwają się, ale korzystając z kolejnych zasad, których nie będę tutaj przytaczał, można zbić kamienie przeciwnika. W przeciwieństwie do szachów rozpoczyna kolor czarny.

IBM_Blue_Gene_P_supercomputer

To wszystko wystarczy, aby nie dać komputerom żadnych szans. Tajemnica tkwi w ilości możliwych ruchów. Podczas gdy w szachach po pierwszym ruchu każdego z graczy możliwe jest 400 różnych układów figur, w przypadku Go tych możliwości jest aż 129 960. Z każdym kolejnym ruchem liczba możliwych układów rośnie lawinowo, jednak w przypadku Go dzieje się to znacznie szybciej. Wskaźnik, który określa jak szybko rośnie liczba kombinacji określa się mianem współczynnika rozgałęzień (branching factor). W przypadku szachów wynosi on 35, w przypadku Go 250.

Go-02

Podsumowując krótko te liczby, strategia polegająca na analizie wszystkich możliwych ruchów, w przypadku Go jest zupełnie nieefektywna. Nawet najszybsze komputery sobie z nią nie radzą na choćby podstawowym poziomie. Nie zapowiada się, aby do czasu wynalezienia komputerów kwantowych miało się w tej kwestii cokolwiek zmienić. Setki czy tysiące razy szybsze komputery niż mamy obecnie w zasadzie nic nie zmieniają. Wszystko razem powoduje, że nawet mało wprawiony gracz w Go pokonuje najlepsze programy i najszybsze komputery.

Charakterystyczne jest również, że w miarę zdobywania doświadczenia ruchu graczy stają się coraz bardziej przewidywalne, do czasu aż osiągną oni poziom zaawansowany, wówczas znów stają się stopniowo coraz mniej przewidywalne i nie umiemy wyjaśnić z czego to wynika.

Ludzi umysł wcale nie taki słaby

Mimo, że gra w Go jest popularna wśród matematyków, fizyków, programistów i innych naukowców, takich jak choćby Einstein czy John Nash (bohater filmu Piękny Umysł, zagrany przez Russella Crowe), nikomu nie udało się dotąd opisać strategii grania w Go. Ruchy są intuicyjne. Gracze widzą właściwy ruch, ale nie umieją wyjaśnić skąd o tym wiedzą, że jest właściwy.

Go-04

Programiści głowią się jak ugryźć ten problem i traktują to wyzwanie na równi z graczami grającymi w Go. Potrzebne jest niestandardowe podejście, opierające się na statystyce i rozgrywaniu losowych partii, aby poradzić siebie z problemem ogromnej kombinacji możliwych ruchów. Wciąż jednak nawet najlepsze programy grające w Go potrafią zachowywać się dziwacznie, jeśli nie irracjonalnie.

O zmaganiach programistów bardzo ciekawy i jednocześnie obszerny artykuł opublikował serwis Wired. Jeśli kogoś temat zainteresował, gorąco polecam lekturę.

Źródła: zdjęcie Garri Kasparow pochodzi z serwisu Taringa, zdjęcie Watsona z serwisu KnowledgeUtopia, zdjęcie superkomputera z Wikipedii, a zdjęcia Go z wspomnianego artykułu Wired.