Sztuczna inteligencja nauczyła się (lepiej) grać w go

Sztuczna inteligencja nauczyła się (lepiej) grać w go

Go to starożytna chińska gra, popularna także w Japonii i Korei. Rozgrywa się ją na planszy zwanej goban, na której wyrysowana jest siatka z 19 poziomych i pionowych linii (istnieją też prostsze wersje, z mniejszą liczbą linii). Na planszy układa się białe i czarne kamienie, celem każdego gracza jest zajęcie jak największej powierzchni na planszy. Po szczegółowy opis zasad odsyłam do Wikipedii, do której linkowałem na początku tego paragrafu.

Zasady gry w go są proste, na tyle proste, że uczy się w nią grać już małe dzieci. Ale prostota zasad nie pociąga za sobą prostoty samej gry, która jest uznawana za jedną z najtrudniejszych, jeśli nie najtrudniejszą z wymyślonych przez ludzi.

Staje się to szczególnie widoczne, gdy spojrzymy na historię prób stworzenia dobrych sztucznych graczy w go.

Sztuczni gracze

Pierwszą grą, którą udało się skutecznie zautomatyzować (w 1952), było kółko i krzyżyk. Przyczyna tegoż jest prosta – bardzo łatwo wypisać wszystkie możliwe kombinacje i ruchy tak, by program zawsze wybierał najlepszy, równie łatwo jest stworzyć program, który sam wyliczy wszystkie możliwe ruchy w tej grze.

Z kolei w połowie lat 90 zeszłego wieku program Chinook przewyższył najlepszych ludzkich graczy w warcaby. Korzystał wtedy z biblioteki otwarć zbudowanej na podstawie historycznych rozgrywek mistrzów, algorytmu przeszukującego i oceniającego możliwe ruchy, a także pełnej biblioteki wszystkich możliwych ruchów w sytuacji, gdy na planszy znajduje się osiem lub mniej pionów. Wystarczyło to, by pokonać najlepszych ówczesnych graczy.

Niezależnie od szczegółów implementacji, co do zasady programy grające w takie gry jak kółko i krzyżyk i warcaby można tworzyć w podobny sposób. Technika ta nazywana jest czasami przeglądaniem drzewa gry.

Wykorzystuje ona reprezentację możliwych rozgrywek w postaci struktury zwanej drzewem. Weźmy na przykład partię kółka i krzyżyka. Podstawą drzewa reprezentującego możliwe gry w kółko i krzyżyk jest pusta siatka, która najpierw rozgałęzia się na dziewięć konarów. Każdy konar odpowiada zapełnieniu jednego pola figurą (kółkiem lub krzyżykiem). Każdy z tych konarów rozgałęzia się następnie osiem razy – odpowiadając ruchowi drugiego gracza. I tak dalej, aż do wyczerpania wszystkich możliwości.

Końcowe rozgałęzienia można pogrupować w trzy główne rodzaj: zwycięstwo gracza stawiającego kółka, zwycięstwo gracza stawiającego krzyżyki i remis. Program tworząc obraz drzewa może sprawdzać za jego pomocą jakie ruchy doprowadzą go do porażki, jakie do zwycięstwa i jakie do remisu. 

Analogiczny sposób można wykorzystać do innych gier ze ściśle zdefiniowanymi regułami, takich jak warcaby czy szachy właśnie. Rzecz jasna jest to tym trudniejsze – pod względem ilości obliczeń koniecznych do wykonania przeszukiwania – im gra jest bardziej złożona.

Twórcy Chinook rozwijali swój program dalej, w 2007 roku doprowadzając go do postaci, w której miał on zapisane wszystkie możliwe kombinacje ustawień pionów w ogóle. Pozwoliło im to udowodnić, że doskonali gracze w warcaby zawsze doprowadzą do remisu (zaś ich program, jako doskonały gracz, zawsze wygra lub zremisuje każdą partię).

Programy szachowe poziom najlepszych ludzkich graczy uzyskały w 1997 roku, gdy Deep Blue pokonał Garriego Kasparowa. Siła Deep Blue także brała się przede wszystkim z mocy obliczeniowej komputera, na którym go uruchomiono – program był w stanie analizować 200 milionów ruchów na sekundę. Ale ani Deep Blue, ani żaden inny istniejący nawet dziś komputer nie jest fizycznie zdolny do obliczenia całego drzewa gry dla szachów.

Stąd siła tych programów bierze się ze współdziałania kilku czynników. Jednym z nich są rozbudowane biblioteki najlepszych ruchów – otwarć, a także historycznych gier końcowych. Innymi słowy pewnej wiedzy o tym na czym polega dobra gra w szachy, zaimplementowanej w strukturze programu przez samych programistów.

To, plus zdolność wykonywania głębokiego choć fragmentarycznego przeszukiwania drzewa gry, pozwala programom komputerowym na zwyciężanie ludzkich graczy.

Sztuczne inteligencje (SI) grające w go

Go, jeśli chodzi o liczbę potencjalnych przebiegów rozgrywek, przewyższa szachy bardziej, niż szachy przewyższają warcaby. Choć gra ma proste zasady, liczba możliwych ruchów i kombinacji kamieni na planszy jest ogromna – googol razy większa niż możliwych ustawień bierek w szachach. W szachach gracz w każdej turze staje przeciętnie przed wyborem 30 możliwych ruchów, w go liczba ta to około 200.

 
 

Jak widzieliśmy z przykładem gry w kółko i krzyżyk, gdy budujemy drzewo gry, liczba rozgałęzień na każdym poziomie odpowiada liczbie możliwych ruchów. Tak więc w go tych rozgałęzień na poszczególnych poziomach jest około 200. Już próba przewidzenia konsekwencji dwóch ruchów do przodu poprzez wypisanie wszystkich możliwości daje około 200*200=40000 wariantów. 

Właśnie dlatego metoda polegająca na przeszukiwaniu całego drzewa gry w poszukiwaniu optymalnych ruchów jest, przynajmniej przy dzisiejszym stanie techniki i szybkości budowanych za jej pomocą komputerów, zupełnie niepraktyczna. Mało tego, nawet stosując technikę znaną z programów szachowych – częściowego przeszukiwania wycinka drzewa gry, liczba możliwych kombinacji ruchów jest tak astronomiczna, że programy, które na tym opierają swoją grę, są bardzo słabe.

Tymczasem kilka dni temu Google ogłosiło, że stworzyło SI, nazwane AlphaGo, zdolne grać w go równie dobrze, co niektórzy najlepsi ludzcy gracze. Zrobiło to w poście adresowanym do szerokiej publiki, jak i naukowej publikacji. Media szybko podchwyciły tę informację.

 
 

Nim przyjrzymy się bliżej sekretom AlphaGo, pozwolę sobie rozwiać kilka przekłamań, które zagościły w niektórych relacjach (za tym artykułem). Przede wszystkim nie tylko Google zanotowało znaczący postęp w tworzeniu sztucznych graczy w go, także naukowcy Facebooka mają się czym pochwalić.

Ponadto AlphaGo jak na razie nie wygrało z najlepszymi graczami w go. Zwyciężyło w walce z europejskim mistrzem gry w go, który jest w tej chwili notowany na 633 miejscu wśród najlepszych graczy na świecie. Ale w marcu ma dojść do rozgrywki między AlphaGo, a obecnie najlepszym graczem w go na Ziemi.

Sekrety AlphaGo

Już na długo przed powstaniem AlphaGo dokonano istotnego postępu w tworzeniu programów grających w go. Osiągnięto to wprowadzając przeszukiwania drzewa metodą Monte Carlo. Polega ono, w wielkim skrócie i uproszczeniu, na tym, że komputer symuluje całe rozgrywki, wybierając przy poszczególnych rozgałęzieniach drzewa gry losowe warianty ruchu. Wykonując w ten sposób pewną liczbę próbkowań przestrzeni możliwych gier, program stara się następnie ocenić które ruchy są statystycznie najbardziej obiecujące. Rzecz jasna nie próbuje analizować wszystkich możliwych wyborów, bo to, jak już zaznaczyliśmy, jest w praktyce niewykonalne.

Oczywiście te analizy połączyć można z wiedzą ekspercką, czyli wbudowaną w program wiedzą o optymalnych strategiach, opracowaną i zakodowaną przez ludzkich twórców danego oprogramowania. Taka wiedza może być na przykład wykorzystana do zawężenia badanych metodą Monte Carlo próbnych rozgrywek.

Metody te pozwoliły znacząco poprawić jakość gry programów do go, ale nadal zdolne one były co najwyżej wygrywać z zupełnie przeciętnymi amatorami.

By znacząco podnieść umiejętności swojego oprogramowania, Google wzbogaciło AlphaGo o element, który wykorzystuje w wielu innych swoich programach – głębokie sieci neuronowe.

Sztuczne sieci neuronowe (SSN) to dość stary koncept, który wzorowany jest na działaniu biologicznych neuronów i ich sieci (stąd nazwa).

Jedną z zalet sieci neuronowych jest to, że oprogramowanie to może się uczyć. Programista nie musi programować każdej możliwej reakcji sieci neuronowej w postaci zestawu reguł jawnie wypisanych w języku programowania, w którym napisany jest program.

Sieci trenuje się, to jest pokazuje wiele przykładów danych, które mają rozpoznawać, a następnie warunkuje, wskazując które rozpoznania są prawidłowe, a które nie. Sieć używana do rozpoznawania pisma ma na wejściu ukazywane skany różnych liter lub słów, zaś po próbnym rozpoznaniu, komunikowanym na wyjściu sieci, otrzymuje informacje, czy rozpoznanie było dobre, co modyfikuje połączenia między neuronami, stopniowo zmieniając i w założeniu ulepszając proces rozpoznawania.

Sieci mogą dzięki temu radzić sobie z danymi w postaci zróżnicowanych wzorców (czyli na przykład pismem lub mową). Gdyby jakiś programista chciał opisać reguły rozpoznawania takich wzorców w formie jawnych instrukcji dla typowego oprogramowania, złożoność tego działania by go przerosła.

Z drugiej strony sieci neuronowe posiadają wadę, jakiej nie mają programy tworzone w formie instrukcji – popełniają błędy. Jeśli programista stworzy zestaw reguł i instrukcji, które na przykład składają się na działający program o funkcji kalkulatora, to możemy przyjąć, że ten kalkulator będzie zawsze udzielał prawidłowej odpowiedzi. Sieć neuronowa rozpoznająca mowę czy obrazy może się pomylić, szczególnie, jeśli zostanie wystawiona na działanie bodźca znacząco odbiegającego od tego, co stanowiło treść jej treningu.

AlphaGo używa dwóch sieci neuronowych

Jakie są funkcje sieci neuronowych AlphaGo? W skrócie: zawężenie drzewa przeszukiwań. Juz widzieliśmy, że programy do go używają nader wybiórczego przeszukiwania drzewa metodą Monte Carlo. AlphaGo posiada dwie sieci neuronowe, które na każdym etapie patrzą na aktualny stan rozgrywki i oceniają, jakie ruchy warto w ogóle zbadać. Innymi słowy z góry eliminują wiele rozgałęzień drzewa gry, wykorzystując metodę Monte Carlo do bardziej efektywnego przeszukiwania części drzewa, które wydaje się zawierać bardziej obiecujące potencjalne strategie rozgrywki.

Jedna sieć ocenia ustawienie na planszy starając się przewidzieć następny ruch przeciwnika (sieć oceniająca taktykę). Druga sieć ocenia szansę, że dany układ kamieni doprowadzi do zwycięstwa. Te dane są następnie wykorzystywane do określenia fragmentu drzewa gry, który warto próbkować metodą Monte Carlo, tak jak to robią inne programy do gry w go.

Uczenie sieci polegało po pierwsze na pokazaniu jej ponad 30 milionów rzeczywistych rozgrywek ludzkich graczy w go. To pozwoliło sieci przewidującej następny ruch uzyskać skuteczność rzędu 57%.

Google wykorzystało też metody samouczenia. Kopie jej sieci rozgrywały dziesiątki milionów gier między sobą, ucząc się po drodze. Tak wytrenowana sieć wygrywała z istniejącym oprogramowaniem nawet bez przeszukiwania drzewa metodą Monte Carlo.

Ale Google poszło dalej. Użyło sieci przewidującej ruchy do wytrenowania wspomnianej drugiej sieci, oceniającej na podstawie aktualnego ułożenia kamieni na planszy szanse zwycięstwa. 

Obie te sieci działają następnie jako przewodnicy wskazujący metodzie Monte Carlo, które obszary drzewa gry go warto próbkować. Sieć taktyczna sugeruje ruchy do zbadania, sieć oceniająca układy kamieni może zatrzymać próbkowanie bez potrzeby symulowania rozgrywki do samego końca, po prostu rozpoznając znalezione w procesie próbkowania pośrednie ułożenia kamieni jako dające dużą lub małą szansę na zwycięstwo.

Ten system pozwolił AlphaGo wygrać 499 na 500 rozgrywek zorganizowanych przez Google między AlphaGo a najlepszymi innymi programami do gry w go jakie są teraz dostępne. Przy czym AlphaGo wygrywało nawet jeśli pozwalało wykonać aż cztery wstępne ruchy przeciwnikowi. Wygrało też wszystkie pięć gier, które rozgrywało z europejskim mistrzem go.

Implikacje

Jakie są szersze implikacje sukcesu AlphaGo? To kolejny pokaz potencjału głębokich sieci neuronowych, oprogramowania zdolnego uczyć się z doświadczenia. Google wykorzystuje takie sieci do rozpoznawania obrazów i mowy.

Ale, jak zwracają uwagę niektórzy komentatorzy, AlphaGo jest w istocie programem hybrydowym. Pewne jego komponenty (przeszukiwanie drzewa metoda Monte Carlo) są produktem rozwoju sztucznej inteligencji według podejścia symbolicznego, w którym próbuje się stworzyć maszyny myślące według precyzyjnych reguł logiki i manipulacji symbolami.

Z kolei sieci neuronowe stanowią, zapewne niedoskonałą, mimikrę tego jak biologiczne mózgi rozpoznają i klasyfikują wzorce: w sposób niebywale wydajny, ale podatny na błędy i złudzenia.

Co ważniejsze, to właśnie ta synteza precyzyjnego myślenia symbolicznego i w pewnym sensie intuicyjnego, statystycznego i podatnego na błędy rozpoznawania wzorców siecią neuronową, czyni AlphaGo w jakiś sposób podobnym do naszych umysłów. Nasze mózgi funkcjonują zanurzone w niebywale złożonym morzu bodźców, z którymi radzą sobie właśnie za pomocą skutecznych mechanizmów szybkiego rozpoznawania i klasyfikowania wzorców. Ale jednocześnie zdolne są do wyrafinowanych operacji na abstrakcyjnych symbolach, prowadzonych wedle precyzyjnych reguł logiki, które z prawdziwych przesłanek mogą wyciągać absolutnie prawdziwe wnioski.

Jeśli komputery kiedykolwiek będą miały dorównać lub przewyższyć ludziom w zdolnościach poznawczych, będą musiały się nauczyć harmonijnego łączenia tych dwóch trybów myślenia na większą skalę.

Możesz polubić fanpage mojego bloga na Facebooku. Możesz też śledzić moje tweety.

Czy epidemię wirusa Zika wywołały komary GMO?

Czy epidemię wirusa Zika wywołały komary GMO?

The 100

The 100