Jak „myślą” silniki szachowe?

Chcę wiedzieć, jak zaprogramowane są silniki do wyszukiwania ruchów. Jestem pewien, że najpierw obliczają najbardziej wymuszające linie, takie jak przechwytywanie i czeki. Ale co z subtelnymi, głębokimi ruchami pozycyjnymi? Wydaje się, że bardzo szybko je odnajdują (ogólnie rzecz biorąc. Oczywiście, że czasami tęsknią za takimi ruchami). W jaki sposób są one zaprogramowane do szukania cichych ruchów / pomysłów pozycyjnych? Nie mogą po prostu brutalnej siły przy każdym ruchu, ponieważ zajęłoby to zbyt długo, dlatego powinien istnieć jakiś sprytny sposób, aby naprawdę szybko osiągnąć najlepsze ruchy. Interesuje mnie to, ponieważ myślę, że pomogłoby to graczom przemyśleć planszę również w prawdziwym świecie.

Zasadniczo silniki szachowe wykorzystują drzewo decyzyjne. Korzeń drzewa to bieżąca pozycja i ma węzeł podrzędny dla każdej pozycji, którą można wykonać, wykonując legalny ruch. Każdy z tych węzłów ma z kolei węzeł podrzędny dla pozycji, do których można dotrzeć, wykonując legalny ruch. Silnik wypycha drzewo na głębokość określoną przez jego możliwości i czas, w którym wolno mu „myśleć”. Pozycje, które można osiągnąć na więcej niż jeden sposób, są po prostu powiązane, tak że nie trzeba będzie ich rozpatrywać więcej niż jeden raz. Po utworzeniu drzewa komputer używa zestawu ważonych reguł do analizy końcowych pozycji w drzewie i zaczyna usuwać te, które są niepożądane lub których przeciwnik może uniemożliwić. Drzewo jest ścięte w ten sposób, dopóki nie zostanie tylko jeden ruch, a komputer wykona ten ruch.

http://www.chess.com/blog/zaifrun zawiera serie lub artykuły na temat tworzenia silnika szachowego, jeśli chcesz dokładniej przyjrzeć się ich działaniu.

Zadajesz dość złożone pytanie, ale dobrze jest wrócić do podstaw. Należy wziąć pod uwagę kilka koncepcji:

Ocena

Jeśli (prawdziwy) gracz zostanie pokazany pozycji i zapytany „kto wygrywa tę grę?”, Jak podejmują decyzję? Najprawdopodobniej sprawdzą kilka podstawowych rzeczy, takich jak: różnice materiałowe, stopień, w jakim elementy zostały opracowane lub są ustawione „dobrze”, podwojone / izolowane / połączone / przekazane pionki, (kontrolowane) otwarte pliki, jak wysoko tablice, na których znajdują się pionki.

Teraz, gdybyś musiał, możesz wymyślić systematyczny sposób obliczania wyniku w oparciu o powyższe. Możesz na przykład zdecydować, że pionek jest wart 1 punkt, a przekazany pionek jest wart 0,3 punktu więcej. Pojedyncze lub podwojone pionki mogą być warte nieco mniej itp. Jeśli zsumujesz wszystko, otrzymasz wartość szacunkową dla najbliższej pozycji pod ręką.

Nazywa się to oceną i zasadniczo wszystkie programy szachowe mają sposób oceniania pozycji (ignorując nowatorskie silniki szachowe AI, które zazwyczaj są bardzo słabe).

Ale co z subtelnymi, głębokimi ruchami pozycyjnymi?

Cóż, ledwo zarysowaliśmy powierzchnię oceny pozycji. Rzeczywista implementacja funkcji oceny może być uproszczona, aby umożliwić ocenę większej liczby pozycji na sekundę (choć w przybliżeniu) lub bardziej złożoną, co prowadzi do mniejszej liczby ocenianych pozycji, ale z większym stopniem pewności. Nie jest niczym niezwykłym, że funkcja oceny bierze pod uwagę setki, a nawet tysiące osobnych informacji.

Szukaj

Właśnie pominąłem coś z powyższego, o czym większość prawdziwych graczy natychmiast pomyśli - czy jest jakiś sposób, aby natychmiast wygrać grę dla którejkolwiek ze stron? Widoczne są jakieś wiązania lub „wiszące” elementy? Chociaż łatwo jest to trywializować, nie jest to nic trywialnego.

Co to znaczy, że gracz ma pełne zaufanie do kombinacji? Ostatecznie sprowadza się to do obliczenia wszystkich opcji. Prawdziwi gracze zazwyczaj tego nie robią (z wyjątkiem trywialnych lub bardzo przymusowych partnerów), przez większość czasu rozważymy tylko garść opcji i wykluczamy inne, które wydają się „niekonstruktywne” lub oczywiście prowadzą do przegranej . Często popełniamy błędy podczas tych obliczeń, np. Możemy zdać sobie sprawę, że zmiana zleceń ruchu powoduje odparowywanie zagrożeń itp. Chodzi o to, że aby być całkowicie pewnym kombinacji, należy obliczyć całą drogę do jej zakończenia, zakładając, że każde gracz wykona dla nich tylko najlepszy możliwy ruch (jest to określane jako „min / max”).

Teraz, biorąc pod uwagę, że szachy mają znacznie większą przestrzeń do wyszukiwania (do tego odnosi się „wszystkie możliwe ruchy w przyszłości”) niż to, co jest możliwe do obliczenia przez komputer, należy dokonać kompromisów. Podobnie jak ludzie, komputery mogą postanowić zignorować całe kierunki myślenia w oparciu o określone kryteria. Jest to znane jako heurystyka . Warto zauważyć, że chociaż możesz być naprawdę pewny kombinacji, jeśli zastosujesz ją brutalnie, złożona funkcja oceny może często wykryć obecność zagrożeń (np. Możemy policzyć widelce, możliwości szpikulca itp.), Aby poprowadzić wyszukiwanie w tym kierunku ).

Ostatecznie, choć komputery są bardzo szybkie, to heurystyka pozwala im na tak głębokie obliczenia. To powiedziawszy, możesz być zaskoczony, jak głęboko nowoczesne silniki obliczają w pełni, zwykle przekraczają 3 ruchy, nawet w szybkich grach.

Wniosek / połączenie wszystkiego

Podsumowując - funkcje ewaluacyjne mają wbudowaną dużą inteligencję (tj. Uwzględniają więcej rzeczy niż przeciętny człowiek), heurystyka pozwala komputerowi wyrównać linie myśli, które według niego prawdopodobnie nie zakończą się dobrze, a komputery są niezwykle, bardzo szybkie. Dodaj je i trudno je pokonać.

Zgadzam się z odpowiedziami.

Pamiętam GM Romana Dzindzichashvili, mówiąc o tym, w jednym z filmów Romana z laboratoriów , nie pamiętam, jaki to był film (jeśli ktoś zna szczegóły, edytuj moją odpowiedź).

Roman powiedział, że twórcą silnika Fritza jest jego przyjaciel. Tak więc Roman przetestował Fritza, aby zobaczyć, jak dobrze jest, a deweloper powiedział Romanowi, że aby Fritz mógł podejmować złożone decyzje (poświęcając materiały w zamian za przewagę pozycyjną), musieli zmienić wartość elementów, na przykład powiedzieć programowi że zły biskup jest wart 1 punkt, biskup na otwartej przekątnej jest wart 7 punktów, rycerze są wart 5 punktów na bliskich pozycjach ...

Nie znam dokładnych liczb dla każdego kawałka, ale tak to działa, a teraz twój silnik nie będzie miał problemu z poświęceniem złego biskupa, czy cokolwiek, jeśli możesz mu powiedzieć wartość każdego kawałka w każdej pozycji.

EDYTOWAĆ

Zobacz także Wiki programowania szachowego .

Po prostu niemożliwe jest, aby komputery wyglądały wystarczająco głęboko (25 warstw i więcej) i sprawdzały każdy możliwy ruch.

Możliwa jest technika zwana przycinaniem alfa-beta, co oznacza, że ​​komputery, podobne do ludzi (ale o wiele lepsze), podążają tylko za obiecującymi kontynuacjami.

Stale oceniają pozycje (w oparciu o niektóre wstępnie zakodowane zasady, wyceniając materiał, bezpieczeństwo króla, aktywność, struktury pionków itp.) I szukają odmian, które wydają się prowadzić do najlepszej pozycji.

Wciąż jest blisko magii, jak potrafią to zrobić wystarczająco skutecznie, aby ocenić miliony tych pozycji w ciągu sekundy.

Podsumowując - masz rację, nie mogą patrzeć na wszystkie ruchy, jeśli grają w szachy strategiczne, ale mogą bardzo szybko patrzeć na przyzwoite ruchy. Problem jest nadal związany z bardzo długoterminowymi planami i horyzontem, do którego mogą się dostrzec, ale nad tym trwają prace (Rybka analizuje znacznie wolniej, ale gra w dużo więcej szachów pozycyjnych, podczas gdy Houdini jest romantyczny, że jego „mechaniczne serce” oblicza więcej ruchów i grać bardziej agresywnie). Nawet komputery mają swoje własne style!

Przycinanie alfa-beta oznacza po prostu, że jeśli znajdziesz linię, która okazuje się dla ciebie źle, przestajesz patrzeć na ruch kandydata, a zamiast tego próbujesz innych. Jest to rodzaj przycinania wstecznego, co oznacza, że ​​nigdy nie przegapisz dobrego ruchu. Natomiast przycinanie do przodu opiera się bardziej na zgadywaniu. Przycinanie daremności, redukcje późnych ruchów i brzytwy są rodzajami przycinania do przodu i wszystkie polegają na odczuciu programisty co do rodzaju ruchów, które należy wziąć pod uwagę. Program, który wykonuje wiele przycinania do przodu, może przegapić zaskakujące ofiary, które prowadzą do partnera, ale z drugiej strony eliminuje wiele naprawdę złych ruchów, więc może głębiej spojrzeć na ruchy, które sprzyja.

Większość silników przeszukuje kilka pierwszych ruchów na pełnej głębokości, badając wszystkie możliwości. Jeśli żaden ruch nie powiedzie się wysoko (tzn. Wydaje się wyraźnie gorszy niż ruch, który już rozważałeś), rozszerzasz wyszukiwanie jeszcze bardziej. Zasadniczo kontynuujesz eksplorację każdej linii, dopóki nie osiągniesz spokojnej pozycji (bez czeków, przechwytywania, zagrożeń wiązanych itp.), A następnie dokonujesz oceny. Ciche ruchy mogą nie być brane pod uwagę, gdy znajdują się głęboko w drzewie wyszukiwania, ale gdy dojdziesz do tej faktycznej pozycji w grze, silnik patrzy na wszystkie ruchy, zarówno ciche, jak i ostre. Rzeczywiście widać to czasami na wyjściu silnika, gdy silnik nagle preferuje ruch, którego nie rozważał kilka ruchów wstecz.

Silniki obliczają tak szybko, że nie jest tak ważne, aby zastanowić się, który ruch najpierw przyjrzeć, ale dla ludzi jest to kluczowe pytanie. Jonathan Tisdall stara się odpowiedzieć na to pytanie w swojej książce „Popraw swoje szachy”. Kiedy atakujesz, sugeruje, abyś najpierw spojrzał na najbardziej gwałtowne ruchy. Kiedy się bronisz, najpierw spoglądasz na najtrudniejsze linie. Przytacza także zasady pozycyjne (np. Centralizacja, koordynacja) przy podejmowaniu decyzji, które ruchy spojrzeć na początku.

Inne książki, które mogą być istotne, to Niewidzialne ruchy szachowe Emmanuela Neimanna i Zmuszające ruchy szachowe Charlesa Hertana, z których oba opowiadają się za znaczeniem rozważania nieoczekiwanych lub zaskakujących ruchów na ostrych pozycjach. Hertan mówi nawet o opracowaniu „komputerowych oczu” dla takich taktyk.