Jaki jest stan techniki w komputerowym wyszukiwaniu drzewa szachowego?

MTD (f) lub jeden z wariantów MTD jest dużym ulepszeniem w stosunku do Standardowej alfa-beta , pod warunkiem, że nie masz naprawdę drobnych szczegółów w swojej funkcji oceny i zakładając, że używasz zabójczej heurystyki . Przydatna jest również heurystyka historii .

Najwyżej oceniany program szachowy Rybka najwyraźniej porzucił MDT(f) na rzecz PVS z zerowym oknem aspiracji na węzłach innych niż PV.

Extended daremne przycinanie, które obejmuje zarówno zwykłe daremne przycinanie, jak i głębokie maszynki do golenia, jest teoretycznie niewłaściwe, ale niezwykle skuteczne w praktyce.

Iteracyjne pogłębienie jest kolejną użyteczną techniką. I wymieniłem tutaj wiele dobrych linków do programowania szachów.

Chociaż wiele optymalizacji opartych na heurystyce (mam na myśli sposoby zwiększenia głębokości drzewa bez faktycznego przeszukiwania) omawianych w literaturze programowania szachowego, myślę, że większość z nich jest rzadko używana. Powodem jest to, że są to dobre wzmacniacze wydajności w teorii, ale nie w praktyce.

Czasami te heurystyki mogą zwrócić zły (znaczy nie najlepszy) ruch też.

Ludzie, z którymi rozmawiałem, zawsze zalecają optymalizację wyszukiwania alfa-beta i wdrożenie iteracyjne zagłębiając się w kod zamiast próbować dodać inne heurystyki.

Głównym powodem jest to, że komputery zwiększają moc obliczeniową, a badania [jak sądzę potrzeba cytowania] wykazały, że programy, które wykorzystują swój pełny czas procesora, aby zmusić drzewo Alfa-beta do maksymalnej głębokości, zawsze wyprzedzały programy, które dzieliły swój czas między pewne poziomy alfa-beta, a następnie niektóre heurystyki.

Mimo zastosowania heurystyki do wydłużenia głębokości drzewa może spowodować więcej szkody niż pożytku, ther jest wiele boostery wydajności można dodać do algorytmu wyszukiwania alfa-beta.

Jestem pewien, że jesteś świadomy, że aby alfa-beta działała dokładnie tak, jak ma działać, powinieneś mieć mechanizm sortowania ruchu (iteratywne pogłębienie). Iteracyjne pogłębienie może dać około 10% zwiększenia wydajności.

Dodanie głównej odmiany techniki searc h do alpha beta może dać dodatkowe 10% doładowania.

Spróbuj MTD(f ) również algorytm. Może również zwiększyć wydajność silnika.

Jeden heurystyczny, który nie został wymieniony, to Null move .

Ed Schröder ma również świetną stronę wyjaśniającą kilka sztuczek, których użył w swoim silniku Rebel, i jak wiele ulepszeń przyczyniło się do szybkości/wydajności: Inside Rebel

Użycie tabeli transpozycyjnej z zobrist hash

Potrzeba bardzo mało kodu do zaimplementowania [jeden XOR przy każdym ruchu lub unmove, i instrukcja if przed rekurencją w drzewie gry], a korzyści są całkiem dobre, zwłaszcza jeśli używasz już iteracyjnego pogłębienia i jest to dość poprawialne (użyj większej tabeli, mniejszej tabeli, strategii zastępczych itp.)]}

Zabójcze ruchy są dobrym przykładem małego rozmiaru kodu i znacznej poprawy w porządkowaniu ruchów.

Większość algorytmów sztucznej inteligencji gier planszowych opiera się na http://en.wikipedia.org/wiki/Minmax MinMax. Celem jest zminimalizowanie ich opcji przy jednoczesnej maksymalizacji opcji. Chociaż w przypadku szachów jest to bardzo duży i kosztowny problem runtime. Aby to zmniejszyć, możesz połączyć minmax z bazą danych wcześniej rozegranych gier. Każda gra, która ma podobną pozycję na planszy i ma ustalony wzór, w jaki sposób ten układ został wygrany dla Twojego koloru, może być używana tak daleko, jak "analizowanie", gdzie się przenieść następny.

Jestem trochę zdezorientowany co masz na myśli przez improvement / code_size. Czy naprawdę masz na myśli poprawę / analizę runtime (big O(n) vs. o (n))? Jeśli tak jest, porozmawiaj z IBM i big blue lub zespołem Microsoft Parallels. Na PDC rozmawiałem z facetem (którego nazwisko Mi umyka), który demonstrował Mahjonga używając 8 rdzeni na przeciwnika i zdobył pierwsze miejsce w konkursie projektowania algorytmów gry (którego nazwisko również umyka mnie).

Nie wydaje mi się, żeby były jakieś "konserwowe" algorytmy tam zawsze wygrać szachy i zrobić to bardzo szybko. Sposób, w jaki musiałbyś to zrobić, to mieć każdą możliwą wcześniej zagraną grę zindeksowaną w bardzo dużej bazie danych opartej na Słowniku i wstępnie buforowaną analizę każdej gry. Byłby to algorytm bardzo compex i byłby bardzo słabym problemem poprawy / złożoności moim zdaniem.

Mogę być nieco poza tematem, ale "state of the art" programy szachowe używają MPI, takich jak Deep Blue dla ogromnej równoległej mocy.

Wystarczy wziąć pod uwagę niż równoległe przetwarzanie odgrywa wielką rolę we współczesnych szachach