W dziale Moje aplikacje możecie się zapoznać z jednym ze stworzonych przeze mnie programów - jest to gra Tysiączek, będąca implementacją gry Tysiąc w kości.
W grze tej przeciwnikiem (a raczej przeciwnikami, ponieważ może w nią grać do sześciu graczy) może być komputer, a dokładniej mówiąc, algorytmy sztucznej inteligencji (AI). Oto ich opis dla tych, którzy są zainteresowani, jak się pisze tego typu gry, w których można grać z komputerem.
Dlaczego od razu w wersji 2, a nie 1? Otóż odpowiedź jest prosta: program w wersji 1.x nie miał wcale sztucznej inteligencji, można było grać jedynie z realnymi graczami. AI pojawiła się w wersji 2.x programu, stąd też przyjąłem, że i sztuczna inteligencja ma od razu wersję 2. Takie to właśnie trochę sztuczne wyjaśnienie .
Algorytmy sztucznej inteligencji zastosowane w grze są tradycyjne, czyli nie wykorzystują żadnego uczenia maszynowego. Wynika to stąd, że przede wszystkim gra jest bardzo losowa - polega na rzucaniu kostek, a jedyne decyzje, jakie należy podejmować, polegają na tym, jakie kostki wybrać, a także, czy ponownie nimi rzucać. Zbiór decyzyjny gry jest więc prosty i niewielki. Użycie uczenia maszynowego w tym przypadku mogłoby być czymś w rodzaju strzelaniem z armaty do muchy. Co innego, gdyby gra miała złożone drzewo decyzyjne - wówczas warto byłoby użyć jakiejś biblioteki C++ obsługującej uczenie maszynowe, zdefiniować model, wytrenować go, a następnie zastosować w programie.
Ponieważ algorytmy są tradycyjne, opierają się więc w zasadzie na wyrażeniach warunkowych if, które reagują na określone informacje i statystyki z gry (na przykład, ile wyrzucono jedynek, ile gracz wyrzucił w danej kolejce, czy przeszedł już do etapu drugiego itp.) i odpowiednio sterują działaniem programu.
W wersji 2. sztucznej inteligencji uwzględniamy także następujące zdarzenia:
AI w wersji 2. działa całkie nieźle i spokojnie można sobie już grać z przeciwnikiem komputerowym. Ma ona jednak jedną podstawową wadę. Gracz w trakcie gry skupia się mianowicie na sobie samym - zlicza punkty, sprawdza, czy ma wystarczającą liczbę kostek, by jeszcze sensownie rzucić itp. Oczywiście, jest to poprawne, jednak algorytm nie przygląda się, jak w tym czasie zachowują się inni gracze, tzn. ile mają punktów, jak im idzie, czy może zagrażają graczowi bieżącemu (pamiętajmy, że z reguł gry w Tysiąca wynika, iż po przeskoczeniu danego gracza zostaje mu odjętych 100 punktów).
Zatem wersja 3. sztucznej inteligencji została tak napisana, by mogła też uwzględniać interakcje między graczem bieżącym a pozostałymi. Gdy gracz ma już zaliczony wynik w danej kolejce, algorytm sprawdza, czy czasem blisko niego nie znajdują się inni gracze, a jeśli tak, zwiększa odpowiednio prawdodpodobieństwo zaryzykowania kolejnego rzutu (nawet jeśli dysponuje małą liczbą kostek), byleby tylko odsunąć od siebie groźbę przeskoczenia.
Co oznacza sformułowanie "blisko gracza"? Przyjmujemy miarę odległości, która polega na różnicy miedzy wartością sumarycznego wyniku dla gracza bieżącego a wartością wyniku gracza innego. Jeśli tak odległość jest mniejsza niż pewna przyjęta wartość progowa, algorytm zaczyna zwiększać prawdopodobieństwo kolejnego, ryzykownego już rzutu (pamiętajmy, że dzieje się to wtedy, gdy gracz ma już zagwarantowane zaliczenie bieżącego wyniku do wyniku sumarycznego, czyli mógłby już nacisnąć przycisk "Koniec").
Zwiększanie prawdopodobieństwa tego ryzyka nie jest też trywialne, ponieważ zależy po pierwsze od odległości (im bliższa odległość, tym bardziej znaczące zwiększenie prawdopodobieństwa), a po drugie od tego, ilu graczy jest w "bliskiej odległości". W tym celu wykorzystano funkcję liniową postaci y = -ax + b. Za pomocą niej uzyskuje się wynik, o który zwiększa się początkową wartość prawdopodobieństwa. Wartość x jest obliczoną odległością. Ponieważ funkcja ma ujemny parametr a, więc działa w sposób odwrotnie proporcjonalny - im większa odległość, tym mniejszy przyrost prawdopodobieństwa (i vice versa). Taka funkcja jest wyznaczana dla każdego z graczy, a wynik sumowany. Jeśli uzyskamy 100%, oznacza to, że gracz na pewno rzuci ponownie kostką.
Inną sprawą, która została uwzględniona w algorytmie w wersji 3., jest zachowanie gracza pod koniec etapu 2. Pamiętajmy, że po etapie 2. gracz przechodzi do finalnego etapu 3., w którym musi wyrzucić 100 w danej kolejce, a jego położenie na skali wyników już się nie zmienia. Oznacza to, że gdy gracz uzyska na przykład 910 punktów, wówczas będzie je już miał przez cały czas. Wiąże się z tym niebezpieczeństwo, że może zostać łatwo przeskoczony przez innego gracza, który uzyska wynik większy niż 910. Wynika stąd, że warto do etapu 3. wejść mając tak dużo punktów, jak tylko możliwe (im bliżej 1000, tym lepiej). Dzięki temu prawdopodobieństwo, że inny gracz nas przeskoczy, będzie niewielkie.
To właśnie uwzględnia sztuczna inteligencja w wersji 3. Po pierwsze, umożliwia graczowi uzyskanie dobrej pozycji wyjściowej w celu "zaatakowania" etapu 3., tzn. sytuuje go blisko granicy 900. Po drugie, jeśli gracz zapewni sobie już przejście do etapu 3., sprawdza, czy jest blisko 900 (ale oczywiście "po drugiej stronie"), a jeśli tak, stosuje omówioną już wcześniej funkcję zmiany prawdodpodobieństwa ryzyka w celu wykonania kolejnego rzutu (im gracz znajdzie się bliżej granicy 900, tym wyższe będzie prawdopodobieństwo dodatkowego rzutu).
Jako ciekawostkę podam, że program w wersji 3.x wizualnie informuje, kiedy algorytm zaczyna ryzykować. Jeśli gracz AI będzie chciał zaryzykować, by uniknąć przeskoczenia, pasek "Pole rzutów" zmieni kolor na żółty. Jeśli gracz będzie się chciał odpowiednio ustawić na dobrej pozycji wyjściowej, by zaatakować etap 3., pasek stanie się zielony. I wreszcie, jeśli gracz AI będzie się chciał oddalić od granicy 900 punktów, pasek zmieni kolor na niebieski.
W wolnej chwili porównałem działanie obu algorytmów - przez kilka weekendów rozgrywałem gry przy użyciu graczy komputerowych wyposażonych w różne wersje AI. W grach brało zawsze udział 6 graczy, z czego połowa miała algorytm AI w wersji 2, a połowa w wersji 3. Wyniki zapisywałem, a następnie przyjrzałem się im, by wyciągnąć odpowiednie wnioski.
Ponieważ rozegrałem dokładnie 165 gier, od razu zaznaczę, że taka liczba jest zupełnie niewystarczająca, by być zupełnie pewnym, który z algorytmów jest lepszy. W rzeczywistości powinno się rozegrać miliony gier, aby w tak losowej rozgrywce znaleźć w miarę pewną odpowiedź. Nawet jeśli potraktowalibyśmy pojedyczy rzut kostką przez jednego gracza jako oddzielną grę, to przy bardzo zgrubnym założeniu, że w ciągu jednej rozgrywki gracz rzuca kostką w przybliżeniu 150 razy, uzyskalibyśmy 150 * 6 * 165 = 148500 "gier", co w dalszym ciągu jest wartością zbyt niską. Przyglądając się takim ograniczonym wynikom można jednak spróbować wyciągnąć pewne wstępne wnioski, co też uczynię.
To, co nas najbardziej interesuje, to informacja, który algorytm był lepszy. Zwyciężył algorytm w wersji 3. w stosunku 59 do 41. Oznacza to, że 59% gier zakończyło się zwycięstwem gracza z algorytmem AI w wersji 3., a 41% gracza z algorytmem w wersji 2.
Niektórzy mogą być zawiedzeni, bo spodziewali się lepszego wyniku. Oto wyjaśnienie.
Po pierwsze, gra jest bardzo losowa, co w dużym stopniu przeszkadza algortymowi w wersji 3 na pokazanie swoich zalet. Co z tego, że jakiś gracz zaryzykuje dwa razy i uniknie przez to przeskoczenia, skoro inny może za jednym razem wyrzucić 100 lub więcej punktów i zniweczyć wszelkie starania.
Po drugie, algorytm w wersji 3 ryzykuje, a więc oznacza to, że czasem ryzyko się opłaci, ale w innych przypadkach po prostu nie uda się zdobyć żadnego punktu, bo po rzucie nie wypadnie nic, co można by zaliczyć do wyniku. Oznacza to, że dość często proste "ciułanie" punktów w sposób zachowawczy, tak jak to czyni algorytm w wersji 2, jest co najmniej tak samo skuteczne, jak agresywna polityka algorytmu w wersji 3.
Widać to po ciekawym trendzie w wynikach. Otóż mimo że ogólnie zwyciężył algorytm w wersji 3, jednak drugie miejsce bezsprzecznie należy się algorytmowi w wersji 2 - wygląda na to, że gracze w wersji 3. czuli zawsze na swoich plecach oddech graczy w wersji 2. Mamy więc pierwsze miejsce dla gracza z algorytmem w wersji 3, drugie miejsce dla gracza z algorytmem w wersji 2, natomiast pozostali gracze z algorytmem w wersji 3. zdobywali przeciętnie bardzo odległe miejsca (w okolicach 4-6 pozycji). Wynika to ze wspomnianego faktu podejmowania ryzyka - jednemu graczowi z AI w wersji 3 udawało się dość często wykorzystać podejmowane ryzyko, natomiast pozostali dwaj gracze, który ryzykowali, niestety nie zdobywali żadnych punktów i byli przeskakiwani przez "spokojnych" graczy z AI w wersji 2. Wniosek z tego jest taki, że ryzyko, by się opłaciło, wymaga jeszcze odrobiny szczęścia - jak w życiu .