Rozumiem, że silniki można teraz podzielić na cztery grupy: te, które używają Alpha-beta (AB) + te, które używają Monte Carlo Tree Search (MCTS) do wyszukiwania, i te, które używają funkcji odręcznych + te, które używają sieci neuronowych do eval. Dwa najsilniejsze silniki to Leela i Sztokfisz. Leela używa MCTS + NN, podczas gdy Sztokfisz używa AB + odręcznie.
Dlaczego te dwie kombinacje? Dlaczego nie NN + AB lub MCTS + odręcznie? Jeśli MCTS jest lepszy od AB, dlaczego Komodo MCTS nie jest silniejszy od Komodo AB? Jeśli AB jest lepszy niż MCTS, dlaczego Leela nie używa AB zamiast tego?
Odpowiedzi:
Prędkość
Sieci neuronowe działają znacznie wolniej niż ręcznie wykonane funkcje oceny. W TCF Superfinal Leela Chess Zero, działająca na dwóch procesorach graficznych, z których każdy ma dedykowane rdzenie tensorowe, jest w stanie przeszukać około 60 tysięcy pozycji na sekundę. Natomiast Sztokfisz na jednym rdzeniu na moim komputerze wyszukuje ponad 2 miliony pozycji na sekundę.
Podczas gdy współczesne silniki mają ogromny wybór technik odcinania niepotrzebnych gałęzi , wyszukiwanie drzewa alfa-beta jest nadal bardzo brutalną techniką, wymagającą przeszukiwania ogromnej liczby pozycji w celu ustalenia dobrych ruchów.
Natomiast MCTS jest znacznie bardziej selektywny i rozszerza swoje drzewo wyszukiwania tylko w kierunku najbardziej obiecujących ruchów, co pozwala mu maksymalnie wykorzystać ograniczoną liczbę węzłów, które można przeszukiwać.
Zachowanie w najgorszym przypadku
Jednym z kluczowych wymagań funkcji oceny dla silnika opartego na wyszukiwaniu alfa-beta jest to, że musi on zachowywać się w najgorszym przypadku . Wynika to z faktu, że każdy duży błąd w ocenie, jakkolwiek rzadki, może być łatwo przeniesiony do katalogu głównego i prowadzić do straszliwie niepoprawnego ruchu.
Ze względu na swoją złożoność sieci neuronowe są podatne na nadmierne dopasowanie i mogą być tak dobre, jak dane użyte do ich szkolenia. Na przykład w meczu 80 Superfinału sezonu 14 TCEC w ruchu 47 Lc0 najwyraźniej nie był zaskoczony dodatkową królową Sztokfisza, oceniając pozycję jako fajną +0,77, podczas gdy Sztokfisz (i większość innych silników) ocenił na +8,31. Popularnym wyjaśnieniem tego jest to, że Lc0 mógł nie mieć znacznej liczby gier z wieloma królowymi na planszy w swoim zestawie treningowym.
Dlatego sieci neuronowe mają złe zachowanie w najgorszym przypadku, a zatem mogą słabo działać z wyszukiwaniem alfa-beta. Natomiast MCTS pozwala zrównoważyć nieprawidłowy wynik przypisany do jednej pozycji poprzez uśrednienie go z rozsądnymi wynikami przypisanymi do pozycji w pobliżu wyszukiwania.
Bezruch
Wszystkie silne silniki alfa-beta wykorzystują technikę zwaną wyszukiwaniem spoczynkowym , ograniczoną formą wyszukiwania alfa-beta stosowaną w węzłach liści, w uznaniu, że ich ręcznie wykonane funkcje oceny działają dobrze tylko w „cichych” pozycjach, gdzie nie ma żadnych przechwyconych ani sprawdzeń .
Na przykład, bezpośrednio po pierwszej połowie wymiany królowej, ręcznie wykonana funkcja oceny może powiedzieć ci, że strona, która właśnie zabrała ich królową, została całkowicie utracona, podczas gdy sieć neuronowa może zrozumieć, że królowa zostanie wkrótce odzyskana.
To sprawia, że ręcznie wykonane funkcje oceny są podobnie nieodpowiednie dla MCTS ze względu na brak przeszukiwania spoczynkowego, co powoduje, że ręcznie wykonywane funkcje działają słabo przez większość czasu (chociaż Komodo 12 MCTS i tak omija to ograniczenie, używając krótkich wyszukiwań alfa-beta , aby uzyskać pozycje spoczynkowe i dlatego pozwól, aby ręcznie wykonana ocena zwróciła rozsądny wynik)
źródło
AB i MCTS niekoniecznie są lepsze od siebie samych. Po prostu są to różne algorytmy wyszukiwania, które działają lepiej z różnymi fundamentami. W przypadku NN MCTS działa dobrze, ponieważ pozwala silnikowi badać gałęzie, które mają się lepiej. Daje to silnikowi większą swobodę patrzenia na to, co „chce”.
Tymczasem w AB należy zasadniczo przyjrzeć się wszystkim gałęziom. Dzieje się tak, ponieważ nawet przy iteracyjnym pogłębianiu silnik tylko do tej pory patrzy na każdą gałąź w każdej iteracji. Nie wie więc, czy jedna gałąź faktycznie wygrywa dla jednej strony, nawet jeśli wydaje się przegrywać na ograniczonej głębokości.
źródło