Drzewa gier |
|
Drzewo gry - drzewo, którego węzły są możliwymi
stanami gry. A czym jest stan gry? To pewne położenie, które można osiągnąć
po wykonaniu ruchu w danej grze. Dla przykładu spójrzmy na problem z dzbanami. Mamy do dyspozycji 2 dzbany, o pojemności 4l i 3l. Celem jest doprowadzenie do sytuacji, w której wyłącznie w dużym dzbanie otrzymamy dokładnie 2l wody (stan docelowy). Początkowo oba dzbany są maksymalnie wypełnione. Ścieżek, które prowadzą do rozwiązania może być wiele, ale najbardziej pożądaną przez użytkownika jest zwykle ta najkrótsza. Aby ograniczyć nadmierny rozrost drzewa należy wykrywać stany już odwiedzone i nie powtarzać już raz wykonanych czynności. Rozpatrzmy teraz drzewo gry NIM. Na stole leży 7 zapałek (początkowo w jednej grupie) i dwaj gracze na przemian dzielą je na podzbiory o różnej liczności. Przegrywa gracz, który nie może wykonać prawidłowego ruchu. Uwaga: zapis 2,2,3 w węźle oznacza, że zapałki podzielone są na podzbiory o liczności 2, 2 i 3. Stan ten jest tożsamy ze stanami 2,3,2 i 3,2,2. Na czerwono zaznaczyłem stany, w których zwycięzcą zostaje gracz nr 1, a na zielono ten, w którym wygrywa gracz 2. Po krótkiej analizie drzewa można zauważyć, że gracz, który rozpoczyna grę, nie ma szans na zwycięstwo przy odpowiedniej grze drugiego gracza. Po dowolnym ruchu inicjującym, rywal "zmusza" gracza nr 1 (poprzez doprowadzenie do stanu 1,2,4 lub 1,3,3) do wykonania przez niego ruchu prowadzącego do stanu 1,1,2,3, a stąd już tylko jeden ruch do zwycięstwa. Grę tę można uogólnić wprowadzając założenie: przeciwnicy posiadają taką samą wiedzę o przestrzeni stanów i wykorzystują ją konsekwentnie do końca. Dodatkowo stan dobry dla jednego gracza jest jednocześnie zły dla drugiego. Gracze wykonują więc takie posunięcia, aby zmaksymalizować (zminimalizować) wartość funkcji obliczającej stan gry, ale także aby drugi gracz (który także będzie się starał wykonać jak najlepszy ruch) miał jak najgorszą możliwość wykonania posunięcia. Oczywiście przy bardziej skomplikowanych grach (szachy, warcaby) czas przeglądania kolejnych poziomów drzewa jest bardzo duży. Metodami jego zmniejszania zajmę się za chwilę. Rozpatrzmy kolejny przykład. Tym razem stany opiszę jedynie przez wartości funkcji oceny. Gracz 1 (MAX) chce oczywiście ją maksymalizować, a gracz 2 (MIN) minimalizować. Na razie umieściłem jedynie wartośći funkcji stanów końcowych. Przy każdym poziomie znajduje się też oznaczenie gracza, do którego należy wybór ruchu. Grę rozpoczyna więc gracz chcący maksymalizować wynik. Aby uzupełnić oceny pozostałych stanów zastosujmy następujący algorytm:
Widzimy więc, że gracz MAX może wygrać 1 "punkt" (znaczenie "punktów" zależy oczywiście od rozważanej gry), a jednocześnie MIN przegrywa 1 "punkt". Jest to podejście stosowane w tzw. grach o zerowej sumie. Rzadko jednak kiedy mamy możliwość (czas) przeglądania całego drzewa, czyli rozważania wszystkich możliwych ruchów (obu graczy) aż do końca gry. Zwykle musimy się ograniczyć do kilku poziomów zagłębienia, czyli do kilku możliwych posunięć od aktualnej pozycji. Funkcja oceniająca dany stan musi więc także przybliżać wartości pozostałych położeń. Projektując komputerowego gracza powinniśmy pamiętać, że w pewnych przypadkach przeglądanie i rozpatrywanie danego fragmentu drzewa jest bezcelowe. Spójrzmy na przykład: Ruch gracza MIN do stanu o wartości +3 (zaznaczony na czerwono) może zostać zablokowany przez gracza MAX, który wie już, że może wymusić stan +5 (oznaczony na zielono), gdzie MIN może liczyć na co najwyżej wynik równy 5 (MIN dąży do minimalizacji!). Dlatego też rozpatrywanie stanów objętych na rysunku pętlą jest bezcelowe, ponieważ gracz MAX nigdy nie pozwoli na dojście do sytuacji oznaczonej kolorem szarym (wartość tego stanu jest przecież gorsza od +5). W algorytmie stosujemy więc dwa parametry:
Zasady stosowania odcięć:
| |
|