Algorytm min-max: Różnice pomiędzy wersjami

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
Przywrócenie uciętego opisu algorytmu alfa-beta
Znacznik: Edytor kodu źródłowego 2017
Linia 13:
Posiadając funkcję '''S''' oceniającą wartość stanu gry w dowolnym momencie (gracz min chce ten stan zminimalizować, a gracz max zmaksymalizować), obliczamy drzewo wszystkich możliwych stanów w grze do pewnej głębokości(ograniczonej zazwyczaj przez naszą moc obliczeniową). Zakładając, że rozgałęzienie drzewa stanów jest stałe i wynosi '''b'''(czyli na każdy ruch można odpowiedzieć '''b''' innymi), a głębokość '''d''' (tyle ruchów do przodu symulujemy algorytmem minmax), to mamy stanów końcowych, dla których obliczamy wartość stanu gry funkcją '''S'''. Zaczynamy przeglądanie od stanów końcowych, symulując optymalne wybory dla obu graczy, tak aby na głębokości '''d'''(w liściach drzewa) była dla nich optymalna liczba '''S''' (stan gry po wykonaniu '''d''' ruchów). Tak więc gracz min zawsze wybiera ruch, który prowadzi do mniejszej wartości końcowej, a gracz max – przeciwnie. Po przeprowadzeniu tej symulacji gracz, który znajduje się w korzeniu drzewa (aktualnie wykonujący ruch), ma pewność, że jego ruch jest optymalny w kontekście informacji o stanie gry z przeprowadzonej symulacji algorytmem minimax na głębokość '''d''' (tzn. maksymalizuje minimalny zysk).
 
Algorytm służy do wybrania optymalnego ruchu w danym momencie, dlatego po ruchu przeciwnika musimy przeprowadzić symulację ponownie. Większa głębokość '''d''' symulacji prowadzi do lepszych ruchów. Optymalizacja algorytmu z odcięciami [[Algorytm alfa-beta|alfa-beta]] pozwala, w optymalnym przypadku, zmniejszyć ilość rozpatrywanych stanów do ~<math>2b^{d/2}</math>, co w efekcie pozwala nam symulować ruchy prawie dwa razy głębiej.
 
Aby osiągnąć optymalne wyniki minimaxem, ważne jest posiadanie dobrej funkcji oceny stanu gry '''S'''. Optymalnej funkcji '''S''' zazwyczaj nie znamy, bo w takim wypadku gra była by już rozwiązana (znalibyśmy optymalną strategię jak np. w kółko i krzyżyk), dlatego stosuje się różne [[Heurystyka (informatyka)|heurystyki]], zazwyczaj wyrażone jako liniowy [[wielomian]] od parametrów stanu gry.