Przycinanie do przodu

Przycinanie alfa-beta przycina gałęzie drzewa, które nie mogą mieć wpływu na ostateczną ocenę, ale przycinanie do przodu przycina ruchy, które wydają się słabymi ruchami, ale mogą być dobrymi. W ten sposób strategia oszczędza czas obliczeń, ryzykując błąd. W terminologii Shannona jest to strategia typu B. Oczywiście większość szachistów robi to, biorąc pod uwagę tylko kilka ruchów z każdej pozycji (przynajmniej świadomie) wszystkie możliwe ruchy. Niestety takie podejście jest dość niebezpieczne, ponieważ nie gwarantujemy, że najlepszy ruch nie zostanie przycięty. PROBCUT lub algorytm cięcia probabilistycznego (Buro, 1995) to przycinająca do przodu wersja wyszukiwania alfa-beta, która wykorzystuje statystyki uzyskane z wcześniejszych doświadczeń, aby zmniejszyć prawdopodobieństwo, że najlepszy ruch zostanie przycięty. Wyszukiwanie alfa-beta usuwa każdy węzeł, który prawdopodobnie znajduje się poza (α β) bieżącym oknem. PROBCUT przycina również węzły, które prawdopodobnie znajdują się poza oknem. Oblicza to prawdopodobieństwo, wykonując płytkie wyszukiwanie w celu obliczenia wartości węzła z kopii zapasowej, a następnie wykorzystując wcześniejsze doświadczenia do oszacowania prawdopodobieństwa, że ​​wynik na głębokości w drzewie będzie poza (α, β) . Buro zastosował tę technikę w swoim programie Othello, LOGISTELLO, i odkrył, że wersja jego programu z PROBCUT pokonuje wersję regularną w 64% przypadków, nawet jeśli zwykła wersja miała dwa razy więcej czasu. Inna technika, późna redukcja ruchów, działa przy założeniu, że porządkowanie ruchów zostało wykonane dobrze, a zatem ruchy, które pojawiają się później na liście możliwych ruchów, są mniej prawdopodobne, że będą dobrymi ruchami. Ale zamiast całkowicie je przycinać, po prostu zmniejszamy głębokość, do której przeszukujemy te ruchy, oszczędzając w ten sposób czas. Jeśli zredukowane wyszukiwanie wróci z wartością wyższą od aktualnej wartości α, możemy ponownie przeprowadzić wyszukiwanie z pełną głębokością. Połączenie wszystkich opisanych tutaj technik daje w wyniku program, który może grać w wiarygodne szachy (lub inne gry). Załóżmy, że zaimplementowaliśmy funkcję oceny dla szachów, rozsądny test odcięcia z wyszukiwaniem stanu spoczynku. Załóżmy również, że po miesiącach żmudnego bitowania, na najnowszym komputerze PC możemy wygenerować i ocenić około miliona węzłów na sekundę. Współczynnik rozgałęzienia dla szachów wynosi średnio około 35, a 355 to około 50 milionów, więc gdybyśmy użyli wyszukiwania minimaksowego, moglibyśmy patrzeć w przyszłość tylko na pięć warstw w około minutę obliczeń; zasady konkurencji nie dałyby nam wystarczająco dużo czasu na przeszukanie sześciu warstw. Choć nie jest niekompetentny, taki program może zostać pokonany przez przeciętnego szachistę, który od czasu do czasu może zaplanować sześć lub osiem partii do przodu. Dzięki wyszukiwaniu alfa-beta i dużej tabeli transpozycji dochodzimy do około 14 warstw, co daje ekspercki poziom gry. Moglibyśmy zamienić nasz komputer na stację roboczą z 8 procesorami graficznymi, uzyskując ponad miliard węzłów na sekundę, ale aby uzyskać status arcymistrza, nadal potrzebowalibyśmy rozbudowanej funkcji oceny i dużej bazy danych ruchów końcowych. Najlepsze programy szachowe, takie jak STOCKFISH, mają to wszystko, często osiągając głębokość 30 lub więcej w drzewie wyszukiwania i znacznie przekraczając możliwości każdego gracza.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *