Sztuczna inteligencja/SI Ćwiczenia 8

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ą).

Zadanie 9

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

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.

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?