Czy istnieje silnik szachowy, który NIE korzysta z funkcji wyszukiwania z użyciem siły?

Każdy silnik szachowy, o jakim słyszałem (w tym wszystko, co znalazłem na liście w Wikipedii) korzysta z wyszukiwania siłowego z funkcją oceny (algorytm minmax), aby zdecydować o jego ruchu.

Nie jest to sposób, w jaki większość ludzi podchodzi do gry, stosując zamiast tego ogólne rozpoznawanie wzorców, więc w zasadzie komputer mógłby zrobić to samo.

Czy jest jakiś silnik szachowy, który nie opiera się na brutalnej sile, aby znaleźć swoje ruchy?

W latach 80. podjęto próby napisania silników szachowych z bazami wiedzy, które wybierałyby ruchy kandydatów jak ludzie, ale zakończyły się one niepowodzeniem. Problem polega na tym, że dopasowanie ludzkich wzorców jest trudne do sformułowania, dlatego stworzenie reguł dla bazy wiedzy było niezwykle trudne.

Szkolenie sieci neuronowej do wybierania ruchów kandydatów wydaje się obiecującą linią badań. Tu i tutaj mogą być dwa stosowne artykuły. (FWIW, To nie jest moja dziedzina Comp Sci)

Możesz rzucić okiem na Giraffe, która była ostatnio w wiadomościach:

https://thestack.com/iot/2015/09/14/neural-network-chess-computer-abandons-brute-force-for-selective-human-approach/

Hype jest taki, że w ciągu 3 dni nauczył się gry i osiągnął poziom IM. Z drugiej strony badania są na

http://arxiv.org/abs/1509.01549

Chciałbym dodać szczegóły do ​​odpowiedzi @ Ian_Bush na Giraffe.

W odpowiedzi @ Ian_Bush zauważono, że Giraffe nie używa obliczeń siły brutalnej. To nie w porządku , ponieważ Giraffe jest nadal silnikiem alfa-beta (nega-max). Tylko różnica w stosunku do standardowego silnika jest to, że funkcja oceny jest dostrojony automatycznie przez głębokiego uczenia się. Dlatego silnik sam uczy się grać.

Tradycyjnie programista silnika dostraja parametry w silniku. Sam dużo zrobiłem. Na przykład, jaką wagę powinieneś dać biskupowi i rycerzowi? 3,0? 3.1? 3,2? Trudno powiedzieć.

Żyrafa podchodzi do problemu w znacznie mądrzejszy sposób. Zaczyna się od kilku wartości początkowych. Silnik używa algorytmu gradientu wynurzania, aby dostroić te wartości. Nie musimy jawnie kodować, jaką wagę powinna mieć królowa w kodzie. To właśnie mamy na myśli „uczenie się”. Nie oznacza to, że silnik może grać w szachy bez wyszukiwania.

EDYCJA : Żyrafa modeluje węzły drzew jako prawdopodobieństwo, że wpadną one w główną wariację. Sprawdź szczegóły w papierze. Osobiście nie wierzę w to podejście, a artykuł pokazuje niewiele dowodów na to, jak użyteczne byłoby to.

To rodzaj dyskusji, jeśli można nazwać wyszukiwanie heurystyczne i ocenić podejście jako brutalną siłę. Większość współczesnych silników szachowych stosuje podejście oparte na regułach w celu oceny pozycji oraz funkcję wyszukiwania opartą na regułach w celu przycinania ruchów.

W rzeczywistości nie jest gwarantowane wybranie „globalnego optymalnego” ruchu, jednak te ruchy są wystarczająco dobre do celu. W tym sensie większość silników szachowych korzysta z przybliżenia globalnego optimum i faktycznie sobie radzi.

Do tej pory nie wiele silników szachowych odniosło sukces na najwyższym poziomie, stosując inne podejście, przynajmniej nie na taniego sprzętu.

Claude Shannon zaproponował dwa typy algorytmów do tworzenia silników szachowych. Silnik „typu A” bada wszystkie możliwe ruchy do pewnej skończonej głębokości, minimalizuje drzewo, a następnie odtwarza ruch z najwyższą oceną z drzewa zmaksymalizowanego (czyli brutalnej siły). Silniki typu B ograniczają wyszukiwanie do tylko części możliwych ruchów w oparciu o niektóre kryteria. Wierzyłem, że faworyzuje typ B jako bardziej obiecujący.

Silniki, które zostały stworzone w latach 70. (np. Hitech, Kaissa), były zwykle brutalną siłą bez przycinania lub tylko alfa-beta, ale ludzie wkrótce zauważyli wartość przycinania drzewa ruchów i linii, które raczej nie okazałyby się silne . Prawie wszystkie najnowsze silniki przycinają drzewo linii, które są wyraźnie słabsze (alfa-beta), a większość silników wykorzystuje również różne rodzaje przycinania do przodu (bezskuteczność, redukcja późnego ruchu, ruch zerowy, brzytwa). W tym sensie nie ma wielu silników, które używają czystej brutalnej siły.

W latach 70. Botvinnik pracował nad silnikiem o nazwie Pioneer stworzonym wokół koncepcji ścieżek ataku, które podlegałyby ocenie. Nigdy nie osiągnął punktu, w którym mógłby zagrać w pełną grę w szachy.

W latach 90. Chris Wittington opowiedział się za wykorzystaniem wiedzy o szachach i stworzył program o nazwie Chess System Tal, który był dość silny jak na swój czas.

Kasparow, Anand i Tord Romstad zauważyli, że Hiarcs wydaje się mieć bardziej szczegółową ocenę niż wiele najlepszych silników, których siła wynika z szybkiego wyszukiwania.

Zasadniczo wszystkie z nich!

Silniki szachowe naprawdę używają brutalnej siły tylko wtedy, gdy:

• powiedział do
• analizują pozycje (rozwiązywanie problemów)
• Poszukiwanie mat (rozwiązywanie problemów, nie podczas gry przeciwko, np. Problemy typu „znajdź partnera w stylu N”)

W przeciwnym razie będą mieli „wyszukiwanie selektywne”, to weźmie pod uwagę wszystkie możliwe ruchy dla danego układu planszy, ale eksploruje tylko kilka z nich. Silnik może jednak przejść na brutalną siłę, jeśli ocenia dwa ruchy bardzo podobnie (więcej niż jeden silny ruch) lub jeśli nie może znaleźć ruchu, który mu się podoba (brak silnych ruchów).

Mają też tendencję do brutalnej siły jako ostatniej linii obrony, jeśli widzisz szanse na mat, to widzi, że nadchodzi i będzie chciał bardzo się starać wyciągnąć i nie może znaleźć wyjścia („efekt Horyzontu”). „to problem z silnikami, przypuśćmy, że straci królową i został ograniczony do 4 głębokości; jeśli może wymienić pionki i odłożyć tę stratę królowej na 4 ruchy, pomyśli, że uratował królową , podczas tego procesu straci co najmniej 1 pionka (ponieważ następny ruch przybliża horyzont z wcześniejszego horyzontu), a ciężar, jaki kładzie na ratowaniu królowej, może oznaczać, że poświęci on pewną obronę, na nic, jeśli śmierć przejdzie ponad horyzont) .

Będzie to również brutalne, gdy wyszukiwanie selektywne nie będzie zbyt przydatne. Właśnie dlatego silniki pracują dłużej, kiedy mają jeszcze 3 sztuki. Muszą użyć siły, ponieważ algorytm selekcji nie może ocenić ruchu. Algorytm selekcji jest świetny podczas gry środkowej, ponieważ może wyglądać tak: „Och, robienie tego z pionkiem blokuje jego [cokolwiek] i wspiera moje [cokolwiek] i [cokolwiek], którego mam mniejszą liczbę broniących niż atakujących” - na przykład .

Jeśli masz króla na środku planszy, jest 8 ruchów, wybiórcze wyszukiwanie będzie wyglądało tak: „Żaden z nich nie robi nic przydatnego, nie mogę powiedzieć”.

Możesz myśleć o selekcji selektywnej jako o dwóch częściach, jest taktyczna w tym sensie, że spróbuje dostrzec ruchy taktyczne, zignoruje wagę zaangażowanych elementów, ponieważ królowa nie będąca częścią żadnej strategii nie jest warta więcej niż niezbędny do tego pionek. Ma również strategiczne znaczenie, ponieważ bada ruchy, które wzmacniają obronę i otwierają się później na potencjalne ataki.

Silnik robi to samo z twojego punktu widzenia i tam iz powrotem i tam iz powrotem.

Coś zwane tabelą transpozycji to duża lista rzeczy, o których myślała, w ten sposób, jeśli skończy się na czymś, co już zrobiło, wie i nie musi go ponownie oceniać.

O ile (wybiórcze :)) trafia tam inną drogą lub chce dalej badać. Załóżmy na przykład, że odkrywa, że ​​twoja wieża jest niezbędna do zbliżającego się ataku, silnik może ponownie ocenić linię, gdy to odkryje. Poprzednia waga, jaką nałożył na tę wieżę (np. 5 punktów, jak ważne jest dla ciebie) może być niedoszacowana.

Selektywne wyszukiwanie może również cofać się, jak powiedziano, że rozważa biskupa, który ruszy prosto na terytorium wroga, do selektora ruchu nie jest ważne, aby można go było łatwo zabrać. Powiedz, że odkrywa to strategicznie, że jest to wspaniały ruch! Może wtedy cofnąć się, by spróbować znaleźć sposób na ochronę tego kwadratu, aby tam dostać gońca. Załóżmy, że wymaga to pionka.

Metoda brutalnej siły rozważałaby linię obejmującą ten ruch pionka, a także (siłą brutalną) biskupa również się porusza, a te same rzeczy, które oceniają pozycję planszy (samo wyszukiwanie selektywne) powiedzą „to jest dobre”, więc zarząd stawki te bardzo się różnią, oba znajdują.

Bardzo trudno jest ocenić pozycję przy użyciu metody brutalnej siły, dlatego wyszukiwanie selektywne działa tak dobrze.

Brutalna siła z pozycji początkowej może znaleźć tego słynnego oficera w 4, który obejmuje królową f7 przykrytą przez biskupa, i jeśli miałaby to wysoko ocenić (ZNALEZIŁEM SZACUNKA! ZADANIA! ZAGRAJ!) To pomyliłby się, ponieważ czerń oczywiście się skontruje. Selektywne wyszukiwanie ocenia pozycję (do dalszej oceny), ponieważ wydaje się być dobra. Oznacza to, że rozważając twoją odpowiedź, może zdecydować, co będzie dla ciebie dobre ...

Tak więc rzeczy, których używa selektywne wyszukiwanie do oceniania rzeczy, są używane przez brutalną siłę, ponieważ „znalazłem mat z udziałem tego ruchu” nie wystarczy, aby powiedzieć, że ruch jest dobry.

Zatem jakie są pierwsze ruchy wybrane (białe) przez silniki szachowe z brutalną siłą?