Posts
Pełna wersja dokumentu dostępna pod adresem: http://www.deltasoftware.pl/dokumenty/Michal_Stanek-Sztuczna_inteligencja_w_grach.pdf
Wstęp
Gwałtowny rozwój komputerów w drugiej połowie ubiegłego wieku przyczynił się do znacznego postępu zarówno w nauce jak i przemyśle. Dały one możliwość realizacji rzeczy które wcześniej można było analizować jedynie teoretycznie. W głowie nie jednego naukowca zrodziło się wówczas pytanie, czy maszyna będzie w stanie dorównać kiedyś możliwością człowieka?
Zaczęła rozwijać się dynamicznie dziedzina zwana sztuczną inteligencją. Zadawano sobie pytanie w jaki sposób mierzyć zdolności maszyny? Dylemat ten rozwiązał Alan Turing konstruując słynny test Turinga. Test ten odnosi się jednak tylko do zdolności językowych. Sam Alan Turing a nawet Shannon rozważał rozszerzenie tego testu o przeprowadzenie rozgrywki w szachy, od wieków bowiem gra ta była uznawana za królową wszystkich gier. Turing stwierdził nawet w jednej ze swoich wypowiedzi z 1951 roku, że nikt nie jest w stanie napisać programu, który gra lepiej od niego samego. Mimo niezaprzeczalnie wielkiego geniuszu w tej kwestii się pomylił.
Mimo że nie ujęta w teście Turinga gra w szachy przez wielu uważana była za wyznacznik zdolności maszyny do myślenia. Określała granicę pomiędzy możliwościami ludzkiego umysłu a maszyną. Ostatecznie po 45 latach prób, zaczynając od roku 1952, kiedy to powstał pierwszy program A. Sammuela, maszyna pokonała szachowego mistrza świata.
Nie tylko szachy wzbudzały zainteresowanie uczonych. Badania i eksperymenty prowadzone były dla bardzo wielu popularnych gier, wśród nich othello, go warcaby. W wielu z nich ostateczny sukces, to znaczy zwycięstwo nad człowiekiem został osiągnięty dużo wcześniej niż w szachach. Przykładowo problem gry w warcaby uważa się obecnie za praktycznie rozstrzygnięty. Oznacza to, że w zdecydowanej większości przypadków jesteśmy w stanie określić wynik gry już po wykonaniu kilku pierwszych ruchów.
Gra, strategia i drzewo gry
Według definicji Von Noumana i Morgensterna gra to składa się z zestawu reguł określających możliwości wyboru postępowania jednostek znajdujących się w sytuacji określanej mianem konfliktu interesów. Każda z tych jednostek stara się maksymalizować swój własny zysk i jednocześnie zminimalizować zysk pozostałych graczy. Reguły gry określają też ilość informacji dostępną każdemu z graczy oraz wysokość wygranych i przegranych.
W ogólności grę można rozumieć jako rozgrywkę prowadzoną przez gracza lub graczy, zgodnie z ustalonymi zasadami gry, w celu osiągnięcia ściśle zdefiniowanego celu.
Należałoby również zdefiniować pojęcie równie ważne - strategia gry, pod którym rozumieć będziemy kompletny zbiór zasad, które determinują posunięcia gracza, wybierane zależnie od sytuacji powstających podczas gry.
Gry można podzielić również na kilka kategorii w zależności od charakterystycznych cech.
Ze względu na ilość graczy:
- Gry bezosobowe (np. Gra w życie)
- Gry jednoosobowe (puzzle, pasjans)
- Gry dwuosobowe (szachy, warcaby, otello, go)
- Gry wieloosobowe (poker, brydż)
Wygrana i przegrana:
- Gry o sumie zerowej (wygrana jednego gracza oznacza przegraną drugiego gracza) – szachy, warcaby, otello
- Gry o sumie nie zerowej – np. Dylemat więźnia
Współpraca graczy:
- Kooperacyjne (gracze współpracują ze sobą)
- Niekooperacyjne (gracze nie współpracują ze sobą)
Występowanie w grze elementu losowości:
- ałkowicie losowe (ruletka)
- Częściowo losowe (brydż i inne gry karciane)
- Całkowicie deterministyczne (warcaby, szachy, otello, go)
To czym jest gra można wyrazić również pewnym równaniem:
Gra = cel + stan początkowy + operatory
Gdzie pod pojęciem operatora rozumieć możemy stosowanie reguł gry. Działanie operatora nie musi być deterministyczne – może go określać np. rozkład zmiennej losowej, w grach częściowo losowych takich np. brydż. Każdy operator może posiadać również koszt związany z jego zastosowaniem. Należy podkreślić, że w grze dwuosobowej mamy wpływ na wybór tylko połowy operatorów.
Rozpoczęcie gry ze stanu początkowego, a następnie stosowanie możliwych operatorów prowadzi do zbudowania tak zwanego drzewa gry, którego reprezentacja przedstawiona jest na rysunku 1(rysunek dostępny w dokumencie pdf).
Algorytm Min-Max
Jednym z większych osiągnięć w teorii gier było opracowanie algorytmu min-max[KNU75]. Zasada jego działania opiera się na prostym spostrzeżeniu, że podczas gry każda ze stron stara się maksymalizować swoje zyski, przy jednoczesnej minimalizacji zysków przeciwnika1(podejście takie można zauważyć już w definicji Von Noumana i Morgensterna).
Zakładając że możemy oszacować stan gry w każdym momencie z dość dużym przybliżeniem, jesteśmy w stanie przewidzieć, które ruchy przybliżą nas do wygranej, a które nie. Oczywiście im głębiej będziemy analizować drzewo gry, tym lepiej można wybrać operatory, które prowadzą nas do wygranej. W ekstremalnym przypadku, gdy jesteśmy w stanie rozwinąć całe drzewo gry jednoznacznie możemy wybrać posunięcia prowadzące nas do wygranej. Algorytm min-max został opracowany i opublikowany przez Knutha i Moore'a w 1975 r. Stanowi on fundament działania wielu innych algorytmów. Ilustracja działania algorytmu min-max przedstawiona jest na rysunku 2 (dostępny w wersji pdf dokumentu).
Na jakość gry przy wykorzystaniu algorytmu min-max wpływają z jednej strony głębokość przeszukiwania z drugiej jakość funkcji heurystycznej. Nie da się osiągnąć zadowalających wyników jeżeli którykolwiek z tych elementów jest źle dobrany.
Algorytm min-max przyczynił się do powstania algorytmu alfa-beta obcięcia, którego działanie polega na ograniczeniu ilości rozwijanych wierzchołków drzewa gry. Dokładne opisy algorytmu Alfa-Beta obcięcia można znaleźć w pracy [KWA04].
Konstrukcja funkcji heurystycznej
Jak wspomniano we wcześniejszym rozdziale na jakość działania algorytmy alfa-beta obcięcia zasadniczy wpływ ma stworzenie odpowiedniej funkcji oceniającej. Funkcja oceniająca jest funkcją heurystyczną1, to znaczy konstruowaną w założeniu, że pewne stany gry są lepsze lub gorsze od innych. Funkcja heurystyczna zazwyczaj przyjmuje postać wielomianu postaci:
F(s) = w1 * x1 + ... + wn * xn,
gdzie:
s - to pewien stan gry, który chcemy ocenić,
x1 - do xn to pewne cechy (np. ilość pionków na planszy, zajmowanie pewnych pól szachownicy),
w1 - do wn są wagami z jakimi brana jest pod uwagę wartość pewnej cechy.
Konstrukcja funkcji heurystycznej, to znaczy dobór odpowiednich parametrów oraz ich wag, zależy zazwyczaj od projektanta (programisty). Z jednej strony podejście takie jest dobre, ponieważ pozwala podzielić problem na dwa mniejsze:
- wyboru cech branych pod uwagę,
- doboru wagi każdej z wcześniej wybranych cech.
Z drugiej natomiast pozostawia pewien element subiektywności osobie, która konstruuje taką funkcję.
GLEM – ogólny liniowy model oceniania
W odpowiedzi na problemy związane z konstrukcją heurystycznych funkcji oceniających powstał GLEM (Generalized Linear Evaluation Model). Ideą jaka przyświecała jego powstaniu była chęć stworzenia standardowego sposobu rozwiązywania klasy problemów cechujących się tym, że funkcję heurystyczną można przedstawić jako kombinację liniową dostatecznej ilości cech [BURO02]. GLEM nie zwalnia nas co prawda z obowiązku wyboru cech podstawowych, przez autorów artykułu nazwanych atomowymi. Nadal zmuszeni jesteśmy określić jakie elementy mają być brane pod uwagę. Przez cechy atomowe rozumiemy tutaj na przykład cechy takie jak obecność konkretnego pionka na konkretnym polu planszy, posiadanie konkretnej karty itp. Resztę parametrów to znaczy wartości wag z jakimi cechy te będą brane pod uwagę dobierane są przez algorytm automatycznie na podstawie dostarczonych przykładów uczących.
.... dalsza część artykułu dostępna w wersji PDF
No comments:
Post a Comment