Chess Optimizations

Question

ok, więc pracowałem nad moim programem szachowym przez chwilę i zaczynam uderzać w ścianę. Zrobiłem wszystkie standardowe optymalizacje (negascout, iteracyjne pogłębianie, ruchy zabójców, heurystyka historyczna, wyszukiwanie spokojne, ocena pozycji pionka, niektóre rozszerzenia wyszukiwania) i nie mam pomysłów!

Mam zamiar wkrótce zrobić wielowątkowe, co powinno dać mi dobry wzrost wydajności, ale poza tym są jakieś inne fajne sztuczki, które spotkaliście? rozważałem przejście na MDF (f), ale słyszałem, że jest to kłopot i naprawdę nie jest tego warte.

to, co najbardziej mnie interesuje, to jakiś algorytm uczenia się, ale nie wiem, czy ktoś zrobił to skutecznie z programem szachowym.

również, czy zmiana na tablicę bitów byłaby znacząca? Obecnie używam 0x88.

Answer 1

Zakładając, że "historia heurystyczna" zawiera jakąś bazę danych z przeszłych ruchów, algorytm uczenia się nie da ci więcej, chyba że gra wiele gier przeciwko temu samemu graczowi. Prawdopodobnie możesz osiągnąć więcej, klasyfikując gracza i poprawiając wybór ruchów z historycznej bazy danych.

Answer 2

Minęło dużo czasu, odkąd zrobiłem programowanie w dowolnym programie szachowym, ale w tym czasie deski bitowe dały znaczną poprawę. Poza tym nie mogę ci wiele doradzić. Czy oceniasz tylko pozycję pionków? Niektóre (nieznaczne) premie za pozycję lub ruchliwość niektórych kluczowych elementów mogą być w porządku.

nie jestem pewien co typu rzeczy chcesz go nauczyć jednak ...

Answer 3

wiem, że jeden poprawa że mówiono na kursach AI w uniwersytecie, gdzie ma ogromną bazę ruchów wykańczających . Więc mając wstępnie obliczoną bazę danych dla gier z niewielką liczbą figur. Tak więc, jeśli trafisz na pozycjonowanie zbliżone do końca w swoim wyszukiwaniu, zatrzymasz wyszukiwanie i przyjmiesz wstępnie obliczoną wartość, która poprawi wyniki wyszukiwania, takie jak dodatkowe pogłębienie, które możesz wykonać dla ważnych/krytycznych ruchów bez dużego wydatkowania czasu obliczeniowego. Wydaje mi się, że jest to również zmiana heurystyk w późnym stanie gry, ale nie jestem szachistą, więc nie znam dynamiki zakończenia gry.

Answer 4

Co do napiwków, wiem, że duże zyski można znaleźć w optymalizacji procedur generowania ruchów przed wszelkimi funkcjami ewaluacyjnymi. Wykonanie tej funkcji tak ciasno, jak to tylko możliwe, może dać ci 10% lub więcej poprawy w węzłach/sek.

Jeśli przenosisz się do bitboardów, poszukaj jakichś archiwów rec.games.chess.computer w przypadku niektórych z doktor Robert Hyatts starych postów na temat Crafty (całkiem pewny, że nie publikuje więcej). Lub pobierz najnowszą kopię z his FTP i zacznij kopać. Jestem prawie pewien, że byłaby to dla ciebie znacząca zmiana.

Answer 5

• Transpozycja Tabela
• Otwarcie Book
• End Bazy Tabela Gra
• Lepsza Static Board for liści Węzły
• Bitboards dla surowego Szybkości

Answer 6

ostrzegamy, coraz wyszukiwarki gra prawo w środowisku z gwintem może być królewski ból (I've tried it). Można to zrobić, ale z jakiegoś wyszukiwania literatury, które odtworzyłem jakiś czas temu, niezwykle trudno jest uzyskać jakiekolwiek przyspieszenie prędkości.

Answer 7

W ciągu ostatniego roku rozwoju mojego silnika szachowego (www.chessbin.com) przez większość czasu optymalizowano mój kod, aby umożliwić lepsze i szybsze wyszukiwanie ruchów. Przez ten czas nauczyłem się kilku sztuczek, którymi chciałbym się z wami podzielić.

wydajność

pomiarowe Zasadniczo można poprawić osiągi na dwa sposoby:

• Ocenić swoje węzły szybciej
• wyszukiwania mniej węzłów wymyślić samą odpowiedź

Twoim pierwszym problemem w optymalizacji kodu będzie pomiar. Skąd wiesz, że naprawdę zrobiłeś różnicę? Aby pomóc Ci w rozwiązaniu tego problemu, musisz upewnić się, że możesz zarejestrować niektóre statystyki podczas wyszukiwania ruchu. Te, które przechwytuję w moim silniku szachowym, to:

• Czas zakończenia wyszukiwania do został zakończony.
• Liczba węzłów poszukiwanej

To pozwoli ci odniesienia i przetestować zmiany. Najlepszym sposobem podejścia do testowania jest utworzenie kilku zapisanych gier z pozycji początkowej, środkowej i końcowej. Zapisz czas i liczbę szukanych węzłów w czerni i bieli. Po wprowadzeniu jakichkolwiek zmian zazwyczaj wykonuję testy przeciwko wyżej wymienionym zapisanym grami, aby sprawdzić, czy dokonałem ulepszeń w dwóch powyższych matrycach: liczba przeszukiwanych węzłów lub szybkość.

Aby jeszcze bardziej komplikować sytuację, po zmianie kodu można uruchomić silnik 3 razy i za każdym razem uzyskać 3 różne wyniki. Powiedzmy, że twój silnik szachowy znalazł najlepszy ruch w 9, 10 i 11 sekundach. To jest spread o około 20%. Czy ulepszyłeś silnik o 10% -20% lub po prostu zmieniłeś obciążenie swojego komputera? Skąd wiesz? Aby walczyć z tym, dodałem metody, które pozwolą mojemu silnikowi na grę przeciwko sobie, spowoduje to ruchy zarówno na biało, jak i na czarno. W ten sposób możesz przetestować nie tylko wariancję czasu nad jednym ruchem, ale także serię aż 50 ruchów w trakcie gry. Jeśli ostatnio gra trwała 10 minut, a teraz zajmuje 9, prawdopodobnie poprawiłeś swój silnik o 10%. Ponowne uruchomienie testu powinno to potwierdzić.

Znalezienie Wydajność Zyskuje

Teraz, gdy wiemy, jak mierzyć wzrost wydajności pozwala omówić jak zidentyfikować potencjalne zyski wydajności.

Jeśli jesteś w środowisku .NET, profiler .NET będzie twoim przyjacielem. Jeśli masz wersję Visual Studio dla programistów, jest ona dostępna za darmo, ale są też inne narzędzia innych firm, z których możesz korzystać. To narzędzie pozwoliło mi zaoszczędzić wiele godzin pracy, ponieważ dzięki temu dowiesz się, gdzie silnik spędza większość czasu i pozwala skoncentrować się na problematycznych miejscach. Jeśli nie masz narzędzia do profilowania, być może będziesz musiał w jakiś sposób zarejestrować znaczniki czasu, ponieważ twój silnik przechodzi przez różne etapy. Nie sugeruję tego. W tym przypadku dobry profiler jest wart swojej wagi w złocie. Red Gate ANTS Profiler jest drogi, ale najlepszy, jaki kiedykolwiek wypróbowałem. Jeśli nie możesz sobie na to pozwolić, skorzystaj przynajmniej z 14-dniowej wersji próbnej.

Twój profiler będzie niemiły zidentyfikować rzeczy dla ciebie, ale oto kilka małych lekcje nauczyłem pracy z C#:

• Zmienia wszystko prywatny
• Cokolwiek nie można zrobić prywatny, należy to uszczelnione
• Możliwe jest wykonanie wielu metod statycznych, takich jak .
• Nie twórz metod rozmownych, jedna metoda jest dłuższa niż 4 mniejsze .
• Tablica szachowa przechowywana jako tablica [8] [8] jest wolniejsza niż tablica [64]
• Zastępuje int, jeśli to możliwe, bajtem.
• Możliwe tylko po powrocie z Twoich metod już od .
• Stosy są lepsze niż listy
• Tablice są lepsze niż stosy i listy .
• Jeśli możesz określić rozmiar listy , zanim ją zapełnisz.
• Rzucanie, boksowanie, un-boxing jest złe.

dalszego wzrostu wydajności:

znajdę generacji przenieść i kolejność jest bardzo ważna. Jednak tutaj jest problem, jak widzę. Jeśli ocenisz wynik każdego ruchu przed posortowaniem i uruchomieniem Alpha Beta, będziesz w stanie zoptymalizować porządek ruchów, dzięki czemu uzyskasz bardzo szybkie wyłączenia Alfa Beta. Jest tak dlatego, że najpierw będziesz w stanie wypróbować najlepszy ruch. Jednak czas poświęcony na ocenę każdego ruchu zostanie zmarnowany. Na przykład, możesz ocenić wynik na 20 ruchach, posortować swoje ruchy wypróbować pierwsze 2 i odebrać odcięcie w ruchu nr 2. Teoretycznie straciłeś czas na pozostałe 18 ruchów.

Z drugiej strony, jeśli zrobisz lżejszą i znacznie szybszą ocenę, powiedz po prostu przechwytuj, twój sort nie będzie aż tak dobry i będziesz musiał przeszukać więcej węzłów (do 60% więcej). Z drugiej strony nie zrobiłbyś ciężkiej oceny każdego możliwego ruchu. Ogólnie rzecz biorąc to podejście jest zwykle szybsze zwykle szybsze.

Znalezienie idealnej równowagi pomiędzy posiadaniem wystarczającej ilości informacji do dobrego sortowania a brakiem dodatkowej pracy na ruchach, których nie wykorzystasz, pozwoli ci znaleźć ogromne zyski w swoim algorytmie wyszukiwania. Co więcej, jeśli wybierzesz uboższe podejście do sortowania, najpierw powinieneś zacząć od płytszego wyszukiwania, powiedz, że musisz przejść 3, posortuj swój ruch, zanim przejdziesz do głębszego wyszukiwania (często nazywa się to Iteracyjnym Pogłębieniem). To znacznie poprawi twój sort i pozwoli na przeszukiwanie znacznie mniej ruchów.

Answer 8

Odpowiedzi na stare pytanie.

Zakładając, że masz już działającą tabelę transpozycji.

Redukcja opóźnionego ruchu. To dało mój program około 100 punktów elo i jest bardzo łatwe do wdrożenia.

Z mojego doświadczenia wynika, że ​​jeśli implementacja nie jest bardzo nieefektywna, faktyczna reprezentacja planszy (0x88, płyta bitowa itp.) Nie jest tak ważna.

Chociaż można sparaliżować silnik szachowy o złej wydajności, generator błyskawiczny ruch sam w sobie nie sprawi, że program będzie dobry.

Zastosowane triki wyszukiwania i funkcja oceny są decydującymi czynnikami decydującymi o ogólnej sile.

Najważniejszymi częściami do tej pory oceny są: Materiał, Przekazywane pionki, Król bezpieczeństwa i Pionek.

Najważniejsze elementy wyszukiwania to: Null Move Pruning, Check Extension i Late Late Reduction.

Twój program może przyjść długą i długą drogą tylko na tych prostych technikach!

Answer 9

To dość stare pytanie, szukałem tylko pytań na temat szachów i znalazłem ten bez odpowiedzi. Cóż, teraz może nie być dla ciebie pomocne, ale może okazać się pomocne dla innych użytkowników.

Nie widziałem tabeli przycinania o transpozycji zerowej, transpozycji .. używasz ich? Dadzą Ci duży impuls ...

Jedną z rzeczy, która dała mi duży impuls, było zminimalizowanie odgałęzień warunkowych ... Wiele rzeczy można wstępnie obliczyć. Szukaj takich możliwości.

Większość współczesnych komputerów ma wiele rdzeni, więc dobrze byłoby zrobić wielowątkowość. Niekoniecznie musisz przejść do MDF (f) w tym celu.

Nie będę sugerował przeniesienia twojego kodu na bitboard. To po prostu za dużo pracy. Nawet bitboards mogą dać impuls na maszynach 64-bitowych.

Wreszcie i co najważniejsze literatura szachowa dominuje wszelkie optymalizacje, których możemy użyć. optymalizacja to za dużo pracy. Spójrz na silniki szachowe o otwartym kodzie źródłowym, szczególnie podstępne i owoce/toga. Początkowo owoce były pierwotnie otwarte.

Answer 10

Profil i punkt odniesienia. Teoretyczne optymalizacje są świetne, ale jeśli nie mierzysz wpływu każdej wprowadzanej zmiany na wydajność, nie będziesz wiedzieć, czy twoja praca poprawia lub pogarsza szybkość końcowego kodu.

Spróbuj ograniczyć karę dla siebie za wypróbowanie różnych algorytmów. Ułatw sobie testowanie różnych implementacji algorytmów względem siebie. Oznacza to, że można łatwo zbudować wersję PVS kodu, a także wersję NegaScout.

Znajdź gorące miejsca. Refaktor. Przepisz w montażu, jeśli to konieczne. Powtarzać.

Answer 11

Dobra zmiana porządku!

Stare pytanie, ale te same techniki obowiązują teraz jak 5 lat temu. Czy nie wszyscy piszemy nasze własne silniki szachowe, mam własną nazwę "Norwegian Gambit", która, mam nadzieję, ostatecznie będzie konkurować z innymi silnikami Java w CCRL. Ja, jak wielu innych, używam Sztokfiszów do pomysłów, ponieważ jest tak pięknie napisany i otwarty. Ich struktura testowa Fishtest i jej społeczność daje również mnóstwo dobrych rad. Warto porównać wyniki oceny z tym, co dostaje Sztokfisz, ponieważ to, jak oceniać, jest prawdopodobnie największą niewiadomą w programowaniu szachowym, a Sztokfisz znika z wielu tradycyjnych złudzeń, które stały się miejskimi legendami (jak podwójny bonus biskupa). Największą różnicą było jednak to, że po wdrożeniu tych samych technik, o których wspomniałeś, Negascout, TT, LMR, zacząłem używać Stockfish do porównania i zauważyłem, że dla tej samej głębi Sztokfisz przeszukiwano znacznie mniej ruchów niż ja (z powodu zamawiania ruchu).

Essentials Move zamawiania

Jedna rzecz, która jest łatwo zapomnieć to dobre posunięcie zamawiania. Aby odcięcie Alpha Beta było efektywne, należy najpierw uzyskać najlepsze ruchy. Z drugiej strony może to być również czasochłonne, dlatego ważne jest, aby robić to tylko w razie potrzeby.

1. stół Transpozycja
2. Uporządkuj promocje i dobre przechwytuje by ich zysk
3. zabójca przemieszcza
4. ruchy, które powodują czeku na przeciwnika
5. Historia heurystyki
6. cichych ruchów - według wartości PSQT

Sortowanie powinno być wykonane w razie potrzeby, zwykle ja t wystarczy sortować przechwytywania, a następnie można uruchomić droższe sortowanie kontroli i PSQT tylko w razie potrzeby.

O Java/C# vs C/C++/Konstrukcja

techniki programowania są takie same jak dla Javy w doskonałej odpowiedzi Adam Berent, którzy używali C#. Oprócz swojej listy chciałbym wspomnieć o unikaniu tablic Object, a raczej używać wielu tablic prymitywów, ale w przeciwieństwie do jego sugestii używania bajtów, stwierdzam, że w 64-bitowej wersji java niewiele można zapisać, używając bajtu i int zamiast 64-bitowego. Przeszedłem również drogę przepisywania na C/C++/Assembly i nie mam żadnego zysku z wydajności. Użyłem kodu złożenia dla instrukcji bitscan, takich jak LZCNT i POPCNT, ale później odkryłem, że Java 8 również używa tych zamiast metod w obiekcie Long. Ku mojemu zaskoczeniu Java jest szybsza, wirtualna maszyna Java 8 wydaje się lepiej optymalizować zadanie niż kompilator języka C.

Answer 12

Późne odpowiedź, ale może to komuś pomóc:

Biorąc pod uwagę wszystkie wymienione wy ​​optymalizacje, 1450 ELO jest bardzo niska. Domyślam się, że coś jest nie tak z twoim kodem. Czy jesteś:

1. napisał perft rutyna i prowadził ją przez zestaw pozycji? Wszystkie testy powinny przejść, więc wiesz, że twój generator ruchu jest wolny od błędów. Jeśli nie masz tego, nie ma sensu mówić o ELO.

2. Napisałem rutynę mirrorBoard i przeprowadziłem kod oceny przez zestaw pozycji? Wynik powinien być taki sam dla normalnych i dublowanych pozycji, w przeciwnym razie masz błąd w eval.

3. Czy masz hashtable (aka table transposition)? Jeśli nie, jest to koniecznością. Pomoże to w wyszukiwaniu i zamawianiu ruchów, dając brutalną różnicę w prędkości.

4. W jaki sposób realizujesz zamawianie akcji? To odwołuje się do punktu 3.

5. Czy wdrożyłeś protokół UCI? Czy twoja funkcja move parsing działa poprawnie?Miałem problem jak to w moim silniku:

   /* Parses a uci move string and return a Board object */ 
       Board parseUCIMoves(String moves)// e2e4 c7c5 g1f3 ...{ 
        //... 
        if (someMove.equals("e1g1") || someMove.equals("e1c1")) 
         //apply proper castle 
       //... 
   } 
   

Czasami silnik rozbił się podczas gry w meczu, a ja myślałem, że to wina GUI, ponieważ wszystkie testy perft były ok. Znalezienie błędu przez szczęście zajęło mi tydzień. Tak więc, przetestuj wszystko.

Dla (1) możesz przeszukać każdą pozycję na głębokość 6. Używam pliku z ~ 1000 pozycjami. Zobacz tutaj: https://chessprogramming.wikispaces.com/Perft

Dla (2) potrzebujesz tylko pliku z milionami pozycji (tylko ciąg FEN).

Biorąc pod uwagę powyższe i bardzo podstawową funkcję oceny (materiał, stoły kwadratowe, pionki, król bezpieczeństwa) powinien grać na + -2000 ELO.