Fotografia autorstwa Jensa Gyldenkærne Clausena

Na pewno grałeś kiedyś w gry planszowe – jeśli nie w szachy, to przynajmniej w warcaby. Albo w gry na kartce, jak kółko i krzyżyk. Jestem również pewien, że miałeś do czynienia z komputerowymi wersjami takich gier, gdzie Twoim przeciwnikiem był gracz komputerowy. Czy zastanawiałeś się kiedyś nad tym, jak to się dzieje, że wykonuje on właśnie taki a nie inny ruch? Albo nad tym czy ruch, który wykonuje jest najlepszym z możliwych? Kluczem do zrozumienia tego zagadnienia są algorytmy sztucznej inteligencji wykorzystywane w grach. Może brzmieć to groźnie, ale tak naprawdę jest to niesamowicie ciekawe zagadnienie!

Jak komputer widzi rozgrywkę?

To pierwsza rzecz, którą trzeba wiedzieć. Wyobraźmy sobie początek partii warcab. Widzimy planszę, na niej ułożonych 12 pionków białych i 12 czarnych. Komputer może “widzieć” to mniej więcej tak :

10101010
01010101
10101010
03030303
30303030
02020202
20202020
02020202

8 rzędów, w każdym po 4 pola używane + 4 pola, na których gra nie będzie się toczyła. Następnie wraz z przebiegiem gry zmienia się zawartość planszy. Komputer wykonując ruch wybiera sobie jeden ze swoich pionów (niech będą one oznaczone numerem 2) i ustawia go w wolnym miejscu (nr 3). Zanim jednak to zrobi, musi zdecydować o tym, który ruch wykona, czyli musi ocenić, który ruch przyniesie mu najwięcej korzyści.

Podejmowanie decyzji

Najważniejszą kwestią przy wyborze ruchu jest tzw. stan gry. Jest to liczba (tak, 1 liczba), która określa obecny układ na planszy. Pierwszy z dwóch rywalizujących ze sobą graczy musi dbać o to, aby liczba ta była jak największa, drugi natomiast musi ją stale zmniejszać. Stan gry jest określany przez pewien wymyślony przez programistów algorytm. Powracając do przykładu warcab, najprostszym (lecz niekoniecznie najlepszym!) sposobem liczenia stanu gry będzie sprawdzenie ilości pionków obu graczy a następnie odjęcie tych liczb od siebie. I tak w przypadku, gdy gracz A ma 5 pionków, a gracz B 7, stan gry będzie wynosił -2. Spójrzmy teraz na przykładową rozgrywkę :

Ruch wykonują pionki czarne. Stan gry w tej chwili wynosi 0, jednak za chwilę będzie wynosił -2. Świetnie? Nie tak prędko! Zaraz po tym gracz biały będzie miał potrójne bicie i nici z przewagi wypracowanej przez przeciwnika! W tej chwili nie można już nic zmienić, jednak na pewno można było uniknąć takiej sytuacji! Jak ma to zrobić komputer?

Przeszukiwanie

Komputer musi metodą prób i błędów sprawdzać wszystkie możliwe ruchy. Co więcej, nie ogranicza się do najbliższego ruchu, ale do kilku, a nawet kilkunastu ruchów w przód (nie mogę znaleźć w tej chwili potwierdzenia tej informacji, ale wydaje mi się, że słynny Deep Blue w 1997 tocząc szachowy pojedynek z Garri Kasparowem przeszukiwał do 20 najbliższych ruchów). O ile w warcabach, czy np. jeszcze prostszej grze – kółko i krzyżyk – ilość ruchów możliwych do wykonania w jednej turze jest mocno ograniczona, w warcabach dodatkowo ruchy te są często wymuszone przez możliwość bicia, o tyle już np. w japońskim Go w pierwszej turze można wykonać 361 ruchów, a w następnych o 1 mniej. Policzmy sobie – 361*360*359 daje nam ponad 46 milionów! W szachach średnia liczba możliwych do wykonania ruchów to ok. 35 i choć wydaje się to dużo mniej, to już przy przeszukiwaniu na głębokości 5 ruchów w przód otrzymujemy ponad 50 milionów ruchów do sprawdzenia. A dla każdego ruchu należy obliczyć stan gry, którego liczenie nie musi polegać jedynie na zliczaniu i odejmowaniu pionków, a może na niego wpływać (w zależności od gry) wiele różnych czynników. Czy komputer rzeczywiście musi wykonywać aż tyle obliczeń?

Algorytmy przeszukiwania

Na szczęście nie jest tak źle, wymyślono wiele algorytmów, które usprawniają przeszukiwanie. Nie będę się tutaj rozpisywał na ich temat, wspomnę jedynie o algorytmie, który jest prawdziwym fundamentem sztucznej inteligencji w grach komputerowych i to na jego podstawie tworzona jest większość algorytmów. Algorytm ten nosi nazwę Alfa – Beta. Co najciekawsze, algorytm ten potrafi odnaleźć rozwiązanie optymalne, tj. takie, które doprowadzi do zwycięstwa! Jednak gdybyśmy chcieli zagrać w szachy z komputerem, który sprawdza wszystkie możliwe opcje jakie pojawią się podczas rozgrywki, na jego pierwszy ruch czekalibyśmy biliony lat! Co to oznacza?

Da się wygrać w szachy z komputerem!

Na pewno jednak nie jest to proste – nawet Kasparow 12 lat temu uległ komputerowi. Jednak nie chodzi tylko o to, żeby być mistrzem – szachy, warcaby, czy tysiące innych gier planszowych to świetna rozrywka dla każdego, czy to dziecka, czy dorosłego. A jeśli nie macie partnera do gry – zawsze możecie spróbować swoich sił na Kurniku czy w jakimkolwiek programie komputerowym – tam można ustawić poziom trudności na “łatwy” i grać ;).

Na koniec ciekawostka : wspomniane wcześniej Go jest jedną z niewielu gier, w których komputer wciąż nie potrafi wygrać z człowiekiem. Ma ona banalne zasady, lecz bardzo trudno jest ocenić stan gry w danej chwili. Polecam wam spróbowanie swoich sił, ja co jakiś czas bardzo chętnie wracam do tej gry i próbuję się zmierzyć czy to z komputerowym czy z ludzkim przeciwnikiem.