ALG(6

286

Rozdział 12. Czy komputery mogą myśleli?

12.3.Algorytm mini-max

Wychodzimy z pozycji startowej (stan gry) i szukamy najlepszego możliwego ruchu. Mamy dwa typy węzłów: „max" i „min”. Algorytm „przypuszcza”, iż przeciwnik skonfrontowany z wieloma wyborami, wykonałby najlepszy ruch dla niego (czyli najgorszy dla nas). Naszym celem będzie zatem wykonanie ruchu, który' maksymalizuje dla nas wartość pozycji, po której przeciwnik wykonał swój najlepszy ruch (taki, który minimalizuje wartość dla niego). Analizujemy w ten sposób pewną ilość poziomów' i analizujemy ty lko te ostatnie. Wartości z tych ostatnich poziomów są „wnoszone” do góry, wedle reguł mini-maxa.

Prosty przykład prezentowany jest na rysunku 12 - 4, i ilustruje sposób wybrania pierwszego najlepszego ruchu. Wartości liczbowe reprezentują siłę rażenia danej pozycji.

Idea mim-max polega na systematycznej propagacji wartości danych pozycji, poczynając od samego dołu, aż do wierzchołka. Jeśli bieżący wierzchołek ojca reprezentuje ruchy gracza A, to z wierzchołkiem tym wiąże się maksimum z wartości jego wierzchołków potomnych.

W przypadku, gdy węzeł reprezentuje przeciwnika (gracza B), to bierze się minimum tych wartości. Dlaczego tak, a nie na przykład odwrotnie? Jest to związane z istotnym założeniem zdrowego rozsądku obu graczy: B będzie się starał maksymalizować swoje szanse zwycięstwa, czyli inaczej mówiąc: zminimalizować szanse A na zwycięstwo. Jeśli analiza całego drzewa nie jest praktycznie możliwa, algorytmy poprzestają na pewnej arbitralnej głębokości -na naszym przykładzie jest to h=2.

³ Ich ilość jest wybieralna i detenninuje głębokość zagłębienia procedury mini-miuc, W przypadku niektóiych gier. zbyt głębokie przeszukiwanie nie ma, oczywiście zbytniego sensu: są one zbyt „płytkie"!