Sztuczna inteligencja/SI Ćwiczenia 8

From Studia Informatyczne

Spis treści

Zadanie 1

Weźmy pod uwagę grę w kółko i krzyżyk na planszy 3x3 i zadanie wyboru ruchu dla gracza X w następującej sytuacji na planszy:

O O  
X    
O   X

Podać pełne drzewo gry dla tej sytuacji początkowej i dokonać oceny wszystkich węzłów za pomocą algorytmu minimaks z punktu widzenia gracza X. Dla węzłów odpowiadających zakończonym partiom przyjąć ocenę 1 w przypadku zwycięstwa gracza X, -1 w przypadku przegranej gracza X oraz 0 w przypadku remisu.

Zadanie 2

Weźmy pod uwagę grę w kółko i krzyżyk na planszy 3x3, w której po pierwszych 3 ruchach uzyskano następującą sytuację na planszy:

O O  
    X
     

Jako następny ruch wybiera gracz X. Jaki jest rozmiar (liczba węzłów) pełnego drzewa gry dla tej sytuacji? Jaki jest rozmiar drzewa gry obciętego do 3 poziomów?

Zadanie 3

W grze w kółko i krzyżyk na planszy 3x3 prześledzić proces wyboru ruchu dla gracza X za pomocą obciętego algorytmu minimaks w następującej sytuacji na planszy:

O X  
  O X
  O  

Limit głębokości wynosi 4. Ocena dla partii rozstrzygniętych wynosi 3 w przypadku wygranej gracza X, -3 w przypadku przegranej gracza X oraz 0 w przypadku remisu. Do oceny partii nierozstrzygniętych stosowana jest funkcja heurystyczna, której wartość jest równa różnicy między liczbą pozostałych szans wygranej dla gracza X i liczbą pozostałych szans wygranej dla gracza O, przy czym przez szansę wygranej rozumiana jest możliwa do uzyskania (niezablokowana przez przeciwnika) trójka w wierszu, kolumnie lub na przekątnej.

Zadanie 4

Dla drzewa gry analizowanego przez obcięty algorytm minimaks w poprzednim zadaniu sprawdzić, czy możliwe jest zastosowanie cięć alfa lub beta.

Zadanie 5

Rozważmy uproszczoną grę w warcaby z planszą 4x4, w której każdy z graczy dysponuje dwoma pionami ustawionymi początkowo na czarnych polach przy krawędziach planszy. Ile wynosi liczba wszystkich możliwych sytuacji na planszy w tej grze (wystarczy podać możliwie dokładne górne ograniczenie)?

Zadanie 6

Dla gry opisanej w poprzednim zadaniu podać drzewo gry z głębokością ograniczoną do 3 poziomów i ocenić każdy węzeł za pomocą obciętego algorytmu minimaks, przyjmując do oceny węzłów terminalnych funkcję heurystyczną, której wartość obliczana jest jako różnica łącznego wskaźnika pozycji dla graczy (suma odległości każdego piona od początkowej krawędzi planszy dla gracza minus suma analogicznych odległości dla przeciwnika).

Zadanie 7

Zaproponować modyfikację zasady minimaksu do gry z przeciwnikiem zachowującym się całkowicie losowo.

Rozwiązanie

Jeśli przeciwnik zachowuje się całkowicie losowo można przyjąć jako ocenę węzła wewnętrznego na poziomie przeciwnika średnią arytmetyczną (wartość oczekiwaną) ocen jego węzłów potomnych.

Zadanie 8

Zaproponować modyfikację zasady minimaksu do gier, w których o zestawie możliwych do wybrania ruchów graczy decyduje czynnik losowy (np. rzut kością).

Rozwiązanie

W każdym węźle nieterminalnym można wyznaczać wartość oczekiwaną oceny z uwzględnieniem rozkładu prawdpopodobieństwa czynnika losowego. Dla każdej konkretnej wartości czynnika losowego rozpatrywane są te ruchy, które są możliwe do wykonania przy tej wartości.

Innymi słowy: gracz wybiera taki ruch, który maksymalizuje oczekiwaną ocenę pozycji (a jego przeciwnik taki, który ją minimalizuje).

Zadanie 9

Zaproponować modyfikację zasady minimaksu do gier, w których o wyniku wykonanego ruchu decyduje czynnik losowy (np. rzut kością).

Rozwiązanie

Każdy ruch może prowadzić do jednej z wielu pozycji (węzłów) zależnie od czynnika losowego. Każdą z tych pozycji należy ocenić stosując algorytm rekurencyjnie.

Oceną ruchu jest, w tym przypadku, nie ocena pojedynczej pozycji ale oczekiwana ocena pozycji, które mogą nastąpić po wybraniu tego ruchu.

Oceną węzła jest maksymalna dla gracza, a minimalna dla przeciwnika, ocena ruchu.

Zadanie 10

Zaproponować zmodyfikowaną wersję obciętego algorytmu minimaks, w której podaje się jako argument maksymalny dostępny czas obliczeń.

Zadanie 11

Zaproponować sposób sterowania „poziomem zaawansowania” gry za pomocą algorytmów opartych na zasadzie minimaksu.

Rozwiązanie

Przykładowe sposoby:

  • zmienianie ograniczenia na głębokość przeszukiwania drzewa gry lub czas obliczeń
  • modyfikacja funkcji heurystycznej (np. coraz bardziej skomplikowana dla coraz wyższych poziomów gry)
  • wprowadzenie regulowanych elementów losowości przy wyborze ruchu (np. losowe zaburzanie ocen węzłów), co może prowadzić do popełniania błędów przez algorytm

Zadanie 12

Zaproponować funkcję heurystyczną do oceny sytuacji na planszy w grze w warcaby.

Zadanie 13

Czy stosowanie pełnego algorytmu minimaks (bez funkcji heurystycznej) gwarantuje zwycięstwo w grze niezależnie od zachowania przeciwnika?

Rozwiązanie

W ogólnym przypadku nie gwarantuje.

W niektórych grach, np. kółko - krzyżyk, optymalna gra obydwu graczy prowadzi do remisu.

Istnieją także gry, w których dla jednego z graczy nie istnieje strategia wygrywająca, czyli przy najlepszej własnej grze przeciwnik zawsze wygrywa.

Zadanie 14

Czy i pod jakimi warunkami obcięty algorytm minimaks gwarantuje uzyskanie najlepszego możliwego wyniku partii?

Rozwiązanie

Każdy z poniższych warunków gwarantuje uzyskanie najlepszego możliwego wyniku partii:

  • funkcja heurystyczna daje dokładnie takie same oceny pozycji jak analiza pełnym algorytmem minimaks
  • głębokość drzewa gry jest mniejsza niż ograniczenie na głębokość w algorytmie
  • wszystkie możliwe przebiegi gry prowadzą do tego samego wyniku