Czy silniki szachowe przechowują wszystkie wcześniej analizowane pozycje między ruchami

Zaczynam grać z silnikami szachowymi. Zauważyłem, że przeniesienie najlepszych silników szachowych może zająć kilka minut. Zastanawiam się dlaczego. Przed każdym ruchem silnik bada do pewnego stopnia wszystkie legalne przyszłe ruchy. Wydaje się jednak, że powtarza to ćwiczenie dla następnego ruchu. Biorąc pod uwagę, że poprzedni ruch został już uwzględniony w drzewie badanych ruchów, czy nie jest to nieskuteczne? A może źle zrozumiałem?

[Edytuj: Zakładam, że powodem, dla którego analizy przenoszenia nie są buforowane, są pewne ograniczenia pamięci komputera, które przyspieszają ponowne uruchomienie analizy]

Programowanie silników szachowych jest bardzo skomplikowanym terytorium, więc od razu skieruję cię do Wiki Programowania Szachowego , które zawiera wiele świetnych informacji na ten temat.

tło

Obliczenia szachowe (i wiele podobnych rzeczy) są na ogół modelowane i uważane za „drzewa gry” lub „ drzewa decyzji ”. Zasadniczo to drzewo jest ukierunkowanym wykresem, z jednym węzłem u góry (bieżąca pozycja), prowadzącym do węzła dla każdego możliwego ruchu, z których każdy prowadzi do większej liczby węzłów dla każdego możliwego następnego ruchu i tak dalej.

W swojej najbardziej uproszczonej, brutalnej sile, silniki szachowe generują wszystkie pozycje na tym drzewie do pewnego poziomu głębokości („warstwa”), oceniając każdą uzyskaną pozycję na podstawie złożonych kryteriów ¹ . Następnie odtwarza ruch, który wydaje się prowadzić do najlepszego wyniku. Obecnie opracowano wiele naprawdę skomplikowanych technik ograniczających liczbę pozycji, na które musi patrzeć silnik, ale zignoruję je dla celów tej odpowiedzi, ponieważ nie zmieniają prawdziwego problemu w dłoń.

Styczna matematyczna

Podstawowym powodem, dla którego silniki zazwyczaj zajmują tyle samo czasu na rozważenie każdego ruchu, jest to, że wielkość drzewa decyzyjnego rośnie wykładniczo wraz z głębokością ( k).

Rozważ pozycję początkową. Wierzchołek drzewa ( k=0) to jeden węzeł. Istnieje 20 możliwych pierwszych ruchów dla Białych, więc głębokość ma dwadzieścia węzłów k=1. Następnie Czarne mają również dwadzieścia dostępnych ruchów dla każdej z opcji Białych: więc przy k=2są 20 * 20 = 400możliwe pozycje! I tylko gorzej, gdy gracze rozwijają swoje pionki!

Na przykład, udawajmy, że dla każdego gracza w danym momencie istnieje zawsze dwadzieścia możliwych ruchów ² . Poinstruujesz komputer, aby spojrzał w przyszłość o pięć ruchów dla każdego gracza (dziesięć warstw). Spójrzmy na rozmiar drzewa brutalnej siły na każdym poziomie. Dla zabawy przyjrzymy się również całkowitej liczbie pozycji w drzewie (od góry do podanego poziomu).

Ply |    Positions   |  Total Tree Size
----------------------------------------
 0  | 1              | 1
 1  | 20             | 21
 2  | 400            | 421
 3  | 8000           | 8421
 4  | 160000         | 168421
 5  | 3200000        | 3368421
 6  | 64000000       | 67368421
 7  | 1280000000     | 1347368421
 8  | 25600000000    | 26947368421
 9  | 512000000000   | 538947368421
10  | 10240000000000 | 10778947368421

Skutkiem tego, że każdy poziom jest wykładniczo większy niż poziom poprzedni, wielkość całego drzewa jest zdominowana przez poziom dolny . Rozważ powyższy przykład: sam ostatni poziom zawiera dziesięć bilionów węzłów. Cała reszta drzewa zawiera tylko pięćset miliardów. Dziesiąta warstwa zawiera około 95% węzłów w całym drzewie (jest to prawdą na każdym poziomie). W praktyce oznacza to, że cały czas poszukiwań jest poświęcony na ocenę „ostatniego” ruchu.

Odpowiedź

Jak to się ma do twojego pytania? Powiedzmy, że komputer jest ustawiony na dziesięć warstw, jak wyżej, i dalej „zapamiętuje” wyniki swoich ocen. Oblicza ruch, odtwarza go, a następnie wykonujesz ruch. Teraz wykonano dwa ruchy, więc przycina wszystkie pozycje z pamięci związane z ruchami, które się nie wydarzyły, i zostaje z drzewem, które schodzi z pozostałych ośmiu ruchów, które już obliczyło: 26 947 368 421 pozycji!

W porządku! Musimy więc obliczyć tylko dwie ostatnie warstwy! Korzystając z naszego oszacowania 20 ruchów na każdej głębokości, łączna liczba ruchów, które musimy tutaj obliczyć, wciąż przekracza dziesięć bilionów. Pozycje, które obliczyliśmy, stanowią jedynie 2,5% możliwości! Nawet buforując wyniki ostatniego ruchu, możemy mieć nadzieję na 2,5% wzrost prędkości! Zasadniczo dlatego nawet jeśli twój program buforuje poprzednie wyniki, zwykle nie widzisz znacznego przyspieszenia między ruchami (z wyjątkiem przypadków, gdy komputer znajdzie przymusowego partnera lub coś takiego!).

Uproszczenie Zastrzeżenie

To pytanie wiąże się z dużą złożonością, dlatego połączyłem się z wiki programowania na samym szczycie i próbowałem wyjaśnić odpowiedź w szerokich kategoriach matematycznych. W rzeczywistości programy zrobić ogólnie części cache na drzewie z ruchu, aby przenieść, i istnieją inne powody, dla których to niewystarczające na własną rękę - kilka prostych powodów (np pewna linia może wyglądać dobrze na zewnątrz do ośmiu ruchów, ale kończy z tyłu -rankuj partnera w ruchu dziewiątym!) i wiele bardzo skomplikowanych (ogólnie związanych z różnymi sprytnymi metodami przycinania). Komputer musi więc patrzeć w przyszłość, próbując uniknąć złych założeń na podstawie głębokości odcięcia poprzedniego ruchu.

¹ Nie będę tutaj wchodził w funkcje heurystyczne, ponieważ jest to jego niezwykle złożony obszar, ale często istnieją pewne korzyści, które można osiągnąć również tutaj poprzez schematy buforowania pozycji.

² Średni współczynnik rozgałęzień wynoszący 20 jest prawdopodobnie o wiele za niski .

Typowy silnik szachowy przechowuje niektóre pozycje i ich brakujące wyniki alfa-beta w tabeli transpozycji, z którą można się zapoznać podczas kolejnych wyszukiwań. Ta tabela nie jest konsultowana bezpośrednio w celu wybrania następnego ruchu, ale sprawia, że ​​wyszukiwanie tego ruchu jest bardziej wydajne na dwa sposoby.

1. Pozycja będzie prawdopodobnie napotkana wiele razy w drzewie wyszukiwania, osiągniętym przez transpozycję lub permutację sekwencji ruchów. Ponieważ można zapoznać się z tabelą, taka pozycja może wymagać oceny tylko kilka razy (dla różnych stałych głębokości wyszukiwania) zamiast dziesiątek razy, gdy pozycja jest odwiedzana i ponownie odwiedzana.

2. Standardową techniką przeszukiwania alfa-beta jest stosowanie iteracyjnego pogłębiania , powtarzalne badanie drzewa na większej głębokości wyszukiwania, aż do osiągnięcia głębokości końcowej. Oceny wyceny obliczone we wcześniejszych iteracjach służą do porządkowania ruchów wyszukiwanych w późniejszych iteracjach. Wiadomo, że alfa-beta działa lepiej (tj. Przycina więcej drzewa wyszukiwania), jeśli dobre ruchy są wyszukiwane przed złymi ruchami.

Przykład dowodzący pamięć silnika:

Rozważ pozycje, w których odkrywane są głębokie nowinki teoretyczne, w szczególności grę Caruana kontra Topałow rozgrywaną w tym roku. Kiedy pozwalasz silnikowi analizować pozycję po ruchu 12 przez mniej więcej krótki czas (powiedzmy 10-15 minut), możesz sprawdzić sugerowane ruchy i zobaczyć, że 13.Re2!wśród nich nie pojawia się TN ( ). Przedstaw sam ruch, cofnij się i pozwól silnikowi ponownie przeanalizować tę samą pozycję przez mniej więcej ten sam czas. O dziwo, po namyśle, silnik uważa TN za jeden z najlepszych ruchów i akceptuje go.

EDYCJA: Oryginalna odpowiedź (podana poniżej) jest błędna, jednak stanowi użyteczny przykład pamięci silnika, który został zacytowany na górze.

O ile mi wiadomo, nie rozpoczynają wyszukiwania drzewa prawie od zera przy każdym ruchu.

Muszą jednak mieć jakąś funkcję, która aktualizuje wartości dla każdego ruchu, a ta funkcja z pewnością ma pamięć krótkotrwałą. Niektóre przykłady to pozycje, w których odkrywane są głębokie nowinki teoretyczne, w szczególności gra Caruana kontra Topałow, którą grał w tym roku. Kiedy pozwalasz silnikowi analizować pozycję po ruchu 12 przez mniej więcej krótki czas (powiedzmy 10-15 minut), możesz sprawdzić sugerowane ruchy i zobaczyć, że 13.Re2!wśród nich nie pojawia się TN ( ). Przedstaw sam ruch, cofnij się i pozwól silnikowi ponownie przeanalizować tę samą pozycję przez mniej więcej ten sam czas. O dziwo, po namyśle, silnik uważa TN za jeden z najlepszych ruchów i akceptuje go.

Nie jestem ekspertem od oprogramowania szachowego, ale tak się dzieje. Można to przynajmniej częściowo wyjaśnić, jeśli (jak powiedziano) funkcja, która ocenia ruchy dla pozycji, ma trochę pamięci.

Henry Keiter już udzielił ogólnej odpowiedzi, dam ci bardziej techniczną odpowiedź. Wszystko zależy od tabeli transpozycji, głębokości wyszukiwania i odcięcia. Dyskusja tutaj jest DUŻO bardziej techniczna niż inne odpowiedzi, ale będzie korzystna dla każdego, kto chce nauczyć się programowania szachowego.

Powszechnym nieporozumieniem jest to, że jeśli pozycja była oceniana wcześniej, wynik oceny może być ponownie wykorzystany, o ile jest wystarczająca ilość pamięci do przechowywania ruchów. Programowanie w szachy jest bardziej skomplikowane. Nawet biorąc pod uwagę nieskończoną pamięć, nadal będziesz musiał ponownie przeszukiwać pozycje. Do każdego ruchu dołączany jest wynik oceny wraz z jego głębokością i granicą. Na przykład, jeśli silnik przechowuje ruch w trybie fail-high, wpis w tabeli miałby dolną granicę. Oznacza to, że jeśli szukasz pozycji, nadal musisz sprawdzić granice, czy możesz użyć poprzedniego wyniku oceny.

Poza tym do każdej oceny przypisana jest głębia. W ramach pogłębiania iteracyjnego, gdy zwiększasz głębokość dla każdej iteracji, nadal będziesz musiał przeszukiwać pozycje, które szukałeś już w poprzedniej iteracji.

Krótka odpowiedź na twoje pytanie jest taka, że silnik przechowuje wszystkie poprzednie analizowane pozycje (tak długo, jak wystarczająca ilość pamięci), ale tych zapisanych wyników nie można ponownie wykorzystać tak łatwo, jak mogłoby się wydawać . W fazie otwarcia, w której jest mniej powtórzeń, te zapisane wyniki są najbardziej przydatne do porządkowania ruchów i kilkunastu heurystyk redukcji ruchów. Na przykład można założyć, że najlepszy ruch z ostatniej głębokości jest najlepszym ruchem na bieżącej głębokości, więc sortujemy listy ruchów i wyszukujemy najlepszy ruch przed innymi ruchami. Mamy nadzieję, że dostaniemy wczesną granicę niezawodności.

Nie mamy nieskończonej pamięci do przechowywania pozycji. Musielibyśmy zdefiniować algorytm mieszający. Algorytm mieszający Zobrista daje nam pseudolosowy rozkład, ale wcześniej czy później nadal musielibyśmy zastąpić niektóre istniejące wpisy.

Każdy silnik ma własny schemat zarządzania czasem. Niektóre silniki i interfejsy GUI pozwalają ustawić tempo, w którym silnik będzie grał. Silniki zawsze obliczają / oceniają / minimaksują na tyle, na ile mogą, biorąc pod uwagę ograniczenia narzucone przez podprogramy zarządzania czasem lub ustawienia użytkownika. Jeśli silnik myśli przez długi czas, jest to prawdopodobne, ponieważ kontrola czasu w grze jest wolna lub użytkownik ustawił ją na powolną.

Pozycje i oceny obliczone przez silnik są przechowywane w tabeli skrótów. Użytkownik może ustawić rozmiar dostępnego skrótu w ustawieniach większości silników UCI. Sam silnik zużywa pewną ilość pamięci RAM, a jeśli ustawisz zbyt duży rozmiar tablicy skrótów, komputer zacznie zapisywać skrót na dysku twardym w postaci wirtualnej pamięci RAM. Dostęp do pamięci na dysku twardym jest uzyskiwany wolniej niż pamięć RAM i zwykle można usłyszeć, jak dysk twardy się odsuwa. Wielu użytkowników ustawia rozmiar tabeli mieszającej, aby zmieściła się w dostępnej pamięci RAM.

Duża część tabeli skrótów staje się bezużyteczna po tym, jak silnik i jego przeciwnik wykonają ruchy, ponieważ inne rozważane pozycje nie są już istotne. Silnik ponownie wykorzysta oceny zapisane w haszu, ale niektóre oceny okazują się nieprawidłowe z powodu efektów horyzontalnych, gdy silnik zejdzie głębiej w dół tej samej linii, więc często musi zmienić kolejność ruchów kandydata.

Ponieważ ilość skrótów jest skończona, silnik musi także podejmować decyzje, które informacje usunąć z skrótu, gdy dodaje nowe informacje. Mechanizm nie wie z góry, jakie ruchy będą odtwarzane, dlatego może przypadkowo usunąć informacje, które byłyby przydatne, ponieważ dodaje nowe dane.

Generalnie silniki nie badają wszystkich legalnych ruchów do określonej głębokości. Eliminują niektóre gałęzie drzewa z rozważania na podstawie przycinania do przodu i do tyłu. Ponadto, jeśli pozycja węzła liścia ma wychwytywanie lub kontrole, które należy jeszcze wykonać, silnik będzie kontynuował tę linię, aż osiągnie pozycję cichą (spoczynkową). Rzeczywiste drzewo jest prawdopodobnie dość głębokie w niektórych miejscach, podczas gdy inne linie mogły zostać obcięte po niewielkiej liczbie ruchów.