Losowość w grze silnika

Jeśli otrzymam dwa silniki, które będą grały przeciwko sobie z tymi samymi kolorami, czy ta sama gra będzie za każdym razem? Jeśli nie, skąd bierze się losowość gry silnika? (Zaniedbanie książki otwierającej, gdzie, jeśli się nie mylę, książka może powiedzieć silnikowi, aby wybierał losowo dwa ruchy, ponieważ są one równie dobre.)

Zakładam, że istnieje losowość, ponieważ w meczu Alphazero vs. Sztokfisz nie zdarzało się wiele razy z rzędu ta sama gra. Jednak nie rozumiem dlaczego. Prawdopodobnie jedynym sposobem na to jest skłonienie silnika do wykonania słabszego ruchu, co brzmi jak seppuku.

Jeśli chodzi o mecz AlphaZero vs Sztokfisz, to pytanie zostało już omówione tutaj przez SmallChess .

Odkładając na bok AlphaZero (który wykorzystuje specjalną rutynę Monte Carlo ¹ do badania linii gry), która jest konstrukcyjnie niedeterministyczna dla zwykłych silników szachowych opartych na heurystyce, takich jak Sztokfisz i inne (choć istnieją inne silniki, które mają procedury oparte na MC, AFAIK Rybka miała taką funkcję), źródło losowości jest zazwyczaj jedynie konsekwencją technicznych aspektów wdrożenia, a nie celowej losowości wprowadzanej algorytmicznie w procesie decyzyjnym silnika. Mówiąc abstrakcyjnie, jednym z powodów tego jest fakt, że silniki nie działają w sposób czysto sekwencyjny (wykonywanie jednego zadania po drugim). Zamiast tego, aby uczynić silniki bardziej wydajnymi, przeprowadzają równoległe wyszukiwanie w różnych gałęziach drzewa możliwych ruchów. Robią to poprzez tak zwane wielowątkowość (lub -processing, ale to trochę inaczej). Wiele wątków procesorów jest jednocześniewykonywanie operacji w celu przeszukania drzewa (i buforowania ocen odwiedzanych pozycji), więc wyobraź sobie, że do każdego wątku przypisano poddrzewo. Problem z tego rodzaju implementacją polega na tym, że ogólne wykonanie wątków staje się wysoce zależne od różnego rodzaju warunków (czasów oczekiwania, zamiany pamięci RAM, ...), więc ostatecznie można wybrać główną odmianę bez zezwolenia na wszystkie inne wątki, aby zakończyć wyszukiwanie.

Dzieje się tak często, ponieważ silnik jest ustawiony na podjęcie decyzji w określonym czasie, więc zarządzanie czasem zmienia zachowanie. Możesz także cofnąć to stwierdzenie, mówiąc: znajomość algorytmu i implementacja deterministycznych procedur wątkowania nie są wystarczające, aby wiarygodnie przewidzieć stan programu po dowolnym czasie t. Oczywiście, jeśli zawsze zezwala się wszystkim wątkom na zakończenie wyszukiwania, a podczas tego wykonywania nie wystąpiły problemy z współbieżnością (na przykład wątek próbujący uzyskać dostęp do określonej pamięci podręcznej, która nie jest dostępna), wówczas zachowanie będzie w pełni odtwarzalne biorąc pod uwagę, że wszystko inne jest takie samo ² .

^{1 : Wraz z faktem, że poprzez dodatkowe szkolenie (na przykład samodzielną grę) jego sieć neuronowa ewoluuje (ponownie dostosowuje parametry), lub jeśli chcesz, jej funkcja oceny nie ma stałej, stałej definicji (w przeciwieństwie do silników opartych na heurystyce ).}

^{2 : Nawet wtedy, jak powiedziałeś, na poziomie początkowym, z książką otwierającą, silnik czasami podejmuje celowe losowe decyzje, które warianty wybrać. Podobnie, poza fazą otwarcia, mogą zdarzyć się chwile, w których wiele odmian ma prawie równe oceny (w ramach rozdzielczości wybranej dla Eval), a następnie w oparciu o projekt, może skończyć się wyborem jednej losowo. Na koniec, na poziomie ustawień silnika należy również zachować ostrożność, na przykład głębokość wyszukiwania i czasy rozważań wybrane dla każdego silnika (i to, czy mogą one dalej obliczyć podczas swoich czasów zastanowienia).}

Dzięki @Phonon szczegółowo opisując moje poprzednie odpowiedzi. Chciałbym dodać jeszcze jeden punkt: kontrolę czasu .

Jedyną deterministyczną kontrolą czasu jest liczba węzłów , ale jest to rzadkie. O wiele bardziej powszechna kontrola czasu - ustalona liczba sekund lub czas gry zasadniczo nie są deterministyczne.

Spróbujmy przykładu. Uruchom sztokfisza na swoim terminalu. Rodzaj:

przejdź do Movetime 20000

To polecenie nakazuje silnikowi wykonać ruch po 20 sekundach. Moje wyniki:

info depth 23 seldepth 32 multipv 1 score cp 6 upperbound nodes 24325860 nps 1216171 hashfull 999 tbhits 0 time 20002 pv g1f3 d7d5
bestmove g1f3 ponder d7d5

Ruch był 1.Nf3. Następnie zabiłem mojego Sztokfiszka, zacząłem nowy. Znowu 20 sekund. Mam:

info depth 23 seldepth 32 multipv 1 score cp 20 nodes 26185280 nps 1309067 hashfull 999 tbhits 0 time 20003 pv d2d4
bestmove d2d4 ponder g8f6

To 1.d4! Ta sama pozycja, wyszukiwanie 20 sekund!

Czy ty widzisz? Po 20 sekundach na ruch, ale z powodu fluktuacji w systemie operacyjnym Linux moja druga seria miała głębsze wyszukiwanie (26185280> 24325860).

Pamiętaj, że ten mały eksperyment nie był nawet wielowątkowy (liczba wątków = 1). Wielowątkowość uczyniłaby jeszcze bardziej niedeterministyczną.

Sztokfisz otrzymał jedną minutę na ruch w meczu Google AlphaZero. Liczba wątków wyniosła 64. Decyzje Sztokfisza w meczu nie mogły być deterministyczne.