Wejściówka 2 - WDSI

1. Co to jest efekt horyzontu?
Jest to wada algorytmu minimaks polegająca na tym, iż analizujemy drzewo gry do ustalonej głębokości - czyli do ustalonego horyzontu przeszukiwań, tuż poza horyzontem pewien stan może całkowicie zmieniać ocenę pozycji. Może się to objawiać tym, że pozycja którą uznaliśmy za najbardziej atrakcyjną tuż za badanym horyzontem jest pozycją przegrywającą grę, lub w drugą stronę gdy odrzucona pozycja poza horyzontem okazuję się pozycja wygrywającą.

2. Co to jest ruch?
Ruch to dwa półruchy, każdy innego gracza. Gdy dwóch graczy wykona po półruchu następuje pełen ruch.

3. Co to jest półruch?
Półruch to ruch jednego z graczy np. przesunięcie pionka w grze. Dwa półruchy - jeden gracza pierwszego, drugi gracza drugiego traktowane są jako całe posunięcie.

4. Co to jest głębokość?
Głębokość to liczba wierzchołków, przez które należy przejść od korzenia drzewa do wierzchołka którego głębokość podajemy. Algorytm minimax ma ustaloną głębokość do której rozwijamy drzewo gry. Im większa głębokość tym lepsze wyniki działania algorytmu lecz zwiększone wykorzystanie mocy obliczeniowej.

5. Opisz algorytm minimax.
Mając dwóch graczy - minimalizującego oraz maksymalizującego oraz funkcję oceniającą wartość stanu gry budujemy drzewo wszystkich możliwych stanów do pewnej ustalonej głębokości. Po zbudowaniu drzewa analizujemy je zaczynając od liści drzewa (dół) i przesuwając się do góry (korzeń) wybieramy optymalne wybory dla każdego z graczy, gracz minimalizujący zawsze wybierze wartość najmniejszą a gracz maksymalizujący największą. Im większa głębokość przesukiwania tym lepsze wyniki działania algorytmu.

6. Opisz przycinanie alfa-beta.
Alfa - gwarantowana dotychczas wypłata gracza maksymalizującego, na początku jest to -nieskończoność.
Beta - gwarantowana dotychczas wypłata gracza minimalizującego, na początku jest to nieskończoność.
Dzieci i ich poddrzewa są analizowane dopóki alfa < beta.
Gdy alfa >= beta to przestajemy analizować kolejne dzieci i ich poddrzewa ponieważ nie będą one miały wpływu na całe drzewo.
Drzewo alfa-beta daje takie same wyniki (oceny ruchów) co minimax. Algorytm jednak znacząco redukuję liczbę węzłów drzewa minimax. Algorytm nie analizuje gałęzi której wynik nie jest potrzebny ponieważ pewnym jest, że gracz wybierze inną - korzystniejszą dla siebie opcję.

7. Różnice i podobieństwa minimax i alfa-beta
Różnice:
- Drzewo przy algorytmie alfa-beta ma zredukowaną liczbę węzłów.
- Alfa-beta cechuje się mniejszą złożonością obliczeniową lecz jest ona zależna od porządku odwiedzania stanów potomnych.
Podobieństwa:
- Algorytmy oddają te same wyniki (oceny ruchów).
- Przebieg algorytmu bardzo zbliżony, drzewo minimaks oraz alfa-beta jest budowane w podobny sposób.