Przeskocz do treści

Delta mi!

Loading

Aktualności (nie tylko) fizyczne

Idus Martiae Anno Domini 2016

Piotr Zalewski

o artykule ...

  • Publikacja w Delcie: maj 2016
  • Publikacja elektroniczna: 1 maja 2016
obrazek

Piętnastego marca stracona została rubież intelektualnej przewagi człowieka nad sztuczną inteligencją, za jaką była uznawana maestria gry w Go. Zakończyła się ostatnia, piąta partia między AlphaGo, programem firmy DeepMind (będącej własnością Google) i Lee Se-dolem (9 dan - najwyższy stopień wtajemniczenia), jednym z najlepszych, jeżeli nie najlepszym zawodowym graczem. AlphaGo wygrał pierwsze trzy rozgrywki. Lee Se-dol wygrał czwartą i, po niezwykle zaciętej walce, przegrał ostatnią.

Na jesieni ten sam program wygrał, w stosunku 5:0, analogiczny mecz z europejskim mistrzem Fan Hui (2 dan). Naprzemiennie rozgrywana była wtedy również seria spotkań nieoficjalnych, która została wygrana przez AlphaGo, ale tylko w stosunku 3:2. W oficjalnych spotkaniach czas był ograniczony do godziny (dla każdego z graczy) z rozszerzeniem o trzy trzydziestosekundowe byoyomi, czyli okresy odnawiające się pod warunkiem wykonania w ich trakcie ruchu. W spotkaniach nieoficjalnych nie było tej początkowej godziny. Reguły te zostały ustalone przez Fan Hui przed rozpoczęciem rozgrywek.

W meczu z Lee Se-dolem początkowy czas wynosił dwie godziny, a trzy byoyomi były sześćdziesięciosekundowe.

Koreański mistrz przed meczem "obawiał się przegrania jednej z pięciu partii". Eksperci Go również stawiali na człowieka. Oczekiwano, że pokonanie przez sztuczną inteligencję najlepszych z najlepszych jest odległe o co najmniej dekadę, jeżeli w ogóle możliwe.

Poglądy te były uzasadniane kombinatoryczną złożonością Go. Szacuje się, że liczba możliwych sytuacji na planszy przekracza liczbę atomów w obserwowalnym wszechświecie. Dlatego gra na najwyższym poziomie opiera się w znacznej mierze na wyćwiczonej przez lata intuicji wykorzystującej wybitne zdolności.

Przypomnijmy, że chodzi o rozgrywkę na kracie utworzonej z dziewiętnastu równoległych i dziewiętnastu prostopadłych do nich linii. Gracze na przemian kładą pojedyncze kamienie, pierwszy czarne, drugi białe, na wolne przecięcia linii. W grze chodzi o odgrodzenie jak największego obszaru za pomocą swoich kamieni (na końcu zalicza się po punkcie za odgrodzone przecięcia; jest kilka sposobów obliczania końcowego wyniku mogących dawać niewielkie różnice - dlatego przed grą ustala się, który sposób zostanie użyty). Kamieni nie można przesuwać, ale ścisłe otoczenie grupy kamieni przeciwnika (tak, że żaden z tych kamieni nie sąsiaduje z wolnym przecięciem linii - nie ma tzw. oddechu) skutkuje zdjęciem całej grupy z planszy. W omawianych rozgrywkach stosowana była (powszechnie używana) reguła komi, przyznająca graczowi posługującemu się białymi kamieniami (zaczynającemu jako drugi) dodatkowe 7,5 punktu.

Po zwycięstwie nad Fan Hui opublikowano pracę [1], w której przedstawiono ogólne zasady działania programu AlphaGo (oraz jego osiągnięcia).

Od dłuższego czasu podstawą programów wykorzystujących sztuczną inteligencję w grach (zwłaszcza tych z pełną informacją jak Go czy szachy) jest metoda MCTS (Monte Carlo Tree Search). W tym przypadku polega ona na ocenie kolejnego ruchu na podstawie rozegrania szeregu jego kontynuacji z kolejnymi ruchami (zarówno swoimi, jak przeciwnika) wybieranymi w przypadkowy sposób, ale spośród tych mieszczących się w ramach aktualnie najlepszej strategii naśladującej najlepszych graczy (ludzi lub maszyny, w tym siebie samą). Metoda ta pozwoliła na osiągnięcie przewagi nad profesjonalistami w szeregu gier (w tym w szachach), ale w Go dawała szansę na wygraną zaledwie z nie najlepszymi amatorami. Jest to, oczywiście, związane właśnie z kombinatoryczną komplikacją Go.

Dodatkowa przewaga AlphaGo została osiągnięta poprzez twórcze wykorzystanie sieci neuronowych o wielu ukrytych warstwach (deep neural networks, DNN). Przez wiele lat uważano, że mnożenie ukrytych warstw takich sieci niewiele pomaga. Ostatnio jednak okazało się, że wykorzystywanie ich do wykonywania hierarchicznych przekształceń wzmacniających lokalne regularności danych wejściowych daje bardzo dobre wyniki w rozpoznawaniu obrazów. A układ kamieni jest przecież obrazem! Temat można dalej zgłębiać za pomocą oryginalnej publikacji [1], ale specjaliści komentują, że na jej podstawie i tak nie da się odtworzyć niuansów działania AlphaGo (co chyba nie powinno specjalnie dziwić).

Warto dodać, że Fan Hui i Lee Se-dol rywalizowali z tzw. rozproszonym AlphaGo posługującym się (przynajmniej w meczu z Fan Hui) czterdziestoma wątkami uruchamianymi na 1202 CPU oraz 176 GPU (Graphics Processing Unit). Ciekawe jest również to, że liczba sprawdzanych pozycji była rzędy wielkości mniejsza niż w przypadku słynnego meczu Deep Blue z Kasparowem przed dwudziestu laty, ale (jak widać) były one sprawdzane mądrzej i precyzyjniej [1]. Jednoczesne użycie DNN i MCTS daje najlepsze rezultaty, ale wyniki użycia samych sieci neuronowych są niewiele gorsze. Uważa się, że jest to sposób zbliżony do intuicyjnej gry profesjonalistów.

Lee Se-dol podchodził bardzo emocjonalnie do meczu z AlphaGo. Wielokrotnie przepraszał, że nie stanął na wysokości zadania. Czwartą partię wygrał, wykonując niestandardowy ruch, którego AlphaGo nie rozpoznał jako kluczowy. Zorientował się dopiero po dziesięciu następnych ruchach. W ostatnim meczu człowiek miał długo niewielką przewagę po błędzie popełnionym przez AlphaGo na początku partii, ale nie zdołał jej utrzymać w końcówce rozgrywanej w rytm byoyomi. Moim zdaniem było widać, że jest na granicy psychofizycznej wytrzymałości. Partia została już uznana za najbardziej niesamowitą z kiedykolwiek rozegranych.

Do historii przejdzie jednak rozpromieniony uśmiech Lee Se-dola po wygranej partii. Być może była to ostatnia taka wygrana człowieka w pojedynku ze sztuczną inteligencją. Sam Lee stwierdził, że nie zamieniłby jej na nic innego.

obrazek

Lee Se-dol po wygranej partii z AlphaGo

Lee Se-dol po wygranej partii z AlphaGo

Jeżeli chodzi o nasze ewentualne (pozostałe) przewagi to zachęcam do przeczytania zakończenia Rozprawy Stanisława Lema.


Do czytania
[1]
David Silver, Aja Huang et al., Mastering the game of Go with deep neural networks and tree search, Nature 529 (2016) 484.