6.1. [trzeba] Rozważmy grę kółko-krzyżyk rozmiaru 3x3 (tic-tac-toe). Definiujemy Xn jako liczbę wierszy, kolumn i przekątnych mających dokładnie n X i zero O. Analogicznie, On oznacza liczbę wierszy, kolumn i przekątnych mających dokładnie n O i zero X. Funkcja użyteczności przypisze +1 każdemu stanowi z X3 = 1 i –1 każdemu stanowi z O3 = 1. Każdy inny stan końcowy ma ocenę 0. Funkcja oceniająca jest zdefiniowana następująco:
Eval(s) = 3.X2(s) + X1(s) – (3.O2(s) + O1(s)).
a)	Ile jest możliwych przebiegów tej gry w przybliżeniu?
b)	Narysuj całe drzewo gry o wysokości 2 (np. 1 X i 1 O) i korzeniu będącym pustą planszą. Zwracaj uwagę na symetrię.
c)	Dopisz ocenę do każdego liścia drzewa.
d)	Używając algorytmu minimax, dopisz ocenę do każdego wierzchołka wewnętrznego i używaj tych wartości do wybierania pierwszego ruchu.
e)	Zaznacz wierzchołki na poziomie 2 (tzn. liście), które będą pominięte używając odcięcie alfa-beta, zakładając przy tym, że wierzchołki są wygenerowane w kolejności optymalnej dla odcięcia alfa-beta.

Rozwiązanie:
a)	Około 9! (niektóre wierzchołki nie będą rozwijane).
b)	Z symetrii, wystarczy narysować 3 synów dla korzenia: X w środku, X w rogu (1,1), X na pozycji (wierz = 1, kolumna = 2). Dla prostoty, z każdego z tych wierzchołków, narysujmy wszystkich 9 wierzchołków podrzędnych w kolejności względem (wierz, kolumna).
c)	(1,2,1,2,2,1,2,1), (1,0,1,-1,1,0,1,0), (-1, -1, 0, -2, 0, -1, 0, -1)
d)	oceny wierzchołków na 1-szym poziomie: 1, -1, -2. Ocena korzenia: 1.
e)	Dla narysowanego drzewa, wszystkie liście w 2-gim i 3-cim poddrzewach nie będące pierwszym synem są eliminowane. Takie stwierdzenie nadal zachodzi w przypadku gdyby liście są uporządkowane w kolejności optymalnej dla odcięcia alfa-beta.

6.2. [warto] Dowieść następujące stwierdzenie: Dla każdego drzewa gry, użyteczność obliczona dla gracza MAX używając strategii minimax w przypadku gracz MIN gra nieoptymalnie jest nigdy niemniejsza niż użyteczność obliczona w przypadku gracz MIN gra optymalnie. Czy potrafisz wymyślić drzewo gry, zgodnie z którym gracz MAX gra lepiej używając nieoptymalnej strategii przeciwko nieoptymalnemu graczowi MIN? 

Odp.: Dla ustalonego drzewa gry, gdyby dla wierzchołków MIN zamiast funkcji MIN używamy funkcji zwracającej wartość pewnego syna, to wartość każdego wierzchołka będzie niemniejsza niż w oryginalnym przypadku.
W grze przeciwko nieoptymalnemu graczowi, można używać następującej modyfikacji:
a)	Oprócz użyteczności obliczonej w normalny sposób, obliczamy także użyteczność ważoną względem odpowiedniej dystrybucji prawdopodobieństwa dla gracza MIN (dla gracza MAX nadal używamy funkcji MAX). W ten sposób, dla każdego wierzchołka mamy parę wartości (\alpha, \alpha’).
b)	Do wybierania ruchu możemy używać pewnego uporządkowania, np.
-	(a,a’) <= (b,b’) jeśli a < b lub a = b i a’ < b’
-	(a,a’) <= (b,b’) jeśli 0,9*a + 0,1*a’ <= 0,9*b + 0,1*b’
-	...

6.3. [można] Rozważmy następującą grę między dwoma graczami:
Stan początkowy:
A _ _ B
1 2 3 4
Gracz A wykonuje pierwszy ruch. Każdy gracz przesuwa swoją literę w lewo lub w prawo do sąsiedniej pustej pozycji. Jeśli przeciwnik zajmuje sąsiednią pozycję, to gracz może przekroczyć do następnej pustej pozycji. (Na przykład, jeśli A jest na 3-ciej pozycji a B na 2-giej pozycji, to A może przesuwać się do 1-szej pozycji.) Gra zakończy kiedy jeden gracz dostaje się na drugiej końcowej pozycji. A wygra jeśli zajmuje 4-tą pozycję, B wygra jeśli zajmuje 1-szą pozycję. 
a)	Narysuj całe drzewo gry, używając następujących konwencji:
•	Napisz każdy stan jako parę (Sa, Sb), gdzie Sa i Sb oznaczają pozycje A i B.
•	Obramuj każdy stan końcowy prostokątem a jego ocenę kółkiem.
•	Obramuj każdy "stan zapętlący" podwójnym prostokątem. Ponieważ nie jest jasne jaka będzie ocena dla takich stanów, napisz "?" w kółku jako ocenę.  
b)	Oblicz ocenę dla każdego wierzchołka i napisz ją w kółku. Wyjaśnij jak postępujesz z wartością "?" i dlaczego.
c)	Wyjaśnij dlaczego standardowa strategia minimax nie działa dla tego drzewa gry. Czy twój zmodyfikowany algorytm daje optymalną decyzję dla wszystkich gier z pętlami. 
d)	Ta gra może być uogólniona dla n pozycji dla każdego n > 2. Dowieść, że A wygra jeśli n jest parzysta i przegra jeśli n jest nieparzysta.

Odp.:
a)	...
b)	Traktujemy "?" jako nieznana (lub neutralna) wartość, czyli 0, i postępujemy zgodnie z strategią minimax. (To podejście jest podobne do semantyki 3-wartościowej programów z negacją w logice.) Korzenie będzie miało wartość 1. (Dla pewności, możemy podstawić wartości otrzymane dla stanów zapętlących i sprawdzić czy nowe drzewo jest "stabilne". Nie mam dowodu, że nowe drzewo będzie stabilne.)
c)	Standardowa strategia minimax nie działa dla drzew z pętlami, ponieważ takie drzewa są nieskończone po rozwijaniu. Proponowana metoda daje optymalną decyzję dla gier z pętlami. Uzasadnienie jest następujące: Gdyby po obliczaniu wierzchołek z "?" nadal ma wartość 0, to wtedy ta wartość jest "stabilna", a gdyby dostanie wartość +1 lub –1, to ta wartość jest zdecydowana poprzez jakiegoś syna, który ma konkretną wartość. (To nie jest jednak dowód.)
d)	Jeśli n jest parzysta, to strategią wygraną dla A jest zawsze przesuwać się w prawo. Jeśli n jest nieparzysta, to strategią wygraną dla B jest zawsze przesuwać się w lewo.

6.7. [trzeba] Dowieść, że po pozytywnej liniowej transformacji wartości liści (tzn. transformacja z x na a.x+b dla a > 0), wybór ruchu jest niezmieniony w drzewie gry nawet kiedy są wierzchołki z prawdopodobieństwem (chance nodes).

Odp.: Taka transformacja jest hormofizmem względem operatorów min, max, średnia (average).

6.9. [warto] Dyskutuj co należy zrobić dla gier z ograniczeniem czasowym.

Odp.: Podstawowym punktem wyjścia jest przeszukiwanie iteracyjnie pogłębiane. Są jeszcze problemy do dyskusji: a) stany niestabilne, b) dla najpotężniejszych ruchów możemy głębiej zbadać. Jak połączymy te cele? Niech studenci na to odpowiadają.

6.13. [warto] Program Chinook (dla warcaby) używa wielkiej biblioteki zakończeń, która daje dokładną wartość dla każdego zakończenia mającego 8 lub mniej pionków na planszy. Jak można efektywnie wygenerować takie bazy? 

Odp.: programowanie dynamiczne.

6.15. [warto] Opisz jak należy zmodyfikować algorytmy minimax i alfa-beta dla gier dwuosobowych w których każdy gracz ma swoją funkcję oceniającą (dla liści). Możemy założyć, że każdy gracz zna funkcję oceniającą przeciwnika. Jeśli nie ma żadnego założenia o wartości wygrającej i wartości przegrającej, czy można odciąć wierzchołki używając strategii alfa-beta?

Odp.: Jeśli obie funkcje oceniające są zgodne z sobą, tzn. f(s) <= f(s’) wttw g(s) <= g(s’), to nic nie trzeba zmienić (tzn. niech MAX używa swojej funkcji dla wszystkich liści drzewa). Załóżmy, że są one nie zgodne. Jeśli MAX bardziej ufa swojej funkcji oceniającej, to niech dalej używa swojej funkcji cały czas (zobacz 6.2.). Gdyby MAX nie wie która funkcja jest lepsza, może postępować w następujący sposób:
a)	Dla minimax: dla liści znajdujących się na poziomach MIN, używa swojej funkcji; dla liści znajdujących się na poziomach MAX, używa funkcji przeciwnika plus pozytywnej liniowej transformacji (zobacz 6.7.) do utożsamiania dwóch przedziałów ocen.
b)	Dla alfa-beta: Ponieważ strategia alfa-beta jest zastosowalna dla każdego drzewa minmax, możemy używać jej normalnie. (A założenia o wartości wygrającej i wartości przegrającej dla dwóch graczy? Niech te wartości będą skończone, aby transformacja ocen jest wykonywalna.)

Jeśli powyższe zadania nie są wystarczy na jedno zajęcie, to proponuję podać studentom zadanie o opracowaniu funkcji oceniającej dla konkretnej gry, np. go-moku.