Sztuczna inteligencja dla gier

Zapraszając Państwa w kolejnych wpisach na tym blogu do poznawania różnych metod sztucznej inteligencji (AI), posługuję się metaforą archipelagu. Dzisiaj prezentuję kolejną "wyspę" tego archipelagu, związaną z metodami AI wykorzystywanymi w programach grających w różne gry. Tematyka ta jest wąska, ale przyniosła wyjątkowo dużo imponujących wyników. Spróbuję dzisiaj Państwu o nich opowiedzieć.

Pomysł, żeby komputer wyposażony w sztuczną inteligencję stał się dla człowieka przeciwnikiem w różnych grach, był naprawdę genialny. Po pierwsze, sytuacja w grze jest dokładnie zdefiniowana przez reguły gry i przez działanie gracza-przeciwnika, więc komputer może działać w sposób maksymalnie logiczny. To nie to samo, co podejmowanie decyzji w realnym świecie, gdzie reguły bywają nieznane, a wiele czynników jest nieprzewidywalnych. Gra jest swoistym laboratorium podejmowania decyzji.
Po drugie, prace nad programami samodzielnie budującymi strategie w grach były przez długi czas mocno sponsorowane przez wojsko, bo wojskowi wierzyli, że program zdolny do pokonania człowieka w jednej z gier strategicznych - po odpowiedniej modyfikacji - będzie mógł wspomagać podejmowanie decyzji przez dowódców na polu walki.
Nie są znane wszystkie fakty i liczby, ale przykładowo wiadomo, że w jednym tylko 1963 roku jedna tylko uczelnia amerykańska (MIT) otrzymała od ARPA dofinansowanie w wysokości 2,2 mln USD. Przy ówczesnej wartości dolara była to bajońska suma, a warto dodać, że finansowanie badań AI przez armię trwało przez wiele lat (od 1958 do 1973 roku) i dotyczyło wielu ośrodków naukowych. Nic dziwnego, że drzewo na tej dziś rozważanej wysepce wyrosło takie duże i takie dorodne!



Nadzieje na praktyczną (w szczególności militarną) użyteczność programów strategicznych do gier okazały się jednak płonne i wojsko fundusze obcięło. Ale rozpędzonej machiny tworzenia programów grających z ludźmi w różne gry zatrzymać się nie dało - i toczyła się ona dalej siłą własnego rozpędu.

Już początkowe wyniki były bardzo obiecujące. W 1952 roku Arthur Lee Samuel zbudował program, który grał w warcaby na poziomie dobrego amatora. Program ten miał możliwość uczenia się i po każdej rozegranej partii grał coraz lepiej, chociaż mistrzowskiego poziomu nie osiągnął. Sukces ten odniósł dopiero jego "późny potomek" o nazwie Chinook, opracowany przez Jonathana Schaeffera, który wygrał mistrzostwa US Open w 1992 roku. Zwróćmy uwagę, że nastąpiło to 40 lat po sukcesach Samuela, więc postęp w tej dziedzinie nie był zbyt szybki. Zresztą sukces Chinooka był tylko częściowy, bo w tym samym 1992 roku przegrał on inne mistrzostwa w Londynie i dopiero w 1995 roku (stale doskonalony i rozszerzany) ponownie sięgnął po mistrzostwo świata, już w sposób nieodwołalny.

Zdecydowanie lepiej przebiegał rozwój programów do gry w szachy. Pierwszy program przyzwoicie grający w tę grę i wygrywający z amatorami stworzył Alex Bernstein w 1958 roku. W słynnej MIT (jak się powszechnie sądzi – najlepszej uczelni technicznej na świecie) powstał w 1962 roku program nazwany (od nazwisk głównych twórców) Kotok-McCarthy. Program ten uznano za najlepszy szachowy program amerykański i rzucono wyzwanie Rosjanom. W latach 1966 i 1967 przez 9 miesięcy toczyły się zmagania między programem Kotok-McCarthy (który w międzyczasie przeniesiono na silniejszy komputer w Uniwersytecie Stanforda w sercu obecnej Krzemowej Doliny) i programem rosyjskim, oznaczanym akronimem ITEP (od angielskiej nazwy moskiewskiego Instytutu Fizyki Teoretycznej i Eksperymentalnej, gdzie się ten program znajdował).

Amerykański program przegrał sromotnie w stosunku 3:1 i chociaż Amerykanie to niepowodzenie przypisywali faktowi, że rosyjskim informatykom doradzał arcymistrz szachowy Michał Botwinnik – to jednak była to porażka bardzo dotkliwa. Rosyjskie władze zareagowały jednak na sukces swoich uczonych w sposób dosyć specyficzny: Dyrektor ITEP Aleksander Kronrod, który dopuścił do tego, że komputer ITEP zamiast rozwiązywać problemy fizyki atomowej był angażowany do jakiejś tam rozgrywki szachowej został wyrzucony ze stanowiska i pozbawiony tytułu profesorskiego.

Ten smutny finał nie zatrzymała jednak rozwoju programów szachowych. Historia odnotowała przygodę znanego badacza i publicysty Dreyfusa, który od 1965 roku toczył regularną krucjatę przeciwko wszystkim zwolennikom tezy, że komputer może wykazywać inteligentne działanie. Tymczasem już w 1969 roku Dreyfus przegrał sromotnie z programem Chess 3.0. Co więcej, nie zdołał nawet zremisować w ani jednej partii!

Potem szereg badaczy tworzyło programy coraz lepiej grające. Na uwagę zasługuje przez wiele lat doskonalony program Deep Thought, stworzony w 1985 roku przez 4 studentów z USA (T. Hsu, T. Anantharaman, M. Campbell, A. Nowatzyk) i program Deep Blue stworzony w 1996 roku przez IBM. Ten proces systematycznego wieloletniego doskonalenia doprowadził do finalnego sukcesu, jakim było pokonanie przez program Deep Blue arcymistrza szachowego, Garry'ego Kasparowa. Nastąpiło to dokładnie 13.05.1997 roku.
Fakt ten był rozmaicie komentowany. Entuzjaści sztucznej inteligenci wskazywali, że nie było wtedy na świecie człowieka, który by wygrał z Kasparowem, więc da się w tym przypadku udowodnić, iż to komputer sterowany inteligentnym programem sam znalazł zwycięską strategię. To rozumowanie miało podważać podnoszony niekiedy (przez sceptyków) argument, że nie ma sztucznej inteligencji, tylko programiści wkładają do tworzonych programów własną inteligencję, a komputer jedynie ją odtwarza jak adapter płytę. Zdaniem entuzjastów tego argumentu w odniesieniu do Deep Blue nie można było zastosować, bo skoro żaden człowiek nie wiedział, jak pokonać Kasparowa, to nikt nie mógł wprowadzić gotowego przepisu na takie zwycięstwo do komputera. Ergo - komputer sam to wymyślił!
Sceptycy wskazywali, że komputer wygrał brutalną siłą - miał zapisane w pamięci setki rozgrywek szachowych i potrafił błyskawicznie wyszukać najlepsze gotowe rozwiązanie w każdej zaistniałej sytuacji. Dzięki temu potrafił przewidywać rozwój sytuacji na szachownicy na 14 ruchów naprzód. I wygrywał, chociaż wcale mądry nie był!

Niezależnie jednak od oceny tego historycznego zwycięstwa - można powiedzieć, że ogromne "drzewo", które wyrosło na omawianej tu wąskiej wysepce, wydało owoce.

W tym artykule omówiono tylko dwa "klasyczne" przykłady wykorzystania metod sztucznej inteligencji do tworzenia programów rywalizujących z intelektem człowieka w umownym "świecie" gier strategicznych: warcaby i szachy. Budowane były też programy grające w inne popularne gry, na przykład w trik-traka (backgammona) i w Othello. Programy te po latach doskonalenia w większości osiągały poziom pozwalający na rywalizację z mistrzami świata. Natomiast grą strategiczną, w której ludzie wciąż jeszcze mają przewagę nad maszynami - jest Go. Ta gra, mniej znana w Europie, ale popularna na przykład w Japonii, charakteryzuje się większą złożonością niż szachy i dlatego rywalizacja maszyn z ludźmi jest tu trudniejsza. Na przykład średnia liczba ruchów podczas partii Go wynosi 260, podczas gdy w szachach partia składa się średnio z 35 ruchów. Liczbę różnych pozycji na planszy Go szacuje się liczbą składającą się z jedynki i 172 zer, podczas gdy liczba pozycji na szachownicy wyraża się liczbą składającą się z jedynki i "zaledwie" 46 zer. Liczbę różnych partii, jakie można rozegrać w Go szacuje się liczbą składającą się z jedynki i 260 zer podczas gdy liczbę różnych partii szachów wyraża się liczbą składającą się z jedynki i "zaledwie" 123 zer.

Oczywiście podane liczby różnych pozycji czy różnych partii dla szachów, żartobliwie skomentowane powyżej słowem "zaledwie", w rzeczywistości są astronomiczne. Ale z porównania podanych liczb wynika, że przewaga złożoności gry w Go nie ulega wątpliwości. Dlatego zapewne jeszcze przez jakiś czas żaden komputer nie zagrozi mistrzowi gry w Go. Jednak prawie na pewno także i ten "bastion ludzkiej dominacji" prędzej czy później padnie pod naporem stale doskonalonych programów komputerowych...

Dzisiaj gry komputerowe to ogromna dziedzina przemysłu i gospodarki. Warcaby, szachy czy trik-trak to klasyka, natomiast dzisiejsi gracze mają do dyspozycji liczne gry z ciekawie zarysowaną fabułą, z doskonale dopracowaną grafiką, z interfejsem użytkownika pozwalającym na stworzenie iluzji autentycznego uczestniczenia w "wydarzeniach" mających miejsce w grze itd. Strategia prowadzenia gry ze strony komputera przestała mieć pierwszorzędne znaczenie, chociaż oczywiście decyduje ona o stopniu trudności, a przez to także - o stopniu atrakcyjności gry. Ale warto przypomnieć o roli sztucznej inteligencji także i w tym obszarze zastosowań komputerów - i warto pamiętać małą wysepkę z wielkim drzewem.
Trwa ładowanie komentarzy...