ALG(7

12.3. Algorytm mini-max 287

Załóżmy również, że wartości liczbowe węzłów z ostatniego poziomu, zostały nam dostarczone przez pewną znaną funkcję ewaluacja. W analizowanym przykładzie został wybrany węzeł z wartością /=max(-/, 2, I). Pamiętajmy, że ten wybór zależy od głębokości analizy drzewa gry i przy' innej wartości h pierwszy ruch mógłby być zupełnie inny!

Istnieje poprawiona wersja algorytmu mini-max, która pozwala znacznie skrócić czas analizy, eliminując zbędne porównania wartości pochodzących z pod-drzcw i tak nie mających szansy na wyniesienie podczas propagacji wartości wg reguły mini-mea. Jest ona powszechnie znana jako algorytm cięć a-p. Przykładowo, wartość -I wyniesiona do góry na rysunku 12-4 (szacujemy węzły terminalne od lewej do prawej) sugeruje, iż nie ma sensu analizować tych części drzewa, które wyniosłyby wartość mniejszą niż -I. Jest to oczywiste wykorzystanie matematycznych własności funkcji min i max...

Przedstawmy wreszcie tajemniczą procedurę mini-max. W celu ułatwienia jej implementacji programowej zostanie ona zaprezentowana w pseudo-kodzie¹.

Algorytm przeszukiwania drzewa gry, z wykorzystaniem reguły mini-mwc, ma następującą postać':

MiniMex{węzeł w) ł

jeśli w jest typu MAX to v=-°°; jeśli w jest typu MIN to v=+°°; jeśli w jest węzłem termi nal -lym to zwróć ewaluacja(w);

Pi, Pz, ■■■ Ptr = generuj (w) ; // potomkowie węzła w. dla j=l...k wykonuj

(

jeśli w jest typu KAX to

v=-nax (v, mimimax (p*) ) ;

w przeciwnym wypadku

v=min (v, [v, mimimax (pk) ) ;

)

zwróć v;

)

Dotychczas unikaliśmy dyskusji na temat funkcji ewaluacja. Powód jest dość prozaiczny: funkcja ta jest silnie związana z rozpatrywaną i nie ma sensu jej omawiać poza jej kontekstem.

⁴    Warto sobie zdać sprawę, że konkretna implementacja procedury mini-mwc może być zmieniona nie do poznania przez grę i sposób jej reprezentacji.

⁵    Ta wersja jest nastawiona na zwycięstwo gracza MAX.