Od szachów do AlphaGo

Prof. Jacek Mańdziuk: Choć bardzo skuteczna i przewyższająca najlepszych graczy ludzkich, sztuczna inteligencja grająca w go nie jest ostatecznym osiągnięciem w dziedzinie gier umysłowych

Dynamiczny rozwój sztucznej inteligencji nie ominął gier. Kanonicznym przykładem postępu w zastosowaniu SI do gier są dokonania firmy Google DeepMind w grze go, która przez dziesięciolecia stanowiła bastion supremacji ludzi nad maszynami w dziedzinie klasycznych gier umysłowych.

O ile wcześniejsze osiągnięcie firmy IBM (maszyna Deep Blue) stanowiło przełom tylko w sensie psychologicznym (to fenomenalne rozwiązanie inżynierskie nie oferowało przełomowych rozwiązań, jeśli chodzi o metody sztucznej inteligencji), o tyle system AlphaGo firmy Google DeepMind, a w jeszcze większym stopniu AlphaGo Zero są dowodem potencjalnie ogromnych możliwości wykorzystania metod SI (uczenia głębokiego, uczenia ze wzmocnieniem oraz symulacji Monte Carlo) do rozwiązywania zagadnień, które dotychczas były poza zasięgiem sztucznych systemów inteligentnych.

Choć bardzo skuteczna i przewyższająca najlepszych graczy ludzkich, sztuczna inteligencja grająca w go nie jest ostatecznym osiągnięciem w dziedzinie gier umysłowych. Stanowi bazę do dalszych rozważań na temat wykorzystania metod SI i uczenia maszynowego w zagadnieniach o bardziej uniwersalnym charakterze.

Badania i wyzwania

Dotychczasowe badania w obszarze gier w znakomitej większości dotyczyły podnoszenia poziomu gry sztucznych graczy. Nie kładziono nacisku na sposób, w jaki wysoki poziom jest osiągany. Celem nadrzędnym było doskonalenie umiejętności gry w celu pokonania najlepszych (ludzkich) graczy na świecie, a kiedy to nastąpiło, rywalizacja z innymi graczami maszynowymi o laury mistrzowskie.

Pokonanie dr. Mariona Tinsleya [Amerykanin, najlepszy w historii gracz w warcaby – red.] przez program Chinook (warcaby), a następnie rozwiązanie tej gry (wykazanie, jaki będzie wynik rozgrywki przy optymalnej grze obu stron) przez grupę badaczy z University of Alberta, prowadzoną przez prof. Jonathana Schaeffera; zwycięstwo Deep Blue nad Garrim Kasparowem, a następnie pojawienie się programów o sile gry powyżej 3000 ELO na jednoprocesorowej maszynie typu PC (Komodo, Houdini, Stockfish, Deep Fritz i in.), czy wreszcie pokonanie Lee Sedola przez AlphaGo – to wszystko doprowadziło do przewartościowania priorytetów w obszarze klasycznych gier dwuosobowych z pełną informacją.

Przede wszystkim na orbitę zainteresowań badaczy powrócił paradygmat human-like playing (grania w sposób podobny do ludzi), a w szczególności aspekt multigame playing (umiejętności gry w wiele gier, zwykle w ramach określonej klasy gier).

Polska: trzy grupy

W środowisku uniwersyteckim istnieją trzy grupy naukowe prowadzące badania w obszarze gier.

Grupa prof. Krzysztofa Krawca z Politechniki Poznańskiej

Prace zespołu badawczego prof. Krawca w obszarze gier (współpracownicy: dr Wojciech Jaśkowski, dr Paweł Liskowski, dr Marcin Szubert, dr Bartosz Wieloch) koncentrują się na uczeniu strategii gier z wykorzystaniem algorytmów ewolucyjnych, algorytmów koewolucyjnych, uczenia ze wzmocnieniem oraz, w ostatnim czasie, sieci neuronowych, a także na hybrydyzacji tych podejść.

W pracach wykorzystywane są różne reprezentacje strategii/graczy oraz różne algorytmy uczenia (m.in. jedno- i dwupopulacyjne algorytmy koewolucyjne, metoda różnic czasowych, metody gradientowe). Efektem tych prac jest m.in. opracowanie strategii, które plasowały się bardzo wysoko, często na pierwszych miejscach, rankingów dla gier Othello (Reversi) oraz SZ-Tetris.

Ponadto zespół prof. Krawca prowadził badania nad aspektami teoretycznymi gier, m.in. nad dokładnymi i przybliżonymi metodami estymacji wymiarowości gier oraz nad rolą kształtowania w uczeniu koewolucyjnym.

Grupa kierowana przez prof. Dominika Ślęzaka z Uniwersytetu Warszawskiego

Główne kierunki badawcze w obszarze gier dotyczą rozwoju narzędzi wspomagających implementację mechanizmów SI w grach wideo (projekt Grail, realizowany we współpracy z firmą Silver Bullet) oraz budowy systemu coachingowego, wspierającego doskonalenie indywidualnych umiejętności graczy w grach eSport (projekt SENSEI, realizowany we współpracy z firmą eSensei).

Oba przedsięwzięcia są współfinansowane przez NCBR (w ramach programu POIR – konkurs GameINN) i stanowią bardzo dobry przykład harmonijnego połączenia badań podstawowych z działaniami wdrożeniowymi.

Dotychczas badania w obszarze gier dotyczyły głównie podnoszenia poziomu gry sztucznych graczy. Nie kładziono nacisku na sposób, w jaki wysoki poziom jest osiągany

W sensie metodologicznym osią przewodnią obu wspomnianych projektów są różne inkarnacje metody MCTS/UCT w połączeniu z obliczeniami granularnymi, realizowanymi na odpowiednio dobranych poziomach granulacji informacji. Obok prof. Ślęzaka głównym projektantem i wykonawcą proponowanych rozwiązań jest mój były doktorant, dr Maciej Świechowski.

Grupa badawcza na Wydziale Matematyki i Nauk Informacyjnych Politechniki Warszawskiej

Główne obszary działalności naukowej kierowanego przeze mnie 12-osobowego (jeden profesor zwyczajny, jeden doktor habilitowany, trzech doktorów, jeden asystent, sześciu doktorantów) zespołu sztucznej inteligencji i inteligencji obliczeniowej dotyczą:

metod sztucznej inteligencji, uczenia maszynowego oraz sztucznych sieci neuronowych;
metaheurystycznych metod populacyjnych (algorytmów genetycznych, metod matematycznych, metod optymalizacji rojem cząstek oraz algorytmów mrówkowych).

Zespół realizuje zarówno badania podstawowe, dotyczące własności teoretycznych wyżej wymienionych metod metaheurystycznych, jak i badania aplikacyjne, wykorzystujące wymienione wyżej metody do rozwiązywania praktycznych zagadnień w różnych domenach zastosowań.

W szczególności badania te dotyczą:

wykorzystania metod silnej sztucznej inteligencji (AGI) w dynamicznych środowiskach wieloagentowych (np. synchronicznych grach wieloosobowych);
opracowania skutecznych (efektywnych i skalowalnych) metod znajdowania stanu równowagowego Stackelberga w grach wielokrokowych (Gry Obronne Stackelberga);
zastosowania samoadaptujących się algorytmów metaheurystycznych do rozwiązywania na przykład trudnych problemów optymalizacyjnych (głównie dynamicznych problemów transportowych);
wykorzystania metod uczenia niewymagających posiadania wiedzy wstępnej (knowledge-free learning) w zagadnieniu general game playing;
efektywnych metod reprezentacji wiedzy w systemach autonomicznych.

W ostatnich kilku latach szczególnie intensywnie rozwijane są przez grupę badania w obszarze kognitywnie inspirowanych metod pozyskiwania i reprezentacji wiedzy w systemach inteligentnych oraz autonomicznych metod uczenia niewymagających trenerów zewnętrznych.

Zagadnieniom tym poświęcona jest między innymi monografia mojego autorstwa, zatytułowana „Knowledge-Free and Learning-Based Methods in Intelligent Game Playing”, wydana przez Springer-Verlag w 2010 roku, oraz organizowane przeze mnie wspólnie z Włodzisławem Duchem i Januszem Starzykiem (Ohio University, USA) corocznie międzynarodowe sympozjum naukowe IEEE Symposium on Computational Intelligence for Human-like Intelligence (2013 – Singapur, 2014 Orlando/USA, 2015 – Kapsztad/RPA, 2016 – Ateny, 2017 – Honolulu/USA, 2018 – Bangaluru/Indie).

Działalność badawcza finansowana jest zarówno ze środków Politechniki Warszawskiej (granty statutowe i dziekańskie), jak źródeł zewnętrznych (grant NCN 2018-2019, grant NCN 2013-2016, grant MPD (2010-2015) Fundacji na rzecz Nauki Polskiej). Badania prowadzone są wspólnie z naukowcami z renomowanych ośrodków naukowych, między innymi Nanyang Technological University w Singapurze, Instytutu Badań Systemowych PAN, University of Alberta w Kanadzie, Uniwersytetu Mikołaja Kopernika w Toruniu, University of New South Wales w Australii oraz National University of Tainan na Tajwanie.

Poza wspomnianymi zespołami można wymienić konkretnych badaczy z innych ośrodków funkcjonujących naukowo w dziedzinie gier, między innymi dr. Piotra Belinga (Uniwersytet Łódzki), prowadzącego badania dotyczące brydża oraz wspomagania przez SI procesu definiowania i budowy gry (projekt Grail), czy dr. Jakuba Kowalskiego (Uniwersytet Wrocławski), rozwijającego idee dotyczące General Game Playing we współpracy z prof. Andrzejem Kisielewiczem.

Trzy nurty badań

Dziedzina gier rozwija się w ostatnich latach bardzo dynamicznie głównie za sprawą popularyzacji nowych metod przeszukiwania (Monte Carlo Tree Search/UCT) oraz analizy i klasyfikacji obrazów (głębokie sieci neuronowe). Jednocześnie wraz z fenomenalnym wzrostem poziomu gry sztucznych agentów można zaobserwować stopniowe przenoszenie punktu ciężkości z dalszego poprawiania gry na problem użyteczności treningowej agentów SI.

W szczególności szeroko rozwijane jest podejście coachingowe, polegające na jak najskuteczniejszej implementacji procesu uczącego realizowanego przez agenta SI w kontekście osiągnięcia przez człowieka – obserwatora zamierzonego celu nauki, np. gry w daną grę, rozwiązywania określonego rodzaju problemów czy skutecznego postępowania w określonych sytuacjach).
Drugi kluczowy obecnie nurt badań dotyczy implementacji paradygmatu human-like playing and problem solving, opierającego się na idei naśladowania umiejętności kognitywnych posiadanych przez ludzi oraz ich wykorzystania podczas gry (ogólniej: w trakcie rozwiązywania problemów decyzyjnych). W tym obszarze mieści się również zagadnienie wiarygodności grającego bota (believability), rozważane między innymi w kontekście testu Turinga dla botów.
Trzecim dynamicznie rozwijanym nurtem badań jest human-machine co-learning and problem solving, czyli problem wspólnego, synergicznego rozwiązywania problemów (często w postaci iteracyjnej pętli: human-in-the-loop) oraz takiego podejścia do procesu nauki/rozwiązywania zadań, które umożliwia efektywne uczenie się przez człowieka, z agentem SI (robotem) w roli partnera – nauczyciela.

Praktycznie wszystkie obszary badawcze dotyczące gier, w tym oczywiście wymienione kierunki wiodące, prowadzą do rozważań teoretycznych oraz rozwiązań praktycznych mających zastosowanie znacznie szersze niż domena, w ramach której są generowane. Znakomita większość metod i algorytmów związanych z tematyką gier ma znaczenie uniwersalne w kontekście rozwiązywania problemów decyzyjnych oraz budowania strategii postępowania w dłuższym horyzoncie czasowym.

W znakomitej większości idee oraz algorytmy powstające w ramach badań przeprowadzonych w domenie gier mogą być w generyczny sposób zastosowane w wielu innych obszarach/problemach decyzyjnych. W związku z tym znaczenie tychże idei, algorytmów i metametod jest znacznie większe niż tylko optymalizacja zachowania graczy SI.

Przyszłość: trzy postulaty

Jakie są perspektywy rozwoju SI w Polsce? Według mnie istnieją trzy absolutnie kluczowe aspekty polityki edukacyjnej i naukowej, które wymagają istotnej modyfikacji i wzmocnienia:

Zwiększenie stopnia umiędzynarodowienia rodzimej nauki poprzez wspieranie instytucjonalne i finansowe współpracy zagranicznej i wymiany osobowej z najlepszymi ośrodkami SI na świecie.
Utworzenie środowiskowych szkół doktorskich, obejmujących kilka podmiotów naukowych z wymogiem posiadania ko-opiekuna/ko-promotora z zagranicy (postulat ten w naturalny sposób wspiera dodatkowo wymianę naukową doktorantów).
Promowanie w sposób szczególny, w ramach oceny parametrycznej jednostek naukowych, publikacji w najbardziej prestiżowych periodykach oraz na konferencjach naukowych. Jeżeli chcemy aspirować do grupy najlepszych, to powinniśmy to robić na pewno nie liczbą, ale jakością publikowanych prac i ich realnym (a nie jedynie formalnym) wpływem na naukę światową.

Powyższe postulaty stanowią w moim przekonaniu absolutne minimum niezbędnych działań w procesie podążania polskiej nauki ze światowymi/europejskimi liderami w dziedzinie sztucznej inteligencji. Pełna lista takich działań byłaby oczywiście znacznie dłuższa.

Materiał jest opracowaniem części pracy prof. Jacka Mańdziuka pt. „Rozwój sztucznej inteligencji i uczenia maszynowego w domenie gier” (Warszawa 2018), przygotowanej dla OPI PIB.